Sea 0.4.0

gov.lbl.dsd.sea.nio.util
Class ArrayIntList

java.lang.Object
  extended bygov.lbl.dsd.sea.nio.util.ArrayIntList
All Implemented Interfaces:
Serializable

public final class ArrayIntList
extends Object
implements Serializable

Efficient resizable auto-expanding list holding int elements; implemented with arrays. The API is intended for easy non-trivial high-throughput processing, and (in an elegant and compact yet different form) provides all list and set functionality of the java.util collections package, as well as a little more. This API fills the gap between raw arrays (non-resizable), nio IntBuffers (non-resizable) and java.util.List and java.util.Set (resizable but not particularly useful for non-trivial high-throughput processing on primitive types).

Indexed element access is zero based: valid indexes range from index 0 (inclusive) to index list.size() (exclusive). Attempts to access out-of-range indexes will throw an IndexOutOfBoundsException.

Note that this implementation is not synchronized, hence not inherently thread safe.

Example usage:

System.out.println(new ArrayIntList(new int[] {0,1,2}));

This class requires JDK 1.4 or higher; otherwise it has zero dependencies. Hence you can simply copy the file into your own project if minimal dependencies are desired.

Also note that the compiler can (and will) easily inline all methods, then optimize away. In fact with the Sun jdk-1.4.2 server VM it is hard to measure any difference to raw array manipulations at abstraction level zero.

Version:
$Revision: 1.36 $, $Date: 2004/08/07 19:13:47 $
See Also:
Serialized Form

Constructor Summary
ArrayIntList()
          Constructs an empty list.
ArrayIntList(int initialCapacity)
          Constructs an empty list with the specified initial capacity.
ArrayIntList(int[] elems)
          Constructs a list SHARING the specified elements.
ArrayIntList(IntBuffer elems)
          Constructs a list containing a copy of the remaining buffer elements.
 
Method Summary
 ArrayIntList add(ArrayIntList elems)
          Appends the specified elements to the end of this list.
 ArrayIntList add(int elem)
          Appends the specified element to the end of this list.
 ArrayIntList add(int[] elems, int offset, int length)
          Appends the elements in the range [offset..offset+length) to the end of this list.
 ArrayIntList add(IntBuffer elems)
          Appends the remaining buffer elements to the end of this list.
 int[] asArray()
          Returns the elements currently stored, including invalid elements between size and capacity, if any.
 IntBuffer asIntBuffer()
          Returns a buffer SHARING elements with the receiver.
 int binarySearch(int key)
          Searches the list for the specified value using the binary search algorithm.
 ArrayIntList clear()
          Removes all elements but keeps the current capacity; Afterwards size() will yield zero.
 ArrayIntList copy()
          Constructs and returns a new list that is a deep copy of the receiver.
 void ensureCapacity(int minCapacity)
          Ensures that the receiver can hold at least the specified number of elements without needing to allocate new internal memory.
 boolean equals(Object otherObj)
          Compares the specified Object with the receiver.
 int findReplace(int from, int to, ArrayIntList pattern, ArrayIntList replacement)
          Finds all matching sublists in the range [from..to) and replaces them with the given replacement.
 int get(int index)
          Returns the element at the specified index.
 int hashCode()
          Returns the hash code value for this list.
 int indexOf(int from, int to, ArrayIntList subList)
          Returns the index of the first occurrence of the given sublist within the range this[from..to).
 int indexOf(int from, int to, int elem)
          Returns the index of the first occurrence of the specified element within the range [from..to).
 int lastIndexOf(int from, int to, ArrayIntList subList)
          Returns the index of the last occurrence of the given sublist within the range this[from..to).
 void remove(int from, int to)
          Removes the elements in the range [from..to).
 boolean removeAll(ArrayIntList other, boolean isOtherSorted)
          Removes from the receiver all elements that are contained in the specified other list.
 void replace(int from, int to, ArrayIntList replacement)
          Replaces all elements in the range [from..to) with the given replacement.
 void replace(int from, int to, int[] replacement, int offset, int length)
          Replaces all elements in the range [from..to) with the elements replacement[offset..offset+length).
 void replace(int from, int to, IntBuffer replacement, int replacementSize)
          Replaces all elements in the range [from..to) with the given replacement.
 void replace(int from, int to, int replacement, int replacementSize)
          Replaces all elements in the range [from..to) with the given replacement.
 boolean retainAll(ArrayIntList other, boolean isOtherSorted)
          Retains (keeps) only the elements in the receiver that are contained in the specified other list.
 void rotate(int from, int to, int distance)
          Rotates (shifts) the elements in the range [from..to) by the specified distance.
 void set(int index, int element)
          Replaces the element at the specified index with the specified element.
 int size()
          Returns the number of contained elements.
 void sort(boolean removeDuplicates)
          Sorts the elements into ascending numerical order.
 ArrayIntList subList(int from, int to)
          Constructs and returns a new list containing a copy of the elements in the range [from..to).
 int[] toArray()
          Returns a copied array of bytes containing all elements; the returned array has length = this.size().
 String toString()
          Returns a string representation, containing the numeric String representation of each element.
 void trimToSize()
          Trims the capacity of the receiver to be the receiver's current size; Releases any superfluos internal memory.
 
Methods inherited from class java.lang.Object
getClass, notify, notifyAll, wait, wait, wait
 

Constructor Detail

ArrayIntList

public ArrayIntList()
Constructs an empty list.


ArrayIntList

public ArrayIntList(int initialCapacity)
Constructs an empty list with the specified initial capacity.

Parameters:
initialCapacity - the number of elements the receiver can hold without auto-expanding itself by allocating new internal memory.

ArrayIntList

public ArrayIntList(int[] elems)
Constructs a list SHARING the specified elements. The initial size and capacity of the list is the length of the backing array.

WARNING: For efficiency reasons and to keep memory usage low, the array is SHARED, not copied . So if subsequently you modify the specified array directly via the [] operator, be sure you know what you're doing.

If you rather need copying behaviour, use copy = new ArrayIntList(int[] elems).copy() or similar.

If you need a list containing a copy of elems[from..to), use list = new ArrayIntList(to-from).add(elems, from, to-from) or list = new ArrayIntList(IntBuffer.wrap(elems, from, to-from)) or similar.

Parameters:
elems - the array backing the constructed list

ArrayIntList

public ArrayIntList(IntBuffer elems)
Constructs a list containing a copy of the remaining buffer elements. The initial size and capacity of the list is elems.remaining().

Parameters:
elems - the elements initially to be added to the list
Method Detail

add

public ArrayIntList add(int elem)
Appends the specified element to the end of this list.

Parameters:
elem - element to be appended to this list.
Returns:
this (for chaining convenience only)

add

public ArrayIntList add(int[] elems,
                        int offset,
                        int length)
Appends the elements in the range [offset..offset+length) to the end of this list.

Parameters:
elems - the elements to be appended
offset - the offset of the first element to add (inclusive)
length - the number of elements to add
Returns:
this (for chaining convenience only)
Throws:
IndexOutOfBoundsException - if indexes are out of range.

add

public ArrayIntList add(ArrayIntList elems)
Appends the specified elements to the end of this list.

Parameters:
elems - elements to be appended.
Returns:
this (for chaining convenience only)

add

public ArrayIntList add(IntBuffer elems)
Appends the remaining buffer elements to the end of this list.

Parameters:
elems - elements to be appended.
Returns:
this (for chaining convenience only)

asArray

public int[] asArray()
Returns the elements currently stored, including invalid elements between size and capacity, if any.

WARNING: For efficiency reasons and to keep memory usage low, the array is SHARED, not copied . So if subsequently you modify the returned array directly via the [] operator, be sure you know what you're doing.

Returns:
the elements currently stored.

asIntBuffer

public IntBuffer asIntBuffer()
Returns a buffer SHARING elements with the receiver. The buffer will have the default NIO byte order, which is ByteOrder.nativeOrder().

WARNING: For efficiency reasons and to keep memory usage low, the array is SHARED, not copied . So if subsequently you modify the returned buffer, be sure you know what you're doing.


binarySearch

public int binarySearch(int key)
Searches the list for the specified value using the binary search algorithm. The list must be sorted (as by the sort method) prior to making this call. If it is not sorted, the results are undefined. If the list contains multiple elements with the specified value, there is no guarantee which one will be found.

Parameters:
key - the value to be searched for.
Returns:
index of the search key, if it is contained in the list; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the list: the index of the first element greater than the key, or list.size(), if all elements in the list are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.
See Also:
sort(boolean)

clear

public ArrayIntList clear()
Removes all elements but keeps the current capacity; Afterwards size() will yield zero.

Returns:
this (for chaining convenience only)

copy

public ArrayIntList copy()
Constructs and returns a new list that is a deep copy of the receiver.

Returns:
a deep copy of the receiver.

equals

public boolean equals(Object otherObj)
Compares the specified Object with the receiver. Returns true if and only if the specified Object is also a list of the same type, both Lists have the same size, and all corresponding pairs of elements in the two Lists are identical. In other words, two Lists are defined to be equal if they contain the same elements in the same order.

Parameters:
otherObj - the Object to be compared for equality with the receiver.
Returns:
true if the specified Object is equal to the receiver.

ensureCapacity

public void ensureCapacity(int minCapacity)
Ensures that the receiver can hold at least the specified number of elements without needing to allocate new internal memory. If necessary, allocates new internal memory and increases the capacity of the receiver.

Parameters:
minCapacity - the desired minimum capacity.

findReplace

public int findReplace(int from,
                       int to,
                       ArrayIntList pattern,
                       ArrayIntList replacement)
Finds all matching sublists in the range [from..to) and replaces them with the given replacement. A sublist matches if it is equal to the given pattern. The pattern must have a size greater than zero. The replacement can have any size. Examples:
 [a,b,c,d,b,c].findReplace(0,6, [b,c], [x,y,z]) --> [a,x,y,z,d,x,y,z]
 [a,b,c,d,b,c].findReplace(0,6, [b,c], []) --> [a,d]
 

Parameters:
from - the index of the first element to search (inclusive)
to - the index of the last element to search (exclusive).
pattern - the sublist to search for
replacement - the elements to replace the found sublists
Returns:
the number of sublists found matching the pattern
Throws:
IndexOutOfBoundsException - if indexes are out of range.
IllegalArgumentException - if pattern.size() == 0.

get

public int get(int index)
Returns the element at the specified index.

Parameters:
index - index of element to return.
Throws:
IndexOutOfBoundsException - if index is out of range.

hashCode

public int hashCode()
Returns the hash code value for this list. The algorithm ensures that list1.equals(list2) implies that list1.hashCode()==list2.hashCode() for any two lists, list1 and list2, as required by the general contract of Object.hashCode.

Warning: run time complexity is O(N)

Returns:
the hash code value for this list.
See Also:
Object.hashCode(), Object.equals(Object), equals(Object), List.hashCode()

indexOf

public int indexOf(int from,
                   int to,
                   ArrayIntList subList)
Returns the index of the first occurrence of the given sublist within the range this[from..to). Returns -1 if the receiver does not contain such a sublist. Examples:
 
 [a,b,c,d,e,b,c,d].indexOf(0,8, [b,c,d]) --> 1
 [a,b,c,d,e].indexOf(0,5, [b,c,d]) --> 1
 [a,b,c,d,e].indexOf(1,4, [b,c,d]) --> 1
 [a,b,c,d,e].indexOf(0,5, [x,y])   --> -1
 [a,b,c,d,e].indexOf(0,3, [b,c,d]) --> -1
 [a].indexOf(0,1, [a,b,c]) --> -1
 [a,b,c,d,e].indexOf(2,3, []) --> 2 // empty sublist is always found
 [].indexOf(0,0, []) --> 0
 

Parameters:
from - the leftmost search index within the receiver, inclusive.
to - the rightmost search index within the receiver, exclusive.
subList - the sublist to search for.
Returns:
the index of the first occurrence of the sublist in the receiver; returns -1 if the sublist is not found.
Throws:
IndexOutOfBoundsException - if indexes are out of range

indexOf

public int indexOf(int from,
                   int to,
                   int elem)
Returns the index of the first occurrence of the specified element within the range [from..to). Returns -1 if the receiver does not contain such an element.

Parameters:
from - the leftmost search index, inclusive.
to - the rightmost search index, exclusive.
elem - element to search for.
Returns:
the index of the first occurrence of the element in the receiver; returns -1 if the element is not found.
Throws:
IndexOutOfBoundsException - if indexes are out of range

lastIndexOf

public int lastIndexOf(int from,
                       int to,
                       ArrayIntList subList)
Returns the index of the last occurrence of the given sublist within the range this[from..to). Returns -1 if the receiver does not contain such a sublist. Examples:
 
 [a,b,c,d,e,b,c,d].lastIndexOf(0,8, [b,c,d]) --> 5
 [a,b,c,d,e].lastIndexOf(0,5, [b,c,d]) --> 1
 [a,b,c,d,e].lastIndexOf(1,4, [b,c,d]) --> 1
 [a,b,c,d,e].lastIndexOf(0,5, [x,y])   --> -1
 [a,b,c,d,e].lastIndexOf(0,3, [b,c,d]) --> -1
 [a].lastIndexOf(0,1, [a,b,c]) --> -1
 [a,b,c,d,e].lastIndexOf(2,3, []) --> 3 // empty sublist is always found
 [].lastIndexOf(0,0, []) --> 0
 

Parameters:
from - the leftmost search index within the receiver, inclusive.
to - the rightmost search index within the receiver, exclusive.
subList - the sublist to search for.
Returns:
the index of the last occurrence of the sublist in the receiver; returns -1 if the sublist is not found.
Throws:
IndexOutOfBoundsException - if indexes are out of range

remove

public void remove(int from,
                   int to)
Removes the elements in the range [from..to). Shifts any subsequent elements to the left. Keeps the current capacity. Note: To remove a single element use remove(index, index+1). To remove all elements use remove(0, list.size()).

Parameters:
from - the index of the first element to removed (inclusive).
to - the index of the last element to removed (exclusive).
Throws:
IndexOutOfBoundsException - if indexes are out of range

removeAll

public boolean removeAll(ArrayIntList other,
                         boolean isOtherSorted)
Removes from the receiver all elements that are contained in the specified other list.

Example: [0,1,2,2,3,3,0].removeAll([2,1]) --> [0,3,3,0]

An efficient asymmetric set difference can be computed along the following lines:

 list1.sort(true);
 list2.sort(true);
 list1.removeAll(list2, true);
 System.out.println(list1);
 

Parameters:
other - the other list to test against (remains unmodified by this method).
isOtherSorted - true if the other list is already sorted ascending, false otherwise (being sorted improves performance).
Returns:
true if the receiver changed as a result of the call.

replace

public void replace(int from,
                    int to,
                    int[] replacement,
                    int offset,
                    int length)
Replaces all elements in the range [from..to) with the elements replacement[offset..offset+length). The replacement can have any length. Increases (or decreases) the receiver's size by length - (to - from). Use from==to to perform pure insertion.

Parameters:
from - the index of the first element to replace (inclusive)
to - the index of the last element to replace (exclusive).
replacement - the elements to replace the replaced elements
offset - the offset of the first replacing element (inclusive)
length - the number of replacing elements
Throws:
IndexOutOfBoundsException - if indexes are out of range.

replace

public void replace(int from,
                    int to,
                    ArrayIntList replacement)
Replaces all elements in the range [from..to) with the given replacement. The replacement can have any length. Increases (or decreases) the receiver's size by replacement.size - (to - from). Use from==to to perform pure insertion. Examples:
 [a,b,c,d,e].replace(1,4, [x,y]) --> [a,x,y,e]
 [a,b].replace(1,1, [w,x,y,z]) --> [a,w,x,y,z,b]
 

Parameters:
from - the index of the first element to replace (inclusive)
to - the index of the last element to replace (exclusive).
replacement - the elements to replace the replaced elements
Throws:
IndexOutOfBoundsException - if indexes are out of range.

replace

public void replace(int from,
                    int to,
                    IntBuffer replacement,
                    int replacementSize)
Replaces all elements in the range [from..to) with the given replacement. The replacement consists of replacement[replacement.position() .. replacement.position() + replacementSize). Increases (or decreases) the receiver's size by replacementSize - (to - from). Use from==to to perform pure insertion. Examples:
 [a,b,c,d,e].replace(1,4, [x,y], 2) --> [a,x,y,e]
 [a,b].replace(1,1, [w,x,y,z], 4) --> [a,w,x,y,z,b]
 
There must hold: 0 < replacementSize <= replacement.remaining().

Parameters:
from - the index of the first element to replace (inclusive)
to - the index of the last element to replace (exclusive).
replacement - the elements to replace the replaced elements
replacementSize - the number of replacing elements
Throws:
IndexOutOfBoundsException - if indexes are out of range.

replace

public void replace(int from,
                    int to,
                    int replacement,
                    int replacementSize)
Replaces all elements in the range [from..to) with the given replacement. The replacement can have any length >= 0. Increases (or decreases) the receiver's size by replacementSize - (to - from). Use from==to to perform pure insertion. Examples:
 [a,b,c,d,e].replace(1,4,x,4) --> [a,x,x,x,x,e]
 [a,b,c,d,e].replace(0,0,x,4) --> [x,x,x,x,a,b,c,d,e]
 

Parameters:
from - the index of the first element to replace (inclusive)
to - the index of the last element to replace (exclusive).
replacement - the elements to replace the replaced elements
replacementSize - the number of times replacement is to replace the replaced elements
Throws:
IndexOutOfBoundsException - if indexes are out of range.

retainAll

public boolean retainAll(ArrayIntList other,
                         boolean isOtherSorted)
Retains (keeps) only the elements in the receiver that are contained in the specified other list. In other words, removes from the receiver all of its elements that are not contained in the specified other list.

Example: [0,1,2,2,3,1].retainAll([2,1]) --> [1,2,2,1]

An efficient set intersection can be computed along the following lines:

 list1.sort(true);
 list2.sort(true);
 list1.retainAll(list2, true);
 System.out.println("list1.retainAll(list2) = " + list1);
 // as a convenient byproduct we now know if list2 is a SUBSET of list1:
 System.out.println("list1.containsAll(list2) = " + (list1.size() == list2.size()));
 // as a convenient byproduct we now know if list1 contains ANY element of list2:
 System.out.println("list1.containsAny(list2) = " + (list1.size() > 0));
 

Parameters:
other - the other list to test against (remains unmodified by this method).
isOtherSorted - true if the other list is already sorted ascending, false otherwise (being sorted improves performance).
Returns:
true if the receiver changed as a result of the call.

rotate

public void rotate(int from,
                   int to,
                   int distance)
Rotates (shifts) the elements in the range [from..to) by the specified distance. After calling this method, the element at index i will be the element previously at index (i - distance) mod to-from, for all values of i between from (inclusive) and to, exclusive. (This method has no effect on the size of the list.) Examples:
   [a, b, c, d, e].rotate(0, 5, 1)  --> [e, a, b, c, d]
   [a, b, c, d, e].rotate(0, 5, 2)  --> [d, e, a, b, c]
   [a, b, c, d, e].rotate(1, 4, -1) --> [a, c, d, b, e]
 

To move elements rightwards, use a positive shift distance. To move elements leftwards, use a negative shift distance.

Note that this method can usefully be applied to sublists to move one or more elements within a list while preserving the order of the remaining elements.

This implementation exchanges the first element into the location it should go, and then repeatedly exchanges the displaced element into the location it should go until a displaced element is swapped into the first element. If necessary, the process is repeated on the second and successive elements, until the rotation is complete. This algorithm is efficient: Time complexity is linear O(to-from), space complexity is constant O(1).

Parameters:
from - the index of the first element to rotate (inclusive)
to - the index of the last element to rotate (exclusive).
distance - the distance to rotate the list. There are no constraints on this value; for example it may be zero, negative, or greater than to-from.
Throws:
IndexOutOfBoundsException - if indexes are out of range.
See Also:
Collections.rotate(java.util.List, int)

set

public void set(int index,
                int element)
Replaces the element at the specified index with the specified element.

Parameters:
index - index of element to replace.
element - element to be stored at the specified index.
Throws:
IndexOutOfBoundsException - if index is out of range.

size

public int size()
Returns the number of contained elements.

Returns:
the number of elements contained in the receiver.

sort

public void sort(boolean removeDuplicates)
Sorts the elements into ascending numerical order. For mathematical set operations, optionally removes duplicate elements before returning. Examples:
 [3,2,2,1].sort(false) --> [1,2,2,3]
 [3,2,2,1].sort(true)  --> [1,2,3]
 

Parameters:
removeDuplicates - remove duplicate elements or keep them?

subList

public ArrayIntList subList(int from,
                            int to)
Constructs and returns a new list containing a copy of the elements in the range [from..to).

Parameters:
from - the index of the first element (inclusive).
to - the index of the last element (exclusive).
Returns:
a new list
Throws:
IndexOutOfBoundsException - if indexes are out of range

toArray

public int[] toArray()
Returns a copied array of bytes containing all elements; the returned array has length = this.size().


toString

public String toString()
Returns a string representation, containing the numeric String representation of each element.


trimToSize

public void trimToSize()
Trims the capacity of the receiver to be the receiver's current size; Releases any superfluos internal memory. An application can use this operation to minimize the storage of the receiver.


Sea 0.4.0