|
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
|
|
|
107 void SegmentTree::Visit(size_t low,
|
|
|
108 size_t high,
|
|
|
109 IVisitor& visitor)
|
|
|
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 {
|
|
|
127 // The interval of this node is fully inside the user-provided interval
|
|
|
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 {
|
|
|
137 GetLeftChild().Visit(b, e, visitor);
|
|
|
138 }
|
|
|
139
|
|
|
140 if (middle < e)
|
|
|
141 {
|
|
|
142 GetRightChild().Visit(b, e, visitor);
|
|
|
143 }
|
|
|
144
|
|
|
145 // The interval of this node only partially intersects the user-provided interval
|
|
|
146 visitor.Visit(*this, false);
|
|
|
147 }
|
|
|
148 }
|
|
|
149 }
|
