ALib C++ Framework
by
Library Version: 2511 R0
Documentation generated by doxygen
Loading...
Searching...
No Matches
stringtree.inl
Go to the documentation of this file.
1//==================================================================================================
2/// \file
3/// This header-file is part of module \alib_containers of the \aliblong.
4///
5/// \emoji :copyright: 2013-2025 A-Worx GmbH, Germany.
6/// Published under #"mainpage_license".
7//==================================================================================================
8ALIB_EXPORT namespace alib { namespace containers {
9
10#if ALIB_DEBUG
11 /// Statistic variable increased by #"StringTreeNamesDynamic" with every creation
12 /// of a node. With process creation the variable is \c 0. A user may reset the variable to
13 /// inspect percentages of name overflows during certain operations. The variable is not thread
14 /// safe and used by any instance of class \b StringTree which uses node handler
15 /// \b StringTreeNamesDynamic.
16 /// @see Sibling variable #"DBG_STATS_STRINGTREE_NAME_OVERFLOWS"
17 ALIB_DLL extern uinteger DBG_STATS_STRINGTREE_NAMES;
18
19 /// Statistic variable increased by #"StringTreeNamesDynamic" with every creation
20 /// of a node whose name exceeds the internal string buffer size.
21 /// With process creation the variable is \c 0. A user may reset the variable to
22 /// inspect percentages of name overflows during certain operations. The variable is not thread
23 /// safe and used by any instance of class \b StringTree which uses node handler
24 /// \b StringTreeNamesDynamic.
25 /// @see Sibling variable #"DBG_STATS_STRINGTREE_NAME_OVERFLOWS"
26 ALIB_DLL extern uinteger DBG_STATS_STRINGTREE_NAME_OVERFLOWS;
27#endif
28
29/// This struct is the default type for template parameter
30/// #"alib_ns_containers_stringtree_referencedoc;TNodeHandler" of class
31/// #"StringTree".
32///
33/// Besides defining the character type as given with template parameter \p{TChar}, the node name
34/// string-type is exposed with #".NameStringType". The string-type depends on the template parameter
35/// \p{TLocalCapacity}:
36/// - If this is \c 0, the type evaluates to a simple string with no internal storage.
37/// - If this is greater than zero, the type evaluates to a #"TLocalString;LocalString"
38/// of given capacity.
39///
40/// This design allows allocating a fixed-size string buffer with each node, and only if a
41/// node's name exceeds this capacity, a dynamic allocation for storing the node name is performed.
42/// As a consequence, some overhead of wasted memory will occur, as this capacity is
43/// allocated with every node, regardless of its name's length.
44/// To investigate into the percentage of overflows to evaluate a reasonable value for template
45/// parameter \p{TLocalCapacity}, simple global debug counters
46/// #"DBG_STATS_STRINGTREE_NAMES" and #"DBG_STATS_STRINGTREE_NAME_OVERFLOWS"
47/// can be used.
48///
49/// Method #".InitializeNode" is invoked after the insertion of a new element (aka "node")
50/// into the container and #".FreeNode" is invoked before the destruction of a node.
51/// When #".InitializeNode" is invoked, the custom object of template type \p{T} (of the \b StringTree)
52/// is already default constructed and the key of the node in union
53/// (field #"detail::StringTreeBase::NodeKey::name;*") is set to what was provided
54/// as a child name or path string. (In the latter case, it is set to a substring of the
55/// given path.). If template parameter \p{TLocalCapacity} is greater than 0, the
56/// method copies the key to field \e storage of the union (which is still accessible with the
57/// base string-type of union-field \e key).
58/// If \c 0 is given, the node name is replaced by a copy of the string which is dynamically
59/// allocated.
60///
61/// ## Custom Implementations ##
62/// A custom implementation has to provide all four entities that this type provides in a
63/// compatible fashion.
64///
65/// The main purpose of the node handler types is to ensure that the name strings of inserted
66/// nodes are duly allocated, copied, and freed as needed:
67/// When a new element is (or a whole path of new elements are) created, then the initial name
68/// of the nodes are taken from the string passed to the corresponding interface method of class
69/// \b StringTree (and inner types). The challenge is that this string's life-cycle might
70/// be only short term. Therefore, right after the creation of an element, the method
71/// #".InitializeNode" is invoked, allowing to create a safe copy of the name.<br>
72/// To free any allocated space, the method #".FreeNode" is invoked.
73///
74/// Besides this, custom implementations may tweak the given node on their own discretion.
75/// Especially a custom implementation may create and recycle other portions of the stored
76/// objects to establish #"alib_contmono_intro_strictweak;weak monotonic allocation rules".
77/// A sample of such more complex behavior is found with \alib type #"FTree".
78///
79/// \see
80/// Two other built-in implementations of this type to be used with \b StringTree instantiations
81/// are provided with this \alibmod:
82/// - #"StringTreeNamesStatic".
83/// - #"StringTreeNamesAlloc".
84/// \see
85/// Further information can be found in chapter #"alib_ns_containers_stringtree_alloc_names"
86/// of the reference documentation of class \b StringTree.
87///
88/// @tparam TChar The character type of the key strings. This type is used with any
89/// interface method of #"StringTree" that accepts a node name
90/// or path string.<br>
91/// Defaults to type #"characters::character".
92/// @tparam TLocalCapacity The capacity of the #"TLocalString;LocalString" to place in
93/// the <b>StringTree</b>'s node. If \c 0 is given, a normal
94/// #"TString;String" is used for the name, and the buffer is
95/// copied to an dynamically allocated array.<br>
96/// Defaults to \c 32.
97template<typename TChar= character, integer TLocalCapacity= 32>
98struct StringTreeNamesDynamic
99{
100 /// The character type that the \b StringTree uses for child name and path strings.
101 using CharacterType = TChar;
102
103 /// The string-type of a node's name.
104 using NameStringType = std::conditional_t<( TLocalCapacity > 0),
105 strings::TLocalString<TChar, TLocalCapacity>,
106 strings::TString <TChar> >;
107
108
109 /// This implementation copies the node's name to a dynamically allocated piece of heap memory.
110 /// \see
111 /// See the class description for further information.
112 /// @param node The node that was just created. Allows access to the key and
113 /// custom value data. While the parent and sibling nodes are likewise accessible,
114 /// it is strictly forbidden to modify those.
115 /// @param tree The instance of struct #"detail::StringTreeBase;*" that invokes
116 /// this method. Any member may be accessed, including
117 /// #"StringTreeBase;nodeTable" which contains the
118 /// allocator that the tree uses for the allocation of nodes.
119 /// @tparam TTree The type of the templated instantiation of struct
120 /// #"detail::StringTreeBase;*" that this method is invoked by.
121 /// (Deduced by the compiler.)
122 template<typename TTree>
123 static
124 void InitializeNode( typename TTree::Node& node, TTree& tree ) {
125 (void) tree;
126
127 // if not a local string buffer, then dynamically allocate and copy.
128 if constexpr (TLocalCapacity <= 0) {
129 CharacterType* buffer= new CharacterType[size_t(node.name.key.Length())];
130 node.name.key.CopyTo( buffer );
131 node.name.key= strings::TString<CharacterType>( buffer, node.name.key.Length() );
132 } else {
133 // create a local string which may allocate heap if name is too long
134 strings::TString<TChar> key= node.name.key; // get current pointer
135 new (&node.name.storage) NameStringType(); // placement-new to re-establish local string
136 node.name.storage.DbgDisableBufferReplacementWarning(); // Disable warnings
137 ALIB_DBG( const TChar* internalBuffer= node.name.storage.Buffer(); ) // get internal local buffer
138 node.name.storage.Append(key); // copy key to buf
139 ALIB_DBG( ++DBG_STATS_STRINGTREE_NAMES;
140 if( internalBuffer != node.name.storage.Buffer() ) // ++statistics if local buffer was too small
141 ++DBG_STATS_STRINGTREE_NAME_OVERFLOWS; )
142 } }
143
144 /// This implementation frees the dynamically allocated memory of the node's name.
145 /// \see
146 /// See the class description for further information.
147 /// @param node The node that is to be removed. Allows access to the key and
148 /// custom value data. While the parent and sibling nodes are likewise accessible,
149 /// it is strictly forbidden to modify those.
150 /// @param tree The instance of struct #"detail::StringTreeBase;*" that invokes
151 /// this method. Any member may be accessed, including
152 /// #"StringTreeBase;nodeTable" which contains the
153 /// allocator that the tree uses for the allocation of nodes.
154 /// @tparam TTree The type of the templated instantiation of struct
155 /// #"detail::StringTreeBase;*" that this method is invoked by.
156 /// (Deduced by the compiler.)
157 template<typename TTree>
158 static
159 void FreeNode( typename TTree::Node& node, TTree& tree ) {
160 (void) tree;
161 if constexpr (TLocalCapacity <= 0)
162 delete[] node.name.key.Buffer();
163 else
164 node.name.storage.~TLocalString();
165 }
166
167}; // StringTreeNamesDynamic
168
169/// Built-in implementation usable as template parameter
170/// #"alib_ns_containers_stringtree_referencedoc;TNodeHandler" of class
171/// #"StringTree".
172///
173/// This type does not allocate memory and does not copy the key string of a node. Therefore, this
174/// type is very efficient to use in situations where exclusively "static" strings for child names
175/// and paths are passed to the interface methods of class \b StringTree (and inner types) which
176/// lead to the creation of new child nodes.<br>
177/// The term "static" here means that the strings given are either static character data of a
178/// compilation unit or by any other means their allocated memory and the contained data survive
179/// the life-cycle of the corresponding \b StringTree.
180///
181/// \see
182/// Two other built-in implementations of this type to be used with \b StringTree instantiations
183/// are provided with this \alibmod:
184/// - #"StringTreeNamesDynamic".
185/// - #"StringTreeNamesAlloc".
186/// \see
187/// Further information can be found in chapter #"alib_ns_containers_stringtree_alloc_names"
188/// of the reference documentation of class \b StringTree.
189///
190/// @tparam TChar The character type of the key strings. This type is used with any
191/// interface method of #"StringTree" that accepts a node name or path
192/// string.
193template<typename TChar= character>
194struct StringTreeNamesStatic
195{
196 /// The character type that the \b StringTree uses for child name and path strings.
197 using CharacterType = TChar;
198
199 /// The string-type of a node's name.
200 using NameStringType = strings::TString<TChar>;
201
202 /// This implementation is empty.
203 ///
204 /// \see
205 /// See description of this class and the "default implementation"
206 /// #"StringTreeNamesDynamic".
207 ///
208 /// @param node The node that was just created. Allows access to the key and
209 /// custom value data. While the parent and sibling nodes are likewise accessible,
210 /// it is strictly forbidden to modify those.
211 /// @param tree The instance of struct #"detail::StringTreeBase;*" that invokes
212 /// this method. Any member may be accessed, including
213 /// #"StringTreeBase;nodeTable" which contains the
214 /// allocator that the tree uses for the allocation of nodes.
215 /// @tparam TTree The type of the templated instantiation of struct
216 /// #"detail::StringTreeBase;*" that this method is invoked by.
217 /// (Deduced by the compiler.)
218 template<typename TTree>
219 static
220 void InitializeNode( typename TTree::Node& node, TTree& tree ) { (void) node; (void) tree; }
221
222 /// This implementation is empty.
223 ///
224 /// \see
225 /// See description of this class and the "default implementation"
226 /// #"StringTreeNamesDynamic".
227 ///
228 /// @param tree The instance of struct #"detail::StringTreeBase;*" that invokes
229 /// this method. Any member may be accessed, including
230 /// #"StringTreeBase;nodeTable" which contains the
231 /// allocator that the tree uses for the allocation of nodes.
232 /// @param node The node that is to be removed. Allows access to the key and
233 /// custom value data. While the parent and sibling nodes are likewise accessible,
234 /// it is strictly forbidden to modify those.
235 /// @tparam TTree The type of the templated instantiation of struct
236 /// #"detail::StringTreeBase;*" that this method is invoked by.
237 /// (Deduced by the compiler.)
238 template<typename TTree>
239 static
240 void FreeNode( TTree::Node& node, TTree& tree ) { (void) node; (void) tree; }
241}; // StringTreeNamesStatic
242
243/// Built-in implementation usable as template parameter
244/// #"alib_ns_containers_stringtree_referencedoc;TNodeHandler" of class
245/// #"StringTree".
246///
247/// This type copies the node's name into memory acquired with the monotonic allocator that the
248/// \b StringTree uses.<br>
249///
250/// \attention
251/// The use of this type is dangerous in respect to memory exhaustion. While class
252/// \b StringTree uses monotonic allocation in a
253/// #"alib_ns_containers_stringtree_hashing;very safe way", with the use of this
254/// type, repeated removals and insertions of tree nodes, increase the memory usage.<br>
255/// Consequently, the use of this type is restricted to cases that imply a limited
256/// number of insertions.
257///
258/// \see
259/// Two other built-in implementations of this type to be used with \b StringTree instantiations
260/// are provided with this \alibmod:
261/// - #"StringTreeNamesStatic".
262/// - #"StringTreeNamesDynamic".
263/// \see
264/// Further information can be found in chapter #"alib_ns_containers_stringtree_alloc_names"
265/// of the reference documentation of class \b StringTree.
266///
267/// @tparam TChar The character type of the key strings. This type is used with any
268/// interface method of #"StringTree" that accepts a node name or path
269/// string.
270template<typename TChar= character>
271struct StringTreeNamesAlloc
272{
273 /// The character type that the \b StringTree uses for child name and path strings.
274 using CharacterType= TChar;
275
276 /// The string-type of a node's name.
277 using NameStringType = strings::TString<TChar>;
278
279 /// This implementation copies the node's name to a piece of memory allocated in the
280 /// allocator found in field #"StringTreeBase;nodeTable"
281 /// of the given \p{tree}.
282 ///
283 /// \see
284 /// See description of this class and the "default implementation"
285 /// #"StringTreeNamesDynamic".
286 ///
287 /// @param node The node that was just created. Allows access to the key and
288 /// custom value data. While the parent and sibling nodes are likewise accessible,
289 /// it is strictly forbidden to modify those.
290 /// @param tree The instance of struct #"detail::StringTreeBase;*" that invokes
291 /// this method. Any member may be accessed, including
292 /// #"StringTreeBase;nodeTable" which contains the
293 /// allocator that the tree uses for the allocation of nodes.
294 /// @tparam TTree The type of the templated instantiation of struct
295 /// #"detail::StringTreeBase;*" that this method is invoked by.
296 /// (Deduced by the compiler.)
297 template<typename TTree>
298 static
299 void InitializeNode( typename TTree::Node& node, TTree& tree )
300 { node.name.storage.Allocate( tree.nodeTable.GetAllocator(), node.name.key ); }
301
302 /// This implementation does nothing.
303 ///
304 /// \see
305 /// See description of this class and the "default implementation"
306 /// #"StringTreeNamesDynamic".
307 ///
308 /// @param tree The instance of struct #"detail::StringTreeBase;*" that invokes
309 /// this method. Any member may be accessed, including
310 /// #"StringTreeBase;nodeTable" which contains the
311 /// allocator that the tree uses for the allocation of nodes.
312 /// @param node The node that is to be removed. Allows access to the key and
313 /// custom value data. While the parent and sibling nodes are likewise accessible,
314 /// it is strictly forbidden to modify those.
315 /// @tparam TTree The type of the templated instantiation of struct
316 /// #"detail::StringTreeBase;*" that this method is invoked by.
317 /// (Deduced by the compiler.)
318 template<typename TTree>
319 static
320 void FreeNode( typename TTree::baseNode& node, TTree& tree ) { (void) node; (void) tree; }
321};
322
323//==================================================================================================
324/// # 1. Introduction # {#alib_ns_containers_stringtree_overview}
325/// This container type implements a directed, non-circular graph (tree) with named nodes.
326///
327/// The internal node type #"detail::StringTreeBase::Node;*" stores:
328/// 1. A name string, which has to be unique in respect to the names of sibling nodes. (Just like
329/// no two files in a folder may have the same name.)
330/// 2. Five pointers to related nodes:
331/// - the parent node
332/// - the previous and next sibling nodes,
333/// - the first and last child nodes,
334/// 3. A data field holding the node's custom value of template type \p{T}.
335///
336/// The way from the root node to a descendent node, usually is called "path". The class incorporates
337/// functionality to work with string representations of such paths where names of child nodes are
338/// concatenated and separated by a special separation character.
339///
340/// The search and creation of tree nodes by using aforementioned path strings, is very similar to
341/// what is well known from addressing files and folders in file systems.
342/// This class does not differentiate between 'folders' and 'files', hence between 'nodes' and
343/// 'leafs'. Every node has the same data of type \p{T} attached and may or may not have child nodes.
344/// If such differentiation - or other semantics - is wanted, this may well be modeled by custom
345/// attributes provided in template type \p{T}.
346///
347/// \I{#############################################################################################}
348/// # 2. Helper Types # {#alib_ns_containers_stringtree_inner}
349/// Two important helper types exist.
350/// All operations on tree nodes like insertion, deletion, search, and attribute access is performed
351/// using objects of the public inner type #"StringTree::TCursor;*". This is a
352/// lightweight, iterator-like "handle" containing a pointer to the originating tree object and to
353/// a represented node. The type provides various methods to travers the tree. It is templated over
354/// a boolean value which determines if a const or mutable \b StringTree is given. Shortcuts for
355/// these types are #"StringTree::Cursor;*" and
356/// #"StringTree::ConstCursor;*".
357///
358/// Besides this, class #"StringTreeIterator" allows recursive iterations with
359/// built-in or custom sort orders. Note that this class is available with inclusion of
360/// #"F;ALib.Containers.StringTreeIterator.H".
361///
362/// Both types are explained in the following paragraphs.
363///
364/// \I{#############################################################################################}
365/// ## 2.1 Inner Class Cursor ## {#alib_ns_containers_stringtree_cursor}
366///
367/// The main interface into class \b %StringTree is given by public, inner type
368/// #"StringTree::Cursor;*". Method #".Root" returns an object of that type that
369/// initially refers to the root node of the tree.
370/// With this, child names and composite "paths" can be used to move the pointer along existing nodes
371/// of the tree or to create new child nodes or even a whole path of such child nodes at once.
372///
373/// Class \b %Cursor is very lightweight as it contains just two pointers, one to the
374/// \b %StringTree it originates from and one to the tree node currently represented.
375/// Hence, objects of this type can be copied, assigned, and passed around very efficiently.<br>
376/// The currently represented node's templated custom data can be accessed with method
377/// #"TCursor Value".
378///
379/// The methods to traverse over the nodes of the tree are:
380/// - #"TCursor GoToRoot"
381/// - #"TCursor GoToParent"
382/// - #"TCursor GoTo"
383/// - #"TCursor GoToNextSibling"
384/// - #"TCursor GoToPreviousSibling"
385/// - #"TCursor GoToChild"
386/// - #"TCursor GoToFirstChild"
387/// - #"TCursor GoToLastChild"
388///
389/// With these methods, class \b StringTree::Cursor constitutes a sort of iterator idiom
390/// idiom. For example, to traverse all entries in the root folder, the following schematic would
391/// be used:
392///
393/// myCursor= myTree.GetRoot()
394/// myCursor.GotoFirstChild()
395/// While( myCursor.IsValid() )
396/// DoSomething( myCursor.Value() )
397/// myCursor.GotoNextSibling
398///
399/// For some of these methods an alternative version exists, which returns a corresponding copy
400/// of the cursor, while leaving the original object unchanged. These methods share
401/// the same name excluding the prefix <b>GoTo</b>.
402///
403/// For the creation of new child nodes or a complete path of such, methods
404/// - #"TCursor GoToCreateChildIfNotExistent" and
405/// - #"TCursor GoToCreatedPathIfNotExistent"
406/// are provided.
407///
408/// Next, four methods that perform node deletion exist:
409/// - #"TCursor::DeleteChild(const NameType&)"
410/// - #"TCursor::DeleteChild(TCursor&)"
411/// - #"TCursor::DeleteChildren" and
412/// - #"TCursor::Delete"
413///
414/// The already mentioned methods:
415/// - #"TCursor::GoToParent",
416/// - #"TCursor::GoToFirstChild",
417/// - #"TCursor::GoToLastChild",
418/// - #"TCursor::GoToNextSibling" and
419/// - #"TCursor::GoToPreviousSibling"
420///
421/// of class \b Cursor can be used to iterate from a node upward to the root node or through the
422/// list of children of a node. Each method may \e invalidate the object in the case that no
423/// corresponding parent or sibling node exists.
424/// Invalid cursor objects can be (or rather have to be!) detected using the method
425/// #"TCursor::IsValid".
426/// Most of the class's methods must not be invoked on an invalidated object. Doing so is undefined
427/// behavior and #"alib_mod_assert;raises an ALib error" in debug-builds.
428/// Invalid \b %Cursor objects can reset to a valid state using the methods
429/// - #"TCursor::GoToRoot" and
430/// - #"TCursor::GoTo"
431///
432/// if absolute path addressing is used.
433///
434/// Instances that have been default-constructed may only be set to a valid state by (copy-)
435/// assigning a valid instance.
436///
437/// \I{#############################################################################################}
438/// ## 2.2. Class StringTreeIterator ## {#alib_ns_containers_stringtree_iterator}
439/// Class #"StringTreeIterator" provides a configurable and controlled
440/// way of iterating a branch of a tree. Some features of the class are:
441/// - Iterators can be initialized to start from any node of the tree
442/// Iteration ends when all (recursive) child nodes of the start node have been visited.
443/// - The iteration follows a "depth first search" approach: Before visiting a sibling node,
444/// all children of a node are visited. However, it is not differentiated whether a sibling
445/// has child nodes or not. In case all siblings with children are to be processed first,
446/// a custom sorter has to be created which prefers those nodes that have children.
447/// - The recursion depth can be limited, including to depth \c 0, which iterates only the
448/// direct child nodes of the start node.
449/// - Before entering a new depth-level during iteration, different sort orders can be set.
450/// The choices are:
451/// - No sorting (iterates in order of node insertion).
452/// - Built-in sorting by node (path) name, ascending/descending, case-sensitive or ignoring case
453/// - user-defined by path name, the number of children, or any other attribute of the node,
454/// of course including a node's custom data values.
455///
456/// Class \b StringTreeIterator is of rather heavy weight, and sorted iteration needs to allocate
457/// memory for sorting the child nodes for each depth level of a potential recursion.
458/// Therefore, it is recommended to reuse instances of the class with later, similar iterations.
459/// In addition, this explains why this class does not follow the concept of
460/// <c>std::iterator_traits</c>, which is designed to be used with lightweight iterator types.
461///
462/// \I{#############################################################################################}
463/// # 3. Node Allocation And Hashing # {#alib_ns_containers_stringtree_hashing}
464/// While each node maintains a doubly linked list of child nodes for iteration, this class stores
465/// each inserted element in a #"HashTable" using the parent node and the
466/// element's name as a unique key.
467/// This is done to be able to search for a child with a given name in constant time.
468/// This container does not perform any other memory allocations than those that this
469/// \b HashTable does.
470///
471/// With that, the implementation of this container type is able to leave all allocation and
472/// <em>"recycling"</em> of node elements to this hash table, which is found in base class's field
473/// #"detail::StringTreeBase::nodeTable;*". As explained in the documentation of
474/// #"HashTable", its allocation mechanism can be made safe in respect to
475/// memory exhaustion. This is true even if a #"MonoAllocator" is used and a virtually
476/// unlimited number of insertions and removals of elements is performed.
477/// Such safeness depends on template parameter \p{TRecycling} which is just passed to the
478/// internal hash table's definition of nodes.
479/// \see
480/// For more information on this topic see also chapter #"alib_contmono_intro_recycling"
481/// of this \alibmod_nl Programmer's Manual.
482///
483/// \I{#############################################################################################}
484/// # 4. Node and Node Name String Allocation # {#alib_ns_containers_stringtree_alloc_names}
485///
486/// The C++ version of this class allows user-defined allocation (and copying) of the node's name
487/// character strings. For this, a template parameter \p{TNodeHandler} is defined,
488/// which defaults to built-in struct #"StringTreeNamesDynamic".
489/// This default "node handler" defines the name type of nodes to #"TLocalString;LocalString"
490/// with a default capacity of \c 32 characters.
491/// This way, this local string performs dynamic allocation automatically when a node is
492/// constructed.<br>
493/// In the case that many "long" node names are expected, it might be efficient to set the capacity
494/// to \c 0. In this case, type \b StringTreeNamesDynamic defines the string-type to a normal
495/// \b String and uses C++ keywords <c>new</c> and <c>delete[]</c> to allocate
496/// and free character buffers for the name string.
497///
498/// A second built-in and ready-to-use "node handler" type is given with
499/// #"StringTreeNamesStatic". This uses an unbuffered \b String and has empty
500/// implementations of its static methods. This way no copies of the original string buffers that
501/// are passed to the to interface methods of class \b Cursor that create children are made.
502/// This is useful (and very efficient!) if \b all child name and creation path strings provided
503/// of class \b %Cursor are permanently valid, or, in other words, their life-cycle spans over
504/// the life-cycle of the nodes in a tree. Then, the names do not need to be copied to dedicated
505/// allocated memory.
506///
507/// Finally, string trees that during their lifetime just grow and where no nodes (or only a limited
508/// number of nodes) are removed until the whole tree is disposed may be instantiated using
509/// the third built-in type #"StringTreeNamesAlloc".
510/// With that, the concept of #"alib_contmono_intro;monotonic allocation" that this container
511/// type might use can be extended to the node name strings.
512/// Type \b StringTreeNamesAlloc grabs the allocator from the tree provided with method
513/// #"StringTreeNamesAlloc::InitializeNode" and just clones the given
514/// string into this.
515///
516/// \I{#############################################################################################}
517/// # 5. Equipping the Root Node with Values # {#alib_ns_containers_stringtree_rootnodevalues}
518/// It depends on the field of application, whether the root node should dispose over an instance
519/// of custom type \p{T} or not.
520/// For example, a tree of depth \c 1, which could be implemented using type
521/// <c>std::vector<T></c>, no stored type \p{T} can be attached to the vector object itself, only
522/// to its "children".<br>
523/// Nevertheless, in many use cases, the root node naturally contains the same data as any other
524/// node in the tree. Therefore, if this class would not support root node data, using
525/// code would, for example, have to check a #"TCursor;Cursor" for pointing
526/// to the root node and in this case get the custom data from somewhere else.<br>
527/// On the other hand, if this class would "insist" in the provision of root node values, then already
528/// with construction of the tree, arguments for the construction of the associated \p{T} object
529/// would have to be provided - even if the root node value was never used.
530/// The provision of initial "dummy" root data, is sometimes not even (easily) possible, and would
531/// sometimes add the need to adjust the custom stored type \p{T} to fit into this class.
532/// (In fact, with former versions of \alib, root-node initialization data was mandatory to provide
533/// already with the construction of the tree.)
534///
535/// Therefore, this class makes the use of root node values optional. After construction of a
536/// \b StringTree, methods #"StringTree::ConstructRootValue" and
537/// methods #"StringTree::DestructRootValue" may be used to initialize and
538/// destruct the optional root nodes' data.
539///
540/// To prevent memory leaks, in debug-compilations, the following \alib_assertions and warnings are
541/// raised:
542/// - #"TCursor::Value;Cursor::Value" will raise an assertion if
543/// called on the root node without having set a value.
544/// - #"StringTree::ConstructRootValue" will raise a warning if called twice
545/// without a prior call to #"StringTree::DestructRootValue".
546/// - #"StringTree::DestructRootValue" will raise a warning if called without
547/// a prior call to #"StringTree::ConstructRootValue".
548/// - The destructor of this class will raise a warning if a root value was set but not deleted.
549///
550/// \I{#############################################################################################}
551/// # Reference Documentation # {#alib_ns_containers_stringtree_referencedoc}
552///
553/// @tparam TAllocator The #"lang::Allocator;allocator type" to use.
554/// @tparam T The custom type of elements stored in this container.
555/// @tparam TNodeHandler
556/// A template type that needs to provide an interface as documented with
557/// #"StringTreeNamesDynamic", which is also the default type
558/// if not specified. For details see
559/// #"alib_ns_containers_stringtree_alloc_names;the corresponding section" of this
560/// class's documentation.
561/// The type is published as #"StringTree::HandlerType;*".
562/// @tparam TRecycling Denotes the type of recycling that is to be performed.
563/// Possible values are
564/// #"Recycling::None",
565/// #"Recycling::Private" (the default), or
566/// #"Recycling::Shared".
567//==================================================================================================
568template<typename TAllocator,
569 typename T,
570 typename TNodeHandler= StringTreeNamesDynamic<character>,
571 Recycling TRecycling = Recycling::Private>
572class StringTree : protected detail::StringTreeBase<TAllocator,T,TNodeHandler,TRecycling>
573{
574 #if !DOXYGEN
575 protected:
576 friend class Cursor;
577 friend class ConstCursor;
578 friend TNodeHandler;
579
580 using basetree = detail::StringTreeBase<TAllocator,T,TNodeHandler,TRecycling>;
581 using baseNodeKey = typename basetree::NodeKey;
582 using baseNodeBase = typename basetree::NodeBase;
583 using baseNode = typename basetree::Node;
584 using baseCursor = typename basetree::CursorBase;
585 using baseConstCursor = typename basetree::ConstCursorBase;
586 #endif
587
588 public:
589 /// Type definition publishing template parameter \p{TAllocator}.
590 using AllocatorType = TAllocator;
591
592 /// The character type of node names and paths strings. This is defined using character type
593 /// definition #"StringTreeNamesDynamic::CharacterType" of template
594 /// type \p{TNodeHandler}.
595 using CharacterType = typename TNodeHandler::CharacterType;
596
597 /// The string-type of node names and paths. This is defined using character type definition
598 /// #"StringTreeNamesDynamic::CharacterType" of template type
599 /// \p{TNodeHandler}.
600 using NameType = strings::TString<CharacterType>;
601
602 /// The substring-type of paths. This is defined using character type definition
603 /// #"StringTreeNamesDynamic::CharacterType" of template type
604 /// \p{TNodeHandler}.
605 using SubstringType = typename strings::TSubstring<CharacterType>;
606
607 /// Type definition publishing template parameter \p{TNodeHandler}.
608 using HandlerType = TNodeHandler;
609
610 /// This type definition may be used to define an externally managed shared recycler,
611 /// which can be passed to the alternative constructor of this class when template
612 /// parameter \p{TRecycling} equals #"Recycling::Shared".
613 /// \see
614 /// Chapter #"alib_contmono_containers_recycling_shared" of the Programmer's Manual
615 /// for this \alibmod.
616 using SharedRecyclerType= typename basetree::SharedRecyclerType;
617
618 /// A handle type used with methods #"TCursor::Export" and #"ImportCursor".
619 /// \note
620 /// Exported #"%StringTree"-cursors are nothing but pointers to the node in the tree.
621 /// The field #".value" is of type #"alib::uinteger" and hence the size of a pointer.
622 /// This class has a very relaxed implementation, which is expressed, for example, in the
623 /// fact that this field is named in lower-case, while still being publicly accessible.
624 /// The rationale for this exclamation from the naming-rules is that the reservation of a
625 /// cursor handle should be possible for external code without including any specific
626 /// header files, by simply reserving a #"alib::uinteger".<br>
627 /// On the other hand, wherever possible, this class and its sibling #"ConstCursorHandle"
628 /// should be used to make the code better readable.
629 /// It might happen that this design is changed in the future.
630 struct CursorHandle
631 {
632 /// The encapsulated value.
633 uinteger value;
634
635 /// Comparison operator.
636 /// @param other The cursor handle to compare this handle to.
637 /// @return \c true if both handles refer to the same cursor or if both handles are
638 /// invalid. \c false otherwise.
639 bool operator==(const CursorHandle& other) const noexcept { return value==other.value; }
640
641 /// Checks if this is a valid handle.
642 /// @return \c true if this handle is not nulled.
643 bool IsValid() const noexcept { return value != 0; }
644 };
645
646 /// A handle type used with methods #"TCursor::Export" and #"ImportCursor".
647 struct ConstCursorHandle
648 {
649 uinteger value; ///< The encapsulated value.
650
651 /// Defaulted default constructor.
652 ConstCursorHandle() =default;
653
654 /// Constructor accepting a raw value.
655 /// @param pValue The value that this handle is supposed to use.
656 ConstCursorHandle(uinteger pValue) : value{pValue} {}
657
658 /// Constructor accepting a mutable handle.
659 /// @param mutableHandle The mutable handle that is to be converted to a constant one.
660 ConstCursorHandle( const CursorHandle& mutableHandle) : value{mutableHandle.value} {}
661
662 /// Comparison operator.
663 /// @param other The cursor handle to compare this handle to.
664 /// @return \c true if both handles refer to the same cursor or if both handles are
665 /// invalid. \c false otherwise.
666 bool operator==(const ConstCursorHandle& other) const noexcept
667 { return value==other.value; }
668
669 /// Comparison operator.
670 /// @param other The cursor handle to compare this handle to.
671 /// @return \c true if both handles refer to the same cursor or if both handles are
672 /// invalid. \c false otherwise.
673 bool operator==(const CursorHandle& other) const noexcept { return value==other.value; }
674
675 /// Checks if this is a valid handle.
676 /// @return \c true if this handle is not nulled.
677 bool IsValid() const noexcept { return value != 0; }
678 };
679
680
681 /// This public, inner class provides the main interface into outer class \b StringTree.
682 /// The class should be considered being similar to a simple pointer or to a lightweight
683 /// iterator type, which refers to a tree and a current node.<br>
684 /// The class's interface allows the access to a node's name and value and to insert and
685 /// remove child nodes.
686 ///
687 /// Instances of this class can be received with method #Root and then from methods of this
688 /// type itself.
689 ///
690 /// The default constructor creates an invalid object, which has to be initialized by
691 /// assigning a valid object before its first use.
692 ///
693 /// \see
694 /// For more information on how this class is used, see paragraph
695 /// #"alib_ns_containers_stringtree_cursor"
696 /// of the description of class \b %StringTree.
697 ///
698 /// @tparam TConst If true, internal fields representing the StringTree and the current Node
699 /// become \c const and methods which are not declared \c const become
700 /// unavailable.
701 ///
702 /// ## Friends ##
703 /// class #"StringTree"
704 template<bool TConst>
705 class TCursor : protected basetree::template TCursorBase<TConst>
706 {
707 #if !DOXYGEN
708 friend class StringTree;
709 #endif
710
711 #if !DOXYGEN
712 #if ALIB_DEBUG_CRITICAL_SECTIONS
713 #define DCS ALIB_DCS_WITH(cmCursor::tree->nodeTable.dcs)
714 #define DCSSHRD ALIB_DCS_SHARED_WITH(cmCursor::tree->nodeTable.dcs)
715 #else
716 #define DCS
717 #define DCSSHRD
718 #endif
719 #endif
720
721 protected:
722 /// Constant or mutable version of the base tree type, depending on template parameter
723 /// \p{TConst}
724 using cmTree = std::conditional_t<!TConst, basetree, const basetree>;
725
726 /// Constant or mutable version of the base node type, depending on template parameter
727 /// \p{TConst}
728 using cmNode = std::conditional_t<!TConst, baseNode, const baseNode>;
729
730 /// Constant or mutable version of the base cursor type, depending on template parameter
731 /// \p{TConst}
732 using cmCursor = std::conditional_t<!TConst, baseCursor, baseConstCursor>;
733
734 //############################## Protected methods (class Cursor) ############################
735 /// Internal constructor
736 /// @param pNode The node to refer to.
737 /// @param pTree The \b %StringTree we work on.
738 TCursor(cmNode *pNode, cmTree *pTree) noexcept
739 : basetree::template TCursorBase<TConst>(pNode, pTree) {}
740
741 /// Checks if this cursor is associated with a tree.
742 /// Empty and optimized out with release-builds.
743 void dbgCheckTree() const {
744 ALIB_ASSERT_ERROR(cmCursor::tree != nullptr, "STRINGTREE",
745 "Invalid StringTree::Cursor: No binding with a StringTree. "
746 "(Probably default-constructed.)")
747 }
748
749 /// Checks if this cursor is associated with a tree and a valid node of the tree.
750 /// Empty and optimized out with release-builds.
751 void dbgCheckTreeAndNode() const {
752 dbgCheckTree();
753 ALIB_ASSERT_ERROR( cmCursor::node != nullptr, "STRINGTREE",
754 "Invalid StringTree::Cursor not representing a node of the assigned tree." )
755 }
756
757 //########################### Constructor, comparison operators, etc #########################
758 public:
759 /// Constant or mutable version of the outer string tree type, depending on template
760 /// parameter \p{TConst}
761 using TStringTree = std::conditional_t<!TConst, StringTree, const StringTree>;
762
763
764 /// Public constructor. Creates an invalid cursor.
765 /// The only way to make a default-constructed instance valid is by
766 /// (copy-) assigning another instance.
767 TCursor() noexcept =default;
768
769 /// Copy constructor.
770 /// @param src The cursor to copy.
771 TCursor( const TCursor& src) noexcept
772 : TCursor{ src.node, src.tree } {}
773
774 /// Move constructor.
775 /// @param src The cursor to move.
776 TCursor( TCursor&& src) noexcept
777 : TCursor{ src.node, src.tree } {}
778
779 /// Trivial default copy assign operator.
780 /// @return A reference to \c this.
781 TCursor &operator=(const TCursor &) noexcept =default;
782
783 /// Trivial default move assign operator.
784 /// @return A reference to \c this.
785 TCursor &operator=(TCursor &&) noexcept =default;
786
787 /// Trivial default destructor.
788 ~TCursor() noexcept =default;
789
790 /// Conversion operator from <em>TCursor<TConst></em> to <em>TCursor<!TConst></em>.
791 /// For const to mutable, this will fail as intended.
792 /// @return A constant iterator, if this is a mutable. Otherwise compilation will
793 /// duly fail.
794 operator TCursor<!TConst>() { return TCursor<!TConst>(cmCursor::node, cmCursor::tree); }
795
796 /// Comparison operator.
797 /// @param other The object to compare ourselves to.
798 /// @return \c true if this and the given cursor are equal, \c false
799 /// otherwise.
800 bool operator==(const TCursor &other) const {
801 return cmCursor::node == other.node
802 && cmCursor::tree == other.tree;
803 }
804
805 /// Comparison operator.
806 /// @param other The object to compare ourselves to.
807 /// @return \c false if this and the given cursor are equal, \c true
808 /// otherwise.
809 bool operator!=(const TCursor &other) const { return !((*this) == other); }
810
811 /// This method exports the address of the node in the \b StringTree.
812 /// The second pointer needed to comprise a cursor determines the tree a node belongs to.
813 /// Sometimes, it is necessary to store and restore a cursor, where the corresponding
814 /// tree is known. With this method, in combination with method StringTree::ImportCursor,
815 /// such storage with <c>sizeof(void*)</c>(instead of twice that size).
816 ///
817 /// \attention In fact this method and the corresponding constructor perform pointer
818 /// operations and keyword <c>reinterpret_cast</c>. Use with care.
819 /// @return A value usable to reconstruct this cursor with the method
820 /// #"StringTree::ImportCursor".
821 CursorHandle Export() { return CursorHandle{uinteger(cmCursor::node)}; }
822
823 /// Overloaded \c const version that returns a \c const handle, usable likewise only
824 /// to re-construct a \c const cursor instance.
825 ///
826 /// @return A value usable to reconstruct this cursor with method
827 /// #"StringTree::ImportCursor".
828 ConstCursorHandle Export() const { return ConstCursorHandle {uinteger(cmCursor::node)}; }
829
830 /// Determines if this is a valid object. Cursors may become invalid with
831 /// transition methods like #GoToParent, #GoToFirstChild, or GoToNextSibling.
832 /// An invalid object may be turned into a valid one by either
833 /// - assigning a valid object (copy assignment), or
834 /// - invoking method #GoToRoot, or
835 /// - invoking method #GoTo using absolute path addressing.
836 ///
837 /// Note that the latter is not applicable to a default-constructed objects
838 /// (which are also invalid) as with such no \b %StringTree is assigned.
839 ///
840 /// @return \c true if this is a valid cursor.
841 /// If invalid, \c false is returned and this object must not be used.
842 bool IsValid() const { return cmCursor::node != nullptr; }
843
844 /// Returns the opposite of #IsValid.
845 ///
846 /// @return \c true if this is an invalid cursor that must not be used,
847 /// \c false otherwise.
848 bool IsInvalid() const { return !IsValid(); }
849
850 //######################### Tree navigation inplace, returning status ########################
851 /// Returns a cursor to the root node of the tree.
852 /// @return A cursor representing the root node of the tree this pointer
853 /// represents.
854 TCursor Root() const {
855 dbgCheckTree();
856 return TCursor(cmCursor::tree, &cmCursor::tree->root.root);
857 }
858
859 /// Moves this cursor to the root node of the tree.
860 /// @return A reference to this object
861 TCursor& GoToRoot() {
862 dbgCheckTree();
863 cmCursor::node = &cmCursor::tree->root.root;
864 return *this;
865 }
866
867 /// Creates a cursor value representing the parent node of the
868 /// node represented by this object.
869 ///
870 /// If this object represents the root node of the tree, the returned cursor
871 /// is invalid.
872 ///
873 /// @return A cursor pointing to the parent node of the node represented
874 /// by this cursor.
875 TCursor Parent() const {
876 dbgCheckTreeAndNode();
877 return TCursor(static_cast<cmNode*>(cmCursor::node->parent), cmCursor::tree);
878 }
879
880 /// Moves this cursor to the parent of the current node.
881 /// If this is the root node, this object becomes invalid.
882 ///
883 /// @return *this to allow concatenated calls
884 TCursor& GoToParent() {DCSSHRD
885 dbgCheckTreeAndNode();
886 cmCursor::node = static_cast<cmNode*>(cmCursor::node->parent);
887 return (*this);
888 }
889
890 /// Returns a cursor value that represents the next sibling of the node
891 /// represented this cursor.
892 /// If the node has no next sibling, an invalid cursor is returned.
893 ///
894 /// @return A cursor object representing the next sibling of the node
895 /// represented by this object.
896 TCursor NextSibling() const {DCSSHRD
897 return TCursor( HasNextSibling() ? static_cast<cmNode*>(cmCursor::node->next())
898 : nullptr,
899 cmCursor::tree );
900 }
901
902 /// Moves this cursor to the next sibling of the represented node.
903 /// If the node has no next sibling, this cursor becomes invalid.
904 /// The latter is always true if this is the root node of the tree.
905 ///
906 /// @return \c true if this cursor was moved,
907 /// \c false if the represented node has no next sibling.
908 bool GoToNextSibling() {DCSSHRD
909 // go to node next and check for hook?
910 if (HasNextSibling()) {
911 cmCursor::node = static_cast<cmNode*>(cmCursor::node->next());
912 return true;
913 }
914 cmCursor::node = nullptr;
915 return false;
916 }
917
918 /// Returns a cursor value that represents the previous sibling of the node
919 /// represented this cursor.
920 /// If the node has no previous sibling, an invalid cursor is returned.
921 ///
922 /// @return A cursor object representing the previous sibling of the node
923 /// represented by this object.
924 TCursor PreviousSibling() const {DCSSHRD
925 return TCursor( HasPreviousSibling() ? static_cast<cmNode*>(cmCursor::node->prev())
926 : nullptr,
927 cmCursor::tree );
928 }
929
930 /// Moves this cursor to the previous sibling of the represented node.
931 /// If the node has no previous sibling, this cursor becomes invalid.
932 /// The latter is always true if this is the root node of the tree.
933 ///
934 /// @return \c true if this cursor was moved,
935 /// \c false if the represented node has no previous sibling.
936 bool GoToPreviousSibling() {DCSSHRD
937 if( HasPreviousSibling() ) {
938 cmCursor::node= static_cast<cmNode*>(cmCursor::node->prev());
939 return true;
940 }
941 cmCursor::node= nullptr;
942 return false;
943 }
944
945 /// Returns a cursor object that represents the first child of the node
946 /// represented.
947 /// If the represented node has no children, an invalid cursor is returned.
948 ///
949 /// @return A cursor representing the first child of the node this cursor points to.
950 TCursor FirstChild() const {DCSSHRD
951 return TCursor( HasChildren() ? static_cast<cmNode*>(cmCursor::node->children.first())
952 : nullptr,
953 cmCursor::tree );
954 }
955
956 /// Moves this cursor to the first child of its represented node.
957 /// If the represented node has no children, this cursor becomes invalid.
958 ///
959 /// @return \c true if the cursor was moved, \c false if the represented node
960 /// has no children.
961 bool GoToFirstChild() {DCSSHRD
962 if( HasChildren() ) {
963 cmCursor::node= static_cast<cmNode*>(cmCursor::node->children.first());
964 return true;
965 }
966 cmCursor::node= nullptr;
967 return false;
968 }
969
970 /// Returns a cursor value that represents the last child of the node
971 /// represented.
972 /// If the represented node has no children, an invalid cursor is returned.
973 ///
974 /// @return A cursor representing the last child of the node represented
975 /// by this cursor.
976 TCursor LastChild() const {DCSSHRD
977 return TCursor( HasChildren() ? static_cast<cmNode*>(cmCursor::node->children.last())
978 : nullptr,
979 cmCursor::tree );
980 }
981
982 /// Moves this cursor to the last child of its represented node.
983 /// If the represented node has no children, this cursor becomes invalid.
984 ///
985 /// @return \c true if the cursor was moved, \c false if the represented node
986 /// has no children.
987 bool GoToLastChild() {DCSSHRD
988 if( HasChildren() ) {
989 cmCursor::node= static_cast<cmNode*>(cmCursor::node->children.last());
990 return true;
991 }
992 cmCursor::node= nullptr;
993 return false;
994 }
995
996 /// Searches a child with the given name and returns a cursor to it.
997 /// If no child with this name exists, the returned cursor is invalid
998 ///
999 /// The given \p{name} is not considered a path and is not checked for being <c>"."</c>
1000 /// or <c>".."</c> or if it contains a separator character.
1001 /// Children with such name cannot exist and hence can't be found. However, in
1002 /// debug-builds, a #"alib_mod_assert;warning is raised".
1003 ///
1004 /// @param name The name of the child to search.
1005 /// @return A cursor representing the last child of the node represented
1006 /// by this cursor.
1007 TCursor Child( const NameType& name ) const {DCSSHRD
1008 dbgCheckTreeAndNode();
1009 ALIB_DBG( cmCursor::tree->checkChildName( name ); ) // gives warning
1010 return TCursor( static_cast<cmNode*>(cmCursor::node->findChild(cmCursor::tree, name)),
1011 cmCursor::tree );
1012 }
1013
1014 /// Searches a child with the given name and moves this cursor to it.
1015 /// If no child with this name exists, the cursor does not change and
1016 /// \c false is returned.
1017 ///
1018 /// The given \p{name} is not considered a path and is not checked for being <c>"."</c>
1019 /// or <c>".."</c> or if it contains a separator character.
1020 /// Children with such a name cannot exist and hence can't be found. However, in
1021 /// debug-builds, a #"alib_mod_assert;warning is raised".
1022 ///
1023 /// @param name The name of the child to search.
1024 /// @return \c true if the child existed and this object changed, \c false
1025 /// otherwise.
1026 bool GoToChild( const NameType& name ) {DCSSHRD
1027 dbgCheckTreeAndNode();
1028 ALIB_DBG( cmCursor::tree->checkChildName( name ); )
1029
1030 cmNode* child= static_cast<cmNode*>(cmCursor::node->findChild( cmCursor::tree, name ));
1031 if(child) {
1032 cmCursor::node= child;
1033 return true;
1034 }
1035 return false;
1036 }
1037
1038 /// Moves this cursor to the child with given \p{name}.
1039 /// If no child with this name exists, one will be created.
1040 ///
1041 /// If the given \p{childName} is invalid (equals to <c>"."</c> or
1042 /// <c>".."</c> or contains the separation character), then still \c true is returned,
1043 /// but this cursor becomes invalid.
1044 /// In addition, with debug-builds, a #"alib_mod_assert;warning is raised".
1045 ///
1046 /// @tparam TArgs Types of variadic parameters given with parameter \p{args}.
1047 /// @param name The name of the desired child.
1048 /// @param args Variadic parameters to be forwarded to the constructor of custom type
1049 /// \p{T} in the case a child is created.
1050 /// @return A pair of a cursor pointing to the child and a boolean that equals
1051 /// \c false if the child was found, and \c true if a child was created.
1052 /// If the given name was invalid, the returned cursor will be invalid
1053 /// while the boolean still indicates "not found" (aka \c true).
1054 template<typename... TArgs>
1055 std::pair<TCursor, bool> CreateChildIfNotExistent( const NameType& name,
1056 TArgs&&... args ) {DCS
1057 dbgCheckTreeAndNode();
1058 if( !cmCursor::tree->checkChildName( name ) )
1059 return std::make_pair( TCursor(cmCursor::tree, nullptr), true );
1060
1061 auto result= cmCursor::node->findOrCreateChild( cmCursor::tree, name,
1062 std::forward<TArgs>(args)... );
1063
1064 return std::make_pair( TCursor( cmCursor::tree, result.first ), result.second );
1065 }
1066
1067 /// Moves this cursor to the child with given \p{name}.
1068 /// If no child with this name exists, one will be created.
1069 ///
1070 /// If the given \p{childName} is invalid (equals to <c>"."</c> or
1071 /// <c>".."</c> or contains the separation character), then still \c true is returned,
1072 /// but this cursor becomes invalid.
1073 /// In addition, with debug-builds, a #"alib_mod_assert;warning is raised".
1074 ///
1075 /// @tparam TArgs Types of variadic parameters given with parameter \p{args}.
1076 /// @param name The name of the desired child.
1077 /// @param args Variadic parameters to be forwarded to the constructor of custom type
1078 /// \p{T} in the case a child is created.
1079 /// @return \c false if the child was found, and \c true if one was created or the given
1080 /// child name was invalid.
1081 template<typename... TArgs>
1082 bool GoToCreateChildIfNotExistent(const NameType& name, TArgs&&... args) {DCS
1083 dbgCheckTreeAndNode();
1084 if( !cmCursor::tree->checkChildName( name ) ) {
1085 cmCursor::node= nullptr;
1086 return true;
1087 }
1088
1089 auto result= cmCursor::node->findOrCreateChild( cmCursor::tree, name,
1090 std::forward<TArgs>(args)... );
1091
1092 cmCursor::node= static_cast<cmNode*>(result.first);
1093 return result.second;
1094 }
1095
1096 /// Follows the given \p{path} from the currently represented node to the target
1097 /// node and returns a new cursor instance..
1098 ///
1099 /// The method supports absolute and relative path addressing: If \p{path} begins
1100 /// with a separation character, then the transition starts with the root node of the
1101 /// \b %StringTree. Furthermore, child name <c>"."</c> is ignored and just skipped
1102 /// while a name of <c>".."</c> addresses the parent node during the transition.
1103 /// Repeated separation characters are ignored.<br>
1104 /// If, while processing the path string, the root node is found an the next
1105 /// path element is "..", this element is ignored and processing continues.
1106 /// As a sample, assuming that nodes \e /a and \e /b exist, the paths:
1107 ///
1108 /// /a/../b
1109 /// and
1110 ///
1111 /// /a/../../b
1112 /// both evaluate to
1113 ///
1114 /// /b
1115 ///
1116 /// Relative paths must not be used on #"TCursor::IsValid;invalid" cursors. Doing so
1117 /// is undefined behavior and #"alib_mod_assert;raises an ALib error" in
1118 /// debug-compilations.
1119 ///
1120 /// If a child along the path does not exist, the traversal is ended and the remaining
1121 /// portion of the path is returned.
1122 ///
1123 /// \note
1124 /// If parameter \p{path} is a temporary object, the resulting \b Substring must
1125 /// not be used, as it refers to the given string's buffer. In any case, its
1126 /// length can still be compared to \c 0 to evaluate success of the traversal.
1127 ///
1128 /// @param path The path to follow, starting with the node this pointer represents.
1129 ///
1130 /// @return A pair of a cursor pointing to last child not of the existing portion
1131 /// of the given \p{path}, and a substring that contains the non-existing
1132 /// portion of a path, or is empty if the complete path existed.
1133 std::pair<TCursor, SubstringType> operator()( const NameType& path ) const {DCSSHRD
1134 dbgCheckTreeAndNode();
1135 SubstringType remainingPath(path);
1136 cmNode* grandChild= cmCursor::followPath( remainingPath );
1137 return std::make_pair( TCursor(grandChild, cmCursor::tree), remainingPath );
1138 }
1139
1140 /// Same as the #"operator()(const NameType&)", but moves this cursor instead of returning
1141 /// a new one.
1142 /// @param path The path to move this cursor along.
1143 /// @return The unconsumed portion of the path.
1144 /// An empty \b Substring if the path existed.
1145 SubstringType GoTo( const NameType& path ) {DCSSHRD
1146 dbgCheckTreeAndNode();
1147 SubstringType remainingPath(path);
1148 cmCursor::node= cmCursor::followPath( remainingPath );
1149 return remainingPath;
1150 }
1151
1152 /// Follows the given path and creates non-existing children along the way.
1153 ///
1154 /// Child names <c>"."</c> and <c>".."</c> are allowed and respected the same as
1155 /// documented with the #"operator()(const NameType&)".
1156 /// New child nodes are constructed by forwarding the given \p{args}. Existing children
1157 /// remain untouched.
1158 ///
1159 /// @tparam TArgs Types of variadic parameters given with parameter \p{args}.
1160 /// @param path The path to move along.
1161 /// @param args Variadic parameters to be forwarded to the constructor of each node
1162 /// that is created.
1163 /// @return A <c>std::pair</c> containing a resulting \b Cursor and the number of nodes
1164 /// created.
1165 template<typename... TArgs>
1166 std::pair<TCursor, integer> CreatePathIfNotExistent( const NameType& path,
1167 TArgs&&... args ) {DCS
1168 dbgCheckTree();
1169 ALIB_ASSERT_ERROR( IsValid() || path.CharAtStart() == cmCursor::tree->separator,
1170 "STRINGTREE", "Invalid StringTree::Cursor given with relative path addressing." )
1171
1172 auto result= cmCursor::followPathCreate( path, std::forward<TArgs>(args)... );
1173
1174 return std::make_pair( TCursor(static_cast<cmNode*>(result.first), cmCursor::tree),
1175 result.second );
1176 }
1177
1178 /// Follows the given path and creates non-existing children along the way.
1179 ///
1180 /// Child names <c>"."</c> and <c>".."</c> are allowed and respected same as in
1181 /// #"operator()(const NameType&)".
1182 ///
1183 /// New child nodes are constructed by forwarding the given \p{args}. Existing children
1184 /// remain untouched.
1185 ///
1186 /// @tparam TArgs Types of variadic parameters given with parameter \p{args}.
1187 /// @param path The path to move along.
1188 /// @param args Variadic parameters to be forwarded to the constructor of each node
1189 /// that is created.
1190 /// @return The number of nodes created.
1191 template<typename... TArgs>
1192 int GoToCreatedPathIfNotExistent( const NameType& path,
1193 TArgs&&... args ) {DCS
1194 dbgCheckTree();
1195 ALIB_ASSERT_ERROR( IsValid() || path.CharAtStart() == cmCursor::tree->separator,
1196 "STRINGTREE", "Invalid StringTree::Cursor given with relative path addressing." )
1197
1198 auto result= cmCursor::followPathCreate( path, std::forward<TArgs>(args)... );
1199 cmCursor::node= static_cast<cmNode*>(result.first);
1200 return result.second;
1201 }
1202
1203 //###################################### Cursor Interface ####################################
1204 /// Returns the name of the represented node.
1205 /// Note that the concatenated names of recursive child nodes, separated by
1206 /// \p{TSeparator} constitute a \e path.
1207 ///
1208 /// @return A constant reference to the name of the represented node.
1209 const NameType& Name() const { dbgCheckTreeAndNode(); return cmCursor::node->name.key; }
1210
1211 /// Returns the tree that this cursor belongs to.
1212 /// @tparam TParent Optional template parameter, which casts the internal tree type
1213 /// to a derived type. This is for convenience, as otherwise the
1214 /// cast hast to be done by the caller which does not look too nice.
1215 /// @return The tree that this object refers to.
1216 template<typename TParent= StringTree>
1217 requires std::derived_from<TParent, StringTree>
1218 TParent& Tree() const { dbgCheckTree(); return *static_cast<TParent*>(cmCursor::tree); }
1219
1220 /// Retrieves a reference to the templated value of type \p{T} stored in the represented
1221 /// node.
1222 /// \note This method is only available if the template parameter \p{TConst} of this
1223 /// type is \c false.
1224 /// @see Operators #operator->() and #operator*().
1225 /// @tparam TRequires Defaulted template parameter. Must not be specified.
1226 /// @return The current node's value.
1227 template<bool TRequires= !TConst>
1228 requires TRequires
1229 T& Value() {
1230 dbgCheckTree();
1231 ALIB_ASSERT_ERROR( !IsRoot() || cmCursor::tree->dbgRootDataSet > 0, "STRINGTREE",
1232 "Root node has no value. Either this operation is unwanted or root node's value\n"
1233 "has to be explicitly set using ConstructRootValue(...)" )
1234 return static_cast<baseNode*>(cmCursor::node)->data;
1235 }
1236
1237 /// Retrieves a constant reference to the templated value of type \p{T} stored in
1238 /// the represented node.
1239 /// @see Operators #operator->() and #operator*().
1240 /// @return The current node's value.
1241 const T& Value() const {
1242 dbgCheckTree();
1243 ALIB_ASSERT_ERROR( !IsRoot() || cmCursor::tree->dbgRootDataSet > 0, "STRINGTREE",
1244 "Root node has no value. Either this operation is unwanted or root node's value\n"
1245 "has to be explicitly set using ConstructRootValue(...)" )
1246 return static_cast<const baseNode*>(cmCursor::node)->data;
1247 }
1248
1249 /// Retrieves a pointer to the templated value of type \p{T} stored
1250 /// in the represented node.
1251 /// \note This method is only available if the template parameter \p{TConst} of this
1252 /// type is \c false.
1253 /// @tparam TRequires Defaulted template parameter. Must not be specified.
1254 /// @return The current node's value.
1255 template<bool TRequires= !TConst>
1256 requires TRequires
1257 T* operator->() {
1258 dbgCheckTree();
1259 ALIB_ASSERT_ERROR( !IsRoot() || cmCursor::tree->dbgRootDataSet > 0, "STRINGTREE",
1260 "Root node has no value. Either this operation is unwanted or root node's value\n"
1261 "has to be explicitly set using ConstructRootValue(...)" )
1262 return &static_cast<baseNode*>(cmCursor::node)->data;
1263 }
1264
1265 /// Retrieves a constant pointer to the templated value of type \p{T} stored in
1266 /// the represented node.
1267 /// @return The current node's value.
1268 const T* operator->() const {
1269 dbgCheckTree();
1270 ALIB_ASSERT_ERROR( !IsRoot() || cmCursor::tree->dbgRootDataSet > 0, "STRINGTREE",
1271 "Root node has no value. Either this operation is unwanted or root node's value\n"
1272 "has to be explicitly set using ConstructRootValue(...)" )
1273 return &static_cast<const baseNode*>(cmCursor::node)->data;
1274 }
1275
1276 /// Retrieves a reference to the templated value of type \p{T} stored
1277 /// in the represented node.
1278 /// \note This method is only available if the template parameter \p{TConst} of this
1279 /// type is \c false.
1280 /// @tparam TRequires Defaulted template parameter. Must not be specified.
1281 /// @return The current node's value.
1282 template<bool TRequires= !TConst>
1283 requires TRequires
1284 T& operator*() {
1285 dbgCheckTree();
1286 ALIB_ASSERT_ERROR( !IsRoot() || cmCursor::tree->dbgRootDataSet > 0, "STRINGTREE",
1287 "Root node has no value. Either this operation is unwanted or root node's value\n"
1288 "has to be explicitly set using ConstructRootValue(...)" )
1289 return static_cast<baseNode*>(cmCursor::node)->data;
1290 }
1291
1292 /// Retrieves a reference to the templated value of type \p{T} stored
1293 /// in the represented node.
1294 /// \note This operator is only available if template parameter \p{TConst} is false.
1295 /// @return The current node's value.
1296 const T& operator*() const {
1297 dbgCheckTree();
1298 ALIB_ASSERT_ERROR( !IsRoot() || cmCursor::tree->dbgRootDataSet > 0, "STRINGTREE",
1299 "Root node has no value. Either this operation is unwanted or root node's value\n"
1300 "has to be explicitly set using ConstructRootValue(...)" )
1301 return static_cast<const baseNode*>(cmCursor::node)->data;
1302 }
1303
1304 /// Returns \c true if this cursor represents the root node of the
1305 /// \b %StringTree, \c false otherwise.
1306 /// @return \c true if this object represents the root node, \c false otherwise.
1307 bool IsRoot() const { dbgCheckTreeAndNode(); return cmCursor::node->isRoot(); }
1308
1309 /// Determines the depth of the node represented by this object. This is done by
1310 /// counting the iterations needed to reach the root node of the tree.
1311 /// @return The distance from this node to the root node.
1312 int Depth() const
1313 {DCSSHRD
1314 dbgCheckTreeAndNode();
1315 return cmCursor::node->depth();
1316 }
1317
1318 /// Determines the distance between the node represented by this cursor to the
1319 /// node represented by given \p{other}. The distace is defined as follows:
1320 ///
1321 /// - \b 0 if other represents the same node.
1322 /// - \b 1 if other represents the parent of this node.
1323 /// - \b 2 if other represents the grand-parent of this node.
1324 /// - \b 3 ...
1325 /// - \b N if other represents the root node.
1326 ///
1327 /// @param other The node to test.
1328 /// @return The distance from this node to the root node. \c -1 is returned in case
1329 /// \p{other} is not found in the path to this node.
1330 int Distance( const TCursor<true>& other ) const {DCSSHRD
1331 dbgCheckTreeAndNode();
1332 ALIB_ASSERT_ERROR( other.node, "STRINGTREE", "Invalid node given." )
1333 ALIB_ASSERT_ERROR( cmCursor::tree == other.tree, "STRINGTREE",
1334 "Given node belongs to a different StringTree." )
1335 return cmCursor::node->distance( other.node );
1336 }
1337
1338 /// Returns \c true if the represented node has at least one direct child.
1339 /// @return \c true if the current node has children, \c false otherwise.
1340 bool HasChildren() const
1341 {DCSSHRD
1342 dbgCheckTreeAndNode();
1343 return cmCursor::node->qtyChildren != 0;
1344 }
1345
1346 /// Returns the number of direct children of the represented node.<br>
1347 /// Note that this method runs in constant time.
1348 /// @return The number of direct children of the represented node.
1349 uinteger CountChildren() const
1350 {DCSSHRD
1351 dbgCheckTreeAndNode();
1352 return cmCursor::node->qtyChildren;
1353 }
1354
1355 /// Evaluates if the node represented by this object has a next sibling in its
1356 /// parent's list of children.
1357 /// @return \c true if a next sibling to this object's represented node exists,
1358 /// \c false otherwise.
1359 bool HasNextSibling() const {DCSSHRD
1360 dbgCheckTreeAndNode();
1361 return !IsRoot()
1362 && !cmCursor::node->parent->children.isLast( cmCursor::node );
1363 }
1364
1365 /// Evaluates if the node represented by this object has a previous sibling in its
1366 /// parent's list of children.
1367 /// @return \c true if a previous sibling to this object's represented node exists,
1368 /// \c false otherwise.
1369 bool HasPreviousSibling() const {DCSSHRD
1370 dbgCheckTreeAndNode();
1371 return !IsRoot()
1372 && !cmCursor::node->parent->children.isFirst( cmCursor::node );
1373 }
1374
1375 /// Writes the absolute path to the represented node (including the represented node's
1376 /// name) to the given \b %AString.<br>
1377 /// If this node represents the root node, then nothing is written but a single
1378 /// separation character.
1379 ///
1380 /// While the implementation of this method is as efficient as possible (to avoid
1381 /// insertions at the beginning of the target string while moving to the destination/root
1382 /// node, internally a local node-stack is created first, which then is traversed
1383 /// top-down), still in many situations, it is recommended to search for other ways to
1384 /// keep track of the current path of a node and modify and re-use such path.
1385 /// For this, class #"StringTreeIterator", optionally allows maintaining
1386 /// a string representing the current path with every iteration.
1387 ///
1388 /// \see
1389 /// Overloaded version <b>AssemblePath(AString&,TCursor<TConst>&,lang::CurrentData)</b>,
1390 /// which allows the creation a relative path from a parent node to this node.
1391 ///
1392 /// @param targetString The string buffer to append the path to.
1393 /// @param targetData Denotes whether \p{target} should be cleared before
1394 /// appending the path. Defaults to \b CurrentData::Clear.
1395 /// @return The given \b AString to allow concatenated operations.
1396 strings::TAString<typename cmTree::CharacterType, lang::HeapAllocator>&
1397 AssemblePath( strings::TAString<typename cmTree::CharacterType>& targetString,
1398 lang::CurrentData targetData=
1399 lang::CurrentData::Clear ) const
1400 {DCSSHRD
1401 if( targetData == lang::CurrentData::Clear )
1402 targetString.Reset();
1403
1404 return cmCursor::node->assemblePath( targetString, cmCursor::node, nullptr,
1405 cmCursor::tree->separator );
1406 }
1407
1408 /// Same as #AssemblePath but accepts a parent node to stop at, instead of the root node.
1409 /// The path created is a relative path from the \p{parent} to the represented node,
1410 /// hence it does \b not include the parent's name and also does \b not start with the
1411 /// separation character. The latter is true even if the given \p{targetParent} represents
1412 /// the root node. In this case the path is a relative path from the root node \c '/'
1413 /// to the child.
1414 ///
1415 /// If the given \p{parent} is not found within the list of parent nodes, then
1416 /// an absolute path from the tree's root to the represented node is returned.
1417 ///
1418 ///
1419 /// @param targetString The string buffer to append the path to.
1420 /// @param parent Denotes the parent node to start a relative path from.
1421 /// @param targetData Denotes whether \p{target} should be cleared before
1422 /// appending the path. Defaults to \b CurrentData::Clear.
1423 /// @return The given \b AString to allow concatenated operations.
1424 strings::TAString<typename cmTree::CharacterType, lang::HeapAllocator>&
1425 AssemblePath( strings::TAString<typename cmTree::CharacterType>& targetString,
1426 const TCursor<true>& parent,
1427 lang::CurrentData targetData
1428 = lang::CurrentData::Clear ) const
1429 {DCSSHRD
1430 dbgCheckTreeAndNode();
1431 if( targetData == lang::CurrentData::Clear )
1432 targetString.Reset();
1433 return cmCursor::node->assemblePath( targetString, cmCursor::node, parent.node,
1434 cmCursor::tree->separator );
1435 }
1436
1437 //################################### Cursor child creation ##################################
1438 /// Creates and returns a child node. If a node already exists, nothing is done and
1439 /// \c nullptr is returned as this is considered an error.
1440 ///
1441 /// If the child name is illegal (equal to <c>"."</c> or <c>".."</c> or contains a
1442 /// separation character), an \alib_warning is raised and an invalid cursor
1443 /// is returned.
1444 ///
1445 /// Template parameter \p{TCheck} may be used to suppress the search for an
1446 /// existing child with the same name, as well as the check for correctness of the
1447 /// given child name.
1448 /// This tremendously improves the execution performance of this method.
1449 ///
1450 /// \attention Setting template parameter \p{TCheck} to #"NC" and inserting
1451 /// child nodes with the same name, sets a \b %StringTree to an
1452 /// undefined state.
1453 ///
1454 /// @tparam TCheck If #"NC", no check for an existing child with the same name
1455 /// is performed.
1456 /// @tparam TArgs Types of variadic parameters given with parameter \p{args}.
1457 /// @param childName The name of the child
1458 /// @param args Variadic parameters to be forwarded to the constructor of custom
1459 /// type \p{T} of the child created.
1460 ///
1461 /// @return A new cursor object representing the created child node.
1462 /// If the given \p{childName} was invalid or the child existed already,
1463 /// the returned object is invalid.
1464 template<typename TCheck =CHK, typename... TArgs>
1465 TCursor CreateChild( const NameType& childName, TArgs&&... args ) const {DCS
1466 dbgCheckTreeAndNode();
1467 if constexpr ( TCheck::value ) {
1468 // check name
1469 if( !baseCursor::tree->checkChildName( childName ) ) {
1470 ALIB_WARNING( "STRINGTREE", "Illegal child name \"{}\"", childName )
1471 return Cursor( nullptr, baseCursor::tree );
1472 }
1473
1474 // check existence
1475 if( baseCursor::node->qtyChildren > 0
1476 && baseCursor::tree->nodeTable.Contains( baseNodeKey( baseCursor::node, childName) ))
1477 return Cursor( nullptr, baseCursor::tree );
1478 }
1479
1480 baseNode* child= &baseCursor::tree->nodeTable.EmplaceUnique( baseCursor::node, childName,
1481 std::forward<TArgs>(args)... )
1482 .Value();
1483 TNodeHandler::InitializeNode( *child, *baseCursor::tree );
1484
1485 baseCursor::node->children.pushEnd( child );
1486 ++baseCursor::node->qtyChildren;
1487 return TCursor( child, baseCursor::tree );
1488 }
1489
1490 //###################################### Cursor deletion #####################################
1491 /// Searches and deletes the child named \p{childName} from the node that this object
1492 /// refers to. This object itself is not changed.
1493 ///
1494 /// \see
1495 /// Overloaded version of this method that accepts a cursor referring to
1496 /// the child in question.
1497 ///
1498 ///
1499 /// @param childName The name of the desired child.
1500 /// @return \c true if the child existed and was deleted, \c false otherwise.
1501 bool DeleteChild( const NameType& childName ) const {DCS
1502 dbgCheckTreeAndNode();
1503 if( baseCursor::node->qtyChildren == 0 )
1504 return false;
1505
1506 auto handle= baseCursor::tree->nodeTable.Extract( baseNodeKey( baseCursor::node, childName) );
1507 if( handle.IsEmpty() )
1508 return false;
1509 handle.Value().deleteChildren( baseCursor::tree );
1510 TNodeHandler::FreeNode( handle.Value(), *baseCursor::tree );
1511 handle.Value().remove();
1512
1513 --baseCursor::node->qtyChildren;
1514 return true;
1515 }
1516
1517 /// Deletes the child represented by the given cursor \p{child} from the node that this
1518 /// cursor refers to. After the invocation, the given \p{child} cursor refers to its
1519 /// next sibling. If no such sibling exists, \p{child} becomes invalid.
1520 /// This cursor itself is not changed.
1521 ///
1522 /// \note
1523 /// This method is useful to implement forward iterations through children of a parent
1524 /// node with the aim to delete certain child nodes. No corresponding version of this
1525 /// method exists that moves the given \p{child} pointer to its previous sibling.
1526 /// For reverse iterations, a copy of the \p{child} argument has to be passed.
1527 /// However, any overhead caused by such temporary object creation will be optimized
1528 /// out by common C++ compilers.
1529 ///
1530 /// @param child Deletes the child represented by the given node.
1531 /// @return The total number of nodes deleted.
1532 uinteger DeleteChild( TCursor& child ) const {DCS
1533 dbgCheckTreeAndNode();
1534 cmNode* nodeToDelete= child.node;
1535 child.GoToNextSibling();
1536 return baseCursor::node->deleteChild( baseCursor::tree, nodeToDelete );
1537 }
1538
1539 /// Deletes the children of the node that this cursor refers to.
1540 /// This object itself is not changed.
1541 ///
1542 /// @return The number of children that were deleted.
1543 uinteger DeleteChildren() const
1544 {DCS
1545 dbgCheckTreeAndNode();
1546 return baseCursor::node->deleteChildren( baseCursor::tree );
1547 }
1548
1549 /// Deletes the branch that this cursor refers to from the tree.
1550 /// If this cursor does not represent the root node, then after the operation,
1551 /// it refers to the parent of the current node.<br>
1552 /// If the represented node is the root node, only the children are deleted and this
1553 /// object remains representing the root node. Note that in this case any explicitly
1554 /// set custom value of the root node is \b not deleted. For this, exclusively methods
1555 /// #ConstructRootValue and #DestructRootValue are to be used.
1556 ///
1557 /// \note
1558 /// When working with the class #"StringTreeIterator", this method invalidates an
1559 /// iterator instance if it is invoked on a returned cursor.
1560 /// To avoid this, the provided special method #"StringTreeIterator::DeleteNode;*"
1561 /// is to be used.
1562 ///
1563 /// @return
1564 /// The total number of nodes deleted. Can be zero, in case this object represents
1565 /// the root node and this node has no children.
1566 uinteger Delete() {DCS
1567 dbgCheckTreeAndNode();
1568 if( baseCursor::node->isRoot() )
1569 return baseCursor::node->deleteChildren( baseCursor::tree );
1570
1571 cmNode * child= baseCursor::node;
1572 baseCursor::node= static_cast<cmNode*>(baseCursor::node->parent);
1573 return baseCursor::node->deleteChild( baseCursor::tree, child );
1574 }
1575 }; // inner class TCursor
1576
1577 /// The mutable version of type \b TCursor<TConst>.
1578 using Cursor = TCursor<false>;
1579
1580 /// The constant version of type \b TCursor<TConst>.
1581 using ConstCursor = TCursor<true>;
1582
1583 protected:
1584 /// Protected methods that allows derived types to create cursor instances from
1585 /// nodes received directly from the hashtable.
1586 /// @param node The base node.
1587 /// @return A valid cursor.
1588 Cursor createCursor(baseNode& node) { return Cursor(&node, this); }
1589
1590 //################################################################################################
1591 // StringTree Main
1592 //################################################################################################
1593 public:
1594 #if !DOXYGEN
1595 #if ALIB_DEBUG_CRITICAL_SECTIONS
1596 #undef DCS
1597 #undef DCSSHRD
1598 #define DCS ALIB_DCS_WITH(basetree::nodeTable.dcs)
1599 #define DCSSHRD ALIB_DCS_SHARED_WITH(basetree::nodeTable.dcs)
1600 #endif
1601 #endif
1602
1603 /// Constructor.
1604 /// @param allocator The allocator instance to use.
1605 /// @param pathSeparator The separation character used with path strings.
1606 StringTree( AllocatorType& allocator, CharacterType pathSeparator )
1607 : basetree( allocator, pathSeparator ) {
1608 #if ALIB_DEBUG_CRITICAL_SECTIONS
1609 basetree::nodeTable.dcs.DCSName= "StringTree";
1610 #endif
1611 }
1612
1613 /// Constructor taking a shared recycler.
1614 /// @param pRecycler The shared recycler.
1615 /// @param pathSeparator The separation character used with path strings.
1616 template<typename TSharedRecycler= SharedRecyclerType>
1617 requires(!std::same_as<TSharedRecycler, void>)
1618 StringTree( CharacterType pathSeparator, TSharedRecycler& pRecycler )
1619 : basetree( pRecycler, pathSeparator ) {
1620 #if ALIB_DEBUG_CRITICAL_SECTIONS
1621 basetree::nodeTable.dcs.DCSName= "StringTree";
1622 #endif
1623 }
1624
1625 /// Destructor.
1626 /// Raises a warning if #"ConstructRootValue;a root value was set" but not deleted accordingly.
1627 ~StringTree() {
1628 for( auto& node : basetree::nodeTable )
1629 TNodeHandler::FreeNode( *static_cast<baseNode*>(&node), *this );
1630
1631 ALIB_ASSERT_WARNING( basetree::dbgRootDataSet == 0, "STRINGTREE",
1632 "Possible memory leak! The root node's value object was set but not deleted before\n"
1633 "destruction of this StringTree. To suppress this warning call DestructRootValue()\n"
1634 "before destruction. In case this is not necessary (because the stored type does not\n"
1635 "leak if not destructed), emplace it in macro ALIB_DBG() to remove the call in\n"
1636 "release-builds." )
1637 }
1638
1639 /// Shortcut to
1640 /// #"HashTable::GetAllocator;NodeTable().GetAllocator()".
1641 /// @return The allocator that was provided in the constructor and stored in the internal
1642 /// #NodeTable.
1643 AllocatorType& GetAllocator() noexcept { return basetree::nodeTable.GetAllocator(); }
1644
1645 #if ALIB_DEBUG_CRITICAL_SECTIONS
1646 /// Returns the critical sections debug instance to allow taking ownership from external
1647 /// code and increase the chance to detect the violation of critical sections.
1648 /// For example, this method is used by class #"StringTreeIterator".
1649 /// This method is available only if the configuration macro #"ALIB_DEBUG_CRITICAL_SECTIONS"
1650 /// is given.
1651 /// @return The internal DCS.
1652 lang::DbgCriticalSections& DbgGetDCS() const { return basetree::nodeTable.dcs; }
1653 #endif
1654
1655 /// Returns the path separator character that this string tree works with.
1656 /// @return The path separator character.
1657 constexpr CharacterType Separator() const noexcept { return basetree::separator; }
1658
1659 #if ALIB_DEBUG_CRITICAL_SECTIONS
1660 /// Sets the critical section name of this string tree. Empty and optimized out if compiler
1661 /// symbol #"ALIB_DEBUG_CRITICAL_SECTIONS" is not set.
1662 /// @param name The name to use with debug-assertions.
1663 void DbgSetDCSName(const char* name) const { basetree::nodeTable.dcs.DCSName= name; }
1664 #else
1665 constexpr void DbgSetDCSName(const char*) const {}
1666 #endif
1667
1668 /// Depending on the use case, it might be appropriate to attach a value of template type \p{T}
1669 /// to the root node of the tree. If so, this can be done with this method. If not done, in
1670 /// debug compilations, the method #"TCursor::Value" will
1671 /// raise an \alib_assertion if called on the root node.
1672 ///
1673 /// Custom data that is explicitly attached to the root node with this method has to be
1674 /// deleted explicitly by calling #DestructRootValue before deletion of the tree.
1675 ///
1676 /// @tparam TArgs Types of variadic parameters given with parameter \p{args}.
1677 /// @param args Variadic parameters to be forwarded to the constructor of custom
1678 /// type \p{T} of the child created.
1679 template<typename... TArgs>
1680 void ConstructRootValue( TArgs&&... args ) {
1681 #if ALIB_DEBUG
1682 ALIB_ASSERT_WARNING( basetree::dbgRootDataSet != 1, "STRINGTREE",
1683 "Root node value is set without prior deletion. Possible memory leak (depending on\n "
1684 "allocation of template type T). This warning is only printed on the first overwrite.")
1685 ++basetree::dbgRootDataSet;
1686 #endif
1687
1688 new (&basetree::root.root.data) T( std::forward<TArgs>(args)... );
1689 }
1690
1691 /// Calls the destructor of the custom data object of type \p{T}, which may explicitly set using
1692 /// #ConstructRootValue.\n
1693 /// If not done, in debug-compilations, an \alib_warning is raised in the destructor
1694 /// of this tree.
1695 void DestructRootValue() {
1696 #if ALIB_DEBUG
1697 ALIB_ASSERT_ERROR( basetree::dbgRootDataSet != 0, "STRINGTREE",
1698 "Deletion of root node data without prior setting (or double deletion)." )
1699 --basetree::dbgRootDataSet;
1700 #endif
1701 basetree::root.root.data.~T();
1702 }
1703
1704 /// Removes all elements from this container. The use of this method is more efficient than
1705 /// deleting the children of the root node.
1706 ///
1707 /// Invokes #"HashTable::Clear;*" on field
1708 /// #"StringTreeBase;nodeTable". As documented with that method, the
1709 /// allocated nodes will be preserved for "recycling" with future insertions.
1710 ///
1711 /// The custom data of the root node is preserved.
1712 void Clear() {DCS
1713 // clear the nodes in the table, then the table itself
1714 for( auto& node : basetree::nodeTable )
1715 TNodeHandler::FreeNode( *static_cast<baseNode*>(&node), *this );
1716 basetree::nodeTable.Clear();
1717
1718 // re-initialize root node
1719 basetree::root.root.children.reset();
1720 basetree::root.root.qtyChildren= 0;
1721 }
1722
1723 /// Clears all nodes and values. The use of this method is more efficient than deleting the
1724 /// children of the root node.<br>
1725 /// In addition, depending on template type \p{TNodeHandler}, it may also declare allocated
1726 /// memory for future reuse.<br>
1727 /// The latter is true for type #"StringTreeNamesAlloc".
1728 ///
1729 /// Invokes #"HashTable::Reset;*" on field
1730 /// #"StringTreeBase;nodeTable".
1731 /// As documented with that method, in the case of #"Recycling;private recycling",
1732 /// all previously allocated recyclable instances of the internal element type are disposed.
1733 ///
1734 /// \note The value of the root-node, set with #ConstructRootValue is not deleted.
1735 void Reset() {
1736 {DCS
1737 for( auto& node : basetree::nodeTable )
1738 TNodeHandler::FreeNode( *static_cast<baseNode*>(&node), *this );
1739 }
1740
1741 basetree::nodeTable.Reset();
1742 basetree::root.root.children.reset();
1743 basetree::root.root.qtyChildren= 0;
1744 }
1745
1746 /// Counts the number of currently allocated but unused (not contained) element nodes
1747 /// that will be recycled with upcoming insertions.
1748 ///
1749 /// \note
1750 /// This method is provided for completeness and unit-testing. It should not be of
1751 /// relevance for common usage.
1752 /// Furthermore, this method is not available (aka does not compile) with instantiations
1753 /// that specify template parameter \p{TRecycling} as
1754 /// #"Recycling::None".
1755 ///
1756 /// @return The number of removed and not yet recycled elements.
1757 integer RecyclablesCount() const { return basetree::nodeTable.RecyclablesCount(); }
1758
1759 /// Returns the overall number of elements contained in this tree.
1760 ///
1761 /// \note
1762 /// This method performs in constant time.
1763 ///
1764 /// @return The number elements contained in this tree.
1765 integer Size() const { return basetree::nodeTable.Size(); }
1766
1767 /// Tests for emptiness.
1768 ///
1769 /// @return \c true if this tree is empty, \c false otherwise.
1770 bool IsEmpty() const { return basetree::nodeTable.Size() == 0; }
1771
1772 /// Invokes #"HashTable::ReserveRecyclables;*" on the internal hashtable.
1773 ///
1774 /// @see Chapter #"alib_contmono_containers_recycling_reserving" of the Programmer's
1775 /// Manual.
1776 ///
1777 /// @param qty The expected resulting number (or increase) of elements to be stored in
1778 /// this container.
1779 /// @param reference Denotes whether \p{qty} is meant as an absolute size or an
1780 /// increase.
1781 void ReserveRecyclables( integer qty, lang::ValueReference reference )
1782 { basetree::nodeTable.ReserveRecyclables( qty, reference ); }
1783
1784 /// Returns the internal #"HashTable" used for storing the tree nodes.
1785 /// This may be used to manipulate load factors, for direct iteration over all nodes, etc.<br>
1786 /// \note The returned object should be used with caution to keep the tree and its data
1787 /// consistent.
1788 /// @return The internal node table.
1789 auto& NodeTable() { return basetree::nodeTable; }
1790
1791 /// Returns the internal #"HashTable" used for storing the tree nodes.
1792 /// This may be used to manipulate load factors, for direct iteration over all nodes, etc.<br>
1793 /// \note The returned object should be used with caution to keep the tree and its data
1794 /// consistent.
1795 /// @return The internal node table.
1796 const auto& NodeTable() const { return basetree::nodeTable; }
1797
1798 /// Creates a cursor instance representing the root node.
1799 /// @return A cursor pointing to the root node of this \b %StringTree.
1800 Cursor Root() { return Cursor( &basetree::root.root, this ); }
1801
1802 /// Creates a \c const cursor instance representing the root node.
1803 /// @return A read-only pointer, pointing to the root node of this \b %StringTree.
1804 const ConstCursor Root() const { return ConstCursor( &basetree::root.root, this ); }
1805
1806 /// Imports a cursor previously exported with #"TCursor Export".
1807 /// @param handle The handle value.
1808 /// @return The imported cursor value.
1809 Cursor ImportCursor( CursorHandle handle )
1810 { return Cursor( reinterpret_cast<typename basetree::Node*>(handle.value), this ); }
1811
1812 /// Imports a cursor previously exported with #"TCursor Export".
1813 /// @param handle The handle value.
1814 /// @return The imported \c const cursor value.
1815 ConstCursor ImportCursor( ConstCursorHandle handle) const
1816 { return ConstCursor( reinterpret_cast<typename basetree::Node*>(handle.value), this ); }
1817
1818 #if !DOXYGEN
1819 #if ALIB_DEBUG_CRITICAL_SECTIONS
1820 #undef DCS
1821 #undef DCSSHRD
1822 #endif
1823 #endif
1824
1825}; // StringTree
1826
1827} // namespace alib::[containers]
1828
1829/// Type alias in namespace \b alib.
1830template<typename TChar, integer TLocalCapacity= 32>
1831using StringTreeNamesDynamic = containers::StringTreeNamesDynamic<TChar, TLocalCapacity>;
1832
1833/// Type alias in namespace \b alib.
1834template<typename TChar>
1835using StringTreeNamesStatic = containers::StringTreeNamesStatic<TChar>;
1836
1837/// Type alias in namespace \b alib.
1838template<typename TChar>
1839using StringTreeNamesAlloc = containers::StringTreeNamesAlloc<TChar>;
1840
1841/// Type alias in namespace \b alib.
1842template<typename TAllocator,
1843 typename T,
1844 typename TNodeHandler = StringTreeNamesDynamic<character>,
1845 Recycling TRecycling = Recycling::Private >
1846using StringTree = containers::StringTree<TAllocator, T, TNodeHandler, TRecycling>;
1847
1848
1849} // namespace [alib]
ALIB_DLL
#define ALIB_DLL
Definition alib.inl:573
ALIB_WARNING
#define ALIB_WARNING(domain,...)
Definition alib.inl:1141
ALIB_ASSERT_WARNING
#define ALIB_ASSERT_WARNING(cond, domain,...)
Definition alib.inl:1145
ALIB_EXPORT
#define ALIB_EXPORT
Definition alib.inl:562
ALIB_DBG
#define ALIB_DBG(...)
Definition alib.inl:931
ALIB_ASSERT_ERROR
#define ALIB_ASSERT_ERROR(cond, domain,...)
Definition alib.inl:1144
alib::containers::StringTree::TCursor::GoTo
SubstringType GoTo(const NameType &path)
Definition stringtree.inl:1145
alib::containers::StringTree::TCursor::Distance
int Distance(const TCursor< true > &other) const
Definition stringtree.inl:1330
alib::containers::StringTree::TCursor::TCursor
TCursor(cmNode *pNode, cmTree *pTree) noexcept
Definition stringtree.inl:738
alib::containers::StringTree::TCursor::operator!=
bool operator!=(const TCursor &other) const
Definition stringtree.inl:809
alib::containers::StringTree::TCursor::operator()
std::pair< TCursor, SubstringType > operator()(const NameType &path) const
Definition stringtree.inl:1133
alib::containers::StringTree::TCursor::operator=
TCursor & operator=(const TCursor &) noexcept=default
alib::containers::StringTree::TCursor::GoToCreatedPathIfNotExistent
int GoToCreatedPathIfNotExistent(const NameType &path, TArgs &&... args)
Definition stringtree.inl:1192
alib::containers::StringTree::TCursor::CreateChild
TCursor CreateChild(const NameType &childName, TArgs &&... args) const
Definition stringtree.inl:1465
alib::containers::StringTree::TCursor::TStringTree
std::conditional_t<!TConst, StringTree, const StringTree > TStringTree
Definition stringtree.inl:761
alib::containers::StringTree::TCursor::AssemblePath
strings::TAString< typename cmTree::CharacterType, lang::HeapAllocator > & AssemblePath(strings::TAString< typename cmTree::CharacterType > &targetString, const TCursor< true > &parent, lang::CurrentData targetData=lang::CurrentData::Clear) const
Definition stringtree.inl:1425
alib::containers::StringTree::TCursor::DeleteChild
uinteger DeleteChild(TCursor &child) const
Definition stringtree.inl:1532
alib::containers::StringTree::TCursor::cmTree
std::conditional_t<!TConst, basetree, const basetree > cmTree
Definition stringtree.inl:724
alib::containers::StringTree::TCursor::Export
ConstCursorHandle Export() const
Definition stringtree.inl:828
alib::containers::StringTree::TCursor::cmNode
std::conditional_t<!TConst, baseNode, const baseNode > cmNode
Definition stringtree.inl:728
alib::containers::StringTree::TCursor::Child
TCursor Child(const NameType &name) const
Definition stringtree.inl:1007
alib::containers::StringTree::TCursor::GoToCreateChildIfNotExistent
bool GoToCreateChildIfNotExistent(const NameType &name, TArgs &&... args)
Definition stringtree.inl:1082
alib::containers::StringTree::TCursor::GoToChild
bool GoToChild(const NameType &name)
Definition stringtree.inl:1026
alib::containers::StringTree::TCursor::CreatePathIfNotExistent
std::pair< TCursor, integer > CreatePathIfNotExistent(const NameType &path, TArgs &&... args)
Definition stringtree.inl:1166
alib::containers::StringTree::TCursor::cmCursor
std::conditional_t<!TConst, baseCursor, baseConstCursor > cmCursor
Definition stringtree.inl:732
alib::containers::StringTree::TCursor::operator==
bool operator==(const TCursor &other) const
Definition stringtree.inl:800
alib::containers::StringTree::TCursor::CreateChildIfNotExistent
std::pair< TCursor, bool > CreateChildIfNotExistent(const NameType &name, TArgs &&... args)
Definition stringtree.inl:1055
alib::containers::StringTree::TCursor::operator=
TCursor & operator=(TCursor &&) noexcept=default
alib::containers::StringTree::TCursor::DeleteChild
bool DeleteChild(const NameType &childName) const
Definition stringtree.inl:1501
alib::containers::StringTree::TCursor::AssemblePath
strings::TAString< typename cmTree::CharacterType, lang::HeapAllocator > & AssemblePath(strings::TAString< typename cmTree::CharacterType > &targetString, lang::CurrentData targetData=lang::CurrentData::Clear) const
Definition stringtree.inl:1397
alib::containers::StringTree::ReserveRecyclables
void ReserveRecyclables(integer qty, lang::ValueReference reference)
Definition stringtree.inl:1781
alib::containers::StringTree::DbgGetDCS
lang::DbgCriticalSections & DbgGetDCS() const
Definition stringtree.inl:1652
alib::containers::StringTree::Separator
constexpr CharacterType Separator() const noexcept
Definition stringtree.inl:1657
alib::containers::StringTree::NodeTable
const auto & NodeTable() const
Definition stringtree.inl:1796
alib::containers::StringTree::ConstCursor
TCursor< true > ConstCursor
The constant version of type TCursor<TConst>.
Definition stringtree.inl:1581
alib::containers::StringTree< MonoAllocator, T, StringTreeNamesAlloc< character > >::CharacterType
typename StringTreeNamesAlloc< character >::CharacterType CharacterType
Definition stringtree.inl:595
alib::containers::StringTree::ImportCursor
Cursor ImportCursor(CursorHandle handle)
Definition stringtree.inl:1809
alib::containers::StringTree::Root
const ConstCursor Root() const
Definition stringtree.inl:1804
alib::containers::StringTree::createCursor
Cursor createCursor(baseNode &node)
Definition stringtree.inl:1588
alib::containers::StringTree::DbgSetDCSName
void DbgSetDCSName(const char *name) const
Definition stringtree.inl:1663
alib::containers::StringTree::GetAllocator
AllocatorType & GetAllocator() noexcept
Definition stringtree.inl:1643
alib::containers::StringTree::Cursor
TCursor< false > Cursor
The mutable version of type TCursor<TConst>.
Definition stringtree.inl:1578
alib::containers::StringTree::StringTree
StringTree(AllocatorType &allocator, CharacterType pathSeparator)
Definition stringtree.inl:1606
alib::containers::StringTree::StringTree
StringTree(CharacterType pathSeparator, TSharedRecycler &pRecycler)
Definition stringtree.inl:1618
alib::containers::StringTree::ConstructRootValue
void ConstructRootValue(TArgs &&... args)
Definition stringtree.inl:1680
alib::containers::StringTree::ImportCursor
ConstCursor ImportCursor(ConstCursorHandle handle) const
Definition stringtree.inl:1815
alib::strings::TString::CharAtStart
TChar CharAtStart() const
Definition string.inl:421
alib::containers::DBG_STATS_STRINGTREE_NAMES
uinteger DBG_STATS_STRINGTREE_NAMES
Definition stringtreebase.cpp:30
alib::containers::DBG_STATS_STRINGTREE_NAME_OVERFLOWS
uinteger DBG_STATS_STRINGTREE_NAME_OVERFLOWS
Definition stringtreebase.cpp:31
alib::lang::CurrentData::Clear
@ Clear
Chooses to clear existing data.
Definition commonenumdefs.inl:82
alib::lang::ValueReference
ValueReference
Denotes if a value is interpreted as an absolute or relative number.
Definition commonenumdefs.inl:208
alib::integer
lang::integer integer
Type alias in namespace alib.
Definition integers.inl:149
alib::StringTreeNamesStatic
containers::StringTreeNamesStatic< TChar > StringTreeNamesStatic
Type alias in namespace alib.
Definition stringtree.inl:1835
alib::Recycling
containers::Recycling Recycling
Type alias in namespace alib.
Definition recycling.inl:35
alib::StringTree
containers::StringTree< TAllocator, T, TNodeHandler, TRecycling > StringTree
Type alias in namespace alib.
Definition stringtree.inl:1846
alib::StringTreeNamesAlloc
containers::StringTreeNamesAlloc< TChar > StringTreeNamesAlloc
Type alias in namespace alib.
Definition stringtree.inl:1839
alib::uinteger
lang::uinteger uinteger
Type alias in namespace alib.
Definition integers.inl:152
alib::StringTreeNamesDynamic
containers::StringTreeNamesDynamic< TChar, TLocalCapacity > StringTreeNamesDynamic
Type alias in namespace alib.
Definition stringtree.inl:1831
alib::CHK
See sibling type #"NC".
Definition chk_nc.inl:33
alib::containers::StringTreeNamesAlloc::NameStringType
strings::TString< TChar > NameStringType
The string-type of a node's name.
Definition stringtree.inl:277
alib::containers::StringTreeNamesAlloc::FreeNode
static void FreeNode(typename TTree::baseNode &node, TTree &tree)
Definition stringtree.inl:320
alib::containers::StringTreeNamesAlloc::InitializeNode
static void InitializeNode(typename TTree::Node &node, TTree &tree)
Definition stringtree.inl:299
alib::containers::StringTreeNamesAlloc::CharacterType
TChar CharacterType
The character type that the StringTree uses for child name and path strings.
Definition stringtree.inl:274
alib::containers::StringTreeNamesDynamic::NameStringType
std::conditional_t<(TLocalCapacity > 0), strings::TLocalString< TChar, TLocalCapacity >, strings::TString< TChar > > NameStringType
The string-type of a node's name.
Definition stringtree.inl:104
alib::containers::StringTreeNamesDynamic::CharacterType
TChar CharacterType
The character type that the StringTree uses for child name and path strings.
Definition stringtree.inl:101
alib::containers::StringTreeNamesDynamic::InitializeNode
static void InitializeNode(typename TTree::Node &node, TTree &tree)
Definition stringtree.inl:124
alib::containers::StringTreeNamesDynamic::FreeNode
static void FreeNode(typename TTree::Node &node, TTree &tree)
Definition stringtree.inl:159
alib::containers::StringTreeNamesStatic::FreeNode
static void FreeNode(TTree::Node &node, TTree &tree)
Definition stringtree.inl:240
alib::containers::StringTreeNamesStatic::CharacterType
TChar CharacterType
The character type that the StringTree uses for child name and path strings.
Definition stringtree.inl:197
alib::containers::StringTreeNamesStatic::InitializeNode
static void InitializeNode(typename TTree::Node &node, TTree &tree)
Definition stringtree.inl:220
alib::containers::StringTreeNamesStatic::NameStringType
strings::TString< TChar > NameStringType
The string-type of a node's name.
Definition stringtree.inl:200
alib::containers::StringTree::ConstCursorHandle
A handle type used with methods #"TCursor::Export" and #"ImportCursor".
Definition stringtree.inl:648
alib::containers::StringTree::ConstCursorHandle::operator==
bool operator==(const CursorHandle &other) const noexcept
Definition stringtree.inl:673
alib::containers::StringTree::ConstCursorHandle::ConstCursorHandle
ConstCursorHandle(const CursorHandle &mutableHandle)
Definition stringtree.inl:660
alib::containers::StringTree::ConstCursorHandle::ConstCursorHandle
ConstCursorHandle()=default
Defaulted default constructor.
alib::containers::StringTree::ConstCursorHandle::value
uinteger value
The encapsulated value.
Definition stringtree.inl:649
alib::containers::StringTree::ConstCursorHandle::operator==
bool operator==(const ConstCursorHandle &other) const noexcept
Definition stringtree.inl:666
alib::containers::StringTree::CursorHandle::value
uinteger value
The encapsulated value.
Definition stringtree.inl:633
alib::containers::StringTree::CursorHandle::operator==
bool operator==(const CursorHandle &other) const noexcept
Definition stringtree.inl:639
alib::containers::detail::StringTreeBase::nodeTable
HashTable< TAllocator, typename NodeKey::ValueDescriptor, typename NodeKey::Hash, typename NodeKey::EqualTo, lang::Caching::Enabled, TRecycling > nodeTable
Definition stringtreebase.inl:441
alib::containers::detail::StringTreeBase::checkChildName
bool checkChildName(const NameType &name) const
Definition stringtreebase.inl:678
alib::lang::AllocatorMember::GetAllocator
TAllocator & GetAllocator() const noexcept
Definition allocation.inl:671