// Created by: Eugeny MALTCHIKOV
// Created on: 2019-04-17
// Copyright (c) 2019 OPEN CASCADE SAS
//
// This file is part of Open CASCADE Technology software library.
//
// This library is free software; you can redistribute it and/or modify it under
// the terms of the GNU Lesser General Public License version 2.1 as published
// by the Free Software Foundation, with special exception defined in the file
// OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
// distribution for complete text of the license and disclaimer of any warranty.
//
// Alternatively, this file may be used under the terms of Open CASCADE
// commercial license or contractual agreement.

#ifndef _BVH_Traverse_Header
#define _BVH_Traverse_Header

#include "BVH_Box.hxx"
#include "BVH_Tree.hxx"

//! The classes implement the traverse of the BVH tree.
//!
//! There are two traverse methods implemented:
//! - Traverse of the single tree
//! - Parallel traverse of two trees
//!
//! To perform Selection of the elements from BVH_Tree using
//! the traverse methods implemented here it is
//! required to define Acceptance/Rejection rules in the
//! following methods:
//! - *RejectNode* - Node rejection by its bounding box.
//!   It is applied to both inner and outer nodes of the BVH tree.
//!   Optionally, the method should compute the metric for the node
//!   which will allow performing traverse faster by descending by the
//!   best branches.
//! - *Accept* - Element acceptance. It takes the index of the element
//!   of BVH tree. The access to the element itself should be performed
//!   through the set on which BVH is built.
//!   The *Accept* method implements the leaf node operation and usually
//!   defines the logic of the whole operation.
//! - *IsMetricBetter* - Compares the metrics of the nodes and returns
//!   true if the left metric is better than the right one.
//! - *RejectMetric* - Node rejection by the metric. It should compare
//!   the metric of the node with the global one and return true
//!   if the global metric is better than the given one.
//! - *Stop* - implements conditions to stop the tree descend if the necessary
//!   elements are already found.
//!
//! The selector of a single tree has an extra method which allows
//! accepting the whole branches without any further checks
//! (e.g. full inclusion test):
//! - *AcceptMetric* - basing on the metric of the node decides if the
//!   node may be accepted without any further checks.
//!
//! Two ways of selection are possible:
//! 1. Set the BVH set containing the tree and use the method Select()
//!    which allows using common interface for setting the BVH Set for accessing
//!    the BVH tree and elements in the Accept method.
//! 2. Keep the BVHSetType void, do not set the BVH set and use the
//!    method Select (const BVH_Tree<>&) which allows performing selection
//!    on the arbitrary BVH tree.
//!
//! Here is the example of usage of the traverse to find the point-triangulation
//! minimal distance.
//! ~~~~
//! // Structure to contain points of the triangle
//! struct Triangle
//! {
//!   Triangle() {}
//!   Triangle(const BVH_Vec3d& theNode1,
//!            const BVH_Vec3d& theNode2,
//!            const BVH_Vec3d& theNode3)
//!     : Node1 (theNode1), Node2 (theNode2), Node3 (theNode3)
//!   {}
//!
//!   BVH_Vec3d Node1;
//!   BVH_Vec3d Node2;
//!   BVH_Vec3d Node3;
//! };
//!
//! // Selector for min point-triangulation distance
//! class BVH_PointTriangulationSqDist :
//!   public BVH_Distance<double, 3, BVH_Vec3d, BVH_BoxSet<double, 3, Triangle>>
//! {
//! public:
//!
//!   // Computes the distance from the point to bounding box
//!   virtual bool RejectNode (const BVH_Vec3d& theCMin,
//!                                        const BVH_Vec3d& theCMax,
//!                                        double& theDistance) const override
//!   {
//!     theDistance = BVH_Tools<double, 3>::PointBoxSquareDistance (myObject, theCMin,
//!     theCMax); return RejectMetric (theDistance);
//!   }
//!
//!   // Computes the distance from the point to triangle
//!   virtual bool Accept (const int theIndex,
//!                                    const double&) override
//!   {
//!     const Triangle& aTri = myBVHSet->Element (theIndex);
//!     double aDist = BVH_Tools<double, 3>::PointTriangleSquareDistance (myObject,
//!     aTri.Node1, aTri.Node2, aTri.Node3); if (aDist < myDistance)
//!     {
//!       myDistance = aDist;
//!       return true;
//!     }
//!     return false;
//!   }
//! };
//!
//! // Point to which the distance is required
//! BVH_Vec3d aPoint = ...;
//! // BVH Set containing triangulation
//! opencascade::handle<BVH_BoxSet<double, 3, Triangle>> aTriangulationSet = ...;
//!
//! BVH_PointTriangulationSqDist aDistTool;
//! aDistTool.SetObject (aPoint);
//! aDistTool.SetBVHSet (aTriangulationSet.get());
//! aDistTool.ComputeDistance();
//! if (aDistTool.IsDone())
//! {
//!   double aPointTriSqDist = aDistTool.Distance();
//! }
//!
//! ~~~~
//!

//! Abstract class implementing the base Traverse interface
//! required for selection of the elements from BVH tree.
//!
//! \tparam MetricType Type of metric to perform more optimal tree descend
template <class MetricType>
class BVH_BaseTraverse
{
public: //! @name Metrics comparison for choosing the best branch
  //! Compares the two metrics and chooses the best one.
  //! Returns true if the first metric is better than the second,
  //! false otherwise.
  virtual bool IsMetricBetter(const MetricType&, const MetricType&) const
  {
    // Keep the left to right tree descend by default
    return true;
  }

public: //! @name Rejection of the node by metric
  //! Rejects the node by the metric
  virtual bool RejectMetric(const MetricType&) const
  {
    // Do not reject any nodes by metric by default
    return false;
  }

public: //! @name Condition to stop the descend
  //! Returns the flag controlling the tree descend.
  //! Returns true if the tree descend should be stopped.
  virtual bool Stop() const
  {
    // Do not stop tree descend by default
    return false;
  }

protected: //! @name Constructors
  //! Constructor
  BVH_BaseTraverse() {}

  //! Destructor
  virtual ~BVH_BaseTraverse() = default;
};

//! Abstract class implementing the traverse of the single binary tree.
//! Selection of the data from the tree is performed by the
//! rules defined in the Accept/Reject methods.
//! See description of the required methods in the comments above.
//!
//! \tparam NumType Numeric data type
//! \tparam Dimension Vector dimension
//! \tparam BVHSetType Type of set containing the BVH tree (required to access the elements by the
//! index) \tparam MetricType Type of metric to perform more optimal tree descend
template <class NumType, int Dimension, class BVHSetType = void, class MetricType = NumType>
class BVH_Traverse : public BVH_BaseTraverse<MetricType>
{
public: //! @name public types
  typedef typename BVH_Box<NumType, Dimension>::BVH_VecNt BVH_VecNt;

public: //! @name Constructor
  //! Constructor
  BVH_Traverse()
      : BVH_BaseTraverse<MetricType>(),
        myBVHSet(nullptr)
  {
  }

public: //! @name Setting the set to access the elements and BVH tree
  //! Sets the BVH Set containing the BVH tree
  void SetBVHSet(BVHSetType* theBVHSet) { myBVHSet = theBVHSet; }

public: //! @name Rules for Accept/Reject
  //! Basing on the given metric, checks if the whole branch may be
  //! accepted without any further checks.
  //! Returns true if the metric is accepted, false otherwise.
  virtual bool AcceptMetric(const MetricType&) const
  {
    // Do not accept the whole branch by default
    return false;
  }

  //! Rejection of the node by bounding box.
  //! Metric is computed to choose the best branch.
  //! Returns true if the node should be rejected, false otherwise.
  virtual bool RejectNode(const BVH_VecNt& theCornerMin,
                          const BVH_VecNt& theCornerMax,
                          MetricType&      theMetric) const = 0;

  //! Leaf element acceptance.
  //! Metric of the parent leaf-node is passed to avoid the check on the
  //! element and accept it unconditionally.
  //! Returns true if the element has been accepted, false otherwise.
  virtual bool Accept(const int theIndex, const MetricType& theMetric) = 0;

public: //! @name Selection
  //! Selection of the elements from the BVH tree by the
  //! rules defined in Accept/Reject methods.
  //! The method requires the BVHSet containing BVH tree to be set.
  //! Returns the number of accepted elements.
  int Select()
  {
    if (myBVHSet)
    {
      const opencascade::handle<BVH_Tree<NumType, Dimension>>& aBVH = myBVHSet->BVH();
      return Select(aBVH);
    }
    return 0;
  }

  //! Performs selection of the elements from the BVH tree by the
  //! rules defined in Accept/Reject methods.
  //! Returns the number of accepted elements.
  int Select(const opencascade::handle<BVH_Tree<NumType, Dimension>>& theBVH);

protected: //! @name Internal structures
  //! Auxiliary structure for keeping the nodes to process
  struct BVH_NodeInStack
  {
    //! Constructor
    constexpr BVH_NodeInStack(const int         theNodeID = 0,
                              const MetricType& theMetric = MetricType()) noexcept
        : NodeID(theNodeID),
          Metric(theMetric)
    {
    }

    // Fields
    int        NodeID; //!< Id of the node in the BVH tree
    MetricType Metric; //!< Metric computed for the node
  };

protected: //! @name Fields
  BVHSetType* myBVHSet;
};

//! Abstract class implementing the parallel traverse of two binary trees.
//! Selection of the data from the trees is performed by the
//! rules defined in the Accept/Reject methods.
//! See description of the required methods in the comments above.
//!
//! \tparam NumType Numeric data type
//! \tparam Dimension Vector dimension
//! \tparam BVHSetType Type of set containing the BVH tree (required to access the elements by the
//! index) \tparam MetricType Type of metric to perform more optimal tree descend
template <class NumType, int Dimension, class BVHSetType = void, class MetricType = NumType>
class BVH_PairTraverse : public BVH_BaseTraverse<MetricType>
{
public: //! @name public types
  typedef typename BVH_Box<NumType, Dimension>::BVH_VecNt BVH_VecNt;

public: //! @name Constructor
  //! Constructor
  BVH_PairTraverse()
      : BVH_BaseTraverse<MetricType>(),
        myBVHSet1(nullptr),
        myBVHSet2(nullptr)
  {
  }

public: //! @name Setting the sets to access the elements and BVH trees
  //! Sets the BVH Sets containing the BVH trees
  void SetBVHSets(BVHSetType* theBVHSet1, BVHSetType* theBVHSet2)
  {
    myBVHSet1 = theBVHSet1;
    myBVHSet2 = theBVHSet2;
  }

public: //! @name Rules for Accept/Reject
  //! Rejection of the pair of nodes by bounding boxes.
  //! Metric is computed to choose the best branch.
  //! Returns true if the pair of nodes should be rejected, false otherwise.
  virtual bool RejectNode(const BVH_VecNt& theCornerMin1,
                          const BVH_VecNt& theCornerMax1,
                          const BVH_VecNt& theCornerMin2,
                          const BVH_VecNt& theCornerMax2,
                          MetricType&      theMetric) const = 0;

  //! Leaf element acceptance.
  //! Returns true if the pair of elements is accepted, false otherwise.
  virtual bool Accept(const int theIndex1, const int theIndex2) = 0;

public: //! @name Selection
  //! Selection of the pairs of elements of two BVH trees by the
  //! rules defined in Accept/Reject methods.
  //! The method requires the BVHSets containing BVH trees to be set.
  //! Returns the number of accepted pairs of elements.
  int Select()
  {
    if (myBVHSet1 && myBVHSet2)
    {
      const opencascade::handle<BVH_Tree<NumType, Dimension>>& aBVH1 = myBVHSet1->BVH();
      const opencascade::handle<BVH_Tree<NumType, Dimension>>& aBVH2 = myBVHSet2->BVH();
      return Select(aBVH1, aBVH2);
    }
    return 0;
  }

  //! Performs selection of the elements from two BVH trees by the
  //! rules defined in Accept/Reject methods.
  //! Returns the number of accepted pairs of elements.
  int Select(const opencascade::handle<BVH_Tree<NumType, Dimension>>& theBVH1,
             const opencascade::handle<BVH_Tree<NumType, Dimension>>& theBVH2);

protected: //! @name Internal structures
  //! Auxiliary structure for keeping the pair of nodes to process
  struct BVH_PairNodesInStack
  {
    //! Constructor
    constexpr BVH_PairNodesInStack(const int         theNodeID1 = 0,
                                   const int         theNodeID2 = 0,
                                   const MetricType& theMetric  = MetricType()) noexcept
        : NodeID1(theNodeID1),
          NodeID2(theNodeID2),
          Metric(theMetric)
    {
    }

    // Fields
    int        NodeID1; //!< Id of the node in the first BVH tree
    int        NodeID2; //!< Id of the node in the second BVH tree
    MetricType Metric;  //!< Metric computed for the pair of nodes
  };

protected: //! @name Fields
  BVHSetType* myBVHSet1;
  BVHSetType* myBVHSet2;
};

#include "BVH_Traverse.lxx"

#endif // _BVH_Traverse_Header