public class IntArrayFrontCodedList extends AbstractObjectList<int[]> implements Serializable, Cloneable
This class stores immutably a list of arrays in a single large array
using front coding (of course, the compression will be reasonable only if
the list is sorted lexicographically—see below). It implements an
immutable type-specific list that returns the i-th array when
calling get(i). The returned array may be
freely modified.
Front coding is based on the idea that if the i-th and the (i+1)-th array have a common prefix, we might store the length of the common prefix, and then the rest of the second array.
This approach, of course, requires that once in a while an array is
stored entirely. The ratio() arrays). A higher ratio
means more compression, but means also a longer access time, as more arrays
have to be probed to build the result. Note that we must build an array
every time get(int) is called, but this class provides also methods
that extract one of the stored arrays in a given array, reducing garbage
collection. See the documentation of the family of get()
methods.
By setting the ratio to 1 we actually disable front coding: however, we still have a data structure storing large list of arrays with a reduced overhead (just one integer per array, plus the space required for lengths).
Note that the typical usage of front-coded lists is under the form of serialized objects; usually, the data that has to be compacted is processed offline, and the resulting structure is stored permanently. Since the pointer array is not stored, the serialized format is very small.
All arrays are stored in a big array. A separate array of pointers indexes arrays whose position is a multiple of the ratio: thus, a higher ratio means also less pointers.
More in detail, an array whose position is a multiple of the ratio is
stored as the array length, followed by the elements of the array. The array
length is coded by a simple variable-length list of k-1 bit
blocks, where k is the number of bits of the underlying primitive
type. All other arrays are stored as follows: let common the
length of the maximum common prefix between the array and its predecessor.
Then we store the array length decremented by common, followed
by common, followed by the array elements whose index is
greater than or equal to common. For instance, if we store
foo, foobar, football and
fool in a front-coded character-array list with ratio 3, the
character array will contain
3 f o o 3 3 b a r 5 3 t b a l l 4 f o o l
AbstractObjectList.ObjectSubList<K>| Modifier and Type | Field and Description |
|---|---|
protected int[][] |
array
The big array containing the compressed arrays.
|
protected int |
n
The number of arrays in the list.
|
protected long[] |
p
The pointers to entire arrays in the list.
|
protected int |
ratio
The ratio of this front-coded list.
|
static long |
serialVersionUID |
| Constructor and Description |
|---|
IntArrayFrontCodedList(Collection<int[]> c,
int ratio)
Creates a new front-coded list containing the arrays in the given collection.
|
IntArrayFrontCodedList(Iterator<int[]> arrays,
int ratio)
Creates a new front-coded list containing the arrays returned by the given iterator.
|
| Modifier and Type | Method and Description |
|---|---|
int |
arrayLength(int index)
Computes the length of the array at the given index.
|
IntArrayFrontCodedList |
clone()
Returns a copy of this list.
|
int[] |
get(int index) |
int |
get(int index,
int[] a)
Stores in the given array an array stored in this front-coded list.
|
int |
get(int index,
int[] a,
int offset,
int length)
Stores in the given array elements from an array stored in this front-coded list.
|
int[] |
getArray(int index) |
ObjectListIterator<int[]> |
listIterator(int start)
Returns a type-specific list iterator on the list starting at a given index.
|
int |
ratio()
Returns the ratio of this list.
|
protected long[] |
rebuildPointerArray()
Computes the pointer array using the currently set ratio, number of elements and underlying array.
|
int |
size() |
String |
toString() |
add, add, addAll, addAll, addElements, addElements, compareTo, contains, ensureIndex, ensureRestrictedIndex, equals, getElements, hashCode, indexOf, iterator, lastIndexOf, listIterator, objectListIterator, objectListIterator, objectSubList, peek, pop, push, remove, removeElements, set, size, subList, topcontainsAll, isEmpty, objectIterator, removeAll, retainAll, toArray, toArrayclear, removefinalize, getClass, notify, notifyAll, wait, wait, waitclear, containsAll, isEmpty, remove, removeAll, retainAll, toArray, toArrayobjectIterator, toArraypublic static final long serialVersionUID
protected final int n
protected final int ratio
protected final int[][] array
protected transient long[] p
public IntArrayFrontCodedList(Iterator<int[]> arrays, int ratio)
arrays - an iterator returning arrays.ratio - the desired ratio.public IntArrayFrontCodedList(Collection<int[]> c, int ratio)
c - a collection containing arrays.ratio - the desired ratio.public int ratio()
public int arrayLength(int index)
index - an index.index-th array.public int[] getArray(int index)
get(int)public int get(int index,
int[] a,
int offset,
int length)
index - an index.a - the array that will store the result.offset - an offset into a where elements will be store.length - a maximum number of elements to store in a.a can hold the extracted elements, the number of extracted elements;
otherwise, the number of remaining elements with the sign changed.public int get(int index,
int[] a)
index - an index.a - the array that will store the content of the result (we assume that it can hold the result).a can hold the extracted elements, the number of extracted elements;
otherwise, the number of remaining elements with the sign changed.public int size()
size in interface Collection<int[]>size in interface List<int[]>size in class AbstractCollection<int[]>public ObjectListIterator<int[]> listIterator(int start)
ObjectListlistIterator in interface ObjectList<int[]>listIterator in interface List<int[]>listIterator in class AbstractObjectList<int[]>List.listIterator(int)public IntArrayFrontCodedList clone()
public String toString()
toString in class AbstractObjectList<int[]>protected long[] rebuildPointerArray()
Copyright © 2013. All Rights Reserved.