|
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 #pragma once
|
|
|
25
|
|
|
26 #include <Compatibility.h>
|
|
|
27 #include <IDynamicObject.h>
|
|
|
28
|
|
|
29 namespace OrthancStone
|
|
|
30 {
|
|
|
31 /**
|
|
|
32 * This implementation of segment trees closely follows Section
|
|
|
33 * 1.2.3.1 (pages 13-15) of "Computational Geometry - An
|
|
|
34 * Introduction" by Preparata and Ian Shamos (1985).
|
|
|
35 **/
|
|
|
36
|
|
|
37 class SegmentTree : public boost::noncopyable
|
|
|
38 {
|
|
|
39 public:
|
|
|
40 class IPayloadFactory : public boost::noncopyable
|
|
|
41 {
|
|
|
42 public:
|
|
|
43 virtual ~IPayloadFactory()
|
|
|
44 {
|
|
|
45 }
|
|
|
46
|
|
|
47 virtual Orthanc::IDynamicObject* Create() = 0;
|
|
|
48 };
|
|
|
49
|
|
|
50 class IVisitor : public boost::noncopyable
|
|
|
51 {
|
|
|
52 public:
|
|
|
53 virtual ~IVisitor()
|
|
|
54 {
|
|
|
55 }
|
|
|
56
|
|
|
57 virtual void Visit(const SegmentTree& node,
|
|
|
58 bool fullyInside) = 0;
|
|
|
59 };
|
|
|
60
|
|
|
61 private:
|
|
|
62 size_t lowBound_;
|
|
|
63 size_t highBound_;
|
|
|
64 std::unique_ptr<SegmentTree> left_;
|
|
|
65 std::unique_ptr<SegmentTree> right_;
|
|
|
66 std::unique_ptr<Orthanc::IDynamicObject> payload_;
|
|
|
67
|
|
|
68 public:
|
|
|
69 SegmentTree(size_t lowBound,
|
|
|
70 size_t highBound,
|
|
|
71 IPayloadFactory& factory);
|
|
|
72
|
|
|
73 size_t GetLowBound() const
|
|
|
74 {
|
|
|
75 return lowBound_;
|
|
|
76 }
|
|
|
77
|
|
|
78 size_t GetHighBound() const
|
|
|
79 {
|
|
|
80 return highBound_;
|
|
|
81 }
|
|
|
82
|
|
|
83 bool IsLeaf() const
|
|
|
84 {
|
|
|
85 return left_.get() == NULL;
|
|
|
86 }
|
|
|
87
|
|
|
88 Orthanc::IDynamicObject& GetPayload() const;
|
|
|
89
|
|
|
90 template <typename T>
|
|
|
91 T& GetTypedPayload() const
|
|
|
92 {
|
|
|
93 return dynamic_cast<T&>(GetPayload());
|
|
|
94 }
|
|
|
95
|
|
|
96 SegmentTree& GetLeftChild() const;
|
|
|
97
|
|
|
98 SegmentTree& GetRightChild() const;
|
|
|
99
|
|
|
100 size_t CountNodes() const;
|
|
|
101
|
|
|
102 // This corresponds to both methods "INSERT()" and "DELETE()" from
|
|
|
103 // the reference textbook
|
|
|
104 void Visit(size_t low,
|
|
|
105 size_t high,
|
|
|
106 IVisitor& visitor);
|
|
|
107 };
|
|
|
108 }
|
