FlexOr.container
Class Heap

java.lang.Object
  FlexOr.container.Heap

All Implemented Interfaces:

Container, java.lang.Cloneable

public class Heap
extends java.lang.Object
implements Container

Version:

1.0 1999 Jan 15

Author:

Gunnar Gotshalks

Constructor Summary

Heap(int capacity, BinaryPredicate orderComparison, BinaryPredicate equalComparison)
Define an empty heap.

Heap(java.lang.Object[] array, int capacity, BinaryPredicate orderComparison, BinaryPredicate equalComparison)
Define a heap from a given array of Objects.

Method Summary

void	add(java.lang.Object obj) Adds obj to the heap.
int	capacity() Maximum number of elements that can be stored in the heap.
java.lang.Object	clone() Return a copy of the heap that points to the same objects as in the original heap.
boolean	contains(java.lang.Object obj) Determines whether an element is in the tree.
java.util.Enumeration<java.lang.Object>	elements() Returns an enumerator sequentially scanning the heap.
boolean	equals(java.lang.Object container) Check for equality of contents of two containers.
boolean	isEmpty() Check if the container is empty.
boolean	isFull() Check if the container is full.
java.lang.Object	remove() Remove the top element in the heap.
void	removeAll() Empty the container.
int	size() Returns the number of elements in the container.
java.lang.String	toString() Return a string representation of the contents of the heap.

Methods inherited from class java.lang.Object

getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

Heap

public Heap(int capacity,
            BinaryPredicate orderComparison,
            BinaryPredicate equalComparison)

Define an empty heap.

Parameters:

capacity - Create heap space of the specified capacity.

orderComparison - defines how nodes are compared when deciding which branch to take.

equalComparison - defines how nodes are checked for equality.

Throws:

TooSmallException - when caller requests a Capacity < 2

Class invariant:

heap[1..currentSize] has the heap property.

(forall i: 1..currentSize ::
       heap[i] orderComparison heap[2*i]
   and heap[i] orderComparison heap[2*i+1] )

Heap

public Heap(java.lang.Object[] array,
            int capacity,
            BinaryPredicate orderComparison,
            BinaryPredicate equalComparison)

Define a heap from a given array of Objects.

Parameters:

array - Create a heap from these objects.

capacity - Create heap space of capacity max(capacity, array.length).

orderComparison - defines how nodes are compared when deciding which branch to take.

equalComparison - defines how nodes are checked for equality.

Throws:

TooSmallException - when caller requests a size < 2.

Method Detail

contains

public boolean contains(java.lang.Object obj)

Determines whether an element is in the tree. O(size) due to linear search.

Requires: True
Ensures: contains(obj) => result = true
      not contains(obj) => result = false

Specified by:

contains in interface Container

isEmpty

public boolean isEmpty()

Check if the container is empty.

Requires: True
Ensures: isEmpty = (count = 0)

Specified by:

isEmpty in interface Container

isFull

public boolean isFull()

Check if the container is full.

Requires: True
Ensures: isFull = (count = Capacity)

Specified by:

isFull in interface Container

size

public int size()

Returns the number of elements in the container.

Requires: True
Ensures: result = size

Specified by:

size in interface Container

elements

public java.util.Enumeration<java.lang.Object> elements()

Returns an enumerator sequentially scanning the heap.

Specified by:

elements in interface Container

Throws:

java.util.NoSuchElementException - when nextElement is called with an empty enumeration sequence.

capacity

public int capacity()

Maximum number of elements that can be stored in the heap.

add

public void add(java.lang.Object obj)

Adds obj to the heap.

Requires: size < Capacity
Ensures: contains(obj) = true
         size = old size + 1

Specified by:

add in interface Container

Throws:

ContainerFullException - when container already contains Capacity elements.

removeAll

public void removeAll()

Empty the container.

Requires: True
Ensures: size = 0

Specified by:

removeAll in interface Container

remove

public java.lang.Object remove()

Remove the top element in the heap.

Requires: size >= 0
Ensures: size = old size - 1
     old inorderSequence = obj ^ inorderSequence

Specified by:

remove in interface Container

Throws:

ContainerEmptyException - when removing from an empty container.

clone

public java.lang.Object clone()

Return a copy of the heap that points to the same objects as in the original heap. Part way between a shallow and deep copy.

Requires: True
Ensures: result = copy of heap

Specified by:

clone in interface Container

Overrides:

clone in class java.lang.Object

toString

public java.lang.String toString()

Return a string representation of the contents of the heap.

Requires: true
Ensures: result = string representation of tree

Specified by:

toString in interface Container

Overrides:

toString in class java.lang.Object

equals

public boolean equals(java.lang.Object container)

Check for equality of contents of two containers. By equality we mean heaps are of the same size corresponding heap elements are equal.

Requires: True
Ensures: result = true => container contents are equal
         result = false => container contents are not equal

Specified by:

equals in interface Container

Overrides:

equals in class java.lang.Object