cern.colt.list
Class MinMaxNumberList

java.lang.Object
  extended by cern.colt.PersistentObject
      extended by cern.colt.list.AbstractCollection
          extended by cern.colt.list.AbstractList
              extended by cern.colt.list.AbstractLongList
                  extended by cern.colt.list.MinMaxNumberList
All Implemented Interfaces:
java.io.Serializable, java.lang.Cloneable

public class MinMaxNumberList
extends AbstractLongList

Resizable compressed list holding numbers; based on the fact that a value in a given interval need not take more than log(max-min+1) bits; implemented with a cern.colt.bitvector.BitVector. First see the package summary and javadoc tree view to get the broad picture.

Numbers can be compressed when minimum and maximum of all values ever to be stored in the list are known. For example, if min=16, max=27, only 4 bits are needed to store a value. No compression is achieved for float and double values.

You can add, get and set elements quite similar to java.util.ArrayList.

Applicability: Applicable if the data is non floating point, highly skewed without "outliers" and minimum and maximum known in advance.

Performance: Basic operations like add(), get(), set(), size() and clear() are O(1), i.e. run in constant time.

200Mhz Pentium Pro, JDK 1.2, NT:
10^6 calls to getQuick() --> 0.5 seconds. (50 times slower than reading from a primitive array of the appropriate type.)
10^6 calls to setQuick() --> 0.8 seconds. (15 times slower than writing to a primitive array of the appropriate type.)

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.

Upon instantiation a contract is signed that defines the interval values may fall into. It is not legal to store values not contained in that interval. WARNING: The contract is not checked. Be sure you do not store illegal values. If you need to store float or double values, you must set the minimum and maximum to [Integer.MIN_VALUE,Integer.MAX_VALUE] or [Long.MIN_VALUE,Long.MAX_VALUE], respectively.

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:

 MinMaxNumberList 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!");

 MinMaxNumberList 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!");
 

Author:
wolfgang.hoschek@cern.ch
See Also:
LongArrayList, DistinctNumberList, Float, Double, Serialized Form

Field Summary
protected  long[] bits
           
protected  int bitsPerElement
           
protected  int capacity
           
protected  long minValue
           
 
Fields inherited from class cern.colt.list.AbstractLongList
size
 
Fields inherited from class cern.colt.PersistentObject
serialVersionUID
 
Constructor Summary
MinMaxNumberList(long minimum, long maximum, int initialCapacity)
          Constructs an empty list with the specified initial capacity and the specified range of values allowed to be hold in this list.
 
Method Summary
 void add(long element)
          Appends the specified element to the end of this list.
 void addAllOfFromTo(long[] elements, int from, int to)
          Appends the elements elements[from] (inclusive), ..., elements[to] (inclusive) to the receiver.
 int bitsPerElement()
          Returns the number of bits necessary to store a single element.
static int bitsPerElement(long minimum, long maximum)
          Returns the number of bits necessary to store values in the range [minimum,maximum].
 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 partFromTo(int from, int to, BitVector qualificants, int qualificantsFrom, long[] part, int partFrom)
          Copies all elements between index from (inclusive) and to (inclusive) into part, starting at index partFrom within part.
 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 minimum, long maximum, int initialCapacity)
          Sets the receiver to an empty list with the specified initial capacity and the specified range of values allowed to be hold in this list.
protected  void setUpBitsPerEntry(long minimum, long maximum)
          This method was created in VisualAge.
 BitVector toBitVector()
          Returns the receiver seen as bitvector.
 void trimToSize()
          Trims the capacity of the receiver to be the receiver's current size.
 long xminimum()
          Deprecated.  
 
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, removeFromTo, 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
 
Methods inherited from class java.lang.Object
finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

minValue

protected long minValue

bitsPerElement

protected int bitsPerElement

bits

protected long[] bits

capacity

protected int capacity
Constructor Detail

MinMaxNumberList

public MinMaxNumberList(long minimum,
                        long maximum,
                        int initialCapacity)
Constructs an empty list with the specified initial capacity and the specified range of values allowed to be hold in this list. Legal values are in the range [minimum,maximum], all inclusive.

Parameters:
minimum - the minimum of values allowed to be hold in this list.
maximum - the maximum of 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 class AbstractLongList
Parameters:
element - element to be appended to this list.

addAllOfFromTo

public void addAllOfFromTo(long[] elements,
                           int from,
                           int to)
Appends the elements elements[from] (inclusive), ..., elements[to] (inclusive) to the receiver.

Parameters:
elements - the elements to be appended to the receiver.
from - the index of the first element to be appended (inclusive)
to - the index of the last element to be appended (inclusive)

bitsPerElement

public int bitsPerElement()
Returns the number of bits necessary to store a single element.


bitsPerElement

public static int bitsPerElement(long minimum,
                                 long maximum)
Returns the number of bits necessary to store values in the range [minimum,maximum].


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 class AbstractLongList
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 class AbstractLongList
Parameters:
index - index of element to return.

partFromTo

public void partFromTo(int from,
                       int to,
                       BitVector qualificants,
                       int qualificantsFrom,
                       long[] part,
                       int partFrom)
Copies all elements between index from (inclusive) and to (inclusive) into part, starting at index partFrom within part. Elements are only copied if a corresponding flag within qualificants is set. More precisely:
 for (; from<=to; from++, partFrom++, qualificantsFrom++) {
    if (qualificants==null || qualificants.get(qualificantsFrom)) {
       part[partFrom] = this.get(from);
    }
 }
 


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 class AbstractLongList
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 class AbstractLongList

setUp

protected void setUp(long minimum,
                     long maximum,
                     int initialCapacity)
Sets the receiver to an empty list with the specified initial capacity and the specified range of values allowed to be hold in this list. Legal values are in the range [minimum,maximum], all inclusive.

Parameters:
minimum - the minimum of values allowed to be hold in this list.
maximum - the maximum of 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.

setUpBitsPerEntry

protected void setUpBitsPerEntry(long minimum,
                                 long maximum)
This method was created in VisualAge.

Parameters:
minValue - long
maxValue - long
initialCapacity - int

toBitVector

public BitVector toBitVector()
Returns the receiver seen as bitvector. WARNING: The bitvector and the receiver share the backing bits. Modifying one of them will affect the other.


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 class AbstractList

xminimum

public long xminimum()
Deprecated. 

deprecated Returns the minimum element legal to the stored in the receiver. Remark: This does not mean that such a minimum element is currently contained in the receiver.