Mercurial > hg > orthanc-stone
annotate OrthancStone/Sources/Toolbox/SegmentTree.cpp @ 2146:743fa9c74443 dicom-sr tip
integration mainline->dicom-sr
author | Sebastien Jodogne <s.jodogne@gmail.com> |
---|---|
date | Fri, 16 Aug 2024 18:09:53 +0200 |
parents | 16c01cc201e7 |
children |
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 | |
2124
16c01cc201e7
updated copyright, as Osimis is not active on Orthanc anymore
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
2114
diff
changeset
|
5 * Copyright (C) 2017-2023 Osimis S.A., Belgium |
2114
c23eef785569
update year to 2024
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
2077
diff
changeset
|
6 * Copyright (C) 2021-2024 Sebastien Jodogne, ICTEAM UCLouvain, Belgium |
1872 | 7 * |
8 * This program is free software: you can redistribute it and/or | |
9 * modify it under the terms of the GNU Lesser 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 * Lesser General Public License for more details. | |
17 * | |
18 * You should have received a copy of the GNU Lesser General Public | |
19 * License along with this program. If not, see | |
20 * <http://www.gnu.org/licenses/>. | |
21 **/ | |
22 | |
23 | |
24 #include "SegmentTree.h" | |
25 | |
26 #include <OrthancException.h> | |
27 | |
28 #include <cassert> | |
29 | |
30 | |
31 namespace OrthancStone | |
32 { | |
33 SegmentTree::SegmentTree(size_t lowBound, | |
34 size_t highBound, | |
35 IPayloadFactory& factory) : | |
36 lowBound_(lowBound), | |
37 highBound_(highBound), | |
38 payload_(factory.Create()) | |
39 { | |
40 if (payload_.get() == NULL) | |
41 { | |
42 throw Orthanc::OrthancException(Orthanc::ErrorCode_NullPointer); | |
43 } | |
44 | |
45 if (lowBound >= highBound) | |
46 { | |
47 throw Orthanc::OrthancException(Orthanc::ErrorCode_ParameterOutOfRange); | |
48 } | |
49 | |
50 if (highBound - lowBound > 1) | |
51 { | |
52 size_t middle = (lowBound + highBound) / 2; | |
53 left_.reset(new SegmentTree(lowBound, middle, factory)); | |
54 right_.reset(new SegmentTree(middle, highBound, factory)); | |
55 } | |
56 } | |
57 | |
58 | |
59 Orthanc::IDynamicObject& SegmentTree::GetPayload() const | |
60 { | |
61 assert(payload_.get() != NULL); | |
62 return *payload_; | |
63 } | |
64 | |
65 | |
66 SegmentTree& SegmentTree::GetLeftChild() const | |
67 { | |
68 if (IsLeaf()) | |
69 { | |
70 throw Orthanc::OrthancException(Orthanc::ErrorCode_BadSequenceOfCalls); | |
71 } | |
72 else | |
73 { | |
74 assert(left_.get() != NULL); | |
75 return *left_; | |
76 } | |
77 } | |
78 | |
79 | |
80 SegmentTree& SegmentTree::GetRightChild() const | |
81 { | |
82 if (IsLeaf()) | |
83 { | |
84 throw Orthanc::OrthancException(Orthanc::ErrorCode_BadSequenceOfCalls); | |
85 } | |
86 else | |
87 { | |
88 assert(right_.get() != NULL); | |
89 return *right_; | |
90 } | |
91 } | |
92 | |
93 | |
94 size_t SegmentTree::CountNodes() const | |
95 { | |
96 if (IsLeaf()) | |
97 { | |
98 return 1; | |
99 } | |
100 else | |
101 { | |
102 return 1 + GetLeftChild().CountNodes() + GetRightChild().CountNodes(); | |
103 } | |
104 } | |
105 | |
106 | |
1873
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
107 void SegmentTree::VisitSegment(size_t low, |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
108 size_t high, |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
109 IVisitor& visitor) const |
1872 | 110 { |
111 if (low >= high) | |
112 { | |
113 throw Orthanc::OrthancException(Orthanc::ErrorCode_ParameterOutOfRange); | |
114 } | |
115 | |
116 assert(payload_.get() != NULL); | |
117 | |
118 // Aliases to use the same variable names as in the textbook | |
119 const size_t& b = low; | |
120 const size_t& e = high; | |
121 const size_t& bv = GetLowBound(); | |
122 const size_t& ev = GetHighBound(); | |
123 | |
124 if (b <= bv && | |
125 ev <= e) | |
126 { | |
1873
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
127 // The segment of this node is fully inside the user-provided segment |
1872 | 128 visitor.Visit(*this, true); |
129 } | |
130 else if (!IsLeaf()) | |
131 { | |
132 // The child nodes are first updated | |
133 size_t middle = (bv + ev) / 2; | |
134 | |
135 if (b < middle) | |
136 { | |
1873
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
137 GetLeftChild().VisitSegment(b, e, visitor); |
1872 | 138 } |
139 | |
140 if (middle < e) | |
141 { | |
1873
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
142 GetRightChild().VisitSegment(b, e, visitor); |
1872 | 143 } |
144 | |
1873
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
145 // The segment of this node only partially intersects the user-provided segment |
1872 | 146 visitor.Visit(*this, false); |
147 } | |
148 } | |
1873
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
149 |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
150 |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
151 const SegmentTree* SegmentTree::FindLeaf(size_t low) const |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
152 { |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
153 if (IsLeaf()) |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
154 { |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
155 if (low == lowBound_) |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
156 { |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
157 return this; |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
158 } |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
159 else |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
160 { |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
161 return NULL; |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
162 } |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
163 } |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
164 else |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
165 { |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
166 size_t middle = (lowBound_ + highBound_) / 2; |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
167 if (low < middle) |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
168 { |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
169 return GetLeftChild().FindLeaf(low); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
170 } |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
171 else |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
172 { |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
173 return GetRightChild().FindLeaf(low); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
174 } |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
175 } |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
176 } |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
177 |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
178 |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
179 const SegmentTree* SegmentTree::FindNode(size_t low, |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
180 size_t high) const |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
181 { |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
182 if (low == lowBound_ && |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
183 high == highBound_) |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
184 { |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
185 return this; |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
186 } |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
187 else if (IsLeaf()) |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
188 { |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
189 return NULL; |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
190 } |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
191 else |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
192 { |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
193 size_t middle = (lowBound_ + highBound_) / 2; |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
194 if (low < middle) |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
195 { |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
196 return GetLeftChild().FindNode(low, high); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
197 } |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
198 else |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
199 { |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
200 return GetRightChild().FindNode(low, high); |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
201 } |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
202 } |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
203 } |
1872 | 204 } |