StringTree< T > Class Template Reference

Collaboration diagram for StringTree< T >:

Class Description

---

This class manages an object of internal type Node, which consists of

• A value of custom (template) type T,
• A pointer to a parent Node and
• A hash table which recursively stores pointers to Node objects, referred to by a string-type key.

This recursive data structure is what comprises a graph with named edges. As this object does not allow insertion of nodes with circular dependencies, the graph is of tree type. The way from the root node to the leafs usually is called "path" and the class incorporates functionality to work with string representations of such paths where names of edges are concatenated and separated by a special separation character. Now, this explains why this class is called StringTree.

The search and creation of tree nodes by using aforementioned path strings, is very similar to what is well known from addressing files and folders in file systems. The difference is however, that this class does not differentiate between 'folders' and 'files', hence between 'nodes' and 'leafs'. Every node has the same value type T and may or may not have child nodes. If such differentiation - or other semantics - is wanted, this may be modeled in custom attributes provided in template type T.

The internal node structure is not exposed publically and the class has no direct interface to manipulate nodes. Instead, the interface is defined by two public inner types. Those are:

• Cursor and
• Walker.

and are explained in the following paragraphs.

Note

The C++ version of this class provides a third type StdIterator

Inner class Cursor: Inserting, Retrieving And Deleting Nodes
The class has no direct interface to manipulate nodes. The main interface into objects of this type is defined by public, inner type Cursor. The only way to create an initial cursor is with method Root, which creates a cursor object referring to the root node of the tree. With this, string names and complete paths can be used to move the cursor along existing nodes of the tree or to create new child nodes or a whole path of children at once. Class cursor is quite lightweight as it contains just two pointers (to the StringTree and the current node). Hence, cursors can be cloned, assigned and passed around very efficiently.

Once a cursor is created it can traverse over the tree nodes using methods

• Cursor.MoveToChild,
• Cursor.MoveToParent,
• Cursor.MoveTo and
• Cursor.MoveToExistingPart.

For the creation of new child nodes or a complete path of such, methods

• Cursor.MoveToChildCreate and
• Cursor.MoveToAndCreateNonExistingPart

are provided. Then, two methods for erasing nodes exist:

• Cursor.DeleteChild and
• Cursor.DeleteChildren

Finally, class cursor can also be used like an iterator. But it explicitly and for good reason does not follow the iteration concepts provided with C#. The iteration feature comes with methods

• Cursor.MoveToParentUnchecked and
• Cursor.IsValid.

The first transitions the cursor to refer to the parent node. Using this method is (almost) the only way how a cursor can get invalidated. Hence a simple loop can be written that visits all nodes from a starting node, up to the root of the tree until Cursor.IsValid evaluates to false.

Inner class Walker: Sorted Iterations
Finally, with Walker, a third StdIterator class is exposed. The rational for having this class is to provide a configurable and controlled way of iterating a tree or a branch. Some features of the class are:

• Can be created from (or reset to) the StringTree itself, Cursor objects
• Can work recursively (with depth limitation) or just on the current nodes' direct children.
• Has several sort options:
  • built-in by path name, ascending/descending, case sensitive or ignoring
  • user defined by path name
  • user defined by template type

The class is rather 'heavy' and recursive iteration needs to allocate memory for a sorted vector of child nodes. Therefore it is recommended to reuse instances of the class with subsequent, similar iterations.

Recursive Iteration

Class Walker supports recursive iteration. Recursiveness is controlled with method Walker.SetRecursionDepth. When the recursive iteration depth is limited, then the very first node (the root node of the iteration) is skipped. With unlimited recursion, the root node is included (as the first result). In the case, that the root node should not be included in an unlimited, recursive iteration, it has to be skipped 'manually'.

Iterators And Changes Of The Underlying Container
Objects of types Cursor and Walker may become invalid when the underlying StringTree object changes and have to be re-initialized after such change. I.e, there is no guarantee given that changes in the tree are not invalidating instances that represent 'higher' nodes or or 'sibling' branches of those which have undergone changes. Such invalid state can not be detected. As a result, the objects have to be reset or disposed on changes of the tree.

Template Parameters

T	The value type of elements stored in the nodes of the tree.

Inner Classes
class	Cursor
class	Node
class	Walker

Public Methods
	StringTree (char _separator='/')
void	Clear ()
Cursor	Root ()

Protected Fields
Node	root
char	separator

Constructor & Destructor Documentation

StringTree()

StringTree ( char  _separator = '/' )

inline

---

Constructor

Parameters

_separator

The separator character used by this string tree and inner classes. Defaults to '/'.

Member Function Documentation

Clear()

void Clear ( )

inline

---

Clears all nodes and values.

Root()

Cursor Root ( )

inline

---

Creates a cursor instance representing the root node.

Returns

A cursor pointing to the root node of this StringTree.

Member Data Documentation

root

Node root

protected

The root node.

separator

char separator

protected

The separator character using with path arguments of interface methods.

---

The documentation for this class was generated from the following file:

• StringTree.cs