fr.univNantes.intcolls
Class BinaryIntSet

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

public class BinaryIntSet
extends java.util.AbstractSet<java.lang.Integer>
implements java.util.NavigableSet<java.lang.Integer>

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

Integers are stored in fixed sized blocks and blocks are indexed on their numbers by a DualArrayIntMap.

We have 4 constructors :

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

 for (BinaryIntSetIterator i = iterator(); i.hasNext(); ) {
     int n = i.nextInt();
 }
 

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 ConcurrentBinaryIntSet instead if you want a thread safe integer collection.

Author:
Pierre-Olivier Terrisse.
See Also:
ConcurrentBinaryIntSet

Field Summary
(package private)  int blockCapacity
          Block capacity in number of slots
(package private)  int blockMask
          Block mask
(package private)  java.util.NavigableMap<java.lang.Integer,Block> blocks
          Bocks 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
BinaryIntSet()
          Constructor of the set with default block capacity
BinaryIntSet(BinaryIntSet is)
          Contructor of the set with another collection of Integers
BinaryIntSet(java.util.Collection<java.lang.Integer> coll)
          Contructor of the set with another collection of Integers
BinaryIntSet(int blockCapacity)
          Constructor of the set
 
Method Summary
 boolean add(java.lang.Integer value)
          Adds an integer element to this collection
 boolean addAll(java.util.Collection<? extends java.lang.Integer> is)
          Adds all of the elements in the specified collection to this collection
 boolean addAll(int[] arr)
          Adds an array of integers.
 boolean addInt(int value)
          Adds an interger element to this collection
 java.lang.Integer ceiling(java.lang.Integer 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.Integer> 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 containsInt(int value)
          Returns true if this collection contains a certain value
 int countBetween(int fromValue, int toValue)
          Counts values between 2 given values
 int countHigher(int value)
          Counts values strictly higher than a given value
 int countLower(int value)
          Counts values strictly lower than a given value
 java.util.Iterator<java.lang.Integer> descendingIterator()
          Returns an iterator over the elements in this set, in descending order.
 java.util.NavigableSet<java.lang.Integer> 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.Integer first()
          Returns the first (lowest) element currently in this set.
 java.lang.Integer floor(java.lang.Integer 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(int bNum, BinaryIntSetIterator.Context context)
          Return a block using context and updates context if needed
 long getSlotValue(int blockNum, int slotNum)
          Low level method : returns a slot value
 int hashCode()
          Returns a hash code value for the set
(package private)  boolean hasHigher(int value, BinaryIntSetIterator.Context context)
          Returns true if the set has a higher value
(package private)  boolean hasLower(int value, BinaryIntSetIterator.Context context)
          Returns true if the set has a lower value
 java.util.SortedSet<java.lang.Integer> headSet(java.lang.Integer toElement)
          Returns a view of the portion of this set whose elements are strictly less than toElement.
 java.util.NavigableSet<java.lang.Integer> headSet(java.lang.Integer 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.Integer higher(java.lang.Integer e)
          Returns the least element in this set strictly greater than the given element, or null if there is no such element.
(package private)  int higherInt(int e, BinaryIntSetIterator.Context context)
          Returns the least element in this set strictly greater than the given element
 BinaryIntSetIterator iterator()
          Returns an iterator on the IntSet
 java.lang.Integer last()
          Returns the last (hightest) element currently in this set.
 java.lang.Integer lower(java.lang.Integer e)
          Returns the greatest element in this set strictly less than the given element, or null if there is no such element.
(package private)  int lowerInt(int e, BinaryIntSetIterator.Context context)
          Returns the greatest element in this set strictly less than the given element
 java.lang.Integer pollFirst()
          Retrieves and removes the first (lowest) element, or returns null if this set is empty.
 java.lang.Integer 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(int[] arr)
          Removes an array of integers.
 boolean removeInt(int 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(int[] arr)
          Retains only the elements in this collection that are contained in the specified array of integers.
 void setSlotValue(int 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.Integer> subSet(java.lang.Integer fromElement, boolean fromInclusive, java.lang.Integer toElement, boolean toInclusive)
          Returns a view of the portion of this set whose elements range from fromElement to toElement
 java.util.SortedSet<java.lang.Integer> subSet(java.lang.Integer fromElement, java.lang.Integer 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.Integer> tailSet(java.lang.Integer fromElement)
          Returns a view of the portion of this set whose elements are greater than or equal to fromElement.
 java.util.NavigableSet<java.lang.Integer> tailSet(java.lang.Integer 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 int blockMask
Block mask


blocks

java.util.NavigableMap<java.lang.Integer,Block> blocks
Bocks of this set


blockShift

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

Constructor Detail

BinaryIntSet

public BinaryIntSet(int blockCapacity)
Constructor of the set

Parameters:
blockCapacity - capacity of blocks in number of slots. Must be a power of 2.
Throws:
java.lang.IllegalArgumentException - if blockCapacity is not positive and power of 2.

BinaryIntSet

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


BinaryIntSet

public BinaryIntSet(java.util.Collection<java.lang.Integer> coll)
Contructor of the set with another collection of Integers

Parameters:
coll - another collection of Intergers

BinaryIntSet

public BinaryIntSet(BinaryIntSet is)
Contructor of the set with another collection of Integers

Parameters:
is - another collection of Intergers
Method Detail

addInt

public boolean addInt(int value)
Adds an interger element to this collection

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

add

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

Specified by:
add in interface java.util.Collection<java.lang.Integer>
Specified by:
add in interface java.util.Set<java.lang.Integer>
Overrides:
add in class java.util.AbstractCollection<java.lang.Integer>
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.Integer>
Specified by:
remove in interface java.util.Set<java.lang.Integer>
Overrides:
remove in class java.util.AbstractCollection<java.lang.Integer>
Parameters:
value - element to remove
Returns:
true if the collection was modified

removeInt

public boolean removeInt(int 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.Integer> is)
Adds all of the elements in the specified collection to this collection

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

addAll

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

Parameters:
arr - array if integer
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.Integer>
Specified by:
removeAll in interface java.util.Set<java.lang.Integer>
Overrides:
removeAll in class java.util.AbstractSet<java.lang.Integer>
Parameters:
is - another IntCollection
Returns:
true if this integer set changed after the operation

removeAll

public boolean removeAll(int[] 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.Integer>
Specified by:
retainAll in interface java.util.Set<java.lang.Integer>
Overrides:
retainAll in class java.util.AbstractCollection<java.lang.Integer>
Parameters:
is1 - another collection
Returns:
true if this collection changed

retainAll

public boolean retainAll(int[] 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.Integer>
Specified by:
size in interface java.util.Set<java.lang.Integer>
Specified by:
size in class java.util.AbstractCollection<java.lang.Integer>
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.Integer>
Specified by:
contains in interface java.util.Set<java.lang.Integer>
Overrides:
contains in class java.util.AbstractCollection<java.lang.Integer>
Parameters:
value - value to search in this collection
Returns:
true if this collection contains the value

containsInt

public boolean containsInt(int 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.Integer>
Specified by:
clear in interface java.util.Set<java.lang.Integer>
Overrides:
clear in class java.util.AbstractCollection<java.lang.Integer>

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.Integer>
Specified by:
equals in interface java.util.Set<java.lang.Integer>
Overrides:
equals in class java.util.AbstractSet<java.lang.Integer>
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.Integer>
Specified by:
hashCode in interface java.util.Set<java.lang.Integer>
Overrides:
hashCode in class java.util.AbstractSet<java.lang.Integer>
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.Integer first()
Returns the first (lowest) element currently in this set.

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

last

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

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

iterator

public BinaryIntSetIterator iterator()
Returns an iterator on the IntSet

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

getBlockWithContext

Block getBlockWithContext(int bNum,
                          BinaryIntSetIterator.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.Integer higher(java.lang.Integer 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.Integer>
Parameters:
e - an element
Returns:
the least element greater than e, or null if there is no such element

higherInt

int higherInt(int e,
              BinaryIntSetIterator.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 Integer.MIN_VALUE if not such element

hasHigher

boolean hasHigher(int value,
                  BinaryIntSetIterator.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.Integer ceiling(java.lang.Integer 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.Integer>

lower

public java.lang.Integer lower(java.lang.Integer 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.Integer>
Returns:
the greatest element less than e, or null if there is no such element

lowerInt

int lowerInt(int e,
             BinaryIntSetIterator.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 Integer.MAX_VALUE if not such element

hasLower

boolean hasLower(int value,
                 BinaryIntSetIterator.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.Integer floor(java.lang.Integer 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.Integer>
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.Integer> comparator()
Returns a comparator for the elements of this Set

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

subSet

public java.util.SortedSet<java.lang.Integer> subSet(java.lang.Integer fromElement,
                                                     java.lang.Integer 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.Integer>
Specified by:
subSet in interface java.util.SortedSet<java.lang.Integer>
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.Integer> headSet(java.lang.Integer 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.Integer>
Specified by:
headSet in interface java.util.SortedSet<java.lang.Integer>
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.Integer> tailSet(java.lang.Integer 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.Integer>
Specified by:
tailSet in interface java.util.SortedSet<java.lang.Integer>
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.Integer 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.Integer>
Returns:
the first element, or null if this set is empty

pollLast

public java.lang.Integer 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.Integer>
Returns:
the last element, or null if this set is empty

descendingSet

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

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

descendingIterator

public java.util.Iterator<java.lang.Integer> 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.Integer>
Returns:
an iterator over the elements in this set, in descending order

subSet

public java.util.NavigableSet<java.lang.Integer> subSet(java.lang.Integer fromElement,
                                                        boolean fromInclusive,
                                                        java.lang.Integer 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.Integer>
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.Integer> headSet(java.lang.Integer 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.Integer>
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.Integer> tailSet(java.lang.Integer 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.Integer>
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 int countLower(int value)
Counts values strictly lower than a given value

Parameters:
value - a value

countHigher

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

Parameters:
value - a value

countBetween

public int countBetween(int fromValue,
                        int 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(int blockNum,
                         int slotNum)
Low level method : returns a slot value

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

setSlotValue

public void setSlotValue(int 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