Heap--Min-Max Heap of Object Pointers

A Heap is a collection of objects with ordering based on a min-max heap (Atkinson, Sack, Santoro, and Strothotte, CACM, 1986). Objects may be added; the min or max may be accessed with first() or last(), respectively, or removed with removeFirst() or removeLast(), respectively. Objects stored at nodes on even (odd) levels are smaller (greater) than or equal to the values stored at their descendants (if any), as determined by applying the virtual compare() function. Object pointers are indexed originating at 0, with index range checking.

CONSTRUCTORS

Heap(int capacity =DEFAULT_CAPACITY): Constructs an empty Heap that can hold up to capacity objects. An NIHCL_ALLOCSIZE error is raised if capacity is not greater than 0. If an attempt is made to add more than capacity objects to a Heap, reSize() is called to increase its capacity. Since this is an expensive operation, is is wise to supply a reasonable estimate for capacity.
Heap(const ArrayOb&): Constructs a Heap from the argument ArrayOb. The constructed Heap has the same size (and capacity) as the argument ArrayOb.

ADDING OBJECTS

virtual Object* add(Object& ob): Adds the argument object ob to this Heap and returns a pointer to ob.

REMOVING OBJECTS

virtual Object* remove(const Object& ob): Removes the first occurrence of an object that isEqual() to ob from this Heap and returns a pointer to the object removed. If no equal object is found, nil is returned.
virtual void removeAll(): Removes all objects from this Heap and sets its size to zero.
virtual Object* removeFirst()
virtual Object* removeLast(): Removes the minimum or maximum object from this Heap and returns a pointer to it. If this Heap is empty, an NIHCL_CLTNEMPTY exception is raised.
virtual Object* removeId(const Object& ob): Removes the occurrence of ob from this Heap and returns a pointer to the object removed. If ob object is not in this Heap, nil is returned.

SEARCHING

virtual unsigned hash() const: Returns a number that classes such as Set can use as a hash table probe. Class Heap implements hash() by exclusive ORing the results of applying hash() to all objects in a Heap.
virtual unsigned occurrencesOf(const Object& ob) const: Returns the number of occurrences of objects isEqual() to ob in this Heap.

RELATIONAL OPERATORS

bool operator==(const Heap&) const
bool operator!=(const Heap&) const: Returns YES if the right Heap operand is equal to (or not equal to) the left Heap operand. Two Heaps are equal if they contain the same number of objects, and corresponding objects are isEqual().

TESTING HEAPS

virtual bool isEmpty() const: Returns YES if this Heap contains no objects.

COPYING HEAPS

virtual void deepenShallowCopy(): Converts this shallow copy to a deep copy by applying deepCopy() to all the object pointers, replacing each pointer with a pointer to its copy.

INDEXING HEAPS

virtual Object*& at(int i)
virtual const Object *const& at(int i) const: Returns a reference to the pointer to the ith object in this Heap. Note that because the objects in a Heap are not completely ordered, the ith object in a Heap is not necessarily the ith smallest object. The at() functions perform a range check on the index i and raise an NIHCL_INDEXRANGE exception if i is out of bounds.
virtual Object* first() const
virtual Object* last() const: Returns a pointer to the minimum (maximum) object in this Heap. If the Heap is empty an NIHCL_CLTNEMPTY error is raised.

HEAP CAPACITY AND SIZE

virtual unsigned capacity() const: Returns the number of objects that this Heap can hold before it will need to be expanded.
virtual unsigned size() const: Returns the number of objects in this Heap.
virtual void reSize(unsigned newSize): Changes the capacity of this Heap to newSize. If newSize is less than or equal to capacity(), then the capacity is not changed.

SUPPORT FOR ITERATORS

virtual void doFinish(Iterator& pos) const: Called to clean up the Iterator pos when it is destroyed.
virtual Object* doNext(Iterator& pos) const: Returns a pointer to the next larger object in the Heap, or 0 if no more objects remain. The Iterator argument pos maintains the current position in this Heap.
virtual void doReset(Iterator& pos) const: Resets the Iterator argument pos so that the next call to doNext() will return the first (minimum) object in this Heap.

SORTING HEAPS

OrderedCltn sort(): Returns an OrderedCltn containing the objects in this Heap, sorted in ascending order.

PROTECTED MEMBERS

Object I/O

virtual void storer(OIOofd& fd) const
virtual void storer(OIOout& strm) const: Stores the objects contained in this Heap to fd or strm by applying storeOn() to each of them.

DISABLED MEMBER FUNCTIONS

virtual void atAllPut(Object&)
virtual int indexOf(const Object&) const
virtual int indexOfSubCollection(const SeqCltn& cltn, int start =0) const
virtual void replaceFrom(int start, int stop, const SeqCltn& replacement, int startAt =0): These functions are implemented as shouldNotImplement().

EXCEPTIONS RAISED

NIHCL_CLTNEMPTY

Go to the previous, next section.