Mercurial > hg > orthanc-stone
annotate UnitTestsSources/ComputationalGeometryTests.cpp @ 1873:e0966648ebd0
unit tests of SegmentTree
author | Sebastien Jodogne <s.jodogne@gmail.com> |
---|---|
date | Tue, 11 Jan 2022 15:36:04 +0100 |
parents | db8a8a19b543 |
children | 08f2476e8f5e |
rev | line source |
---|---|
1872 | 1 /** |
2 * Stone of Orthanc | |
3 * Copyright (C) 2012-2016 Sebastien Jodogne, Medical Physics | |
4 * Department, University Hospital of Liege, Belgium | |
5 * Copyright (C) 2017-2022 Osimis S.A., Belgium | |
6 * Copyright (C) 2021-2022 Sebastien Jodogne, ICTEAM UCLouvain, Belgium | |
7 * | |
8 * This program is free software: you can redistribute it and/or | |
9 * modify it under the terms of the GNU Affero General Public License | |
10 * as published by the Free Software Foundation, either version 3 of | |
11 * the License, or (at your option) any later version. | |
12 * | |
13 * This program is distributed in the hope that it will be useful, but | |
14 * WITHOUT ANY WARRANTY; without even the implied warranty of | |
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
16 * Affero General Public License for more details. | |
17 * | |
18 * You should have received a copy of the GNU Affero General Public License | |
19 * along with this program. If not, see <http://www.gnu.org/licenses/>. | |
20 **/ | |
21 | |
22 | |
23 #include <gtest/gtest.h> | |
24 | |
25 #include "../OrthancStone/Sources/Toolbox/SegmentTree.h" | |
26 | |
27 #include <Logging.h> | |
28 #include <OrthancException.h> | |
29 | |
30 | |
31 namespace | |
32 { | |
1873
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
33 typedef Orthanc::SingleValueObject<int> Counter; |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
34 |
1872 | 35 class CounterFactory : public OrthancStone::SegmentTree::IPayloadFactory |
36 { | |
1873
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
37 private: |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
38 int value_; |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
39 |
1872 | 40 public: |
1873
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
41 CounterFactory(int value) : |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
42 value_(value) |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
43 { |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
44 } |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
45 |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
46 virtual Orthanc::IDynamicObject* Create() ORTHANC_OVERRIDE |
1872 | 47 { |
1873
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
48 return new Counter(value_); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
49 } |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
50 }; |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
51 |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
52 class IncrementVisitor : public OrthancStone::SegmentTree::IVisitor |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
53 { |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
54 private: |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
55 int increment_; |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
56 |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
57 public: |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
58 IncrementVisitor(int increment) : |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
59 increment_(increment) |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
60 { |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
61 } |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
62 |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
63 virtual void Visit(const OrthancStone::SegmentTree& node, |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
64 bool fullyInside) ORTHANC_OVERRIDE |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
65 { |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
66 if (fullyInside) |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
67 { |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
68 Counter& payload = node.GetTypedPayload<Counter>(); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
69 |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
70 if (payload.GetValue() + increment_ < 0) |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
71 { |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
72 throw Orthanc::OrthancException(Orthanc::ErrorCode_InternalError); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
73 } |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
74 else |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
75 { |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
76 payload.SetValue(payload.GetValue() + increment_); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
77 } |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
78 } |
1872 | 79 } |
80 }; | |
81 } | |
82 | |
83 | |
1873
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
84 TEST(SegmentTree, Create) |
1872 | 85 { |
1873
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
86 CounterFactory factory(42); |
1872 | 87 OrthancStone::SegmentTree root(4u, 15u, factory); // Check out Figure 1.1 (page 14) from textbook |
88 | |
89 ASSERT_EQ(4u, root.GetLowBound()); | |
90 ASSERT_EQ(15u, root.GetHighBound()); | |
91 ASSERT_FALSE(root.IsLeaf()); | |
1873
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
92 ASSERT_EQ(42, root.GetTypedPayload<Counter>().GetValue()); |
1872 | 93 ASSERT_EQ(21u, root.CountNodes()); |
94 | |
1873
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
95 const OrthancStone::SegmentTree* n = &root.GetLeftChild(); |
1872 | 96 ASSERT_EQ(4u, n->GetLowBound()); |
97 ASSERT_EQ(9u, n->GetHighBound()); | |
98 ASSERT_FALSE(n->IsLeaf()); | |
99 ASSERT_EQ(9u, n->CountNodes()); | |
100 | |
101 n = &root.GetLeftChild().GetLeftChild(); | |
102 ASSERT_EQ(4u, n->GetLowBound()); | |
103 ASSERT_EQ(6u, n->GetHighBound()); | |
104 ASSERT_FALSE(n->IsLeaf()); | |
105 ASSERT_EQ(3u, n->CountNodes()); | |
106 | |
107 n = &root.GetLeftChild().GetLeftChild().GetLeftChild(); | |
108 ASSERT_EQ(4u, n->GetLowBound()); | |
109 ASSERT_EQ(5u, n->GetHighBound()); | |
110 ASSERT_TRUE(n->IsLeaf()); | |
111 ASSERT_THROW(n->GetLeftChild(), Orthanc::OrthancException); | |
112 ASSERT_THROW(n->GetRightChild(), Orthanc::OrthancException); | |
113 ASSERT_EQ(1u, n->CountNodes()); | |
114 | |
115 n = &root.GetLeftChild().GetLeftChild().GetRightChild(); | |
116 ASSERT_EQ(5u, n->GetLowBound()); | |
117 ASSERT_EQ(6u, n->GetHighBound()); | |
118 ASSERT_TRUE(n->IsLeaf()); | |
119 ASSERT_EQ(1u, n->CountNodes()); | |
120 | |
121 n = &root.GetLeftChild().GetRightChild(); | |
122 ASSERT_EQ(6u, n->GetLowBound()); | |
123 ASSERT_EQ(9u, n->GetHighBound()); | |
124 ASSERT_FALSE(n->IsLeaf()); | |
125 ASSERT_EQ(5u, n->CountNodes()); | |
126 | |
127 n = &root.GetLeftChild().GetRightChild().GetLeftChild(); | |
128 ASSERT_EQ(6u, n->GetLowBound()); | |
129 ASSERT_EQ(7u, n->GetHighBound()); | |
130 ASSERT_TRUE(n->IsLeaf()); | |
131 ASSERT_EQ(1u, n->CountNodes()); | |
132 | |
133 n = &root.GetLeftChild().GetRightChild().GetRightChild(); | |
134 ASSERT_EQ(7u, n->GetLowBound()); | |
135 ASSERT_EQ(9u, n->GetHighBound()); | |
136 ASSERT_FALSE(n->IsLeaf()); | |
137 ASSERT_EQ(3u, n->CountNodes()); | |
138 | |
139 n = &root.GetLeftChild().GetRightChild().GetRightChild().GetLeftChild(); | |
140 ASSERT_EQ(7u, n->GetLowBound()); | |
141 ASSERT_EQ(8u, n->GetHighBound()); | |
142 ASSERT_TRUE(n->IsLeaf()); | |
143 ASSERT_EQ(1u, n->CountNodes()); | |
144 | |
145 n = &root.GetLeftChild().GetRightChild().GetRightChild().GetRightChild(); | |
146 ASSERT_EQ(8u, n->GetLowBound()); | |
147 ASSERT_EQ(9u, n->GetHighBound()); | |
148 ASSERT_TRUE(n->IsLeaf()); | |
149 ASSERT_EQ(1u, n->CountNodes()); | |
150 | |
151 n = &root.GetRightChild(); | |
152 ASSERT_EQ(9u, n->GetLowBound()); | |
153 ASSERT_EQ(15u, n->GetHighBound()); | |
154 ASSERT_FALSE(n->IsLeaf()); | |
155 ASSERT_EQ(11u, n->CountNodes()); | |
156 | |
157 n = &root.GetRightChild().GetLeftChild(); | |
158 ASSERT_EQ(9u, n->GetLowBound()); | |
159 ASSERT_EQ(12u, n->GetHighBound()); | |
160 ASSERT_FALSE(n->IsLeaf()); | |
161 ASSERT_EQ(5u, n->CountNodes()); | |
162 | |
163 n = &root.GetRightChild().GetLeftChild().GetLeftChild(); | |
164 ASSERT_EQ(9u, n->GetLowBound()); | |
165 ASSERT_EQ(10u, n->GetHighBound()); | |
166 ASSERT_TRUE(n->IsLeaf()); | |
167 ASSERT_EQ(1u, n->CountNodes()); | |
168 | |
169 n = &root.GetRightChild().GetLeftChild().GetRightChild(); | |
170 ASSERT_EQ(10u, n->GetLowBound()); | |
171 ASSERT_EQ(12u, n->GetHighBound()); | |
172 ASSERT_FALSE(n->IsLeaf()); | |
173 ASSERT_EQ(3u, n->CountNodes()); | |
174 | |
175 n = &root.GetRightChild().GetLeftChild().GetRightChild().GetLeftChild(); | |
176 ASSERT_EQ(10u, n->GetLowBound()); | |
177 ASSERT_EQ(11u, n->GetHighBound()); | |
178 ASSERT_TRUE(n->IsLeaf()); | |
179 ASSERT_EQ(1u, n->CountNodes()); | |
180 | |
181 n = &root.GetRightChild().GetLeftChild().GetRightChild().GetRightChild(); | |
182 ASSERT_EQ(11u, n->GetLowBound()); | |
183 ASSERT_EQ(12u, n->GetHighBound()); | |
184 ASSERT_TRUE(n->IsLeaf()); | |
185 ASSERT_EQ(1u, n->CountNodes()); | |
186 | |
187 n = &root.GetRightChild().GetRightChild(); | |
188 ASSERT_EQ(12u, n->GetLowBound()); | |
189 ASSERT_EQ(15u, n->GetHighBound()); | |
190 ASSERT_FALSE(n->IsLeaf()); | |
191 ASSERT_EQ(5u, n->CountNodes()); | |
192 | |
193 n = &root.GetRightChild().GetRightChild().GetLeftChild(); | |
194 ASSERT_EQ(12u, n->GetLowBound()); | |
195 ASSERT_EQ(13u, n->GetHighBound()); | |
196 ASSERT_TRUE(n->IsLeaf()); | |
197 ASSERT_EQ(1u, n->CountNodes()); | |
198 | |
199 n = &root.GetRightChild().GetRightChild().GetRightChild(); | |
200 ASSERT_EQ(13u, n->GetLowBound()); | |
201 ASSERT_EQ(15u, n->GetHighBound()); | |
202 ASSERT_FALSE(n->IsLeaf()); | |
203 ASSERT_EQ(3u, n->CountNodes()); | |
204 | |
205 n = &root.GetRightChild().GetRightChild().GetRightChild().GetLeftChild(); | |
206 ASSERT_EQ(13u, n->GetLowBound()); | |
207 ASSERT_EQ(14u, n->GetHighBound()); | |
208 ASSERT_TRUE(n->IsLeaf()); | |
209 ASSERT_EQ(1u, n->CountNodes()); | |
210 | |
211 n = &root.GetRightChild().GetRightChild().GetRightChild().GetRightChild(); | |
212 ASSERT_EQ(14u, n->GetLowBound()); | |
213 ASSERT_EQ(15u, n->GetHighBound()); | |
214 ASSERT_TRUE(n->IsLeaf()); | |
215 ASSERT_EQ(1u, n->CountNodes()); | |
1873
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
216 |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
217 ASSERT_TRUE(root.FindLeaf(3) == NULL); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
218 for (size_t i = 4; i < 15; i++) |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
219 { |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
220 n = root.FindLeaf(i); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
221 ASSERT_TRUE(n != NULL); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
222 ASSERT_TRUE(n->IsLeaf()); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
223 ASSERT_EQ(i, n->GetLowBound()); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
224 ASSERT_EQ(i + 1, n->GetHighBound()); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
225 ASSERT_EQ(42, n->GetTypedPayload<Counter>().GetValue()); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
226 } |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
227 ASSERT_TRUE(root.FindLeaf(15) == NULL); |
1872 | 228 } |
1873
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
229 |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
230 |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
231 static bool CheckCounter(const OrthancStone::SegmentTree& node, |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
232 int expectedValue) |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
233 { |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
234 if (node.GetTypedPayload<Counter>().GetValue() != expectedValue) |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
235 { |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
236 return false; |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
237 } |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
238 else if (node.IsLeaf()) |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
239 { |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
240 return true; |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
241 } |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
242 else |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
243 { |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
244 return (CheckCounter(node.GetLeftChild(), expectedValue) && |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
245 CheckCounter(node.GetRightChild(), expectedValue)); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
246 } |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
247 } |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
248 |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
249 |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
250 #if 0 |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
251 static void Print(const OrthancStone::SegmentTree& node, |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
252 unsigned int indent) |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
253 { |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
254 for (size_t i = 0; i < indent; i++) |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
255 printf(" "); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
256 printf("(%lu,%lu): %d\n", node.GetLowBound(), node.GetHighBound(), node.GetTypedPayload<Counter>().GetValue()); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
257 if (!node.IsLeaf()) |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
258 { |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
259 Print(node.GetLeftChild(), indent + 1); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
260 Print(node.GetRightChild(), indent + 1); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
261 } |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
262 } |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
263 #endif |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
264 |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
265 |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
266 TEST(SegmentTree, Visit) |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
267 { |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
268 CounterFactory factory(0); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
269 OrthancStone::SegmentTree root(4u, 15u, factory); // Check out Figure 1.1 (page 14) from textbook |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
270 |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
271 ASSERT_TRUE(CheckCounter(root, 0)); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
272 |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
273 IncrementVisitor plus(1); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
274 IncrementVisitor minus(-1); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
275 |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
276 root.VisitSegment(0, 20, plus); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
277 ASSERT_EQ(1, root.GetTypedPayload<Counter>().GetValue()); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
278 ASSERT_TRUE(CheckCounter(root.GetLeftChild(), 0)); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
279 ASSERT_TRUE(CheckCounter(root.GetRightChild(), 0)); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
280 |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
281 root.VisitSegment(0, 20, plus); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
282 ASSERT_EQ(2, root.GetTypedPayload<Counter>().GetValue()); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
283 ASSERT_TRUE(CheckCounter(root.GetLeftChild(), 0)); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
284 ASSERT_TRUE(CheckCounter(root.GetRightChild(), 0)); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
285 |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
286 root.VisitSegment(0, 20, minus); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
287 root.VisitSegment(0, 20, minus); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
288 ASSERT_TRUE(CheckCounter(root, 0)); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
289 |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
290 root.VisitSegment(8, 11, plus); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
291 ASSERT_EQ(0, root.FindNode(4, 15)->GetTypedPayload<Counter>().GetValue()); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
292 ASSERT_EQ(0, root.FindNode(4, 9)->GetTypedPayload<Counter>().GetValue()); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
293 ASSERT_EQ(0, root.FindNode(4, 6)->GetTypedPayload<Counter>().GetValue()); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
294 ASSERT_EQ(0, root.FindNode(4, 5)->GetTypedPayload<Counter>().GetValue()); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
295 ASSERT_EQ(0, root.FindNode(5, 6)->GetTypedPayload<Counter>().GetValue()); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
296 ASSERT_EQ(0, root.FindNode(6, 9)->GetTypedPayload<Counter>().GetValue()); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
297 ASSERT_EQ(0, root.FindNode(6, 7)->GetTypedPayload<Counter>().GetValue()); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
298 ASSERT_EQ(0, root.FindNode(7, 9)->GetTypedPayload<Counter>().GetValue()); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
299 ASSERT_EQ(0, root.FindNode(7, 8)->GetTypedPayload<Counter>().GetValue()); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
300 ASSERT_EQ(1, root.FindNode(8, 9)->GetTypedPayload<Counter>().GetValue()); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
301 ASSERT_EQ(0, root.FindNode(9, 15)->GetTypedPayload<Counter>().GetValue()); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
302 ASSERT_EQ(0, root.FindNode(9, 12)->GetTypedPayload<Counter>().GetValue()); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
303 ASSERT_EQ(1, root.FindNode(9, 10)->GetTypedPayload<Counter>().GetValue()); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
304 ASSERT_EQ(0, root.FindNode(10, 12)->GetTypedPayload<Counter>().GetValue()); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
305 ASSERT_EQ(1, root.FindNode(10, 11)->GetTypedPayload<Counter>().GetValue()); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
306 ASSERT_EQ(0, root.FindNode(11, 12)->GetTypedPayload<Counter>().GetValue()); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
307 ASSERT_EQ(0, root.FindNode(12, 15)->GetTypedPayload<Counter>().GetValue()); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
308 ASSERT_EQ(0, root.FindNode(12, 13)->GetTypedPayload<Counter>().GetValue()); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
309 ASSERT_EQ(0, root.FindNode(13, 15)->GetTypedPayload<Counter>().GetValue()); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
310 ASSERT_EQ(0, root.FindNode(13, 14)->GetTypedPayload<Counter>().GetValue()); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
311 ASSERT_EQ(0, root.FindNode(14, 15)->GetTypedPayload<Counter>().GetValue()); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
312 |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
313 root.VisitSegment(9, 11, minus); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
314 ASSERT_EQ(0, root.FindNode(4, 15)->GetTypedPayload<Counter>().GetValue()); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
315 ASSERT_EQ(0, root.FindNode(4, 9)->GetTypedPayload<Counter>().GetValue()); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
316 ASSERT_EQ(0, root.FindNode(4, 6)->GetTypedPayload<Counter>().GetValue()); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
317 ASSERT_EQ(0, root.FindNode(4, 5)->GetTypedPayload<Counter>().GetValue()); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
318 ASSERT_EQ(0, root.FindNode(5, 6)->GetTypedPayload<Counter>().GetValue()); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
319 ASSERT_EQ(0, root.FindNode(6, 9)->GetTypedPayload<Counter>().GetValue()); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
320 ASSERT_EQ(0, root.FindNode(6, 7)->GetTypedPayload<Counter>().GetValue()); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
321 ASSERT_EQ(0, root.FindNode(7, 9)->GetTypedPayload<Counter>().GetValue()); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
322 ASSERT_EQ(0, root.FindNode(7, 8)->GetTypedPayload<Counter>().GetValue()); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
323 ASSERT_EQ(1, root.FindNode(8, 9)->GetTypedPayload<Counter>().GetValue()); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
324 ASSERT_TRUE(CheckCounter(root.GetRightChild(), 0)); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
325 |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
326 root.VisitSegment(8, 9, minus); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
327 ASSERT_TRUE(CheckCounter(root, 0)); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
328 } |