OCCT

// Copyright (c) 2026 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 _BRepGraph_ParentExplorer_HeaderFile
#define _BRepGraph_ParentExplorer_HeaderFile

#include <BRepGraph.hxx>
#include <BRepGraphInc_Definition.hxx>
#include <BRepGraphInc_Instance.hxx>
#include <BRepGraphInc_Reference.hxx>
#include <BRepGraph_ParentIterator.hxx>
#include <NCollection_BaseAllocator.hxx>
#include <NCollection_ForwardRange.hxx>
#include <NCollection_LocalArray.hxx>
#include <TopAbs_Orientation.hxx>
#include <TopLoc_Location.hxx>

#include <optional>

//! @brief Upward occurrence-aware parent traversal for BRepGraph.
//! @see BRepGraph class comment "Iterator guide" for choosing between iterator types.
//!
//! Enumerates all ancestor nodes reachable from a starting node.
//! Traversal is path-aware: when the same definition is reached through multiple
//! occurrence paths, each path contributes its own parent sequence with its own
//! accumulated location and orientation.
//!
//! The traversal follows the actual graph structure transparently - every node
//! kind is visited as a distinct entity (no hidden collapses):
//!   Vertex -> Edge,  Edge -> CoEdge,  CoEdge -> Wire,  Wire -> Face,
//!   Face -> Shell,  Shell -> Solid,  Solid -> CompSolid/Compound,
//!   topology root -> Occurrence, Product child -> Occurrence,
//!   Occurrence -> parent Product.
//!
//! ## Traversal modes
//! - **Recursive**: walks the full ancestor chain to the graph roots.
//!   Without target kind, all ancestors are emitted.
//!   With target kind, only matching ancestors are emitted but intermediate
//!   levels are traversed to reach them.
//! - **DirectParents**: yields only the immediate parents of the starting node.
//!   No ascent into grandparents.  With target kind, only parents
//!   matching the kind are returned.
class BRepGraph_ParentExplorer
{
public:
  DEFINE_STANDARD_ALLOC

  //! Relationship kind between Current() and CurrentChild().
  enum class LinkKind
  {
    None,       //!< No current branch step.
    Reference,  //!< Current() owns CurrentChild() through a RefId.
    Structural, //!< Current() reaches CurrentChild() through a structural non-ref link.
  };

  //! Upward traversal strategy.
  enum class TraversalMode
  {
    Recursive,     //!< Walk the full ancestor chain to the graph roots.
    DirectParents, //!< Yields only the immediate parents of the starting node.
  };

  //! Consolidated configuration for the explorer.
  //!
  //! The `Config`-based constructor is the preferred idiom: new options can be
  //! added as fields without additional constructor overloads.
  //!
  //! @code
  //!   BRepGraph_ParentExplorer::Config aConfig;
  //!   aConfig.Mode       = BRepGraph_ParentExplorer::TraversalMode::DirectParents;
  //!   aConfig.TargetKind = BRepGraph_NodeId::Kind::Shell;
  //!   for (auto [id, loc, ori] : BRepGraph_ParentExplorer(aGraph, aNode, aConfig)) { ... }
  //! @endcode
  struct Config
  {
    TraversalMode Mode = TraversalMode::Recursive;
    std::optional<BRepGraph_NodeId::Kind>
      TargetKind;                                    //!< Emit only this kind (no value = emit all).
    std::optional<BRepGraph_NodeId::Kind> AvoidKind; //!< Do not ascend through this kind.
    bool EmitAvoidKind = false;                      //!< Emit matching avoid-kind ancestors once.
  };

  //! Preferred long-term constructor: all tuning knobs in `Config`.
  //! @param[in] theGraph  graph to walk
  //! @param[in] theNode   starting node whose ancestors are explored
  //! @param[in] theConfig traversal configuration
  Standard_EXPORT BRepGraph_ParentExplorer(const BRepGraph&       theGraph,
                                           const BRepGraph_NodeId theNode,
                                           const Config&          theConfig);

  //! Explore all parents of the starting node.
  //! @param[in] theGraph graph to walk
  //! @param[in] theNode  starting node whose ancestors are explored
  Standard_EXPORT BRepGraph_ParentExplorer(const BRepGraph&       theGraph,
                                           const BRepGraph_NodeId theNode);

  //! Explore parents of the starting node using the given traversal mode.
  //! @param[in] theGraph graph to walk
  //! @param[in] theNode  starting node whose ancestors are explored
  //! @param[in] theMode  traversal strategy (recursive or direct parents)
  Standard_EXPORT BRepGraph_ParentExplorer(const BRepGraph&       theGraph,
                                           const BRepGraph_NodeId theNode,
                                           const TraversalMode    theMode);

  //! Explore all parents while pruning branches at the avoid kind.
  //! @param[in] theGraph        graph to walk
  //! @param[in] theNode         starting node whose ancestors are explored
  //! @param[in] theAvoidKind    node kind to avoid ascending through
  //! @param[in] theEmitAvoidKind if true, emit matching avoid-kind ancestors once
  //! @param[in] theMode         traversal strategy
  Standard_EXPORT BRepGraph_ParentExplorer(
    const BRepGraph&                             theGraph,
    const BRepGraph_NodeId                       theNode,
    const std::optional<BRepGraph_NodeId::Kind>& theAvoidKind,
    const bool                                   theEmitAvoidKind,
    const TraversalMode                          theMode = TraversalMode::Recursive);

  //! Explore only parents of the given kind.
  //! @param[in] theGraph     graph to walk
  //! @param[in] theNode      starting node whose ancestors are explored
  //! @param[in] theTargetKind kind of nodes to emit
  Standard_EXPORT BRepGraph_ParentExplorer(const BRepGraph&             theGraph,
                                           const BRepGraph_NodeId       theNode,
                                           const BRepGraph_NodeId::Kind theTargetKind);

  //! Explore only parents of the given kind using the given traversal mode.
  //! @param[in] theGraph     graph to walk
  //! @param[in] theNode      starting node whose ancestors are explored
  //! @param[in] theTargetKind kind of nodes to emit
  //! @param[in] theMode      traversal strategy
  Standard_EXPORT BRepGraph_ParentExplorer(const BRepGraph&             theGraph,
                                           const BRepGraph_NodeId       theNode,
                                           const BRepGraph_NodeId::Kind theTargetKind,
                                           const TraversalMode          theMode);

  //! Explore parents of the given kind while pruning branches at the avoid kind.
  //! @param[in] theGraph        graph to walk
  //! @param[in] theNode         starting node whose ancestors are explored
  //! @param[in] theTargetKind   kind of nodes to emit
  //! @param[in] theAvoidKind    node kind to avoid ascending through
  //! @param[in] theEmitAvoidKind if true, emit matching avoid-kind ancestors once
  //! @param[in] theMode         traversal strategy
  Standard_EXPORT BRepGraph_ParentExplorer(
    const BRepGraph&                             theGraph,
    const BRepGraph_NodeId                       theNode,
    const BRepGraph_NodeId::Kind                 theTargetKind,
    const std::optional<BRepGraph_NodeId::Kind>& theAvoidKind,
    const bool                                   theEmitAvoidKind,
    const TraversalMode                          theMode = TraversalMode::Recursive);

  //! Returns the traversal configuration this explorer was constructed with.
  //! Read-only - configuration is fixed for the lifetime of the explorer.
  [[nodiscard]] const Config& GetConfig() const { return myConfig; }

  //! True if another matching parent is available.
  [[nodiscard]] bool More() const { return myHasMore; }

  //! Advance to the next matching parent.
  Standard_EXPORT void Next();

  //! Current matching ancestor node with accumulated location and orientation.
  [[nodiscard]] Standard_EXPORT BRepGraphInc::NodeInstance Current() const;

  //! Current matching ancestor definition without copying placement state.
  [[nodiscard]] BRepGraph_NodeId CurrentNode() const noexcept { return myCurrent; }

  //! Current accumulated location. The reference remains valid until Next().
  [[nodiscard]] Standard_EXPORT const TopLoc_Location& CurrentLocation() const;

  //! Current accumulated orientation.
  [[nodiscard]] Standard_EXPORT TopAbs_Orientation CurrentOrientation() const;

  //! Returns the immediate child of Current() on the currently emitted branch.
  //! Returns invalid NodeId when no current ancestor is available.
  [[nodiscard]] Standard_EXPORT BRepGraph_NodeId CurrentChild() const;

  //! Returns how Current() is linked to CurrentChild().
  [[nodiscard]] Standard_EXPORT LinkKind CurrentLinkKind() const;

  //! Returns the exact parent-owned RefId linking Current() to CurrentChild(),
  //! when that branch step is represented by a reference entry.
  //!
  //! Some upward steps are structural and therefore have no parent-owned ref
  //! entry even though the parent itself is still emitted by the explorer.
  //! In those cases this method returns an invalid RefId, for example for
  //! CoEdge->Edge and Occurrence->Product/topology-root.
  [[nodiscard]] Standard_EXPORT BRepGraph_RefId CurrentRef() const;

  //! Accumulated location at the starting node of the current branch.
  [[nodiscard]] Standard_EXPORT const TopLoc_Location& LeafLocation() const;

  //! Accumulated orientation at the starting node of the current branch.
  [[nodiscard]] Standard_EXPORT TopAbs_Orientation LeafOrientation() const;

  //! True if Current() is the explicit root node of the current branch.
  [[nodiscard]] Standard_EXPORT bool IsCurrentBranchRoot() const;

  //! Returns an STL-compatible iterator for range-based for loops.
  NCollection_ForwardRangeIterator<BRepGraph_ParentExplorer> begin()
  {
    return NCollection_ForwardRangeIterator<BRepGraph_ParentExplorer>(this);
  }

  //! Returns a sentinel marking the end of iteration.
  NCollection_ForwardRangeSentinel end() const { return NCollection_ForwardRangeSentinel{}; }

private:
  struct StackFrame
  {
    BRepGraph_NodeId                   Node;
    BRepGraph_ParentIterator::Position NextParentPosition;
    int                                StepToChild = -1;
    BRepGraph_RefId                    RefToChild;
    int                                LocationIndex  = -1;
    TopAbs_Orientation                 AccOrientation = TopAbs_FORWARD;
  };

  Standard_EXPORT void startTraversal();
  Standard_EXPORT void advance();
  Standard_EXPORT bool emitNextFromCurrentBranch();
  Standard_EXPORT void backtrackAfterBranchEmission();
  Standard_EXPORT bool nextParentFrame(StackFrame& theChild, StackFrame& theParent) const;
  Standard_EXPORT void prepareCurrentBranch();
  Standard_EXPORT void applyTransition(const BRepGraph_NodeId theParent,
                                       const BRepGraph_NodeId theChild,
                                       const int              theStepToChild,
                                       const BRepGraph_RefId  theRefToChild,
                                       int&                   theLocationIndex,
                                       TopAbs_Orientation&    theOrientation);

  [[nodiscard]] Standard_EXPORT int branchRootFrame() const;

  static std::optional<BRepGraph_NodeId::Kind> normalizeAvoidKind(
    const BRepGraph_NodeId                       theNode,
    const std::optional<BRepGraph_NodeId::Kind>& theTargetKind,
    const std::optional<BRepGraph_NodeId::Kind>& theAvoidKind);

  static bool canContainTarget(const BRepGraph_NodeId::Kind theParentKind,
                               const BRepGraph_NodeId::Kind theTargetKind);

  [[nodiscard]] Standard_EXPORT bool pushFrame(StackFrame&& theFrame);
  Standard_EXPORT void               popFrame();

  int pushLocation(TopLoc_Location theLocation);

  [[nodiscard]] const TopLoc_Location& frameLocation(const StackFrame& theFrame) const
  {
    static const TopLoc_Location THE_IDENTITY;
    return theFrame.LocationIndex >= 0 ? myLocations[theFrame.LocationIndex] : THE_IDENTITY;
  }

  [[nodiscard]] bool matchesAvoid(const BRepGraph_NodeId theNode) const
  {
    return myConfig.AvoidKind.has_value() && theNode.NodeKind == *myConfig.AvoidKind;
  }

  [[nodiscard]] bool shouldEmit(const BRepGraph_NodeId theNode) const
  {
    const bool isAvoid = matchesAvoid(theNode);
    const bool isFind =
      !myConfig.TargetKind.has_value() || theNode.NodeKind == *myConfig.TargetKind;
    return myConfig.EmitAvoidKind ? (isFind || isAvoid) : (isFind && !isAvoid);
  }

  StackFrame& topFrame() { return myStack[myStackTop]; }

  const StackFrame& topFrame() const { return myStack[myStackTop]; }

private:
  static constexpr int THE_INLINE_STACK_SIZE = 16;
  //! Inline fast path; deeper non-identity ChildRef/OccurrenceRef chains grow dynamically.
  static constexpr int THE_INLINE_LOCATION_SIZE = 2;

  const BRepGraph* myGraph = nullptr;
  BRepGraph_NodeId myNode;
  Config           myConfig; //!< Traversal configuration - single source of truth.

  NCollection_LocalArray<StackFrame, THE_INLINE_STACK_SIZE>         myStack;
  NCollection_LocalArray<TopLoc_Location, THE_INLINE_LOCATION_SIZE> myLocations;
  int                                                               myStackTop     = -1;
  int                                                               myLocationTop  = -1;
  int                                                               myEmitIndex    = -1;
  int                                                               myCurrentFrame = -1;
  uint32_t                                                          myMaxDepth     = 0;

  BRepGraph_NodeId myCurrent;
  bool             myHasMore = false;
};

#endif // _BRepGraph_ParentExplorer_HeaderFile