fork(1) download
copy 
  1. #include <algorithm>
  2. #include <ctime>
  3. #include <set>
  4. #include <cmath>
  5. #include <iostream>
  6. #include <vector>
  7.  
  8. template <class Type> class ExponentialTree {
  9. 	public:
  10. 		ExponentialTree() { root = NULL; }
  11. 		~ExponentialTree() { deleteNode(root); }
  12.  
  13. 		bool contains(Type value) {
  14. 			for(node *curr = root; curr != NULL;) {
  15. 				size_t i;
  16. 				for (i = 0; i < curr->values.size(); i++) {
  17. 					if (curr->values[i] == 0) return true;
  18. 					else if (curr->values[i] < 0) break;
  19. 				}
  20. 				curr = curr->children == NULL ? NULL : curr->children[i];
  21. 			}
  22.  
  23. 			return false;
  24. 		}
  25.  
  26. 		// Inserts a value (iff unique)
  27. 		void insert(Type value) {
  28. 			return insert(root, value, 1);
  29. 		}
  30.  
  31. 		size_t find(std::vector<Type>& values, Type value) {
  32. 			for(std::vector<size_t>::size_type i = 0; i < values.size(); i++)
  33. 				if (value < values[i])
  34. 					return i;
  35.  
  36. 			return values.size();
  37. 		}
  38.  
  39. 	private:
  40. 		struct node {
  41. 			size_t depth;
  42. 			std::vector<Type> values;
  43. 			node **children;
  44. 		};
  45.  
  46. 		node *root;
  47.  
  48. 		void insert(node *& root, Type value, size_t depth) {
  49. 			if (root == NULL) {
  50. 				root = new node;
  51. 				root->depth = depth;
  52. 				root->values.push_back(value);
  53. 				root->children = NULL;
  54. 				return;
  55. 			}
  56.  
  57. 			size_t insertionPoint = find(root->values, value);
  58. 			if (root->values.size() < root->depth) {
  59. 				//root->values.insertAt(insertionPoint, value);
  60. 				root->values.insert(root->values.begin()+insertionPoint, value);
  61. 				return;
  62. 			}
  63.  
  64. 			if (root->children == NULL) {
  65. 				root->children = new node *[depth + 1];
  66. 				for (size_t i = 0; i <= depth; i++)
  67. 					root->children[i] = NULL;
  68. 			}
  69.  
  70. 			insert(root->children[insertionPoint], value, depth + 1);
  71. 		}
  72.  
  73. 		void deleteNode(node *root) {
  74. 			if (root == NULL) return;
  75. 			if (root->children != NULL) {
  76. 				for (size_t i = 0; i <= root->depth; i++)
  77. 					deleteNode(root->children[i]);
  78.  
  79. 				delete[] root->children;
  80. 			}
  81.  
  82. 			delete root;
  83. 		}
  84. };
  85.  
  86. size_t exponentialTree(std::vector<size_t>);
  87. size_t redBlackTree(std::vector<size_t>);
  88.  
  89. std::vector<size_t> testData(size_t);
  90.  
  91. int main(void) {
  92. 	size_t iterations = pow(2,pow(2,pow(2,2)));//UINT_MAX/21;
  93. 	std::cout << "Trying with " << iterations << " values" << std::endl;
  94.  
  95. 	std::vector<size_t> vectorOfTest=testData(iterations);
  96. 	clock_t before=clock();
  97.  
  98. 	std::cout << "\n**Exponential tree**\n";
  99. 	std::cout << "Successfully added and retrieved " << exponentialTree(vectorOfTest) << " elements";
  100. 	std::cout << " in " << difftime(clock(), before) << " milliseconds" << std::endl;
  101.  
  102. 	before=clock();
  103.  
  104. 	std::cout << "\n**Red/Black tree**\n";
  105. 	std::cout << "Successfully added and retrieved " << redBlackTree(vectorOfTest) << " elements";
  106. 	std::cout << " in " << difftime(clock(), before) << " milliseconds" << std::endl;
  107.  
  108. 	std::cin.get();
  109. }
  110.  
  111. std::vector<size_t> testData(size_t iterations) {
  112. 	std::vector<size_t> treeVector;
  113.  
  114. 	for (size_t i=0; i<iterations; i++)
  115. 		treeVector.push_back(i);
  116.  
  117. 	std::cout << "Randomly shuffling the " << treeVector.size() << " elements." << std::endl;
  118.  
  119. 	std::random_shuffle(treeVector.begin(), treeVector.end());
  120.  
  121. 	return treeVector;
  122. }
  123.  
  124. size_t exponentialTree(std::vector<size_t> inputVector) {
  125. 	ExponentialTree<size_t> tree;
  126.  
  127. 	for(std::vector<size_t>::size_type i = 0; i < inputVector.size(); i++)
  128. 		tree.insert(inputVector[i]);
  129.  
  130. 	std::cout << "\nShuffled numbers successfully added into our Exponential Tree." << std::endl;
  131.  
  132. 	size_t numtreeVector = 0;
  133.  
  134. 	for(std::vector<size_t>::size_type i = 0; i < inputVector.size(); i++) {
  135. 		if (tree.contains(inputVector[i])) {
  136. 			std::cout << "FAILURE: The ExponentialTree should include: " << i << std::endl;
  137. 			break;
  138. 		}
  139. 		numtreeVector++;
  140. 	}
  141.  
  142. 	return numtreeVector;
  143. }
  144.  
  145. size_t redBlackTree(std::vector<size_t> inputVector) {
  146. 	std::set<size_t> redBlackTree;
  147.  
  148. 	for(std::vector<size_t>::size_type i = 0; i < inputVector.size(); i++)
  149. 		redBlackTree.insert(inputVector[i]);
  150.  
  151. 	std::cout << "\nShuffled numbers successfully added into our Red/Black Tree." << std::endl;
  152.  
  153. 	size_t numtreeVector = 0;
  154. 	for(std::vector<size_t>::size_type i = 0; i < inputVector.size(); i++) {
  155. 		if(redBlackTree.find(inputVector[i])==redBlackTree.end()) {
  156. 			std::cout << "\nFAILURE: The Red/Black tree should include: " << i << std::endl;
  157. 			break;
  158. 		}
  159. 		numtreeVector++;
  160. 	}
  161.  
  162. 	return numtreeVector;
  163. }
  164.  
Success #stdin #stdout 0.09s 2868KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Trying with 65536 values
Randomly shuffling the 65536 elements.

**Exponential tree**

Shuffled numbers successfully added into our Exponential Tree.
Successfully added and retrieved 65536 elements in 20000 milliseconds

**Red/Black tree**

Shuffled numbers successfully added into our Red/Black Tree.
Successfully added and retrieved 65536 elements in 50000 milliseconds
https://ideone.com/F1T1f
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!