8.40. File tom/IntegerRangeSet

class tom.IntegerRangeSet

The 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.

inherits

State supers: State, Enumerable

instance tom.IntegerRangeSet

variables

IntegerRangeSetNode root;

The root of the tree holding information.

methods

boolean
  add int v;

Add v to the receiving set. Return FALSE if it was already present; TRUE otherwise.

boolean
  equal id other;

Undocumented.

boolean
  equalIntegerRangeSetNode IntegerRangeSetNode other;

Undocumented.

id
  intersectionWith id other;

Return a new set being the intersection of the receiving set and the other set.

boolean
  isEmpty;

Undocumented.

boolean
  isSubsetOf id other;

Return YES if the receiving set is a subset of the other set.

(boolean, int) (non_empty, value)
  highestPresent;

Return the highest value present in the set.

(boolean, int) (non_empty, value)
  lowestPresent;

Return the lowest value present in the set.

boolean
  member int v;

Return TRUE iff the set contains v.

int
  nextNonPresent int i;

Return the smallest element >= i that is not yet in the set.

(boolean, int)
  nextPresent int i;

Return the smallest element > i that is contained in the tree, preceded by whether such an element actually is in the tree.

int
  previousNonPresent int i;

Return the largest element <= i that is not yet in the set.

(boolean, int)
  previousPresent int i;

Return the largest element <= i that is in the set.

boolean (b)
  remove int v;

Remove v from the set, returning TRUE if it was actually contained.

void
  shiftFrom int i;

Increase the value of all elements in the tree >= i by one.

(boolean, int)
  smallestElement;

Return the smallest value contained, preceded by whether we're not empty.

void
  uniteWith id other;

Modify the receiving set by adding the elements from the other set.

OutputStream
  write OutputStream s;

Undocumented.

Enumerator
  enumerator;

Undocumented.

protected id
  initWithEnumerator Enumerator e;

Undocumented.

class tom.IntegerRangeSetNode

inherits

State supers: State

instance tom.IntegerRangeSetNode

variables

id left;

The left and right subtrees.

id right;

int offset;

The offset from our parent.

int size;

The number of integers in this node.

methods

boolean
  add int v;

Add v to the tree rooted at the receiving node. Return FALSE if it was already present; TRUE otherwise.

boolean
  equalIntegerRangeSetNode id other;

Undocumented.

id
  init (int, int) (o, s);

Designated initializer.

int
  highestPresent;

Return the highest value present in the set.

int
  lowestPresent;

Return the lowest value present in the set.

boolean
  member int v;

Return TRUE iff the set contains v.

int
  nextNonPresent int i;

Return the smallest element >= i that is not yet in the tree.

(boolean, int)
  nextPresent int i;

Return the smallest element > i that is contained in the tree, preceded by whether such an element actually is in the tree.

int
  previousNonPresent int i;

Return the largest element <= i that is not yet in the tree.

(boolean, int)
  previousPresent int i;

Return the largest element in the tree which is smaller than i.

(id, boolean)
  remove int v;

Remove v from the receiving tree, returning the modified tree, and TRUE if it was actually removed.

void
  shiftFrom int i;

Increase the value of all elements in the tree >= i by one.

int
  smallestElement;

Return the smallest value contained.

OutputStream
   write OutputStream s
  offset int i;

Undocumented.

protected (id, id, int, int)
  dissect;

Return the guts of this object.

protected (id, int)
  mergeLRL int v;

Merge the subtree rooted at this node, to accomodate the value 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;

Merge the subtree rooted at this node, to accomodate the value 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;

Adjust the offset by n.

protected void
  set_right id n;

Set the right node.

protected void
  setRightMost id r;

Set the right most node of the receiving tree to r.

class tom.IntegerRangeSetNodeEnumerator

inherits

State supers: State, Enumerator

instance tom.IntegerRangeSetNodeEnumerator

variables

IntegerRangeSetNode root;

The root of the tree of nodes.

int previous;

The previous integer value retrieved.

methods

id
  init IntegerRangeSetNode r;

Undocumented.

(boolean, Number)
  next;

Undocumented.

(boolean, int) (valid, value)
  next;

Undocumented.