Mercurial > hg > orthanc-stone

comparison OrthancStone/Sources/Toolbox/SegmentTree.cpp @ 1872:db8a8a19b543

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
SegmentTree
author Sebastien Jodogne <s.jodogne@gmail.com>
date Tue, 11 Jan 2022 12:15:22 +0100
parents
children e0966648ebd0
comparison
equal deleted inserted replaced
1871:7053b8a0aaec 1872:db8a8a19b543
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 }