Mercurial > hg > orthanc-stone
diff OrthancStone/Sources/Toolbox/SegmentTree.cpp @ 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 |
line wrap: on
line diff
--- a/OrthancStone/Sources/Toolbox/SegmentTree.cpp Tue Jan 11 12:15:22 2022 +0100 +++ b/OrthancStone/Sources/Toolbox/SegmentTree.cpp Tue Jan 11 15:36:04 2022 +0100 @@ -104,9 +104,9 @@ } - void SegmentTree::Visit(size_t low, - size_t high, - IVisitor& visitor) + void SegmentTree::VisitSegment(size_t low, + size_t high, + IVisitor& visitor) const { if (low >= high) { @@ -124,7 +124,7 @@ if (b <= bv && ev <= e) { - // The interval of this node is fully inside the user-provided interval + // The segment of this node is fully inside the user-provided segment visitor.Visit(*this, true); } else if (!IsLeaf()) @@ -134,16 +134,71 @@ if (b < middle) { - GetLeftChild().Visit(b, e, visitor); + GetLeftChild().VisitSegment(b, e, visitor); } if (middle < e) { - GetRightChild().Visit(b, e, visitor); + GetRightChild().VisitSegment(b, e, visitor); } - // The interval of this node only partially intersects the user-provided interval + // The segment of this node only partially intersects the user-provided segment visitor.Visit(*this, false); } } + + + const SegmentTree* SegmentTree::FindLeaf(size_t low) const + { + if (IsLeaf()) + { + if (low == lowBound_) + { + return this; + } + else + { + return NULL; + } + } + else + { + size_t middle = (lowBound_ + highBound_) / 2; + if (low < middle) + { + return GetLeftChild().FindLeaf(low); + } + else + { + return GetRightChild().FindLeaf(low); + } + } + } + + + const SegmentTree* SegmentTree::FindNode(size_t low, + size_t high) const + { + if (low == lowBound_ && + high == highBound_) + { + return this; + } + else if (IsLeaf()) + { + return NULL; + } + else + { + size_t middle = (lowBound_ + highBound_) / 2; + if (low < middle) + { + return GetLeftChild().FindNode(low, high); + } + else + { + return GetRightChild().FindNode(low, high); + } + } + } }