treeClass.h

Go to the documentation of this file.

/*******************************************************************************
** Copyright (c) 2025 MAK Technologies, Inc.
** All rights reserved.
*******************************************************************************/
 
//! \file treeClass.h
//! \ingroup vreUtil
//! \brief Provides a generic hierarchical tree structure implementation
//!
//! This file defines the DtTreeClass template which provides a robust tree structure
//! implementation for building parent-child hierarchies in the VREngage system.
//! It supports owned and unowned children, name-based lookups, and various tree
//! manipulation operations.
 
#pragma once
#include "vreUtil/baseClass.h"
 
#include "vreUtil/logger.h"
 
#include <memory>
#include <functional>
#include <list>
#include <map>
 
namespace makVre
{
 
//! \brief Template class implementing a tree structure with parent-child relationships
//! \tparam SELF_T The derived class type (CRTP pattern)
//! \tparam SUPER_T The base class type, defaults to DtSpObject
//!
//! This class provides a comprehensive implementation of a tree data structure
//! with smart pointer ownership management, child lookup by name, and various
//! traversal capabilities. It's designed to be used as a base class for objects
//! that need to exist in hierarchical relationships.
template <class SELF_T, class SUPER_T = DtSpObject>
class DtTreeClass : public DtSpSubClass<SELF_T, SUPER_T>
{
public:
   //! \brief Shared pointer type for this class
   using Sptr = std::shared_ptr<SELF_T>;
   //! \brief Function type for child traversal callbacks
   using ForChildFn = std::function<bool(Sptr child)>;
   //! \brief Function type for child search predicates
   using FindChildFn = std::function<bool(Sptr child)>;
 
   //! \brief Default constructor
   //!
   //! Creates a new tree node with ownership of children enabled by default
   DtTreeClass()
      : myOwnsChildren(true)
   {
   }
 
   //! \brief Virtual destructor
   //!
   //! Removes all children when the node is destroyed
   virtual ~DtTreeClass() override { removeAllChildren(); }
 
   //! \brief Sets whether this node owns its children
   //! \param owns True if this node should own its children, false otherwise
   //!
   //! When a node owns its children, it maintains strong references to them,
   //! preventing their destruction as long as the parent exists
   virtual void setOwnsChildren(bool owns) { myOwnsChildren = owns; }
 
   //! \brief Checks if this node owns its children
   //! \return True if this node owns its children, false otherwise
   virtual bool ownsChildren() { return myOwnsChildren; }
 
   //! \brief Adds a child to this node
   //! \param child Shared pointer to the child node to add
   //! \return True if the child was added successfully, false otherwise
   //!
   //! This method adds a child to this node if:
   //! - The child is not null
   //! - The child is not already a child of this node
   //! - The child does not already have a parent
   //!
   //! The child is added to either the owned or unowned list based on
   //! the current ownership setting of this node.
   virtual bool addChild(Sptr child)
   {
      pruneChildren();
 
      if (!child)
      {
         LOG_WARN("UTIL") << "Cannot add null child ptr." << std::endl;
         return false;
      }
 
      if (isChild(child))
      {
         return true;
      }
 
      if (child->parent())
      {
         return false;
      }
 
      if (ownsChildren())
      {
         myOwnedChildren.emplace_back(child);
      }
      else
      {
         myUnownedChildren.emplace_back(child);
      }
 
      child->setParent(this->self());
 
      return true;
   }
 
   //! \brief Removes a child from this node
   //! \param child Shared pointer to the child node to remove
   //! \return True if the child was removed successfully, false if not found
   //!
   //! This method searches for the child in both the owned and unowned
   //! children lists and removes it if found. It also clears the parent
   //! reference from the child.
   virtual bool removeChild(Sptr child)
   {
      bool found = false;
      {
         auto findIt = myOwnedChildren.begin();
         for (; findIt != myOwnedChildren.end(); ++findIt)
         {
            if (*findIt == child)
            {
               myOwnedChildren.erase(findIt);
               found = true;
               break;
            }
         }
      }
      if (!found)
      {
         auto findIt = myUnownedChildren.begin();
         for (; findIt != myUnownedChildren.end(); ++findIt)
         {
            if (findIt->lock() == child)
            {
               myUnownedChildren.erase(findIt);
               found = true;
               break;
            }
         }
      }
 
      if (found && child->parent() != this->self())
      {
         LOG_WARN("UTIL") << "Parent of child did not match this." << std::endl;
      }
 
      if (child->parent() == this->self())
      {
         child->setParent(Sptr());
      }
 
      pruneChildren();
 
      return found;
   }
 
   //! \brief Removes all children from this node
   //!
   //! This method removes all children from this node, converting owned children
   //! to unowned first to prevent their destruction during the process. It then
   //! clears the parent reference from all children and clears internal lists.
   virtual void removeAllChildren()
   {
      // First convert all owned children to unowned to prevent destruction
      for (auto child : myOwnedChildren)
      {
         myUnownedChildren.emplace_back(child);
      }
 
      myOwnedChildren.clear();
      pruneChildren();
 
      // Clear parent reference from all children
      for (auto child : myUnownedChildren)
      {
         child.lock()->setParent(Sptr());
      }
 
      myUnownedChildren.clear();
      myChildrenByName.clear();
   }
 
   //! \brief Iterates over all children and applies a function to each
   //! \param fn Function to apply to each child
   //! \return True if the function was applied to all children, false if interrupted
   //!
   //! This method iterates over all children (both owned and unowned) and applies
   //! the provided function to each. If the function returns false for any child,
   //! iteration stops and the method returns false. Otherwise, it returns true.
   //!
   //! Note that it creates copies of the child lists before iteration to allow
   //! safe modification of the lists during iteration.
   virtual bool forEachChild(ForChildFn fn)
   {
      OwnedChildList ownedCopy = myOwnedChildren;
      for (auto child : ownedCopy)
      {
         if (!fn(child))
         {
            return false;
         }
      }
      ownedCopy.clear();
 
      pruneChildren();
 
      UnownedChildList unownedCopy = myUnownedChildren;
      for (auto child : unownedCopy)
      {
         if (!fn(child.lock()))
         {
            return false;
         }
      }
      unownedCopy.clear();
 
      return true;
   }
 
   //! \brief Finds a child that matches a given predicate
   //! \param fn Predicate function to test each child
   //! \return Shared pointer to the first matching child, or null if none found
   //!
   //! This method searches through all children (both owned and unowned) and
   //! returns the first child for which the predicate function returns true.
   //! If no child matches, it returns a null pointer.
   virtual Sptr findChild(FindChildFn fn)
   {
      // First check owned children
      for (auto child : myOwnedChildren)
      {
         if (fn(child))
         {
            return child;
         }
      }
 
      pruneChildren();
 
      // Then check unowned children
      for (auto child : myUnownedChildren)
      {
         if (fn(child.lock()))
         {
            return child.lock();
         }
      }
 
      return Sptr();
   }
 
   //! \brief Checks if a given node is a child of this node
   //! \param child Shared pointer to the node to check
   //! \return True if the node is a child of this node, false otherwise
   //!
   //! This method checks both the owned and unowned children lists to determine
   //! if the specified node is a direct child of this node.
   virtual bool isChild(Sptr child)
   {
      // Check owned children
      {
         auto findIt = myOwnedChildren.begin();
         for (; findIt != myOwnedChildren.end(); ++findIt)
         {
            if (*findIt == child)
            {
               return true;
            }
         }
      }
      // Check unowned children
      {
         auto findIt = myUnownedChildren.begin();
         for (; findIt != myUnownedChildren.end(); ++findIt)
         {
            if (findIt->lock() == child)
            {
               return true;
            }
         }
      }
      return false;
   }
 
   //! \brief Finds a child by name
   //! \param name The name of the child to find
   //! \return Shared pointer to the child with the given name, or null if none found
   //!
   //! This method first checks a name-to-child map for fast lookup. If the child
   //! is not found in the map, it searches all children for one with the given name.
   //! If found, it adds the child to the name map for faster subsequent lookups.
   //!
   //! The method also performs cleanup of expired references in the name map.
   virtual Sptr findChild(const std::string& name)
   {
      // First, check the name map for fast lookup
      {
         auto findIt = myChildrenByName.find(name);
         if (findIt != myChildrenByName.end())
         {
            // Check for expired reference
            if (!findIt->second.expired())
            {
               Sptr found = findIt->second.lock();
               // Check that the name still matches
               if (found->name() == name)
               {
                  return findIt->second.lock();
               }
            }
 
            // If we're still here, either the reference expired or
            // the name changed. Clean up the defunct entry.
            myChildrenByName.erase(findIt);
         }
      }
 
      // Clean up any expired references in the name map
      {
         auto it = myChildrenByName.begin();
         while (it != myChildrenByName.end())
         {
            if (it->second.expired())
            {
               it = myChildrenByName.erase(it);
            }
            else
            {
               ++it;
            }
         }
      }
 
      // Failed to find in the name map, so search all children
      Sptr found = findChild(
         [&](Sptr child)
         {
            return child->name() == name;
         });
 
      if (found)
      {
         // Add the name to the map for faster subsequent lookup
         myChildrenByName[name] = found;
         return found;
      }
 
      return Sptr();
   }
 
   //! \brief Gets the total number of children
   //! \return The total number of children (both owned and unowned)
   virtual unsigned int numChildren() { return myOwnedChildren.size() + myUnownedChildren.size(); }
 
   //! \brief Checks if this node has any children
   //! \return True if this node has at least one child, false otherwise
   virtual bool hasChildren() { return numChildren() > 0; }
 
   //! \brief Gets the parent of this node
   //! \return Shared pointer to the parent node, or null if no parent
   virtual Sptr parent() { return myParent.lock(); }
 
protected:
   //! \brief Sets the parent of this node
   //! \param parent Shared pointer to the new parent node
   //!
   //! This protected method is called by the addChild and removeChild methods
   //! to update the parent reference of this node.
   virtual void setParent(Sptr parent) { myParent = parent; }
 
   //! \brief Removes expired weak references from the unowned children list
   //!
   //! This protected method is called internally to clean up any weak references
   //! to children that have been destroyed. It iterates through the unowned
   //! children list and removes any expired references.
   virtual void pruneChildren()
   {
      auto it = myUnownedChildren.begin();
      while (it != myUnownedChildren.end())
      {
         if (it->expired())
         {
            it = myUnownedChildren.erase(it);
         }
         else
         {
            ++it;
         }
      }
   }
 
protected:
   //! \brief Weak pointer type for this class
   using Wptr = std::weak_ptr<SELF_T>;
   //! \brief Type for the list of owned children
   using OwnedChildList = std::list<Sptr>;
   //! \brief Type for the list of unowned children
   using UnownedChildList = std::list<Wptr>;
   //! \brief Type for the map of child names to child pointers
   using ChildNameMap = std::map<std::string, Wptr>;
 
   //! \brief List of children owned by this node (strong references)
   OwnedChildList myOwnedChildren;
   //! \brief List of children not owned by this node (weak references)
   UnownedChildList myUnownedChildren;
 
   //! \brief Map of child names to child pointers for fast lookup
   ChildNameMap myChildrenByName;
 
   //! \brief Flag indicating whether this node owns its children
   bool myOwnsChildren;
 
   //! \brief Weak reference to the parent node
   Wptr myParent;
};
 
} // namespace makVre