#include <algorithm>
#include <ctime>
#include <set>
#include <cmath>
#include <iostream>
#include <vector>

template <class Type> class ExponentialTree {
	public:
		ExponentialTree() { root = NULL; }
		~ExponentialTree() { deleteNode(root); }

		bool contains(Type value) {
			for(node *curr = root; curr != NULL;) {
				size_t i;
				for (i = 0; i < curr->values.size(); i++) {
					if (curr->values[i] == 0) return true;
					else if (curr->values[i] < 0) break;
				}
				curr = curr->children == NULL ? NULL : curr->children[i];
			}

			return false;
		}

		// Inserts a value (iff unique)
		void insert(Type value) {
			return insert(root, value, 1);
		}

		size_t find(std::vector<Type>& values, Type value) {
			for(std::vector<size_t>::size_type i = 0; i < values.size(); i++)
				if (value < values[i])
					return i;

			return values.size();
		}

	private:
		struct node {
			size_t depth;
			std::vector<Type> values;
			node **children;
		};

		node *root;

		void insert(node *& root, Type value, size_t depth) {
			if (root == NULL) {
				root = new node;
				root->depth = depth;
				root->values.push_back(value);
				root->children = NULL;
				return;
			}

			size_t insertionPoint = find(root->values, value);
			if (root->values.size() < root->depth) {
				//root->values.insertAt(insertionPoint, value);
				root->values.insert(root->values.begin()+insertionPoint, value);
				return;
			}

			if (root->children == NULL) {
				root->children = new node *[depth + 1];
				for (size_t i = 0; i <= depth; i++)
					root->children[i] = NULL;
			}

			insert(root->children[insertionPoint], value, depth + 1);
		}

		void deleteNode(node *root) {
			if (root == NULL) return;
			if (root->children != NULL) {
				for (size_t i = 0; i <= root->depth; i++)
					deleteNode(root->children[i]);

				delete[] root->children;
			}

			delete root;
		}
};

size_t exponentialTree(std::vector<size_t>);
size_t redBlackTree(std::vector<size_t>);

std::vector<size_t> testData(size_t);

int main(void) {
	size_t iterations = pow(2,pow(2,pow(2,2)));//UINT_MAX/21;
	std::cout << "Trying with " << iterations << " values" << std::endl;

	std::vector<size_t> vectorOfTest=testData(iterations);
	clock_t before=clock();

	std::cout << "\n**Exponential tree**\n";
	std::cout << "Successfully added and retrieved " << exponentialTree(vectorOfTest) << " elements";
	std::cout << " in " << difftime(clock(), before) << " milliseconds" << std::endl;

	before=clock();

	std::cout << "\n**Red/Black tree**\n";
	std::cout << "Successfully added and retrieved " << redBlackTree(vectorOfTest) << " elements";
	std::cout << " in " << difftime(clock(), before) << " milliseconds" << std::endl;

	std::cin.get();
}

std::vector<size_t> testData(size_t iterations) {
	std::vector<size_t> treeVector;

	for (size_t i=0; i<iterations; i++)
		treeVector.push_back(i);

	std::cout << "Randomly shuffling the " << treeVector.size() << " elements." << std::endl;

	std::random_shuffle(treeVector.begin(), treeVector.end());

	return treeVector;
}

size_t exponentialTree(std::vector<size_t> inputVector) {
	ExponentialTree<size_t> tree;

	for(std::vector<size_t>::size_type i = 0; i < inputVector.size(); i++)
		tree.insert(inputVector[i]);

	std::cout << "\nShuffled numbers successfully added into our Exponential Tree." << std::endl;

	size_t numtreeVector = 0;

	for(std::vector<size_t>::size_type i = 0; i < inputVector.size(); i++) {
		if (tree.contains(inputVector[i])) {
			std::cout << "FAILURE: The ExponentialTree should include: " << i << std::endl;
			break;
		}
		numtreeVector++;
	}

	return numtreeVector;
}

size_t redBlackTree(std::vector<size_t> inputVector) {
	std::set<size_t> redBlackTree;

	for(std::vector<size_t>::size_type i = 0; i < inputVector.size(); i++)
		redBlackTree.insert(inputVector[i]);

	std::cout << "\nShuffled numbers successfully added into our Red/Black Tree." << std::endl;

	size_t numtreeVector = 0;
	for(std::vector<size_t>::size_type i = 0; i < inputVector.size(); i++) {
		if(redBlackTree.find(inputVector[i])==redBlackTree.end()) {
			std::cout << "\nFAILURE: The Red/Black tree should include: " << i << std::endl;
			break;
		}
		numtreeVector++;
	}

	return numtreeVector;
}