ALox  V. 2402 R. 0
Home ALox for C++ ALox for C# ALox for Java Download
Inner Classes | Public Methods | Protected Fields | List of all members
StringTree< T > Class Template Reference
Collaboration diagram for StringTree< T >:
[legend]

Class Description


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

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:

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

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

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

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

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:

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
TThe 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
_separatorThe 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: