Class DistinctNumberList
- java.lang.Object
-
- cern.colt.PersistentObject
-
- cern.colt.list.AbstractCollection
-
- cern.colt.list.AbstractList
-
- cern.colt.list.AbstractLongList
-
- cern.colt.list.DistinctNumberList
-
- All Implemented Interfaces:
java.io.Serializable
,java.lang.Cloneable
public class DistinctNumberList extends AbstractLongList
Resizable compressed list holding numbers; based on the fact that a number from a large list with few distinct values need not take more than log(distinctValues) bits; implemented with a MinMaxNumberList. First see the package summary and javadoc tree view to get the broad picture.This class can, for example, be useful when making large lists of numbers persistent. Also useful when very large lists would otherwise consume too much main memory.
You can add, get and set elements quite similar to java.util.ArrayList.
Applicability: Applicable if data is highly skewed and legal values are known in advance. Robust in the presence of "outliers".
Performance: Operations get(), size() and clear() are O(1), i.e. run in constant time. Operations like add() and set() are O(log(distinctValues.length)).
Upon instantiation a contract is signed that defines the distinct values allowed to be hold in this list. It is not legal to store elements other than specified by the contract. Any attempt to violate the contract will throw an IllegalArgumentException.
Although access methods are only defined on long values you can also store all other primitive data types: boolean, byte, short, int, long, float, double and char. You can do this by explicitly representing them as long values. Use casts for discrete data types. Use the methods of java.lang.Float and java.lang.Double for floating point data types: Recall that with those methods you can convert any floating point value to a long value and back without losing any precision:
Example usage:
DistinctNumberList list = ... instantiation goes here double d1 = 1.234; list.add(Double.doubleToLongBits(d1)); double d2 = Double.longBitsToDouble(list.get(0)); if (d1!=d2) System.out.println("This is impossible!"); DistinctNumberList list2 = ... instantiation goes here float f1 = 1.234f; list2.add((long) Float.floatToIntBits(f1)); float f2 = Float.intBitsToFloat((int)list2.get(0)); if (f1!=f2) System.out.println("This is impossible!");
- Version:
- 1.0, 09/24/99
- See Also:
LongArrayList
,MinMaxNumberList
,Float
,Double
, Serialized Form
-
-
Field Summary
Fields Modifier and Type Field Description protected long[]
distinctValues
protected MinMaxNumberList
elements
-
Fields inherited from class cern.colt.list.AbstractLongList
size
-
Fields inherited from class cern.colt.PersistentObject
serialVersionUID
-
-
Constructor Summary
Constructors Constructor Description DistinctNumberList(long[] distinctValues, int initialCapacity)
Constructs an empty list with the specified initial capacity and the specified distinct values allowed to be hold in this list.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description void
add(long element)
Appends the specified element to the end of this list.protected int
codeOf(long element)
Returns the code that shall be stored for the given element.void
ensureCapacity(int minCapacity)
Ensures that the receiver can hold at least the specified number of elements without needing to allocate new internal memory.long
getQuick(int index)
Returns the element at the specified position in the receiver; WARNING: Does not check preconditions.void
removeFromTo(int from, int to)
Removes from the receiver all elements whose index is betweenfrom
, inclusive andto
, inclusive.void
setQuick(int index, long element)
Replaces the element at the specified position in the receiver with the specified element; WARNING: Does not check preconditions.protected void
setSizeRaw(int newSize)
Sets the size of the receiver without modifying it otherwise.protected void
setUp(long[] distinctValues, int initialCapacity)
Sets the receiver to an empty list with the specified initial capacity and the specified distinct values allowed to be hold in this list.void
trimToSize()
Trims the capacity of the receiver to be the receiver's current size.-
Methods inherited from class cern.colt.list.AbstractLongList
addAllOfFromTo, beforeInsert, beforeInsertAllOfFromTo, beforeInsertDummies, binarySearch, binarySearchFromTo, clone, contains, delete, elements, elements, equals, fillFromToWith, forEach, get, indexOf, indexOfFromTo, lastIndexOf, lastIndexOfFromTo, mergeSortFromTo, mergeSortFromTo, partFromTo, quickSortFromTo, quickSortFromTo, removeAll, replaceFromToWithFrom, replaceFromToWithFromTo, replaceFromWith, retainAll, reverse, set, shuffleFromTo, size, times, toList, toString
-
Methods inherited from class cern.colt.list.AbstractList
addAllOf, beforeInsertAllOf, checkRange, checkRangeFromTo, clear, mergeSort, quickSort, remove, setSize, shuffle, sort, sortFromTo
-
Methods inherited from class cern.colt.list.AbstractCollection
isEmpty
-
-
-
-
Field Detail
-
distinctValues
protected long[] distinctValues
-
elements
protected MinMaxNumberList elements
-
-
Constructor Detail
-
DistinctNumberList
public DistinctNumberList(long[] distinctValues, int initialCapacity)
Constructs an empty list with the specified initial capacity and the specified distinct values allowed to be hold in this list.- Parameters:
distinctValues
- an array sorted ascending containing the distinct values allowed to be hold in this list.initialCapacity
- the number of elements the receiver can hold without auto-expanding itself by allocating new internal memory.
-
-
Method Detail
-
add
public void add(long element)
Appends the specified element to the end of this list.- Overrides:
add
in classAbstractLongList
- Parameters:
element
- element to be appended to this list.
-
codeOf
protected int codeOf(long element)
Returns the code that shall be stored for the given element.
-
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.- Specified by:
ensureCapacity
in classAbstractLongList
- Parameters:
minCapacity
- the desired minimum capacity.
-
getQuick
public long getQuick(int index)
Returns the element at the specified position in the receiver; WARNING: Does not check preconditions. Provided with invalid parameters this method may return invalid elements without throwing any exception! You should only use this method when you are absolutely sure that the index is within bounds. Precondition (unchecked): index >= 0 && index < size().- Specified by:
getQuick
in classAbstractLongList
- Parameters:
index
- index of element to return.
-
removeFromTo
public void removeFromTo(int from, int to)
Removes from the receiver all elements whose index is betweenfrom
, inclusive andto
, inclusive. Shifts any succeeding elements to the left (reduces their index). This call shortens the list by (to - from + 1) elements.- Overrides:
removeFromTo
in classAbstractLongList
- Parameters:
from
- index of first element to be removed.to
- index of last element to be removed.- Throws:
java.lang.IndexOutOfBoundsException
- index is out of range (size()>0 && (from<0 || from>to || to>=size())).
-
setQuick
public void setQuick(int index, long element)
Replaces the element at the specified position in the receiver with the specified element; WARNING: Does not check preconditions. Provided with invalid parameters this method may access invalid indexes without throwing any exception! You should only use this method when you are absolutely sure that the index is within bounds. Precondition (unchecked): index >= 0 && index < size().- Specified by:
setQuick
in classAbstractLongList
- Parameters:
index
- index of element to replace.element
- element to be stored at the specified position.
-
setSizeRaw
protected void setSizeRaw(int newSize)
Sets the size of the receiver without modifying it otherwise. This method should not release or allocate new memory but simply set some instance variable like size.- Overrides:
setSizeRaw
in classAbstractLongList
-
setUp
protected void setUp(long[] distinctValues, int initialCapacity)
Sets the receiver to an empty list with the specified initial capacity and the specified distinct values allowed to be hold in this list.- Parameters:
distinctValues
- an array sorted ascending containing the distinct values allowed to be hold in this list.initialCapacity
- the number of elements the receiver can hold without auto-expanding itself by allocating new internal memory.
-
trimToSize
public void trimToSize()
Trims the capacity of the receiver to be the receiver's current size. An application can use this operation to minimize the storage of the receiver.- Overrides:
trimToSize
in classAbstractList
-
-