 |
ALib C++ Library
|
|
|
ALib C++ Library
|
|
#include <stringtree.hpp>
This container type implements a directed, non-circular graph (tree) with named nodes.
The internal node type detail::StringTreeBase::Node stores:
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.
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::NodePtr. This is a lightweight "handle" containing a pointer to the originating tree object and to a represented node.
Besides this, class StringTree::RecursiveIterator allows recursive iterations with built-in or custom sort orders.
Both types are explained in the following paragraphs.
The main interface into class StringTree is given by public, inner type StringTree::NodePtr. 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 NodePtr is very lightweight as it contains just two pointers, one to 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 NodePtr::Value.
The methods to traverse over the nodes of the tree are:
For some of these methods an alternative version exists, which returns a corresponding copy of the node pointer, 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
Next, four methods that perform node deletion exist:
The already mentioned methods:
of class NodePtr 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 node pointer objects can be (or rather have to be!) detected using method NodePtr::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 NodePtr objects can reset to a valid state using methods
Instances that have been default-constructed may only be set to a valid state by (copy-) assigning a valid instance.
Class StringTree::RecursiveIterator provides a configurable and controlled way of iterating a branch of a tree. Some features of the class are:
0, which iterates only the direct child nodes of the start node.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.
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.
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 NodePtr that create children are made. This is useful (and very efficient!) if all child name and creation path strings provided of class NodePtr 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.
| 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 511 of file stringtree.hpp.
Public Types | |
| using | CharacterType = typename TNodeMaintainer::CharacterType |
| using | NameType = typename strings::TString< CharacterType > |
| using | SubstringType = typename strings::TSubstring< CharacterType > |
| using | TSharedRecycler = typename basetree::TSharedRecycler |
Inner Classes | |
| class | NodePtr |
| class | RecursiveIterator |
Public Methods | |
| template<typename... TArgs> | |
| StringTree (MonoAllocator *allocator, CharacterType pathSeparator, TArgs &&... args) | |
| template<typename... TArgs> | |
| StringTree (MonoAllocator *allocator, TSharedRecycler &pRecycler, CharacterType pathSeparator, TArgs &&... args) | |
| ~StringTree () | |
| void | Clear () |
| bool | IsEmpty () const |
| integer | RecyclablesCount () const |
| void | ReserveRecyclables (integer expected, lib::ValueReference reference) |
| template<typename... TArgs> | |
| void | Reset (TArgs &&... args) |
| NodePtr | Root () |
| void | SetAllocatorPostConstruction (MonoAllocator *pAllocator) |
| integer | Size () const |
Additional Inherited Members | |
 Protected Types inherited from StringTreeBase< T, TNodeMaintainer, TRecycling > | |
| using | CharacterType = typename TNodeMaintainer::CharacterType |
| using | NameType = typename TNodeMaintainer::NameStringType |
| using | NodeList = lib::detail::BidiListHelper< Node > |
| using | SubstringType = typename strings::TSubstring< CharacterType > |
| using | TSharedRecycler = typename decltype(nodeTable)::TSharedRecycler |
| using | ValueType = typename strings::TString< typename TNodeMaintainer::CharacterType > |
| Protected Fields inherited from StringTreeBase< T, TNodeMaintainer, TRecycling > | |
| monomem::HashTable< Node, Node, NodeKey, void, typename NodeKey::Hash, typename NodeKey::EqualTo, typename NodeKey::Access, Caching::Enabled, TRecycling > | nodeTable |
| Node | root |
| CharacterType | separator |
| Protected Methods inherited from StringTreeBase< T, TNodeMaintainer, TRecycling > | |
| template<typename... TArgs> | |
| StringTreeBase (MonoAllocator *allocator, CharacterType pathSeparator, TArgs &&... args) | |
| template<typename... TArgs> | |
| StringTreeBase (MonoAllocator *allocator, TSharedRecycler &pRecycler, CharacterType pathSeparator, TArgs &&... args) | |
| bool | checkChildName (const NameType &name) |
| 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 528 of file stringtree.hpp.
| 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 532 of file stringtree.hpp.
| 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 536 of file stringtree.hpp.
| using TSharedRecycler = typename basetree::TSharedRecycler |
This type definition may be used to define an externally managed shared recycler, which can be passed to the alterative constructor of this class when template parameter TRecycling equals Recycling::Shared.
Definition at line 544 of file stringtree.hpp.
|
inline |
Constructor.
| TArgs | Types of variadic parameters given with parameter args. |
| allocator | The monotonic allocator to use. |
| pathSeparator | The separation character used with path strings. |
| args | Variadic parameters to be forwarded to constructor of custom type T of this tree's root node. |
Definition at line 2153 of file stringtree.hpp.
|
inline |
Constructor taking a shared recycler.
| TArgs | Types of variadic parameters given with parameter args. |
| allocator | The monotonic allocator to use. |
| pRecycler | The shared recycler. |
| pathSeparator | The separation character used with path strings. |
| args | Variadic parameters to be forwarded to constructor of custom type T of this tree's root node. |
Definition at line 2168 of file stringtree.hpp.
|
inline |
|
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 2206 of file stringtree.hpp.
|
inline |
Tests for emptyness.
true if this tree is empty, false otherwise. Definition at line 2284 of file stringtree.hpp.
|
inline |
Counts the number of currently allocated but unused (not contained) element nodes that will be recycled with upcoming insertions.
Definition at line 2261 of file stringtree.hpp.
|
inline |
Allocates the required space for the number of elements expected.
| 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 2301 of file stringtree.hpp.
|
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.
The custom data of the root node is deleted and default constructed using the given arguments.
| TArgs | Types of variadic parameters given with parameter args. |
| args | Variadic parameters to be forwarded to constructor of custom type T of this tree's root node. |
Definition at line 2235 of file stringtree.hpp.
|
inline |
Creates a node pointer instance representing the root node.
Definition at line 2310 of file stringtree.hpp.
|
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.
| pAllocator | The allocator that was omitted in the constructor. |
Definition at line 2190 of file stringtree.hpp.
|
inline |
Returns the overall number of elements contained in this tree.
Definition at line 2274 of file stringtree.hpp.