|
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.ArrayByteList
Efficient resizable auto-expanding list holding byte
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 ByteBuffers (non-resizable) and
java.util.List and java.util.Set (resizable but not particularly useful for
non-trivial high-throughput processing on primitive types).
For example, this class is convenient to parse and/or assemble
variable-sized network messages if message lengths are a priori unknown.
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 ArrayByteList(new byte[] {0,1,2})); // insert and replace ArrayByteList demo = new ArrayByteList(new byte[] {0,1,2}); demo.replace(0,0, new byte[] {4,5}); // insert System.out.println(demo); // yields [4,5,0,1,2] demo.replace(0,2, new byte[] {6,7,8,9}); System.out.println(demo); // yields [6,7,8,9,0,1,2] // sort, search and remove System.out.println(demo.subList(1,3)); // yields [7,8] demo.sort(true); System.out.println(demo); System.out.println(demo.binarySearch((byte) 7)); demo.remove(4, 4+1); // remove elem at index 4 System.out.println(demo); System.out.println(demo.binarySearch((byte) 7)); // efficient file I/O System.out.println(new ArrayByteList(0).add(new java.io.FileInputStream("/etc/passwd")).toString(null)); new java.io.FileOutputStream("/tmp/test").write(demo.asArray(), 0, demo.size()); System.out.println(new ArrayByteList(0).add(new java.io.FileInputStream("/tmp/test"))); System.out.println(new ArrayByteList(0).add(new java.io.FileInputStream("/tmp/test").getChannel())); // network I/O via stream java.nio.charset.Charset charset = java.nio.charset.Charset.forName("ISO-8859-1"); System.out.println(new ArrayByteList(0).add(new java.net.URL("http://www.google.com").openStream()).toString(charset)); // simple HTTP via raw socket channel java.nio.channels.SocketChannel channel = java.nio.channels.SocketChannel.open(); channel.connect(new java.net.InetSocketAddress("www.google.com", 80)); channel.write(new ArrayByteList("GET / HTTP/1.0" + "\r\n\r\n", charset).asByteBuffer()); System.out.println(new ArrayByteList(0).add(channel).toString(charset));
Manipulating primitive values other than bytes is not directly
supported. However, this can be done via asByteBuffer()
along the following lines:
// get and set 4 byte integer value at end of list: list = ... int val = list.asByteBuffer().getInt(list.size() - 4); list.asByteBuffer().setInt(list.size() - 4, val * 10); // append 8 byte double value: list = ... double elemToAdd = 1234.0; list.replace(list.size(), list.size(), (byte)0, 8); // add 8 bytes at end list.asByteBuffer().putDouble(list.size() - 8, elemToAdd); // insert 8 byte double value at beginning: list = ... double elemToInsert = 1234.0; list.replace(0, 0, 0, 8); // insert 8 bytes at beginning list.asByteBuffer().putDouble(0, elemToInsert);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 | |
ArrayByteList()
Constructs an empty list. |
|
ArrayByteList(byte[] elems)
Constructs a list SHARING the specified elements. |
|
ArrayByteList(ByteBuffer elems)
Constructs a list containing a copy of the remaining buffer elements. |
|
ArrayByteList(CharSequence str,
Charset charset)
Constructs a list containing a copy of the encoded form of the given char sequence (String, StringBuffer, CharBuffer, etc). |
|
ArrayByteList(int initialCapacity)
Constructs an empty list with the specified initial capacity. |
Method Summary | |
ArrayByteList |
add(ArrayByteList elems)
Appends the specified elements to the end of this list. |
ArrayByteList |
add(byte elem)
Appends the specified element to the end of this list. |
ArrayByteList |
add(byte[] elems,
int offset,
int length)
Appends the elements in the range [offset..offset+length) to the end of this list. |
ArrayByteList |
add(ByteBuffer elems)
Appends the remaining buffer elements to the end of this list. |
ArrayByteList |
add(CharSequence str,
Charset charset)
Appends the encoded form of the given char sequence (String, StringBuffer, CharBuffer, etc). |
ArrayByteList |
add(InputStream elems)
Appends the remaining elements of the stream to the end of this list, reading until end-of-stream. |
ArrayByteList |
add(ReadableByteChannel elems)
Appends the remaining elements of the channel to the end of this list, reading until end-of-stream. |
byte[] |
asArray()
Returns the elements currently stored, including invalid elements between size and capacity, if any. |
ByteBuffer |
asByteBuffer()
Returns a buffer SHARING elements with the receiver. |
OutputStream |
asOutputStream()
Creates and returns an unsynchronized output stream that appends to this SHARED backing byte list. |
int |
binarySearch(byte key)
Searches the list for the specified value using the binary search algorithm. |
ArrayByteList |
clear()
Removes all elements but keeps the current capacity; Afterwards size() will yield zero. |
ArrayByteList |
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,
ArrayByteList pattern,
ArrayByteList replacement)
Finds all matching sublists in the range [from..to) and
replaces them with the given replacement. |
byte |
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,
ArrayByteList subList)
Returns the index of the first occurrence of the given sublist within the range this[from..to) . |
int |
indexOf(int from,
int to,
byte elem)
Returns the index of the first occurrence of the specified element within the range [from..to) . |
int |
lastIndexOf(int from,
int to,
ArrayByteList 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(ArrayByteList other)
Removes from the receiver all elements that are contained in the specified other list. |
void |
replace(int from,
int to,
ArrayByteList replacement)
Replaces all elements in the range [from..to) with the given replacement. |
void |
replace(int from,
int to,
byte[] 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,
ByteBuffer replacement,
int replacementSize)
Replaces all elements in the range [from..to) with the given replacement. |
void |
replace(int from,
int to,
byte replacement,
int replacementSize)
Replaces all elements in the range [from..to) with the given replacement. |
boolean |
retainAll(ArrayByteList other)
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,
byte 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. |
ArrayByteList |
subList(int from,
int to)
Constructs and returns a new list containing a copy of the elements in the range [from..to) . |
byte[] |
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. |
String |
toString(Charset charset)
Returns a decoded string representation of all elements. |
String |
toString(int from,
int to,
Charset charset)
Returns a decoded string representation of the bytes in the given range [from..to) . |
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 ArrayByteList()
public ArrayByteList(int initialCapacity)
initialCapacity
- the number of elements the receiver can hold without
auto-expanding itself by allocating new internal memory.public ArrayByteList(byte[] 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 ArrayByteList(byte[] elems).copy()
or similar.
If you need a list containing a copy of elems[from..to)
, use
list = new ArrayByteList(to-from).add(elems, from, to-from)
or list = new ArrayByteList(ByteBuffer.wrap(elems, from, to-from))
or similar.
elems
- the array backing the constructed listpublic ArrayByteList(ByteBuffer elems)
elems.remaining()
.
elems
- the elements initially to be added to the listpublic ArrayByteList(CharSequence str, Charset charset)
str
- the string to convert.charset
- the charset to convert with (e.g. Charset.forName("US-ASCII")
,
Charset.forName("ISO-8859-1")
).
If null
uses Charset.forName("UTF-8")
as the default charset.Method Detail |
public ArrayByteList add(byte elem)
elem
- element to be appended to this list.
this
(for chaining convenience only)public ArrayByteList add(byte[] 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 ArrayByteList add(ArrayByteList elems)
elems
- elements to be appended.
this
(for chaining convenience only)public ArrayByteList add(ByteBuffer elems)
elems
- elements to be appended.
this
(for chaining convenience only)public ArrayByteList add(CharSequence str, Charset charset)
str
- the string to convert.charset
- the charset to convert with (e.g. Charset.forName("US-ASCII")
,
Charset.forName("ISO-8859-1")
).
If null
uses Charset.forName("UTF-8")
as the default charset.
this
(for chaining convenience only)public ArrayByteList add(InputStream elems) throws IOException
elems
- the input stream to read from.
this
(for chaining convenience only)
IOException
- if an I/O error occurs.public ArrayByteList add(ReadableByteChannel elems) throws IOException
elems
- the channel to read from.
this
(for chaining convenience only)
IOException
- if an I/O error occurs.public byte[] 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 ByteBuffer asByteBuffer()
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 OutputStream asOutputStream()
ByteArrayOutputStream
.
Writing to the stream means adding (appending) elements to the end of the (auto-expanding) backing list.
Closing the stream has no effect. The stream's methods can be called after the stream has been closed without generating an IOException. In fact the stream implementation never ever throws an IOException.
If your legacy code requires adapting to an InputStream
instead,
simply use the non-copying ByteArrayInputStream
, for example as in
new java.io.ByteArrayInputStream(list.asArray(), 0, list.size())
.
public int binarySearch(byte key)
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.
key
- the value to be searched for.
(-(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.sort(boolean)
public ArrayByteList clear()
size()
will yield zero.
this
(for chaining convenience only)public ArrayByteList 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, ArrayByteList pattern, ArrayByteList 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 byte get(int index)
index
- index of element to return.
IndexOutOfBoundsException
- if index is out of range.public int hashCode()
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)
Object.hashCode()
,
Object.equals(Object)
,
equals(Object)
,
List.hashCode()
public int indexOf(int from, int to, ArrayByteList 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, byte 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, ArrayByteList 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(ArrayByteList other)
Example: [0,1,2,2,3,3,0].removeAll([2,1]) --> [0,3,3,0]
other
- the other list to test against (remains unmodified by this method).
true
if the receiver changed as a result of the
call.public void replace(int from, int to, byte[] 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, ArrayByteList 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, ByteBuffer 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, byte 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(ArrayByteList other)
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); 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()));
other
- the other list to test against (remains unmodified by this method).
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, byte 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 ArrayByteList 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 byte[] toArray()
public String toString()
public String toString(Charset charset)
charset
- the charset to convert with (e.g. Charset.forName("US-ASCII")
,
Charset.forName("ISO-8859-1")
).
If null
uses Charset.forName("UTF-8")
as the default charset.public String toString(int from, int to, Charset charset)
[from..to)
.
from
- the index of the first element (inclusive).to
- the index of the last element (exclusive).charset
- the charset to convert with (e.g. Charset.forName("US-ASCII")
,
Charset.forName("ISO-8859-1")
).
If null
uses Charset.forName("UTF-8")
as the default charset.
IndexOutOfBoundsException
- if indexes are out of rangepublic void trimToSize()
|
Sea 0.4.0 | ||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |