87 #include "Iterator.hpp" 115 template <
typename KT,
typename VT,
typename cmp = std::less<KT>>
120 std::unique_ptr<APutils::Node<std::pair<const KT, VT>>>
root;
133 if (!root)
return nullptr;
135 auto tmp = root.get();
137 tmp = tmp->left.get();
151 auto tmp = root.get();
153 if (
op(x,tmp->data.first)) {
154 tmp = tmp->left.get();
155 }
else if (
op(tmp->data.first, x)) {
156 tmp = tmp->right.get();
182 if (a.get()->right) {
183 __copy(t, a.get()->right);
201 void __balance(std::vector<std::pair<const KT, VT>>& v,
long long int a,
long long int b) {
205 long long int mid{(b + a)/2};
206 #ifdef __DEBUG_AP_BST 207 std::cout <<
"Inserting " << v[mid].first <<
" in place " << mid << std::endl;
247 bst() noexcept : op{}, root{
nullptr} {}
257 explicit bst(cmp x) noexcept : op{x}, root{
nullptr} {}
268 explicit bst(
const bst& t) : op{t.
op}, root{std::unique_ptr<node_type>(
new node_type(t.root.get()->data,
nullptr))} {
269 if (t.root.get()->left) {
270 __copy(t, t.root.get()->left);
272 if (t.root.get()->right) {
273 __copy(t, t.root.get()->right);
286 bst(
bst&& t) noexcept =
default;
300 if (t.
root.get()->left) {
303 if (t.
root.get()->right) {
333 #ifdef __DEBUG_AP_BST 334 std::cout <<
"CALL: COPY_INSERT: APbst::bst::insert(const pair_type& x)" << std::endl;
336 auto tmp = root.get();
338 if (
op(x.first,tmp->data.first)) {
340 tmp = tmp->left.get();
343 return std::make_pair<iterator, bool>(
iterator{tmp->left.get()},
true);
345 }
else if (
op(tmp->data.first, x.first)) {
347 tmp = tmp->right.get();
350 return std::make_pair<iterator, bool>(
iterator{tmp->right.get()},
true);
353 return std::make_pair<iterator, bool>(
iterator{tmp},
false);
358 return std::make_pair<iterator, bool>(
iterator{tmp},
true);
374 #ifdef __DEBUG_AP_BST 375 std::cout <<
"CALL: MOVE_INSERT: APbst::bst::insert(pair_type&& x)" << std::endl;
377 auto tmp = root.get();
379 if (
op(x.first,tmp->data.first)) {
381 tmp = tmp->left.get();
383 tmp->left.reset(
new node_type{std::move(x), tmp});
384 return std::make_pair<iterator, bool>(
iterator{tmp->left.get()},
true);
386 }
else if (
op(tmp->data.first, x.first)) {
388 tmp = tmp->right.get();
390 tmp->right.reset(
new node_type{std::move(x), tmp});
391 return std::make_pair<iterator, bool>(
iterator{tmp->right.get()},
true);
394 return std::make_pair<iterator, bool>(
iterator{tmp},
false);
397 root.reset(
new node_type{std::move(x),
nullptr});
398 return std::make_pair<iterator, bool>(
iterator{tmp},
true);
414 template<
class... Types>
415 std::pair<iterator,bool>
emplace(Types&&... args) {
439 #ifdef __DEBUG_AP_BST 440 std::cout <<
"CALL: NONCONST_BEGIN" << std::endl;
455 #ifdef __DEBUG_AP_BST 456 std::cout <<
"CALL: CONST_BEGIN" << std::endl;
480 #ifdef __DEBUG_AP_BST 481 std::cout <<
"CALL: NONCONST_END" << std::endl;
495 #ifdef __DEBUG_AP_BST 496 std::cout <<
"CALL: CONST_END" << std::endl;
520 #ifdef __DEBUG_AP_BST 521 std::cout <<
"CALL: NONCONST_FIND" << std::endl;
535 #ifdef __DEBUG_AP_BST 536 std::cout <<
"CALL: CONST_FIND" << std::endl;
548 std::vector<pair_type> v{};
549 for (
const auto& it : *
this) {
553 long long int mid{(
static_cast<long long int> (v.size()))/2};
554 #ifdef __DEBUG_AP_BST 555 std::cout <<
"Inserting " << v[mid].first <<
" in palce " << mid << std::endl;
572 #ifdef __DEBUG_AP_BST 573 std::cout <<
"CALL: COPY_[]" << std::endl;
587 #ifdef __DEBUG_AP_BST 588 std::cout <<
"CALL: MOVE_[]" << std::endl;
622 auto itStop = x.
cend();
623 for (
auto it = x.
cbegin(); it != itStop; ++it) {
626 it.printNode(os,
true);
649 for (
const auto& it : *
this) {
650 ss << it.first <<
" : " << it.second << std::endl;
663 auto __nodeToDeleteIt =
find(x);
665 auto __nodeToDelete = __nodeToDeleteIt.currentNode;
668 if (!__nodeToDelete)
return;
671 if (__nodeToDelete == root.get()) {
672 if ((!__nodeToDelete->left) && (!__nodeToDelete->right)) {
674 }
else if ( !(!__nodeToDelete->left) != !(!__nodeToDelete->right) ) {
675 if (__nodeToDelete->left) {
676 root.reset(__nodeToDelete->left.release());
677 __nodeToDelete->left->parent =
nullptr;
679 root.reset(__nodeToDelete->right.release());
680 __nodeToDelete->right->parent =
nullptr;
688 auto __nodeSuccessor = (++__nodeToDeleteIt).currentNode;
694 auto dummyNode = std::unique_ptr<node_type>(
new node_type(__nodeSuccessor->data,
nullptr));
695 dummyNode.get()->left .reset(__nodeToDelete->left .release());
696 dummyNode.get()->left .get()->parent = dummyNode.get();
699 if (__nodeToDelete->right.get() == __nodeSuccessor) {
700 dummyNode.get()->right.reset(__nodeSuccessor->right.release());
701 dummyNode.get()->right.get()->parent = dummyNode.get();
703 dummyNode.get()->right.reset(__nodeToDelete->right.release());
704 dummyNode.get()->right.get()->parent = dummyNode.get();
705 if (__nodeSuccessor->right) {
707 __nodeSuccessor->right->parent = __nodeSuccessor->parent;
708 __nodeSuccessor->parent->left.reset(__nodeSuccessor->right.release());
710 __nodeSuccessor->parent->left.reset();
714 root.reset(dummyNode.release());
721 auto __nodeParent = __nodeToDelete->parent;
723 if ((!__nodeToDelete->left) && (!__nodeToDelete->right)) {
724 if (__nodeParent->left.get() == __nodeToDelete) {
725 __nodeParent->left.reset();
727 __nodeParent->right.reset();
729 }
else if ( !(!__nodeToDelete->left) != !(!__nodeToDelete->right) ) {
730 if (__nodeToDelete->left) {
731 __nodeToDelete->left.get()->parent = __nodeParent;
732 if (__nodeParent->left.get() == __nodeToDelete) {
733 __nodeParent->left.reset(__nodeToDelete->left.release());
735 __nodeParent->right.reset(__nodeToDelete->left.release());
738 __nodeToDelete->right.get()->parent = __nodeParent;
739 if (__nodeParent->left.get() == __nodeToDelete) {
740 __nodeParent->left.reset(__nodeToDelete->right.release());
742 __nodeParent->right.reset(__nodeToDelete->right.release());
751 auto __nodeSuccessor = (++__nodeToDeleteIt).currentNode;
758 auto dummyNode = std::unique_ptr<node_type>(
new node_type(__nodeSuccessor->data, __nodeParent));
759 dummyNode.get()->left .reset(__nodeToDelete->left .release());
760 dummyNode.get()->left .get()->parent = dummyNode.get();
763 if (__nodeToDelete->right.get() == __nodeSuccessor) {
764 dummyNode.get()->right.reset(__nodeSuccessor->right.release());
765 dummyNode.get()->right.get()->parent = dummyNode.get();
767 if (__nodeParent->left.get() == __nodeToDelete) {
768 __nodeParent->left .reset(dummyNode.release());
770 __nodeParent->right.reset(dummyNode.release());
773 dummyNode.get()->right.reset(__nodeToDelete->right.release());
774 dummyNode.get()->right.get()->parent = dummyNode.get();
776 if (__nodeParent->left.get() == __nodeToDelete) {
777 __nodeParent->left .reset(dummyNode.release());
779 __nodeParent->right.reset(dummyNode.release());
781 if (__nodeSuccessor->right) {
783 __nodeSuccessor->right->parent = __nodeSuccessor->parent;
784 __nodeSuccessor->parent->left.reset(__nodeSuccessor->right.release());
786 __nodeSuccessor->parent->left.reset();
std::pair< iterator, bool > insert(pair_type &&x)
Inserts a APutils::Node by moving it in the tree, if not already present.
Definition: BST.hpp:373
Class that implements an iterator of a tree.
Definition: Iterator.hpp:19
const_iterator find(const key_type &x) const
Finds if a node just exists.
Definition: BST.hpp:534
const_iterator end() const noexcept
Returns a const_iterator to one-past the last element.
Definition: BST.hpp:494
VT mapped_type
The Value type of the Node of the tree.
Definition: BST.hpp:223
friend std::ostream & operator<<(std::ostream &os, const bst &x)
Put-to operator that prints the tree.
Definition: BST.hpp:618
const_iterator cend() const noexcept
The const version of end(), to be used when a const_iterator is needed.
Definition: BST.hpp:507
typename std::pair< const KT, VT > pair_type
The Pair type of the tree, i.e. std::pair<const Key,Value>.
Definition: BST.hpp:227
mapped_type & operator[](const key_type &x)
Subscripting operator performing a copy.
Definition: BST.hpp:571
void __copy(const bst &t, std::unique_ptr< APutils::Node< std::pair< const KT, VT >>> &a)
Internal helper function for the copy operations.
Definition: BST.hpp:177
const_iterator begin() const noexcept
Returns a const_iterator to the left-most APutils::Node.
Definition: BST.hpp:454
typename APutils::__iterator< node_type, const pair_type > const_iterator
The const iterator type.
Definition: BST.hpp:239
bst() noexcept
Empty constructor.
Definition: BST.hpp:247
const_iterator cbegin() const noexcept
The const version of begin(), to be used when a const_iterator is needed.
Definition: BST.hpp:467
typename APutils::Node< pair_type > node_type
The Node type of the tree, i.e. Node<Pair>.
Definition: BST.hpp:231
APutils::Node< std::pair< const KT, VT > > * __find(const KT &x) const
Internal helper function for find().
Definition: BST.hpp:150
std::pair< iterator, bool > emplace(Types &&... args)
Inserts a APutils::Node constructed in-place.
Definition: BST.hpp:415
iterator find(const key_type &x)
Finds a APutils::Node and possibly change its value.
Definition: BST.hpp:519
typename APutils::__iterator< node_type, pair_type > iterator
The non-const iterator type.
Definition: BST.hpp:235
bst(cmp x) noexcept
Empty constructor with an explicit comparison ("less than") operation.
Definition: BST.hpp:257
bst & operator=(const bst &t)
Copy assignment for bst.
Definition: BST.hpp:297
bst(const bst &t)
Copy constructor.
Definition: BST.hpp:268
APutils::Node< std::pair< const KT, VT > > * __begin() const
Internal helper function for begin().
Definition: BST.hpp:131
void erase(const key_type &x)
Removes the element (if it exists) with Key x.
Definition: BST.hpp:662
void clear() noexcept
Clears the content of the tree.
Definition: BST.hpp:425
mapped_type & operator[](key_type &&x)
Subscripting operator performing a move.
Definition: BST.hpp:586
iterator begin() noexcept
Returns an iterator to the left-most APutils::Node.
Definition: BST.hpp:438
void __balance(std::vector< std::pair< const KT, VT >> &v, long long int a, long long int b)
Internal helper function for balance().
Definition: BST.hpp:201
KT key_type
The Key type of the Node of the tree.
Definition: BST.hpp:219
Class that implements a node of a tree.
Definition: Node.hpp:26
std::pair< iterator, bool > insert(const pair_type &x)
Inserts a APutils::Node by copying it in the tree, if not already present.
Definition: BST.hpp:332
std::unique_ptr< APutils::Node< std::pair< const KT, VT > > > root
The root Node of the tree.
Definition: BST.hpp:120
Namespace for the Binary Search Tree.
Definition: BST.hpp:97
void balance()
Balances the tree.
Definition: BST.hpp:547
cmp op
Operator of comparison ("less than") for the Key type.
Definition: BST.hpp:118
void printRawTree(std::stringstream &ss)
Prints the tree in an easy way.
Definition: BST.hpp:648
Class that implements a Binary Search Tree.
Definition: BST.hpp:116
iterator end() noexcept
Returns an iterator to one-past the last element.
Definition: BST.hpp:479