Mercurial > hg > orthanc-stone
comparison 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 |
comparison
equal
deleted
inserted
replaced
1872:db8a8a19b543 | 1873:e0966648ebd0 |
---|---|
102 return 1 + GetLeftChild().CountNodes() + GetRightChild().CountNodes(); | 102 return 1 + GetLeftChild().CountNodes() + GetRightChild().CountNodes(); |
103 } | 103 } |
104 } | 104 } |
105 | 105 |
106 | 106 |
107 void SegmentTree::Visit(size_t low, | 107 void SegmentTree::VisitSegment(size_t low, |
108 size_t high, | 108 size_t high, |
109 IVisitor& visitor) | 109 IVisitor& visitor) const |
110 { | 110 { |
111 if (low >= high) | 111 if (low >= high) |
112 { | 112 { |
113 throw Orthanc::OrthancException(Orthanc::ErrorCode_ParameterOutOfRange); | 113 throw Orthanc::OrthancException(Orthanc::ErrorCode_ParameterOutOfRange); |
114 } | 114 } |
122 const size_t& ev = GetHighBound(); | 122 const size_t& ev = GetHighBound(); |
123 | 123 |
124 if (b <= bv && | 124 if (b <= bv && |
125 ev <= e) | 125 ev <= e) |
126 { | 126 { |
127 // The interval of this node is fully inside the user-provided interval | 127 // The segment of this node is fully inside the user-provided segment |
128 visitor.Visit(*this, true); | 128 visitor.Visit(*this, true); |
129 } | 129 } |
130 else if (!IsLeaf()) | 130 else if (!IsLeaf()) |
131 { | 131 { |
132 // The child nodes are first updated | 132 // The child nodes are first updated |
133 size_t middle = (bv + ev) / 2; | 133 size_t middle = (bv + ev) / 2; |
134 | 134 |
135 if (b < middle) | 135 if (b < middle) |
136 { | 136 { |
137 GetLeftChild().Visit(b, e, visitor); | 137 GetLeftChild().VisitSegment(b, e, visitor); |
138 } | 138 } |
139 | 139 |
140 if (middle < e) | 140 if (middle < e) |
141 { | 141 { |
142 GetRightChild().Visit(b, e, visitor); | 142 GetRightChild().VisitSegment(b, e, visitor); |
143 } | 143 } |
144 | 144 |
145 // The interval of this node only partially intersects the user-provided interval | 145 // The segment of this node only partially intersects the user-provided segment |
146 visitor.Visit(*this, false); | 146 visitor.Visit(*this, false); |
147 } | 147 } |
148 } | 148 } |
149 | |
150 | |
151 const SegmentTree* SegmentTree::FindLeaf(size_t low) const | |
152 { | |
153 if (IsLeaf()) | |
154 { | |
155 if (low == lowBound_) | |
156 { | |
157 return this; | |
158 } | |
159 else | |
160 { | |
161 return NULL; | |
162 } | |
163 } | |
164 else | |
165 { | |
166 size_t middle = (lowBound_ + highBound_) / 2; | |
167 if (low < middle) | |
168 { | |
169 return GetLeftChild().FindLeaf(low); | |
170 } | |
171 else | |
172 { | |
173 return GetRightChild().FindLeaf(low); | |
174 } | |
175 } | |
176 } | |
177 | |
178 | |
179 const SegmentTree* SegmentTree::FindNode(size_t low, | |
180 size_t high) const | |
181 { | |
182 if (low == lowBound_ && | |
183 high == highBound_) | |
184 { | |
185 return this; | |
186 } | |
187 else if (IsLeaf()) | |
188 { | |
189 return NULL; | |
190 } | |
191 else | |
192 { | |
193 size_t middle = (lowBound_ + highBound_) / 2; | |
194 if (low < middle) | |
195 { | |
196 return GetLeftChild().FindNode(low, high); | |
197 } | |
198 else | |
199 { | |
200 return GetRightChild().FindNode(low, high); | |
201 } | |
202 } | |
203 } | |
149 } | 204 } |