Description:

template<typename T, typename TNodeMaintainer = StringTreeNamesDynamic<character>, typename TRecycling = Recycling::Private>
class alib::monomem::StringTree< T, TNodeMaintainer, TRecycling >

1. Introduction

This container type implements a directed, non-circular graph (tree) with named nodes.

The internal node type detail::StringTreeBase::Node stores:

A name string, which has to be unique in respect to the names of sibling nodes. (Just like no two files in a folder may have the same name.)
Five pointers to related nodes:
- the parent node
- the previous and next sibling nodes,
- the first and last child nodes,
A data field holding the node's custom value of template type T .

The way from the root node to a descendent node, usually is called "path". The class incorporates functionality to work with string representations of such paths where names of child nodes are concatenated and separated by a special separation character.

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. This class does not differentiate between 'folders' and 'files', hence between 'nodes' and 'leafs'. Every node has the same data of type T attached and may or may not have child nodes. If such differentiation - or other semantics - is wanted, this may well be modeled by custom attributes provided in template type T .

2. Inner Types

Two public inner types exist. All operations on tree nodes like insertion, deletion, search and attribute access is performed using objects of public type StringTree::TCursor . This is a lightweight, iterator-like "handle" containing a pointer to the originating tree object and to a represented node. The type provides various methods to travers the tree. It is templated over a boolean value which determines if a const or mutable StringTree is given. Shortcuts for these types are StringTree::Cursor and StringTree::ConstCursor .

Besides this, class StringTree::RecursiveIterator allows recursive iterations with built-in or custom sort orders.

Both types are explained in the following paragraphs.

2.1 Inner Class Cursor

The main interface into class StringTree is given by public, inner type StringTree::Cursor . Method Root returns an object of that type that initially refers to the root node of the tree. With this, child names and composite "paths" can be used to move the pointer along existing nodes of the tree or to create new child nodes or even a whole path of such child nodes at once.

Class Cursor is very lightweight as it contains just two pointers, one to the StringTree it originates from and one to the tree node currently represented. Hence, objects of this type can be copied, assigned and passed around very efficiently.
The currently represented node's templated custom data can be accessed with method TCursor::Value.

The methods to traverse over the nodes of the tree are:

With these methods, class StringTree::Cursor constitutes a sort of iterator idiom idiom. For example to traverse all entries in the root folder, the following schematic would be used:

     myCursor=  myTree.GetRoot()
     myCursor.GotoFirstChild()
     While( myCursor.IsValid() )
         DoSomething( myCursor.Value() )
         myCursor.GotoNextSibling

For some of these methods an alternative version exists, which returns a corresponding copy of the cursor, while leaving the original object unchanged. These methods share the same name excluding the prefix GoTo.

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

TCursor::GoToCreateChildIfNotExistent and ,
TCursor::GoToCreatedPathIfNotExistent are provided.

Next, four methods that perform node deletion exist:

TCursor::DeleteChild (two overloaded versions),
TCursor::DeleteChildren and
TCursor::Delete

The already mentioned methods:

of class Cursor can be used to iterate from a node upward to the root node or through the list of children of a node. Each method may invalidate the object in the case that no corresponding parent or sibling node exists. Invalid cursor objects can be (or rather have to be!) detected using method TCursor::IsValid. Most of the class's methods must not be invoked on an invalidated object. Doing so is undefined behavior and raises an ALib assertion in debug-builds. Invalid Cursor objects can reset to a valid state using methods

if absolute path addressing is used.

Instances that have been default-constructed may only be set to a valid state by (copy-) assigning a valid instance.

2.2. Inner Class RecursiveIterator

Class StringTree::RecursiveIterator provides a configurable and controlled way of iterating a branch of a tree. Some features of the class are:

Iterators can be initialized to start from any node of the tree Iteration ends when all (recursive) child nodes of the start node have been visited.
The iteration follows a "depth first search" approach: Prior to visiting a sibling node, all children of a node are visited.
The recursion depth can be limited, including to depth 0, which iterates only the direct child nodes of the start node.
Prior to entering a new depth-level during iteration, different sort orders can be set. The choices are:
- No sorting (iterates in order of node insertion).
- Built-in sorting by node (path) name, ascending/descending, case sensitive or ignoring case
- user defined by path name, number of children or any other attribute of the node, of-course including a node's custom data values.

Class RecursiveIterator is of rather heavy weight and sorted iteration needs to allocate memory for sorting the child nodes for each depth level of a potential recursion. Therefore it is recommended to reuse instances of the class with subsequent, similar iterations. In addition this explains why this class does not follow the concept of std::iterator_traits, which is designed to be used with lightweight iterator types.

3. Node Allocation And Hashing

While each node maintains a doubly linked list of child nodes for iteration, this class stores each inserted element in a HashTable using the parent node and the element's name as a unique key. This is done to be able to search for a child with a given name in constant time. This container does not perform any other memory allocations than those that this HashTable does.

With that, the implementation of this container type is able to leave all allocation and "recycling" of node elements to this hash table, which is found in base class's field detail::StringTreeBase::nodeTable . As explained in the documentation of HashTable , its allocation mechanism can be made safe in respect to memory exhaustion of the underlying MonoAllocator , even if a virtually unlimited number of insertions and removals of elements is performed. Such safeness depends on template parameter TRecycling which is just passed to the definition of the internal hash table of nodes.

See also: For more information on this topic see also chapter 1.5 Recycling of this ALib Module Programmer's Manual.

4. Node and Node Name String Allocation

The C++ version of this class allows user-defined allocation (and copying) of the node's name character strings. For this, template parameter TNodeMaintainer is defined, which defaults to built-tin struct StringTreeNamesDynamic . This default "node maintainer" defines the name type of nodes to LocalString with a default capacity of 32 characters. This way, dynamic allocation is performed automatically by this local string when a node is constructed.
In the case that many "long" node names are expected, it might be efficient to set the capacity to 0. In this case, type StringTreeNamesDynamic defines the string type to a normal String and uses C++ keywords new and delete[] to allocate and free character buffers for the name string.

A second built-in and ready to use "node maintainer" type is given with StringTreeNamesStatic . This uses an unbuffered String and has empty implementations of its static methods. This way no copies of the original string buffers that are passed to the to interface methods of class Cursor that create children are made. This is useful (and very efficient!) if all child name and creation path strings provided of class Cursor are permanently valid (in other words, their life-cycle spans over the life-cycle of the nodes in a tree) and therefore do not need to be copied to dedicated allocated memory. If this precondition is not assured, the StringTree produces undefined behavior.

Finally, string trees that during their lifetime just grow and where no nodes (or only a limited number of nodes) are removed until the whole tree is disposed, may be instantiated using the third built-in type StringTreeNamesMonoAlloc . With that, the concept of monotonic allocation that this container type uses can be extended to the node name strings. Type StringTreeNamesMonoAlloc grabs the allocator from the tree provided with method InitializeNode and just clones the given string into this.

5. Equipping the Root Node with Values

It depends on the field of application, whether the root node should dispose over an instance of custom type T or not. For example a tree of depth 1, which could be implemented using type std::vector<T>, no value type can be be attached to the vector object itself, only to its "children".
Nevertheless, in many use cases, the root node naturally contains the same data as any other node in the tree. Therefore, if this class would not support root node data, using code would for example have to check a Cursor for pointing to the root node and in this case get the custom data from somewhere else.
On the other hand, if this class would "insist" in the provision of root node values, then already with construction of the tree, arguments for the construction of the associated T object would have to be provided - even if the root node value was never used. The provision of initial "dummy" root data, is sometimes not even (easily) possible, and would sometimes add the need to adjust the custom value type T to fit into this class. (In fact, with former versions of ALib , root-node initialization data was mandatory to provide already with the construction of the tree.)

Therefore, this class makes the use of root node values optional. After construction of a StringTree, methods ConstructRootValue and methods DeleteRootValue may be used to initialize and delete the optional root nodes' data.

To prevent memory leaks, in debug-compilations, the following ALib assertions and warnings are raised:

alib::monomem;StringTree;TCursor::Value;Cursor::Value "monomem;StringTree;TCursor::Value;Cursor::Value" will raise an assertion if called on the root node without having set a value.
ConstructRootValue will raise a warning if called twice without a prior call to DeleteRootValue .
DeleteRootValue will raise a warning if called without a prior call to ConstructRootValue .
The destructor of this class will raise a warning if a root value was set but not deleted.

Reference Documentation

Template Parameters

T	The custom value type of elements stored in this container.
TNodeMaintainer	A template type that needs to provide an interface as documented with StringTreeNamesDynamic , which is also the default type if not specified. For details see corresponding section of this class's documentation.
TRecycling	Denotes the type of recycling that is to be performed. Possible values are Recycling::Private (the default), Recycling::Shared or Recycling::None .

Definition at line 617 of file stringtree.hpp.

#include <stringtree.hpp>

Inheritance diagram for StringTree< T, TNodeMaintainer, TRecycling >:

[legend]

Collaboration diagram for StringTree< T, TNodeMaintainer, TRecycling >:

[legend]

Inner Type Index:
class	TCursor

class	TRecursiveIterator

Public Type Index:
using	CharacterType = typename TNodeMaintainer::CharacterType

using	ConstCursor = TCursor<true>

using	ConstRecursiveIterator = TRecursiveIterator<true>

using	Cursor = TCursor<false>

using	NameType = typename strings::TString<CharacterType>

using	RecursiveIterator = TRecursiveIterator<false>

using	SubstringType = typename strings::TSubstring<CharacterType>

using	TSharedRecycler = typename basetree::TSharedRecycler

Public Method Index:
	StringTree (MonoAllocator *allocator, CharacterType pathSeparator)

	StringTree (MonoAllocator *allocator, CharacterType pathSeparator, TSharedRecycler &pRecycler)

	~StringTree ()

void	Clear ()

template<typename... TArgs>
void	ConstructRootValue (TArgs &&... args)

void	DeleteRootValue ()

MonoAllocator *	GetAllocator ()

bool	IsEmpty () const

auto &	NodeTable ()

const auto &	NodeTable () const

integer	RecyclablesCount () const

void	ReserveRecyclables (integer expected, lang::ValueReference reference)

void	Reset ()

Cursor	Root ()

const ConstCursor	Root () const

void	SetAllocatorPostConstruction (MonoAllocator *pAllocator)

integer	Size () const

Type Definition Details:

◆ CharacterType

template<typename T , typename TNodeMaintainer = StringTreeNamesDynamic<character>, typename TRecycling = Recycling::Private>

using CharacterType = typename TNodeMaintainer::CharacterType

The character type of node names and paths strings. This is defined using character type definition CharacterType of template type TNodeMaintainer .

Definition at line 640 of file stringtree.hpp.

◆ ConstCursor

template<typename T , typename TNodeMaintainer = StringTreeNamesDynamic<character>, typename TRecycling = Recycling::Private>

using ConstCursor = TCursor<true>

The constant version of type StringTree::TCursor .

Definition at line 1608 of file stringtree.hpp.

◆ ConstRecursiveIterator

template<typename T , typename TNodeMaintainer = StringTreeNamesDynamic<character>, typename TRecycling = Recycling::Private>

using ConstRecursiveIterator = TRecursiveIterator<true>

The constant version of type StringTree::TRecursiveIterator .

Definition at line 2368 of file stringtree.hpp.

◆ Cursor

template<typename T , typename TNodeMaintainer = StringTreeNamesDynamic<character>, typename TRecycling = Recycling::Private>

using Cursor = TCursor<false>

The mutable version of type StringTree::TCursor .

Definition at line 1605 of file stringtree.hpp.

◆ NameType

template<typename T , typename TNodeMaintainer = StringTreeNamesDynamic<character>, typename TRecycling = Recycling::Private>

using NameType = typename strings::TString<CharacterType>

The string type of node names and paths. This is defined using character type definition CharacterType of template type TNodeMaintainer .

Definition at line 645 of file stringtree.hpp.

◆ RecursiveIterator

template<typename T , typename TNodeMaintainer = StringTreeNamesDynamic<character>, typename TRecycling = Recycling::Private>

using RecursiveIterator = TRecursiveIterator<false>

The mutable version of type StringTree::TRecursiveIterator .

Definition at line 2365 of file stringtree.hpp.

◆ SubstringType

template<typename T , typename TNodeMaintainer = StringTreeNamesDynamic<character>, typename TRecycling = Recycling::Private>

using SubstringType = typename strings::TSubstring<CharacterType>

The sub-string type of paths. This is defined using character type definition CharacterType of template type TNodeMaintainer .

Definition at line 650 of file stringtree.hpp.

◆ TSharedRecycler

template<typename T , typename TNodeMaintainer = StringTreeNamesDynamic<character>, typename TRecycling = Recycling::Private>

using TSharedRecycler = typename basetree::TSharedRecycler

This type definition may be used to define an externally managed shared recycler, which can be passed to the alternative constructor of this class when template parameter TRecycling equals Recycling::Shared .

See also: Chapter 3.3 Shared Recycling of the Programmer's Manual for this ALib Module .

Definition at line 658 of file stringtree.hpp.

Constructor(s) / Destructor Details::

◆ StringTree() [1/2]

template<typename T , typename TNodeMaintainer = StringTreeNamesDynamic<character>, typename TRecycling = Recycling::Private>

StringTree	(	MonoAllocator *	allocator,
		CharacterType	pathSeparator )

inline

Constructor.

Parameters

allocator	The monotonic allocator to use.
pathSeparator	The separation character used with path strings.

Definition at line 2380 of file stringtree.hpp.

◆ StringTree() [2/2]

template<typename T , typename TNodeMaintainer = StringTreeNamesDynamic<character>, typename TRecycling = Recycling::Private>

StringTree	(	MonoAllocator *	allocator,
		CharacterType	pathSeparator,
		TSharedRecycler &	pRecycler )

inline

Constructor taking a shared recycler.

Parameters

allocator	The monotonic allocator to use.
pRecycler	The shared recycler.
pathSeparator	The separation character used with path strings.

Definition at line 2390 of file stringtree.hpp.

◆ ~StringTree()

template<typename T , typename TNodeMaintainer = StringTreeNamesDynamic<character>, typename TRecycling = Recycling::Private>

~StringTree ( )

inline

Destructor. Raises a warning if a root value was but not deleted accordingly.

Definition at line 2399 of file stringtree.hpp.

Method Details:

◆ Clear()

template<typename T , typename TNodeMaintainer = StringTreeNamesDynamic<character>, typename TRecycling = Recycling::Private>

void Clear ( )

inline

Removes all elements from this container. The use of this method is more efficient than deleting the children of the root node.

Invokes HashTable::Clear on field nodeTable . As documented with that method, the allocated nodes will be preserved for "recycling" with future insertions.

The custom data of the root node is preserved.

Definition at line 2486 of file stringtree.hpp.

◆ ConstructRootValue()

template<typename T , typename TNodeMaintainer = StringTreeNamesDynamic<character>, typename TRecycling = Recycling::Private>

template<typename... TArgs>

void ConstructRootValue ( TArgs &&... args )

inline

Depending on the use case, it might be appropriate to attach a value of template type T to the root node of the tree. If so, this can be done with this method. If not done, in debug compilations, method TCursor::Value will raise an ALib assertion if called on the root node.

Custom data that is explicitly attached to the root node with this method has to be deleted explicitly by calling DeleteRootValue prior to deletion of the tree.

Template Parameters

TArgs Types of variadic parameters given with parameter args .

Parameters

args	Variadic parameters to be forwarded to constructor of custom type T of the child created.

Definition at line 2449 of file stringtree.hpp.

◆ DeleteRootValue()

template<typename T , typename TNodeMaintainer = StringTreeNamesDynamic<character>, typename TRecycling = Recycling::Private>

void DeleteRootValue ( )

inline

Deletes the custom data object of type T , which may explicitly set using ConstructRootValue.
If not done, in debug-compilations, an ALib warning is raised in the destructor of this tree.

Definition at line 2466 of file stringtree.hpp.

◆ GetAllocator()

template<typename T , typename TNodeMaintainer = StringTreeNamesDynamic<character>, typename TRecycling = Recycling::Private>

MonoAllocator * GetAllocator ( )

inline

Shortcut to NodeTable().GetAllocator .

Returns: The allocator that was provided in the constructor and stored in the internal NodeTable.

Definition at line 2428 of file stringtree.hpp.

◆ IsEmpty()

template<typename T , typename TNodeMaintainer = StringTreeNamesDynamic<character>, typename TRecycling = Recycling::Private>

bool IsEmpty ( ) const

inline

Tests for emptiness.

Returns: true if this tree is empty, false otherwise.

Definition at line 2557 of file stringtree.hpp.

◆ NodeTable() [1/2]

template<typename T , typename TNodeMaintainer = StringTreeNamesDynamic<character>, typename TRecycling = Recycling::Private>

auto & NodeTable ( )

inline

Returns the internal HashTable used for storing the tree nodes. This may be used to manipulate load factors, for direct iteration over all nodes, etc.

Note: The returned object should be used with caution to keep the tree and its data consistent.

Returns: The internal node table.

Definition at line 2586 of file stringtree.hpp.

◆ NodeTable() [2/2]

template<typename T , typename TNodeMaintainer = StringTreeNamesDynamic<character>, typename TRecycling = Recycling::Private>

const auto & NodeTable ( ) const

inline

Returns the internal HashTable used for storing the tree nodes. This may be used to manipulate load factors, for direct iteration over all nodes, etc.

Note: The returned object should be used with caution to keep the tree and its data consistent.

Returns: The internal node table.

Definition at line 2598 of file stringtree.hpp.

◆ RecyclablesCount()

template<typename T , typename TNodeMaintainer = StringTreeNamesDynamic<character>, typename TRecycling = Recycling::Private>

integer RecyclablesCount ( ) const

inline

Counts the number of currently allocated but unused (not contained) element nodes that will be recycled with upcoming insertions.

Note: This method is provided for completeness and unit-testing. It should not be of relevance for common usage. Furthermore, this method is not available (aka does not compile) with instantiations that specify template parameter TRecycling as Recycling::None .

Returns: The number of removed and not yet recycled elements.

Definition at line 2534 of file stringtree.hpp.

◆ ReserveRecyclables()

template<typename T , typename TNodeMaintainer = StringTreeNamesDynamic<character>, typename TRecycling = Recycling::Private>

void ReserveRecyclables	(	integer	expected,
		lang::ValueReference	reference )

inline

Allocates the required space for the number of elements expected.

Note: If the definite number of stored elements that is never exceeded is known, a snapshot of the monotonic allocator could be taken after the invocation of this method and then used to reset the monotonic allocator with preserving the memory used by this container.

Parameters

expected	The expected number or increase of elements to be stored in the hash table.
reference	Denotes whether expected is meant as an absolute size or an increase .

Definition at line 2574 of file stringtree.hpp.

◆ Reset()

template<typename T , typename TNodeMaintainer = StringTreeNamesDynamic<character>, typename TRecycling = Recycling::Private>

void Reset ( )

inline

Clears all nodes and values. The use of this method is more efficient than deleting the children of the root node.
In addition, depending on template type TNodeMaintainer , it may also declare allocated memory for future reuse.
The latter is true for type StringTreeNamesMonoAlloc .

In case of private recycling disposes all previously allocated recyclable instances of internal element type.

Note: The value of the root-node, set with ConstructRootValue is not deleted.

Definition at line 2510 of file stringtree.hpp.

◆ Root() [1/2]

template<typename T , typename TNodeMaintainer = StringTreeNamesDynamic<character>, typename TRecycling = Recycling::Private>

Cursor Root ( )

inline

Creates a cursor instance representing the root node.

Returns: A cursor pointing to the root node of this StringTree.

Definition at line 2607 of file stringtree.hpp.

◆ Root() [2/2]

template<typename T , typename TNodeMaintainer = StringTreeNamesDynamic<character>, typename TRecycling = Recycling::Private>

const ConstCursor Root ( ) const

inline

Creates a const cursor instance representing the root node.

Returns: A read-only pointer, pointing to the root node of this StringTree.

Definition at line 2616 of file stringtree.hpp.

◆ SetAllocatorPostConstruction()

template<typename T , typename TNodeMaintainer = StringTreeNamesDynamic<character>, typename TRecycling = Recycling::Private>

void SetAllocatorPostConstruction ( MonoAllocator * pAllocator )

inline

In some situations, the allocator object to use might not be available with construction of an instance. This method may be used to attach an external allocator at a later point in time - but prior to this instance's first use.

Parameters

pAllocator The allocator that was omitted in the constructor.

Definition at line 2418 of file stringtree.hpp.

◆ Size()

template<typename T , typename TNodeMaintainer = StringTreeNamesDynamic<character>, typename TRecycling = Recycling::Private>

integer Size ( ) const

inline

Returns the overall number of elements contained in this tree.

Note: This method performs in constant time.

Returns: The number elements contained in this tree.

Definition at line 2547 of file stringtree.hpp.

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

stringtree.hpp

Description:

1. Introduction

2. Inner Types

2.1 Inner Class Cursor

2.2. Inner Class RecursiveIterator

3. Node Allocation And Hashing

4. Node and Node Name String Allocation

5. Equipping the Root Node with Values

Reference Documentation

Inner Type Index:

Public Type Index:

Public Method Index:

Type Definition Details:

◆ CharacterType

◆ ConstCursor

◆ ConstRecursiveIterator

◆ Cursor

◆ NameType

◆ RecursiveIterator

◆ SubstringType

◆ TSharedRecycler

Constructor(s) / Destructor Details::

◆ StringTree() [1/2]

◆ StringTree() [2/2]

◆ ~StringTree()

Method Details:

◆ Clear()

◆ ConstructRootValue()

◆ DeleteRootValue()

◆ GetAllocator()

◆ IsEmpty()

◆ NodeTable() [1/2]

◆ NodeTable() [2/2]

◆ RecyclablesCount()

◆ ReserveRecyclables()

◆ Reset()

◆ Root() [1/2]

◆ Root() [2/2]

◆ SetAllocatorPostConstruction()

◆ Size()