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

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