|
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 {
|
|
|
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 }
|
