/****************************************************************************** Heap ---------------------------------------------------- Copyright (c) Gunnar Gotshalks. All Rights Reserved. Permission to use, copy, modify, and distribute this software and its documentation for NON-COMMERCIAL purposes and without fee is hereby granted. *******************************************************************************/ package FlexOr.container; import java.util.*; import java.lang.reflect.*; /**

@author Gunnar Gotshalks @version 1.0 1999 Jan 15 */ public class Heap implements Container { /** Define an empty heap. @param capacity Create heap space of the specified capacity. @param orderComparison defines how nodes are compared when deciding which branch to take. @param equalComparison defines how nodes are checked for equality. @exception 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] )
*/ public Heap(int capacity, BinaryPredicate orderComparison, BinaryPredicate equalComparison) { Capacity = capacity; if (Capacity < 2) { throw new TooSmallException("Heap should have Capacity >= 2"); } heap = new Object[Capacity+1]; comparison = orderComparison; equalTo = equalComparison; } /** Define a heap from a given array of Objects. @param array Create a heap from these objects. @param capacity Create heap space of capacity max(capacity, array.length). @param orderComparison defines how nodes are compared when deciding which branch to take. @param equalComparison defines how nodes are checked for equality. @exception TooSmallException when caller requests a size < 2. */ public Heap(Object[] array, int capacity, BinaryPredicate orderComparison, BinaryPredicate equalComparison) { currentSize = Array.getLength(array); Capacity = Math.max(capacity, currentSize); if (Capacity < 2) { throw new TooSmallException("Heap should have Capacity >= 2"); } heap = new Object[Capacity+1]; System.arraycopy(array, 0, heap, 1, currentSize); comparison = orderComparison; equalTo = equalComparison; heapify(); } /****************************************************************************** Defining the component objects *******************************************************************************/ /** The heap is stored in an array. heap[0] to minimize arithmetic in the algorithms. */ protected Object[] heap ; /** Number of the nodes actually in the heap. */ protected int currentSize = 0; /** Maximum number of nodes in the heap. */ final int Capacity; /** Defines how to compare data to maintain the heap property. */ private BinaryPredicate comparison; /** Defines what equal node data means. Could mean only part of the data are equal, for example keys but not the value associated with a key. */ private BinaryPredicate equalTo; /******************************************************************************* Access Methods *******************************************************************************/ /** 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
*/ synchronized public boolean contains(Object obj) { for (int i = 1 ; i <= currentSize ; i++) { if (equalTo.execute(obj, heap[i])) return true; } return false; } /** Check if the container is empty. 

Requires: True
Ensures: isEmpty = (count = 0)
*/ synchronized public boolean isEmpty() { return currentSize == 0; } /** Check if the container is full. 

Requires: True
Ensures: isFull = (count = Capacity)
*/ synchronized public boolean isFull() { return currentSize == Capacity; } /** Returns the number of elements in the container. 

Requires: True
Ensures: result = size
*/ synchronized public int size() { return currentSize; } /** Returns an enumerator sequentially scanning the heap. @exception NoSuchElementException when nextElement is called with an empty enumeration sequence. */ synchronized public Enumeration elements() { return new Enumeration () { public boolean hasMoreElements() { return current <= currentSize; } public Object nextElement() { if (current > currentSize) throw new NoSuchElementException(); return heap[current++]; } private int current = 1; }; } /** Maximum number of elements that can be stored in the heap. */ synchronized public int capacity() { return Capacity; } /******************************************************************************* Update Methods *******************************************************************************/ /** Adds obj to the heap. 

Requires: size < Capacity
Ensures: contains(obj) = true
         size = old size + 1
@exception ContainerFullException when container already contains Capacity elements. */ synchronized public void add(Object obj) { if (currentSize == Capacity) throw new ContainerFullException("Reached maxumum size of " + Capacity); heap[++currentSize] = obj; restoreHeapUp(); } /** Empty the container. 

Requires: True
Ensures: size = 0
*/ synchronized public void removeAll() { currentSize = 0; } /** Remove the top element in the heap. 

Requires: size >= 0
Ensures: size = old size - 1
     old inorderSequence = obj ^ inorderSequence
@exception ContainerEmptyException when removing from an empty container. */ synchronized public Object remove() { if (currentSize <= 0) { throw new ContainerEmptyException(); } Object result = heap[1]; heap[1] = heap[currentSize--]; restoreHeapDown(1); return result; } /******************************************************************************* Object Methods *******************************************************************************/ /** 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
*/ synchronized public Object clone() { Heap result = new Heap(Capacity, comparison, equalTo); for (int i = 1 ; i <= currentSize ; i++) { result.heap[i] = heap[i]; } result.currentSize = currentSize; return result; } /** Return a string representation of the contents of the heap. 

Requires: true
Ensures: result = string representation of tree
*/ synchronized public String toString() { if (currentSize <= 0) return "[]"; StringBuffer result = new StringBuffer(); result = result.append("[ " + heap[1].toString()); for (int i = 2 ; i <= currentSize ; i++) { result = result.append(" " + heap[i].toString()); } result = result.append(" ]"); return result.toString(); } /** 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
*/ synchronized public boolean equals(Object container) { if ( container == null || ! (container instanceof Heap) || currentSize != ((Heap) container).currentSize) return false; Object[] otherHeap = ((Heap)container).heap; for (int i = 1 ; i <= currentSize ; i++) { if (!equalTo.execute(heap[i], otherHeap[i])) return false; } return true; } /******************************************************************************* Support classes and methods *******************************************************************************/ /** Rearrange, if necessary, heap elements to restore the heap property with respect to comparison. 

Requires: True
Ensure: heap has the heap property.
*/

  private void heapify() {
    for (int i = currentSize/2 ; i > 0 ; i-- ) {
      restoreHeapDown(i);
    }  
  }

/** Percolate down the obj at the root of the current subtree, if it violates
the heap property.


Requires: Subtrees at 2*root and 2*root+1 have the heap
property
Ensures: Heap property holds in the subtree beginning at root.
*/

  private void restoreHeapDown(int root) {
    int left = 2*root;
    if (left > currentSize) return;
    int right = left + 1;
    if (right > currentSize) { // Only a left child exists
        if (comparison.execute(heap[root], heap[left])) return;
        else { swap(root,left); return; }
    }
    
    // Both children exist.
    
    if (comparison.execute(heap[root], heap[left])) {
        if (comparison.execute(heap[root], heap[right])) return;
        else { swap(root, right);
               restoreHeapDown(right);
        }
    }
    else {
        if (comparison.execute(heap[root], heap[right])) {
            swap(root, left);
            restoreHeapDown(left);
        }
        else {
            if (comparison.execute(heap[left], heap[right])) {
                swap(root, left);
                restoreHeapDown(left);
            }
            else {
                swap(root, right);
                restoreHeapDown(right);
            }
        } 
    }
  }

/** Percolate up the obj at heap[currentSize], if it violates the heap
property.


Requires: heap[1..currentSize-1] has the heap property.
Ensures: heap[1..currentSize] has the heap property.
*/
  
  private void restoreHeapUp() {
    int current = currentSize;
    int parent;
    while (current > 1) {
      parent = current/2;
      if (comparison.execute(heap[parent], heap[current])) break;
      swap(parent, current);
      current = parent;
    }
  }

/** Exchange elements heap[a] and heap[b]. */

  private void swap(int a, int b) {
    Object tmp = heap[a];
    heap[a] = heap[b];
    heap[b] = tmp;
  }
  
} // End of class BinaryTree