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.

_builtin_.Any
  extract_min
pre
  !max_heap;
Extract the root of the heap, which must be a heap storing the minimum value at its root.

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

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

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

_builtin_.Any (object)
  extract_root
pre
  length > 0
post
  length >= 0 && [object heap_index] == 0;
Extract and return the root object of the heap.

_builtin_.Any (object)
  root
pre
  length > 0;
Return the root object of the heap, without extracting it.

void
  remove HeapElement elt
pre
  [elt heap_index] > 0 && elements[([elt heap_index] - 1)] == elt
post
  [elt heap_index] == 0;
Remove the elt from the receiving heap. The elt must be an element of the heap.

MutableCollection

void
  add HeapElement object
pre
  [object heap_index] == 0
post
  length == 1 + old length;
Add the object to this Heap. It may not yet be part of any (other) heap, as stated by the precondition.

void
  addElementsFromEnumerator Enumerator e;
Undocumented.

void
  empty;
Undocumented.

Enumerable

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

Internal methods

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


Generated by tm 1.01.