|
Sea 0.4.0 | ||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object gov.lbl.dsd.sea.nio.util.ArrayIntList
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.
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 |
public ArrayIntList()
public ArrayIntList(int initialCapacity)
initialCapacity
- the number of elements the receiver can hold without
auto-expanding itself by allocating new internal memory.public ArrayIntList(int[] elems)
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.
elems
- the array backing the constructed listpublic ArrayIntList(IntBuffer elems)
elems.remaining()
.
elems
- the elements initially to be added to the listMethod Detail |
public ArrayIntList add(int elem)
elem
- element to be appended to this list.
this
(for chaining convenience only)public ArrayIntList add(int[] elems, int offset, int length)
[offset..offset+length)
to the end of this list.
elems
- the elements to be appendedoffset
- the offset of the first element to add (inclusive)length
- the number of elements to add
this
(for chaining convenience only)
IndexOutOfBoundsException
- if indexes are out of range.public ArrayIntList add(ArrayIntList elems)
elems
- elements to be appended.
this
(for chaining convenience only)public ArrayIntList add(IntBuffer elems)
elems
- elements to be appended.
this
(for chaining convenience only)public int[] asArray()
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.
public IntBuffer asIntBuffer()
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.
public int binarySearch(int key)
key
- the value to be searched for.
sort(boolean)
public ArrayIntList clear()
size()
will yield zero.
this
(for chaining convenience only)public ArrayIntList copy()
public boolean equals(Object otherObj)
otherObj
- the Object to be compared for equality with the receiver.
public void ensureCapacity(int minCapacity)
minCapacity
- the desired minimum capacity.public int findReplace(int from, int to, ArrayIntList pattern, ArrayIntList replacement)
[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]
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 forreplacement
- the elements to replace the found sublists
IndexOutOfBoundsException
- if indexes are out of range.
IllegalArgumentException
- if pattern.size() == 0.public int get(int index)
index
- index of element to return.
IndexOutOfBoundsException
- if index is out of range.public int hashCode()
Warning: run time complexity is O(N)
Object.hashCode()
,
Object.equals(Object)
,
equals(Object)
,
List.hashCode()
public int indexOf(int from, int to, ArrayIntList subList)
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
from
- the leftmost search index within the receiver, inclusive.to
- the rightmost search index within the receiver, exclusive.subList
- the sublist to search for.
-1
if the sublist is not found.
IndexOutOfBoundsException
- if indexes are out of rangepublic int indexOf(int from, int to, int elem)
[from..to)
. Returns -1
if the
receiver does not contain such an element.
from
- the leftmost search index, inclusive.to
- the rightmost search index, exclusive.elem
- element to search for.
-1
if the element is not found.
IndexOutOfBoundsException
- if indexes are out of rangepublic int lastIndexOf(int from, int to, ArrayIntList subList)
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
from
- the leftmost search index within the receiver, inclusive.to
- the rightmost search index within the receiver, exclusive.subList
- the sublist to search for.
-1
if the sublist is not found.
IndexOutOfBoundsException
- if indexes are out of rangepublic void remove(int from, int to)
[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())
.
from
- the index of the first element to removed (inclusive).to
- the index of the last element to removed (exclusive).
IndexOutOfBoundsException
- if indexes are out of rangepublic boolean removeAll(ArrayIntList other, boolean isOtherSorted)
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);
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).
true
if the receiver changed as a result of the
call.public void replace(int from, int to, int[] replacement, int offset, int length)
[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.
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 elementsoffset
- the offset of the first replacing element (inclusive)length
- the number of replacing elements
IndexOutOfBoundsException
- if indexes are out of range.public void replace(int from, int to, ArrayIntList replacement)
[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]
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
IndexOutOfBoundsException
- if indexes are out of range.public void replace(int from, int to, IntBuffer replacement, int replacementSize)
[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()
.
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 elementsreplacementSize
- the number of replacing elements
IndexOutOfBoundsException
- if indexes are out of range.public void replace(int from, int to, int replacement, int replacementSize)
[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]
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 elementsreplacementSize
- the number of times replacement
is to replace the replaced elements
IndexOutOfBoundsException
- if indexes are out of range.public boolean retainAll(ArrayIntList other, boolean isOtherSorted)
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));
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).
true
if the receiver changed as a result of the
call.public void rotate(int from, int to, int distance)
[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).
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
.
IndexOutOfBoundsException
- if indexes are out of range.Collections.rotate(java.util.List, int)
public void set(int index, int element)
index
- index of element to replace.element
- element to be stored at the specified index.
IndexOutOfBoundsException
- if index is out of range.public int size()
public void sort(boolean removeDuplicates)
[3,2,2,1].sort(false) --> [1,2,2,3] [3,2,2,1].sort(true) --> [1,2,3]
removeDuplicates
- remove duplicate elements or keep them?public ArrayIntList subList(int from, int to)
[from..to)
.
from
- the index of the first element (inclusive).to
- the index of the last element (exclusive).
IndexOutOfBoundsException
- if indexes are out of rangepublic int[] toArray()
public String toString()
public void trimToSize()
|
Sea 0.4.0 | ||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |