/****************************************************************************** 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