edu.emory.mathcs.util.collections.shorts
Class ShortIntervalSet

java.lang.Object
  extended byedu.emory.mathcs.util.collections.shorts.AbstractShortCollection
      extended byedu.emory.mathcs.util.collections.shorts.AbstractShortSet
          extended byedu.emory.mathcs.util.collections.shorts.AbstractShortSortedSet
              extended byedu.emory.mathcs.util.collections.shorts.ShortIntervalSet
All Implemented Interfaces:
java.io.Serializable, ShortCollection, ShortSet, ShortSortedSet

public class ShortIntervalSet
extends AbstractShortSortedSet
implements java.io.Serializable

Set of short 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 short as they form clusters (short 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.shorts.AbstractShortSortedSet
AbstractShortSortedSet.AbstractComplementSubView, AbstractShortSortedSet.AbstractSubView, AbstractShortSortedSet.ForwardIntervalItemIterator, AbstractShortSortedSet.ReverseIntervalItemIterator
 
Constructor Summary
ShortIntervalSet()
          Creates a new set of shorts.
ShortIntervalSet(ShortCollection c)
           
ShortIntervalSet(ShortSet c)
           
ShortIntervalSet(short min, short max)
           
 
Method Summary
 boolean add(short n)
          Adds an element to the set if it is not already present.
 boolean addAll(ShortCollection 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(short first, short last)
          Adds to this set all the numbers between first and last, inclusive, that are not already present in this set and beshort to this set's domain.
 short ceiling(short n)
          Returns the smallest number in this set >= e.
 ShortInterval ceilingInterval(short 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.
 ShortSet complementSet()
          Returns a complement view of this set.
 boolean contains(short n)
          Checks whether the set contains a given element
 boolean containsInterval(short first, short 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.
 ShortIterator descendingIterator()
          Returns an iterator over numbers in this set, in a decreasing numerical order.
 ShortInterval enclosingInterval(short 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.
 short first()
          Returns the smallest number in this set.
 ShortInterval firstInterval()
          Returns the first (left-most), widest interval contained in this set, or null if this set is empty.
 short floor(short n)
          Returns the largest number in this set <= e.
 ShortInterval floorInterval(short n)
          Returns the largest (right-most), widest interval contained in this set which elements are not all greater than the specified number.
 short higher(short n)
          Returns the smallest number in this set > e.
 ShortInterval higherInterval(short 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.
 ShortIterator iterator()
          Returns an iterator over numbers in this set, in an increasing numerical order.
 short last()
          Returns the largest number in this set.
 ShortInterval lastInterval()
          Returns the last (right-most), widest interval contained in this set, or null if this set is empty.
 short lower(short n)
          Returns the largest number in this set < e.
 ShortInterval lowerInterval(short n)
          Returns the largest and widest interval contained in this set which all elements are strictly less than the specified number.
 short max()
          The largest number that can be stored in this set.
 short min()
          The smallest number that can be stored in this set.
 short pollFirst()
          Returns and removes the smallest number in this set.
 ShortInterval pollFirstInterval()
          Returns and removes the first (left-most), widest interval contained in this set, or null if this set is empty.
 short pollLast()
          Returns and removes the largest number in this set.
 ShortInterval pollLastInterval()
          Returns and removes the last (right-most), widest interval contained in this set, or null if this set is empty.
 boolean remove(short n)
          Removes the specified number from this set if it is present.
 boolean removeAll(ShortCollection c)
          Removes from this set all of its elements that are contained in the specified collection.
 boolean removeInterval(short first, short last)
          Removes from this set all the numbers between first and last, inclusive.
 short size64()
           
 ShortSortedSet subSet(short first, short 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.shorts.AbstractShortSortedSet
headSet, retainAll, retainInterval, size, tailSet, toCompactString
 
Methods inherited from class edu.emory.mathcs.util.collections.shorts.AbstractShortSet
equals, hashCode
 
Methods inherited from class edu.emory.mathcs.util.collections.shorts.AbstractShortCollection
containsAll, 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.shorts.ShortSortedSet
toString
 
Methods inherited from interface edu.emory.mathcs.util.collections.shorts.ShortSet
containsAll, equals, hashCode, toArray, toArray
 

Constructor Detail

ShortIntervalSet

public ShortIntervalSet()
Creates a new set of shorts.


ShortIntervalSet

public ShortIntervalSet(short min,
                        short max)

ShortIntervalSet

public ShortIntervalSet(ShortCollection c)

ShortIntervalSet

public ShortIntervalSet(ShortSet c)
Method Detail

min

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

Specified by:
min in interface ShortSet
Overrides:
min in class AbstractShortSet

max

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

Specified by:
max in interface ShortSet
Overrides:
max in class AbstractShortSet

intervalCount

public int intervalCount()
Description copied from interface: ShortSortedSet
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 ShortSortedSet
Overrides:
intervalCount in class AbstractShortSortedSet

size64

public short size64()

isEmpty

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

Specified by:
isEmpty in interface ShortSet
Overrides:
isEmpty in class AbstractShortSortedSet

clear

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

Specified by:
clear in interface ShortSet
Overrides:
clear in class AbstractShortCollection

add

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

Specified by:
add in interface ShortSet
Overrides:
add in class AbstractShortCollection
Returns:
true is the element was added

addInterval

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

Specified by:
addInterval in interface ShortSet
Overrides:
addInterval in class AbstractShortSet

addAll

public boolean addAll(ShortCollection c)
Description copied from interface: ShortSet
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 ShortSet
Overrides:
addAll in class AbstractShortSet

remove

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

Specified by:
remove in interface ShortSet
Overrides:
remove in class AbstractShortCollection

removeInterval

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

Specified by:
removeInterval in interface ShortSet
Overrides:
removeInterval in class AbstractShortSet

removeAll

public boolean removeAll(ShortCollection c)
Description copied from interface: ShortSet
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 ShortSet
Overrides:
removeAll in class AbstractShortSet

contains

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

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

containsInterval

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

Specified by:
containsInterval in interface ShortSet
Overrides:
containsInterval in class AbstractShortSet

enclosingInterval

public ShortInterval enclosingInterval(short e)
Description copied from interface: ShortSortedSet
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 ShortSortedSet
Returns:
the interval containing the specified number.

lower

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

Specified by:
lower in interface ShortSortedSet
Overrides:
lower in class AbstractShortSortedSet

floor

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

Specified by:
floor in interface ShortSortedSet
Overrides:
floor in class AbstractShortSortedSet

higher

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

Specified by:
higher in interface ShortSortedSet
Overrides:
higher in class AbstractShortSortedSet

ceiling

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

Specified by:
ceiling in interface ShortSortedSet
Overrides:
ceiling in class AbstractShortSortedSet

intervalIterator

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

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

iterator

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

Specified by:
iterator in interface ShortSortedSet
Overrides:
iterator in class AbstractShortSortedSet

descendingIntervalIterator

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

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

descendingIterator

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

Specified by:
descendingIterator in interface ShortSortedSet
Overrides:
descendingIterator in class AbstractShortSortedSet

first

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

Specified by:
first in interface ShortSortedSet
Overrides:
first in class AbstractShortSortedSet

last

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

Specified by:
last in interface ShortSortedSet
Overrides:
last in class AbstractShortSortedSet

pollFirst

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

Specified by:
pollFirst in interface ShortSortedSet
Overrides:
pollFirst in class AbstractShortSortedSet

pollLast

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

Specified by:
pollLast in interface ShortSortedSet
Overrides:
pollLast in class AbstractShortSortedSet

firstInterval

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

Specified by:
firstInterval in interface ShortSortedSet
Overrides:
firstInterval in class AbstractShortSortedSet

lastInterval

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

Specified by:
lastInterval in interface ShortSortedSet
Overrides:
lastInterval in class AbstractShortSortedSet

ceilingInterval

public ShortInterval ceilingInterval(short n)
Description copied from interface: ShortSortedSet
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 ShortSortedSet
Returns:
the smallest interval which upper bound is >= than the specified number.

floorInterval

public ShortInterval floorInterval(short n)
Description copied from interface: ShortSortedSet
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 ShortSortedSet
Returns:
the largest interval which lower bound is <= than the specified number.

higherInterval

public ShortInterval higherInterval(short n)
Description copied from interface: ShortSortedSet
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 ShortSortedSet
Returns:
the smallest interval greater than the specified number.

lowerInterval

public ShortInterval lowerInterval(short n)
Description copied from interface: ShortSortedSet
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 ShortSortedSet
Returns:
the largest interval smaller than the specified number.

pollFirstInterval

public ShortInterval pollFirstInterval()
Description copied from interface: ShortSortedSet
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 ShortSortedSet
Overrides:
pollFirstInterval in class AbstractShortSortedSet

pollLastInterval

public ShortInterval pollLastInterval()
Description copied from interface: ShortSortedSet
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 ShortSortedSet
Overrides:
pollLastInterval in class AbstractShortSortedSet

subSet

public ShortSortedSet subSet(short first,
                             short last)
Description copied from interface: ShortSortedSet
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 ShortSortedSet
Parameters:
first - the minimum element of this view (inclusive).
last - the maximum element of this view (inclusive).
Returns:
the subset view

complementSet

public ShortSet complementSet()
Description copied from interface: ShortSet
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 ShortSet
Overrides:
complementSet in class AbstractShortSet