33 template<
class KEY,
class VALUE>
38 typedef std::pair<KEY, VALUE> value_type;
48 const value_type keyValue_;
49 const BTree left, right;
59 Node(
const value_type& keyValue) :
60 height_(1), keyValue_(keyValue) {
66 Node(
const BTree& l,
const value_type& keyValue,
const BTree& r) :
68 keyValue_(keyValue), left(l), right(r) {
71 inline const KEY& key()
const {
return keyValue_.first;}
72 inline const VALUE& value()
const {
return keyValue_.second;}
78 typedef std::shared_ptr<const Node> sharedNode;
81 inline const value_type& keyValue()
const {
return root_->keyValue_;}
82 inline const KEY& key()
const {
return root_->key(); }
83 inline const VALUE& value()
const {
return root_->value(); }
84 inline const BTree& left()
const {
return root_->left; }
85 inline const BTree& right()
const {
return root_->right; }
88 static BTree balance(
const BTree& l,
const value_type& xd,
const BTree& r) {
91 const BTree& ll = l.left(), lr = l.right();
92 if (ll.
height() >= lr.height())
93 return BTree(ll, l.keyValue(),
BTree(lr, xd, r));
95 BTree _left(ll, l.keyValue(), lr.left());
96 BTree _right(lr.right(), xd, r);
97 return BTree(_left, lr.keyValue(), _right);
99 }
else if (hr > hl + 2) {
100 const BTree& rl = r.left(), rr = r.right();
101 if (rr.height() >= rl.
height())
102 return BTree(
BTree(l, xd, rl), r.keyValue(), rr);
104 BTree _left(l, xd, rl.left());
105 BTree _right(rl.right(), r.keyValue(), rr);
106 return BTree(_left, rl.keyValue(), _right);
109 return BTree(l, xd, r);
125 root_(new Node(keyValue)) {
130 root_(new Node(l, keyValue, r)) {
147 const KEY& x = xd.first;
149 return BTree(left(), xd, right());
151 return balance(left().
add(xd), keyValue(), right());
153 return balance(left(), keyValue(), right().
add(xd));
158 return add(std::make_pair(x, d));
162 bool mem(
const KEY& x)
const {
163 if (!root_)
return false;
164 if (x == key())
return true;
166 return left().mem(x);
168 return right().mem(x);
173 return (other.root_ == root_);
181 if (other.root_ == root_)
return true;
185 return (keyValue() == other.keyValue()) && (left() == other.left())
186 && (right() == other.right());
194 const value_type&
min()
const {
195 if (!root_)
throw std::invalid_argument(
"BTree::min: empty tree");
196 if (left().
empty())
return keyValue();
202 if (!root_)
throw std::invalid_argument(
"BTree::remove_min: empty tree");
203 if (left().
empty())
return right();
204 return balance(left().
remove_min(), keyValue(), right());
209 if (t1.
empty())
return t2;
210 if (t2.
empty())
return t1;
211 const value_type& xd = t2.
min();
217 if (!root_)
return BTree();
219 return merge(left(), right());
221 return balance(left().
remove(x), keyValue(), right());
223 return balance(left(), keyValue(), right().
remove(x));
228 return (root_ !=
nullptr) ? root_->height_ : 0;
233 if (!root_)
return 0;
234 return left().size() + 1 + right().size();
241 const VALUE&
find(
const KEY& k)
const {
242 const Node* node = root_.get();
244 const KEY& key = node->key();
245 if (k < key) node = node->left.root_.get();
246 else if (key < k) node = node->right.root_.get();
247 else return node->value();
250 throw std::invalid_argument(
"BTree::find: key not found");
254 void print(
const std::string& s =
"")
const {
257 std::stringstream ss;
259 k.print(s + ss.str() +
" ");
260 left().print(s +
"L ");
261 right().print(s +
"R ");
265 void iter(std::function<
void(
const KEY&,
const VALUE&)> f)
const {
276 std::pair<KEY, TO> xd(key(), f(key(), value()));
287 ACC
fold(std::function<ACC(
const KEY&,
const VALUE&,
const ACC&)> f,
288 const ACC& a)
const {
289 if (!root_)
return a;
290 ACC ar = right().fold(f, a);
291 ACC am = f(key(), value(), ar);
292 return left().fold(f, am);
304 typedef std::pair<sharedNode, bool> flagged;
307 std::stack<flagged> path_;
309 const sharedNode& current()
const {
310 return path_.top().first;
314 return path_.top().second;
322 if (path_.empty())
return;
323 sharedNode t = current()->right.root_;
327 while (!path_.empty() && done())
330 path_.top().second =
true;
333 path_.push(std::make_pair(t,
false));
342 typedef ptrdiff_t difference_type;
343 typedef std::forward_iterator_tag iterator_category;
344 typedef std::pair<KEY, VALUE> value_type;
345 typedef const value_type* pointer;
346 typedef const value_type& reference;
356 path_.push(std::make_pair(t,
false));
363 return path_ == __x.path_;
368 return path_ != __x.path_;
373 if (path_.empty())
throw std::invalid_argument(
374 "operator*: tried to dereference end");
375 return current()->keyValue_;
380 if (path_.empty())
throw std::invalid_argument(
381 "operator->: tried to dereference end");
382 return &(current()->keyValue_);
406 return const_iterator(root_);
410 const_iterator
end()
const {
411 return const_iterator();
bool operator==(const BTree &other) const
Definition: BTree.h:180
bool mem(const KEY &x) const
Definition: BTree.h:162
bool operator!=(const Matrix &A, const Matrix &B)
Definition: Matrix.h:106
const_iterator()
Definition: BTree.h:349
Binary tree.
Definition: BTree.h:34
static BTree merge(const BTree &t1, const BTree &t2)
Definition: BTree.h:208
void print(const std::string &s="") const
Definition: BTree.h:254
size_t size() const
Definition: BTree.h:232
Const iterator Not trivial: iterator keeps a stack to indicate current path from root_.
Definition: BTree.h:299
ACC fold(std::function< ACC(const KEY &, const VALUE &, const ACC &)> f, const ACC &a) const
Definition: BTree.h:287
const_iterator begin() const
Definition: BTree.h:405
const_iterator(const sharedNode &root)
Definition: BTree.h:353
BTree(const value_type &keyValue)
Definition: BTree.h:124
bool empty() const
Definition: BTree.h:140
BTree()
Definition: BTree.h:115
BTree(const BTree &l, const value_type &keyValue, const BTree &r)
Definition: BTree.h:129
BTree remove_min() const
Definition: BTree.h:201
Definition: chartTesting.h:28
Self & operator++()
Definition: BTree.h:386
reference operator*() const
Definition: BTree.h:372
bool operator!=(const Self &__x) const
Definition: BTree.h:367
BTree add(const KEY &x, const VALUE &d) const
Definition: BTree.h:157
BTree add(const value_type &xd) const
Definition: BTree.h:145
BTree< KEY, TO > map(std::function< TO(const KEY &, const VALUE &)> f) const
Definition: BTree.h:274
Self operator++(int)
Definition: BTree.h:392
void iter(std::function< void(const KEY &, const VALUE &)> f) const
Definition: BTree.h:265
BTree & operator=(const BTree &other)
Definition: BTree.h:134
const_iterator end() const
Definition: BTree.h:410
BTree(const BTree &other)
Definition: BTree.h:119
const VALUE & find(const KEY &k) const
Definition: BTree.h:241
pointer operator->() const
Definition: BTree.h:379
bool operator==(const Self &__x) const
Definition: BTree.h:362
const value_type & min() const
Definition: BTree.h:194
size_t height() const
Definition: BTree.h:227
bool same(const BTree &other) const
Definition: BTree.h:172