annotate OrthancStone/Sources/Toolbox/SegmentTree.cpp @ 1893:90b5e116a5f9

removed DicomStructureSet::GetStructureColor()
author Sebastien Jodogne <s.jodogne@gmail.com>
date Wed, 19 Jan 2022 14:01:57 +0100
parents e0966648ebd0
children 07964689cb0b
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
1872
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
1 /**
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
2 * Stone of Orthanc
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
3 * Copyright (C) 2012-2016 Sebastien Jodogne, Medical Physics
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
4 * Department, University Hospital of Liege, Belgium
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
5 * Copyright (C) 2017-2022 Osimis S.A., Belgium
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
6 * Copyright (C) 2021-2022 Sebastien Jodogne, ICTEAM UCLouvain, Belgium
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
7 *
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
8 * This program is free software: you can redistribute it and/or
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
9 * modify it under the terms of the GNU Lesser General Public License
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
10 * as published by the Free Software Foundation, either version 3 of
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
11 * the License, or (at your option) any later version.
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
12 *
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
13 * This program is distributed in the hope that it will be useful, but
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
14 * WITHOUT ANY WARRANTY; without even the implied warranty of
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
16 * Lesser General Public License for more details.
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
17 *
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
18 * You should have received a copy of the GNU Lesser General Public
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
19 * License along with this program. If not, see
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
20 * <http://www.gnu.org/licenses/>.
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
21 **/
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
22
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
23
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
24 #include "SegmentTree.h"
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
25
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
26 #include <OrthancException.h>
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
27
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
28 #include <cassert>
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
29
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
30
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
31 namespace OrthancStone
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
32 {
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
33 SegmentTree::SegmentTree(size_t lowBound,
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
34 size_t highBound,
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
35 IPayloadFactory& factory) :
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
36 lowBound_(lowBound),
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
37 highBound_(highBound),
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
38 payload_(factory.Create())
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
39 {
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
40 if (payload_.get() == NULL)
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
41 {
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
42 throw Orthanc::OrthancException(Orthanc::ErrorCode_NullPointer);
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
43 }
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
44
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
45 if (lowBound >= highBound)
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
46 {
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
47 throw Orthanc::OrthancException(Orthanc::ErrorCode_ParameterOutOfRange);
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
48 }
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
49
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
50 if (highBound - lowBound > 1)
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
51 {
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
52 size_t middle = (lowBound + highBound) / 2;
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
53 left_.reset(new SegmentTree(lowBound, middle, factory));
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
54 right_.reset(new SegmentTree(middle, highBound, factory));
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
55 }
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
56 }
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
57
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
58
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
59 Orthanc::IDynamicObject& SegmentTree::GetPayload() const
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
60 {
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
61 assert(payload_.get() != NULL);
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
62 return *payload_;
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
63 }
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
64
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
65
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
66 SegmentTree& SegmentTree::GetLeftChild() const
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
67 {
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
68 if (IsLeaf())
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
69 {
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
70 throw Orthanc::OrthancException(Orthanc::ErrorCode_BadSequenceOfCalls);
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
71 }
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
72 else
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
73 {
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
74 assert(left_.get() != NULL);
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
75 return *left_;
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
76 }
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
77 }
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
78
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
79
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
80 SegmentTree& SegmentTree::GetRightChild() const
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
81 {
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
82 if (IsLeaf())
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
83 {
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
84 throw Orthanc::OrthancException(Orthanc::ErrorCode_BadSequenceOfCalls);
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
85 }
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
86 else
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
87 {
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
88 assert(right_.get() != NULL);
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
89 return *right_;
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
90 }
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
91 }
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
92
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
93
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
94 size_t SegmentTree::CountNodes() const
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
95 {
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
96 if (IsLeaf())
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
97 {
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
98 return 1;
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
99 }
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
100 else
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
101 {
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
102 return 1 + GetLeftChild().CountNodes() + GetRightChild().CountNodes();
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
103 }
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
104 }
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
105
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
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
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
110 {
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
111 if (low >= high)
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
112 {
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
113 throw Orthanc::OrthancException(Orthanc::ErrorCode_ParameterOutOfRange);
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
114 }
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
115
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
116 assert(payload_.get() != NULL);
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
117
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
118 // Aliases to use the same variable names as in the textbook
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
119 const size_t& b = low;
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
120 const size_t& e = high;
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
121 const size_t& bv = GetLowBound();
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
122 const size_t& ev = GetHighBound();
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
123
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
124 if (b <= bv &&
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
125 ev <= e)
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
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
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
128 visitor.Visit(*this, true);
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
129 }
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
130 else if (!IsLeaf())
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
131 {
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
132 // The child nodes are first updated
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
133 size_t middle = (bv + ev) / 2;
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
134
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
135 if (b < middle)
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
136 {
1873
e0966648ebd0 unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents: 1872
diff changeset
137 GetLeftChild().VisitSegment(b, e, visitor);
1872
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
138 }
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
139
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
140 if (middle < e)
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
141 {
1873
e0966648ebd0 unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents: 1872
diff changeset
142 GetRightChild().VisitSegment(b, e, visitor);
1872
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
143 }
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
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
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
146 visitor.Visit(*this, false);
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
147 }
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
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
db8a8a19b543 SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff changeset
204 }