Mercurial > hg > orthanc-stone
comparison UnitTestsSources/ComputationalGeometryTests.cpp @ 1872:db8a8a19b543
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 } |