Mercurial > hg > orthanc-stone

comparison UnitTestsSources/ComputationalGeometryTests.cpp @ 1873:e0966648ebd0

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
unit tests of SegmentTree
author Sebastien Jodogne <s.jodogne@gmail.com>
date Tue, 11 Jan 2022 15:36:04 +0100
parents db8a8a19b543
children 08f2476e8f5e
comparison
equal deleted inserted replaced
1872:db8a8a19b543 1873:e0966648ebd0
28 #include <OrthancException.h> 28 #include <OrthancException.h>
29 29
30 30
31 namespace 31 namespace
32 { 32 {
33 typedef Orthanc::SingleValueObject<int> Counter;
34
33 class CounterFactory : public OrthancStone::SegmentTree::IPayloadFactory 35 class CounterFactory : public OrthancStone::SegmentTree::IPayloadFactory
34 { 36 {
37 private:
38 int value_;
39
35 public: 40 public:
36 virtual Orthanc::IDynamicObject* Create() 41 CounterFactory(int value) :
42 value_(value)
37 { 43 {
38 return new Orthanc::SingleValueObject<int>(42); 44 }
45
46 virtual Orthanc::IDynamicObject* Create() ORTHANC_OVERRIDE
47 {
48 return new Counter(value_);
39 } 49 }
40 }; 50 };
41 } 51
42 52 class IncrementVisitor : public OrthancStone::SegmentTree::IVisitor
43 53 {
44 TEST(SegmentTree, Basic) 54 private:
45 { 55 int increment_;
46 CounterFactory factory; 56
57 public:
58 IncrementVisitor(int increment) :
59 increment_(increment)
60 {
61 }
62
63 virtual void Visit(const OrthancStone::SegmentTree& node,
64 bool fullyInside) ORTHANC_OVERRIDE
65 {
66 if (fullyInside)
67 {
68 Counter& payload = node.GetTypedPayload<Counter>();
69
70 if (payload.GetValue() + increment_ < 0)
71 {
72 throw Orthanc::OrthancException(Orthanc::ErrorCode_InternalError);
73 }
74 else
75 {
76 payload.SetValue(payload.GetValue() + increment_);
77 }
78 }
79 }
80 };
81 }
82
83
84 TEST(SegmentTree, Create)
85 {
86 CounterFactory factory(42);
47 OrthancStone::SegmentTree root(4u, 15u, factory); // Check out Figure 1.1 (page 14) from textbook 87 OrthancStone::SegmentTree root(4u, 15u, factory); // Check out Figure 1.1 (page 14) from textbook
48 88
49 ASSERT_EQ(4u, root.GetLowBound()); 89 ASSERT_EQ(4u, root.GetLowBound());
50 ASSERT_EQ(15u, root.GetHighBound()); 90 ASSERT_EQ(15u, root.GetHighBound());
51 ASSERT_FALSE(root.IsLeaf()); 91 ASSERT_FALSE(root.IsLeaf());
52 ASSERT_EQ(42, root.GetTypedPayload< Orthanc::SingleValueObject<int> >().GetValue()); 92 ASSERT_EQ(42, root.GetTypedPayload<Counter>().GetValue());
53 ASSERT_EQ(21u, root.CountNodes()); 93 ASSERT_EQ(21u, root.CountNodes());
54 94
55 OrthancStone::SegmentTree* n = &root.GetLeftChild(); 95 const OrthancStone::SegmentTree* n = &root.GetLeftChild();
56 ASSERT_EQ(4u, n->GetLowBound()); 96 ASSERT_EQ(4u, n->GetLowBound());
57 ASSERT_EQ(9u, n->GetHighBound()); 97 ASSERT_EQ(9u, n->GetHighBound());
58 ASSERT_FALSE(n->IsLeaf()); 98 ASSERT_FALSE(n->IsLeaf());
59 ASSERT_EQ(9u, n->CountNodes()); 99 ASSERT_EQ(9u, n->CountNodes());
60 100
171 n = &root.GetRightChild().GetRightChild().GetRightChild().GetRightChild(); 211 n = &root.GetRightChild().GetRightChild().GetRightChild().GetRightChild();
172 ASSERT_EQ(14u, n->GetLowBound()); 212 ASSERT_EQ(14u, n->GetLowBound());
173 ASSERT_EQ(15u, n->GetHighBound()); 213 ASSERT_EQ(15u, n->GetHighBound());
174 ASSERT_TRUE(n->IsLeaf()); 214 ASSERT_TRUE(n->IsLeaf());
175 ASSERT_EQ(1u, n->CountNodes()); 215 ASSERT_EQ(1u, n->CountNodes());
176 } 216
217 ASSERT_TRUE(root.FindLeaf(3) == NULL);
218 for (size_t i = 4; i < 15; i++)
219 {
220 n = root.FindLeaf(i);
221 ASSERT_TRUE(n != NULL);
222 ASSERT_TRUE(n->IsLeaf());
223 ASSERT_EQ(i, n->GetLowBound());
224 ASSERT_EQ(i + 1, n->GetHighBound());
225 ASSERT_EQ(42, n->GetTypedPayload<Counter>().GetValue());
226 }
227 ASSERT_TRUE(root.FindLeaf(15) == NULL);
228 }
229
230
231 static bool CheckCounter(const OrthancStone::SegmentTree& node,
232 int expectedValue)
233 {
234 if (node.GetTypedPayload<Counter>().GetValue() != expectedValue)
235 {
236 return false;
237 }
238 else if (node.IsLeaf())
239 {
240 return true;
241 }
242 else
243 {
244 return (CheckCounter(node.GetLeftChild(), expectedValue) &&
245 CheckCounter(node.GetRightChild(), expectedValue));
246 }
247 }
248
249
250 #if 0
251 static void Print(const OrthancStone::SegmentTree& node,
252 unsigned int indent)
253 {
254 for (size_t i = 0; i < indent; i++)
255 printf(" ");
256 printf("(%lu,%lu): %d\n", node.GetLowBound(), node.GetHighBound(), node.GetTypedPayload<Counter>().GetValue());
257 if (!node.IsLeaf())
258 {
259 Print(node.GetLeftChild(), indent + 1);
260 Print(node.GetRightChild(), indent + 1);
261 }
262 }
263 #endif
264
265
266 TEST(SegmentTree, Visit)
267 {
268 CounterFactory factory(0);
269 OrthancStone::SegmentTree root(4u, 15u, factory); // Check out Figure 1.1 (page 14) from textbook
270
271 ASSERT_TRUE(CheckCounter(root, 0));
272
273 IncrementVisitor plus(1);
274 IncrementVisitor minus(-1);
275
276 root.VisitSegment(0, 20, plus);
277 ASSERT_EQ(1, root.GetTypedPayload<Counter>().GetValue());
278 ASSERT_TRUE(CheckCounter(root.GetLeftChild(), 0));
279 ASSERT_TRUE(CheckCounter(root.GetRightChild(), 0));
280
281 root.VisitSegment(0, 20, plus);
282 ASSERT_EQ(2, root.GetTypedPayload<Counter>().GetValue());
283 ASSERT_TRUE(CheckCounter(root.GetLeftChild(), 0));
284 ASSERT_TRUE(CheckCounter(root.GetRightChild(), 0));
285
286 root.VisitSegment(0, 20, minus);
287 root.VisitSegment(0, 20, minus);
288 ASSERT_TRUE(CheckCounter(root, 0));
289
290 root.VisitSegment(8, 11, plus);
291 ASSERT_EQ(0, root.FindNode(4, 15)->GetTypedPayload<Counter>().GetValue());
292 ASSERT_EQ(0, root.FindNode(4, 9)->GetTypedPayload<Counter>().GetValue());
293 ASSERT_EQ(0, root.FindNode(4, 6)->GetTypedPayload<Counter>().GetValue());
294 ASSERT_EQ(0, root.FindNode(4, 5)->GetTypedPayload<Counter>().GetValue());
295 ASSERT_EQ(0, root.FindNode(5, 6)->GetTypedPayload<Counter>().GetValue());
296 ASSERT_EQ(0, root.FindNode(6, 9)->GetTypedPayload<Counter>().GetValue());
297 ASSERT_EQ(0, root.FindNode(6, 7)->GetTypedPayload<Counter>().GetValue());
298 ASSERT_EQ(0, root.FindNode(7, 9)->GetTypedPayload<Counter>().GetValue());
299 ASSERT_EQ(0, root.FindNode(7, 8)->GetTypedPayload<Counter>().GetValue());
300 ASSERT_EQ(1, root.FindNode(8, 9)->GetTypedPayload<Counter>().GetValue());
301 ASSERT_EQ(0, root.FindNode(9, 15)->GetTypedPayload<Counter>().GetValue());
302 ASSERT_EQ(0, root.FindNode(9, 12)->GetTypedPayload<Counter>().GetValue());
303 ASSERT_EQ(1, root.FindNode(9, 10)->GetTypedPayload<Counter>().GetValue());
304 ASSERT_EQ(0, root.FindNode(10, 12)->GetTypedPayload<Counter>().GetValue());
305 ASSERT_EQ(1, root.FindNode(10, 11)->GetTypedPayload<Counter>().GetValue());
306 ASSERT_EQ(0, root.FindNode(11, 12)->GetTypedPayload<Counter>().GetValue());
307 ASSERT_EQ(0, root.FindNode(12, 15)->GetTypedPayload<Counter>().GetValue());
308 ASSERT_EQ(0, root.FindNode(12, 13)->GetTypedPayload<Counter>().GetValue());
309 ASSERT_EQ(0, root.FindNode(13, 15)->GetTypedPayload<Counter>().GetValue());
310 ASSERT_EQ(0, root.FindNode(13, 14)->GetTypedPayload<Counter>().GetValue());
311 ASSERT_EQ(0, root.FindNode(14, 15)->GetTypedPayload<Counter>().GetValue());
312
313 root.VisitSegment(9, 11, minus);
314 ASSERT_EQ(0, root.FindNode(4, 15)->GetTypedPayload<Counter>().GetValue());
315 ASSERT_EQ(0, root.FindNode(4, 9)->GetTypedPayload<Counter>().GetValue());
316 ASSERT_EQ(0, root.FindNode(4, 6)->GetTypedPayload<Counter>().GetValue());
317 ASSERT_EQ(0, root.FindNode(4, 5)->GetTypedPayload<Counter>().GetValue());
318 ASSERT_EQ(0, root.FindNode(5, 6)->GetTypedPayload<Counter>().GetValue());
319 ASSERT_EQ(0, root.FindNode(6, 9)->GetTypedPayload<Counter>().GetValue());
320 ASSERT_EQ(0, root.FindNode(6, 7)->GetTypedPayload<Counter>().GetValue());
321 ASSERT_EQ(0, root.FindNode(7, 9)->GetTypedPayload<Counter>().GetValue());
322 ASSERT_EQ(0, root.FindNode(7, 8)->GetTypedPayload<Counter>().GetValue());
323 ASSERT_EQ(1, root.FindNode(8, 9)->GetTypedPayload<Counter>().GetValue());
324 ASSERT_TRUE(CheckCounter(root.GetRightChild(), 0));
325
326 root.VisitSegment(8, 9, minus);
327 ASSERT_TRUE(CheckCounter(root, 0));
328 }