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 TChildNr;
typedef std::vector<TChildNr> TChildPath;

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

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

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

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

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

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

  // 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* rootItemPtr = 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* rootItemPtr = 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(TChildNr childNr) 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* newChildPtr, TChildNr childNr = -1);

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

private:
  // Administrative info for the node
  TChildNr m_childNr;
  long m_depth;

  // The surrounding nodes
  TItemType* m_thisPtr;
  TItemType* m_parentPtr;
  TItemType* m_firstChildPtr;
  TItemType* m_lastChildPtr;
  TItemType* m_nextSiblingPtr;
  TItemType* m_prevSiblingPtr;

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






// Constructor
template <typename TItemType>
TTreeNode<TItemType>::TTreeNode(TItemType* thisPtr):
 m_childNr(0),
 m_depth(0),
 m_thisPtr(thisPtr),
 m_parentPtr(nullptr),
 m_firstChildPtr(nullptr),
 m_lastChildPtr(nullptr),
 m_nextSiblingPtr(nullptr),
 m_prevSiblingPtr(nullptr) {
}

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

// Gets the root node
template <typename TItemType>
TItemType* TTreeNode<TItemType>::GetRootNode() const {
  TItemType* parentPtr = m_thisPtr;
  while (parentPtr->m_parentPtr != nullptr)
    parentPtr = parentPtr->m_parentPtr;
  return parentPtr;
}

// 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* TTreeNode<TItemType>::GetNextNode(const TItemType* rootItemPtr) const {
  // Look if we can traverse to the first child
  TItemType* nextItemPtr = nullptr;
  if (m_firstChildPtr != nullptr)
    // Yes -> do so
    nextItemPtr = m_firstChildPtr;
  else {
    // No -> look if we're the root node
    if (m_thisPtr != rootItemPtr) {
      // No -> look if there's a next sibling
      if (m_nextSiblingPtr != nullptr) {
        // Yes -> go there
        nextItemPtr = m_nextSiblingPtr;
      } else {
        // No -> find the next sibling at the shallowest parent level allowed
        TItemType* nextParentPtr = m_parentPtr;
        while (nextParentPtr != nullptr && nextParentPtr != rootItemPtr) {
          if (nextParentPtr->m_nextSiblingPtr != nullptr) {
            // Found -> take this one
            nextItemPtr = nextParentPtr->m_nextSiblingPtr;
            break;
          } else {
            nextParentPtr = nextParentPtr->m_parentPtr;
          }
        }
      }
    }
  }

  // And return the found node
  return nextItemPtr;
}

// 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* TTreeNode<TItemType>::GetPrevNode(const TItemType* rootItemPtr) const {
  // Look if further traversal is required
  TItemType* prevItemPtr = nullptr;
  if (m_thisPtr != rootItemPtr) {
    // Yes -> look if there's a previous sibling
    if (m_prevSiblingPtr != nullptr) {
      // Yes -> find it's deepest last child
      prevItemPtr = m_prevSiblingPtr;
      while (prevItemPtr->m_lastChildPtr != nullptr) {
        prevItemPtr = prevItemPtr->m_lastChildPtr;
      }
    } else {
      // No -> go to our parent
      prevItemPtr = m_parentPtr;
    }
  }

  // And return the found node
  return prevItemPtr;
}

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

// Gets the child number with our parent
template <typename TItemType>
TChildNr TTreeNode<TItemType>::GetChildNr() const {
  return m_childNr;
}

// Gets the path to the node
// The path consists of an array of child nr's
template <typename TItemType>
TChildPath TTreeNode<TItemType>::GetChildPath() const {
  TChildPath childPath;
  childPath.resize(m_depth);
  const TItemType* nextItemPtr = m_thisPtr;
  long pathIndex = m_depth - 1;
  while (nextItemPtr->m_parentPtr != nullptr) {
    childPath[pathIndex] = nextItemPtr->m_childNr;
    nextItemPtr = nextItemPtr->m_parentPtr;
    --pathIndex;
  }
  return childPath;
}

// Retrieves the child at the given child path relative to
// this node
template <typename TItemType>
TItemType* TTreeNode<TItemType>::GetChildFromPath(TChildPath& childPath) {
  TItemType* itemPtr = m_thisPtr;
  for (auto nextChildNr: childPath) {
    itemPtr = itemPtr->GetChild(nextChildNr);
  }
  return itemPtr;
}

// Changes our child number
// If the child number is < 0 or too large, the child is placed at the end
template <typename TItemType>
void TTreeNode<TItemType>::SetChildNr(TChildNr newChildNr) {
  // Look if we have a parent
  if (m_parentPtr != nullptr) {
    // Yes -> determine the new child number
    TChildNr maxChildNr = m_parentPtr->m_lastChildPtr->m_childNr;
    if (newChildNr < 0 || newChildNr > maxChildNr) {
      newChildNr = maxChildNr;
    }

    // Look if a new child number is specified
    if (newChildNr != m_childNr) {
      // Yes -> take us out of the child chain
      if (m_nextSiblingPtr != nullptr) {
        m_nextSiblingPtr->m_prevSiblingPtr = m_prevSiblingPtr;
      } else {
        m_parentPtr->m_lastChildPtr = m_prevSiblingPtr;
      }
      if (m_prevSiblingPtr != nullptr) {
        m_prevSiblingPtr->m_nextSiblingPtr = m_nextSiblingPtr;
      } else {
        m_parentPtr->m_firstChildPtr = m_nextSiblingPtr;
      }

      // Re-number all child numbers for the following siblings
      TItemType* nextSiblingPtr = m_nextSiblingPtr;
      while (nextSiblingPtr != nullptr) {
        --nextSiblingPtr->m_childNr;
        nextSiblingPtr = nextSiblingPtr->m_nextSiblingPtr;
      }

      // Get the child to insert before and after
      TItemType* beforeSiblingPtr = m_parentPtr->m_firstChildPtr;
      TItemType* afterSiblingPtr = nullptr;
      TChildNr foundChildNr = newChildNr;
      while (foundChildNr > 0 && beforeSiblingPtr != nullptr) {
        afterSiblingPtr = beforeSiblingPtr;
        beforeSiblingPtr = beforeSiblingPtr->m_nextSiblingPtr;
        if (foundChildNr > 0) {
          --foundChildNr;
        }
      }

      // Link us between the new siblings
      m_prevSiblingPtr = afterSiblingPtr;
      m_nextSiblingPtr = beforeSiblingPtr;
      if (beforeSiblingPtr != nullptr) {
        beforeSiblingPtr->m_prevSiblingPtr = m_thisPtr;
      } else {
        m_parentPtr->m_lastChildPtr = m_thisPtr;
      }
      if (afterSiblingPtr != nullptr) {
        afterSiblingPtr->m_nextSiblingPtr = m_thisPtr;
      } else {
        m_parentPtr->m_firstChildPtr = m_thisPtr;
      }

      // Note the new child number
      m_childNr = newChildNr;

      // And remap the following child's numbers
      nextSiblingPtr = m_nextSiblingPtr;
      while (nextSiblingPtr != nullptr) {
        ++nextSiblingPtr->m_childNr;
        nextSiblingPtr = nextSiblingPtr->m_nextSiblingPtr;
      }
    }
  }
}

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

// Gets the number of descendants
template <typename TItemType>
long TTreeNode<TItemType>::GetNumDescendants() const {
  long numDescendants = GetNumChildren();
  TItemType* nextChildPtr = m_firstChildPtr;
  while (nextChildPtr != nullptr) {
    numDescendants += nextChildPtr->GetNumDescendants();
    nextChildPtr = nextChildPtr->m_nextSiblingPtr;
  }
  return numDescendants;
}

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

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

// Gets the given child
template <typename TItemType>
TItemType* TTreeNode<TItemType>::GetChild(TChildNr childNr) const {
  TItemType* childPtr = m_firstChildPtr;
  while (childNr > 0 && childPtr != nullptr) {
    childPtr = childPtr->m_nextSiblingPtr;
    --childNr;
  }
  return childPtr;
}

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

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

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

// Kills all children of this node
template <typename TItemType>
void TTreeNode<TItemType>::ClearChildren() {
  // Loop over all children
  TItemType* nextChildPtr = m_firstChildPtr;
  while (nextChildPtr != nullptr) {
    // Note the child to delete
    TItemType* deleteChildPtr = nextChildPtr;

    // Go to the next child
    nextChildPtr = nextChildPtr->m_nextSiblingPtr;

    // And delete the child
    delete deleteChildPtr;
  }

  // And no children left
  m_firstChildPtr = nullptr;
  m_lastChildPtr = 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 TTreeNode<TItemType>::AddChild(TItemType* newChildPtr, long childNr) {
  // Make sure it's unlinked from any other parent
  newChildPtr->MakeOrphan();

  // Get the new child number
  TChildNr maxChildNr = m_lastChildPtr == nullptr?
    0:
    (m_lastChildPtr->m_childNr + 1);
  if (childNr < 0 || childNr > maxChildNr) {
    childNr = maxChildNr;
  }

  // Get the child to insert before and after
  TItemType* beforeChildPtr = m_firstChildPtr;
  TItemType* afterChildPtr = nullptr;
  TChildNr foundChildNr = childNr;
  while (foundChildNr > 0 && beforeChildPtr != nullptr) {
    afterChildPtr = beforeChildPtr;
    beforeChildPtr = beforeChildPtr->m_nextSiblingPtr;
    --foundChildNr;
  }

  // Link the child between the other siblings
  newChildPtr->m_parentPtr = m_thisPtr;
  newChildPtr->m_prevSiblingPtr = afterChildPtr;
  newChildPtr->m_nextSiblingPtr = beforeChildPtr;
  if (beforeChildPtr != nullptr) {
    beforeChildPtr->m_prevSiblingPtr = newChildPtr;
  } else {
    m_lastChildPtr = newChildPtr;
  }
  if (afterChildPtr != nullptr) {
    afterChildPtr->m_nextSiblingPtr = newChildPtr;
  } else {
    m_firstChildPtr = newChildPtr;
  }

  // Note the child's number
  newChildPtr->m_childNr = childNr;

  // Remap the following child's numbers
  TItemType* nextChildPtr = newChildPtr->m_nextSiblingPtr;
  while (nextChildPtr != nullptr) {
    ++nextChildPtr->m_childNr;
    nextChildPtr = nextChildPtr->m_nextSiblingPtr;
  }

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

// Removes us from our parent's list of children
template <typename TItemType>
void TTreeNode<TItemType>::MakeOrphan() {
  // Look if we're an orphan already
  if (m_parentPtr != nullptr) {
    // No -> remove us from in between our siblings
    if (m_prevSiblingPtr != nullptr) {
      m_prevSiblingPtr->m_nextSiblingPtr = m_nextSiblingPtr;
    } else {
      m_parentPtr->m_firstChildPtr = m_nextSiblingPtr;
    }
    if (m_nextSiblingPtr != nullptr) {
      m_nextSiblingPtr->m_prevSiblingPtr = m_prevSiblingPtr;
    } else {
      m_parentPtr->m_lastChildPtr = m_prevSiblingPtr;
    }

    // Re-number all child numbers for the following siblings
    TItemType* nextSiblingPtr = m_nextSiblingPtr;
    while (nextSiblingPtr != nullptr) {
      --nextSiblingPtr->m_childNr;
      nextSiblingPtr = nextSiblingPtr->m_nextSiblingPtr;
    }

    // We're an orphan now
    m_parentPtr = nullptr;
    m_childNr = 0;

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

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

  // And change the depth of our children accordingly
  TItemType* nextChildPtr = m_firstChildPtr;
  while (nextChildPtr != nullptr) {
    nextChildPtr->SetDepth(newDepth + 1);
    nextChildPtr = nextChildPtr->m_nextSiblingPtr;
  }
}

#endif // INCLUDE_TWOLOGS_COMMON_TREENODE_H