ds.binaryheap.h

#pragma once
#include "common.h"
#include "ds.arraybinarytree.h"
#include <assert.h>
#include <string>
#include <cstdlib>
#include "ds.aux.hastree.h"
#include "ds.kvpair.h"

using namespace std;

// enable-disable testing classes in this file
#include "test.this.module.h"

namespace yasi{

namespace ds{

	// the Heap interface
	template<class E, class Node> // E is the element class
	class IBinaryHeap {
		virtual bool heapify(const E* srcArr, const int numElems) = 0; // create a heap from an array; ; returns true on success/false on failure
		virtual const E& top() const = 0; // gives the top element; behavior undefined when heap empty
		virtual void pop() = 0; // gives the top element and removes it from the heap; behavior undefined when heap empty
		virtual void push(const E&) = 0; // adds an element to the heap
		virtual Node* insert(const E&) = 0; // adds an element to the heap; returns the pointer to the new node, or NULL on failure
		virtual int size() const = 0;
		virtual bool empty() const = 0;
	public:
		virtual ~IBinaryHeap(){};


	};

	// default min heap parent-child predicate
	// returns true if parent <= child
	// note: operator < and == must be defined/overloaded for template class E
template<class E>
class MinHeapParentChildPredicate{
public:
	MinHeapParentChildPredicate(){}
	bool operator() ( const E& parent, const E& child) const {
		return (parent <= child);
	}
	virtual ~MinHeapParentChildPredicate(){}
};
template<class E>
class MaxHeapParentChildPredicate{
public:
	MaxHeapParentChildPredicate(){}
	bool operator() (const E& parent, const E& child) const {
		return !(parent < child);
	}
	virtual ~MaxHeapParentChildPredicate(){}
};

template <class E>
class BinaryHeapBase :	public IBinaryHeap<E, IndexedBTNode<E> >,
						public virtual ds::aux::HasTree<ArrayBinaryTree<E> >{
public:
	BinaryHeapBase(){}
	virtual ~BinaryHeapBase(){}

};

//
// HeapParentChildPredicate will take two arguments of type E: parentElem and childElem, 
// and returns true if the parentElem is allowed to be the parent of childElem in the heap.
// This predicate defines the heap comparison, which is by default min-heap
//
template<class E, class HeapParentChildPredicate = MinHeapParentChildPredicate<E>  >
class BinaryHeap :	public BinaryHeapBase<E>{
	FRIEND_TEST_CLASS( BinaryHeapTest);
public:
	// public typedef
	typedef ArrayBinaryTree<E> Tree;
protected:
	Tree bt;
	typedef IndexedBTNode<E> node_t;
	typedef IndexedBTNode<E>* node_tptr;
	HeapParentChildPredicate lesseq; // the comparator predicate

	// This is the next insertion index
	int _insertIndex;
	bool _heapBad; // flag for corrupted heap
	E _defaultElement; // placeholder value for returning from methods


	// parent must be less than or equal to child
	bool heapPropertyParentChild(node_t* pParent, node_t* pChild){
		if (pParent != NULL && pChild != NULL)
			return lesseq(pParent->element, pChild->element);
		else
			return false;
	}

	int getRootIndex(){
		return bt.getRootIndex();
	}

	// swap the elements of two nodes
	// todo: is it possible to optimize the swap?
	void swapElements(node_t* p1, node_t* p2){
		if (p1 && p2){
			E e1 = p1->element;
			p1->setElement(p2->element);
			p2->setElement(e1);
		}
	}

	// selects the appropriate child for bubble down
	// checks heap property among parent, left, right nodes
	// if no child is appropriate (or pNode is external/NULL), returns NULL
	node_t* selectChildForBubbleDown(node_t* pNode){
		node_t	*pChild = NULL;
		if (pNode != NULL && bt.isInternal(pNode)){

			node_t	*pLeft = bt.left(pNode), 
					*pRight = bt.right(pNode);

			// if pNode has only one child, select it if it violates heap property
			if (pLeft == NULL && pRight != NULL && 
				!heapPropertyParentChild(pNode, pRight)) {
				pChild = pRight;
			}
			else if (pRight == NULL && pLeft != NULL &&
				!heapPropertyParentChild(pNode, pLeft) ) {
				pChild = pLeft;
			}
			else{
				// both non-null
				// find the smaller element among left and right
				if (heapPropertyParentChild(pLeft, pRight)){
					// left <= right
					pChild = pLeft;
				}
				else{
					// left > right
					pChild = pRight;
				}
				// note that if left == right, left is selected

				// check heap property with parent
				if (heapPropertyParentChild(pNode, pChild)){
					// no need to bubble down
					pChild = NULL;
				}
				else{
					// should bubble down through pChild already selected
				}
			}
		}
		return pChild;
	}

	// propagate a node up until the heap property is satisfied
	void bubbleUp(node_t* pNode){
		if (pNode != NULL){
			if (pNode == bt.root()) return; // root; done

			node_t* pParent = bt.parent(pNode); // get parent
			while ( pParent && pNode && !heapPropertyParentChild(pParent, pNode)){ // check heap property
				swapElements(pParent, pNode); // swap because heap property violated
				// prepare for next level
				pNode = pParent;
				pParent = bt.parent(pParent);
			}
		}
	}

	// propagate a node down until the heap property is satisfied
	void bubbleDown(node_t* pNode){
		if (pNode != NULL && bt.isInternal(pNode)){
			// find the child with largest discrepancy
			node_t *pChild = selectChildForBubbleDown(pNode);
			if(pChild != NULL){
				// found appropriate child for bubble down
				swapElements(pNode, pChild);
				bubbleDown(pChild);
			}
		}
	}

	// forcefully sets the elements in the tree
	// heap-property and size property is ignored
	void setTree(const E* pElems, const int numElems){
		bt.clear(); // clear the tree
		bt.fromArray(pElems, numElems); // build the tree
		_insertIndex = size() + 1; // prepare for add/remove
	}

public:
	// to be used by client code to refer to the output of push()
	typedef node_t HeapNode;

	BinaryHeap(): _heapBad(false){
	}
	BinaryHeap(const E* pArr, const int numElems) : _heapBad(false){
		heapify(pArr, numElems);
	}
	virtual ~BinaryHeap(){
		clear();
	}

	// pure virtual method from HasTree class
	const Tree& tree() const{ return bt; }



	bool corrupted(){
		return _heapBad;
	}

	void clear(){
		bt.clear();
		_insertIndex = bt.getRootIndex();
		_heapBad = false;
	}

	void reset(){
		bt.reset();
		_insertIndex = bt.getRootIndex();
		_heapBad = false;
	}

	/// public interface
	// create a heap from an array
	bool heapify(const E* pArr, const int numElems) {
		if (pArr != NULL && numElems > 0){
			if (!empty())
				reset(); // clear current data and prepare for adding nodes

			for (int i = 0; i < numElems; i++){
				if (insert(pArr[i]) == NULL){
					_heapBad = true;
					return false;
				}
			}
			return true;
		}
		return false;
	}



	// returns the top element
	const E& top()const override {
		if (size() > 0){
			return bt.root()->element;
		}
		else
			return _defaultElement;
	}

	// returns the top element and removes it from the heap
	void pop() override
	{
		if (size() <= 0) return;
		else{
			if (size() == 1){
				assert(bt.remove(bt.root()) == true); // // remove the only node
				_insertIndex--;
			}
			else {
				node_t* pNode = bt.nodeAt(_insertIndex - 1); // most recently added node
				assert(pNode != NULL);

				swapElements(bt.root(), pNode); // swap element with root
				assert(bt.remove(pNode) == true); // remove the most recently added node
				bubbleDown(bt.root());
				_insertIndex--; // the last node at last level is deleted
			}
		}
	}


	// adds an element to the heap
	// returns the pointer to the node
	node_t* insert(const E& e) {
		node_t* pNode = NULL;
		if (bt.empty()){
			pNode = bt.addRoot(e);
			if ( pNode != NULL){
				this->_insertIndex = pNode->index() + 1;
			}
		}
		else{
			// insert the new node at appropriate index
			pNode = bt.insertAt(e, _insertIndex);
			if (pNode != NULL){
				// insertion ok
				_insertIndex++;
				// fix the heap
				bubbleUp(pNode);
			}
		}
		return pNode;
	}

	void push(const E& e) override{
		assert(insert(e) != NULL);
	}

	int size() const override{
		return bt.size();
	}
	bool empty() const override{
		return bt.empty();
	}
	// gives a string represenation of the heap
	string toString(){
		return bt.toStringBFS();
	}
};

	// a custom binary tree comparator
	// treeA <= treeB if treeB/treeA not empty and 
	//		treeA.root()->element <= treeB.root()->element
	template<class E>
	class TreeComparisonPredicate{
		typedef ArrayBinaryTree<E> Tree;
	public:
		bool operator() (const Tree* pParent, const Tree* pChild) const{
			typedef ArrayBinaryTree<E>::Node Node;
			if (!pChild->empty() && !pParent->empty()){
				Node* pParentRoot = pParent->root();
				Node* pChildRoot = pChild->root();
				const E& pe = pParentRoot->element;
				const E& ce = pChildRoot->element;
				return pe <= ce;
			}
			else
				return false;
		}
	};

	// max-heap of numeric strings
	class NumericStringMaxHeapPredicate{
	public:
		bool operator() (const string& parent, const string& child) const{
			int p = atoi(parent.c_str()),
				c = atoi(child.c_str());
			return p >= c;
		}
	};




} // namespace yasi.ds
} // namespace yasi