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