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
12/**
13 * @file testBTree.cpp
14 * @date Feb 3, 2010
15 * @author Chris Beall
16 * @author Frank Dellaert
17 */
18
19#include <CppUnitLite/TestHarness.h>
20#include <gtsam_unstable/base/BTree.h>
21
22#include <list>
23
24using namespace std;
25using namespace gtsam;
26
27typedef pair<size_t, size_t> Range;
28typedef BTree<string, Range> RangeTree;
29typedef BTree<string, int> IntTree;
30
31static std::stringstream ss;
32static string x1("x1"), x2("x2"), x3("x3"), x4("x4"), x5("x5");
33typedef pair<string, int> KeyInt;
34KeyInt p1(x1, 1), p2(x2, 2), p3(x3, 3), p4(x4, 4), p5(x5, 5);
35
36/* ************************************************************************* */
37int f(const string& key, const Range& range) {
38 return range.first;
39}
40
41void g(const string& key, int i) {
42 ss << (string) key;
43}
44
45int add(const string& k, int v, int a) {
46 return v + a;
47}
48
49/* ************************************************************************* */
50TEST( BTree, add )
51{
52 RangeTree tree;
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(x: x1, d: 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(x: x5, d: Range(5, 2));
63 RangeTree tree3 = tree2.add(x: x3, d: 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(x: x2, d: Range(2, 4));
69 RangeTree tree5 = tree4.add(x: x4, d: 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(x: x4, d: 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/* ************************************************************************* */
91TEST( BTree, equality )
92{
93 IntTree tree1 = IntTree().add(xd: p1).add(xd: p2).add(xd: p3).add(xd: p4).add(xd: p5);
94 CHECK(tree1==tree1)
95 CHECK(tree1.same(tree1))
96
97 IntTree tree2 = IntTree().add(xd: p1).add(xd: p2).add(xd: p3).add(xd: p4).add(xd: p5);
98 CHECK(tree2==tree1)
99 CHECK(!tree2.same(tree1))
100
101 IntTree tree3 = IntTree().add(xd: p1).add(xd: p2).add(xd: p3).add(xd: 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(xd: 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/* ************************************************************************* */
119TEST( BTree, iterating )
120{
121 IntTree tree = IntTree().add(xd: p1).add(xd: p2).add(xd: p3).add(xd: p4).add(xd: p5);
122
123 // test iter
124 tree.iter(f: 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 (first: tree.begin(),last: tree.end(),result: back_inserter(x&: actual));
155 CHECK(actual==expected)
156}
157
158/* ************************************************************************* */
159TEST( BTree, remove )
160{
161 IntTree tree5 = IntTree().add(xd: p1).add(xd: p2).add(xd: p3).add(xd: p4).add(xd: p5);
162 LONGS_EQUAL(5,tree5.size())
163 CHECK(tree5.mem(x3))
164 IntTree tree4 = tree5.remove(x: x3);
165 LONGS_EQUAL(4,tree4.size())
166 CHECK(!tree4.mem(x3))
167}
168
169/* ************************************************************************* */
170TEST( 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(x: key, d: value);
179 LONGS_EQUAL(i,tree.size())
180 CHECK(tree.find(key) == value)
181 expected.emplace_back(args&: key, args&: 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(first: tree.begin(), last: tree.end(), result: back_inserter(x&: 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(x: key);
196 LONGS_EQUAL(i-1,tree.size())
197 CHECK(!tree.mem(key))
198 }
199}
200
201/* ************************************************************************* */
202int main() {
203 TestResult tr;
204 return TestRegistry::runAllTests(result&: tr);
205}
206/* ************************************************************************* */
207