Heap.mon

package com.apamax.containers;

/** A comparator for a heap containing integers. 
 */
event HeapIntegerComparator
{
	/** True for a min-heap, false for a max-heap. */
	boolean increasing;
	/** Compare two integers.
	 * @returns Positive if increasing and a > b, or not increasing and a < b, 0 if equal and negative otherwise.
	 * @param a The first integer to compare.
	 * @param b The second integer to compare.
	 */
	action compare(any a, any b) returns integer
	{
		if (increasing) {
			return <integer>a-<integer>b;
		} else {
			return <integer>b-<integer>a;
		}
	}
}
/** A comparator for a heap containing strings. 
 */
event HeapStringComparator
{
	/** True for a min-heap, false for a max-heap. */
	boolean increasing;
	/** Compare two strings.
	 * @returns Positive if increasing and a > b, or not increasing and a < b, 0 if equal and negative otherwise.
	 * @param a The first string to compare.
	 * @param b The second string to compare.
	 */
	action compare(any a, any b) returns integer
	{
		integer positive := 1;
		if not increasing {
			positive := -1;
		}
		if <string>a < <string>b {
			return -positive;
		} else if <string>a = <string>b {
			return 0;
		} else {
			return positive;
		}
	}
}
/** A comparator for a heap containing events, given a field name which will be an integer to order the heap. 
 */
event HeapIntegerFieldComparator
{
	/** The field of the event to use for the comparison. Must be an integer. */
	string fieldName;
	/** True for a min-heap, false for a max-heap. */
	boolean increasing;
	/** Compare two events.
	 * @returns Positive if increasing and a > b, or not increasing and a < b, 0 if equal and negative otherwise.
	 * @param a The first event to compare.
	 * @param b The second event to compare.
	 */
	action compare(any a, any b) returns integer
	{
		if (increasing) {
			return <integer>a.getField(fieldName)-<integer>b.getField(fieldName);
		} else {
			return <integer>b.getField(fieldName)-<integer>a.getField(fieldName);
		}
	}
}
/**
 * A Max/Min-value Heap object with configurable type comparators.
 *
 * Create with a comparator object determining the Heap order and comparison function.
 * 
 * Several built-in comparators are available.
 *
 * @see HeapIntegerFieldComparator
 * @see HeapIntegerComparator
 * @see HeapStringComparator
 */
event Heap
{
	/** Create an empty heap with the given comparator.
	 * The comparator determines if this is a min-heap or a max-heap and how to compare the values.
	 * @param comparator A Comparator object with a <tt>compare</tt> action with the signature <tt>action&lt;any, any&gt; returns integer</tt>.
	 */
	static action create(any comparator) returns Heap
	{
		Heap h := new Heap;
		h.data := new sequence<any>;
		h.comparator := <action<any, any> returns integer> comparator.getAction("compare");
		return h;
	}
	/** Create an in-place heap on the given sequence, with the given comparator.
	 * The comparator determines if this is a min-heap or a max-heap and how to compare the values.
	 * @param data A sequence which will be heapified in-place and further heap operations will be made on the array.
	 * @param comparator A Comparator object with a <tt>compare</tt> action with the signature <tt>action&lt;any, any&gt; returns integer</tt>.
	 */
	static action heapify(sequence<any> data, any comparator) returns Heap
	{
		Heap h := new Heap;
		h.data := data;
		h.comparator := <action<any, any> returns integer> comparator.getAction("compare");
		h.makeHeap();
		return h;
	}

	/** Return the top value from the heap, according to its comparator. */
	action peekTop() returns any
	{
		return data[0];
	}

	/** Remove and return the top value from the heap, according to its comparator, maintaining the heap. */
	action pop() returns any
	{
		any t := data[0];
		data[0] := data[data.size()-1];
		data.remove(data.size()-1);
		heapifyDown(0);
		return t;
	}

	/** Push a new value into the heap, maintaining the heap. 
	 * @param val The value to add to the heap.
	 */
	action push(any val)
	{
		data.append(val);
		heapifyUp(data.size()-1);
	}

	/** Returns true if the heap is empty. */
	action empty() returns boolean
	{
		return data.size() = 0;
	}

	/** Returns the number of values in the heap. */
	action size() returns integer
	{
		return data.size();
	}

	/** @private */
	action swap(integer a, integer b)
	{
		any tmp := data[a];
		data[a] := data[b];
		data[b] := tmp;
	}

	/** @private */
	action parentOf(integer index) returns integer
	{
		return (index-1)/2;
	}

	/** @private */
	action leftChildOf(integer index) returns integer
	{
		integer child := (index*2)+1;
		if child >= data.size() { return -1; }
		else { return child; }
	}

	/** @private */
	action rightChildOf(integer index) returns integer
	{
		integer child := (index+1)*2;
		if child >= data.size() { return -1; }
		else { return child; }
	}

	/** @private */
	action heapifyDown(integer index)
	{
		integer leftChild := leftChildOf(index);
		integer rightChild := rightChildOf(index);
		integer largestNode := index;
		if leftChild > 0 and comparator(data[leftChild], data[largestNode]) < 0 {
			largestNode := leftChild;
		}
		if rightChild > 0 and comparator(data[rightChild], data[largestNode]) < 0 {
			largestNode := rightChild;
		}
		if largestNode != index {
			swap(index, largestNode);
			heapifyDown(largestNode);
		}
	}

	/** @private */
	action heapifyUp(integer index)
	{
		integer parent := parentOf(index);
		if index > 0 and comparator(data[index], data[parent]) < 0 {
			swap(index, parent);
			heapifyUp(parent);
		}
	}

	/** @private */
	action makeHeap()
	{
		integer lastNonLeaf := (data.size()/2)-1;
		while lastNonLeaf >= 0 {
			heapifyDown(lastNonLeaf);
			lastNonLeaf := lastNonLeaf - 1;
		}
	}

	/** @private */
	sequence<any> data;
	/** @private */
	action<any, any> returns integer comparator;
}