001    /*
002     * Copyright (c) 2003, The Regents of the University of California, through
003     * Lawrence Berkeley National Laboratory (subject to receipt of any required
004     * approvals from the U.S. Dept. of Energy). All rights reserved.
005     */
006    package gov.lbl.dsd.sea.nio.util;
007    
008    import java.io.IOException;
009    import java.nio.IntBuffer;
010    
011    /**
012    Efficient resizable auto-expanding list holding <code>int</code> elements; implemented with arrays.
013    The API is intended for easy non-trivial high-throughput processing, 
014    and (in an elegant and compact yet different form) provides all list and set functionality 
015    of the java.util collections package, as well as a little more.
016    This API fills the gap between raw arrays (non-resizable), nio IntBuffers (non-resizable) and
017    java.util.List and java.util.Set (resizable but not particularly useful for 
018    <i>non-trivial high-throughput</i> processing on primitive types).
019    <p>
020    Indexed element access is zero based: valid indexes range from 
021    index <code>0</code> (inclusive) to index <code>list.size()</code> (exclusive).
022    Attempts to access out-of-range indexes will throw an {@link IndexOutOfBoundsException}.
023    <p>
024    <strong>Note that this implementation is not synchronized, hence not inherently thread safe.</strong>
025    <p>
026    Example usage:
027    <pre>
028    System.out.println(new ArrayIntList(new int[] {0,1,2}));
029    </pre>
030    <p>
031    This class requires JDK 1.4 or higher; otherwise it has zero dependencies. 
032    Hence you can simply copy the file into your own project if minimal dependencies are desired.
033    <p>
034    Also note that the compiler can (and will) easily inline all methods, then optimize away.
035    In fact with the Sun jdk-1.4.2 server VM it is hard to measure any difference 
036    to raw array manipulations at abstraction level zero.
037    
038    @author whoschek@lbl.gov
039    @author $Author: hoschek3 $
040    @version $Revision: 1.36 $, $Date: 2004/08/07 19:13:47 $
041    */
042    public final class ArrayIntList implements java.io.Serializable {
043    
044            /**
045             * The array into which the elements of the list are stored. The
046             * capacity of the list is the length of this array.
047             */
048            private transient int[] elements;
049    
050            /**
051             * The current number of elements contained in this list.
052             */
053            private int size;
054    
055            /**
056             * For compatibility across versions
057             */
058            private static final long serialVersionUID = 2982195016849084649L;      
059                    
060            /**
061             * Constructs an empty list.
062             */
063            public ArrayIntList() {
064                    this(10);
065            }
066    
067            /**
068             * Constructs an empty list with the specified initial capacity.
069             * 
070             * @param initialCapacity
071             *            the number of elements the receiver can hold without
072             *            auto-expanding itself by allocating new internal memory.
073             */
074            public ArrayIntList(int initialCapacity) {
075                    elements = new int[initialCapacity];
076                    size = 0;
077            }
078    
079            /**
080             * Constructs a list SHARING the specified elements. The initial size and
081             * capacity of the list is the length of the backing array.
082             * <p>
083             * <b>WARNING: </b> For efficiency reasons and to keep memory usage low,
084             * <b>the array is SHARED, not copied </b>. So if subsequently you modify the
085             * specified array directly via the [] operator, be sure you know what
086             * you're doing.
087             * <p>
088             * If you rather need copying behaviour, use
089             * <code>copy = new ArrayIntList(int[] elems).copy()</code> or similar.
090             * <p>
091             * If you need a list containing a copy of <code>elems[from..to)</code>, use
092             * <code>list = new ArrayIntList(to-from).add(elems, from, to-from)</code> 
093             * or <code>list = new ArrayIntList(IntBuffer.wrap(elems, from, to-from))</code>
094             * or similar.
095             * 
096             * @param elems
097             *            the array backing the constructed list
098             */
099            public ArrayIntList(int[] elems) {
100                    elements = elems;
101                    size = elems.length;
102            }
103    
104            /**
105             * Constructs a list containing a copy of the remaining buffer elements. The
106             * initial size and capacity of the list is <code>elems.remaining()</code>.
107             * 
108             * @param elems
109             *            the elements initially to be added to the list
110             */
111            public ArrayIntList(IntBuffer elems) {
112                    this(elems.remaining());
113                    add(elems);
114            }
115    
116            /**
117             * Appends the specified element to the end of this list.
118             * 
119             * @param elem
120             *            element to be appended to this list.
121             * @return <code>this</code> (for chaining convenience only)
122             */
123            public ArrayIntList add(int elem) {
124                    if (size == elements.length) ensureCapacity(size + 1);
125                    elements[size++] = elem;
126                    return this;
127                    // equally correct alternative impl: insert(size, elem);
128            }
129    
130            /**
131             * Appends the elements in the range <code>[offset..offset+length)</code> to the end of this list.
132             * 
133             * @param elems the elements to be appended
134             * @param offset the offset of the first element to add (inclusive)
135             * @param length the number of elements to add
136             * @return <code>this</code> (for chaining convenience only)
137             * @throws IndexOutOfBoundsException if indexes are out of range.
138             */
139            public ArrayIntList add(int[] elems, int offset, int length) {
140                    if (offset < 0 || length < 0 || offset + length > elems.length) 
141                            throw new IndexOutOfBoundsException("offset: " + offset + ", length: " + length + ", elems.length: " + elems.length);
142                    ensureCapacity(size + length);
143                    System.arraycopy(elems, offset, this.elements, size, length);
144                    size += length;
145                    return this;
146                    // equally correct alternative impl: replace(size, size, elems, offset, length);
147            }
148    
149            /**
150             * Appends the specified elements to the end of this list.
151             * 
152             * @param elems
153             *            elements to be appended.
154             * @return <code>this</code> (for chaining convenience only)
155             */
156            public ArrayIntList add(ArrayIntList elems) {
157                    replace(size, size, elems);
158                    return this;
159            }
160            
161            /**
162             * Appends the remaining buffer elements to the end of this list.
163             * 
164             * @param elems
165             *            elements to be appended.
166             * @return <code>this</code> (for chaining convenience only)
167             */
168            public ArrayIntList add(IntBuffer elems) {
169                    int length = elems.remaining();
170                    ensureCapacity(size + length);
171                    elems.get(this.elements, size, length);
172                    size += length;
173                    return this;
174                    // equally correct alternative impl: replace(size, size, elems, elems.remaining());
175            }
176            
177            /**
178             * Returns the elements currently stored, including invalid elements between
179             * size and capacity, if any.
180             * <p>
181             * <b>WARNING: </b> For efficiency reasons and to keep memory usage low,
182             * <b>the array is SHARED, not copied </b>. So if subsequently you modify the
183             * returned array directly via the [] operator, be sure you know what you're
184             * doing.
185             * 
186             * @return the elements currently stored.
187             */
188            public int[] asArray() {
189                    return elements;
190            }
191    
192            /**
193             * Returns a buffer SHARING elements with the receiver. The buffer will
194             * have the default NIO byte order, which is ByteOrder.nativeOrder().
195             * <p>
196             * <b>WARNING: </b> For efficiency reasons and to keep memory usage low,
197             * <b>the array is SHARED, not copied </b>. So if subsequently you modify the
198             * returned buffer, be sure you know what you're doing.
199             */
200            public IntBuffer asIntBuffer() {
201                    return IntBuffer.wrap(elements, 0, size);
202            }
203    
204        /**
205             * Searches the list for the specified value using the binary search
206             * algorithm. The list <strong>must </strong> be sorted (as by the
207             * <tt>sort</tt> method) prior to making this call. If it is not sorted,
208             * the results are undefined. If the list contains multiple elements with
209             * the specified value, there is no guarantee which one will be found.
210             * 
211             * @param key
212             *            the value to be searched for.
213             * @return index of the search key, if it is contained in the list;
214             *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
215             *         <i>insertion point </i> is defined as the point at which the key
216             *         would be inserted into the list: the index of the first element
217             *         greater than the key, or <tt>list.size()</tt>, if all elements
218             *         in the list are less than the specified key. Note that this
219             *         guarantees that the return value will be >= 0 if and only if
220             *         the key is found.
221             * @see #sort(boolean)
222             */
223            public int binarySearch(int key) {
224                    int low = 0;
225                    int high = size - 1;
226    
227                    while (low <= high) {
228                            int mid = (low + high) >> 1; // >> 1 is equivalent to divide by 2
229                            int midVal = elements[mid];
230    
231                            if (midVal < key)
232                                    low = mid + 1;
233                            else if (midVal > key)
234                                    high = mid - 1;
235                            else
236                                    return mid; // key found
237                    }
238                    return -(low + 1); // key not found.
239            }
240    
241            /**
242             * Removes all elements but keeps the current capacity; Afterwards
243             * <code>size()</code> will yield zero.
244             * 
245             * @return <code>this</code> (for chaining convenience only)
246             */
247            public ArrayIntList clear() {
248                    size = 0;
249                    return this;
250                    // equally correct alternative impl: remove(0, size);
251            }
252                    
253            /**
254             * Constructs and returns a new list that is a deep copy of the receiver.
255             * 
256             * @return a deep copy of the receiver.
257             */
258            public ArrayIntList copy() {
259                    return new ArrayIntList(toArray());
260            }
261    
262            /**
263             * Compares the specified Object with the receiver. Returns true if and only
264             * if the specified Object is also a list of the same type, both Lists
265             * have the same size, and all corresponding pairs of elements in the two
266             * Lists are identical. In other words, two Lists are defined to be equal if
267             * they contain the same elements in the same order.
268             * 
269             * @param otherObj
270             *            the Object to be compared for equality with the receiver.
271             * @return true if the specified Object is equal to the receiver.
272             */
273            public boolean equals(Object otherObj) { //delta
274                    if (this == otherObj) return true;
275                    if (!(otherObj instanceof ArrayIntList)) return false;
276                    ArrayIntList other = (ArrayIntList) otherObj;
277                    if (size != other.size) return false;
278                    return indexOf(0, size, other) >= 0;
279            }
280    
281            /**
282             * Ensures that the receiver can hold at least the specified number of
283             * elements without needing to allocate new internal memory. If necessary,
284             * allocates new internal memory and increases the capacity of the receiver.
285             * 
286             * @param minCapacity
287             *            the desired minimum capacity.
288             */
289            public void ensureCapacity(int minCapacity) {
290                    if (minCapacity > elements.length) {
291                            int newCapacity = Math.max(minCapacity, (elements.length * 3) / 2 + 1);
292                            elements = subArray(0, size, newCapacity);
293                    }
294            }
295    
296            /**
297             * Finds all matching sublists in the range <code>[from..to)</code> and
298             * replaces them with the given replacement. A sublist matches if it is
299             * equal to the given pattern. The pattern must have a size greater than
300             * zero. The replacement can have any size. 
301             * Examples: 
302             * <pre>
303             * [a,b,c,d,b,c].findReplace(0,6, [b,c], [x,y,z]) --> [a,x,y,z,d,x,y,z]
304             * [a,b,c,d,b,c].findReplace(0,6, [b,c], []) --> [a,d]
305             * </pre>
306             * 
307             * @param from the index of the first element to search (inclusive)
308             * @param to   the index of the last element to search (exclusive).
309             * @param pattern the sublist to search for
310             * @param replacement the elements to replace the found sublists
311             * @return the number of sublists found matching the pattern
312             * @throws IndexOutOfBoundsException if indexes are out of range.
313             * @throws IllegalArgumentException if pattern.size() == 0.
314             */
315            public int findReplace(int from, int to, ArrayIntList pattern, ArrayIntList replacement) {
316                    checkRange(from, to);
317                    if (pattern.size == 0) throw new IllegalArgumentException("pattern size must be > 0");
318                    int n = 0;
319                    while ((from = indexOf(from, to, pattern)) >= 0) {
320                            if (pattern != replacement) { // do more than just counting matches
321                                    replace(from, from + pattern.size, replacement);
322                                    to += replacement.size - pattern.size;
323                            }
324                            from += replacement.size;
325                            n++;
326                    }
327                    return n;
328            }
329            
330            /**
331             * Returns the element at the specified index.
332             * 
333             * @param index
334             *            index of element to return.
335             * @throws IndexOutOfBoundsException if index is out of range.
336             */
337            public int get(int index) {
338                    checkIndex(index);
339                    return elements[index];
340            }
341    
342            /**
343             * Returns the hash code value for this list. The algorithm ensures that
344             * <tt>list1.equals(list2)</tt> implies that
345             * <tt>list1.hashCode()==list2.hashCode()</tt> for any two lists,
346             * <tt>list1</tt> and <tt>list2</tt>, as required by the general
347             * contract of <tt>Object.hashCode</tt>.
348             * <p>
349             * Warning: run time complexity is O(N)
350             * 
351             * @return the hash code value for this list.
352             * @see Object#hashCode()
353             * @see Object#equals(Object)
354             * @see #equals(Object)
355             * @see java.util.List#hashCode()
356             */
357            public int hashCode() {
358                    int hashCode = 1;
359                    int[] elems = elements;
360                    for (int i = size; --i >= 0; )
361                            hashCode = 31*hashCode + elems[i];
362                    return hashCode;
363            }
364    
365            /**
366             * Returns the index of the first occurrence of the given sublist within 
367             * the range <code>this[from..to)</code>.
368             * Returns <code>-1</code> if the receiver does not contain such a sublist.
369             * Examples:
370             * <pre> 
371             * [a,b,c,d,e,b,c,d].indexOf(0,8, [b,c,d]) --> 1
372             * [a,b,c,d,e].indexOf(0,5, [b,c,d]) --> 1
373             * [a,b,c,d,e].indexOf(1,4, [b,c,d]) --> 1
374             * [a,b,c,d,e].indexOf(0,5, [x,y])   --> -1
375             * [a,b,c,d,e].indexOf(0,3, [b,c,d]) --> -1
376             * [a].indexOf(0,1, [a,b,c]) --> -1
377             * [a,b,c,d,e].indexOf(2,3, []) --> 2 // empty sublist is always found
378             * [].indexOf(0,0, []) --> 0
379             * </pre>
380             * 
381             * @param from
382             *            the leftmost search index within the receiver, inclusive.
383             * @param to
384             *            the rightmost search index within the receiver, exclusive.
385             * @param subList
386             *            the sublist to search for.
387             * @return the index of the first occurrence of the sublist in the receiver;
388             *         returns <code>-1</code> if the sublist is not found.
389             * @throws IndexOutOfBoundsException
390             *             if indexes are out of range
391             */
392            public int indexOf(int from, int to, ArrayIntList subList) {
393                    // brute-force algorithm, but very efficiently implemented
394                    checkRange(from, to);
395                    int[] elems = elements;
396                    int[] subElems = subList.elements;
397                    int subsize = subList.size;
398                    to -= subsize;
399                    while (from <= to) {
400                            int i = subsize;
401                            int j = from + subsize;
402                            while (--i >= 0 && elems[--j] == subElems[i]) { // compare from right to left
403                                    ;
404                            }
405                            if (i < 0) return from; // found
406                            from++;
407                    }
408                    return -1; // not found
409            }
410    
411            /**
412             * Returns the index of the first occurrence of the specified element within
413             * the range <code>[from..to)</code>. Returns <code>-1</code> if the
414             * receiver does not contain such an element.
415             * 
416             * @param from
417             *            the leftmost search index, inclusive.
418             * @param to
419             *            the rightmost search index, exclusive.
420             * @param elem
421             *            element to search for.
422             * @return the index of the first occurrence of the element in the receiver;
423             *         returns <code>-1</code> if the element is not found.
424             * @throws IndexOutOfBoundsException
425             *             if indexes are out of range
426             */
427            public int indexOf(int from, int to, int elem) {
428                    checkRange(from, to);
429                    int[] elems = elements;
430                    for (int i = from; i < to; i++) {
431                            if (elem == elems[i]) return i; //found
432                    }
433                    return -1; //not found
434            }
435            
436            /**
437             * Returns the index of the last occurrence of the given sublist within 
438             * the range <code>this[from..to)</code>.
439             * Returns <code>-1</code> if the receiver does not contain such a sublist.
440             * Examples:
441             * <pre> 
442             * [a,b,c,d,e,b,c,d].lastIndexOf(0,8, [b,c,d]) --> 5
443             * [a,b,c,d,e].lastIndexOf(0,5, [b,c,d]) --> 1
444             * [a,b,c,d,e].lastIndexOf(1,4, [b,c,d]) --> 1
445             * [a,b,c,d,e].lastIndexOf(0,5, [x,y])   --> -1
446             * [a,b,c,d,e].lastIndexOf(0,3, [b,c,d]) --> -1
447             * [a].lastIndexOf(0,1, [a,b,c]) --> -1
448             * [a,b,c,d,e].lastIndexOf(2,3, []) --> 3 // empty sublist is always found
449             * [].lastIndexOf(0,0, []) --> 0
450             * </pre>
451             * 
452             * @param from
453             *            the leftmost search index within the receiver, inclusive.
454             * @param to
455             *            the rightmost search index within the receiver, exclusive.
456             * @param subList
457             *            the sublist to search for.
458             * @return the index of the last occurrence of the sublist in the receiver;
459             *         returns <code>-1</code> if the sublist is not found.
460             * @throws IndexOutOfBoundsException
461             *             if indexes are out of range
462             */
463            public int lastIndexOf(int from, int to, ArrayIntList subList) {
464                    // brute-force algorithm, but very efficiently implemented
465                    checkRange(from, to);
466                    int[] elems = elements;
467                    int[] subElems = subList.elements;
468                    
469                    int subsize = subList.size;
470                    from += subsize;
471                    while (from <= to) {
472                            int i = subsize;
473                            int j = to;
474                            while (--i >= 0 && elems[--j] == subElems[i]) { // compare from right to left
475                                    ;
476                            }
477                            if (i < 0) return to - subsize; // found
478                            to--;
479                    }
480                    return -1; // not found
481            }
482    
483            /**
484             * Removes the elements in the range <code>[from..to)</code>. Shifts any
485             * subsequent elements to the left. Keeps the current capacity.
486             * Note: To remove a single element use <code>remove(index, index+1)</code>. 
487             * To remove all elements use <code>remove(0, list.size())</code>.
488             * 
489             * @param from
490             *            the index of the first element to removed (inclusive).
491             * @param to
492             *            the index of the last element to removed (exclusive).
493             * @throws IndexOutOfBoundsException
494             *             if indexes are out of range
495             */
496            public void remove(int from, int to) {
497                    shrinkOrExpand(from, to, 0);
498                    // equally correct alternative impl: replace(from, to, 0, 0); 
499            }
500            
501            /**
502             * Removes from the receiver all elements that are contained in the
503             * specified other list.
504             * <p>
505             * Example: <code>[0,1,2,2,3,3,0].removeAll([2,1]) --> [0,3,3,0]</code>
506             * <p>
507             * An efficient <i>asymmetric set difference</i> can be computed along the following lines: 
508             * <pre>
509             * list1.sort(true);
510             * list2.sort(true);
511             * list1.removeAll(list2, true);
512             * System.out.println(list1);
513             * </pre>
514             * 
515             * @param other
516             *            the other list to test against (remains unmodified by this method).
517             * @param isOtherSorted
518             *            true if the other list is already sorted ascending, false otherwise (being sorted improves performance).
519             * @return <code>true</code> if the receiver changed as a result of the
520             *         call.
521             */
522            public boolean removeAll(ArrayIntList other, boolean isOtherSorted) {
523                    // time complexity is O(N log M) if sorted; O(N*M) otherwise
524                    if (size == 0 || other.size() == 0) return false; //nothing to do
525                    int limit = other.size();
526                    int j = 0;
527    
528                    for (int i = 0; i < size; i++) {
529                            if (isOtherSorted ? other.binarySearch(elements[i]) < 0 : other.indexOf(0, limit, elements[i]) < 0) {
530                                    elements[j++] = elements[i];
531                            }
532                    }
533    
534                    boolean modified = (j != size);
535                    size = j;
536                    return modified;
537            }
538            
539            /**
540             * The powerful work horse for all add/insert/replace/remove methods.
541             * One powerful efficient method does it all :-)
542             */
543            private void shrinkOrExpand(int from, int to, int replacementSize) {
544                    checkRange(from, to);
545                    int diff = replacementSize - (to - from);
546                    if (diff != 0) {
547                            ensureCapacity(size + diff);
548                            if (size - to > 0) { // check is for performance only (arraycopy is native method)
549                                    // diff > 0 shifts right, diff < 0 shifts left
550                                    System.arraycopy(elements, to, elements, to + diff, size - to);
551                            }
552                            size += diff;
553                    }
554            }
555            
556            /**
557             * Replaces all elements in the range <code>[from..to)</code> with the
558             * elements <code>replacement[offset..offset+length)</code>. The replacement can have any length.
559             * Increases (or decreases) the receiver's size by <code>length - (to - from)</code>.
560             * Use <code>from==to</code> to perform pure insertion.
561             * 
562             * @param from the index of the first element to replace (inclusive)
563             * @param to   the index of the last element to replace (exclusive).
564             * @param replacement the elements to replace the replaced elements
565             * @param offset the offset of the first replacing element (inclusive)
566             * @param length the number of replacing elements
567             * @throws IndexOutOfBoundsException if indexes are out of range.
568             */
569            public void replace(int from, int to, int[] replacement, int offset, int length) {
570                    if (offset < 0 || length < 0 || offset + length > replacement.length) 
571                            throw new IndexOutOfBoundsException("offset: " + offset + ", length: " + length + ", replacement.length: " + replacement.length);
572                    shrinkOrExpand(from, to, length);
573                    System.arraycopy(replacement, offset, this.elements, from, length);
574            }
575            
576            /**
577             * Replaces all elements in the range <code>[from..to)</code> with the given replacement.
578             * The replacement can have any length.
579             * Increases (or decreases) the receiver's size by <code>replacement.size - (to - from)</code>.
580             * Use <code>from==to</code> to perform pure insertion. Examples:
581             * <pre>
582             * [a,b,c,d,e].replace(1,4, [x,y]) --> [a,x,y,e]
583             * [a,b].replace(1,1, [w,x,y,z]) --> [a,w,x,y,z,b]
584             * </pre>
585             * 
586             * @param from the index of the first element to replace (inclusive)
587             * @param to   the index of the last element to replace (exclusive).
588             * @param replacement the elements to replace the replaced elements
589             * @throws IndexOutOfBoundsException if indexes are out of range.
590             */
591            public void replace(int from, int to, ArrayIntList replacement) {
592                    shrinkOrExpand(from, to, replacement.size);
593                    System.arraycopy(replacement.elements, 0, this.elements, from, replacement.size);
594            }
595            
596            /**
597             * Replaces all elements in the range <code>[from..to)</code> with the given replacement.
598             * The replacement consists of 
599             * <code>replacement[replacement.position() .. replacement.position() + replacementSize)</code>.
600             * Increases (or decreases) the receiver's size by <code>replacementSize - (to - from)</code>.
601             * Use <code>from==to</code> to perform pure insertion. Examples:
602             * <pre>
603             * [a,b,c,d,e].replace(1,4, [x,y], 2) --> [a,x,y,e]
604             * [a,b].replace(1,1, [w,x,y,z], 4) --> [a,w,x,y,z,b]
605             * </pre>
606             * There must hold: <code>0 < replacementSize <= replacement.remaining()</code>. 
607             * 
608             * @param from the index of the first element to replace (inclusive)
609             * @param to   the index of the last element to replace (exclusive).
610             * @param replacement the elements to replace the replaced elements
611             * @param replacementSize the number of replacing elements
612             * @throws IndexOutOfBoundsException if indexes are out of range.
613             */
614            public void replace(int from, int to, IntBuffer replacement, int replacementSize) {
615                    if (replacementSize < 0 || replacementSize > replacement.remaining()) 
616                            throw new IndexOutOfBoundsException("replacementSize: " + replacementSize);
617                    shrinkOrExpand(from, to, replacementSize);
618                    replacement.get(this.elements, from, replacementSize);
619            }
620            
621            /**
622             * Replaces all elements in the range <code>[from..to)</code> with the given replacement.
623             * The replacement can have any length >= 0.
624             * Increases (or decreases) the receiver's size by <code>replacementSize - (to - from)</code>.
625             * Use <code>from==to</code> to perform pure insertion. Examples:
626             * <pre>
627             * [a,b,c,d,e].replace(1,4,x,4) --> [a,x,x,x,x,e]
628             * [a,b,c,d,e].replace(0,0,x,4) --> [x,x,x,x,a,b,c,d,e]
629             * </pre>
630             * 
631             * @param from the index of the first element to replace (inclusive)
632             * @param to   the index of the last element to replace (exclusive).
633             * @param replacement the elements to replace the replaced elements
634             * @param replacementSize the number of times <code>replacement</code> is to replace the replaced elements
635             * @throws IndexOutOfBoundsException if indexes are out of range.
636             */
637            public void replace(int from, int to, int replacement, int replacementSize) {
638                    checkSize(replacementSize);
639                    shrinkOrExpand(from, to, replacementSize);
640                    while (replacementSize-- > 0) elements[from++] = replacement;
641                    //java.util.Arrays.fill(this.elements, from, from + replacementSize, replacement);                      
642            }
643            
644            /**
645             * Retains (keeps) only the elements in the receiver that are contained in
646             * the specified other list. In other words, removes from the receiver all
647             * of its elements that are not contained in the specified other list.
648             * <p>
649             * Example: <code>[0,1,2,2,3,1].retainAll([2,1]) --> [1,2,2,1]</code>
650             * <p>
651             * An efficient <i>set intersection</i> can be computed along the following lines: 
652             * <pre>
653             * list1.sort(true);
654             * list2.sort(true);
655             * list1.retainAll(list2, true);
656             * System.out.println("list1.retainAll(list2) = " + list1);
657             * // as a convenient byproduct we now know if list2 is a SUBSET of list1:
658             * System.out.println("list1.containsAll(list2) = " + (list1.size() == list2.size()));
659             * // as a convenient byproduct we now know if list1 contains ANY element of list2:
660             * System.out.println("list1.containsAny(list2) = " + (list1.size() > 0));
661             * </pre>
662             * 
663             * @param other
664             *            the other list to test against (remains unmodified by this method).
665             * @param isOtherSorted
666             *            true if the other list is already sorted ascending, false otherwise (being sorted improves performance).
667             * @return <code>true</code> if the receiver changed as a result of the
668             *         call.
669             */
670            public boolean retainAll(ArrayIntList other, boolean isOtherSorted) {
671                    // time complexity is O(N log M) if sorted; O(N*M) otherwise
672                    if (size == 0) return false;
673                    if (other.size() == 0) {
674                            size = 0;
675                            return true;
676                    }
677    
678                    int limit = other.size();
679                    int j = 0;
680                    for (int i = 0; i < size; i++) {
681                            if (isOtherSorted ? other.binarySearch(elements[i]) >= 0 : other.indexOf(0, limit, elements[i]) >= 0)
682                                    elements[j++] = elements[i];
683                    }
684    
685                    boolean modified = (j != size);
686                    size = j;
687                    return modified;
688            }
689    
690        /**
691             * Rotates (shifts) the elements in the range <code>[from..to)</code> by
692             * the specified distance. After calling this method, the element at index
693             * <code>i</code> will be the element previously at index
694             * <code>(i - distance)</code> mod <code>to-from</code>, for all values
695             * of <code>i</code> between <code>from</code> (inclusive) and
696             * <code>to</code>, exclusive. (This method has no effect on the size of
697             * the list.) Examples:
698             * 
699             * <pre>
700             *   [a, b, c, d, e].rotate(0, 5, 1)  --> [e, a, b, c, d]
701             *   [a, b, c, d, e].rotate(0, 5, 2)  --> [d, e, a, b, c]
702             *   [a, b, c, d, e].rotate(1, 4, -1) --> [a, c, d, b, e]
703             * </pre>
704             * 
705             * <p>
706             * To move elements rightwards, use a positive shift distance. To move
707             * elements leftwards, use a negative shift distance.
708             * <p>
709             * Note that this method can usefully be applied to sublists to move one or
710             * more elements within a list while preserving the order of the remaining
711             * elements.
712             * <p>
713             * This implementation exchanges the first element into the location it
714             * should go, and then repeatedly exchanges the displaced element into the
715             * location it should go until a displaced element is swapped into the first
716             * element. If necessary, the process is repeated on the second and
717             * successive elements, until the rotation is complete. This algorithm is
718             * efficient: Time complexity is linear O(to-from), space complexity is
719             * constant O(1).
720             * 
721             * @param from
722             *            the index of the first element to rotate (inclusive)
723             * @param to
724             *            the index of the last element to rotate (exclusive).
725             * @param distance
726             *            the distance to rotate the list. There are no constraints on
727             *            this value; for example it may be zero, negative, or greater than
728             *            <code>to-from</code>.
729             * @throws IndexOutOfBoundsException
730             *             if indexes are out of range.
731             * @see java.util.Collections#rotate(java.util.List, int)
732             */
733            public void rotate(int from, int to, int distance) {
734                    checkRange(from, to);
735                    int length = to - from;
736                    if (length == 0) return;
737                    distance = distance % length;
738                    if (distance < 0) distance += length;
739                    if (distance == 0) return;
740    
741                    int[] elems = elements;
742                    for (int nMoved = 0; nMoved != length; from++) {
743                            int displaced = elems[from];
744                            int i = from;
745                            do {
746                                    i += distance;
747                                    if (i >= to) i -= length;
748                                    
749                                    int tmp = elems[i];
750                                    elems[i] = displaced;
751                                    displaced = tmp;
752    
753                                    nMoved++;
754                            } while (i != from);
755                    }
756        }
757            
758            /**
759             * Replaces the element at the specified index with the specified
760             * element.
761             * 
762             * @param index
763             *            index of element to replace.
764             * @param element
765             *            element to be stored at the specified index.
766             * @throws IndexOutOfBoundsException
767             *             if index is out of range.
768             */
769            public void set(int index, int element) {
770                    checkIndex(index);
771                    elements[index] = element;
772                    // equally correct alternative impl: replace(index, index+1, element, 1); 
773            }
774    
775            /**
776             * Returns the number of contained elements.
777             *
778             * @return  the number of elements contained in the receiver.
779             */
780            public int size() {
781                    return size;
782            }
783    
784            /**
785             * Sorts the elements into ascending numerical order. For mathematical set
786             * operations, optionally removes duplicate elements before returning.
787             * Examples:
788             * <pre>
789             * [3,2,2,1].sort(false) --> [1,2,2,3]
790             * [3,2,2,1].sort(true)  --> [1,2,3]
791             * </pre>
792             * 
793             * @param removeDuplicates remove duplicate elements or keep them?
794             */ 
795            public void sort(boolean removeDuplicates) {
796                    final int maxWidth = 256 * 1024; // memory consumption threshold (also prevents int overflows in countSort())
797                    if (size > 60) { // performance threshold heuristic
798                            // compute minimum and maximum values
799                            int[] elems = elements;
800                            int min = elems[0];
801                            int max = min;
802                            for (int i = 1; i < size && max - min < maxWidth && max - min >= 0; i++) { // width < 0 on int overflow
803                                    int elem = elems[i];
804                                    if (elem > max) max = elem;
805                                    else if (elem < min) min = elem;
806                            }
807                            
808                            int width = max - min;
809                            if (width < maxWidth && width >= 0 ) {
810                                    int countSortEstimate = Math.max(width, size); // O(Max(width,N))
811                                    double log2 = Math.log(size) / 0.6931471805599453; // O(N*log(N,base=2)) ; ln(2)=0.6931471805599453
812                                    double quickSortEstimate = size * log2; 
813                                    if (countSortEstimate < quickSortEstimate) {
814                                            //System.out.println("using countSort..");
815                                            countSort(removeDuplicates, min, max);  
816                                            return;
817                                    }
818                            }
819                    }
820    
821                    // use quicksort if there is no more efficient alternative:
822                    java.util.Arrays.sort(elements, 0, size);
823                    if (removeDuplicates) removeDuplicates();
824            }
825            
826            /** efficient sort implementation: O(N) via frequency counts */
827            private void countSort(boolean removeDuplicates, int min, int max) {
828                    // countSort is most efficient on large lists that have values that are in a small [min,max] range              
829                    // assertion: max - min +1 does not yield int overflow
830                    int[] counts = new int[max - min + 1];  // could use BitSet if removeDuplicates
831                    for (int i = size; --i >= 0; ) {
832                            counts[elements[i] - min]++;
833                    }
834                    
835                    int j = 0;
836                    for (int i = min; i >= min && i <= max; i++) { // safe even with int overflow 
837                            int k = counts[i - min];
838                            if (removeDuplicates && k > 1) k = 1;
839                            while (--k >= 0) {
840                                    elements[j++] = i;
841                            }
842                    }
843                    size = j;
844            }
845    
846            /**
847             * [1,2,2,3,3,3] --> [1,2,3]
848             * Assertion: list must be sorted prior to calling this method
849             */
850            private void removeDuplicates() {
851                    int i = 0;
852                    int j = 0;
853                    while (j < size) {
854                            int elem = elements[j++];
855                            elements[i++] = elem;
856                            while (j < size && elements[j] == elem) j++; // skip duplicates
857                    }
858                    size = i;
859            }
860            
861            /** Small helper method eliminating redundancy. */
862            private int[] subArray(int from, int length, int capacity) {
863                    int[] subArray = new int[capacity];
864                    System.arraycopy(elements, from, subArray, 0, length);
865                    return subArray;
866            }
867    
868            /**
869             * Constructs and returns a new list containing a copy of the elements in
870             * the range <code>[from..to)</code>.
871             * 
872             * @param from
873             *            the index of the first element (inclusive).
874             * @param to
875             *            the index of the last element (exclusive).
876             * @return a new list
877             * @throws IndexOutOfBoundsException
878             *             if indexes are out of range
879             */
880            public ArrayIntList subList(int from, int to) {
881                    checkRange(from, to);
882                    return new ArrayIntList(subArray(from, to - from, to - from));
883            }
884    
885            /**
886             * Returns a copied array of bytes containing all elements; the returned
887             * array has length = this.size().
888             */
889            public int[] toArray() {
890                    return subArray(0, size, size);
891            }
892    
893            /**
894             * Returns a string representation, containing the numeric String
895             * representation of each element.
896             */
897            public String toString() {
898                    //return toList().toString();
899                    StringBuffer buf = new StringBuffer(4*size);
900                    buf.append("[");
901                    for (int i = 0; i < size; i++) {
902                            buf.append(elements[i]);
903                            if (i < size-1) buf.append(", ");
904                    }
905                    buf.append("]");
906                    return buf.toString();
907            }
908    
909            /**
910             * Trims the capacity of the receiver to be the receiver's current size;
911             * Releases any superfluos internal memory. An application can use this
912             * operation to minimize the storage of the receiver.
913             */
914            public void trimToSize() {
915                    if (elements.length > size) {
916                            elements = subArray(0, size, size);
917                    }
918            }
919    
920            /**
921             * Checks if the given index is in range.
922             */
923            private void checkIndex(int index) {
924                    if (index >= size || index < 0)
925                            throw new IndexOutOfBoundsException("index: " + index
926                                                    + ", size: " + size);
927            }
928    
929            /**
930             * Checks if the given range is within the contained array's bounds.
931             */
932            private void checkRange(int from, int to) {
933                    if (from < 0 || from > to || to > size)
934                            throw new IndexOutOfBoundsException("from: " + from + ", to: "
935                                                    + to + ", size: " + size);
936            }
937    
938            /**
939             * Checks if the given size is within bounds.
940             */
941            private void checkSize(int newSize) {
942                    if (newSize < 0)
943                            throw new IndexOutOfBoundsException("newSize: " + newSize);
944            }
945    
946            /** efficient Serializable support */
947            private void writeObject(java.io.ObjectOutputStream out) throws IOException {
948                    out.defaultWriteObject();
949                    out.writeInt(elements.length);
950                    for (int i = 0; i < size; i++) {
951                            out.writeInt(elements[i]);
952                    }
953            }
954    
955            /** efficient Serializable support */
956            private void readObject(java.io.ObjectInputStream in) throws IOException,
957                            ClassNotFoundException {
958                    in.defaultReadObject();
959                    elements = new int[in.readInt()];
960                    for (int i = 0; i < size; i++) {
961                            elements[i] = in.readInt();
962                    }
963            }
964    
965            // **************************************************************************** 
966            // following are some method not deemed a) important enough or b) complex enough
967            // to warrant interface bloat:
968            // **************************************************************************** 
969                    
970    
971    //      /**
972    //       * Appends the specified elements to the end of this list.
973    //       * <p>
974    //       * If you need to append <code>elems[from..to)</code>, use
975    //       * <code>list.add(new ArrayIntList(elems).subList(from, to))</code> 
976    //       * or <code>list.add(IntBuffer.wrap(elems, from, to-from))</code>
977    //       * or similar.
978    //       * 
979    //       * @param elems
980    //       *            elements to be appended.
981    //       * @return <code>this</code> (for chaining convenience only)
982    //       */
983    //      public ArrayIntList add(int[] elems) {
984    //              replace(size, size, elems);
985    //              return this;
986    //      }
987    //      
988    //      /**
989    //       * Inserts the specified element before the specified index. Shifts the
990    //       * element currently at that index (if any) and any subsequent elements
991    //       * to the right. This is equivalent to <code>replace(index, index, elem, 1)</code>.
992    //       * 
993    //       * @param index
994    //       *            index before which the specified element is to be inserted
995    //       * @param elem
996    //       *            element to insert.
997    //       * @throws IndexOutOfBoundsException if index is out of range.
998    //       */
999    //      private void insert(int index, int elem) {
1000    //              replace(index, index, elem, 1);
1001    //      }
1002    //      
1003    //      /**
1004    //       * Inserts the specified elements before the specified index. Shifts the
1005    //       * element currently at that index (if any) and any subsequent elements
1006    //       * to the right.
1007    //       * 
1008    //       * @param index
1009    //       *            index before which the specified elements are to be inserted
1010    //       * @param elems
1011    //       *            elements to insert.
1012    //       * @throws IndexOutOfBoundsException if index is out of range.
1013    //       */
1014    //      private void insert(int index, int[] elems) {
1015    //              replace(index, index, elems);
1016    //      }
1017    //      
1018    //      /**
1019    //       * Inserts the specified elements before the specified index. Shifts the
1020    //       * element currently at that index (if any) and any subsequent elements
1021    //       * to the right.
1022    //       * 
1023    //       * @param index
1024    //       *            index before which the specified elements are to be inserted
1025    //       * @param elems
1026    //       *            elements to insert.
1027    //       * @throws IndexOutOfBoundsException if index is out of range.
1028    //       */
1029    //      private void insert(int index, ArrayIntList elems) {
1030    //              replace(index, index, elems);
1031    //      }
1032    //      
1033    //      /**
1034    //       * Inserts the remaining buffer elements before the specified index.
1035    //       * Shifts the element currently at that index (if any) and any subsequent
1036    //       * elements to the right.
1037    //       * 
1038    //       * @param index
1039    //       *            index before which the specified elements are to be inserted
1040    //       * @param elems
1041    //       *            elements to insert.
1042    //       * @throws IndexOutOfBoundsException if index is out of range.
1043    //       */
1044    //      private void insert(int index, IntBuffer elems) {
1045    //              replace(index, index, elems);
1046    //      }
1047    
1048    //      /**
1049    //       * Returns the index of the last occurrence of the specified element within
1050    //       * the range <code>[from..to)</code>. Returns <code>-1</code> if the
1051    //       * receiver does not contain such an element.
1052    //       * 
1053    //       * @param from
1054    //       *            the leftmost search index, inclusive.
1055    //       * @param to
1056    //       *            the rightmost search index, exclusive.
1057    //       * @param elem
1058    //       *            element to search for.
1059    //       * @return the index of the last occurrence of the element in the receiver;
1060    //       *         returns <code>-1</code> if the element is not found.
1061    //       * @throws IndexOutOfBoundsException
1062    //       *             if indexes are out of range.
1063    //       */
1064    //      public int lastIndexOf(int from, int to, int elem) {
1065    //              checkRange(from, to);
1066    //              int[] elems = elements;
1067    //              for (int i = to; --i >= from; ) {
1068    //                      if (elem == elems[i]) return i; //found
1069    //              }
1070    //              return -1; //not found
1071    //      }
1072    
1073    //      /**
1074    //       * Removes the element at the specified index. Shifts any subsequent
1075    //       * elements to the left. Keeps the current capacity.
1076    //       * 
1077    //       * @param index
1078    //       *            the index of the element to removed.
1079    //       * @throws IndexOutOfBoundsException
1080    //       *             if index is out of range
1081    //       */
1082    //      public void remove(int index) {
1083    //              remove(index, index+1);
1084    //      }
1085    
1086    //      /**
1087    //       * Reverses the order of elements in the range <code>[from..to)</code>.
1088    //       * Last becomes first, second last becomes second first, and so on.
1089    //       * <p>
1090    //       * Example: <code>[a,b,c,d].reverse(0,4) --> [d,c,b,a]</code>
1091    //       * 
1092    //       * @param from the index of the first element (inclusive)
1093    //       * @param to the index of the last element (exclusive).
1094    //       * @throws IndexOutOfBoundsException if indexes are out of range.
1095    //       */
1096    //      public void reverse(int from, int to) {
1097    //              checkRange(from, to);
1098    //              int[] elems = elements;         
1099    //              int middle = from + (to - from) / 2;
1100    //              to--;           
1101    //              for ( ; from < middle; from++, to--) { // swap
1102    //                      int tmp = elems[from];
1103    //                      elems[from] = elems[to];
1104    //                      elems[to] = tmp;
1105    //              }
1106    //      }
1107    
1108    //      /**
1109    //       * Sets the size to the given new size, expanding the list capacity if
1110    //       * necessary. 
1111    //       * <p>
1112    //       * Capacity expansion introduces a new backing array. If the new
1113    //       * size is greater than the current size the elements between the current
1114    //       * size and the new size will become legally accessible but have undefined
1115    //       * values. An application will typically want to set these elements to defined
1116    //       * values immediately after this method returns. Note that
1117    //       * <code>setSize(0)</code> effectively clears the list (as does
1118    //       * <code>remove(0, list.size()</code>).
1119    //       * 
1120    //       * @param newSize the new size.
1121    //       * @return <code>this</code> (for chaining convenience only)
1122    //       * @throws IndexOutOfBoundsException if new size is less than zero.
1123    //       */
1124    //      public ArrayIntList setSize(int newSize) {
1125    //              checkSize(newSize);
1126    //              ensureCapacity(newSize);
1127    //              // equivalent impl: shrinkOrExpand(0, size, newSize);
1128    //              size = newSize;
1129    //              return this;
1130    //      }
1131    
1132    //      /**
1133    //       * Returns a <code>java.util.ArrayList</code> containing a copy of all elements.
1134    //       */
1135    //      public java.util.ArrayList toList() {
1136    //              java.util.ArrayList list = new java.util.ArrayList(size);
1137    //              for (int i = 0; i < size; i++)
1138    //                      list.add(new Integer(elements[i]));
1139    //              return list;
1140    //      }
1141    
1142    }