Mercurial > hg > orthanc-stone

comparison OrthancStone/Sources/Toolbox/SegmentTree.cpp @ 1873:e0966648ebd0

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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 }