bundles/org.simantics.db.impl/src/org/simantics/db/impl/graph/TIntArrayListInternal.java

   1 ///////////////////////////////////////////////////////////////////////////////\r
   2 // Copyright (c) 2001, Eric D. Friedman All Rights Reserved.\r
   3 // Copyright (c) 2009, Rob Eden All Rights Reserved.\r
   4 // Copyright (c) 2009, Jeff Randall All Rights Reserved.\r
   5 //\r
   6 // This library is free software; you can redistribute it and/or\r
   7 // modify it under the terms of the GNU Lesser General Public\r
   8 // License as published by the Free Software Foundation; either\r
   9 // version 2.1 of the License, or (at your option) any later version.\r
  10 //\r
  11 // This library is distributed in the hope that it will be useful,\r
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of\r
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\r
  14 // GNU General Public License for more details.\r
  15 //\r
  16 // You should have received a copy of the GNU Lesser General Public\r
  17 // License along with this program; if not, write to the Free Software\r
  18 // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.\r
  19 ///////////////////////////////////////////////////////////////////////////////\r
  20 \r
  21 package org.simantics.db.impl.graph;\r
  22 \r
  23 import gnu.trove.TIntCollection;\r
  24 import gnu.trove.function.TIntFunction;\r
  25 import gnu.trove.impl.Constants;\r
  26 import gnu.trove.impl.HashFunctions;\r
  27 import gnu.trove.iterator.TIntIterator;\r
  28 import gnu.trove.procedure.TIntProcedure;\r
  29 \r
  30 import java.io.IOException;\r
  31 import java.io.ObjectInput;\r
  32 import java.io.ObjectOutput;\r
  33 import java.util.Arrays;\r
  34 import java.util.Collection;\r
  35 import java.util.ConcurrentModificationException;\r
  36 import java.util.NoSuchElementException;\r
  37 import java.util.Random;\r
  38 \r
  39 \r
  40 //////////////////////////////////////////////////\r
  41 // THIS IS A GENERATED CLASS. DO NOT HAND EDIT! //\r
  42 //////////////////////////////////////////////////\r
  43 \r
  44 \r
  45 /**\r
  46  * A resizable, array-backed list of int primitives.\r
  47  */\r
  48 public class TIntArrayListInternal {\r
  49 \r
  50     /** the data of the list */\r
  51     protected int[] _data;\r
  52 \r
  53     /** the index after the last entry in the list */\r
  54     protected int _pos;\r
  55 \r
  56     /** the default capacity for new lists */\r
  57     protected static final int DEFAULT_CAPACITY = Constants.DEFAULT_CAPACITY;\r
  58 \r
  59     /** the int value that represents null */\r
  60     protected int no_entry_value;\r
  61 \r
  62 \r
  63     /**\r
  64      * Creates a new <code>TIntArrayList</code> instance with the\r
  65      * default capacity.\r
  66      */\r
  67     @SuppressWarnings({"RedundantCast"})\r
  68     public TIntArrayListInternal() {\r
  69         this( DEFAULT_CAPACITY, ( int ) 0 );\r
  70     }\r
  71 \r
  72 \r
  73     /**\r
  74      * Creates a new <code>TIntArrayList</code> instance with the\r
  75      * specified capacity.\r
  76      *\r
  77      * @param capacity an <code>int</code> value\r
  78      */\r
  79     @SuppressWarnings({"RedundantCast"})\r
  80     public TIntArrayListInternal( int capacity ) {\r
  81         this( capacity, ( int ) 0 );\r
  82     }\r
  83 \r
  84 \r
  85     /**\r
  86      * Creates a new <code>TIntArrayList</code> instance with the\r
  87      * specified capacity.\r
  88      *\r
  89      * @param capacity an <code>int</code> value\r
  90      * @param no_entry_value an <code>int</code> value that represents null.\r
  91      */\r
  92     public TIntArrayListInternal( int capacity, int no_entry_value ) {\r
  93         _data = new int[ capacity ];\r
  94         _pos = 0;\r
  95         this.no_entry_value = no_entry_value;\r
  96     }\r
  97 \r
  98     /**\r
  99      * Creates a new <code>TIntArrayList</code> instance that contains\r
 100      * a copy of the collection passed to us.\r
 101      *\r
 102      * @param collection the collection to copy\r
 103      */\r
 104     public TIntArrayListInternal ( TIntCollection collection ) {\r
 105         this( collection.size() );\r
 106         addAll( collection ); \r
 107     }\r
 108 \r
 109 \r
 110     /**\r
 111      * Creates a new <code>TIntArrayList</code> instance whose\r
 112      * capacity is the length of <tt>values</tt> array and whose\r
 113      * initial contents are the specified values.\r
 114      * <p>\r
 115      * A defensive copy of the given values is held by the new instance.\r
 116      *\r
 117      * @param values an <code>int[]</code> value\r
 118      */\r
 119     public TIntArrayListInternal( int[] values ) {\r
 120         this( values.length );\r
 121         add( values );\r
 122     }\r
 123 \r
 124     protected TIntArrayListInternal(int[] values, int no_entry_value, boolean wrap) {\r
 125         if (!wrap)\r
 126             throw new IllegalStateException("Wrong call");\r
 127 \r
 128         if (values == null)\r
 129             throw new IllegalArgumentException("values can not be null");\r
 130 \r
 131         _data = values;\r
 132         _pos = values.length;\r
 133         this.no_entry_value = no_entry_value;\r
 134     }\r
 135 \r
 136     /**\r
 137      * Returns a primitive List implementation that wraps around the given primitive array.\r
 138      * <p/>\r
 139      * NOTE: mutating operation are allowed as long as the List does not grow. In that case\r
 140      * an IllegalStateException will be thrown\r
 141      *\r
 142      * @param values\r
 143      * @return\r
 144      */\r
 145     public static TIntArrayListInternal wrap(int[] values) {\r
 146         return wrap(values, ( int ) 0);\r
 147     }\r
 148 \r
 149     /**\r
 150      * Returns a primitive List implementation that wraps around the given primitive array.\r
 151      * <p/>\r
 152      * NOTE: mutating operation are allowed as long as the List does not grow. In that case\r
 153      * an IllegalStateException will be thrown\r
 154      *\r
 155      * @param values\r
 156      * @param no_entry_value\r
 157      * @return\r
 158      */\r
 159     public static TIntArrayListInternal wrap(int[] values, int no_entry_value) {\r
 160         return new TIntArrayListInternal(values, no_entry_value, true) {\r
 161             /**\r
 162              * Growing the wrapped external array is not allow\r
 163              */\r
 164             @Override\r
 165             public void ensureCapacity(int capacity) {\r
 166                 if (capacity > _data.length)\r
 167                     throw new IllegalStateException("Can not grow ArrayList wrapped external array");\r
 168             }\r
 169         };\r
 170     }\r
 171 \r
 172     /** {@inheritDoc} */\r
 173     public int getNoEntryValue() {\r
 174         return no_entry_value;\r
 175     }\r
 176 \r
 177 \r
 178     // sizing\r
 179 \r
 180     /**\r
 181      * Grow the internal array as needed to accommodate the specified number of elements.\r
 182      * The size of the array bytes on each resize unless capacity requires more than twice\r
 183      * the current capacity.\r
 184      */\r
 185     public void ensureCapacity( int capacity ) {\r
 186         if ( capacity > _data.length ) {\r
 187             int newCap = Math.max( _data.length << 1, capacity );\r
 188             int[] tmp = new int[ newCap ];\r
 189             System.arraycopy( _data, 0, tmp, 0, _data.length );\r
 190             _data = tmp;\r
 191         }\r
 192     }\r
 193 \r
 194 \r
 195     /** {@inheritDoc} */\r
 196     public int sizeInternal() {\r
 197         return _pos;\r
 198     }\r
 199 \r
 200 \r
 201     /** {@inheritDoc} */\r
 202     public boolean isEmpty() {\r
 203         return _pos == 0;\r
 204     }\r
 205 \r
 206 \r
 207     /**\r
 208      * Sheds any excess capacity above and beyond the current size of the list.\r
 209      */\r
 210     public void trimToSize() {\r
 211         if ( _data.length > sizeInternal() ) {\r
 212             int[] tmp = new int[ sizeInternal() ];\r
 213             toArray( tmp, 0, tmp.length );\r
 214             _data = tmp;\r
 215         }\r
 216     }\r
 217 \r
 218 \r
 219     // modifying\r
 220 \r
 221     /** {@inheritDoc} */\r
 222     public boolean add( int val ) {\r
 223         ensureCapacity( _pos + 1 );\r
 224         _data[ _pos++ ] = val;\r
 225         return true;\r
 226     }\r
 227 \r
 228 \r
 229     /** {@inheritDoc} */\r
 230     public void add( int[] vals ) {\r
 231         add( vals, 0, vals.length );\r
 232     }\r
 233 \r
 234 \r
 235     /** {@inheritDoc} */\r
 236     public void add( int[] vals, int offset, int length ) {\r
 237         ensureCapacity( _pos + length );\r
 238         System.arraycopy( vals, offset, _data, _pos, length );\r
 239         _pos += length;\r
 240     }\r
 241 \r
 242 \r
 243     /** {@inheritDoc} */\r
 244     public void insert( int offset, int value ) {\r
 245         if ( offset == _pos ) {\r
 246             add( value );\r
 247             return;\r
 248         }\r
 249         ensureCapacity( _pos + 1 );\r
 250         // shift right\r
 251         System.arraycopy( _data, offset, _data, offset + 1, _pos - offset );\r
 252         // insert\r
 253         _data[ offset ] = value;\r
 254         _pos++;\r
 255     }\r
 256 \r
 257 \r
 258     /** {@inheritDoc} */\r
 259     public void insert( int offset, int[] values ) {\r
 260         insert( offset, values, 0, values.length );\r
 261     }\r
 262 \r
 263 \r
 264     /** {@inheritDoc} */\r
 265     public void insert( int offset, int[] values, int valOffset, int len ) {\r
 266         if ( offset == _pos ) {\r
 267             add( values, valOffset, len );\r
 268             return;\r
 269         }\r
 270 \r
 271         ensureCapacity( _pos + len );\r
 272         // shift right\r
 273         System.arraycopy( _data, offset, _data, offset + len, _pos - offset );\r
 274         // insert\r
 275         System.arraycopy( values, valOffset, _data, offset, len );\r
 276         _pos += len;\r
 277     }\r
 278 \r
 279 \r
 280     /** {@inheritDoc} */\r
 281     public int getAt( int offset ) {\r
 282         if ( offset >= _pos ) {\r
 283             throw new ArrayIndexOutOfBoundsException( offset );\r
 284         }\r
 285         return _data[ offset ];\r
 286     }\r
 287 \r
 288 \r
 289     /**\r
 290      * Returns the value at the specified offset without doing any bounds checking.\r
 291      */\r
 292     public int getQuick( int offset ) {\r
 293         return _data[ offset ];\r
 294     }\r
 295 \r
 296 \r
 297     /** {@inheritDoc} */\r
 298     public int set( int offset, int val ) {\r
 299         if ( offset >= _pos ) {\r
 300             throw new ArrayIndexOutOfBoundsException( offset );\r
 301         }\r
 302 \r
 303                 int prev_val = _data[ offset ];\r
 304         _data[ offset ] = val;\r
 305                 return prev_val;\r
 306     }\r
 307 \r
 308 \r
 309     /** {@inheritDoc} */\r
 310     public int replace( int offset, int val ) {\r
 311         if ( offset >= _pos ) {\r
 312             throw new ArrayIndexOutOfBoundsException( offset );\r
 313         }\r
 314         int old = _data[ offset ];\r
 315         _data[ offset ] = val;\r
 316         return old;\r
 317     }\r
 318 \r
 319 \r
 320     /** {@inheritDoc} */\r
 321     public void set( int offset, int[] values ) {\r
 322         set( offset, values, 0, values.length );\r
 323     }\r
 324 \r
 325 \r
 326     /** {@inheritDoc} */\r
 327     public void set( int offset, int[] values, int valOffset, int length ) {\r
 328         if ( offset < 0 || offset + length > _pos ) {\r
 329             throw new ArrayIndexOutOfBoundsException( offset );\r
 330         }\r
 331         System.arraycopy( values, valOffset, _data, offset, length );\r
 332     }\r
 333 \r
 334 \r
 335     /**\r
 336      * Sets the value at the specified offset without doing any bounds checking.\r
 337      */\r
 338     public void setQuick( int offset, int val ) {\r
 339         _data[ offset ] = val;\r
 340     }\r
 341 \r
 342 \r
 343     /** {@inheritDoc} */\r
 344     public void clear() {\r
 345         clear( DEFAULT_CAPACITY );\r
 346     }\r
 347 \r
 348 \r
 349     /**\r
 350      * Flushes the internal state of the list, setting the capacity of the empty list to\r
 351      * <tt>capacity</tt>.\r
 352      */\r
 353     public void clear( int capacity ) {\r
 354         _data = new int[ capacity ];\r
 355         _pos = 0;\r
 356     }\r
 357 \r
 358 \r
 359     /**\r
 360      * Sets the size of the list to 0, but does not change its capacity. This method can\r
 361      * be used as an alternative to the {@link #clear()} method if you want to recycle a\r
 362      * list without allocating new backing arrays.\r
 363      */\r
 364     public void reset() {\r
 365         _pos = 0;\r
 366         Arrays.fill( _data, no_entry_value );\r
 367     }\r
 368 \r
 369 \r
 370     /**\r
 371      * Sets the size of the list to 0, but does not change its capacity. This method can\r
 372      * be used as an alternative to the {@link #clear()} method if you want to recycle a\r
 373      * list without allocating new backing arrays. This method differs from\r
 374      * {@link #reset()} in that it does not clear the old values in the backing array.\r
 375      * Thus, it is possible for getQuick to return stale data if this method is used and\r
 376      * the caller is careless about bounds checking.\r
 377      */\r
 378     public void resetQuick() {\r
 379         _pos = 0;\r
 380     }\r
 381 \r
 382 \r
 383     /** {@inheritDoc} */\r
 384     public boolean removeValue( int value ) {\r
 385         for ( int index = 0; index < _pos; index++ ) {\r
 386             if ( value == _data[index]  ) {\r
 387                 remove( index, 1 );\r
 388                 return true;\r
 389             }\r
 390         }\r
 391         return false;\r
 392     }\r
 393 \r
 394 \r
 395     /** {@inheritDoc} */\r
 396     public int removeAt( int offset ) {\r
 397         int old = getAt( offset );\r
 398         remove( offset, 1 );\r
 399         return old;\r
 400     }\r
 401 \r
 402 \r
 403     /** {@inheritDoc} */\r
 404     public void remove( int offset, int length ) {\r
 405                 if ( length == 0 ) return;\r
 406         if ( offset < 0 || offset >= _pos ) {\r
 407             throw new ArrayIndexOutOfBoundsException(offset);\r
 408         }\r
 409 \r
 410         if ( offset == 0 ) {\r
 411             // data at the front\r
 412             System.arraycopy( _data, length, _data, 0, _pos - length );\r
 413         }\r
 414         else if ( _pos - length == offset ) {\r
 415             // no copy to make, decrementing pos "deletes" values at\r
 416             // the end\r
 417         }\r
 418         else {\r
 419             // data in the middle\r
 420             System.arraycopy( _data, offset + length, _data, offset,\r
 421                 _pos - ( offset + length ) );\r
 422         }\r
 423         _pos -= length;\r
 424         // no need to clear old values beyond _pos, because this is a\r
 425         // primitive collection and 0 takes as much room as any other\r
 426         // value\r
 427     }\r
 428 \r
 429 \r
 430     /** {@inheritDoc} */\r
 431     public TIntIterator iteratorInternal() {\r
 432         return new TIntArrayIterator( 0 );\r
 433     }\r
 434 \r
 435 \r
 436     /** {@inheritDoc} */\r
 437     public boolean containsAll( Collection<?> collection ) {\r
 438         for ( Object element : collection ) {\r
 439             if ( element instanceof Integer ) {\r
 440                 int c = ( ( Integer ) element ).intValue();\r
 441                 if ( ! contains( c ) ) {\r
 442                     return false;\r
 443                 }\r
 444             } else {\r
 445                 return false;\r
 446             }\r
 447 \r
 448         }\r
 449         return true;\r
 450     }\r
 451 \r
 452 \r
 453     /** {@inheritDoc} */\r
 454     public boolean containsAll( TIntCollection collection ) {\r
 455         if ( this == collection ) {\r
 456             return true;\r
 457         }\r
 458         TIntIterator iter = collection.iterator();\r
 459         while ( iter.hasNext() ) {\r
 460             int element = iter.next();\r
 461             if ( ! contains( element ) ) {\r
 462                 return false;\r
 463             }\r
 464         }\r
 465         return true;\r
 466     }\r
 467 \r
 468 \r
 469     /** {@inheritDoc} */\r
 470     public boolean containsAll( int[] array ) {\r
 471         for ( int i = array.length; i-- > 0; ) {\r
 472             if ( ! contains( array[i] ) ) {\r
 473                 return false;\r
 474             }\r
 475         }\r
 476         return true;\r
 477     }\r
 478 \r
 479 \r
 480 //    /** {@inheritDoc} */\r
 481 //    public boolean addAll( Collection<? extends Integer> collection ) {\r
 482 //        boolean changed = false;\r
 483 //        for ( Integer element : collection ) {\r
 484 //            int e = element.intValue();\r
 485 //            if ( add( e ) ) {\r
 486 //                changed = true;\r
 487 //            }\r
 488 //        }\r
 489 //        return changed;\r
 490 //    }\r
 491 \r
 492 \r
 493     /** {@inheritDoc} */\r
 494     public boolean addAll( TIntCollection collection ) {\r
 495         boolean changed = false;\r
 496         TIntIterator iter = collection.iterator();\r
 497         while ( iter.hasNext() ) {\r
 498             int element = iter.next();\r
 499             if ( add( element ) ) {\r
 500                 changed = true;\r
 501             }\r
 502         }\r
 503         return changed;\r
 504     }\r
 505 \r
 506 \r
 507     /** {@inheritDoc} */\r
 508     public boolean addAll( int[] array ) {\r
 509         boolean changed = false;\r
 510         for ( int element : array ) {\r
 511             if ( add( element ) ) {\r
 512                 changed = true;\r
 513             }\r
 514         }\r
 515         return changed;\r
 516     }\r
 517 \r
 518 \r
 519     /** {@inheritDoc} */\r
 520     @SuppressWarnings({"SuspiciousMethodCalls"})\r
 521     public boolean retainAll( Collection<?> collection ) {\r
 522         boolean modified = false;\r
 523             TIntIterator iter = iteratorInternal();\r
 524             while ( iter.hasNext() ) {\r
 525                 if ( ! collection.contains( Integer.valueOf ( iter.next() ) ) ) {\r
 526                         iter.remove();\r
 527                         modified = true;\r
 528                 }\r
 529             }\r
 530             return modified;\r
 531     }\r
 532 \r
 533 \r
 534     /** {@inheritDoc} */\r
 535     public boolean retainAll( TIntCollection collection ) {\r
 536         if ( this == collection ) {\r
 537             return false;\r
 538         }\r
 539         boolean modified = false;\r
 540             TIntIterator iter = iteratorInternal();\r
 541             while ( iter.hasNext() ) {\r
 542                 if ( ! collection.contains( iter.next() ) ) {\r
 543                         iter.remove();\r
 544                         modified = true;\r
 545                 }\r
 546             }\r
 547             return modified;\r
 548     }\r
 549 \r
 550 \r
 551     /** {@inheritDoc} */\r
 552     public boolean retainAll( int[] array ) {\r
 553         boolean changed = false;\r
 554         Arrays.sort( array );\r
 555         int[] data = _data;\r
 556 \r
 557         for ( int i = _pos; i-- > 0; ) {\r
 558             if ( Arrays.binarySearch( array, data[i] ) < 0 ) {\r
 559                 remove( i, 1 );\r
 560                 changed = true;\r
 561             }\r
 562         }\r
 563         return changed;\r
 564     }\r
 565 \r
 566 \r
 567     /** {@inheritDoc} */\r
 568     public boolean removeAll( Collection<?> collection ) {\r
 569         boolean changed = false;\r
 570         for ( Object element : collection ) {\r
 571             if ( element instanceof Integer ) {\r
 572                 int c = ( ( Integer ) element ).intValue();\r
 573                 if ( removeValue( c ) ) {\r
 574                     changed = true;\r
 575                 }\r
 576             }\r
 577         }\r
 578         return changed;\r
 579     }\r
 580 \r
 581 \r
 582     /** {@inheritDoc} */\r
 583     public boolean removeAll( TIntCollection collection ) {\r
 584         if ( collection == this ) {\r
 585             clear();\r
 586             return true;\r
 587         }\r
 588         boolean changed = false;\r
 589         TIntIterator iter = collection.iterator();\r
 590         while ( iter.hasNext() ) {\r
 591             int element = iter.next();\r
 592             if ( removeValue( element ) ) {\r
 593                 changed = true;\r
 594             }\r
 595         }\r
 596         return changed;\r
 597     }\r
 598 \r
 599 \r
 600     /** {@inheritDoc} */\r
 601     public boolean removeAll( int[] array ) {\r
 602         boolean changed = false;\r
 603         for ( int i = array.length; i-- > 0; ) {\r
 604             if ( removeValue(array[i]) ) {\r
 605                 changed = true;\r
 606             }\r
 607         }\r
 608         return changed;\r
 609     }\r
 610 \r
 611 \r
 612     /** {@inheritDoc} */\r
 613     public void transformValues( TIntFunction function ) {\r
 614         for ( int i = _pos; i-- > 0; ) {\r
 615             _data[ i ] = function.execute( _data[ i ] );\r
 616         }\r
 617     }\r
 618 \r
 619 \r
 620     /** {@inheritDoc} */\r
 621     public void reverse() {\r
 622         reverse( 0, _pos );\r
 623     }\r
 624 \r
 625 \r
 626     /** {@inheritDoc} */\r
 627     public void reverse( int from, int to ) {\r
 628         if ( from == to ) {\r
 629             return;             // nothing to do\r
 630         }\r
 631         if ( from > to ) {\r
 632             throw new IllegalArgumentException( "from cannot be greater than to" );\r
 633         }\r
 634         for ( int i = from, j = to - 1; i < j; i++, j-- ) {\r
 635             swap( i, j );\r
 636         }\r
 637     }\r
 638 \r
 639 \r
 640     /** {@inheritDoc} */\r
 641     public void shuffle( Random rand ) {\r
 642         for ( int i = _pos; i-- > 1; ) {\r
 643             swap( i, rand.nextInt( i ) );\r
 644         }\r
 645     }\r
 646 \r
 647 \r
 648     /**\r
 649      * Swap the values at offsets <tt>i</tt> and <tt>j</tt>.\r
 650      *\r
 651      * @param i an offset into the data array\r
 652      * @param j an offset into the data array\r
 653      */\r
 654     private void swap( int i, int j ) {\r
 655         int tmp = _data[ i ];\r
 656         _data[ i ] = _data[ j ];\r
 657         _data[ j ] = tmp;\r
 658     }\r
 659 \r
 660 \r
 661     // copying\r
 662 \r
 663 //    /** {@inheritDoc} */\r
 664 //    public TIntList subList( int begin, int end ) {\r
 665 //      if ( end < begin ) {\r
 666 //                      throw new IllegalArgumentException( "end index " + end +\r
 667 //                              " greater than begin index " + begin );\r
 668 //              }\r
 669 //              if ( begin < 0 ) {\r
 670 //                      throw new IndexOutOfBoundsException( "begin index can not be < 0" );\r
 671 //              }\r
 672 //              if ( end > _data.length ) {\r
 673 //                      throw new IndexOutOfBoundsException( "end index < " + _data.length );\r
 674 //              }\r
 675 //              TIntArrayListInternal list = new TIntArrayListInternal( end - begin );\r
 676 //        for ( int i = begin; i < end; i++ ) {\r
 677 //              list.add( _data[ i ] );\r
 678 //        }\r
 679 //        return list;\r
 680 //    }\r
 681 \r
 682 \r
 683     /** {@inheritDoc} */\r
 684     public int[] toArrayInternal() {\r
 685         return toArray( 0, _pos );\r
 686     }\r
 687 \r
 688 \r
 689     /** {@inheritDoc} */\r
 690     public int[] toArray( int offset, int len ) {\r
 691         int[] rv = new int[ len ];\r
 692         toArray( rv, offset, len );\r
 693         return rv;\r
 694     }\r
 695 \r
 696 \r
 697     /** {@inheritDoc} */\r
 698     public int[] toArray( int[] dest ) {\r
 699         int len = dest.length;\r
 700         if ( dest.length > _pos ) {\r
 701             len = _pos;\r
 702             dest[len] = no_entry_value;\r
 703         }\r
 704         toArray( dest, 0, len );\r
 705         return dest;\r
 706     }\r
 707 \r
 708 \r
 709     /** {@inheritDoc} */\r
 710     public int[] toArray( int[] dest, int offset, int len ) {\r
 711         if ( len == 0 ) {\r
 712             return dest;             // nothing to copy\r
 713         }\r
 714         if ( offset < 0 || offset >= _pos ) {\r
 715             throw new ArrayIndexOutOfBoundsException( offset );\r
 716         }\r
 717         System.arraycopy( _data, offset, dest, 0, len );\r
 718         return dest;\r
 719     }\r
 720 \r
 721 \r
 722     /** {@inheritDoc} */\r
 723     public int[] toArray( int[] dest, int source_pos, int dest_pos, int len ) {\r
 724         if ( len == 0 ) {\r
 725             return dest;             // nothing to copy\r
 726         }\r
 727         if ( source_pos < 0 || source_pos >= _pos ) {\r
 728             throw new ArrayIndexOutOfBoundsException( source_pos );\r
 729         }\r
 730         System.arraycopy( _data, source_pos, dest, dest_pos, len );\r
 731         return dest;\r
 732     }\r
 733 \r
 734 \r
 735     // comparing\r
 736 \r
 737     /** {@inheritDoc} */\r
 738     @Override\r
 739     public boolean equals( Object other ) {\r
 740         if ( other == this ) {\r
 741             return true;\r
 742         }\r
 743         else if ( other instanceof TIntArrayListInternal ) {\r
 744                 TIntArrayListInternal that = ( TIntArrayListInternal )other;\r
 745             if ( that.sizeInternal() != this.sizeInternal() ) return false;\r
 746             else {\r
 747                 for ( int i = _pos; i-- > 0; ) {\r
 748                     if ( this._data[ i ] != that._data[ i ] ) {\r
 749                         return false;\r
 750                     }\r
 751                 }\r
 752                 return true;\r
 753             }\r
 754         }\r
 755         else return false;\r
 756     }\r
 757 \r
 758 \r
 759     /** {@inheritDoc} */\r
 760     @Override\r
 761     public int hashCode() {\r
 762         int h = 0;\r
 763         for ( int i = _pos; i-- > 0; ) {\r
 764             h += HashFunctions.hash( _data[ i ] );\r
 765         }\r
 766         return h;\r
 767     }\r
 768 \r
 769 \r
 770     // procedures\r
 771 \r
 772     /** {@inheritDoc} */\r
 773     public boolean forEach( TIntProcedure procedure ) {\r
 774         for ( int i = 0; i < _pos; i++ ) {\r
 775             if ( !procedure.execute( _data[ i ] ) ) {\r
 776                 return false;\r
 777             }\r
 778         }\r
 779         return true;\r
 780     }\r
 781 \r
 782 \r
 783     /** {@inheritDoc} */\r
 784     public boolean forEachDescending( TIntProcedure procedure ) {\r
 785         for ( int i = _pos; i-- > 0; ) {\r
 786             if ( !procedure.execute( _data[ i ] ) ) {\r
 787                 return false;\r
 788             }\r
 789         }\r
 790         return true;\r
 791     }\r
 792 \r
 793 \r
 794     // sorting\r
 795 \r
 796     /** {@inheritDoc} */\r
 797     public void sort() {\r
 798         Arrays.sort( _data, 0, _pos );\r
 799     }\r
 800 \r
 801 \r
 802     /** {@inheritDoc} */\r
 803     public void sort( int fromIndex, int toIndex ) {\r
 804         Arrays.sort( _data, fromIndex, toIndex );\r
 805     }\r
 806 \r
 807 \r
 808     // filling\r
 809 \r
 810     /** {@inheritDoc} */\r
 811     public void fill( int val ) {\r
 812         Arrays.fill( _data, 0, _pos, val );\r
 813     }\r
 814 \r
 815 \r
 816     /** {@inheritDoc} */\r
 817     public void fill( int fromIndex, int toIndex, int val ) {\r
 818         if ( toIndex > _pos ) {\r
 819           ensureCapacity( toIndex );\r
 820           _pos = toIndex;\r
 821         }\r
 822         Arrays.fill( _data, fromIndex, toIndex, val );\r
 823     }\r
 824 \r
 825 \r
 826     // searching\r
 827 \r
 828     /** {@inheritDoc} */\r
 829     public int binarySearch( int value ) {\r
 830         return binarySearch( value, 0, _pos );\r
 831     }\r
 832 \r
 833 \r
 834     /** {@inheritDoc} */\r
 835     public int binarySearch(int value, int fromIndex, int toIndex) {\r
 836         if ( fromIndex < 0 ) {\r
 837             throw new ArrayIndexOutOfBoundsException( fromIndex );\r
 838         }\r
 839         if ( toIndex > _pos ) {\r
 840             throw new ArrayIndexOutOfBoundsException( toIndex );\r
 841         }\r
 842 \r
 843         int low = fromIndex;\r
 844         int high = toIndex - 1;\r
 845 \r
 846         while ( low <= high ) {\r
 847             int mid = ( low + high ) >>> 1;\r
 848             int midVal = _data[ mid ];\r
 849 \r
 850             if ( midVal < value ) {\r
 851                 low = mid + 1;\r
 852             }\r
 853             else if ( midVal > value ) {\r
 854                 high = mid - 1;\r
 855             }\r
 856             else {\r
 857                 return mid; // value found\r
 858             }\r
 859         }\r
 860         return -( low + 1 );  // value not found.\r
 861     }\r
 862 \r
 863 \r
 864     /** {@inheritDoc} */\r
 865     public int indexOf( int value ) {\r
 866         return indexOf( 0, value );\r
 867     }\r
 868 \r
 869 \r
 870     /** {@inheritDoc} */\r
 871     public int indexOf( int offset, int value ) {\r
 872         for ( int i = offset; i < _pos; i++ ) {\r
 873             if ( _data[ i ] == value ) {\r
 874                 return i;\r
 875             }\r
 876         }\r
 877         return -1;\r
 878     }\r
 879 \r
 880 \r
 881     /** {@inheritDoc} */\r
 882     public int lastIndexOf( int value ) {\r
 883         return lastIndexOf( _pos, value );\r
 884     }\r
 885 \r
 886 \r
 887     /** {@inheritDoc} */\r
 888     public int lastIndexOf( int offset, int value ) {\r
 889         for ( int i = offset; i-- > 0; ) {\r
 890             if ( _data[ i ] == value ) {\r
 891                 return i;\r
 892             }\r
 893         }\r
 894         return -1;\r
 895     }\r
 896 \r
 897 \r
 898     /** {@inheritDoc} */\r
 899     public boolean contains( int value ) {\r
 900         return lastIndexOf( value ) >= 0;\r
 901     }\r
 902 \r
 903 \r
 904 //    /** {@inheritDoc} */\r
 905 //    public TIntList grep( TIntProcedure condition ) {\r
 906 //      TIntArrayListInternal list = new TIntArrayListInternal();\r
 907 //        for ( int i = 0; i < _pos; i++ ) {\r
 908 //            if ( condition.execute( _data[ i ] ) ) {\r
 909 //                list.add( _data[ i ] );\r
 910 //            }\r
 911 //        }\r
 912 //        return list;\r
 913 //    }\r
 914 \r
 915 \r
 916 //    /** {@inheritDoc} */\r
 917 //    public TIntList inverseGrep( TIntProcedure condition ) {\r
 918 //      TIntArrayListInternal list = new TIntArrayListInternal();\r
 919 //        for ( int i = 0; i < _pos; i++ ) {\r
 920 //            if ( !condition.execute( _data[ i ] ) ) {\r
 921 //                list.add( _data[ i ] );\r
 922 //            }\r
 923 //        }\r
 924 //        return list;\r
 925 //    }\r
 926 \r
 927 \r
 928     /** {@inheritDoc} */\r
 929     public int max() {\r
 930         if ( sizeInternal() == 0 ) {\r
 931             throw new IllegalStateException("cannot find maximum of an empty list");\r
 932         }\r
 933         int max = Integer.MIN_VALUE;\r
 934         for ( int i = 0; i < _pos; i++ ) {\r
 935                 if ( _data[ i ] > max ) {\r
 936                         max = _data[ i ];\r
 937                 }\r
 938         }\r
 939         return max;\r
 940     }\r
 941 \r
 942 \r
 943     /** {@inheritDoc} */\r
 944     public int min() {\r
 945         if ( sizeInternal() == 0 ) {\r
 946             throw new IllegalStateException( "cannot find minimum of an empty list" );\r
 947         }\r
 948         int min = Integer.MAX_VALUE;\r
 949         for ( int i = 0; i < _pos; i++ ) {\r
 950                 if ( _data[i] < min ) {\r
 951                         min = _data[i];\r
 952                 }\r
 953         }\r
 954         return min;\r
 955     }\r
 956 \r
 957 \r
 958     /** {@inheritDoc} */\r
 959     public int sum() {\r
 960         int sum = 0;\r
 961         for ( int i = 0; i < _pos; i++ ) {\r
 962                         sum += _data[ i ];\r
 963         }\r
 964         return sum;\r
 965     }\r
 966 \r
 967 \r
 968     // stringification\r
 969 \r
 970     /** {@inheritDoc} */\r
 971     @Override\r
 972     public String toString() {\r
 973         final StringBuilder buf = new StringBuilder( "{" );\r
 974         for ( int i = 0, end = _pos - 1; i < end; i++ ) {\r
 975             buf.append( _data[ i ] );\r
 976             buf.append( ", " );\r
 977         }\r
 978         if ( sizeInternal() > 0 ) {\r
 979             buf.append( _data[ _pos - 1 ] );\r
 980         }\r
 981         buf.append( "}" );\r
 982         return buf.toString();\r
 983     }\r
 984 \r
 985 \r
 986     /** TIntArrayList iterator */\r
 987     class TIntArrayIterator implements TIntIterator {\r
 988 \r
 989         /** Index of element to be returned by subsequent call to next. */\r
 990         private int cursor = 0;\r
 991 \r
 992         /**\r
 993          * Index of element returned by most recent call to next or\r
 994          * previous.  Reset to -1 if this element is deleted by a call\r
 995          * to remove.\r
 996          */\r
 997         int lastRet = -1;\r
 998 \r
 999 \r
1000         TIntArrayIterator( int index ) {\r
1001             cursor = index;\r
1002         }\r
1003 \r
1004 \r
1005         /** {@inheritDoc} */\r
1006         public boolean hasNext() {\r
1007             return cursor < sizeInternal();\r
1008             }\r
1009 \r
1010 \r
1011         /** {@inheritDoc} */\r
1012         public int next() {\r
1013             try {\r
1014                 int next = getAt( cursor );\r
1015                 lastRet = cursor++;\r
1016                 return next;\r
1017             } catch ( IndexOutOfBoundsException e ) {\r
1018                 throw new NoSuchElementException();\r
1019             }\r
1020         }\r
1021 \r
1022 \r
1023         /** {@inheritDoc} */\r
1024         public void remove() {\r
1025             if ( lastRet == -1 )\r
1026                         throw new IllegalStateException();\r
1027 \r
1028             try {\r
1029                 TIntArrayListInternal.this.remove( lastRet, 1);\r
1030                 if ( lastRet < cursor )\r
1031                     cursor--;\r
1032                 lastRet = -1;\r
1033             } catch ( IndexOutOfBoundsException e ) {\r
1034                 throw new ConcurrentModificationException();\r
1035             }\r
1036         }\r
1037     }\r
1038 \r
1039 \r
1040     public void writeExternal( ObjectOutput out ) throws IOException {\r
1041         // VERSION\r
1042         out.writeByte( 0 );\r
1043 \r
1044         // POSITION\r
1045         out.writeInt( _pos );\r
1046 \r
1047         // NO_ENTRY_VALUE\r
1048         out.writeInt( no_entry_value );\r
1049 \r
1050         // ENTRIES\r
1051         int len = _data.length;\r
1052         out.writeInt( len );\r
1053         for( int i = 0; i < len; i++ ) {\r
1054                 out.writeInt( _data[ i ] );\r
1055         }\r
1056     }\r
1057 \r
1058 \r
1059     public void readExternal( ObjectInput in )\r
1060         throws IOException, ClassNotFoundException {\r
1061 \r
1062         // VERSION\r
1063         in.readByte();\r
1064 \r
1065         // POSITION\r
1066         _pos = in.readInt();\r
1067 \r
1068         // NO_ENTRY_VALUE\r
1069         no_entry_value = in.readInt();\r
1070 \r
1071         // ENTRIES\r
1072         int len = in.readInt();\r
1073         _data = new int[ len ];\r
1074         for( int i = 0; i < len; i++ ) {\r
1075                 _data[ i ] = in.readInt();\r
1076         }\r
1077     }\r
1078 } // TIntArrayList\r