Skip navigation links
IT services and product development
Menu
TwoLogs
IT services and product development

Source code for C_TreeNode

Download

The source files for this module are listed below.  You can also download the module C_TreeNode as a zip archive; this archive contains all the source files and documentation.

Description

CTreeNode allows you to build object trees, where each node can have an arbitrary number of children.  CTreeNode also allows for easy tree navigation, node manipulation and node retrieval.

Information

CTreeNode can be used to create trees of objects.  A tree is made up of nodes, where each node can have multiple child nodes.  All nodes are arranged in a fixed order under their parent node.  Only pointers to the nodes are stored, so be sure to create each node with new.

To use CTreeNode, you have to derive a class from it.  The interface of CTreeNode is expressed in terms of the template type you use; use your own class' type to make trees of your own class objects.

In your class' constructor you have to feed the 'this' instance pointer to the CTreeNode base class.  This way the tree knows which node it represents.

Once a node is being destructed, it will first destroy it's children and then it will remove itself from the tree.  To easily delete the whole tree, it is thus sufficient to delete the root node.

Each node is placed under a parent node, except for the root node.  Each node therefore has a depth (the number of parents it has), with the root node having a depth of 0.  You can query the depth by using the GetDepth method.  Each node also has a 'child number'; the index of the node under it's parent.  The first node will have child nr. 0.  Use the GetChildNr method to find the node's child nr., and use SetChildNr to assign it a different position in the child list.

The tree can be navigated by using the following methods:

GetRootNode
Get the root node of the tree
GetParent
Get the parent node for this node (or nullptr when the node is the root node)
GetChild, GetFirstChild and GetLastChild
Get a particular child under this node
GetNextSibling and GetPrevSibling
Get a particular sibling to this node
GetNextNode and GetPrevNode
Traverse the entire tree starting at this node; the traversal will be depth first

There are several methods to manage the structure of your tree.  You can use SetChildNr to place a particular node in another position under it's parent node.  Use ClearChildren to destroy all children (they will be destroyed, not just removed from the tree).  Adding new nodes as child nodes can be done via the AddChild method.  And when you want to split off a part of the tree, you can use the MakeOrphan method; this method will make a new root node of the given node.

When you want to extract the path to a node, you can use the GetChildPath method.  You can later use the returned child path to find the node again using the method GetChildFromPath, provided the topology of the relevant part of the tree has not been changed.  This approach also allows you to find mirror nodes in identically shaped trees.

Notes / todo's

  • Represent the list of child nodes with a std::list for code simplification

Files

Each file belonging to this source code module is listed below.

TreeNode.h

/*******************************************************************************

  Version: 4
  Author:  Carl Colijn, TwoLogs
  Contact: c.colijn@twologs.com
  Source:  https://www.twologs.com/sourcecode

  This code is freely distributable, as long as this comment remains intact.
  If you find this source useful, you may use this code in your own projects
  free of charge, but some acknowledgement to the author of this code is always
  appreciated :)
  The source is however distributed 'as is' without waranty and/or support, and
  may not be fit for each and every application.  Use it at your own discretion
  and at your own risk.
  The source already has undergone testing.  This doesn't mean however that all
  bugs are removed from this piece of code.  If you find one of them, please
  contact me about it.  I can however not guarantee when and if the bug will be
  fixed.

  More information about this module can be found in the accompanying HTML file.

*******************************************************************************/

#ifndef INCLUDE_TWOLOGS_COMMON_TREENODE_H
#define INCLUDE_TWOLOGS_COMMON_TREENODE_H

#include <vector>

typedef long CChildNr;
typedef std::vector<CChildNr> CChildPath;

template <typename TItemType>
class CTreeNode {
public:
  // Con- & destructor
  CTreeNode(TItemType* puThis);
  virtual ~CTreeNode();

  // Gets the depth of this node
  long GetDepth() const;

  // Gets the child number with our parent
  CChildNr GetChildNr() const;

  // Gets the path to the node
  // The path consists of an array of child nr's
  CChildPath GetChildPath() const;

  // Retrieves the child at the given child path relative to
  // this node
  TItemType* GetChildFromPath(CChildPath& oPath);

  // Changes our child number
  // If the child number is < 0 or too large, the child is placed at the end
  void SetChildNr(CChildNr nNewNumber);

  // Gets the number of children
  long GetNumChildren() const;

  // Gets the number of descendants
  long GetNumDescendants() const;

  // Gets the root node
  TItemType* GetRootNode() const;

  // Gets the next node (depth-first only)
  // If a root node is given, traversal will not go deeper than this node
  TItemType* GetNextNode(const TItemType* puRootNode = nullptr) const;

  // Gets the previous node (inverse depth-first only)
  // If a root node is given, traversal will not go deeper than this node
  TItemType* GetPrevNode(const TItemType* puRootNode = nullptr) const;

  // Gets the parent node
  TItemType* GetParent() const;

  // Gets the first child node
  TItemType* GetFirstChild() const;

  // Gets the last child node
  TItemType* GetLastChild() const;

  // Gets the given child
  TItemType* GetChild(CChildNr nChildNr) const;

  // Gets the next sibling node
  TItemType* GetNextSibling() const;

  // Gets the previous sibling node
  TItemType* GetPrevSibling() const;

  // Kills all children of this node
  void ClearChildren();

  // Adds the given child at the given child number.
  // If the child number is < 0 or too large, the child is added to the end
  void AddChild(TItemType* puNewChild, CChildNr nChildNr = -1);

  // Makes an orphan of this node
  void MakeOrphan();

private:
  // Administrative info for the node
  CChildNr m_nChildNr;
  long m_nDepth;

  // The surrounding nodes
  TItemType* m_puThis;
  TItemType* m_puParent;
  TItemType* m_puFirstChild;
  TItemType* m_puLastChild;
  TItemType* m_puNextSibling;
  TItemType* m_puPrevSibling;

  // Recursively sets the depth of this node and our subnodes
  void SetDepth(long nNewDepth);
};






// Constructor
template <typename TItemType>
CTreeNode<TItemType>::CTreeNode(TItemType* puThis):
 m_nChildNr(0),
 m_nDepth(0),
 m_puThis(puThis),
 m_puParent(nullptr),
 m_puFirstChild(nullptr),
 m_puLastChild(nullptr),
 m_puNextSibling(nullptr),
 m_puPrevSibling(nullptr) {
}

// Destructor
template <typename TItemType>
CTreeNode<TItemType>::~CTreeNode() {
  ClearChildren();
  MakeOrphan();
}

// Gets the root node
template <typename TItemType>
TItemType* CTreeNode<TItemType>::GetRootNode() const {
  TItemType* puParent = m_puThis;
  while (puParent->m_puParent != nullptr)
    puParent = puParent->m_puParent;
  return puParent;
}

// Gets the next node (depth-first only)
// If a root node is given, traversal will not go deeper than this node
template <typename TItemType>
TItemType* CTreeNode<TItemType>::GetNextNode(const TItemType* puRootNode) const {
  // Look if we can traverse to the first child
  TItemType* puNextNode = nullptr;
  if (m_puFirstChild != nullptr)
    // Yes -> do so
    puNextNode = m_puFirstChild;
  else {
    // No -> look if we're the root node
    if (m_puThis != puRootNode) {
      // No -> look if there's a next sibling
      if (m_puNextSibling != nullptr) {
        // Yes -> go there
        puNextNode = m_puNextSibling;
      } else {
        // No -> find the next sibling at the shallowest parent level allowed
        TItemType* puNextParent = m_puParent;
        while (puNextParent != nullptr && puNextParent != puRootNode) {
          if (puNextParent->m_puNextSibling != nullptr) {
            // Found -> take this one
            puNextNode = puNextParent->m_puNextSibling;
            break;
          } else {
            puNextParent = puNextParent->m_puParent;
          }
        }
      }
    }
  }

  // And return the found node
  return puNextNode;
}

// Gets the previous node (inverse depth-first only)
// If a root node is given, traversal will not go deeper than this node
template <typename TItemType>
TItemType* CTreeNode<TItemType>::GetPrevNode(const TItemType* puRootNode) const {
  // Look if further traversal is required
  TItemType* puPrevNode = nullptr;
  if (m_puThis != puRootNode) {
    // Yes -> look if there's a previous sibling
    if (m_puPrevSibling != nullptr) {
      // Yes -> find it's deepest last child
      puPrevNode = m_puPrevSibling;
      while (puPrevNode->m_puLastChild != nullptr) {
        puPrevNode = puPrevNode->m_puLastChild;
      }
    } else {
      // No -> go to our parent
      puPrevNode = m_puParent;
    }
  }

  // And return the found node
  return puPrevNode;
}

// Gets the depth of this node
template <typename TItemType>
long CTreeNode<TItemType>::GetDepth() const {
  return m_nDepth;
}

// Gets the child number with our parent
template <typename TItemType>
CChildNr CTreeNode<TItemType>::GetChildNr() const {
  return m_nChildNr;
}

// Gets the path to the node
// The path consists of an array of child nr's
template <typename TItemType>
CChildPath CTreeNode<TItemType>::GetChildPath() const {
  CChildPath oPath;
  oPath.resize(m_nDepth);
  const TItemType* pcuNextNode = m_puThis;
  long nPathIndex = m_nDepth - 1;
  while (pcuNextNode->m_puParent != nullptr) {
    oPath[nPathIndex] = pcuNextNode->m_nChildNr;
    pcuNextNode = pcuNextNode->m_puParent;
    --nPathIndex;
  }
  return oPath;
}

// Retrieves the child at the given child path relative to
// this node
template <typename TItemType>
TItemType* CTreeNode<TItemType>::GetChildFromPath(CChildPath& oPath) {
  TItemType* poNode = m_puThis;
  for (auto nNextChildNr: oPath) {
    poNode = poNode->GetChild(nNextChildNr);
  }
  return poNode;
}

// Changes our child number
// If the child number is < 0 or too large, the child is placed at the end
template <typename TItemType>
void CTreeNode<TItemType>::SetChildNr(CChildNr nNewNumber) {
  // Look if we have a parent
  if (m_puParent != nullptr) {
    // Yes -> determine the new child number
    CChildNr nNewChildNr = nNewNumber;
    CChildNr nMaxChildNr = m_puParent->m_puLastChild->m_nChildNr;
    if (nNewChildNr < 0 || nNewChildNr > nMaxChildNr)
      nNewChildNr = nMaxChildNr;

    // Look if a new child number is specified
    if (nNewChildNr != m_nChildNr) {
      // Yes -> take us out of the child chain
      if (m_puNextSibling != nullptr)
        m_puNextSibling->m_puPrevSibling = m_puPrevSibling;
      else
        m_puParent->m_puLastChild = m_puPrevSibling;
      if (m_puPrevSibling != nullptr)
        m_puPrevSibling->m_puNextSibling = m_puNextSibling;
      else
        m_puParent->m_puFirstChild = m_puNextSibling;

      // Re-number all child numbers for the following siblings
      TItemType* puNextSibling = m_puNextSibling;
      while (puNextSibling != nullptr) {
        --puNextSibling->m_nChildNr;
        puNextSibling = puNextSibling->m_puNextSibling;
      }

      // Get the child to insert before and after
      TItemType* puBeforeSibling = m_puParent->m_puFirstChild;
      TItemType* puAfterSibling = nullptr;
      CChildNr nFindChildNr = nNewChildNr;
      while (nFindChildNr > 0 && puBeforeSibling != nullptr) {
        puAfterSibling = puBeforeSibling;
        puBeforeSibling = puBeforeSibling->m_puNextSibling;
        if (nFindChildNr > 0)
          --nFindChildNr;
      }

      // Link us between the new siblings
      m_puPrevSibling = puAfterSibling;
      m_puNextSibling = puBeforeSibling;
      if (puBeforeSibling != nullptr)
        puBeforeSibling->m_puPrevSibling = m_puThis;
      else
        m_puParent->m_puLastChild = m_puThis;
      if (puAfterSibling != nullptr)
        puAfterSibling->m_puNextSibling = m_puThis;
      else
        m_puParent->m_puFirstChild = m_puThis;

      // Note the new child number
      m_nChildNr = nNewChildNr;

      // And remap the following child's numbers
      puNextSibling = m_puNextSibling;
      while (puNextSibling != nullptr) {
        ++puNextSibling->m_nChildNr;
        puNextSibling = puNextSibling->m_puNextSibling;
      }
    }
  }
}

// Gets the number of children
template <typename TItemType>
long CTreeNode<TItemType>::GetNumChildren() const {
  return m_puLastChild == nullptr? 0: m_puLastChild->m_nChildNr + 1;
}

// Gets the number of descendants
template <typename TItemType>
long CTreeNode<TItemType>::GetNumDescendants() const {
  long nNumDescendants = GetNumChildren();
  TItemType* puNextChild = m_puFirstChild;
  while (puNextChild != nullptr) {
    nNumDescendants += puNextChild->GetNumDescendants();
    puNextChild = puNextChild->m_puNextSibling;
  }
  return nNumDescendants;
}

// Gets the parent node
template <typename TItemType>
TItemType* CTreeNode<TItemType>::GetParent() const {
  return m_puParent;
}

// Gets the first child node
template <typename TItemType>
TItemType* CTreeNode<TItemType>::GetFirstChild() const {
  return m_puFirstChild;
}

// Gets the given child
template <typename TItemType>
TItemType* CTreeNode<TItemType>::GetChild(CChildNr nChildNr) const {
  TItemType* puChild = m_puFirstChild;
  while (nChildNr > 0 && puChild != nullptr) {
    puChild = puChild->m_puNextSibling;
    --nChildNr;
  }
  return puChild;
}

// Gets the last child node
template <typename TItemType>
TItemType* CTreeNode<TItemType>::GetLastChild() const {
  return m_puLastChild;
}

// Gets the next sibling node
template <typename TItemType>
TItemType* CTreeNode<TItemType>::GetNextSibling() const {
  return m_puNextSibling;
}

// Gets the previous sibling node
template <typename TItemType>
TItemType* CTreeNode<TItemType>::GetPrevSibling() const {
  return m_puPrevSibling;
}

// Kills all children of this node
template <typename TItemType>
void CTreeNode<TItemType>::ClearChildren() {
  // Loop over all children
  TItemType* puNextChild = m_puFirstChild;
  while (puNextChild != nullptr) {
    // Note the child to delete
    TItemType* puDeleteChild = puNextChild;

    // Go to the next child
    puNextChild = puNextChild->m_puNextSibling;

    // And delete the child
    delete puDeleteChild;
  }

  // And no children left
  m_puFirstChild = nullptr;
  m_puLastChild = nullptr;
}

// Adds the given child at the given child number.
// If the child number is < 0 or too large, the child is added to the end
template <typename TItemType>
void CTreeNode<TItemType>::AddChild(TItemType* puNewChild, long nChildNr) {
  // Make sure it's unlinked from any other parent
  puNewChild->MakeOrphan();

  // Get the new child number
  CChildNr nMaxChildNr = m_puLastChild == nullptr?
    0:
    (m_puLastChild->m_nChildNr + 1);
  if (nChildNr < 0 || nChildNr > nMaxChildNr)
    nChildNr = nMaxChildNr;

  // Get the child to insert before and after
  TItemType* puBeforeChild = m_puFirstChild;
  TItemType* puAfterChild = nullptr;
  CChildNr nFindChildNr = nChildNr;
  while (nFindChildNr > 0 && puBeforeChild != nullptr) {
    puAfterChild = puBeforeChild;
    puBeforeChild = puBeforeChild->m_puNextSibling;
    --nFindChildNr;
  }

  // Link the child between the other siblings
  puNewChild->m_puParent = m_puThis;
  puNewChild->m_puPrevSibling = puAfterChild;
  puNewChild->m_puNextSibling = puBeforeChild;
  if (puBeforeChild != nullptr)
    puBeforeChild->m_puPrevSibling = puNewChild;
  else
    m_puLastChild = puNewChild;
  if (puAfterChild != nullptr)
    puAfterChild->m_puNextSibling = puNewChild;
  else
    m_puFirstChild = puNewChild;

  // Note the child's number
  puNewChild->m_nChildNr = nChildNr;

  // Remap the following child's numbers
  TItemType* puNextChild = puNewChild->m_puNextSibling;
  while (puNextChild != nullptr) {
    ++puNextChild->m_nChildNr;
    puNextChild = puNextChild->m_puNextSibling;
  }

  // And note it's depth
  puNewChild->SetDepth(m_nDepth + 1);
}

// Removes us from our parent's list of children
template <typename TItemType>
void CTreeNode<TItemType>::MakeOrphan() {
  // Look if we're an orphan already
  if (m_puParent != nullptr) {
    // No -> remove us from in between our siblings
    if (m_puPrevSibling != nullptr)
      m_puPrevSibling->m_puNextSibling = m_puNextSibling;
    else
      m_puParent->m_puFirstChild = m_puNextSibling;
    if (m_puNextSibling != nullptr)
      m_puNextSibling->m_puPrevSibling = m_puPrevSibling;
    else
      m_puParent->m_puLastChild = m_puPrevSibling;

    // Re-number all child numbers for the following siblings
    TItemType* puNextSibling = m_puNextSibling;
    while (puNextSibling != nullptr) {
      --puNextSibling->m_nChildNr;
      puNextSibling = puNextSibling->m_puNextSibling;
    }

    // We're an orphan now
    m_puParent = nullptr;
    m_nChildNr = 0;

    // And set our depth
    SetDepth(0);
  }
}

// Recursively sets the depth of this node and our subnodes
template <typename TItemType>
void CTreeNode<TItemType>::SetDepth(long nNewDepth) {
  // Note our new depth
  m_nDepth = nNewDepth;

  // And change the depth of our children accordingly
  TItemType* puNextChild = m_puFirstChild;
  while (puNextChild != nullptr) {
    puNextChild->SetDepth(nNewDepth + 1);
    puNextChild = puNextChild->m_puNextSibling;
  }
}

#endif // INCLUDE_TWOLOGS_COMMON_TREENODE_H