Mercurial > hg > orthanc-stone

comparison UnitTestsSources/ComputationalGeometryTests.cpp @ 1872:db8a8a19b543

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
SegmentTree
author Sebastien Jodogne <s.jodogne@gmail.com>
date Tue, 11 Jan 2022 12:15:22 +0100
parents
children e0966648ebd0
comparison
equal deleted inserted replaced
1871:7053b8a0aaec 1872:db8a8a19b543
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 {
33 class CounterFactory : public OrthancStone::SegmentTree::IPayloadFactory
34 {
35 public:
36 virtual Orthanc::IDynamicObject* Create()
37 {
38 return new Orthanc::SingleValueObject<int>(42);
39 }
40 };
41 }
42
43
44 TEST(SegmentTree, Basic)
45 {
46 CounterFactory factory;
47 OrthancStone::SegmentTree root(4u, 15u, factory); // Check out Figure 1.1 (page 14) from textbook
48
49 ASSERT_EQ(4u, root.GetLowBound());
50 ASSERT_EQ(15u, root.GetHighBound());
51 ASSERT_FALSE(root.IsLeaf());
52 ASSERT_EQ(42, root.GetTypedPayload< Orthanc::SingleValueObject<int> >().GetValue());
53 ASSERT_EQ(21u, root.CountNodes());
54
55 OrthancStone::SegmentTree* n = &root.GetLeftChild();
56 ASSERT_EQ(4u, n->GetLowBound());
57 ASSERT_EQ(9u, n->GetHighBound());
58 ASSERT_FALSE(n->IsLeaf());
59 ASSERT_EQ(9u, n->CountNodes());
60
61 n = &root.GetLeftChild().GetLeftChild();
62 ASSERT_EQ(4u, n->GetLowBound());
63 ASSERT_EQ(6u, n->GetHighBound());
64 ASSERT_FALSE(n->IsLeaf());
65 ASSERT_EQ(3u, n->CountNodes());
66
67 n = &root.GetLeftChild().GetLeftChild().GetLeftChild();
68 ASSERT_EQ(4u, n->GetLowBound());
69 ASSERT_EQ(5u, n->GetHighBound());
70 ASSERT_TRUE(n->IsLeaf());
71 ASSERT_THROW(n->GetLeftChild(), Orthanc::OrthancException);
72 ASSERT_THROW(n->GetRightChild(), Orthanc::OrthancException);
73 ASSERT_EQ(1u, n->CountNodes());
74
75 n = &root.GetLeftChild().GetLeftChild().GetRightChild();
76 ASSERT_EQ(5u, n->GetLowBound());
77 ASSERT_EQ(6u, n->GetHighBound());
78 ASSERT_TRUE(n->IsLeaf());
79 ASSERT_EQ(1u, n->CountNodes());
80
81 n = &root.GetLeftChild().GetRightChild();
82 ASSERT_EQ(6u, n->GetLowBound());
83 ASSERT_EQ(9u, n->GetHighBound());
84 ASSERT_FALSE(n->IsLeaf());
85 ASSERT_EQ(5u, n->CountNodes());
86
87 n = &root.GetLeftChild().GetRightChild().GetLeftChild();
88 ASSERT_EQ(6u, n->GetLowBound());
89 ASSERT_EQ(7u, n->GetHighBound());
90 ASSERT_TRUE(n->IsLeaf());
91 ASSERT_EQ(1u, n->CountNodes());
92
93 n = &root.GetLeftChild().GetRightChild().GetRightChild();
94 ASSERT_EQ(7u, n->GetLowBound());
95 ASSERT_EQ(9u, n->GetHighBound());
96 ASSERT_FALSE(n->IsLeaf());
97 ASSERT_EQ(3u, n->CountNodes());
98
99 n = &root.GetLeftChild().GetRightChild().GetRightChild().GetLeftChild();
100 ASSERT_EQ(7u, n->GetLowBound());
101 ASSERT_EQ(8u, n->GetHighBound());
102 ASSERT_TRUE(n->IsLeaf());
103 ASSERT_EQ(1u, n->CountNodes());
104
105 n = &root.GetLeftChild().GetRightChild().GetRightChild().GetRightChild();
106 ASSERT_EQ(8u, n->GetLowBound());
107 ASSERT_EQ(9u, n->GetHighBound());
108 ASSERT_TRUE(n->IsLeaf());
109 ASSERT_EQ(1u, n->CountNodes());
110
111 n = &root.GetRightChild();
112 ASSERT_EQ(9u, n->GetLowBound());
113 ASSERT_EQ(15u, n->GetHighBound());
114 ASSERT_FALSE(n->IsLeaf());
115 ASSERT_EQ(11u, n->CountNodes());
116
117 n = &root.GetRightChild().GetLeftChild();
118 ASSERT_EQ(9u, n->GetLowBound());
119 ASSERT_EQ(12u, n->GetHighBound());
120 ASSERT_FALSE(n->IsLeaf());
121 ASSERT_EQ(5u, n->CountNodes());
122
123 n = &root.GetRightChild().GetLeftChild().GetLeftChild();
124 ASSERT_EQ(9u, n->GetLowBound());
125 ASSERT_EQ(10u, n->GetHighBound());
126 ASSERT_TRUE(n->IsLeaf());
127 ASSERT_EQ(1u, n->CountNodes());
128
129 n = &root.GetRightChild().GetLeftChild().GetRightChild();
130 ASSERT_EQ(10u, n->GetLowBound());
131 ASSERT_EQ(12u, n->GetHighBound());
132 ASSERT_FALSE(n->IsLeaf());
133 ASSERT_EQ(3u, n->CountNodes());
134
135 n = &root.GetRightChild().GetLeftChild().GetRightChild().GetLeftChild();
136 ASSERT_EQ(10u, n->GetLowBound());
137 ASSERT_EQ(11u, n->GetHighBound());
138 ASSERT_TRUE(n->IsLeaf());
139 ASSERT_EQ(1u, n->CountNodes());
140
141 n = &root.GetRightChild().GetLeftChild().GetRightChild().GetRightChild();
142 ASSERT_EQ(11u, n->GetLowBound());
143 ASSERT_EQ(12u, n->GetHighBound());
144 ASSERT_TRUE(n->IsLeaf());
145 ASSERT_EQ(1u, n->CountNodes());
146
147 n = &root.GetRightChild().GetRightChild();
148 ASSERT_EQ(12u, n->GetLowBound());
149 ASSERT_EQ(15u, n->GetHighBound());
150 ASSERT_FALSE(n->IsLeaf());
151 ASSERT_EQ(5u, n->CountNodes());
152
153 n = &root.GetRightChild().GetRightChild().GetLeftChild();
154 ASSERT_EQ(12u, n->GetLowBound());
155 ASSERT_EQ(13u, n->GetHighBound());
156 ASSERT_TRUE(n->IsLeaf());
157 ASSERT_EQ(1u, n->CountNodes());
158
159 n = &root.GetRightChild().GetRightChild().GetRightChild();
160 ASSERT_EQ(13u, n->GetLowBound());
161 ASSERT_EQ(15u, n->GetHighBound());
162 ASSERT_FALSE(n->IsLeaf());
163 ASSERT_EQ(3u, n->CountNodes());
164
165 n = &root.GetRightChild().GetRightChild().GetRightChild().GetLeftChild();
166 ASSERT_EQ(13u, n->GetLowBound());
167 ASSERT_EQ(14u, n->GetHighBound());
168 ASSERT_TRUE(n->IsLeaf());
169 ASSERT_EQ(1u, n->CountNodes());
170
171 n = &root.GetRightChild().GetRightChild().GetRightChild().GetRightChild();
172 ASSERT_EQ(14u, n->GetLowBound());
173 ASSERT_EQ(15u, n->GetHighBound());
174 ASSERT_TRUE(n->IsLeaf());
175 ASSERT_EQ(1u, n->CountNodes());
176 }