Mercurial > hg > orthanc-stone
annotate OrthancStone/Sources/Toolbox/SegmentTree.h @ 2062:f5db73779f2d deep-learning
fix
author | Sebastien Jodogne <s.jodogne@gmail.com> |
---|---|
date | Wed, 03 May 2023 16:48:59 +0200 |
parents | e0966648ebd0 |
children | 07964689cb0b |
rev | line source |
---|---|
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 | |
1873
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
57 // "fullyInside" is true iff. the segment of "node" is fully |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
58 // inside the user-provided segment |
1872 | 59 virtual void Visit(const SegmentTree& node, |
60 bool fullyInside) = 0; | |
61 }; | |
62 | |
63 private: | |
64 size_t lowBound_; | |
65 size_t highBound_; | |
66 std::unique_ptr<SegmentTree> left_; | |
67 std::unique_ptr<SegmentTree> right_; | |
68 std::unique_ptr<Orthanc::IDynamicObject> payload_; | |
69 | |
70 public: | |
71 SegmentTree(size_t lowBound, | |
72 size_t highBound, | |
73 IPayloadFactory& factory); | |
74 | |
75 size_t GetLowBound() const | |
76 { | |
77 return lowBound_; | |
78 } | |
79 | |
80 size_t GetHighBound() const | |
81 { | |
82 return highBound_; | |
83 } | |
84 | |
85 bool IsLeaf() const | |
86 { | |
87 return left_.get() == NULL; | |
88 } | |
89 | |
90 Orthanc::IDynamicObject& GetPayload() const; | |
91 | |
92 template <typename T> | |
93 T& GetTypedPayload() const | |
94 { | |
95 return dynamic_cast<T&>(GetPayload()); | |
96 } | |
97 | |
98 SegmentTree& GetLeftChild() const; | |
99 | |
100 SegmentTree& GetRightChild() const; | |
101 | |
102 size_t CountNodes() const; | |
103 | |
1873
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
104 /** |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
105 * Apply the given visitor to all the segments that intersect the |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
106 * [low,high] segment. This corresponds to both methods "INSERT()" |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
107 * and "DELETE()" from the reference textbook. |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
108 **/ |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
109 void VisitSegment(size_t low, |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
110 size_t high, |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
111 IVisitor& visitor) const; |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
112 |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
113 // For unit tests |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
114 const SegmentTree* FindLeaf(size_t low) const; |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
115 |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
116 // For unit tests |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
117 const SegmentTree* FindNode(size_t low, |
e0966648ebd0
unit tests of SegmentTree
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1872
diff
changeset
|
118 size_t high) const; |
1872 | 119 }; |
120 } |