ds.arraybinarytree.h

#pragma once
#include "common.h"
#include <vector>
#include "utils.h"
#include "ds.tree.h"
#include "ds.binarytree.h"
#include "ds.binarytreebase.h"
#include <iostream>
#include <typeinfo>

using namespace std;

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

namespace yasi{
	namespace ds{

		///// abstract class
		//template<class E>
		//class BinaryTreeNode : public TreeNode < E > {
		//public:
		//	virtual BinaryTreeNode left() = 0;
		//	virtual BinaryTreeNode right() = 0;
		//	virtual BinaryTreeNode parent() = 0;
		//};


		class IArrayBinaryTreeNode{
		public:
			virtual ~IArrayBinaryTreeNode(){}
			virtual int index() const = 0;
			virtual void setIndex(int) = 0;
			virtual int leftIndex() const = 0;
			virtual int rightIndex() const = 0;
			virtual int parentIndex() const = 0;
		};


		template<class E>
		class IndexedBTNode :	public virtual IArrayBinaryTreeNode, 
								public virtual TreeNode<E> {
			FRIEND_TEST_CLASS( IndexedBTNodeTest); // enable testing
		protected:
			int _index; /// -1 by default
			const int NULL_INDEX; // marks whether a node is empty/invalid
		public:
			IndexedBTNode() : TreeNode<E>(), NULL_INDEX(-1) {
				_index = NULL_INDEX;
			}
			IndexedBTNode(const E& e) : TreeNode<E>(e), NULL_INDEX(-1){
				_index = NULL_INDEX;
			}
			IndexedBTNode(const E& e, int index) : TreeNode<E>(e), NULL_INDEX(-1){
				_index = index;
			}
			void setIndex(int index) override{
				_index = index;
			}
			int index() const override{
				return _index;
			}
			int leftIndex() const override{
				return (_index << 1);
			}
			int rightIndex() const override{
				return (_index << 1) + 1;
			}
			int parentIndex() const override{
				return _index >> 1;
			}

			// check if this node is marked as null
			bool isNull(){
				return _index == NULL_INDEX;
			}
			void makeNull(){
				_index = NULL_INDEX;
			}
			virtual ~IndexedBTNode(){

			}
		};

		// interface for ArrayBinaryTree
		template<class E, class Node>
		class IArrayBinaryTree : public virtual IBinaryTree < E, Node > {
		public:
			virtual ~IArrayBinaryTree(){}
			virtual void fromArray(const E*, const int) = 0;
			virtual int getRootIndex() const = 0;
			virtual Node* nodeAt(int) const = 0;
			virtual Node* insertAt(const E& e, int) = 0;
		};


		// nodes are internally kept in an array (vector, actually)
		// the 0 index is always empty to facilitate easy parent-child indexing.
		// thus the root is stored at index 1
		// it does not yet implement the IArrayBinaryTree interface
		template<class E>
		class ArrayBinaryTree : public virtual IArrayBinaryTree<E, IndexedBTNode<E> >,
								public virtual BinaryTreeBase<E, IndexedBTNode<E>>{
			///////////// enable testing ////////////////
			FRIEND_TEST_CLASS(ArrayBinaryTreeTest);
			FRIEND_TEST_CLASS(BinaryHeapTest);

			typedef IndexedBTNode<E> node_t;
			const int ROOT_INDEX = 1; // for quick parent-child indexing, 1 instead of 0

			// the underlying container
			const uint INIT_CAPACITY = 2; // initial size of the array
			const float LOAD_FACTOR = 2; // how much the array size increases at each resize

			// do not initialize _capacity and _size here; let constructors do that
			uint _capacity; // current length of the array, not necessarily the same as the capacity of a vector (due to automatic resizing)
			uint _size; // the actual size of the tree, always <= _capacity.

			// the vector
			vector< node_t* > _arr; // the array of pointers to nodes

			// returns true if 0 <= index < capacity
			bool isArrIndex(uint k) const{
				return k >= 0 && k < _capacity;
			}
			// returns true if the node-ptr at index is not null 
			bool nodeNotNull(int k) const{
				return nodeAt(k) != NULL;
			}
			// returns the content at the index of the vector
			// the return value can be NULL

			// replaces the element of a valid node at an occupied index
			node_t* replaceAt(E e, int index){
				node_t* pNode = NULL;
				if (nodeNotNull(index)){
					// the index contains non-null node
					pNode = _arr[index]; // find node
					pNode->setElement(e); // update value
				}
				return pNode;
			}

			////////////////// has bugs, incomplete
			//E _pullSubtreeUp(node_t* pFrom, node_t* pTo, bool bRemoveWriteSubtree = 1){
			//	if (nodeNotNull(pFrom) && nodeNotNull(pTo)){
			//		E eRet = pTo->element; // the return value
			//		// now make two cursors: one to read and one to write
			//		node_t *pRead = pFrom, *pWrite = pTo;
			//		// first, delete the existing subtree at pTo
			//		// this eliminates issues stemming from size-difference between two subtrees
			//		while (nodeNotNull(pRead) && nodeNotNull(pWrite)){
			//			// copy element from read to write
			//			pWrite->setElement(pRead->element);
			//			// copy left subtree of pRead
			//			if (hasLeft(pRead) && !hasLeft(pWrite) ){
			//				// pWrite does not have a left child
			//				// create a new left node
			//				addLeft(pRead->element, pWrite);
			//			}
			//			if (hasLeft(pRead)){
			//				// now recursive to the left
			//				_pullSubtreeUp(left(pRead), left(pWrite), 0); // no need to delete the write subtree again
			//			}
			//			// copy right subtree of pRead
			//			if (hasRight(pRead) && !hasRight(pWrite)){
			//				// pWrite does not have a right child
			//				// create a new right node
			//				addRight(pRead->element, pWrite);
			//			}
			//			if (hasRight(pRead)){
			//				// now recursive to the right
			//				_pullSubtreeUp(right(pRead), right(pWrite), 0); // no need to delete the write subtree again
			//			}
			//		}
			//		// finally, delete the the source subtree
			//		remove(pFrom);
			//	}
			//}


			// creates the actual container and fills with NULL pointers
			void initArr(const int capacity){
				_capacity = capacity;
				_size = 0;
				_arr = vector<node_t*>(capacity, 0);
				for (int i = 0; i < capacity; i++){
					_arr.push_back(0); // fill the vector with NULL pointers
				}

			}
			// increases the size of the array
			// initializes new slots with NULL pointer
			void resize(int newSize, node_t* initValue = 0){
				uint i = _capacity; // old capacity
				_arr.resize(newSize, initValue);
				_capacity = _arr.capacity() - 1; // new capacity; one less than vector-capacity to possibly stop auto-resize
				while (i < _capacity){
					_arr.push_back(0); // fill the unused slots with NULL
					i = i + 1;
				}
			}
		protected:
			typedef ArrayBinaryTree<E> self;
		public:
			typedef node_t Node;

			// initial size is zero, capacity is INIT_CAPACITY
			// all slots of the array is filled with 0
			ArrayBinaryTree() : _size(0), _capacity(INIT_CAPACITY){
				initArr(INIT_CAPACITY);
			}

			// construct a binary tree from a given array
			ArrayBinaryTree(const E* pSrcArr, const unsigned int arrSize) : _capacity(0), _size(0){
				fromArray(pSrcArr, arrSize);
			}

			// copy constructor
			ArrayBinaryTree(const self& other){
				*this = other;
			}

			// construct a binary tree from a given array
			void fromArray(const E* pSrcArr, const int arrSize){
				if (arrSize <= 0) {
					cout << "Argument arrSize is negative" << endl;
					initArr(INIT_CAPACITY);
				}
				else{
					// either _arr is initialized, or not
					// if it is, we need to clear it first
					if (_capacity != 0){ // initialized
						clear();
					}
					// create array
					initArr(arrSize + 1); // +1 for the unused 0-index slot
					// insert elements into array
					for (int i = 1; i < arrSize + 1; i++){
						E e = pSrcArr[i - 1];
						insertAt(e, i);
					}
				}
			}

			// returns true if the node-ptr at index is not null 
			inline bool nodeNotNull(const node_t* pNode) const override{
				return pNode != NULL && nodeAt(pNode->index()) != NULL;
			}

			self& operator=(const self& other){
				this->_arr = other._arr;
				this->_capacity = other._capacity;
				this->_size = other._size;
				return *this;
			}


			///////////// done but needs test/reason-for-existence
			////
			//// sets the param "pDestArr" with a dynamically-allocated array of elements; the order is the same as that in the internal array
			//// also sets the param "numElems" with the number of elements in the array
			//// the param "emptyElem" is used to denote empty slots in the internal array
			//// elements in "pDestArr" maintains the tree-structure
			//bool toArray(E* pDestArr, int& numElems, E nullElem){
			//	numElems = 0;
			//	E* pRawArr = new E[_capacity];
			//
			//	int countElems = 0; // how many elements touched
			//	for (int i = 0; i < _capacity && countElems < _size; i++){ // discard the index 0
			//		node_t* pNode = nodeAt(i);
			//		if (pNode == NULL){
			//			pRawArr[i] = nullElem;
			//		}
			//		else{
			//			pRawArr[i] = pNode->element;
			//			countElems++;
			//		}
			//		numElems++;
			//	}
			//	if (countElems == _size){
			//		// good
			//		pDestArr = new E[numElems];
			//		for (int i = 0; i < numElems; i++){
			//			pDestArr[i] = pRawArr[i];
			//		}
			//		DELETE_ARR_SAFE(pRawArr);
			//		return true;
			//	}
			//	else 
			//		return false;
			//}


			/////////// done but needs test/reason-for-existence
			//
			// sets the param "*ppDestArr" with a dynamically-allocated array of elements; the order is the same as that in the internal array
			// also sets the param "numElems" with the number of elements in the array
			// the param "emptyElem" is used to denote empty slots in the internal array
			//
			// Caution: elements in "*ppDestArr" DOES NOT MAINTAIN the tree-structure
			bool elements(E** ppDestArr, int& numElems){
				numElems = _size;
				*ppDestArr = new E[_size];
				E* pDestArr = *ppDestArr;

				uint countElems = 0; // how many elements touched
				for (uint i = 1; i < _capacity && countElems < _size; i++){ // discard the index 0
					node_t* pNode = nodeAt(i);
					if (pNode != NULL){
						pDestArr[countElems] = pNode->element;
						countElems++;
					}
				}
				if (countElems == _size){
					// good
					return true;
				}
				else
					return false;
			}
			void reset(){
				clear();
				initArr(INIT_CAPACITY);
			}
			void clear(){
				// delete each pointer contained in the vector
				for (uint i = 0; i < _capacity && i < _arr.size(); i++){
					DELETE_SAFE(_arr[i]);
				}

				// clear the vector
				_arr.clear();

				// clean the slate
				_size = 0;
				_capacity = INIT_CAPACITY;
			}

			///////////////////////////////////////////////
			////////////// Interface IArrayBinaryTree /////
			///////////////////////////////////////////////
			int getRootIndex() const override{
				return ROOT_INDEX;
			}
			node_t* nodeAt(int k) const override{
				if (isArrIndex(k)){
					return _arr[k];
				}
				else
					return NULL;
			}
			// master method for inserting new items
			// caution: 
			//	(1) inserts at arbitrary unoccupied index, increasing the capacity when the index is too large
			//	(2) cannot insert at zero index
			//	(3) does not check parent/child relationship; the node can be possibly without a parent
			//	(4) if a too large index is specified, runs the risk of memory allocation error
			// dynamically allocates a new node; increases the tree-size by one
			// returns the node-ptr on success, NULL on failure
			node_t* insertAt(const E& e, int index) override{
				node_t* pNode = NULL;
				if (index <= 0) {
					// cannot insert at negative or zero index
					return NULL;
				}
				else{
					while ((uint) index >= _capacity){
						// need to increase capacity
						_capacity = (int)(_capacity * LOAD_FACTOR);
						_arr.resize(_capacity, 0); // newly added values are zero
					}

					// now insert into desired position. it must be unoccupied
					if (isArrIndex(index) && !nodeNotNull(index)){
						pNode = new node_t(e, index); // dynamic allocation of the node object. Must delete later.
						_arr[index] = pNode; // put in the array
						_size++; // increment size
					}
				}
				return pNode;
			}


			///////////////////////////////////////////////
			////////////// Interface ITree ////////////////
			///////////////////////////////////////////////
			bool empty() const override{
				return _size == 0; // because we are keeping the first slot empty
			}
			int size() const override{
				return _size; // because we are keeping the first slot empty
			}
			virtual node_t* root() const  {
				if (empty()) 
					return NULL;
				else 
					return nodeAt(ROOT_INDEX);
			}
			// removes the subtree rooted at a node and discards the element stored at that node.
			// returns false if any error occurs, true otherwise
			bool remove(node_t* pNode)override{
				E temp;
				return remove(pNode, temp);
			}

			// removes the subtree rooted at a node and saves the value at that node at the output argument e.
			// returns false if any error occurs, true otherwise
			bool remove(node_t* pNode, E& e) override{ // e is output param
				if (pNode != NULL && nodeNotNull(pNode->index())){
					bool success = true;
					e = pNode->element;
					E temp;
					if (hasLeft(pNode)){
						success = remove(left(pNode), temp);
					}
					if (hasRight(pNode)){
						success &= remove(right(pNode), temp);
					}
					// subtree deleted
					_arr[pNode->index()] = 0; // mark the slot as empty
					DELETE_SAFE(pNode); // delete the allocated memory

					_size--; // size decreases
					return success;
				}
				else
					return false;
			}

			bool removeNode(node_t* pNode)override {
				E temp;
				return removeNode(pNode, temp);
			}

			// removes a node and saves the value at that node at the output argument e.
			// caution: this may leave the tree broken
			// returns false if any error occurs, true otherwise
			bool removeNode(node_t* pNode, E& e) override{ // e is output param
				if (pNode != NULL && nodeNotNull(pNode->index())){
					e = pNode->element;
					_arr[pNode->index()] = 0; // mark the slot as empty
					DELETE_SAFE(pNode); // delete the allocated memory

					_size--; // size decreases
					return true;
				}
				else
					return false;
			}
			bool isRoot(const node_t* pNode) const override{
				return (pNode != NULL) &&
					pNode->index() == ROOT_INDEX &&
					parent(pNode) == NULL;
			}

			// succeeds if the tree is empty
			// otherwise, returns NULL
			node_t* addRoot(const E& e) override{
				if (root() == NULL){
					// no root
					return insertAt(e, ROOT_INDEX);
				}
				else
					return NULL;
			}


			// prints out the nodes in level order
			string toString() const override{
				return this->toStringNodeArray("|", "");
			}
			string toStringNodeArray() const {
				return this->toStringNodeArray("|", "");
			}
			string toStringNodeArray(const char* strDelim, const char* strEmptySlot) const{
				// cout << endl << "ArrayBinaryTree contents:" << endl;
				std::stringstream buffer;
				for (uint i = 0; i < _capacity; i++){
					if (_arr[i] == NULL){
						// print empty slots
						buffer << strEmptySlot;
					}
					else{
						buffer << _arr[i]->element;
					}
					// don't print the last delim
					//if (i < _capacity - 1){
						buffer << strDelim;
					//}
				}
				// done
				return buffer.str();
			}

			///////////////////////////////////////////////
			/////////// Interface IBinaryTree /////////////
			///////////////////////////////////////////////
			node_t* parent(const node_t* pNode)  const override{
				return nodeAt(pNode->parentIndex());
			}
			node_t* left(const node_t* pNode)  const override{
				return nodeAt(pNode->leftIndex());
			}
			node_t* right(const node_t* pNode) const override{
				return nodeAt(pNode->rightIndex());
			}
			// returns the sibling of a node; 
			// the return value wll be null if no sibling
			node_t* addLeft(const E& e, node_t* pParent) override{
				return insertAt(e, pParent->leftIndex());
			}
			node_t* addRight(const E& e, node_t* pParent) override{
				return insertAt(e, pParent->rightIndex());
			}


			//////////////////// buggy and incomplete
			//// removes a node having zero or one child; the child, if exists, is not deleted 
			//// the child becomes a child of the parent of the deleted node
			//// returns the value at the deleted node.
			//// throws exception E_NODE_NOT_FOUND if the node is bad
			//// throws exception E_BAD_NODE if the node has both children
			//E removeAndLink(node_t* pNode){
			//	if (nodeNotNull(pNode)){
			//		if (numChildren(pNode) != 2){
			//			E e = pNode->element;
			//			if (isRoot(pNode)){
			//				// we are removing the root
			//				/////// todo: pullup entire subtree
			//			}
			//			else{
			//				// removing non-root node
			//				node_t* pParent = parent(pNode);
			//				// it is easy if the node is external
			//				if (isExternal(pNode)){
			//					// deleting external node
			//					if (isLeft(pNode)){
			//						_arr[pParent->leftIndex] = NULL;
			//					}
			//					else{
			//						_arr[pParent->rightIndex] = NULL;
			//					}
			//				}
			//				else{
			//					// deleting internal node
			//					node_t* pChild = hasLeft(pNode)
			//						? left(pNode)
			//						: right(pNode);
			//					// connect child and grand-parent
			//					///////// todo: pull-up entire subtree
			//				}
			//			}
			//			// ok
			//			DELETE_SAFE(pNode); // manually free-up the memory
			//			_size--; // update size
			//			// done
			//			return e;
			//		}
			//		else{
			//			throw E_BAD_NODE;
			//		}
			//	}
			//	else throw E_NODE_NOT_FOUND;
			//}



			virtual ~ArrayBinaryTree(){
				this->clear();
			}

			// returns the string-representation of the internal arr in the param "*pcStr"
			// the memory for "*pcStr" is allocated dynamically, which must be deleted later

			template<class E>
			bool operator==(const ArrayBinaryTree<E>& other) const{
				return this->size() == other.size() &&
					this->toStringBFS() == other.toStringBFS();
			}
			template<class E>
			bool operator!=(const ArrayBinaryTree<E>& other) const{
				return !(*this == other);
			}

		};

		// for printing purpose only
		// prints the BFS representation of the tree
		template<class E>
		ostream& operator << (ostream& out, const ArrayBinaryTree<E>& t){
			out << t.toStringBFS();
			return out;
		}


	}
}