fr.univNantes.intcolls
Class BinaryLongSet

java.lang.Object
  extended by java.util.AbstractCollection<E>
      extended by java.util.AbstractSet<java.lang.Long>
          extended by fr.univNantes.intcolls.BinaryLongSet
All Implemented Interfaces:
java.lang.Iterable<java.lang.Long>, java.util.Collection<java.lang.Long>, java.util.NavigableSet<java.lang.Long>, java.util.Set<java.lang.Long>, java.util.SortedSet<java.lang.Long>
Direct Known Subclasses:
ConcurrentBinaryLongSet

public class BinaryLongSet
extends java.util.AbstractSet<java.lang.Long>
implements java.util.NavigableSet<java.lang.Long>

This class implements a NavigableSet on a faster manner than HashSet or TreeSet do.

Longs are stored in fixed sized blocks and blocks are indexed on their numbers by a DualArrayLongMap.

We have 4 constructors :

You can use this class in two ways : You can simply replace your instanciations of HashSet or TreeSet by BinaryLongSet. The performance of your code will be improved because HashSet and TreeSet use to store Longs objects rather than the primitive int type. To improve more the performances, you can also replace calls of add(Long) by addLong(long), and iterator use by :

 for (BinaryLongSetIterator i = iterator(); i.hasNext(); ) {
     int n = i.nextLong();
 }
 

size() method is a constant-time operation, as this class always knows its size. This method does not need elements traversal.

Warning : this collection is not thread safe ! Use ConcurrentBinaryLongSet instead if you want a thread safe integer collection.

Author:
Pierre-Olivier Terrisse.
See Also:
ConcurrentBinaryLongSet

Field Summary
(package private)  int blockCapacity
          Block capacity in number of slots
(package private)  long blockMask
          Block mask
(package private)  java.util.NavigableMap<java.lang.Long,Block> blocks
          Blocks of this set
(package private)  int blockShift
          Number of bits to shift the element to obtain the block number
(package private) static int DEFAULT_BLOCK_CAPACITY
          Default block capacity in number of slots
private  int size
          Size of the set (number of elements)
 
Constructor Summary
BinaryLongSet()
          Constructor of the set with default block capacity
BinaryLongSet(BinaryLongSet is)
          Contructor of the set with another collection of Longs
BinaryLongSet(java.util.Collection<java.lang.Long> coll)
          Contructor of the set with another collection of Longs
BinaryLongSet(int blockCapacity)
          Constructor of the set
 
Method Summary
 boolean add(java.lang.Long value)
          Adds an integer element to this collection
 boolean addAll(java.util.Collection<? extends java.lang.Long> is)
          Adds all of the elements in the specified collection to this collection
 boolean addAll(long[] arr)
          Adds an array of integers.
 boolean addLong(long value)
          Adds a long integer element to this collection
 java.lang.Long ceiling(java.lang.Long e)
          Returns the least element in this set greater than or equal to the given element, or null if there is no such element.
 void clear()
          Removes all the values from the set
 java.util.Comparator<? super java.lang.Long> comparator()
          Returns a comparator for the elements of this Set
 boolean contains(java.lang.Object value)
          Returns true if this collection contains a certain value
 boolean containsLong(long value)
          Returns true if this collection contains a certain value
 long countBetween(long fromValue, long toValue)
          Counts values between 2 given values
 long countHigher(long value)
          Counts values strictly higher than a given value
 long countLower(long value)
          Counts values strictly lower than a given value
 java.util.Iterator<java.lang.Long> descendingIterator()
          Returns an iterator over the elements in this set, in descending order.
 java.util.NavigableSet<java.lang.Long> descendingSet()
          Returns a reverse order view of the elements contained in this set.
 boolean equals(java.lang.Object obj)
          Indicates whether some other object is "equal to" this one.
 java.lang.Long first()
          Returns the first (lowest) element currently in this set.
 java.lang.Long floor(java.lang.Long e)
          Returns the greatest element in this set less than or equal to the given element, or null if there is no such element.
 void fromBooleanArray(boolean[] tab)
          Set values of the set with true indices of a boolean array.
(package private)  Block getBlockWithContext(long bNum, BinaryLongSetIterator.Context context)
          Return a block using context and updates context if needed
 long getSlotValue(long blockNum, int slotNum)
          Low level method : returns a slot value
 int hashCode()
          Returns a hash code value for the set
(package private)  boolean hasHigher(long value, BinaryLongSetIterator.Context context)
          Returns true if the set has a higher value
(package private)  boolean hasLower(long value, BinaryLongSetIterator.Context context)
          Returns true if the set has a lower value
 java.util.SortedSet<java.lang.Long> headSet(java.lang.Long toElement)
          Returns a view of the portion of this set whose elements are strictly less than toElement.
 java.util.NavigableSet<java.lang.Long> headSet(java.lang.Long toElement, boolean inclusive)
          Returns a view of the portion of this set whose elements are less than (or equal to, if inclusive is true) toElement.
 java.lang.Long higher(java.lang.Long e)
          Returns the least element in this set strictly greater than the given element, or null if there is no such element.
(package private)  long higherLong(long e, BinaryLongSetIterator.Context context)
          Returns the least element in this set strictly greater than the given element
 BinaryLongSetIterator iterator()
          Returns an iterator on the long set
 java.lang.Long last()
          Returns the last (hightest) element currently in this set.
 java.lang.Long lower(java.lang.Long e)
          Returns the greatest element in this set strictly less than the given element, or null if there is no such element.
(package private)  long lowerLong(long e, BinaryLongSetIterator.Context context)
          Returns the greatest element in this set strictly less than the given element
 java.lang.Long pollFirst()
          Retrieves and removes the first (lowest) element, or returns null if this set is empty.
 java.lang.Long pollLast()
          Retrieves and removes the last (highest) element, or returns null if this set is empty.
 boolean remove(java.lang.Object value)
          Removes an element from the collection
 boolean removeAll(java.util.Collection<?> is)
          Removes all of the elements in the specified collection to this collection
 boolean removeAll(long[] arr)
          Removes an array of integers.
 boolean removeLong(long value)
          Removes an element from the collection
 boolean retainAll(java.util.Collection<?> is1)
          Retains only the elements in this collection that are contained in the specified collection
 boolean retainAll(long[] arr)
          Retains only the elements in this collection that are contained in the specified array of integers.
 void setSlotValue(long blockNum, int slotNum, long slotVal)
          Low level method : sets a slot value.
 int size()
          Returns the number of elements contained in the collection
 java.util.NavigableSet<java.lang.Long> subSet(java.lang.Long fromElement, boolean fromInclusive, java.lang.Long toElement, boolean toInclusive)
          Returns a view of the portion of this set whose elements range from fromElement to toElement
 java.util.SortedSet<java.lang.Long> subSet(java.lang.Long fromElement, java.lang.Long toElement)
          Returns a view of the portion of this sorted set whose elements range from fromElement, inclusive, to toElement, exclusive.
 int sum()
          Returns the sum of all elements
 java.util.SortedSet<java.lang.Long> tailSet(java.lang.Long fromElement)
          Returns a view of the portion of this set whose elements are greater than or equal to fromElement.
 java.util.NavigableSet<java.lang.Long> tailSet(java.lang.Long fromElement, boolean inclusive)
          Returns a view of the portion of this set whose elements are greater than (or equal to, if inclusive is true) fromElement.
 boolean[] toBooleanArray(int arraySize)
          Returns a boolean array mapped with this set.
 
Methods inherited from class java.util.AbstractCollection
containsAll, isEmpty, toArray, toArray, toString
 
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface java.util.Set
containsAll, isEmpty, toArray, toArray
 

Field Detail

size

private int size
Size of the set (number of elements)


DEFAULT_BLOCK_CAPACITY

static final int DEFAULT_BLOCK_CAPACITY
Default block capacity in number of slots

See Also:
Constant Field Values

blockCapacity

final int blockCapacity
Block capacity in number of slots


blockMask

final long blockMask
Block mask


blocks

java.util.NavigableMap<java.lang.Long,Block> blocks
Blocks of this set


blockShift

final int blockShift
Number of bits to shift the element to obtain the block number

Constructor Detail

BinaryLongSet

public BinaryLongSet(int blockCapacity)
Constructor of the set

Parameters:
blockCapacity - capacity of blocks in number of slots. Must be a power of 2.

BinaryLongSet

public BinaryLongSet()
Constructor of the set with default block capacity


BinaryLongSet

public BinaryLongSet(java.util.Collection<java.lang.Long> coll)
Contructor of the set with another collection of Longs

Parameters:
coll - another collection of longs

BinaryLongSet

public BinaryLongSet(BinaryLongSet is)
Contructor of the set with another collection of Longs

Parameters:
is - another collection of long integers
Method Detail

addLong

public boolean addLong(long value)
Adds a long integer element to this collection

Parameters:
value - value to add
Returns:
true if the collection was modified

add

public boolean add(java.lang.Long value)
Adds an integer element to this collection

Specified by:
add in interface java.util.Collection<java.lang.Long>
Specified by:
add in interface java.util.Set<java.lang.Long>
Overrides:
add in class java.util.AbstractCollection<java.lang.Long>
Parameters:
value - value to add
Returns:
true if the collection was modified

remove

public boolean remove(java.lang.Object value)
Removes an element from the collection

Specified by:
remove in interface java.util.Collection<java.lang.Long>
Specified by:
remove in interface java.util.Set<java.lang.Long>
Overrides:
remove in class java.util.AbstractCollection<java.lang.Long>
Parameters:
value - element to remove
Returns:
true if the collection was modified

removeLong

public boolean removeLong(long value)
Removes an element from the collection

Parameters:
value - element to remove
Returns:
true if the collection was modified

addAll

public boolean addAll(java.util.Collection<? extends java.lang.Long> is)
Adds all of the elements in the specified collection to this collection

Specified by:
addAll in interface java.util.Collection<java.lang.Long>
Specified by:
addAll in interface java.util.Set<java.lang.Long>
Overrides:
addAll in class java.util.AbstractCollection<java.lang.Long>
Parameters:
is - another long collection
Returns:
true if this integer set changed after the operation

addAll

public boolean addAll(long[] arr)
Adds an array of integers. Equivalent to addAll(Arrays.asList(arr)) but faster.

Parameters:
arr - array of long integers
Returns:
true if this integer set changed after the operation

removeAll

public boolean removeAll(java.util.Collection<?> is)
Removes all of the elements in the specified collection to this collection

Specified by:
removeAll in interface java.util.Collection<java.lang.Long>
Specified by:
removeAll in interface java.util.Set<java.lang.Long>
Overrides:
removeAll in class java.util.AbstractSet<java.lang.Long>
Parameters:
is - another long collection
Returns:
true if this integer set changed after the operation

removeAll

public boolean removeAll(long[] arr)
Removes an array of integers. Equivalent to removeAll(Arrays.asList(arr)) but faster.

Parameters:
arr - array if integer
Returns:
true if this integer set changed after the operation

retainAll

public boolean retainAll(java.util.Collection<?> is1)
Retains only the elements in this collection that are contained in the specified collection

Specified by:
retainAll in interface java.util.Collection<java.lang.Long>
Specified by:
retainAll in interface java.util.Set<java.lang.Long>
Overrides:
retainAll in class java.util.AbstractCollection<java.lang.Long>
Parameters:
is1 - another collection
Returns:
true if this collection changed

retainAll

public boolean retainAll(long[] arr)
Retains only the elements in this collection that are contained in the specified array of integers. Equivalent to retainAll(Arrays.asList(arr)) but faster ?.

Parameters:
arr - array if integer
Returns:
true if this integer set changed after the operation

size

public int size()
Returns the number of elements contained in the collection

Specified by:
size in interface java.util.Collection<java.lang.Long>
Specified by:
size in interface java.util.Set<java.lang.Long>
Specified by:
size in class java.util.AbstractCollection<java.lang.Long>
Returns:
the size of the collection

contains

public boolean contains(java.lang.Object value)
Returns true if this collection contains a certain value

Specified by:
contains in interface java.util.Collection<java.lang.Long>
Specified by:
contains in interface java.util.Set<java.lang.Long>
Overrides:
contains in class java.util.AbstractCollection<java.lang.Long>
Parameters:
value - value to search in this collection
Returns:
true if this collection contains the value

containsLong

public boolean containsLong(long value)
Returns true if this collection contains a certain value

Parameters:
value - value to search in this collection
Returns:
true if this collection contains the value

clear

public void clear()
Removes all the values from the set

Specified by:
clear in interface java.util.Collection<java.lang.Long>
Specified by:
clear in interface java.util.Set<java.lang.Long>
Overrides:
clear in class java.util.AbstractCollection<java.lang.Long>

equals

public boolean equals(java.lang.Object obj)
Indicates whether some other object is "equal to" this one.

Specified by:
equals in interface java.util.Collection<java.lang.Long>
Specified by:
equals in interface java.util.Set<java.lang.Long>
Overrides:
equals in class java.util.AbstractSet<java.lang.Long>
Parameters:
obj - the reference object with which to compare.
Returns:
true if this object is the same as the obj argument; false otherwise.

hashCode

public int hashCode()
Returns a hash code value for the set

Specified by:
hashCode in interface java.util.Collection<java.lang.Long>
Specified by:
hashCode in interface java.util.Set<java.lang.Long>
Overrides:
hashCode in class java.util.AbstractSet<java.lang.Long>
Returns:
an integer value that must be consistant with equals()

sum

public int sum()
Returns the sum of all elements

Returns:
the sum

first

public java.lang.Long first()
Returns the first (lowest) element currently in this set.

Specified by:
first in interface java.util.SortedSet<java.lang.Long>
Returns:
the first (lowest) element currently in this set
Throws:
java.util.NoSuchElementException - - if this set is empty

last

public java.lang.Long last()
Returns the last (hightest) element currently in this set.

Specified by:
last in interface java.util.SortedSet<java.lang.Long>
Returns:
the last (hightest) element currently in this set
Throws:
java.util.NoSuchElementException - - if this set is empty

iterator

public BinaryLongSetIterator iterator()
Returns an iterator on the long set

Specified by:
iterator in interface java.lang.Iterable<java.lang.Long>
Specified by:
iterator in interface java.util.Collection<java.lang.Long>
Specified by:
iterator in interface java.util.NavigableSet<java.lang.Long>
Specified by:
iterator in interface java.util.Set<java.lang.Long>
Specified by:
iterator in class java.util.AbstractCollection<java.lang.Long>
Returns:
iterator

getBlockWithContext

Block getBlockWithContext(long bNum,
                          BinaryLongSetIterator.Context context)
Return a block using context and updates context if needed

Parameters:
bNum - block number
context - iterator's context if any, null otherwise
Returns:
block number bNum of null if no block at bNum

higher

public java.lang.Long higher(java.lang.Long e)
Returns the least element in this set strictly greater than the given element, or null if there is no such element.

Specified by:
higher in interface java.util.NavigableSet<java.lang.Long>
Parameters:
e - an element
Returns:
the least element greater than e, or null if there is no such element

higherLong

long higherLong(long e,
                BinaryLongSetIterator.Context context)
Returns the least element in this set strictly greater than the given element

Parameters:
e - an element
context - iterator's context if any, null otherwise
Returns:
the least element greater than e or Long.MIN_VALUE if not such element

hasHigher

boolean hasHigher(long value,
                  BinaryLongSetIterator.Context context)
Returns true if the set has a higher value

Parameters:
value - a value
context - iterator's context if any, null otherwise
Returns:
true if the set contains a higher value

ceiling

public java.lang.Long ceiling(java.lang.Long e)
Returns the least element in this set greater than or equal to the given element, or null if there is no such element. the least element greater than or equal to e, or -1 if there is no such element

Specified by:
ceiling in interface java.util.NavigableSet<java.lang.Long>

lower

public java.lang.Long lower(java.lang.Long e)
Returns the greatest element in this set strictly less than the given element, or null if there is no such element.

Specified by:
lower in interface java.util.NavigableSet<java.lang.Long>
Returns:
the greatest element less than e, or null if there is no such element

lowerLong

long lowerLong(long e,
               BinaryLongSetIterator.Context context)
Returns the greatest element in this set strictly less than the given element

Parameters:
e - an element
context - iterator's context if any, null otherwise
Returns:
the greatest element less than e or Long.MAX_VALUE if not such element

hasLower

boolean hasLower(long value,
                 BinaryLongSetIterator.Context context)
Returns true if the set has a lower value

Parameters:
value - a value
context - iterator's context if any, null otherwise
Returns:
true if the set contains a lower value

floor

public java.lang.Long floor(java.lang.Long e)
Returns the greatest element in this set less than or equal to the given element, or null if there is no such element.

Specified by:
floor in interface java.util.NavigableSet<java.lang.Long>
Returns:
the greatest element less than or equal to e, or -1 if there is no such element

comparator

public java.util.Comparator<? super java.lang.Long> comparator()
Returns a comparator for the elements of this Set

Specified by:
comparator in interface java.util.SortedSet<java.lang.Long>
Returns:
null because this SortedSet uses natural ordering

subSet

public java.util.SortedSet<java.lang.Long> subSet(java.lang.Long fromElement,
                                                  java.lang.Long toElement)
Returns a view of the portion of this sorted set whose elements range from fromElement, inclusive, to toElement, exclusive.

Specified by:
subSet in interface java.util.NavigableSet<java.lang.Long>
Specified by:
subSet in interface java.util.SortedSet<java.lang.Long>
Parameters:
fromElement - low endpoint (inclusive) of the subSet.
toElement - high endpoint (exclusive) of the subSet
Returns:
a view of the specified range within this sorted set.

headSet

public java.util.SortedSet<java.lang.Long> headSet(java.lang.Long toElement)
Returns a view of the portion of this set whose elements are strictly less than toElement.

Specified by:
headSet in interface java.util.NavigableSet<java.lang.Long>
Specified by:
headSet in interface java.util.SortedSet<java.lang.Long>
Parameters:
toElement - high endpoint (exclusive) of the returned set
Returns:
a view of the portion of this set whose elements are strictly less than toElement

tailSet

public java.util.SortedSet<java.lang.Long> tailSet(java.lang.Long fromElement)
Returns a view of the portion of this set whose elements are greater than or equal to fromElement.

Specified by:
tailSet in interface java.util.NavigableSet<java.lang.Long>
Specified by:
tailSet in interface java.util.SortedSet<java.lang.Long>
Parameters:
fromElement - low endpoint (inclusive) of the returned set
Returns:
a view of the portion of this set whose elements are greater than or equal to fromElement

pollFirst

public java.lang.Long pollFirst()
Retrieves and removes the first (lowest) element, or returns null if this set is empty.

Specified by:
pollFirst in interface java.util.NavigableSet<java.lang.Long>
Returns:
the first element, or null if this set is empty

pollLast

public java.lang.Long pollLast()
Retrieves and removes the last (highest) element, or returns null if this set is empty.

Specified by:
pollLast in interface java.util.NavigableSet<java.lang.Long>
Returns:
the last element, or null if this set is empty

descendingSet

public java.util.NavigableSet<java.lang.Long> descendingSet()
Returns a reverse order view of the elements contained in this set.

Specified by:
descendingSet in interface java.util.NavigableSet<java.lang.Long>
Returns:
a reverse order view of this set

descendingIterator

public java.util.Iterator<java.lang.Long> descendingIterator()
Returns an iterator over the elements in this set, in descending order. Equivalent in effect to descendingSet().iterator().

Specified by:
descendingIterator in interface java.util.NavigableSet<java.lang.Long>
Returns:
an iterator over the elements in this set, in descending order

subSet

public java.util.NavigableSet<java.lang.Long> subSet(java.lang.Long fromElement,
                                                     boolean fromInclusive,
                                                     java.lang.Long toElement,
                                                     boolean toInclusive)
Returns a view of the portion of this set whose elements range from fromElement to toElement

Specified by:
subSet in interface java.util.NavigableSet<java.lang.Long>
Parameters:
fromElement - low endpoint of the returned set
fromInclusive - true if the low endpoint is to be included in the returned view
toElement - high endpoint of the returned set
toInclusive - true if the high endpoint is to be included in the returned view
Returns:
a view of the portion of this set whose elements range from fromElement to toElement

headSet

public java.util.NavigableSet<java.lang.Long> headSet(java.lang.Long toElement,
                                                      boolean inclusive)
Returns a view of the portion of this set whose elements are less than (or equal to, if inclusive is true) toElement. The returned set is backed by this set, so changes in the returned set are reflected in this set, and vice-versa. The returned set supports all optional set operations that this set supports.

Specified by:
headSet in interface java.util.NavigableSet<java.lang.Long>
Parameters:
toElement - high endpoint of the returned set
inclusive - true if the high endpoint is to be included in the returned view
Returns:
a view of the portion of this set whose elements are less than (or equal to, if inclusive is true) toElement

tailSet

public java.util.NavigableSet<java.lang.Long> tailSet(java.lang.Long fromElement,
                                                      boolean inclusive)
Returns a view of the portion of this set whose elements are greater than (or equal to, if inclusive is true) fromElement. The returned set is backed by this set, so changes in the returned set are reflected in this set, and vice-versa. The returned set supports all optional set operations that this set supports.

Specified by:
tailSet in interface java.util.NavigableSet<java.lang.Long>
Parameters:
fromElement - low endpoint of the returned set
inclusive - true if the low endpoint is to be included in the returned view
Returns:
a view of the portion of this set whose elements are greater than or equal to fromElement

countLower

public long countLower(long value)
Counts values strictly lower than a given value

Parameters:
value - a value

countHigher

public long countHigher(long value)
Counts values strictly higher than a given value

Parameters:
value - a value

countBetween

public long countBetween(long fromValue,
                         long toValue)
Counts values between 2 given values

Parameters:
fromValue - first value, including
toValue - second value, not including
Returns:
number of values between fromValue and toValue

toBooleanArray

public boolean[] toBooleanArray(int arraySize)
Returns a boolean array mapped with this set.
Let tab be the returned array. For each integer i contained in the set, tab[i] = true. For each integer i not contained in the set, tab[i] = false.

Parameters:
arraySize - minimum size of the array, or -1 to let the method automatically determine the array size.
Returns:
an array of booleans

fromBooleanArray

public void fromBooleanArray(boolean[] tab)
Set values of the set with true indices of a boolean array. This a a reverse method of toBooleanArray()

Parameters:
tab - boolean array

getSlotValue

public long getSlotValue(long blockNum,
                         int slotNum)
Low level method : returns a slot value

Parameters:
blockNum - block number
slotNum - slot number
Returns:
slot value

setSlotValue

public void setSlotValue(long blockNum,
                         int slotNum,
                         long slotVal)
Low level method : sets a slot value. Possibly a new block is created.

Parameters:
blockNum - block number
slotNum - slot number
slotVal - slot value