ds.arraybinarytree.test.h

#pragma once

#if YASI_TEST_THIS_MODULE != 1
#define YASI_TEST_THIS_MODULE  1
#endif
#include "ds.arraybinarytree.h"

namespace yasi{
	namespace ds{

		///
		/// Test IndexedBTNode
		///
		class IndexedBTNodeTest :public yasi::Test{
		protected:
			void init(){
				IndexedBTNode<int> n1;
				ASSERT_EQ(-1, n1._index) << "Default index should be -1";
				n1.setIndex(5);
				ASSERT_EQ(5, n1.index()) << "index should be 5";
				n1.setElement(7);
				ASSERT_EQ(7, n1.element) << "element should be 5";

				n1.makeNull();
				ASSERT_EQ(true, n1.isNull()) << "makeNull() and isNull() disagree";
			}
			void indexing(){
				const int N = 7;
				IndexedBTNode<int> n[N];
				for (int i = 0; i < N; i++){
					n[i].setIndex(i);
				}
				ASSERT_EQ(0, n[0].leftIndex()) << "left of 0 must be 0";
				ASSERT_EQ(1, n[0].rightIndex()) << "right of 0 must be 1";

				ASSERT_EQ(1, n[2].parentIndex()) << "parent of 2 must be 1";
				ASSERT_EQ(1, n[3].parentIndex()) << "parent of 3 must be 1";
				ASSERT_EQ(2, n[4].parentIndex()) << "parent of 4 must be 2";
				ASSERT_EQ(4, n[2].leftIndex()) << "left of 2 must be 4";
				ASSERT_EQ(5, n[2].rightIndex()) << "right of 2 must be 5";

			}
		};
		ADD_TEST_F(IndexedBTNodeTest, init);
		ADD_TEST_F(IndexedBTNodeTest, indexing);
		////////////// end testing IndexedBTNode

		///
		/// Test ArrayBinaryTree
		///
		class ArrayBinaryTreeTest : public yasi::Test{
		protected:
			typedef ArrayBinaryTree<int>::node_t node_t;
			typedef ArrayBinaryTree<int>::node_t* node_tptr;
		public:

			template<class E>
			static void checkElements(ArrayBinaryTree<E> *pBt, const E* pElemsArr, const int numElems){
				// finally, check array
				E *pTreeElems;
				int n;
				ArrayBinaryTree<E>& bt = *pBt; // must use reference, otherwise the tree will be destroyed upon exit
				bt.elements(&pTreeElems, n);
				ASSERT_EQ(n, numElems) << "actual array size " << n << " should equal target size " << numElems << endl
					<< "actual   : " << arrToString<E>(pTreeElems, n) << endl
					<< "expected: " << arrToString<E>(pElemsArr, n);

				ASSERT_EQ(true, arrcmp<E>(pTreeElems, pElemsArr, n)) << "elements array not right." << endl
					<< "actual   : " << arrToString<E>(pTreeElems, n) << endl
					<< "expected: " << arrToString<E>(pElemsArr, n);

				// done
				DELETE_ARR_SAFE(pTreeElems);
			}

			void constructor(){
				ArrayBinaryTree<int> bt;
				ASSERT_EQ(1, bt.ROOT_INDEX) << "Index of root is not 1";
				ASSERT_LE(bt.INIT_CAPACITY, bt._arr.capacity()) << "Initial _capacity must be <= containers capacity";
				ASSERT_LE((uint)2, bt._arr.capacity()) << "Initial capacity must be >= 2";
				ASSERT_EQ(0, bt.size()) << "Initial size is not zero";
				for (uint i = 0; i < bt._capacity; i++){
					ASSERT_EQ(0, bt._arr[i]) << "Pointer at index " << i << " is not initialized to NULL";
				}

				ASSERT_EQ(NULL, bt.root()) << "root should have been NULL";
			}

			void elements(){
				int srcArr[] = { 10, 20, 30, 40, 50, 60 };
				int n = ARR_LENGTH(srcArr);
				ArrayBinaryTree<int> bt(srcArr, n);

				int* pElemArr;
				int numElems;
				bt.elements(&pElemArr, numElems);
				ASSERT_EQ(n, numElems) << "number of elements is not " << n;
				for (int i = 0; i < numElems; i++){
					ASSERT_EQ(srcArr[i], pElemArr[i]) << "element mismatch at index " << i;
				}
				DELETE_ARR_SAFE(pElemArr);
			}

			void fromArr(){
				int srcArr[] = { 10, 20, 30, 40, 50, 60 };
				uint n = ARR_LENGTH(srcArr);
				ArrayBinaryTree<int> bt(srcArr, n);
				ASSERT_EQ(n, bt.size()) << "size of tree is not " << n;
				// check node-ptrs stored in internal container
				int i = 0;
				for (uint i = 0; i < bt._capacity; i++){
					if (i >= 1 && i <= n){
						// valid node-ptrs
						ASSERT_NE(0, (int)bt._arr[i]) << "Pointer NULL at index " << i;
						ASSERT_EQ(srcArr[i - 1], bt._arr[i]->element) << "array element mismatch for internal index " << i;
					}
					else{
						// invalid node-ptrs
						ASSERT_EQ(0, (int)bt._arr[i]) << "Pointer not NULL at index " << i;
					}
				}
				// also, use elements() method
				int* pElemArr;
				int numElems;
				bt.elements(&pElemArr, numElems);
				ASSERT_EQ(n, numElems) << "number of elements is not " << n;
				for (int i = 0; i < numElems; i++){
					ASSERT_EQ(srcArr[i], pElemArr[i]) << "element mismatch at index " << i;
				}
				DELETE_ARR_SAFE(pElemArr);
			}

			void isArrIndex(){
				ArrayBinaryTree<int> bt;
				ASSERT_EQ(false, bt.isArrIndex(-1)) << "Negative index is accepted";
				ASSERT_EQ(true, bt.isArrIndex(0)) << "0 index is rejected";
				ASSERT_EQ(true, bt.isArrIndex(bt._capacity - 1)) << "index (capacity - 1) is rejected";
				ASSERT_EQ(false, bt.isArrIndex(bt._capacity)) << "index beyond capacity is accepted";
			}

			void nodeAt(){
				ArrayBinaryTree<int> bt;
				bt.addRoot(5);

				bt.nodeAt(-1);

				ASSERT_EQ(0, (int)bt.nodeAt(-1)) << "Negative index is accepted";
				ASSERT_EQ(0, (int)bt.nodeAt(0)) << "Index 0 is accepted";
				ASSERT_EQ(0, (int)bt.nodeAt(bt._capacity)) << "Too large index is accepted";
				ASSERT_NE(0, (int)bt.nodeAt(1)) << "The root is not recognized";

				int e;
				bt.remove(bt.root(), e); // remove root
				ASSERT_EQ(0, (int)bt.nodeAt(1)) << "TreeNode accepted after deletion";
			}

			void nodeNotNull(){
				ArrayBinaryTree<int> bt;
				bt.addRoot(5);

				ASSERT_EQ(false, bt.nodeNotNull(-1)) << "Negative index is accepted";
				ASSERT_EQ(false, bt.nodeNotNull(0)) << "Zero index is accepted";
				ASSERT_EQ(false, bt.nodeNotNull(bt._capacity)) << "Too large index is accepted";
				ASSERT_EQ(true, bt.nodeNotNull(1)) << "The root is not recognized";

				int e;
				bt.remove(bt.root(), e); // remove root
				ASSERT_EQ(false, bt.nodeNotNull(1)) << "TreeNode accepted after deletion";
			}

			void addRoot(){
				ArrayBinaryTree<int> bt;
				ASSERT_EQ(0, bt.size());
				bt.addRoot(10);
				ASSERT_EQ(1, bt.size()) << "tree-size should have been 1";
				ASSERT_EQ(0, (int)bt.nodeAt(0)) << "As per Goodrich-Tamassia convention, first slot in the array should have been empty";
				ASSERT_EQ(10, bt.nodeAt(1)->element) << "Value at the root should have been 10";
				ASSERT_EQ(false, bt.isLeft(bt.root())) << "root cannot be a left child";
				ASSERT_EQ(false, bt.isRight(bt.root())) << "root cannot be a right child";
				ASSERT_EQ(false, bt.isInternal(bt.root())) << "root should have been external";
				ASSERT_EQ(false, bt.hasLeft(bt.root())) << "root does not have a left child";
				ASSERT_EQ(false, bt.hasRight(bt.root())) << "root does not have a right child";
			}

			void insertAt(){
				ArrayBinaryTree<int> bt;
				EXPECT_EQ(0, (int)bt.insertAt(4, -1)) << "inserting at negative index succeeded";
				EXPECT_EQ(0, (int)bt.insertAt(4, 0)) << "inserting at 0 index succeeded";
				EXPECT_NE(0, (int)bt.insertAt(4, 2 * bt._capacity)) << "inserting at too large index failed";
				ASSERT_NE(0, (int)bt.insertAt(4, 1)) << "inserting at index 1 failed";
				ASSERT_EQ(0, (int)bt.insertAt(4, 1)) << "inserting at an occupied index succeeded";
				bt.remove(bt.nodeAt(1));
				ASSERT_NE(0, (int)bt.insertAt(4, 1)) << "inserting at a recently deleted slot failed";
			}

			void replaceAt(){
				ArrayBinaryTree<int> bt;
				EXPECT_EQ(0, (int)bt.replaceAt(4, -1)) << "replacing at negative index succeeded";
				EXPECT_EQ(0, (int)bt.replaceAt(4, 0)) << "replacing at 0 index succeeded";
				EXPECT_EQ(0, (int)bt.replaceAt(4, 2 * bt._capacity)) << "replacing at too large index succeeded";
				ASSERT_EQ(0, (int)bt.replaceAt(4, 1)) << "replacing at unused index 1 succeeded";
				bt.addRoot(10);
				ASSERT_NE(0, (int)bt.replaceAt(4, 1)) << "replacing at occupied index 1 failed";
				int index = bt.root()->index();
				bt.remove(bt.root());
				ASSERT_EQ(0, (int)bt.replaceAt(4, index)) << "replacing at a recently deleted index succeeded";
			}

			void sibling(){
				ArrayBinaryTree<int> bt;
				ASSERT_EQ(0, (int)bt.sibling(bt.nodeAt(0))) << "sibling of NULL node succeeded";
				bt.addRoot(4);
				ASSERT_EQ(0, (int)bt.sibling(bt.root())) << "sibling of root node succeeded";
				ArrayBinaryTree<int>::node_t* n1 = bt.addLeft(5, bt.root());
				ASSERT_EQ(0, (int)bt.sibling(n1)) << "sibling of only-child succeeded";
				ArrayBinaryTree<int>::node_t* n2 = bt.addRight(5, bt.root());
				ASSERT_EQ(n2, bt.sibling(n1)) << "sibling of valid node failed";
				bt.remove(bt.left(bt.root())); // remove n1
				ASSERT_EQ(0, (int)bt.sibling(n2)) << "sibling of a deleted-sibling-node succeeded";

			}

			void resize(){
				int srcArr[] = { 10, 20, 30, 40, 50 };
				int n = ARR_LENGTH(srcArr);
				ArrayBinaryTree<int> bt(srcArr, n);
				int oldCapacity = bt._capacity;
				// copy current data
				// node_tptr is actually int (because it is a pointer)
				node_tptr* pOldArr = new node_tptr[oldCapacity];
				memcpy(pOldArr, (node_tptr*)bt._arr.data(), sizeof(node_tptr) * oldCapacity);

				bt.resize(2 * oldCapacity + 5, 0);
				int newCapacity = bt._capacity;
				const node_tptr* pNewArr = (node_tptr*)bt._arr.data();
				// all new slots must be initialized to zero
				for (int i = 0; i < newCapacity; i++){
					if (i < oldCapacity){
						// old slots
						ASSERT_EQ(pOldArr[i], pNewArr[i]) << "content mismatch at index " << i;
					}
					else{
						// new slots
						ASSERT_EQ(0, pNewArr[i]) << "new slots contain non-NULL pointer at index " << i;
					}
				}
				// done test
				DELETE_ARR_SAFE(pOldArr);
			}

			void toString(){
				int srcArr[] = { 10, 20, 30, 40, 50, 60, 70 };
				int n = ARR_LENGTH(srcArr);
				ArrayBinaryTree<int> bt(srcArr, n);
				// delete 50 and 60
				int e1, e2;
				bool ok = bt.remove(bt.nodeAt(5), e1);
				ASSERT_EQ(true, ok) << "falied to remove 50";
				ASSERT_EQ(50, e1) << "50 was not deleted";
				ok = bt.remove(bt.nodeAt(6), e2);
				ASSERT_EQ(true, ok) << "falied to remove 60";
				ASSERT_EQ(60, e2) << "60 was not deleted";

				// now print
				const char* sDelim = "|"; // need to be single-char for testing purpose
				const char* sEmptySlot = ""; // need to be empty for testing purpose
				string strBt = bt.toStringNodeArray(sDelim, sEmptySlot);
				// remove trailing single-char delimiters
				for (int i = strBt.length() - 1; strBt[i] == sDelim[0]; i--){
					strBt[i] = NULL;
				}
				strBt = string(strBt.c_str());
				// now strBt should equal "|10|20|30|40|||70"
				string strExpected = "|10|20|30|40|||70";
				ASSERT_EQ(strExpected, strBt) << "Expected " << strExpected << " but found " << strBt;


				bt.clear();
				bt.fromArray(srcArr, n);// 10 20 30 40 50 60 70
				/////////// preorder
				strBt = bt.toStringPreOrder();
				strBt = strPurge(strBt, "| ");
				strExpected = "10204050306070";
				ASSERT_EQ(strExpected, strBt) << "preorder mismatch";

				/////////// postorder
				strBt = bt.toStringPostOrder();
				strBt = strPurge(strBt, "| ");
				strExpected = "40502060703010";
				ASSERT_EQ(strExpected, strBt) << "postorder mismatch";

				/////////// inorder
				strBt = bt.toStringInOrder();
				strBt = strPurge(strBt, "| ");
				strExpected = "40205010603070";
				ASSERT_EQ(strExpected, strBt) << "inorder mismatch";


				/////////// BFSorder
				strBt = bt.toStringBFS();
				strBt = strPurge(strBt, "| ");
				strExpected = "10203040506070";
				ASSERT_EQ(strExpected, strBt) << "BFS order mismatch";
			}

			void remove(){
				int e;
				int srcArr[] = { 10, 20, 30, 40, 50, 60 };
				int n = ARR_LENGTH(srcArr);
				ArrayBinaryTree<int> bt(srcArr, n);
				{
					SCOPED_TRACE("tree arr before remove");
					checkElements(&bt, srcArr, n);
				}
				//bt.toString(&cBt);
				//DELETE_ARR_SAFE(cBt);


				bool ok = bt.remove(bt.nodeAt(0));
				ASSERT_EQ(false, ok) << "removing from index 0 succeeded";
				ok = bt.remove(bt.nodeAt(-1));
				ASSERT_EQ(false, ok) << "removing from negative index succeeded";

				//bt.toString(&cBt);
				//DELETE_ARR_SAFE(cBt);

				// removing the root will remove the entire tree
				ok = bt.remove(bt.root(), e); // 10
				ASSERT_EQ(true, ok) << "remove(root) failed";
				ASSERT_EQ(10, e) << "removed element should have been 10";
				ASSERT_EQ(0, bt.size()) << "Deleting subtree at root should make the size zero.";

				// remove a subtree
				bt.fromArray(srcArr, ARR_LENGTH(srcArr));
				// arr = { 10, 20, 30, 40, 50, 60 };
				ok = bt.remove(bt.left(bt.root()), e); // remove subtree 20
				ASSERT_EQ(true, ok) << "remove(20) failed";
				ASSERT_EQ(20, e) << "removed element should have been 20";
				ASSERT_EQ(ARR_LENGTH(srcArr) - 3, bt.size()) << "Remaining tree has improper size";
				{
					SCOPED_TRACE("remove(20)");
					int newArr[] = { 10, 30, 60 };
					checkElements(&bt, newArr, ARR_LENGTH(newArr));
				}
			}

			void removeNode(){
				int e;
				int srcArr[] = { 10, 20, 30, 40, 50, 60 };
				int n = ARR_LENGTH(srcArr);
				ArrayBinaryTree<int> bt(srcArr, n);
				{
					SCOPED_TRACE("tree arr before remove");
					checkElements(&bt, srcArr, n);
				}

				// remove a single node
				bool ok = bt.removeNode(bt.root(), e); // 10
				ASSERT_EQ(true, ok) << "remove(root) failed";
				ASSERT_EQ(10, e) << "removed element should have been 10";
				// arr = { ?, 20, 30, 40, 50, 60 };
				{
					SCOPED_TRACE("removeNode(10)");
					int newArr[] = { 20, 30, 40, 50, 60 };
					checkElements(&bt, newArr, 5);

					ASSERT_EQ(5, bt.size()) << "size of the tree should be 5";
					ASSERT_EQ(0, (int)bt.nodeAt(1)) << "the pointer at the deleted position must be NULL";
				}

				// remove another single node
				ok = bt.removeNode(bt.nodeAt(3), e); // 30
				ASSERT_EQ(true, ok) << "removeNode(30) failed";
				ASSERT_EQ(30, e) << "removed element should have been 30";
				// arr = { ?, 20, ?, 40, 50, 60 };
				{
					SCOPED_TRACE("removeNode(30)");
					int newArr[] = { 20, 40, 50, 60 };
					checkElements(&bt, newArr, 4);

					ASSERT_EQ(4, bt.size()) << "size of the tree should be 4";
					ASSERT_EQ(0, (int)bt.nodeAt(3)) << "the pointer at the deleted position must be NULL";
				}

			}

			void clear(){
				int srcArr[] = { 10, 20, 30, 40, 50, 60 };
				int n = ARR_LENGTH(srcArr);
				ArrayBinaryTree<int> bt(srcArr, n);
				bt.clear();
				ASSERT_EQ(0, bt.size()) << "size not 0";
				ASSERT_EQ(true, bt.empty()) << "tree not empty";
				ASSERT_EQ(NULL, bt.root()) << "root not NULL";

			}

			//void addElements(){
			//	ArrayBinaryTree<int> bt;
			//	bt.addRoot(10);
			//	bt.addLeft(20, bt.root());
			//	bt.addRight(30, bt.root());
			//	ASSERT_EQ(true, bt.isInternal(bt.root())) << "root should have been internal";
			//	ASSERT_EQ(true, bt.isExternal(bt.left(bt.root()))) << "root's left child should have been external";
			//	bt.addLeft(40, bt.left(bt.root()));
			//	ASSERT_EQ(false, bt.isExternal(bt.left(bt.root()))) << "root's left child should have been internal";
			//	bt.addRight(70, bt.right(bt.root()));
			//}
		};

		// create tests
		ADD_TEST_F(ArrayBinaryTreeTest, constructor);
		ADD_TEST_F(ArrayBinaryTreeTest, isArrIndex);
		ADD_TEST_F(ArrayBinaryTreeTest, nodeAt);
		ADD_TEST_F(ArrayBinaryTreeTest, nodeNotNull);
		ADD_TEST_F(ArrayBinaryTreeTest, addRoot);
		ADD_TEST_F(ArrayBinaryTreeTest, insertAt);
		ADD_TEST_F(ArrayBinaryTreeTest, replaceAt);
		ADD_TEST_F(ArrayBinaryTreeTest, remove);
		ADD_TEST_F(ArrayBinaryTreeTest, removeNode);
		ADD_TEST_F(ArrayBinaryTreeTest, sibling);
		ADD_TEST_F(ArrayBinaryTreeTest, elements);
		ADD_TEST_F(ArrayBinaryTreeTest, fromArr);
		ADD_TEST_F(ArrayBinaryTreeTest, resize);
		ADD_TEST_F(ArrayBinaryTreeTest, toString);
		ADD_TEST_F(ArrayBinaryTreeTest, clear);

	}
}