Mercurial > hg > orthanc-stone
annotate OrthancStone/Sources/Toolbox/SegmentTree.cpp @ 1873:e0966648ebd0
unit tests of SegmentTree
| author | Sebastien Jodogne <s.jodogne@gmail.com> |
|---|---|
| date | Tue, 11 Jan 2022 15:36:04 +0100 |
| parents | db8a8a19b543 |
| children | 07964689cb0b |
| 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 | |
| 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 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 } |