IntegerRangeSet
is good at holding ranges of integers. Ranges
are stored in an unbalanced tree. The number of ranges dictates the
memory usage by the set. Testing for membership is O(log n) where n
is the number of ranges.
IntegerRangeSetNode root;
boolean add int v;
v
to the receiving set. Return FALSE
if it was already
present; TRUE
otherwise.
boolean equal id other;
boolean equalIntegerRangeSetNode IntegerRangeSetNode other;
id intersectionWith id other;
other
set.
boolean isEmpty;
boolean isSubsetOf id other;
YES
if the receiving set is a subset of the other
set.
(boolean, int) (non_empty, value) highestPresent;
(boolean, int) (non_empty, value) lowestPresent;
boolean member int v;
TRUE
iff the set contains v
.
int nextNonPresent int i;
i
that is not yet in the set.
(boolean, int) nextPresent int i;
i
that is contained in the tree,
preceded by whether such an element actually is in the tree.
int previousNonPresent int i;
i
that is not yet in the set.
(boolean, int) previousPresent int i;
i
that is in the set.
boolean (b) remove int v;
v
from the set, returning TRUE
if it was actually
contained.
void shiftFrom int i;
i
by one.
(boolean, int) smallestElement;
void uniteWith id other;
OutputStream write OutputStream s;
Enumerator enumerator;
protected id initWithEnumerator Enumerator e;
id left;
id right;
int offset;
int size;
boolean add int v;
v
to the tree rooted at the receiving node. Return FALSE
if
it was already present; TRUE
otherwise.
boolean equalIntegerRangeSetNode id other;
id init (int, int) (o, s);
int highestPresent;
int lowestPresent;
boolean member int v;
TRUE
iff the set contains v
.
int nextNonPresent int i;
i
that is not yet in the tree.
(boolean, int) nextPresent int i;
i
that is contained in the tree,
preceded by whether such an element actually is in the tree.
int previousNonPresent int i;
i
that is not yet in the tree.
(boolean, int) previousPresent int i;
i
.
(id, boolean) remove int v;
v
from the receiving tree, returning the modified tree, and
TRUE
if it was actually removed.
void shiftFrom int i;
i
by one.
int smallestElement;
OutputStream write OutputStream s offset int i;
protected (id, id, int, int) dissect;
protected (id, int) mergeLRL int v;
v
,
returning the modified tree and the extra size for our parent node.
Our parent actually holds the value v
(as the first value).
protected (id, int) mergeRLL int v;
v
,
returning the modified tree and the extra size for our parent node.
Our parent actually holds the value v
(as the last value).
protected void offset int n;
offset
by n
.
protected void set_right id n;
right
node.
protected void setRightMost id r;
r
.
IntegerRangeSetNode root;
int previous;
id init IntegerRangeSetNode r;
(boolean, Number) next;
(boolean, int) (valid, value) next;