fork(1) download
  1. #include <memory>
  2. #include <iostream>
  3.  
  4. /// Binary Search Tree
  5. template<class T> class bstree {
  6. // I will make use of protected, feel free to use private only
  7. // ... can be used to create another template
  8. // ... or for debug purposes - printouts in such derived class
  9. // ... but remember to never inherit publicly
  10. // ... because it has public non-virtual destructor
  11. //================================================================== node
  12. protected:
  13. struct node; // forward declaration
  14. typedef std::unique_ptr<node>
  15. ptr; ///< managed pointer to node
  16. struct node {
  17. ptr left; ///< left node (if any)
  18. ptr right; ///< right node (if any)
  19. T value; ///< stored value
  20. //------------------------------------------------ node: construction
  21. node() {}
  22. node(
  23. const T& value,
  24. node* left = nullptr,
  25. node* right = nullptr)
  26. : left(left), right(right), value(value) {}
  27. node(
  28. T&& value,
  29. node* left = nullptr,
  30. node* right = nullptr)
  31. : left(left), right(right), value(value) {}
  32. //--------------------------------------------------- node: deep copy
  33. /// Make a deep copy of all nodes. May be called on null as well.
  34. node* copy() {
  35. return !this ? nullptr :
  36. new node(value,
  37. left->copy(),
  38. right->copy());
  39. }
  40. //-------------------------------------------------- node: find value
  41. /// Find node with specified value. May be called on null as well.
  42. node* find(const T& what) {
  43. node* it = this;
  44. while(it) {
  45. if(what < value)
  46. it = it->left.get();
  47. else if(value < what)
  48. it = it->right.get();
  49. else break;
  50. }
  51. return it;
  52. }
  53. //------------------------------------------------- node: place value
  54. /// Find place for new node \return null if already there
  55. ptr* where(const T& what) {
  56. node* it = this;
  57. ptr* where;
  58. for(;;) {
  59. if(what < it->value) {
  60. if(!it->left) return &it->left;
  61. it = it->left.get();
  62. } else if(it->value < what) {
  63. if(!it->right) return &it->right;
  64. it = it->right.get();
  65. } else return nullptr;
  66. }
  67. }
  68. };
  69. //================================================================== data
  70. protected:
  71. ptr root; ///< root node
  72. size_t count; ///< total number of nodes
  73. //====================================================== ctor, copy, move
  74. public:
  75. /// Default constructor for empty tree
  76. bstree(): root(), count(0) {}
  77. //note: no need for a destructor, we use managed pointers
  78. // ~bstree() {}
  79. /// Copy constructor
  80. bstree(const bstree& src)
  81. : root(src.root->copy()), count(src.count) {}
  82. /// Move constructor
  83. bstree(bstree&& rhs)
  84. : root(std::move(rhs.root)), count(rhs.count) {
  85. rhs.count = 0; }
  86. /// Move assignment
  87. bstree& operator = (bstree&& rhs) {
  88. root.swap(rhs.root);
  89. std::swap(count, rhs.count);
  90. return *this; }
  91. /// Copy assignment
  92. bstree& operator = (const bstree& rhs) {
  93. if (this != &rhs) {// no self-copy
  94. root.reset(rhs.root->copy());
  95. count = rhs.count; }
  96. return *this; }
  97. //=============================================================== methods
  98. public:
  99. bool contains(const T& value) {
  100. return root && root->find(value); }
  101. bool insert(const T& value) {
  102. ptr* where = &root;
  103. if(root) {
  104. where = root->where(value);
  105. if(!where) return false; }
  106. where->reset(new node(value));
  107. ++count; return true;
  108. }
  109. bool insert(T&& value) {
  110. ptr* where = &root;
  111. if(root) {
  112. where = root->where(value);
  113. if(!where) return false; }
  114. where->reset(new node(value));
  115. ++count; return true;
  116. }
  117. };
  118.  
  119. //#######################################################################
  120.  
  121. using std::cout;
  122. using std::endl;
  123.  
  124. class test: protected bstree<int> {
  125. typedef bstree<int> base;
  126. void print(node* it) {
  127. if(!it) return;
  128. cout << '<' << it->value << ':';
  129. print(it->left.get()); cout << '|';
  130. print(it->right.get()); cout << '>';
  131. }
  132. public:
  133. using base::contains;
  134. using base::insert;
  135. public:
  136. test() { cout << "new" << endl; }
  137. test(test&& rhs): base(rhs) { cout << "move .ctor" << endl; }
  138. test(const test& src): base(src) { cout << "copy .ctor" << endl; }
  139. test& operator = (test&& rhs) {
  140. cout << "move assign" << endl;
  141. base::operator = ((base&&)rhs);
  142. return *this; }
  143. test& operator = (const test& src) {
  144. cout << "copy assign" << endl;
  145. base::operator = (src);
  146. return *this; }
  147. void print() {
  148. print(root.get()); cout << endl; }
  149. };
  150.  
  151. int main() {
  152. test tree;
  153. tree.insert(3);
  154. tree.insert(2);
  155. tree.insert(4);
  156. cout << std::boolalpha << tree.insert(2) << endl;
  157. cout << tree.contains(3) << ' ' << tree.contains(1) << endl;
  158. tree.print();
  159. tree = tree;
  160. tree = std::move(tree);
  161. tree.print();
  162. tree.insert(1);
  163. tree.insert(5);
  164. tree.print();
  165. }
Success #stdin #stdout 0s 3436KB
stdin
Standard input is empty
stdout
new
false
true false
<3:<2:|>|<4:|>>
copy assign
move assign
<3:<2:|>|<4:|>>
<3:<2:<1:|>|>|<4:|<5:|>>>