testBTree.cpp
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 
21 
22 #include <list>
23 
24 using namespace std;
25 using namespace gtsam;
26 
27 typedef pair<size_t, size_t> Range;
30 
31 static std::stringstream ss;
32 static string x1("x1"), x2("x2"), x3("x3"), x4("x4"), x5("x5");
33 typedef pair<string, int> KeyInt;
34 KeyInt p1(x1, 1), p2(x2, 2), p3(x3, 3), p4(x4, 4), p5(x5, 5);
35 
36 /* ************************************************************************* */
37 int f(const string& key, const Range& range) {
38  return range.first;
39 }
40 
41 void g(const string& key, int i) {
42  ss << (string) key;
43 }
44 
45 int add(const string& k, int v, int a) {
46  return v + a;
47 }
48 
49 /* ************************************************************************* */
51 {
53  CHECK(tree.empty())
54  LONGS_EQUAL(0,tree.height())
55 
56  // check the height of tree after adding an element
57  RangeTree tree1 = tree.add(x1, Range(1, 1));
58  LONGS_EQUAL(1,tree1.height())
59  LONGS_EQUAL(1,tree1.size())
60  CHECK(tree1.find(x1) == Range(1,1))
61 
62  RangeTree tree2 = tree1.add(x5, Range(5, 2));
63  RangeTree tree3 = tree2.add(x3, Range(3, 3));
64  LONGS_EQUAL(3,tree3.size())
65  CHECK(tree3.find(x5) == Range(5,2))
66  CHECK(tree3.find(x3) == Range(3,3))
67 
68  RangeTree tree4 = tree3.add(x2, Range(2, 4));
69  RangeTree tree5 = tree4.add(x4, Range(4, 5));
70  LONGS_EQUAL(5,tree5.size())
71  CHECK(tree5.find(x4) == Range(4,5))
72 
73  // Test functional nature: tree5 and tree6 have different values for x4
74  RangeTree tree6 = tree5.add(x4, Range(6, 6));
75  CHECK(tree5.find(x4) == Range(4,5))
76  CHECK(tree6.find(x4) == Range(6,6))
77 
78  // test assignment
79  RangeTree c5 = tree5;
80  LONGS_EQUAL(5,c5.size())
81  CHECK(c5.find(x4) == Range(4,5))
82 
83  // test map
84  // After (map f tree5) tree contains (x1,1), (x2,2), etc...
85  IntTree mapped = tree5.map<int> (f);
86  LONGS_EQUAL(2,mapped.find(x2));
87  LONGS_EQUAL(4,mapped.find(x4));
88 }
89 
90 /* ************************************************************************* */
92 {
93  IntTree tree1 = IntTree().add(p1).add(p2).add(p3).add(p4).add(p5);
94  CHECK(tree1==tree1)
95  CHECK(tree1.same(tree1))
96 
97  IntTree tree2 = IntTree().add(p1).add(p2).add(p3).add(p4).add(p5);
98  CHECK(tree2==tree1)
99  CHECK(!tree2.same(tree1))
100 
101  IntTree tree3 = IntTree().add(p1).add(p2).add(p3).add(p4);
102  CHECK(tree3!=tree1)
103  CHECK(tree3!=tree2)
104  CHECK(!tree3.same(tree1))
105  CHECK(!tree3.same(tree2))
106 
107  IntTree tree4 = tree3.add(p5);
108  CHECK(tree4==tree1)
109  CHECK(!tree4.same(tree1))
110 
111  IntTree tree5 = tree1;
112  CHECK(tree5==tree1)
113  CHECK(tree5==tree2)
114  CHECK(tree5.same(tree1))
115  CHECK(!tree5.same(tree2))
116 }
117 
118 /* ************************************************************************* */
119 TEST( BTree, iterating )
120 {
121  IntTree tree = IntTree().add(p1).add(p2).add(p3).add(p4).add(p5);
122 
123  // test iter
124  tree.iter(g);
125  CHECK(ss.str() == string("x1x2x3x4x5"));
126 
127  // test fold
128  LONGS_EQUAL(25,tree.fold<int>(add,10))
129 
130  // test iterator
131  BTree<string, int>::const_iterator it = tree.begin(), it2 = tree.begin();
132  CHECK(it==it2)
133  CHECK(*it == p1)
134  CHECK(it->first == x1)
135  CHECK(it->second == 1)
136  CHECK(*(++it) == p2)
137  CHECK(it!=it2)
138  CHECK(it==(++it2))
139  CHECK(*(++it) == p3)
140  CHECK(*(it++) == p3)
141  // post-increment, not so efficient
142  CHECK(*it == p4)
143  CHECK(*(++it) == p5)
144  CHECK((++it)==tree.end())
145 
146  // acid iterator test
147  int sum = 0;
148  for (const KeyInt& p : tree) sum += p.second;
149  LONGS_EQUAL(15,sum)
150 
151  // STL iterator test
152  auto expected = std::list<KeyInt> {p1, p2, p3, p4, p5};
153  std::list<KeyInt> actual;
154  copy (tree.begin(),tree.end(),back_inserter(actual));
155  CHECK(actual==expected)
156 }
157 
158 /* ************************************************************************* */
159 TEST( BTree, remove )
160 {
161  IntTree tree5 = IntTree().add(p1).add(p2).add(p3).add(p4).add(p5);
162  LONGS_EQUAL(5,tree5.size())
163  CHECK(tree5.mem(x3))
164  IntTree tree4 = tree5.remove(x3);
165  LONGS_EQUAL(4,tree4.size())
166  CHECK(!tree4.mem(x3))
167 }
168 
169 /* ************************************************************************* */
170 TEST( BTree, stress )
171 {
172  RangeTree tree;
173  list<RangeTree::value_type> expected;
174  int N = 128;
175  for (int i = 1; i <= N; i++) {
176  string key('a', i);
177  Range value(i - 1, i);
178  tree = tree.add(key, value);
179  LONGS_EQUAL(i,tree.size())
180  CHECK(tree.find(key) == value)
181  expected.emplace_back(key, value);
182  }
183 
184  // Check height is log(N)
185  LONGS_EQUAL(8,tree.height())
186 
187  // stress test iterator
188  list<RangeTree::value_type> actual;
189  copy(tree.begin(), tree.end(), back_inserter(actual));
190  CHECK(actual==expected)
191 
192  // deconstruct the tree
193  for (int i = N; i >= N; i--) {
194  string key('a', i);
195  tree = tree.remove(key);
196  LONGS_EQUAL(i-1,tree.size())
197  CHECK(!tree.mem(key))
198  }
199 }
200 
201 /* ************************************************************************* */
202 int main() {
203  TestResult tr;
204  return TestRegistry::runAllTests(tr);
205 }
206 /* ************************************************************************* */
const gtsam::Symbol key('X', 0)
#define CHECK(condition)
Definition: Test.h:108
static string x3("x3")
bool mem(const KEY &x) const
Definition: BTree.h:162
static int runAllTests(TestResult &result)
Binary tree.
Definition: BTree.h:34
int f(const string &key, const Range &range)
Definition: testBTree.cpp:37
Matrix expected
Definition: testMatrix.cpp:971
KeyInt p4(x4, 4)
static string x2("x2")
BTree< string, int > IntTree
Definition: testBTree.cpp:29
size_t size() const
Definition: BTree.h:232
Definition: BFloat16.h:88
purely functional binary tree
TEST(BTree, add)
Definition: testBTree.cpp:50
#define N
Definition: gksort.c:12
static string x5("x5")
void g(const string &key, int i)
Definition: testBTree.cpp:41
int main()
Definition: testBTree.cpp:202
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
KeyInt p1(x1, 1)
Array< int, Dynamic, 1 > v
bool empty() const
Definition: BTree.h:140
KeyInt p5(x5, 5)
BTree< string, Range > RangeTree
Definition: testBTree.cpp:28
BTree remove(const KEY &x) const
Definition: BTree.h:216
pair< size_t, size_t > Range
Definition: testBTree.cpp:27
static std::stringstream ss
Definition: testBTree.cpp:31
#define LONGS_EQUAL(expected, actual)
Definition: Test.h:134
KeyInt p3(x3, 3)
traits
Definition: chartTesting.h:28
KeyInt p2(x2, 2)
static string x1("x1")
BTree add(const value_type &xd) const
Definition: BTree.h:145
Double_ range(const Point2_ &p, const Point2_ &q)
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
float * p
const_iterator end() const
Definition: BTree.h:410
bool equality(const Errors &actual, const Errors &expected, double tol)
Definition: Errors.cpp:52
const VALUE & find(const KEY &k) const
Definition: BTree.h:241
static string x4("x4")
int add(const string &k, int v, int a)
Definition: testBTree.cpp:45
pair< string, int > KeyInt
Definition: testBTree.cpp:33
size_t height() const
Definition: BTree.h:227
bool same(const BTree &other) const
Definition: BTree.h:172


gtsam
Author(s):
autogenerated on Tue Jul 4 2023 02:37:58