# HG changeset patch
# User Sebastien Jodogne <s.jodogne@gmail.com>
# Date 1641899722 -3600
# Node ID db8a8a19b5439fec57142fc229febd75d6e0c292
# Parent  7053b8a0aaecbf50221f497727dde91999d5f95a
SegmentTree

diff -r 7053b8a0aaec -r db8a8a19b543 OrthancStone/Resources/CMake/OrthancStoneConfiguration.cmake
--- a/OrthancStone/Resources/CMake/OrthancStoneConfiguration.cmake	Tue Jan 11 11:18:48 2022 +0100
+++ b/OrthancStone/Resources/CMake/OrthancStoneConfiguration.cmake	Tue Jan 11 12:15:22 2022 +0100
@@ -427,6 +427,8 @@
   ${ORTHANC_STONE_ROOT}/Toolbox/LinearAlgebra.cpp
   ${ORTHANC_STONE_ROOT}/Toolbox/LinearAlgebra.h
   ${ORTHANC_STONE_ROOT}/Toolbox/PixelTestPatterns.h
+  ${ORTHANC_STONE_ROOT}/Toolbox/SegmentTree.cpp
+  ${ORTHANC_STONE_ROOT}/Toolbox/SegmentTree.h
   ${ORTHANC_STONE_ROOT}/Toolbox/ShearWarpProjectiveTransform.cpp
   ${ORTHANC_STONE_ROOT}/Toolbox/ShearWarpProjectiveTransform.h
   ${ORTHANC_STONE_ROOT}/Toolbox/SlicesSorter.cpp
diff -r 7053b8a0aaec -r db8a8a19b543 OrthancStone/Sources/Toolbox/SegmentTree.cpp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/OrthancStone/Sources/Toolbox/SegmentTree.cpp	Tue Jan 11 12:15:22 2022 +0100
@@ -0,0 +1,149 @@
+/**
+ * Stone of Orthanc
+ * Copyright (C) 2012-2016 Sebastien Jodogne, Medical Physics
+ * Department, University Hospital of Liege, Belgium
+ * Copyright (C) 2017-2022 Osimis S.A., Belgium
+ * Copyright (C) 2021-2022 Sebastien Jodogne, ICTEAM UCLouvain, Belgium
+ *
+ * This program is free software: you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public License
+ * as published by the Free Software Foundation, either version 3 of
+ * the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this program. If not, see
+ * <http://www.gnu.org/licenses/>.
+ **/
+
+
+#include "SegmentTree.h"
+
+#include <OrthancException.h>
+
+#include <cassert>
+
+
+namespace OrthancStone
+{
+  SegmentTree::SegmentTree(size_t lowBound,
+                           size_t highBound,
+                           IPayloadFactory& factory) :
+    lowBound_(lowBound),
+    highBound_(highBound),
+    payload_(factory.Create())
+  {
+    if (payload_.get() == NULL)
+    {
+      throw Orthanc::OrthancException(Orthanc::ErrorCode_NullPointer);
+    }
+    
+    if (lowBound >= highBound)
+    {
+      throw Orthanc::OrthancException(Orthanc::ErrorCode_ParameterOutOfRange);
+    }
+    
+    if (highBound - lowBound > 1)
+    {
+      size_t middle = (lowBound + highBound) / 2;
+      left_.reset(new SegmentTree(lowBound, middle, factory));
+      right_.reset(new SegmentTree(middle, highBound, factory));
+    }
+  }
+
+
+  Orthanc::IDynamicObject& SegmentTree::GetPayload() const
+  {
+    assert(payload_.get() != NULL);
+    return *payload_;
+  }
+
+
+  SegmentTree& SegmentTree::GetLeftChild() const
+  {
+    if (IsLeaf())
+    {
+      throw Orthanc::OrthancException(Orthanc::ErrorCode_BadSequenceOfCalls);
+    }
+    else
+    {
+      assert(left_.get() != NULL);
+      return *left_;
+    }
+  }
+
+
+  SegmentTree& SegmentTree::GetRightChild() const
+  {
+    if (IsLeaf())
+    {
+      throw Orthanc::OrthancException(Orthanc::ErrorCode_BadSequenceOfCalls);
+    }
+    else
+    {
+      assert(right_.get() != NULL);
+      return *right_;
+    }
+  }
+
+
+  size_t SegmentTree::CountNodes() const
+  {
+    if (IsLeaf())
+    {
+      return 1;
+    }
+    else
+    {
+      return 1 + GetLeftChild().CountNodes() + GetRightChild().CountNodes();
+    }
+  }
+
+
+  void SegmentTree::Visit(size_t low,
+                          size_t high,
+                          IVisitor& visitor)
+  {
+    if (low >= high)
+    {
+      throw Orthanc::OrthancException(Orthanc::ErrorCode_ParameterOutOfRange);
+    }
+    
+    assert(payload_.get() != NULL);
+    
+    // Aliases to use the same variable names as in the textbook
+    const size_t& b = low;
+    const size_t& e = high;
+    const size_t& bv = GetLowBound();
+    const size_t& ev = GetHighBound();
+    
+    if (b <= bv &&
+        ev <= e)
+    {
+      // The interval of this node is fully inside the user-provided interval
+      visitor.Visit(*this, true);
+    }
+    else if (!IsLeaf())
+    {
+      // The child nodes are first updated
+      size_t middle = (bv + ev) / 2;
+
+      if (b < middle)
+      {
+        GetLeftChild().Visit(b, e, visitor);
+      }
+
+      if (middle < e)
+      {
+        GetRightChild().Visit(b, e, visitor);
+      }
+      
+      // The interval of this node only partially intersects the user-provided interval
+      visitor.Visit(*this, false);
+    }
+  }
+}
diff -r 7053b8a0aaec -r db8a8a19b543 OrthancStone/Sources/Toolbox/SegmentTree.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/OrthancStone/Sources/Toolbox/SegmentTree.h	Tue Jan 11 12:15:22 2022 +0100
@@ -0,0 +1,108 @@
+/**
+ * Stone of Orthanc
+ * Copyright (C) 2012-2016 Sebastien Jodogne, Medical Physics
+ * Department, University Hospital of Liege, Belgium
+ * Copyright (C) 2017-2022 Osimis S.A., Belgium
+ * Copyright (C) 2021-2022 Sebastien Jodogne, ICTEAM UCLouvain, Belgium
+ *
+ * This program is free software: you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public License
+ * as published by the Free Software Foundation, either version 3 of
+ * the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this program. If not, see
+ * <http://www.gnu.org/licenses/>.
+ **/
+
+
+#pragma once
+
+#include <Compatibility.h>
+#include <IDynamicObject.h>
+
+namespace OrthancStone
+{
+  /**
+   * This implementation of segment trees closely follows Section
+   * 1.2.3.1 (pages 13-15) of "Computational Geometry - An
+   * Introduction" by Preparata and Ian Shamos (1985).
+   **/
+
+  class SegmentTree : public boost::noncopyable
+  {
+  public:
+    class IPayloadFactory : public boost::noncopyable
+    {
+    public:
+      virtual ~IPayloadFactory()
+      {
+      }
+
+      virtual Orthanc::IDynamicObject* Create() = 0;
+    };
+
+    class IVisitor : public boost::noncopyable
+    {
+    public:
+      virtual ~IVisitor()
+      {
+      }
+
+      virtual void Visit(const SegmentTree& node,
+                         bool fullyInside) = 0;
+    };
+
+  private:
+    size_t                                    lowBound_;
+    size_t                                    highBound_;
+    std::unique_ptr<SegmentTree>              left_;
+    std::unique_ptr<SegmentTree>              right_;
+    std::unique_ptr<Orthanc::IDynamicObject>  payload_;
+    
+  public:
+    SegmentTree(size_t lowBound,
+                size_t highBound,
+                IPayloadFactory& factory);
+
+    size_t GetLowBound() const
+    {
+      return lowBound_;
+    }
+
+    size_t GetHighBound() const
+    {
+      return highBound_;
+    }
+
+    bool IsLeaf() const
+    {
+      return left_.get() == NULL;
+    }
+
+    Orthanc::IDynamicObject& GetPayload() const;
+
+    template <typename T>
+    T& GetTypedPayload() const
+    {
+      return dynamic_cast<T&>(GetPayload());
+    }
+
+    SegmentTree& GetLeftChild() const;
+
+    SegmentTree& GetRightChild() const;
+
+    size_t CountNodes() const;
+
+    // This corresponds to both methods "INSERT()" and "DELETE()" from
+    // the reference textbook
+    void Visit(size_t low,
+               size_t high,
+               IVisitor& visitor);
+  };
+}
diff -r 7053b8a0aaec -r db8a8a19b543 UnitTestsSources/ComputationalGeometryTests.cpp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/UnitTestsSources/ComputationalGeometryTests.cpp	Tue Jan 11 12:15:22 2022 +0100
@@ -0,0 +1,176 @@
+/**
+ * Stone of Orthanc
+ * Copyright (C) 2012-2016 Sebastien Jodogne, Medical Physics
+ * Department, University Hospital of Liege, Belgium
+ * Copyright (C) 2017-2022 Osimis S.A., Belgium
+ * Copyright (C) 2021-2022 Sebastien Jodogne, ICTEAM UCLouvain, Belgium
+ *
+ * This program is free software: you can redistribute it and/or
+ * modify it under the terms of the GNU Affero General Public License
+ * as published by the Free Software Foundation, either version 3 of
+ * the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Affero General Public License for more details.
+ *
+ * You should have received a copy of the GNU Affero General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ **/
+
+
+#include <gtest/gtest.h>
+
+#include "../OrthancStone/Sources/Toolbox/SegmentTree.h"
+
+#include <Logging.h>
+#include <OrthancException.h>
+
+
+namespace
+{
+  class CounterFactory : public OrthancStone::SegmentTree::IPayloadFactory
+  {
+  public:
+    virtual Orthanc::IDynamicObject* Create()
+    {
+      return new Orthanc::SingleValueObject<int>(42);
+    }
+  };
+}
+
+
+TEST(SegmentTree, Basic)
+{
+  CounterFactory factory;
+  OrthancStone::SegmentTree root(4u, 15u, factory);   // Check out Figure 1.1 (page 14) from textbook
+  
+  ASSERT_EQ(4u, root.GetLowBound());
+  ASSERT_EQ(15u, root.GetHighBound());
+  ASSERT_FALSE(root.IsLeaf());
+  ASSERT_EQ(42, root.GetTypedPayload< Orthanc::SingleValueObject<int> >().GetValue());
+  ASSERT_EQ(21u, root.CountNodes());
+
+  OrthancStone::SegmentTree* n = &root.GetLeftChild();
+  ASSERT_EQ(4u, n->GetLowBound());
+  ASSERT_EQ(9u, n->GetHighBound());
+  ASSERT_FALSE(n->IsLeaf());
+  ASSERT_EQ(9u, n->CountNodes());
+
+  n = &root.GetLeftChild().GetLeftChild();
+  ASSERT_EQ(4u, n->GetLowBound());
+  ASSERT_EQ(6u, n->GetHighBound());
+  ASSERT_FALSE(n->IsLeaf());
+  ASSERT_EQ(3u, n->CountNodes());
+
+  n = &root.GetLeftChild().GetLeftChild().GetLeftChild();
+  ASSERT_EQ(4u, n->GetLowBound());
+  ASSERT_EQ(5u, n->GetHighBound());
+  ASSERT_TRUE(n->IsLeaf());
+  ASSERT_THROW(n->GetLeftChild(), Orthanc::OrthancException);
+  ASSERT_THROW(n->GetRightChild(), Orthanc::OrthancException);
+  ASSERT_EQ(1u, n->CountNodes());
+
+  n = &root.GetLeftChild().GetLeftChild().GetRightChild();
+  ASSERT_EQ(5u, n->GetLowBound());
+  ASSERT_EQ(6u, n->GetHighBound());
+  ASSERT_TRUE(n->IsLeaf());
+  ASSERT_EQ(1u, n->CountNodes());
+
+  n = &root.GetLeftChild().GetRightChild();
+  ASSERT_EQ(6u, n->GetLowBound());
+  ASSERT_EQ(9u, n->GetHighBound());
+  ASSERT_FALSE(n->IsLeaf());
+  ASSERT_EQ(5u, n->CountNodes());
+
+  n = &root.GetLeftChild().GetRightChild().GetLeftChild();
+  ASSERT_EQ(6u, n->GetLowBound());
+  ASSERT_EQ(7u, n->GetHighBound());
+  ASSERT_TRUE(n->IsLeaf());
+  ASSERT_EQ(1u, n->CountNodes());
+
+  n = &root.GetLeftChild().GetRightChild().GetRightChild();
+  ASSERT_EQ(7u, n->GetLowBound());
+  ASSERT_EQ(9u, n->GetHighBound());
+  ASSERT_FALSE(n->IsLeaf());
+  ASSERT_EQ(3u, n->CountNodes());
+
+  n = &root.GetLeftChild().GetRightChild().GetRightChild().GetLeftChild();
+  ASSERT_EQ(7u, n->GetLowBound());
+  ASSERT_EQ(8u, n->GetHighBound());
+  ASSERT_TRUE(n->IsLeaf());
+  ASSERT_EQ(1u, n->CountNodes());
+
+  n = &root.GetLeftChild().GetRightChild().GetRightChild().GetRightChild();
+  ASSERT_EQ(8u, n->GetLowBound());
+  ASSERT_EQ(9u, n->GetHighBound());
+  ASSERT_TRUE(n->IsLeaf());
+  ASSERT_EQ(1u, n->CountNodes());
+
+  n = &root.GetRightChild();
+  ASSERT_EQ(9u, n->GetLowBound());
+  ASSERT_EQ(15u, n->GetHighBound());
+  ASSERT_FALSE(n->IsLeaf());
+  ASSERT_EQ(11u, n->CountNodes());
+
+  n = &root.GetRightChild().GetLeftChild();
+  ASSERT_EQ(9u, n->GetLowBound());
+  ASSERT_EQ(12u, n->GetHighBound());
+  ASSERT_FALSE(n->IsLeaf());
+  ASSERT_EQ(5u, n->CountNodes());
+
+  n = &root.GetRightChild().GetLeftChild().GetLeftChild();
+  ASSERT_EQ(9u, n->GetLowBound());
+  ASSERT_EQ(10u, n->GetHighBound());
+  ASSERT_TRUE(n->IsLeaf());
+  ASSERT_EQ(1u, n->CountNodes());
+
+  n = &root.GetRightChild().GetLeftChild().GetRightChild();
+  ASSERT_EQ(10u, n->GetLowBound());
+  ASSERT_EQ(12u, n->GetHighBound());
+  ASSERT_FALSE(n->IsLeaf());
+  ASSERT_EQ(3u, n->CountNodes());
+
+  n = &root.GetRightChild().GetLeftChild().GetRightChild().GetLeftChild();
+  ASSERT_EQ(10u, n->GetLowBound());
+  ASSERT_EQ(11u, n->GetHighBound());
+  ASSERT_TRUE(n->IsLeaf());
+  ASSERT_EQ(1u, n->CountNodes());
+
+  n = &root.GetRightChild().GetLeftChild().GetRightChild().GetRightChild();
+  ASSERT_EQ(11u, n->GetLowBound());
+  ASSERT_EQ(12u, n->GetHighBound());
+  ASSERT_TRUE(n->IsLeaf());
+  ASSERT_EQ(1u, n->CountNodes());
+
+  n = &root.GetRightChild().GetRightChild();
+  ASSERT_EQ(12u, n->GetLowBound());
+  ASSERT_EQ(15u, n->GetHighBound());
+  ASSERT_FALSE(n->IsLeaf());
+  ASSERT_EQ(5u, n->CountNodes());
+
+  n = &root.GetRightChild().GetRightChild().GetLeftChild();
+  ASSERT_EQ(12u, n->GetLowBound());
+  ASSERT_EQ(13u, n->GetHighBound());
+  ASSERT_TRUE(n->IsLeaf());
+  ASSERT_EQ(1u, n->CountNodes());
+
+  n = &root.GetRightChild().GetRightChild().GetRightChild();
+  ASSERT_EQ(13u, n->GetLowBound());
+  ASSERT_EQ(15u, n->GetHighBound());
+  ASSERT_FALSE(n->IsLeaf());
+  ASSERT_EQ(3u, n->CountNodes());
+
+  n = &root.GetRightChild().GetRightChild().GetRightChild().GetLeftChild();
+  ASSERT_EQ(13u, n->GetLowBound());
+  ASSERT_EQ(14u, n->GetHighBound());
+  ASSERT_TRUE(n->IsLeaf());
+  ASSERT_EQ(1u, n->CountNodes());
+
+  n = &root.GetRightChild().GetRightChild().GetRightChild().GetRightChild();
+  ASSERT_EQ(14u, n->GetLowBound());
+  ASSERT_EQ(15u, n->GetHighBound());
+  ASSERT_TRUE(n->IsLeaf());
+  ASSERT_EQ(1u, n->CountNodes());
+}
diff -r 7053b8a0aaec -r db8a8a19b543 UnitTestsSources/UnitTestsSources.cmake
--- a/UnitTestsSources/UnitTestsSources.cmake	Tue Jan 11 11:18:48 2022 +0100
+++ b/UnitTestsSources/UnitTestsSources.cmake	Tue Jan 11 12:15:22 2022 +0100
@@ -19,6 +19,7 @@
 
 
 set(UNIT_TESTS_SOURCES
+  ${CMAKE_CURRENT_LIST_DIR}/ComputationalGeometryTests.cpp
   ${CMAKE_CURRENT_LIST_DIR}/DicomTests.cpp
   ${CMAKE_CURRENT_LIST_DIR}/GenericToolboxTests.cpp
   ${CMAKE_CURRENT_LIST_DIR}/GeometryToolboxTests.cpp