Mercurial > hg > orthanc-stone
annotate OrthancStone/Sources/Toolbox/SegmentTree.h @ 1873:e0966648ebd0
unit tests of SegmentTree
| author | Sebastien Jodogne <s.jodogne@gmail.com> |
|---|---|
| date | Tue, 11 Jan 2022 15:36:04 +0100 |
| parents | db8a8a19b543 |
| 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 } |