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);
+      }
+    }
+  }
 }