IT services and product development
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
Other pages:
| ||