edu.emory.mathcs.util.collections.longs
Class LongIntervalSet

java.lang.Object
  extended byedu.emory.mathcs.util.collections.longs.AbstractLongCollection
      extended byedu.emory.mathcs.util.collections.longs.AbstractLongSet
          extended byedu.emory.mathcs.util.collections.longs.AbstractLongSortedSet
              extended byedu.emory.mathcs.util.collections.longs.LongIntervalSet
All Implemented Interfaces:
LongCollection, LongSet, LongSortedSet, java.io.Serializable

public class LongIntervalSet
extends AbstractLongSortedSet
implements java.io.Serializable

Set of long numbers that is optimized towards clustered distributions. The implementation keeps the atomic information about intervals of numbers, hence this set can hold billions of elements as long as they form clusters (long consecutive runs). The main application of this class is in collision detection arrays, e.g. to aid in generation of unique IDs that are roughly sequential but possibly cyclic (process IDs, packet IDs) with ID recycling and gap filling.

Caution: descending iterators aren't particularly well tested.

Author:
Dawid Kurzyniec
See Also:
Serialized Form

Nested Class Summary
 
Nested classes inherited from class edu.emory.mathcs.util.collections.longs.AbstractLongSortedSet
AbstractLongSortedSet.AbstractComplementSubView, AbstractLongSortedSet.AbstractSubView, AbstractLongSortedSet.ForwardIntervalItemIterator, AbstractLongSortedSet.ReverseIntervalItemIterator
 
Constructor Summary
LongIntervalSet()
          Creates a new set of longs.
LongIntervalSet(LongCollection c)
           
LongIntervalSet(long min, long max)
           
LongIntervalSet(LongSet c)
           
 
Method Summary
 boolean add(long n)
          Adds an element to the set if it is not already present.
 boolean addAll(LongCollection c)
          Adds all of the elements in the specified collection to this set if they're not already present, and if they fall within this set's domain.
 boolean addInterval(long first, long last)
          Adds to this set all the numbers between first and last, inclusive, that are not already present in this set and belong to this set's domain.
 long ceiling(long n)
          Returns the smallest number in this set >= e.
 LongInterval ceilingInterval(long n)
          Returns the smallest (left-most), widest interval contained in this set which elements are not all smaller than the specified number.
 void clear()
          Removes all elements from the set.
 LongSet complementSet()
          Returns a complement view of this set.
 boolean contains(long n)
          Checks whether the set contains a given element
 boolean containsInterval(long first, long last)
          Returns true if this set contains all the numbers between first and last, inclusive; false otherwise.
 java.util.Iterator descendingIntervalIterator()
          Returns an iterator over intervals of this set, in a decreasing numerical order.
 LongIterator descendingIterator()
          Returns an iterator over numbers in this set, in a decreasing numerical order.
 LongInterval enclosingInterval(long e)
          Returns the widest interval contained in this set that includes the specified number, or null if this set does not include the specified number.
 long first()
          Returns the smallest number in this set.
 LongInterval firstInterval()
          Returns the first (left-most), widest interval contained in this set, or null if this set is empty.
 long floor(long n)
          Returns the largest number in this set <= e.
 LongInterval floorInterval(long n)
          Returns the largest (right-most), widest interval contained in this set which elements are not all greater than the specified number.
 long higher(long n)
          Returns the smallest number in this set > e.
 LongInterval higherInterval(long n)
          Returns the smallest (left-most), widest interval contained in this set which all elements are strictly greater than the specified number.
 int intervalCount()
          Returns the minimum count of intervals into which this set can be decomposed.
 java.util.Iterator intervalIterator()
          Returns an iterator over intervals of this set, in an increasing numerical order.
 boolean isEmpty()
          Returns true if this set is empty; false otherwise.
 LongIterator iterator()
          Returns an iterator over numbers in this set, in an increasing numerical order.
 long last()
          Returns the largest number in this set.
 LongInterval lastInterval()
          Returns the last (right-most), widest interval contained in this set, or null if this set is empty.
 long lower(long n)
          Returns the largest number in this set < e.
 LongInterval lowerInterval(long n)
          Returns the largest and widest interval contained in this set which all elements are strictly less than the specified number.
 long max()
          The largest number that can be stored in this set.
 long min()
          The smallest number that can be stored in this set.
 long pollFirst()
          Returns and removes the smallest number in this set.
 LongInterval pollFirstInterval()
          Returns and removes the first (left-most), widest interval contained in this set, or null if this set is empty.
 long pollLast()
          Returns and removes the largest number in this set.
 LongInterval pollLastInterval()
          Returns and removes the last (right-most), widest interval contained in this set, or null if this set is empty.
 boolean remove(long n)
          Removes the specified number from this set if it is present.
 boolean removeAll(LongCollection c)
          Removes from this set all of its elements that are contained in the specified collection.
 boolean removeInterval(long first, long last)
          Removes from this set all the numbers between first and last, inclusive.
 long size64()
          // PREPROC: Long,Int only Returns the number of elements in this set.
 LongSortedSet subSet(long first, long last)
          A subset view containing all elements from this set between first, inclusive, and last, inclusive.
 
Methods inherited from class edu.emory.mathcs.util.collections.longs.AbstractLongSortedSet
headSet, retainAll, retainInterval, tailSet, toCompactString
 
Methods inherited from class edu.emory.mathcs.util.collections.longs.AbstractLongSet
equals, hashCode
 
Methods inherited from class edu.emory.mathcs.util.collections.longs.AbstractLongCollection
containsAll, size, toArray, toArray, toString
 
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface edu.emory.mathcs.util.collections.longs.LongSortedSet
toString
 
Methods inherited from interface edu.emory.mathcs.util.collections.longs.LongSet
containsAll, equals, hashCode, size, toArray, toArray
 

Constructor Detail

LongIntervalSet

public LongIntervalSet()
Creates a new set of longs.


LongIntervalSet

public LongIntervalSet(long min,
                       long max)

LongIntervalSet

public LongIntervalSet(LongCollection c)

LongIntervalSet

public LongIntervalSet(LongSet c)
Method Detail

min

public long min()
Description copied from interface: LongSet
The smallest number that can be stored in this set.

Specified by:
min in interface LongSet
Overrides:
min in class AbstractLongSet

max

public long max()
Description copied from interface: LongSet
The largest number that can be stored in this set.

Specified by:
max in interface LongSet
Overrides:
max in class AbstractLongSet

intervalCount

public int intervalCount()
Description copied from interface: LongSortedSet
Returns the minimum count of intervals into which this set can be decomposed. For instance, {1, 3,4,5, 8,9}.intervalCount() == 3.

Specified by:
intervalCount in interface LongSortedSet
Overrides:
intervalCount in class AbstractLongSortedSet

size64

public long size64()
Description copied from interface: LongSet
// PREPROC: Long,Int only Returns the number of elements in this set. // PREPROC: Long,Int only

Specified by:
size64 in interface LongSet
Overrides:
size64 in class AbstractLongSortedSet

isEmpty

public boolean isEmpty()
Description copied from interface: LongSet
Returns true if this set is empty; false otherwise.

Specified by:
isEmpty in interface LongSet
Overrides:
isEmpty in class AbstractLongSortedSet

clear

public void clear()
Removes all elements from the set.

Specified by:
clear in interface LongSet
Overrides:
clear in class AbstractLongCollection

add

public boolean add(long n)
Adds an element to the set if it is not already present.

Specified by:
add in interface LongSet
Overrides:
add in class AbstractLongCollection
Returns:
true is the element was added

addInterval

public boolean addInterval(long first,
                           long last)
Description copied from interface: LongSet
Adds to this set all the numbers between first and last, inclusive, that are not already present in this set and belong to this set's domain.

Specified by:
addInterval in interface LongSet
Overrides:
addInterval in class AbstractLongSet

addAll

public boolean addAll(LongCollection c)
Description copied from interface: LongSet
Adds all of the elements in the specified collection to this set if they're not already present, and if they fall within this set's domain. If the specified collection is also a set, the addAll operation effectively modifies this set so that its value is the union of the two sets, intersected with this set's domain. The behavior of this operation is undefined if the specified collection is modified while the operation is in progress.

Specified by:
addAll in interface LongSet
Overrides:
addAll in class AbstractLongSet

remove

public boolean remove(long n)
Description copied from interface: LongSet
Removes the specified number from this set if it is present.

Specified by:
remove in interface LongSet
Overrides:
remove in class AbstractLongCollection

removeInterval

public boolean removeInterval(long first,
                              long last)
Description copied from interface: LongSet
Removes from this set all the numbers between first and last, inclusive.

Specified by:
removeInterval in interface LongSet
Overrides:
removeInterval in class AbstractLongSet

removeAll

public boolean removeAll(LongCollection c)
Description copied from interface: LongSet
Removes from this set all of its elements that are contained in the specified collection. If the specified collection is also a set, this operation effectively modifies this set so that its value is the asymmetric set difference of the two sets.

Specified by:
removeAll in interface LongSet
Overrides:
removeAll in class AbstractLongSet

contains

public boolean contains(long n)
Checks whether the set contains a given element

Specified by:
contains in interface LongSet
Overrides:
contains in class AbstractLongCollection
Parameters:
n - the element
Returns:
true if the set contains n, false otherwise

containsInterval

public boolean containsInterval(long first,
                                long last)
Description copied from interface: LongSet
Returns true if this set contains all the numbers between first and last, inclusive; false otherwise.

Specified by:
containsInterval in interface LongSet
Overrides:
containsInterval in class AbstractLongSet

enclosingInterval

public LongInterval enclosingInterval(long e)
Description copied from interface: LongSortedSet
Returns the widest interval contained in this set that includes the specified number, or null if this set does not include the specified number.

Specified by:
enclosingInterval in interface LongSortedSet
Returns:
the interval containing the specified number.

lower

public long lower(long n)
Description copied from interface: LongSortedSet
Returns the largest number in this set < e.

Specified by:
lower in interface LongSortedSet
Overrides:
lower in class AbstractLongSortedSet

floor

public long floor(long n)
Description copied from interface: LongSortedSet
Returns the largest number in this set <= e.

Specified by:
floor in interface LongSortedSet
Overrides:
floor in class AbstractLongSortedSet

higher

public long higher(long n)
Description copied from interface: LongSortedSet
Returns the smallest number in this set > e.

Specified by:
higher in interface LongSortedSet
Overrides:
higher in class AbstractLongSortedSet

ceiling

public long ceiling(long n)
Description copied from interface: LongSortedSet
Returns the smallest number in this set >= e.

Specified by:
ceiling in interface LongSortedSet
Overrides:
ceiling in class AbstractLongSortedSet

intervalIterator

public java.util.Iterator intervalIterator()
Description copied from interface: LongSortedSet
Returns an iterator over intervals of this set, in an increasing numerical order.

Specified by:
intervalIterator in interface LongSortedSet
Returns:
an iterator over intervals of this set

iterator

public LongIterator iterator()
Description copied from interface: LongSortedSet
Returns an iterator over numbers in this set, in an increasing numerical order.

Specified by:
iterator in interface LongSortedSet
Overrides:
iterator in class AbstractLongSortedSet

descendingIntervalIterator

public java.util.Iterator descendingIntervalIterator()
Description copied from interface: LongSortedSet
Returns an iterator over intervals of this set, in a decreasing numerical order.

Specified by:
descendingIntervalIterator in interface LongSortedSet
Returns:
a descending iterator over intervals of this set

descendingIterator

public LongIterator descendingIterator()
Description copied from interface: LongSortedSet
Returns an iterator over numbers in this set, in a decreasing numerical order.

Specified by:
descendingIterator in interface LongSortedSet
Overrides:
descendingIterator in class AbstractLongSortedSet

first

public long first()
Description copied from interface: LongSortedSet
Returns the smallest number in this set.

Specified by:
first in interface LongSortedSet
Overrides:
first in class AbstractLongSortedSet

last

public long last()
Description copied from interface: LongSortedSet
Returns the largest number in this set.

Specified by:
last in interface LongSortedSet
Overrides:
last in class AbstractLongSortedSet

pollFirst

public long pollFirst()
Description copied from interface: LongSortedSet
Returns and removes the smallest number in this set.

Specified by:
pollFirst in interface LongSortedSet
Overrides:
pollFirst in class AbstractLongSortedSet

pollLast

public long pollLast()
Description copied from interface: LongSortedSet
Returns and removes the largest number in this set.

Specified by:
pollLast in interface LongSortedSet
Overrides:
pollLast in class AbstractLongSortedSet

firstInterval

public LongInterval firstInterval()
Description copied from interface: LongSortedSet
Returns the first (left-most), widest interval contained in this set, or null if this set is empty.

Specified by:
firstInterval in interface LongSortedSet
Overrides:
firstInterval in class AbstractLongSortedSet

lastInterval

public LongInterval lastInterval()
Description copied from interface: LongSortedSet
Returns the last (right-most), widest interval contained in this set, or null if this set is empty.

Specified by:
lastInterval in interface LongSortedSet
Overrides:
lastInterval in class AbstractLongSortedSet

ceilingInterval

public LongInterval ceilingInterval(long n)
Description copied from interface: LongSortedSet
Returns the smallest (left-most), widest interval contained in this set which elements are not all smaller than the specified number. In other words, it either includes the specified number or has all elements strictly greater than the specified number.

Specified by:
ceilingInterval in interface LongSortedSet
Returns:
the smallest interval which upper bound is >= than the specified number.

floorInterval

public LongInterval floorInterval(long n)
Description copied from interface: LongSortedSet
Returns the largest (right-most), widest interval contained in this set which elements are not all greater than the specified number. In other words, it either includes the specified number or has all elements strictly less than the specified number.

Specified by:
floorInterval in interface LongSortedSet
Returns:
the largest interval which lower bound is <= than the specified number.

higherInterval

public LongInterval higherInterval(long n)
Description copied from interface: LongSortedSet
Returns the smallest (left-most), widest interval contained in this set which all elements are strictly greater than the specified number.

Specified by:
higherInterval in interface LongSortedSet
Returns:
the smallest interval greater than the specified number.

lowerInterval

public LongInterval lowerInterval(long n)
Description copied from interface: LongSortedSet
Returns the largest and widest interval contained in this set which all elements are strictly less than the specified number.

Specified by:
lowerInterval in interface LongSortedSet
Returns:
the largest interval smaller than the specified number.

pollFirstInterval

public LongInterval pollFirstInterval()
Description copied from interface: LongSortedSet
Returns and removes the first (left-most), widest interval contained in this set, or null if this set is empty.

Specified by:
pollFirstInterval in interface LongSortedSet
Overrides:
pollFirstInterval in class AbstractLongSortedSet

pollLastInterval

public LongInterval pollLastInterval()
Description copied from interface: LongSortedSet
Returns and removes the last (right-most), widest interval contained in this set, or null if this set is empty.

Specified by:
pollLastInterval in interface LongSortedSet
Overrides:
pollLastInterval in class AbstractLongSortedSet

subSet

public LongSortedSet subSet(long first,
                            long last)
Description copied from interface: LongSortedSet
A subset view containing all elements from this set between first, inclusive, and last, inclusive. More precisely, the view is narrowed to the domain [min, max]. Hence, complement set of this set will NOT include any elements outside [min, max].

Specified by:
subSet in interface LongSortedSet
Parameters:
first - the minimum element of this view (inclusive).
last - the maximum element of this view (inclusive).
Returns:
the subset view

complementSet

public LongSet complementSet()
Description copied from interface: LongSet
Returns a complement view of this set. Complement view is a set that has the same domain as this set, and consists of all numbers from the domain that are not contained in this set. Changes done to this set are reflected in the complement view after it is created.

Specified by:
complementSet in interface LongSet
Overrides:
complementSet in class AbstractLongSet