Mercurial > hg > orthanc-stone
comparison OrthancStone/Sources/Toolbox/SegmentTree.h @ 1872:db8a8a19b543
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 #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 } |