8.36. File tom/Heap

class tom.Heap

inherits

State supers: State, MutableCollection

instance tom.Heap

variables

MutableArray elements;

The array used to store the elements.

public int length;

The number of elements. This is equal to [elements length].

public mutable selector compare_selector;

The selector used to have two elements compare themselves. If this isn't set, i_compare_r will be used.

boolean max_heap;

If this is TRUE, this is a heap of which the root node is the largest. Otherwise, the root is the smallest node.

methods

id
  init;

Invoke [self init TRUE].

id (self)
  init boolean root_is_max;

Designated initializer.

boolean
  dump_simple_p;

Return NO.

Any
  extract_min
pre
  !max_heap;

Extract the root of the heap, which must be a heap storing the minimum value at its root.

int
  index_of_element All element;

Return the index of the element in this heap. Used by elements that do not remember their own index.

Any (object)
  min
pre
  !max_heap;

Return the minimum value of the heap, which must be a heap storing the minimum value at its root. Return nil if the heap is empty.

Any
  extract_max
pre
  max_heap;

Extract the root of the heap, which must be a heap which stores the maximum value at its root.

Any (object)
  max
pre
  max_heap;

Return the maximum value of the heap, which must be a heap storing the maximum value at its root. Return nil if the heap is empty.

Any (object)
  extract_root
pre
  length > 0
post
  length == old length - 1;

Extract and return the root object of the heap.

Any (object)
  root
pre
  length > 0;

Return the root object of the heap, without extracting it.

void
  remove Comparable elt;

Remove the elt from the receiving heap. The elt should be an element of the heap.

void
  add Comparable object
post
  length == 1 + old length;

Add the object to this Heap.

void
  addElementsFromEnumerator Enumerator e;

Undocumented.

void
  empty;

Remove all elements.

Enumerator
  enumerator;

Return an enumerator on the elements of this heap. Note that the order of the elements returned is undefined.

protected void
  build_heap;

Build a heap from the elements already in elements.

int
  compare (Comparable, Comparable) (one, other);

Let one compare itself with the other, either using the compare_selector, or, if not set, the int compare id method.

protected void
  heapify int index;

Heapify from the node at index i (which is off by 1 compared to the index of the element in the elements array).