fork download
copy 
  1. /**
  2.  * A template BTree
  3.  *
  4.  * Author: Erel Segal
  5.  * Date: 2010-10-14
  6.  */
  7.  
  8. #include <string>
  9. #include <iostream>
  10. #include <vector>
  11. #include <utility>
  12. using namespace std;
  13.  
  14.  
  15. template <typename K, typename T, int MIN_RANK> class BTree {
  16. 	vector< pair<K,T> > pairs;
  17. 	vector<BTree<K,T,MIN_RANK>*> children;
  18. 	BTree<K,T,MIN_RANK>* parent;
  19. 		// all keys at children[i] are smaller than pairs[i].first
  20.  
  21. public:
  22. 	size_t keyCount() const { return pairs.size(); }
  23. 	size_t childCount() const { return children.size(); }
  24. 	bool isLeaf() const { return !children[0]; }
  25.  
  26. 	static const size_t MAX_KEY_COUNT = 2*MIN_RANK-1;
  27. 	static const size_t MAX_RANK = 2*MIN_RANK;
  28.  
  29. 	BTree<K,T,MIN_RANK>(
  30. 		int newKeyCount=0, BTree<K,T,MIN_RANK>* newParent=NULL): 
  31. 			pairs(newKeyCount), children(newKeyCount+1), parent(newParent) { }
  32.  
  33. protected:
  34. 	size_t indexOfLeastUpperBound(K key) const {
  35. 		// NOTE: Could use binary search.
  36. 		for (size_t i=0; i<pairs.size(); ++i) {
  37. 			if (pairs[i].first >= key)
  38. 				return i;
  39. 		}
  40. 		return pairs.size();
  41. 	}
  42.  
  43. 	// If there are too many children, split them in the middle
  44. 	void splitChildrenIfNeeded() {
  45. 			if (pairs.size() > MAX_KEY_COUNT) {
  46. 				size_t MEDIAN_KEY_INDEX = (int) ((pairs.size()-1)/2);
  47. 				pair<K,T>& pair_to_promote = pairs[MEDIAN_KEY_INDEX];
  48. 				cout << "splitting at " << pair_to_promote.first << endl;
  49.  
  50. 				// child 0 includes all keys less than k:
  51. 				BTree<K,T,MIN_RANK>* leftChild = new BTree<K,T,MIN_RANK> (MEDIAN_KEY_INDEX, this);
  52. 				leftChild->pairs.assign(pairs.begin(), pairs.begin()+MEDIAN_KEY_INDEX);
  53. 				leftChild->children.assign(children.begin(), children.begin()+MEDIAN_KEY_INDEX+1);
  54.  
  55. 				// child 1 includes all keys greater than k:
  56. 				BTree<K,T,MIN_RANK>* rightChild = new BTree<K,T,MIN_RANK> (pairs.size()-MEDIAN_KEY_INDEX-1, this);
  57. 				rightChild->pairs.assign(pairs.begin()+MEDIAN_KEY_INDEX+1, pairs.end());
  58. 				rightChild->children.assign(children.begin()+MEDIAN_KEY_INDEX+1, children.end());
  59.  
  60. 				if (parent) {   // b2a. split a non-root leaf
  61. 					int iParentLUB = parent->indexOfLeastUpperBound(pair_to_promote.first);
  62. 					cout << "moving to parent as #" << iParentLUB << endl;
  63. 					parent->pairs.insert(parent->pairs.begin()+iParentLUB, pair_to_promote);
  64. 					parent->children.insert(parent->children.begin()+iParentLUB, leftChild);
  65. 					parent->children[iParentLUB+1] = rightChild;
  66. 					parent->splitChildrenIfNeeded();
  67. 					leftChild->parent = rightChild->parent = parent;
  68. 				} else {   // b2b. we are at the root - create a new root with a single key
  69. 					cout << "creating a new root" << endl;
  70. 					//pairs.clear();
  71. 					//pairs.push_back(pair_to_promote);
  72. 					pairs[0] = pair_to_promote;
  73. 					pairs.erase(pairs.begin()+1, pairs.end());
  74. 					//pairs.push_back(pair_to_promote);
  75. 					printKeys(cout);
  76. 					children.clear();
  77. 					children.push_back(leftChild);
  78. 					children.push_back(rightChild);
  79. 					leftChild->parent = rightChild->parent = this;
  80. 				}
  81. 			}
  82.  
  83. 	}
  84.  
  85.  
  86. public:
  87.  
  88. 	// return a pointer to the data related to the given key, or NULL if not found.
  89. 	T* get (K key) {
  90. 		size_t iLUB = indexOfLeastUpperBound(key);
  91. 		if (iLUB<pairs.size()) {
  92. 			pair<K,T>& keyValue = pairs[iLUB];
  93. 			if (key==keyValue.first)
  94. 				return &keyValue.second;
  95. 		}
  96. 		return (children[iLUB]? children[iLUB]->get(key): NULL);
  97. 	}
  98.  
  99. 	void insert(K key, T value) {
  100. 		size_t iLUB = indexOfLeastUpperBound(key);
  101. 		if (iLUB<pairs.size()) {
  102. 			pair<K,T>& keyValue = pairs[iLUB];
  103. 			if (key==keyValue.first) {
  104. 				keyValue.second = value;
  105. 				return;
  106. 			}
  107. 		}
  108. 		//printKeys(cout);
  109. 		cout << "inserting " << key << " as #" << iLUB << endl;
  110.  
  111. 		if (children[iLUB]) {  // a. insert it at the child, or -
  112. 			children[iLUB]->insert(key,value);
  113. 			return;
  114. 		} else {               // b. add it to this leaf
  115. 			pairs.insert (pairs.begin()+iLUB, pair<K,T>(key,value));
  116. 			children.insert (children.begin()+iLUB, NULL); // insert an empty child (it's a leaf)
  117. 			splitChildrenIfNeeded();
  118. 			return;
  119. 		}
  120. 	}
  121.  
  122. 	void printInOrder(ostream& out, string prefix="") const {
  123. 		if (!pairs.size())
  124. 			return;
  125. 		const pair<K,T>* pair0 = &pairs[0];
  126. 		if (children[0]) {
  127. 			out << prefix+"  BEFORE " << pair0->first << ":" << endl;
  128. 			children[0]->printInOrder(out, prefix+"  ");
  129. 		}
  130. 		out << prefix << pair0->first << ": " << pair0->second << endl;
  131. 		size_t lastChild = children.size()-1;
  132. 		for (size_t i=1; i<lastChild; ++i) {
  133. 			const pair<K,T>* before = &pairs[i-1];
  134. 			const pair<K,T>* after = &pairs[i];
  135. 			if (children[i]) {
  136. 				out << prefix+"  BETWEEN " << before->first << " AND " << after->first << ":" << endl;
  137. 				children[i]->printInOrder(out, prefix+"  ");
  138. 			}
  139. 			out << prefix << after->first << ": " << after->second << endl;
  140. 		}
  141. 		if (children[lastChild]) {
  142. 			const pair<K,T>* pairLast = &pairs[lastChild-1];
  143. 			out << prefix+"  AFTER " << pairLast->first << ":" << endl;
  144. 			children[lastChild]->printInOrder(out, prefix+"  ");
  145. 		}
  146. 	}
  147.  
  148. 	// for debug:
  149. 	void printKeys(ostream& out) const {
  150. 		out << pairs.size() << " keys:";
  151. 		for (size_t i=0; i<pairs.size(); ++i) {
  152. 			out << pairs[i].first << " ";
  153. 		}
  154. 		out << endl;
  155. 	}
  156. };  // template class BTree
  157.  
  158.  
  159.  
  160. int main() {
  161. 	BTree<string, int, 2> atree;
  162. 	atree.printInOrder(cout); cout<<endl;
  163.   atree.insert ("b",1);
  164. 	atree.printInOrder(cout); cout<<endl;
  165.   atree.insert ("c",8);
  166. 	atree.printInOrder(cout); cout<<endl;
  167.   atree.insert ("g",7);
  168. 	atree.printInOrder(cout); cout<<endl;
  169.   atree.insert ("h",3);
  170. 	atree.printInOrder(cout); cout<<endl;
  171.   atree.insert ("k",6);
  172. 	atree.printInOrder(cout); cout<<endl;
  173.   atree.insert ("d",2);
  174. 	atree.printInOrder(cout); cout<<endl;
  175.   atree.insert ("m",4);
  176. 	atree.printInOrder(cout); cout<<endl;
  177.   atree.insert ("r",5);
  178. 	atree.printInOrder(cout); cout<<endl;
  179.   atree.insert ("w",5);
  180. 	atree.printInOrder(cout); cout<<endl;
  181.   atree.insert ("z",5);
  182. 	atree.printInOrder(cout); cout<<endl;
  183.   atree.insert ("a",9);
  184. 	atree.printInOrder(cout); cout<<endl;
  185.   cout << "a = " << *atree.get ("a") << endl;
  186.   cout << "b = " << *atree.get ("b") << endl;
  187.   cout << "c = " << *atree.get ("c") << endl;
  188.   cout << "d = " << *atree.get ("d") << endl;
  189.   cout << "g = " << *atree.get ("g") << endl;
  190.   cout << "h = " << *atree.get ("h") << endl;
  191.   cout << "k = " << *atree.get ("k") << endl;
  192.   cout << "m = " << *atree.get ("m") << endl;
  193.   cout << "r = " << *atree.get ("r") << endl;
  194.   cout << "w = " << *atree.get ("w") << endl;
  195.   cout << "z = " << *atree.get ("z") << endl;
  196. }
  197.  
Success #stdin #stdout 0s 2876KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
inserting b as #0
b: 1

inserting c as #1
b: 1
c: 8

inserting g as #2
b: 1
c: 8
g: 7

inserting h as #3
splitting at c
creating a new root
1 keys:c 
  BEFORE c:
  b: 1
c: 8
  AFTER c:
  g: 7
  h: 3

inserting k as #1
inserting k as #2
  BEFORE c:
  b: 1
c: 8
  AFTER c:
  g: 7
  h: 3
  k: 6

inserting d as #1
inserting d as #0
splitting at g
moving to parent as #1
  BEFORE c:
  b: 1
c: 8
  BETWEEN c AND g:
  d: 2
g: 7
  AFTER g:
  h: 3
  k: 6

inserting m as #2
inserting m as #2
  BEFORE c:
  b: 1
c: 8
  BETWEEN c AND g:
  d: 2
g: 7
  AFTER g:
  h: 3
  k: 6
  m: 4

inserting r as #2
inserting r as #3
splitting at k
moving to parent as #2
  BEFORE c:
  b: 1
c: 8
  BETWEEN c AND g:
  d: 2
g: 7
  BETWEEN g AND k:
  h: 3
k: 6
  AFTER k:
  m: 4
  r: 5

inserting w as #3
inserting w as #2
  BEFORE c:
  b: 1
c: 8
  BETWEEN c AND g:
  d: 2
g: 7
  BETWEEN g AND k:
  h: 3
k: 6
  AFTER k:
  m: 4
  r: 5
  w: 5

inserting z as #3
inserting z as #3
splitting at r
moving to parent as #3
splitting at g
creating a new root
1 keys:g 
  BEFORE g:
    BEFORE c:
    b: 1
  c: 8
    AFTER c:
    d: 2
g: 7
  AFTER g:
    BEFORE k:
    h: 3
  k: 6
    BETWEEN k AND r:
    m: 4
  r: 5
    AFTER r:
    w: 5
    z: 5

inserting a as #0
inserting a as #0
inserting a as #0
  BEFORE g:
    BEFORE c:
    a: 9
    b: 1
  c: 8
    AFTER c:
    d: 2
g: 7
  AFTER g:
    BEFORE k:
    h: 3
  k: 6
    BETWEEN k AND r:
    m: 4
  r: 5
    AFTER r:
    w: 5
    z: 5

a = 9
b = 1
c = 8
d = 2
g = 7
h = 3
k = 6
m = 4
r = 5
w = 5
z = 5
https://ideone.com/DztXk
language:
C++ (gcc 8.3)
created:
13 years ago
visibility:
public

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!