BTree.h
Go to the documentation of this file.
1 /* ----------------------------------------------------------------------------
2 
3  * GTSAM Copyright 2010, Georgia Tech Research Corporation,
4  * Atlanta, Georgia 30332-0415
5  * All Rights Reserved
6  * Authors: Frank Dellaert, et al. (see THANKS for the full author list)
7 
8  * See LICENSE for the license information
9 
10  * -------------------------------------------------------------------------- */
11 
20 #pragma once
21 
22 #include <stack>
23 #include <sstream>
24 #include <memory>
25 #include <functional>
26 
27 namespace gtsam {
28 
33  template<class KEY, class VALUE>
34  class BTree {
35 
36  public:
37 
38  typedef std::pair<KEY, VALUE> value_type;
39 
40  private:
41 
45  struct Node {
46 
47  const size_t height_;
48  const value_type keyValue_;
49  const BTree left, right;
50 
52  Node() {
53  }
54 
59  Node(const value_type& keyValue) :
60  height_(1), keyValue_(keyValue) {
61  }
62 
66  Node(const BTree& l, const value_type& keyValue, const BTree& r) :
67  height_(l.height() >= r.height() ? l.height() + 1 : r.height() + 1),
68  keyValue_(keyValue), left(l), right(r) {
69  }
70 
71  inline const KEY& key() const { return keyValue_.first;}
72  inline const VALUE& value() const { return keyValue_.second;}
73 
74  }; // Node
75 
76  // We store a shared pointer to the root of the functional tree
77  // composed of Node classes. If root_==nullptr, the tree is empty.
78  typedef std::shared_ptr<const Node> sharedNode;
79  sharedNode root_;
80 
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; }
86 
88  static BTree balance(const BTree& l, const value_type& xd, const BTree& r) {
89  size_t hl = l.height(), hr = r.height();
90  if (hl > hr + 2) {
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));
94  else {
95  BTree _left(ll, l.keyValue(), lr.left());
96  BTree _right(lr.right(), xd, r);
97  return BTree(_left, lr.keyValue(), _right);
98  }
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);
103  else {
104  BTree _left(l, xd, rl.left());
105  BTree _right(rl.right(), r.keyValue(), rr);
106  return BTree(_left, rl.keyValue(), _right);
107  }
108  } else
109  return BTree(l, xd, r);
110  }
111 
112  public:
113 
115  BTree() {
116  }
117 
119  BTree(const BTree& other) :
120  root_(other.root_) {
121  }
122 
124  BTree(const value_type& keyValue) :
125  root_(new Node(keyValue)) {
126  }
127 
129  BTree(const BTree& l, const value_type& keyValue, const BTree& r) :
130  root_(new Node(l, keyValue, r)) {
131  }
132 
135  root_ = other.root_;
136  return *this;
137  }
138 
140  bool empty() const {
141  return !root_;
142  }
143 
145  BTree add(const value_type& xd) const {
146  if (empty()) return BTree(xd);
147  const KEY& x = xd.first;
148  if (x == key())
149  return BTree(left(), xd, right());
150  else if (x < key())
151  return balance(left().add(xd), keyValue(), right());
152  else
153  return balance(left(), keyValue(), right().add(xd));
154  }
155 
157  BTree add(const KEY& x, const VALUE& d) const {
158  return add(std::make_pair(x, d));
159  }
160 
162  bool mem(const KEY& x) const {
163  if (!root_) return false;
164  if (x == key()) return true;
165  if (x < key())
166  return left().mem(x);
167  else
168  return right().mem(x);
169  }
170 
172  inline bool same(const BTree& other) const {
173  return (other.root_ == root_);
174  }
175 
180  bool operator==(const BTree& other) const {
181  if (other.root_ == root_) return true; // if same, we're done
182  if (empty() && !other.empty()) return false;
183  if (!empty() && other.empty()) return false;
184  // both non-empty, recurse: check this key-value pair and subtrees...
185  return (keyValue() == other.keyValue()) && (left() == other.left())
186  && (right() == other.right());
187  }
188 
189  inline bool operator!=(const BTree& other) const {
190  return !operator==(other);
191  }
192 
194  const value_type& min() const {
195  if (!root_) throw std::invalid_argument("BTree::min: empty tree");
196  if (left().empty()) return keyValue();
197  return left().min();
198  }
199 
201  BTree remove_min() const {
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());
205  }
206 
208  static BTree merge(const BTree& t1, const BTree& t2) {
209  if (t1.empty()) return t2;
210  if (t2.empty()) return t1;
211  const value_type& xd = t2.min();
212  return balance(t1, xd, t2.remove_min());
213  }
214 
216  BTree remove(const KEY& x) const {
217  if (!root_) return BTree();
218  if (x == key())
219  return merge(left(), right());
220  else if (x < key())
221  return balance(left().remove(x), keyValue(), right());
222  else
223  return balance(left(), keyValue(), right().remove(x));
224  }
225 
227  size_t height() const {
228  return (root_ != nullptr) ? root_->height_ : 0;
229  }
230 
232  size_t size() const {
233  if (!root_) return 0;
234  return left().size() + 1 + right().size();
235  }
236 
241  const VALUE& find(const KEY& k) const {
242  const Node* node = root_.get();
243  while (node) {
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();
248  }
249 
250  throw std::invalid_argument("BTree::find: key not found");
251  }
252 
254  void print(const std::string& s = "") const {
255  if (empty()) return;
256  KEY k = key();
257  std::stringstream ss;
258  ss << height();
259  k.print(s + ss.str() + " ");
260  left().print(s + "L ");
261  right().print(s + "R ");
262  }
263 
265  void iter(std::function<void(const KEY&, const VALUE&)> f) const {
266  if (!root_) return;
267  left().iter(f);
268  f(key(), value());
269  right().iter(f);
270  }
271 
273  template<class TO>
274  BTree<KEY, TO> map(std::function<TO(const KEY&, const VALUE&)> f) const {
275  if (empty()) return BTree<KEY, TO> ();
276  std::pair<KEY, TO> xd(key(), f(key(), value()));
277  return BTree<KEY, TO> (left().map(f), xd, right().map(f));
278  }
279 
286  template<class ACC>
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); // fold over right subtree
291  ACC am = f(key(), value(), ar); // apply f with current value
292  return left().fold(f, am); // fold over left subtree
293  }
294 
300 
301  private:
302 
304  typedef std::pair<sharedNode, bool> flagged;
305 
307  std::stack<flagged> path_;
308 
309  const sharedNode& current() const {
310  return path_.top().first;
311  }
312 
313  bool done() const {
314  return path_.top().second;
315  }
316 
317  // The idea is we already iterated through the left-subtree and current key-value.
318  // We now try pushing left subtree of right onto the stack. If there is no right
319  // sub-tree, we pop this node of the stack and the parent becomes the iterator.
320  // We avoid going down a right-subtree that was already visited by checking the flag.
321  void increment() {
322  if (path_.empty()) return;
323  sharedNode t = current()->right.root_;
324  if (!t || done()) {
325  // no right subtree, iterator becomes first parent with a non-visited right subtree
326  path_.pop();
327  while (!path_.empty() && done())
328  path_.pop();
329  } else {
330  path_.top().second = true; // flag we visited right
331  // push right root and its left-most path onto the stack
332  while (t) {
333  path_.push(std::make_pair(t, false));
334  t = t->left.root_;
335  }
336  }
337  }
338 
339  public:
340 
341  // traits for playing nice with STL
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;
347 
350  }
351 
353  const_iterator(const sharedNode& root) {
354  sharedNode t = root;
355  while (t) {
356  path_.push(std::make_pair(t, false));
357  t = t->left.root_;
358  }
359  }
360 
362  bool operator==(const Self& __x) const {
363  return path_ == __x.path_;
364  }
365 
367  bool operator!=(const Self& __x) const {
368  return path_ != __x.path_;
369  }
370 
372  reference operator*() const {
373  if (path_.empty()) throw std::invalid_argument(
374  "operator*: tried to dereference end");
375  return current()->keyValue_;
376  }
377 
379  pointer operator->() const {
380  if (path_.empty()) throw std::invalid_argument(
381  "operator->: tried to dereference end");
382  return &(current()->keyValue_);
383  }
384 
386  Self& operator++() {
387  increment();
388  return *this;
389  }
390 
392  Self operator++(int) {
393  Self __tmp = *this;
394  increment();
395  return __tmp;
396  }
397 
398  }; // const_iterator
399 
400  // to make BTree work with range-based for
401  // We do *not* want a non-const iterator
402  typedef const_iterator iterator;
403 
405  const_iterator begin() const {
406  return const_iterator(root_);
407  }
408 
410  const_iterator end() const {
411  return const_iterator();
412  }
413 
414  }; // BTree
415 
416 } // namespace gtsam
417 
const BTree & left() const
Definition: BTree.h:84
bool operator!=(const BTree &other) const
Definition: BTree.h:189
static BTree balance(const BTree &l, const value_type &xd, const BTree &r)
Definition: BTree.h:88
bool operator==(const BTree &other) const
Definition: BTree.h:180
bool mem(const KEY &x) const
Definition: BTree.h:162
std::pair< KEY, VALUE > value_type
Definition: BTree.h:38
Binary tree.
Definition: BTree.h:34
const KEY & key() const
Definition: BTree.h:71
const sharedNode & current() const
Definition: BTree.h:309
const value_type & reference
Definition: BTree.h:346
static BTree merge(const BTree &t1, const BTree &t2)
Definition: BTree.h:208
std::shared_ptr< const Node > sharedNode
Definition: BTree.h:78
Node(const value_type &keyValue)
Definition: BTree.h:59
void print(const std::string &s="") const
Definition: BTree.h:254
size_t size() const
Definition: BTree.h:232
std::pair< KEY, VALUE > value_type
Definition: BTree.h:344
std::forward_iterator_tag iterator_category
Definition: BTree.h:343
const value_type keyValue_
Definition: BTree.h:48
const BTree & right() const
Definition: BTree.h:85
Const iterator Not trivial: iterator keeps a stack to indicate current path from root_.
Definition: BTree.h:299
static const Line3 l(Rot3(), 1, 1)
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 BTree left
Definition: BTree.h:49
const_iterator(const sharedNode &root)
Definition: BTree.h:353
BTree(const value_type &keyValue)
Definition: BTree.h:124
Node(const BTree &l, const value_type &keyValue, const BTree &r)
Definition: BTree.h:66
bool empty() const
Definition: BTree.h:140
const KEY & key() const
Definition: BTree.h:82
Point2(* f)(const Point3 &, OptionalJacobian< 2, 3 >)
RealScalar s
BTree(const BTree &l, const value_type &keyValue, const BTree &r)
Definition: BTree.h:129
std::stack< flagged > path_
Definition: BTree.h:307
BTree remove_min() const
Definition: BTree.h:201
const size_t height_
Definition: BTree.h:47
std::pair< sharedNode, bool > flagged
Definition: BTree.h:304
static std::stringstream ss
Definition: testBTree.cpp:31
const value_type * pointer
Definition: BTree.h:345
traits
Definition: chartTesting.h:28
reference operator*() const
Definition: BTree.h:372
bool operator!=(const Self &__x) const
Definition: BTree.h:367
const_iterator Self
Definition: BTree.h:303
const value_type & keyValue() const
Definition: BTree.h:81
const VALUE & value() const
Definition: BTree.h:72
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
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_iterator iterator
Definition: BTree.h:402
const VALUE & find(const KEY &k) const
Definition: BTree.h:241
pointer operator->() const
Definition: BTree.h:379
set noclip points set clip one set noclip two set bar set border lt lw set xdata set ydata set zdata set x2data set y2data set boxwidth set dummy x
const VALUE & value() const
Definition: BTree.h:83
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
Point2 t(10, 10)
const BTree right
Definition: BTree.h:49
bool same(const BTree &other) const
Definition: BTree.h:172
sharedNode root_
Definition: BTree.h:79


gtsam
Author(s):
autogenerated on Tue Jul 4 2023 02:33:59