Class CharArrayFrontCodedBigList
- All Implemented Interfaces:
BigList<char[]>
,ObjectBigList<char[]>
,ObjectCollection<char[]>
,ObjectIterable<char[]>
,Size64
,Stack<char[]>
,Serializable
,Cloneable
,Comparable<BigList<? extends char[]>>
,Iterable<char[]>
,Collection<char[]>
,RandomAccess
This class stores immutably a big list of arrays in a single
big 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 (also known as prefix-omission) compression 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 of a front-coded list defines how often this happens (once every 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(long)
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.
Implementation Details
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
- See Also:
-
Nested Class Summary
Nested classes/interfaces inherited from class it.unimi.dsi.fastutil.objects.AbstractObjectBigList
AbstractObjectBigList.ObjectRandomAccessSubList<K>, AbstractObjectBigList.ObjectSubList<K>
-
Constructor Summary
ConstructorDescriptionCharArrayFrontCodedBigList
(Collection<char[]> c, int ratio) Creates a new front-coded list containing the arrays in the given collection.CharArrayFrontCodedBigList
(Iterator<char[]> arrays, int ratio) Creates a new front-coded list containing the arrays returned by the given iterator. -
Method Summary
Modifier and TypeMethodDescriptionint
arrayLength
(long index) Computes the length of the array at the given index.clone()
Returns a copy of this list.void
dump
(DataOutputStream array, DataOutputStream pointers) char[]
get
(long index) Returns the element at the specified position.int
get
(long index, char[] a) Stores in the given array an array stored in this front-coded list.int
get
(long index, char[] a, int offset, int length) Stores in the given array elements from an array stored in this front-coded list.char[]
getArray
(long index) Returns an array stored in this front-coded list.ObjectBigListIterator
<char[]> listIterator
(long start) Returns a type-specific list iterator on this type-specific big list starting at a given index.int
ratio()
long
size64()
Returns the size of this data structure as a long.toString()
Methods inherited from class it.unimi.dsi.fastutil.objects.AbstractObjectBigList
add, add, addAll, addAll, addElements, addElements, clear, compareTo, contains, equals, forEach, getElements, hashCode, indexOf, iterator, lastIndexOf, listIterator, peek, pop, push, remove, removeElements, set, setElements, size, size, subList, top
Methods inherited from class java.util.AbstractCollection
containsAll, isEmpty, remove, removeAll, retainAll, toArray, toArray
Methods inherited from interface java.util.Collection
containsAll, isEmpty, parallelStream, remove, removeAll, removeIf, retainAll, stream, toArray, toArray, toArray
Methods inherited from interface it.unimi.dsi.fastutil.objects.ObjectBigList
addAll, addAll, addAll, addAll, getElements, setElements, setElements, spliterator
-
Constructor Details
-
CharArrayFrontCodedBigList
Creates a new front-coded list containing the arrays returned by the given iterator.- Parameters:
arrays
- an iterator returning arrays.ratio
- the desired ratio.
-
CharArrayFrontCodedBigList
Creates a new front-coded list containing the arrays in the given collection.- Parameters:
c
- a collection containing arrays.ratio
- the desired ratio.
-
-
Method Details
-
ratio
public int ratio() -
arrayLength
public int arrayLength(long index) Computes the length of the array at the given index.- Parameters:
index
- an index.- Returns:
- the length of the
index
-th array.
-
get
public char[] get(long index) Returns the element at the specified position.- Specified by:
get
in interfaceBigList<char[]>
- Parameters:
index
- a position in the big list.- Returns:
- the element at the specified position.
- See Also:
- Implementation Specification:
- This implementation delegates to
getArray(long)
.
-
getArray
public char[] getArray(long index) Returns an array stored in this front-coded list.- Parameters:
index
- an index.- Returns:
- the corresponding array stored in this front-coded list.
-
get
public int get(long index, char[] a, int offset, int length) Stores in the given array elements from an array stored in this front-coded list.- Parameters:
index
- an index.a
- the array that will store the result.offset
- an offset intoa
where elements will be store.length
- a maximum number of elements to store ina
.- Returns:
- if
a
can hold the extracted elements, the number of extracted elements; otherwise, the number of remaining elements with the sign changed.
-
get
public int get(long index, char[] a) Stores in the given array an array stored in this front-coded list.- Parameters:
index
- an index.a
- the array that will store the content of the result (we assume that it can hold the result).- Returns:
- if
a
can hold the extracted elements, the number of extracted elements; otherwise, the number of remaining elements with the sign changed.
-
size64
public long size64()Description copied from interface:Size64
Returns the size of this data structure as a long. -
listIterator
Description copied from class:AbstractObjectBigList
Returns a type-specific list iterator on this type-specific big list starting at a given index.- Specified by:
listIterator
in interfaceBigList<char[]>
- Specified by:
listIterator
in interfaceObjectBigList<char[]>
- Overrides:
listIterator
in classAbstractObjectBigList<char[]>
- Parameters:
start
- index of first element to be returned from the big-list iterator.- Returns:
- a big-list iterator of the elements in this big list, starting at the specified position in this big list.
- See Also:
-
clone
Returns a copy of this list.- Returns:
- a copy of this list.
-
toString
- Overrides:
toString
in classAbstractObjectBigList<char[]>
-
dump
- Throws:
IOException
-