ALib C++ Library
Library Version: 2412 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/// \emoji :copyright: 2013-2024 A-Worx GmbH, Germany.
6/// Published under \ref mainpage_license "Boost Software License".
7//==================================================================================================
8#ifndef HPP_ALIB_MONOMEM_CONTAINERS_STRINGTREE
9#define HPP_ALIB_MONOMEM_CONTAINERS_STRINGTREE 1
10#pragma once
11#if !defined(DOXYGEN)
12# include "alib/alib.hpp"
13#endif
14ALIB_ASSERT_MODULE(STRINGS)
15
16#include "alib/containers/detail/stringtreebase.inl"
17#include <algorithm>
18
19namespace alib { namespace containers {
20
21#if ALIB_DEBUG
22 /// Statistic variable increased by \alib{containers;StringTreeNamesDynamic} with every creation
23 /// of a node. With process creation the variable is \c 0. A user may reset the variable to
24 /// inspect percentages of name overflows during certain operations. The variable is not thread
25 /// safe and used by any instance of class \b StringTree which uses node handler
26 /// \b StringTreeNamesDynamic.
27 /// @see Sibling variable \alib{containers;DBG_STATS_STRINGTREE_NAME_OVERFLOWS}
29
30 /// Statistic variable increased by \alib{containers;StringTreeNamesDynamic} with every creation
31 /// of a node whose name exceeds the internal string buffer size.
32 /// With process creation the variable is \c 0. A user may reset the variable to
33 /// inspect percentages of name overflows during certain operations. The variable is not thread
34 /// safe and used by any instance of class \b StringTree which uses node handler
35 /// \b StringTreeNamesDynamic.
36 /// @see Sibling variable \alib{containers;DBG_STATS_STRINGTREE_NAME_OVERFLOWS}
38#endif
39
40/// This struct is the default type for template parameter
41/// \ref alib_ns_containers_stringtree_referencedoc "TNodeHandler" of class
42/// \alib{containers;StringTree}.
43///
44/// Besides defining the character type as given with template parameter \p{TChar}, the node name
45/// string-type is exposed with #NameStringType. The string-type depends on the template parameter
46/// \p{TLocalCapacity}:
47/// - If this is \c 0, the type evaluates to a simple string with no internal storage.
48/// - If this is greater than zero, the type evaluates to a \alib{strings;TLocalString;LocalString}
49/// of given capacity.
50///
51/// This design allows allocating a fixed-size string buffer with each node, and only if a
52/// node's name exceeds this capacity, a dynamic allocation for storing the node name is performed.
53/// As a consequence, some overhead of wasted memory will occur, as this capacity is
54/// allocated with every node, regardless of its name's length.
55/// To investigate into the percentage of overflows to evaluate a reasonable value for template
56/// parameter \p{TLocalCapacity}, simple global debug counters
57/// \alib{containers;DBG_STATS_STRINGTREE_NAMES} and \alib{containers;DBG_STATS_STRINGTREE_NAME_OVERFLOWS}
58/// can be used.
59///
60/// Method #InitializeNode is invoked after insertion of a new element (aka "node")
61/// into the container and #FreeNode is invoked before the destruction of a node.
62/// When #InitializeNode is invoked, the custom object of template type \p{T} (of the \b StringTree)
63/// is already default constructed and the key of the node in union
64/// (field \alib{containers;detail::StringTreeBase::NodeKey::name}) is set to what was provided
65/// as a child name or path string. (In the latter case, it is set to a substring of the
66/// given path.). If template parameter \p{TLocalCapacity} is greater than 0, the
67/// method copies the key to field \e storage of the union (which is still accessible with the
68/// base string-type of union-field \e key).
69/// If \c 0 is given, the node name is replaced by a copy of the string which is dynamically
70/// allocated.
71///
72/// ## Custom Implementations ##
73/// A custom implementation has to provide all four entities that this type provides in a
74/// compatible fashion.
75///
76/// The main purpose of the node handler types is to ensure that the name strings of inserted
77/// nodes are duly allocated, copied and freed as needed:
78/// When a new element is (or a whole path of new elements are) created, then the initial name
79/// of the nodes are taken from the string passed to the corresponding interface method of class
80/// \b StringTree (and inner types). The challenge is that these string's life-cycle might
81/// be only short term. Therefore, right after the creation of an element, method #InitializeNode
82/// is invoked, allowing to create a safe copy of the name.<br>
83/// To free any allocated space, method #FreeNode is invoked.
84///
85/// Besides this, custom implementation may tweak the given node on their own discretion.
86/// Especially a custom implementation may create and recycle other portions of the stored
87/// objects, to establish \ref alib_contmono_intro_strictweak "weak monotonic allocation rules".
88/// A sample of such more complex behavior is found with \alib type \alib{files;FTree}.
89///
90/// \see
91/// Two other built-in implementations of this type to be used with \b StringTree instantiations
92/// are provided with this \alibmod:
93/// - \alib{containers;StringTreeNamesStatic}.
94/// - \alib{containers;StringTreeNamesAlloc}.
95/// \see
96/// Further information can be found in chapter
97/// \ref alib_ns_containers_stringtree_alloc_names "4. Node and Node Name String Allocation"
98/// of the reference documentation of class \b StringTree.
99///
100/// @tparam TChar The character type of the key strings. This type is used with any
101/// interface method of \alib{containers;StringTree} that accepts a node name
102/// or path string.<br>
103/// Defaults to type \alib{characters;character}.
104/// @tparam TLocalCapacity The capacity of the \alib{strings;TLocalString;LocalString} to place in
105/// the <b>StringTree</b>'s node. If \c 0 is given, a normal
106/// \alib{strings;TString;String} is used for the name, and the buffer is
107/// copied to an dynamically allocated array.<br>
108/// Defaults to \c 32.
109template<typename TChar= character, integer TLocalCapacity= 32>
111{
112 /// The character type that the \b StringTree uses for child name and path strings.
113 using CharacterType = TChar;
114
115 /// The string-type of a node's name.
116 using NameStringType = ATMP_IF_T_F ( (TLocalCapacity > 0),
118 ALIB_COMMA TLocalCapacity
120 strings::TString <TChar> );
121
122
123 /// This implementation copies the node's name to a dynamically allocated piece of heap memory.
124 /// \see
125 /// See class description for further information.
126 /// @param tree The instance of struct \alib{containers;detail::StringTreeBase} that invokes
127 /// this method. Any member may be accessed, including
128 /// \alib{containers::detail::StringTreeBase;nodeTable} which contains the
129 /// allocator that the tree uses for the allocation of nodes.
130 /// @param node The node that was just created. Allows access to the key and
131 /// custom value data. While the parent and sibling nodes are likewise accessible,
132 /// it is strictly forbidden to modify those.
133 /// @tparam TTree The type of the templated instantiation of struct
134 /// \alib{containers;detail::StringTreeBase} that this method is invoked by.
135 /// (Deduced by the compiler.)
136 template<typename TTree>
137 static
138 void InitializeNode( TTree& tree, typename TTree::Node& node )
139 {
140 (void) tree;
141
142 // if not a local string buffer, then dynamically allocate and copy.
143 if constexpr (TLocalCapacity <= 0)
144 {
145 CharacterType* buffer= new CharacterType[size_t(node.name.key.Length())];
146 node.name.key.CopyTo( buffer );
147 node.name.key= strings::TString<CharacterType>( buffer, node.name.key.Length() );
148 }
149 else
150 {
151 // create a local string which may allocate heap if name is too long
152 strings::TString<TChar> key= node.name.key; // get current pointer
153 new (&node.name.storage) NameStringType(); // placement-new to re-establish local string
154 node.name.storage.DbgDisableBufferReplacementWarning(); // Disable warnings
155 ALIB_DBG( const TChar* internalBuffer= node.name.storage.Buffer(); ) // get internal local buffer
156 node.name.storage.Append(key); // copy key to buf
158 if( internalBuffer != node.name.storage.Buffer() ) // ++statistics if local buffer was too small
160 }
161 }
162
163 /// This implementation frees the dynamically allocated memory of the node's name.
164 /// \see
165 /// See class description for further information.
166 /// @param tree The instance of struct \alib{containers;detail::StringTreeBase} that invokes
167 /// this method. Any member may be accessed, including
168 /// \alib{containers::detail::StringTreeBase;nodeTable} which contains the
169 /// allocator that the tree uses for the allocation of nodes.
170 /// @param node The node that is to be removed. Allows access to the key and
171 /// custom value data. While the parent and sibling nodes are likewise accessible,
172 /// it is strictly forbidden to modify those.
173 /// @tparam TTree The type of the templated instantiation of struct
174 /// \alib{containers;detail::StringTreeBase} that this method is invoked by.
175 /// (Deduced by the compiler.)
176 template<typename TTree>
177 static
178 void FreeNode( TTree& tree, typename TTree::Node& node )
179 {
180 (void) tree;
181 if constexpr (TLocalCapacity <= 0)
182 delete[] node.name.key.Buffer();
183 else
184 node.name.storage.~TLocalString();
185 }
186
187}; // StringTreeNamesDynamic
188
189/// Built-in implementation usable as template parameter
190/// \ref alib_ns_containers_stringtree_referencedoc "TNodeHandler" of class
191/// \alib{containers;StringTree}.
192///
193/// This type does not allocate memory and does not copy the key string of a node. Therefore, this
194/// type is very efficient to use in situations where exclusively "static" strings for child names
195/// and paths are passed to the interface methods of class \b StringTree (and inner types) which lead
196/// to the creation of new child nodes.<br>
197/// The term "static" here means that the strings given are either static character data of a
198/// compilation unit or by any other means their allocated memory and the contained data survive
199/// the life-cycle of the corresponding \b StringTree.
200///
201/// \see
202/// Two other built-in implementations of this type to be used with \b StringTree instantiations
203/// are provided with this \alibmod:
204/// - \alib{containers;StringTreeNamesDynamic}.
205/// - \alib{containers;StringTreeNamesAlloc}.
206/// \see
207/// Further information can be found in chapter
208/// \ref alib_ns_containers_stringtree_alloc_names "4. Node and Node Name String Allocation"
209/// of the reference documentation of class \b StringTree.
210///
211/// @tparam TChar The character type of the key strings. This type is used with any
212/// interface method of \alib{containers;StringTree} that accepts a node name or path
213/// string.
214template<typename TChar= character>
216{
217 /// The character type that the \b StringTree uses for child name and path strings.
218 using CharacterType = TChar;
219
220 /// The string-type of a node's name.
222
223 /// This implementation is empty.
224 ///
225 /// \see
226 /// See description of this class and the "default implementation"
227 /// \alib{containers;StringTreeNamesDynamic}.
228 ///
229 /// @param tree The instance of struct \alib{containers;detail::StringTreeBase} that invokes
230 /// this method. Any member may be accessed, including
231 /// \alib{containers::detail::StringTreeBase;nodeTable} which contains the
232 /// allocator that the tree uses for the allocation of nodes.
233 /// @param node The node that was just created. Allows access to the key and
234 /// custom value data. While the parent and sibling nodes are likewise accessible,
235 /// it is strictly forbidden to modify those.
236 /// @tparam TTree The type of the templated instantiation of struct
237 /// \alib{containers;detail::StringTreeBase} that this method is invoked by.
238 /// (Deduced by the compiler.)
239 template<typename TTree>
240 static
241 void InitializeNode( TTree& tree, typename TTree::Node& node )
242 {
243 (void) tree;
244 (void) node;
245 }
246
247 /// This implementation is empty.
248 ///
249 /// \see
250 /// See description of this class and the "default implementation"
251 /// \alib{containers;StringTreeNamesDynamic}.
252 ///
253 /// @param tree The instance of struct \alib{containers;detail::StringTreeBase} that invokes
254 /// this method. Any member may be accessed, including
255 /// \alib{containers::detail::StringTreeBase;nodeTable} which contains the
256 /// allocator that the tree uses for the allocation of nodes.
257 /// @param node The node that is to be removed. Allows access to the key and
258 /// custom value data. While the parent and sibling nodes are likewise accessible,
259 /// it is strictly forbidden to modify those.
260 /// @tparam TTree The type of the templated instantiation of struct
261 /// \alib{containers;detail::StringTreeBase} that this method is invoked by.
262 /// (Deduced by the compiler.)
263 template<typename TTree>
264 static
265 void FreeNode( TTree& tree, typename TTree::Node& node )
266 { (void) tree; (void) node; }
267}; // StringTreeNamesStatic
268
269/// Built-in implementation usable as template parameter
270/// \ref alib_ns_containers_stringtree_referencedoc "TNodeHandler" of class
271/// \alib{containers;StringTree}.
272///
273/// This type copies the node's name into memory acquired with the monotonic allocator that the
274/// \b StringTree uses.<br>
275///
276/// \attention
277/// The use of this type is dangerous in respect to memory exhaustion. While class
278/// \b StringTree uses monotonic allocation in a
279/// \ref alib_ns_containers_stringtree_hashing "very safe way", with the use of this
280/// type, repeated removals and insertions of tree nodes, increase the memory usage.<br>
281/// Consequently, the use of this type is restricted to cases that imply a limited
282/// number of insertions.
283///
284/// \see
285/// Two other built-in implementations of this type to be used with \b StringTree instantiations
286/// are provided with this \alibmod:
287/// - \alib{containers;StringTreeNamesStatic}.
288/// - \alib{containers;StringTreeNamesDynamic}.
289/// \see
290/// Further information can be found in chapter
291/// \ref alib_ns_containers_stringtree_alloc_names "4. Node and Node Name String Allocation"
292/// of the reference documentation of class \b StringTree.
293///
294/// @tparam TChar The character type of the key strings. This type is used with any
295/// interface method of \alib{containers;StringTree} that accepts a node name or path
296/// string.
297template<typename TChar= character>
299{
300 /// The character type that the \b StringTree uses for child name and path strings.
301 using CharacterType= TChar;
302
303 /// The string-type of a node's name.
305
306 /// This implementation copies the node's name to a piece of memory allocated in the
307 /// allocator found in field \alib{containers::detail::StringTreeBase;nodeTable}
308 /// of the given \p{tree}.
309 ///
310 /// \see
311 /// See description of this class and the "default implementation"
312 /// \alib{containers;StringTreeNamesDynamic}.
313 ///
314 /// @param tree The instance of struct \alib{containers;detail::StringTreeBase} that invokes
315 /// this method. Any member may be accessed, including
316 /// \alib{containers::detail::StringTreeBase;nodeTable} which contains the
317 /// allocator that the tree uses for the allocation of nodes.
318 /// @param node The node that was just created. Allows access to the key and
319 /// custom value data. While the parent and sibling nodes are likewise accessible,
320 /// it is strictly forbidden to modify those.
321 /// @tparam TTree The type of the templated instantiation of struct
322 /// \alib{containers;detail::StringTreeBase} that this method is invoked by.
323 /// (Deduced by the compiler.)
324 template<typename TTree>
325 static
326 void InitializeNode( TTree& tree, typename TTree::Node& node )
327 {
328 node.name.storage.Allocate( tree.nodeTable.GetAllocator(), node.name.key );
329 }
330
331 /// This implementation does nothing.
332 ///
333 /// \see
334 /// See description of this class and the "default implementation"
335 /// \alib{containers;StringTreeNamesDynamic}.
336 ///
337 /// @param tree The instance of struct \alib{containers;detail::StringTreeBase} that invokes
338 /// this method. Any member may be accessed, including
339 /// \alib{containers::detail::StringTreeBase;nodeTable} which contains the
340 /// allocator that the tree uses for the allocation of nodes.
341 /// @param node The node that is to be removed. Allows access to the key and
342 /// custom value data. While the parent and sibling nodes are likewise accessible,
343 /// it is strictly forbidden to modify those.
344 /// @tparam TTree The type of the templated instantiation of struct
345 /// \alib{containers;detail::StringTreeBase} that this method is invoked by.
346 /// (Deduced by the compiler.)
347 template<typename TTree>
348 static
349 void FreeNode( TTree& tree, typename TTree::baseNode& node ) { (void) tree; (void) node; }
350};
351
352//==================================================================================================
353/// # 1. Introduction # {#alib_ns_containers_stringtree_overview}
354/// This container type implements a directed, non-circular graph (tree) with named nodes.
355///
356/// The internal node type \alib{containers;detail::StringTreeBase::Node} stores:
357/// 1. A name string, which has to be unique in respect to the names of sibling nodes. (Just like
358/// no two files in a folder may have the same name.)
359/// 2. Five pointers to related nodes:
360/// - the parent node
361/// - the previous and next sibling nodes,
362/// - the first and last child nodes,
363/// 3. A data field holding the node's custom value of template type \p{T}.
364///
365/// The way from the root node to a descendent node, usually is called "path". The class incorporates
366/// functionality to work with string representations of such paths where names of child nodes are
367/// concatenated and separated by a special separation character.
368///
369/// The search and creation of tree nodes by using aforementioned path strings, is very similar to
370/// what is well known from addressing files and folders in file systems.
371/// This class does not differentiate between 'folders' and 'files', hence between 'nodes' and
372/// 'leafs'. Every node has the same data of type \p{T} attached and may or may not have child nodes.
373/// If such differentiation - or other semantics - is wanted, this may well be modeled by custom
374/// attributes provided in template type \p{T}.
375///
376/// \I{#############################################################################################}
377/// # 2. Inner Types # {#alib_ns_containers_stringtree_inner}
378/// Two public inner types exist.
379/// All operations on tree nodes like insertion, deletion, search and attribute access is performed
380/// using objects of public type \alib{containers;StringTree::TCursor}. This is a lightweight,
381/// iterator-like "handle" containing a pointer to the originating tree object and to a represented
382/// node. The type provides various methods to travers the tree. It is templated over a boolean
383/// value which determines if a const or mutable \b StringTree is given. Shortcuts for these
384/// types are \alib{containers;StringTree::Cursor} and \alib{containers;StringTree::ConstCursor}.
385///
386/// Besides this, class \alib{containers;StringTree::RecursiveIterator} allows recursive
387/// iterations with built-in or custom sort orders.
388///
389/// Both types are explained in the following paragraphs.
390///
391/// \I{#############################################################################################}
392/// ## 2.1 Inner Class Cursor ## {#alib_ns_containers_stringtree_cursor}
393///
394/// The main interface into class \b %StringTree is given by public, inner type
395/// \alib{containers;StringTree::Cursor}. Method #Root returns an object of that type that
396/// initially refers to the root node of the tree.
397/// With this, child names and composite "paths" can be used to move the pointer along existing nodes
398/// of the tree or to create new child nodes or even a whole path of such child nodes at once.
399///
400/// Class \b %Cursor is very lightweight as it contains just two pointers, one to the
401/// \b %StringTree it originates from and one to the tree node currently represented.
402/// Hence, objects of this type can be copied, assigned and passed around very efficiently.<br>
403/// The currently represented node's templated custom data can be accessed with method
404/// #TCursor::Value.
405///
406/// The methods to traverse over the nodes of the tree are:
407/// - #TCursor::GoToRoot
408/// - #TCursor::GoToParent
409/// - #TCursor::GoTo
410/// - #TCursor::GoToNextSibling
411/// - #TCursor::GoToPreviousSibling
412/// - #TCursor::GoToChild
413/// - #TCursor::GoToFirstChild
414/// - #TCursor::GoToLastChild
415///
416/// With these methods, class \b StringTree::Cursor constitutes a sort of iterator idiom
417/// idiom. For example to traverse all entries in the root folder, the following schematic would
418/// be used:
419///
420/// myCursor= myTree.GetRoot()
421/// myCursor.GotoFirstChild()
422/// While( myCursor.IsValid() )
423/// DoSomething( myCursor.Value() )
424/// myCursor.GotoNextSibling
425///
426/// For some of these methods an alternative version exists, which returns a corresponding copy
427/// of the cursor, while leaving the original object unchanged. These methods share
428/// the same name excluding the prefix <b>GoTo</b>.
429///
430/// For the creation of new child nodes or a complete path of such, methods
431/// - #TCursor::GoToCreateChildIfNotExistent and ,
432/// - #TCursor::GoToCreatedPathIfNotExistent
433/// are provided.
434///
435/// Next, four methods that perform node deletion exist:
436/// - #TCursor::DeleteChild (two overloaded versions),
437/// - #TCursor::DeleteChildren and
438/// - #TCursor::Delete
439///
440/// The already mentioned methods:
441/// - #TCursor::GoToParent,
442/// - #TCursor::GoToFirstChild,
443/// - #TCursor::GoToLastChild,
444/// - #TCursor::GoToNextSibling and
445/// - #TCursor::GoToPreviousSibling
446///
447/// of class \b Cursor can be used to iterate from a node upward to the root node or through the
448/// list of children of a node. Each method may \e invalidate the object in the case that no
449/// corresponding parent or sibling node exists.
450/// Invalid cursor objects can be (or rather have to be!) detected using method
451/// #TCursor::IsValid.
452/// Most of the class's methods must not be invoked on an invalidated object. Doing so is undefined
453/// behavior and raises an \alib assertion in debug-builds.
454/// Invalid \b %Cursor objects can reset to a valid state using methods
455/// - #TCursor::GoToRoot and
456/// - #TCursor::GoTo
457///
458/// if absolute path addressing is used.
459///
460/// Instances that have been default-constructed may only be set to a valid state by (copy-)
461/// assigning a valid instance.
462///
463/// \I{#############################################################################################}
464/// ## 2.2. Inner Class RecursiveIterator ## {#alib_ns_containers_stringtree_iterator}
465/// Class \alib{containers;StringTree::RecursiveIterator} provides a configurable and controlled
466/// way of iterating a branch of a tree. Some features of the class are:
467/// - Iterators can be initialized to start from any node of the tree
468/// Iteration ends when all (recursive) child nodes of the start node have been visited.
469/// - The iteration follows a "depth first search" approach: Before visiting a sibling node,
470/// all children of a node are visited. However, it is not differentiated whether a sibling
471/// has child nodes or not. In case all siblings with children are to be processed first,
472/// a custom sorter has to be created which prefers those nodes that have children.
473/// - The recursion depth can be limited, including to depth \c 0, which iterates only the
474/// direct child nodes of the start node.
475/// - Before entering a new depth-level during iteration, different sort orders can be set.
476/// The choices are:
477/// - No sorting (iterates in order of node insertion).
478/// - Built-in sorting by node (path) name, ascending/descending, case-sensitive or ignoring case
479/// - user-defined by path name, number of children or any other attribute of the node, of course
480/// including a node's custom data values.
481///
482/// Class \b RecursiveIterator is of rather heavy weight and sorted iteration needs to allocate
483/// memory for sorting the child nodes for each depth level of a potential recursion.
484/// Therefore it is recommended to reuse instances of the class with subsequent, similar iterations.
485/// In addition this explains why this class does not follow the concept of
486/// <c>std::iterator_traits</c>, which is designed to be used with lightweight iterator types.
487///
488/// \I{#############################################################################################}
489/// # 3. Node Allocation And Hashing # {#alib_ns_containers_stringtree_hashing}
490/// While each node maintains a doubly linked list of child nodes for iteration, this class stores
491/// each inserted element in a \alib{containers;HashTable} using the parent node and the
492/// element's name as a unique key.
493/// This is done to be able to search for a child with a given name in constant time.
494/// This container does not perform any other memory allocations than those that this
495/// \b HashTable does.
496///
497/// With that, the implementation of this container type is able to leave all allocation and
498/// <em>"recycling"</em> of node elements to this hash table, which is found in base class's field
499/// \alib{containers;detail::StringTreeBase::nodeTable}. As explained in the documentation of
500/// \alib{containers;HashTable}, its allocation mechanism can be made safe in respect to
501/// memory exhaustion. This is true even if a \alib{MonoAllocator} is used and a virtually
502/// unlimited number of insertions and removals of elements is performed.
503/// Such safeness depends on template parameter \p{TRecycling} which is just passed to the
504/// internal hash table's definition of nodes.
505/// \see
506/// For more information on this topic see also chapter \ref alib_contmono_intro_recycling
507/// of this \alibmod_nl Programmer's Manual.
508///
509/// \I{#############################################################################################}
510/// # 4. Node and Node Name String Allocation # {#alib_ns_containers_stringtree_alloc_names}
511///
512/// The C++ version of this class allows user-defined allocation (and copying) of the node's name
513/// character strings. For this, a template parameter \p{TNodeHandler} is defined,
514/// which defaults to built-in struct \alib{containers;StringTreeNamesDynamic}.
515/// This default "node handler" defines the name type of nodes to \alib{strings;TLocalString;LocalString}
516/// with a default capacity of \c 32 characters.
517/// This way, this local string performs dynamic allocation automatically when a node is
518/// constructed.<br>
519/// In the case that many "long" node names are expected, it might be efficient to set the capacity
520/// to \c 0. In this case, type \b StringTreeNamesDynamic defines the string-type to a normal
521/// \b String and uses C++ keywords <c>new</c> and <c>delete[]</c> to allocate
522/// and free character buffers for the name string.
523///
524/// A second built-in and ready-to-use "node handler" type is given with
525/// \alib{containers;StringTreeNamesStatic}. This uses an unbuffered \b String and has empty
526/// implementations of its static methods. This way no copies of the original string buffers that
527/// are passed to the to interface methods of class \b Cursor that create children are made.
528/// This is useful (and very efficient!) if \b all child name and creation path strings provided
529/// of class \b %Cursor are permanently valid, or, in other words, their life-cycle spans over
530/// the life-cycle of the nodes in a tree. Then, the names do not need to be copied to dedicated
531/// allocated memory.
532///
533/// Finally, string trees that during their lifetime just grow and where no nodes (or only a limited
534/// number of nodes) are removed until the whole tree is disposed may be instantiated using
535/// the third built-in type \alib{containers;StringTreeNamesAlloc}.
536/// With that, the concept of \ref alib_contmono_intro "monotonic allocation" that this container
537/// type might use can be extended to the node name strings.
538/// Type \b StringTreeNamesAlloc grabs the allocator from the tree provided with method
539/// \alib{containers::StringTreeNamesAlloc;InitializeNode} and just clones the given
540/// string into this.
541///
542/// \I{#############################################################################################}
543/// # 5. Equipping the Root Node with Values # {#alib_ns_containers_stringtree_rootnodevalues}
544/// It depends on the field of application, whether the root node should dispose over an instance
545/// of custom type \p{T} or not.
546/// For example a tree of depth \c 1, which could be implemented using type
547/// <c>std::vector<T></c>, no stored type \p{T} can be be attached to the vector object itself, only
548/// to its "children".<br>
549/// Nevertheless, in many use cases, the root node naturally contains the same data as any other
550/// node in the tree. Therefore, if this class would not support root node data, using
551/// code would for example have to check a \alib{containers::StringTree;TCursor;Cursor} for pointing
552/// to the root node and in this case get the custom data from somewhere else.<br>
553/// On the other hand, if this class would "insist" in the provision of root node values, then already
554/// with construction of the tree, arguments for the construction of the associated \p{T} object
555/// would have to be provided - even if the root node value was never used.
556/// The provision of initial "dummy" root data, is sometimes not even (easily) possible, and would
557/// sometimes add the need to adjust the custom stored type \p{T} to fit into this class.
558/// (In fact, with former versions of \alib, root-node initialization data was mandatory to provide
559/// already with the construction of the tree.)
560///
561/// Therefore, this class makes the use of root node values optional. After construction of a
562/// \b StringTree, methods \alib{containers::StringTree;ConstructRootValue} and
563/// methods \alib{containers::StringTree;DestructRootValue} may be used to initialize and
564/// destruct the optional root nodes' data.
565///
566/// To prevent memory leaks, in debug-compilations, the following \alib assertions and warnings are
567/// raised:
568/// - \alib{containers::StringTree;TCursor::Value;Cursor::Value} will raise an assertion if
569/// called on the root node without having set a value.
570/// - \alib{containers::StringTree;ConstructRootValue} will raise a warning if called twice
571/// without a prior call to \alib{containers::StringTree;DestructRootValue}.
572/// - \alib{containers::StringTree;DestructRootValue} will raise a warning if called without
573/// a prior call to \alib{containers::StringTree;ConstructRootValue}.
574/// - The destructor of this class will raise a warning if a root value was set but not deleted.
575///
576/// \I{#############################################################################################}
577/// # Reference Documentation # {#alib_ns_containers_stringtree_referencedoc}
578///
579/// @tparam TAllocator The allocator type to use, as prototyped with \alib{lang;Allocator}.
580/// @tparam T The custom type of elements stored in this container.
581/// @tparam TNodeHandler
582/// A template type that needs to provide an interface as documented with
583/// \alib{containers;StringTreeNamesDynamic}, which is also the default type
584/// if not specified. For details see
585/// \ref alib_ns_containers_stringtree_alloc_names "corresponding section" of this
586/// class's documentation.
587/// The type is published as \alib{containers;StringTree::HandlerType}.
588/// @tparam TRecycling Denotes the type of recycling that is to be performed.
589/// Possible values are
590/// \alib{containers;Recycling;None},
591/// \alib{containers;Recycling;Private} (the default), or
592/// \alib{containers;Recycling;Shared}.
593//==================================================================================================
594template<typename TAllocator,
595 typename T,
596 typename TNodeHandler= StringTreeNamesDynamic<character>,
597 Recycling TRecycling = Recycling::Private>
598class StringTree : protected detail::StringTreeBase<TAllocator,T,TNodeHandler,TRecycling>
599{
600 #if !DOXYGEN
601 protected:
602 friend class Cursor;
603
604 friend class ConstCursor;
605
606 friend TNodeHandler;
607
609 using baseNodeKey = typename basetree::NodeKey;
610 using baseNodeBase = typename basetree::NodeBase;
611 using baseNode = typename basetree::Node;
612 using baseCursor = typename basetree::CursorBase;
613 using baseConstCursor = typename basetree::ConstCursorBase;
614 #endif
615
616 public:
617 /// Type definition publishing template parameter \p{TAllocator}.
618 using AllocatorType = TAllocator;
619
620 /// The character type of node names and paths strings. This is defined using character type
621 /// definition \alib{containers::StringTreeNamesDynamic;CharacterType} of template
622 /// type \p{TNodeHandler}.
623 using CharacterType = typename TNodeHandler::CharacterType;
624
625 /// The string-type of node names and paths. This is defined using character type definition
626 /// \alib{containers::StringTreeNamesDynamic;CharacterType} of template type
627 /// \p{TNodeHandler}.
629
630 /// The substring-type of paths. This is defined using character type definition
631 /// \alib{containers::StringTreeNamesDynamic;CharacterType} of template type
632 /// \p{TNodeHandler}.
634
635 /// Type definition publishing template parameter \p{TNodeHandler}.
636 using HandlerType = TNodeHandler;
637
638 /// This type definition may be used to define an externally managed shared recycler,
639 /// which can be passed to the alternative constructor of this class when template
640 /// parameter \p{TRecycling} equals \alib{containers;Recycling;Shared}.
641 /// \see
642 /// Chapter \ref alib_contmono_containers_recycling_shared of the Programmer's Manual
643 /// for this \alibmod.
644 using SharedRecyclerType= typename basetree::SharedRecyclerType;
645
646
647 /// A handle type used with methods #TCursor::Export and #ImportCursor.
649 {
650 uinteger value; ///< The encapsulated value.
651
652 /// Comparison operator.
653 /// @param other The cursor handle to compare this handle to.
654 /// @return \c true if both handles refer to the same cursor or if both handles are
655 /// invalid. \c false otherwise.
656 bool operator==(const CursorHandle& other) const noexcept { return value==other.value; }
657
658 /// Checks if this is a valid handle.
659 /// @return \c true if this handle is not nulled.
660 bool IsValid() const noexcept { return value != 0; }
661 };
662
663 /// A handle type used with methods #TCursor::Export and #ImportCursor.
665 {
666 uinteger value; ///< The encapsulated value.
667
668 /// Comparison operator.
669 /// @param other The cursor handle to compare this handle to.
670 /// @return \c true if both handles refer to the same cursor or if both handles are
671 /// invalid. \c false otherwise.
672 bool operator==(const ConstCursorHandle& other) const noexcept
673 { return value==other.value; }
674
675 /// Comparison operator.
676 /// @param other The cursor handle to compare this handle to.
677 /// @return \c true if both handles refer to the same cursor or if both handles are
678 /// invalid. \c false otherwise.
679 bool operator==(const CursorHandle& other) const noexcept
680 { return value==other.value; }
681
682 /// Checks if this is a valid handle.
683 /// @return \c true if this handle is not nulled.
684 bool IsValid() const noexcept { return value != 0; }
685 };
686
687 //==========================================================================================
688 /// This public, inner class provides the main interface into outer class \b StringTree.
689 /// The class should be considered being similar to a simple pointer or to a lightweight
690 /// iterator type, which refers to a tree and a current node.<br>
691 /// The class's interface allows the access to a node's name and value and to insert and
692 /// remove child nodes.
693 ///
694 /// Instances of this class can be received with methods #Root and #RecursiveIterator::Node.
695 ///
696 /// The default constructor creates an invalid object, which has to be initialized by
697 /// assigning a valid object before its first use.
698 ///
699 /// \see
700 /// For more information on how this class is used, see paragraph
701 /// \ref alib_ns_containers_stringtree_cursor "2.1 Inner Class Cursor"
702 /// of the description of class \b %StringTree.
703 ///
704 /// @tparam TConst If true, internal fields representing the StringTree and the current Node
705 /// become \c const and methods which are not declared \c const become
706 /// unavailable.
707 ///
708 /// ## Friends ##
709 /// class \alib{containers;StringTree}
710 //==========================================================================================
711 template<bool TConst>
712 class TCursor : protected basetree::template TCursorBase<TConst>
713 {
714 #if !DOXYGEN
715 friend class StringTree;
716 #endif
717
718 #if !DOXYGEN
719 #if ALIB_DEBUG_CRITICAL_SECTIONS
720 #define DCS ALIB_DCS_WITH(cmCursor::tree->nodeTable.dcs)
721 #define DCSSHRD ALIB_DCS_SHARED_WITH(cmCursor::tree->nodeTable.dcs)
722 #else
723 #define DCS
724 #define DCSSHRD
725 #endif
726 #endif
727
728 protected:
729 /// Constant or mutable version of the base tree type, depending on template parameter
730 /// \p{TConst}
731 using cmTree = ATMP_IF_T_F(!TConst, basetree, const basetree);
732
733 /// Constant or mutable version of the base node type, depending on template parameter
734 /// \p{TConst}
735 using cmNode = ATMP_IF_T_F(!TConst, baseNode, const baseNode);
736
737 /// Constant or mutable version of the base cursor type, depending on template parameter
738 /// \p{TConst}
739 using cmCursor = ATMP_IF_T_F(!TConst, baseCursor, baseConstCursor);
740
741 //#### Protected methods (class Cursor) ##############################################
742
743 /// Internal constructor
744 /// @param pTree The \b %StringTree we work on.
745 /// @param pNode The node to refer to.
746 TCursor(cmTree *pTree, cmNode *pNode) noexcept
747 : basetree::template TCursorBase<TConst>(pTree, pNode) {}
748
749 /// Checks if this cursor is associated with a tree.
750 /// Empty and optimized out with release-builds.
751 void dbgCheckTree() const
752 {
753 ALIB_ASSERT_ERROR(cmCursor::tree != nullptr, "MONOMEM/STRINGTREE",
754 "Invalid StringTree::Cursor: No binding with a StringTree. "
755 "(Probably default-constructed.)")
756 }
757
758 /// Checks if this cursor is associated with a tree and a valid node of the tree.
759 /// Empty and optimized out with release-builds.
761 {
762 dbgCheckTree();
763 ALIB_ASSERT_ERROR( cmCursor::node != nullptr, "MONOMEM/STRINGTREE",
764 "Invalid StringTree::Cursor not representing a node of the assigned tree." )
765 }
766
767 //#### Constructor, comparison operators, etc #####################################
768 public:
769 /// Constant or mutable version of the outer string tree type, depending on template
770 /// parameter \p{TConst}
772
773
774 /// Public constructor. Creates an invalid cursor.
775 /// The only way to make a default-constructed instance valid is by
776 /// (copy-) assigning another instance.
777 TCursor() noexcept = default;
778
779 /// Copy constructor.
780 /// @param src The cursor to copy.
781 TCursor( const TCursor& src) noexcept
782 : TCursor{ src.tree, src.node }
783 {}
784
785 /// Move constructor.
786 /// @param src The cursor to move.
787 TCursor( TCursor&& src) noexcept
788 : TCursor{ src.tree, src.node }
789 {}
790
791 /// Trivial default copy assign operator.
792 /// @return A reference to \c this.
793 TCursor &operator=(const TCursor &) noexcept = default;
794
795 /// Trivial default move assign operator.
796 /// @return A reference to \c this.
797 TCursor &operator=(TCursor &&) noexcept = default;
798
799 /// Trivial default destructor.
800 ~TCursor() noexcept = default;
801
802 /// Conversion operator from <em>TCursor<TConst></em> to <em>TCursor<!TConst></em>.
803 /// For const to mutable, this will fail as intended.
804 /// @return A constant iterator, if this is a mutable. Otherwise compilation will
805 /// duly fail.
806 operator TCursor<!TConst>() { return TCursor<!TConst>(cmCursor::tree, cmCursor::node); }
807
808 /// Comparison operator.
809 /// @param other The object to compare ourselves to.
810 /// @return \c true if this and given cursor are equal, \c false
811 /// otherwise.
812 bool operator==(const TCursor &other) const
813 {
814 return cmCursor::node == other.node
815 && cmCursor::tree == other.tree;
816 }
817
818 /// Comparison operator.
819 /// @param other The object to compare ourselves to.
820 /// @return \c false if this and given cursor are equal, \c true
821 /// otherwise.
822 bool operator!=(const TCursor &other) const
823 {
824 return !((*this) == other);
825 }
826
827 /// This method exports the address of the node in the \b StringTree.
828 /// The second pointer needed to comprise a cursor determines the tree a node belongs to.
829 /// Sometimes, it is necessary to store and restore a cursor, where the corresponding
830 /// tree is known. With this method, in combination with method StringTree::ImportCursor,
831 /// such storage with <c>sizeof(void*)</c>(instead of twice that size).
832 ///
833 /// \attention In fact this method and the corresponding constructor perform pointer
834 /// operations and keyword <c>reinterpret_cast</c>. Use with care.
835 /// @return A value usable to reconstruct this cursor with the method
836 /// #StringTree::ImportCursor.
837 CursorHandle Export() { return CursorHandle {uinteger(cmCursor::node)}; }
838
839 /// Overloaded \c const version that returns a \c const handle, usable likewise only
840 /// to re-construct a \c const cursor instance.
841 ///
842 /// @return A value usable to reconstruct this cursor with method
843 /// #StringTree::ImportCursor.
844 ConstCursorHandle Export() const{return ConstCursorHandle {uinteger(cmCursor::node)};}
845
846 /// Determines if this is a valid object. Cursors may become invalid with
847 /// transition methods like #GoToParent, #GoToFirstChild or GoToNextSibling.
848 /// An invalid object may be turned into a valid one by either
849 /// - assigning a valid object (copy assignment), or
850 /// - invoking method #GoToRoot, or
851 /// - invoking method #GoTo using absolute path addressing.
852 ///
853 /// Note that the latter is not applicable to a default-constructed objects
854 /// (which are also invalid) as with such no \b %StringTree is assigned.
855 ///
856 /// @return \c true if this is a valid cursor.
857 /// If invalid, \c false is returned and this object must not be used.
858 bool IsValid() const
859 {
860 return cmCursor::node != nullptr;
861 }
862
863 /// Returns the opposite of #IsValid.
864 ///
865 /// @return \c true if this is an invalid cursor that must not be used,
866 /// \c false otherwise.
867 bool IsInvalid() const
868 {
869 return !IsValid();
870 }
871
872 //#### Tree navigation inplace, returning status #########################
873 /// Returns a cursor to the root node of the tree.
874 /// @return A cursor representing the root node of the tree this pointer
875 /// represents.
876 TCursor Root() const
877 {
878 dbgCheckTree();
879 return TCursor(cmCursor::tree, &cmCursor::tree->root.root);
880 }
881
882 /// Moves this cursor to the root node of the tree.
883 /// @return A reference to this object
885 {
886 dbgCheckTree();
887 cmCursor::node = &cmCursor::tree->root.root;
888 return *this;
889 }
890
891 /// Creates a cursor value representing the parent node of the
892 /// node represented by this object.
893 ///
894 /// If this object represents the root node of the tree, the returned cursor
895 /// is invalid.
896 ///
897 /// @return A cursor pointing to the parent node of the node represented
898 /// by this cursor.
900 {
902 return TCursor(cmCursor::tree, static_cast<cmNode*>(cmCursor::node->parent));
903 }
904
905 /// Moves this cursor to the parent of the current node.
906 /// If this is the root node, this object becomes invalid.
907 ///
908 /// @return *this to allow concatenated calls
910 {DCSSHRD
912 cmCursor::node = static_cast<cmNode*>(cmCursor::node->parent);
913 return (*this);
914 }
915
916 /// Returns a cursor value that represents the next sibling of the node
917 /// represented this cursor.
918 /// If the node has no next sibling, an invalid cursor is returned.
919 ///
920 /// @return A cursor object representing the next sibling of the node
921 /// represented by this object.
923 {DCSSHRD
924 return TCursor(cmCursor::tree, HasNextSibling() ? static_cast<cmNode*>(cmCursor::node->next())
925 : nullptr);
926 }
927
928 /// Moves this cursor to the next sibling of the represented node.
929 /// If the node has no next sibling, this cursor becomes invalid.
930 /// The latter is always true if this is the root node of the tree.
931 ///
932 /// @return \c true if this cursor was moved,
933 /// \c false if the represented node has no next sibling.
935 {DCSSHRD
936 // go to node next and check for hook?
937 if (HasNextSibling())
938 {
939 cmCursor::node = static_cast<cmNode*>(cmCursor::node->next());
940 return true;
941 }
942 cmCursor::node = nullptr;
943 return false;
944 }
945
946 /// Returns a cursor value that represents the previous sibling of the node
947 /// represented this cursor.
948 /// If the node has no previous sibling, an invalid cursor is returned.
949 ///
950 /// @return A cursor object representing the previous sibling of the node
951 /// represented by this object.
953 {DCSSHRD
954 return TCursor(cmCursor::tree, HasPreviousSibling() ? static_cast<cmNode*>(cmCursor::node->prev())
955 : nullptr );
956 }
957
958 /// Moves this cursor to the previous sibling of the represented node.
959 /// If the node has no previous sibling, this cursor becomes invalid.
960 /// The latter is always true if this is the root node of the tree.
961 ///
962 /// @return \c true if this cursor was moved,
963 /// \c false if the represented node has no previous sibling.
965 {DCSSHRD
966 if( HasPreviousSibling() )
967 {
968 cmCursor::node= static_cast<cmNode*>(cmCursor::node->prev());
969 return true;
970 }
971 cmCursor::node= nullptr;
972 return false;
973 }
974
975 /// Returns a cursor object that represents the first child of the node
976 /// represented.
977 /// If the represented node has no children, an invalid cursor is returned.
978 ///
979 /// @return A cursor representing the first child of the node this cursor points to.
981 {DCSSHRD
982 return TCursor( cmCursor::tree, HasChildren() ? static_cast<cmNode*>(cmCursor::node->children.first())
983 : nullptr );
984 }
985
986 /// Moves this cursor to the first child of its represented node.
987 /// If the represented node has no children, this cursor becomes invalid.
988 ///
989 /// @return \c true if the cursor was moved, \c false if the represented node
990 /// has no children.
992 {DCSSHRD
993 if( HasChildren() )
994 {
995 cmCursor::node= static_cast<cmNode*>(cmCursor::node->children.first());
996 return true;
997 }
998 cmCursor::node= nullptr;
999 return false;
1000 }
1001
1002 /// Returns a cursor value that represents the last child of the node
1003 /// represented.
1004 /// If the represented node has no children, an invalid cursor is returned.
1005 ///
1006 /// @return A cursor representing the last child of the node represented
1007 /// by this cursor.
1009 {DCSSHRD
1010 return TCursor( cmCursor::tree, HasChildren() ? static_cast<cmNode*>(cmCursor::node->children.last())
1011 : nullptr );
1012 }
1013
1014 /// Moves this cursor to the last child of its represented node.
1015 /// If the represented node has no children, this cursor becomes invalid.
1016 ///
1017 /// @return \c true if the cursor was moved, \c false if the represented node
1018 /// has no children.
1020 {DCSSHRD
1021 if( HasChildren() )
1022 {
1023 cmCursor::node= static_cast<cmNode*>(cmCursor::node->children.last());
1024 return true;
1025 }
1026 cmCursor::node= nullptr;
1027 return false;
1028 }
1029
1030 /// Searches a child with the given name and returns a cursor to it.
1031 /// If no child with this name exists, the returned cursor is invalid
1032 ///
1033 /// The given \p{name} is not considered a path and is not checked for being <c>"."</c>
1034 /// or <c>".."</c> or if it contains a separator character.
1035 /// Children with such name cannot exist and hence can't be found. However, in
1036 /// debug-builds, an \ref ALIB_WARNING is reported.
1037 ///
1038 /// @param name The name of the child to search.
1039 /// @return A cursor representing the last child of the node represented
1040 /// by this cursor.
1041 TCursor Child( const NameType& name ) const
1042 {DCSSHRD
1044 ALIB_DBG( cmCursor::tree->checkChildName( name ); ) // gives warning
1045 return TCursor( cmCursor::tree,
1046 static_cast<cmNode*>(cmCursor::node->findChild(cmCursor::tree, name)));
1047 }
1048
1049 /// Searches a child with the given name and moves this cursor to it.
1050 /// If no child with this name exists, the cursor does not change and
1051 /// \c false is returned.
1052 ///
1053 /// The given \p{name} is not considered a path and is not checked for being <c>"."</c>
1054 /// or <c>".."</c> or if it contains a separator character.
1055 /// Children with such a name cannot exist and hence can't be found. However, in
1056 /// debug-builds, an \ref ALIB_WARNING is reported.
1057 ///
1058 /// @param name The name of the child to search.
1059 /// @return \c true if the child existed and this object changed, \c false
1060 /// otherwise.
1061 bool GoToChild( const NameType& name )
1062 {DCSSHRD
1064 ALIB_DBG( cmCursor::tree->checkChildName( name ); )
1065
1066 cmNode* child= static_cast<cmNode*>(cmCursor::node->findChild( cmCursor::tree, name ));
1067 if(child)
1068 {
1069 cmCursor::node= child;
1070 return true;
1071 }
1072 return false;
1073 }
1074
1075 /// Moves this cursor to the child with given \p{name}.
1076 /// If no child with this name exists, one will be created.
1077 ///
1078 /// If the given \p{childName} is invalid (equals to <c>"."</c> or
1079 /// <c>".."</c> or contains the separation character), then still \c true is returned,
1080 /// but this cursor becomes invalid.
1081 /// In addition, with debug-builds, an \ref ALIB_WARNING is reported.
1082 ///
1083 /// @tparam TArgs Types of variadic parameters given with parameter \p{args}.
1084 /// @param name The name of the desired child.
1085 /// @param args Variadic parameters to be forwarded to the constructor of custom type
1086 /// \p{T} in the case a child is created.
1087 /// @return A pair of a cursor pointing to the child and a boolean that equals
1088 /// \c false if the child was found, and \c true if a child was created.
1089 /// If the given name was invalid, the returned cursor will be invalid
1090 /// while the boolean still indicates "not found" (aka \c true).
1091 template<typename... TArgs>
1092 std::pair<TCursor, bool> CreateChildIfNotExistent( const NameType& name,
1093 TArgs&&... args )
1094 {DCS
1096 if( !cmCursor::tree->checkChildName( name ) )
1097 return std::make_pair( TCursor(cmCursor::tree, nullptr), true );
1098
1099 auto result= cmCursor::node->findOrCreateChild( cmCursor::tree, name,
1100 std::forward<TArgs>(args)... );
1101
1102 return std::make_pair( TCursor( cmCursor::tree, result.first ), result.second );
1103 }
1104
1105 /// Moves this cursor to the child with given \p{name}.
1106 /// If no child with this name exists, one will be created.
1107 ///
1108 /// If the given \p{childName} is invalid (equals to <c>"."</c> or
1109 /// <c>".."</c> or contains the separation character), then still \c true is returned,
1110 /// but this cursor becomes invalid.
1111 /// In addition, with debug-builds, an \ref ALIB_WARNING is reported.
1112 ///
1113 /// @tparam TArgs Types of variadic parameters given with parameter \p{args}.
1114 /// @param name The name of the desired child.
1115 /// @param args Variadic parameters to be forwarded to the constructor of custom type
1116 /// \p{T} in the case a child is created.
1117 /// @return \c false if the child was found, and \c true if one was created or the given
1118 /// child name was invalid.
1119 template<typename... TArgs>
1120 bool GoToCreateChildIfNotExistent(const NameType& name, TArgs&&... args)
1121 {DCS
1123 if( !cmCursor::tree->checkChildName( name ) )
1124 {
1125 cmCursor::node= nullptr;
1126 return true;
1127 }
1128
1129 auto result= cmCursor::node->findOrCreateChild( cmCursor::tree, name,
1130 std::forward<TArgs>(args)... );
1131
1132 cmCursor::node= static_cast<cmNode*>(result.first);
1133 return result.second;
1134 }
1135
1136 /// Follows the given \p{path} from the currently represented node to the target
1137 /// node and returns a new cursor instance..
1138 ///
1139 /// The method supports absolute and relative path addressing: If \p{path} begins
1140 /// with a separation character, then the transition starts with the root node of the
1141 /// \b %StringTree. Furthermore, child name <c>"."</c> is ignored and just skipped
1142 /// while a name of <c>".."</c> addresses the parent node during the transition.
1143 /// Repeated separation characters are ignored.<br>
1144 /// If, while processing the path string, the root node is found an the next
1145 /// path element is "..", this element is ignored and processing continues.
1146 /// As a sample, assuming that nodes \e /a and \e /b exist, the paths:
1147 ///
1148 /// /a/../b
1149 /// and
1150 ///
1151 /// /a/../../b
1152 /// both evaluate to
1153 ///
1154 /// /b
1155 ///
1156 /// Relative paths must not be used on \ref TCursor::IsValid "invalid" cursors. Doing so
1157 /// is undefined behavior and raises an \alib assertion in debug-compilations.
1158 ///
1159 /// If a child along the path does not exist, the traversal is ended and the remaining
1160 /// portion of the path is returned.
1161 ///
1162 /// \note
1163 /// If parameter \p{path} is a temporary object, the resulting \b Substring must
1164 /// not be used, as it refers to the given string's buffer. In any case, its
1165 /// length can still be compared to \c 0 to evaluate success of the traversal.
1166 ///
1167 /// @param path The path to follow, starting with the node this pointer represents.
1168 ///
1169 /// @return A pair of a cursor pointing to last child not of the existing portion
1170 /// of the given \p{path}, and a substring that contains the non-existing
1171 /// portion of a path, or is empty if the complete path existed.
1172 std::pair<TCursor, SubstringType> operator()( const NameType& path ) const
1173 {DCSSHRD
1175 SubstringType remainingPath(path);
1176 cmNode* grandChild= cmCursor::followPath( remainingPath );
1177 return std::make_pair( TCursor(cmCursor::tree, grandChild), remainingPath );
1178 }
1179
1180 /// Same as the
1181 /// \doxlinkproblem{classalib_1_1containers_1_1StringTree_1_1TCursor.html;a55db5acb390a2d38dd8e30c123cb6e4b;operator()(const NameType&)},
1182 /// but moves this cursor instead of returning a new one.
1183 ///
1184 /// @param path The path to move this cursor along.
1185 /// @return The unconsumed portion of the path.
1186 /// An empty \b Substring if the path existed.
1188 {DCSSHRD
1190 SubstringType remainingPath(path);
1191 cmCursor::node= cmCursor::followPath( remainingPath );
1192 return remainingPath;
1193 }
1194
1195 /// Follows the given path and creates non-existing children along the way.
1196 ///
1197 /// Child names <c>"."</c> and <c>".."</c> are allowed and respected the same as
1198 /// documented with the
1199 /// \doxlinkproblem{classalib_1_1containers_1_1StringTree_1_1TCursor.html;a55db5acb390a2d38dd8e30c123cb6e4b;operator()(const NameType&)}.
1200 /// New child nodes are constructed by forwarding the given \p{args}. Existing children
1201 /// remain untouched.
1202 ///
1203 /// @tparam TArgs Types of variadic parameters given with parameter \p{args}.
1204 /// @param path The path to move along.
1205 /// @param args Variadic parameters to be forwarded to the constructor of each node
1206 /// that is created.
1207 /// @return A <c>std::pair</c> containing a resulting \b Cursor and the number of nodes
1208 /// created.
1209 template<typename... TArgs>
1210 std::pair<TCursor, integer> CreatePathIfNotExistent( const NameType& path,
1211 TArgs&&... args )
1212 {DCS
1213 dbgCheckTree();
1214 ALIB_ASSERT_ERROR( IsValid() || path.CharAtStart() == cmCursor::tree->separator,
1215 "MONOMEM/STRINGTREE",
1216 "Invalid StringTree::Cursor given with relative path addressing." )
1217
1218 auto result= cmCursor::followPathCreate( path, std::forward<TArgs>(args)... );
1219
1220 return std::make_pair( TCursor(cmCursor::tree, static_cast<cmNode*>(result.first)),
1221 result.second );
1222 }
1223
1224 /// Follows the given path and creates non-existing children along the way.
1225 ///
1226 /// Child names <c>"."</c> and <c>".."</c> are allowed and respected same as in
1227 /// \doxlinkproblem{classalib_1_1containers_1_1StringTree_1_1TCursor.html;a55db5acb390a2d38dd8e30c123cb6e4b;operator()(const NameType&)}.
1228 ///
1229 /// New child nodes are constructed by forwarding the given \p{args}. Existing children
1230 /// remain untouched.
1231 ///
1232 /// @tparam TArgs Types of variadic parameters given with parameter \p{args}.
1233 /// @param path The path to move along.
1234 /// @param args Variadic parameters to be forwarded to the constructor of each node
1235 /// that is created.
1236 /// @return The number of nodes created.
1237 template<typename... TArgs>
1239 TArgs&&... args )
1240 {DCS
1241 dbgCheckTree();
1242 ALIB_ASSERT_ERROR( IsValid() || path.CharAtStart() == cmCursor::tree->separator,
1243 "MONOMEM/STRINGTREE",
1244 "Invalid StringTree::Cursor given with relative path addressing." )
1245
1246 auto result= cmCursor::followPathCreate( path, std::forward<TArgs>(args)... );
1247 cmCursor::node= static_cast<cmNode*>(result.first);
1248 return result.second;
1249 }
1250
1251 //##### Cursor Interface #######################################################
1252 /// Returns the name of the represented node.
1253 /// Note that the concatenated names of recursive child nodes, separated by
1254 /// \p{TSeparator} constitute a \e path.
1255 ///
1256 /// @return A constant reference to the name of the represented node.
1257 const NameType& Name() const
1258 {
1260 return cmCursor::node->name.key;
1261 }
1262
1263 #if DOXYGEN
1264 /// Returns the tree that this cursor belongs to.
1265 /// @tparam TParent Optional template parameter, which casts the internal tree type
1266 /// to a derived type. This is for convenience, as otherwise the
1267 /// cast hast to be done by the caller which does not look too nice.
1268 /// @return The tree that this object refers to.
1269 template<typename TParent= StringTree> const
1270 inline
1271 TParent& Tree();
1272
1273 #else
1274
1275 template<typename TParent= StringTree>
1276 inline
1277 ATMP_T_IF(TParent&, ATMP_ISOF(TParent, StringTree))
1278 Tree() const
1279 {
1280 dbgCheckTree();
1281 return *static_cast<TParent*>(cmCursor::tree);
1282 }
1283 #endif
1284
1285 #if DOXYGEN
1286 /// Retrieves a reference to the templated value of type \p{T} stored in the represented
1287 /// node.
1288 /// \note This method is only available if template parameter \p{TConst} is false.
1289 /// @see Operators #operator->() and #operator*().
1290 /// @return The current node's value.
1291 T& Value();
1292 #else
1293 template<bool TEnableIf= !TConst>
1294 ATMP_T_IF(T&, TEnableIf)
1295 Value()
1296 {
1297 dbgCheckTree();
1298 ALIB_ASSERT_ERROR( !IsRoot() || cmCursor::tree->dbgRootDataSet > 0, "MONOMEM/STRINGTREE",
1299 "Root node has no value. Either this operation is unwanted or root node's value\n"
1300 "has to be explicitly set using SetRootNode(...)" )
1301 return static_cast<baseNode*>(cmCursor::node)->data;
1302 }
1303 #endif // ALIB_DOX
1304
1305
1306 /// Retrieves a constant reference to the templated value of type \p{T} stored in
1307 /// the represented node.
1308 /// @see Operators #operator->() and #operator*().
1309 /// @return The current node's value.
1310 const T& Value() const
1311 {
1312 dbgCheckTree();
1313 ALIB_ASSERT_ERROR( !IsRoot() || cmCursor::tree->dbgRootDataSet > 0, "MONOMEM/STRINGTREE",
1314 "Root node has no value. Either this operation is unwanted or root node's value\n"
1315 "has to be explicitly set using SetRootNode(...)" )
1316 return static_cast<const baseNode*>(cmCursor::node)->data;
1317 }
1318
1319 #if DOXYGEN
1320 /// Retrieves a pointer to the templated value of type \p{T} stored
1321 /// in the represented node.
1322 /// \note This operator is only available if template parameter \p{TConst} is false.
1323 /// @return The current node's value.
1325 #else
1326 template<bool TEnableIf= !TConst>
1327 ATMP_T_IF(T*, TEnableIf)
1328 operator->()
1329 {
1330 dbgCheckTree();
1331 ALIB_ASSERT_ERROR( !IsRoot() || cmCursor::tree->dbgRootDataSet > 0, "MONOMEM/STRINGTREE",
1332 "Root node has no value. Either this operation is unwanted or root node's value\n"
1333 "has to be explicitly set using SetRootNode(...)" )
1334 return &static_cast<baseNode*>(cmCursor::node)->data;
1335 }
1336 #endif // ALIB_DOX
1337
1338 /// Retrieves a constant pointer to the templated value of type \p{T} stored in
1339 /// the represented node.
1340 /// @return The current node's value.
1341 const T* operator->() const
1342 {
1343 dbgCheckTree();
1344 ALIB_ASSERT_ERROR( !IsRoot() || cmCursor::tree->dbgRootDataSet > 0, "MONOMEM/STRINGTREE",
1345 "Root node has no value. Either this operation is unwanted or root node's value\n"
1346 "has to be explicitly set using SetRootNode(...)" )
1347 return &static_cast<const baseNode*>(cmCursor::node)->data;
1348 }
1349
1350 #if DOXYGEN
1351 /// Retrieves a reference to the templated value of type \p{T} stored
1352 /// in the represented node.
1353 /// \note This operator is only available if template parameter \p{TConst} is false.
1354 /// @return The current node's value.
1356 #else
1357 template<bool TEnableIf= !TConst>
1358 ATMP_T_IF(T&, TEnableIf)
1359 operator*()
1360 {
1361 dbgCheckTree();
1362 ALIB_ASSERT_ERROR( !IsRoot() || cmCursor::tree->dbgRootDataSet > 0, "MONOMEM/STRINGTREE",
1363 "Root node has no value. Either this operation is unwanted or root node's value\n"
1364 "has to be explicitly set using SetRootNode(...)" )
1365 return static_cast<baseNode*>(cmCursor::node)->data;
1366 }
1367 #endif // ALIB_DOX
1368
1369 /// Retrieves a reference to the templated value of type \p{T} stored
1370 /// in the represented node.
1371 /// \note This operator is only available if template parameter \p{TConst} is false.
1372 /// @return The current node's value.
1373 const T& operator*() const
1374 {
1375 dbgCheckTree();
1376 ALIB_ASSERT_ERROR( !IsRoot() || cmCursor::tree->dbgRootDataSet > 0, "MONOMEM/STRINGTREE",
1377 "Root node has no value. Either this operation is unwanted or root node's value\n"
1378 "has to be explicitly set using SetRootNode(...)" )
1379 return static_cast<const baseNode*>(cmCursor::node)->data;
1380 }
1381
1382 /// Returns \c true if this cursor represents the root node of the
1383 /// \b %StringTree, \c false otherwise.
1384 /// @return \c true if this object represents the root node, \c false otherwise.
1385 bool IsRoot() const
1386 {
1388 return cmCursor::node->isRoot();
1389 }
1390
1391 /// Determines the depth of the node represented by this object. This is done by
1392 /// counting the iterations needed to reach the root node of the tree.
1393 /// @return The distance from this node to the root node.
1394 int Depth() const
1395 {DCSSHRD
1397 return cmCursor::node->depth();
1398 }
1399
1400 /// Determines the distance between the node represented by this cursor to the
1401 /// node represented by given \p{other}. The distace is defined as follows:
1402 ///
1403 /// - \b 0 if other represents the same node.
1404 /// - \b 1 if other represents the parent of this node.
1405 /// - \b 2 if other represents the grand-parent of this node.
1406 /// - \b 3 ...
1407 /// - \b N if other represents the root node.
1408 ///
1409 /// @param other The node to test.
1410 /// @return The distance from this node to the root node. \c -1 is returned in case
1411 /// \p{other} is not found in the path to this node.
1412 int Distance( const TCursor<true>& other ) const
1413 {DCSSHRD
1415 ALIB_ASSERT_ERROR( other.node, "MONOMEM/STRINGTREE", "Invalid node given." )
1416 ALIB_ASSERT_ERROR( cmCursor::tree == other.tree, "MONOMEM/STRINGTREE",
1417 "Given node belongs to a different StringTree." )
1418 return cmCursor::node->distance( other.node );
1419 }
1420
1421 /// Returns \c true if the represented node has at least one direct child.
1422 /// @return \c true if the current node has children, \c false otherwise.
1423 bool HasChildren() const
1424 {DCSSHRD
1426 return cmCursor::node->qtyChildren != 0;
1427 }
1428
1429 /// Returns the number of direct children of the represented node.<br>
1430 /// Note that this method runs in constant time.
1431 /// @return The number of direct children of the represented node.
1433 {DCSSHRD
1435 return cmCursor::node->qtyChildren;
1436 }
1437
1438 /// Evaluates if the node represented by this object has a next sibling in its
1439 /// parent's list of children.
1440 /// @return \c true if a next sibling to this object's represented node exists,
1441 /// \c false otherwise.
1442 bool HasNextSibling() const
1443 {DCSSHRD
1445 return !IsRoot()
1446 && !cmCursor::node->parent->children.isLast( cmCursor::node );
1447 }
1448
1449 /// Evaluates if the node represented by this object has a previous sibling in its
1450 /// parent's list of children.
1451 /// @return \c true if a previous sibling to this object's represented node exists,
1452 /// \c false otherwise.
1454 {DCSSHRD
1456 return !IsRoot()
1457 && !cmCursor::node->parent->children.isFirst( cmCursor::node );
1458 }
1459
1460 /// Writes the absolute path to the represented node (including the represented node's
1461 /// name) to the given \b %AString.<br>
1462 /// If this node represents the root node, then nothing is written but a single
1463 /// separation character.
1464 ///
1465 /// While the implementation of this method is as efficient as possible (to avoid
1466 /// insertions at the beginning of the target string while moving to the destination/root
1467 /// node, internally a local node-stack is created first, which then is traversed
1468 /// top-down), still in many situations, it is recommended to search for other ways to
1469 /// keep track of the current path of a node and modify and re-use such path.
1470 /// For this, class \alib{containers;StringTree::RecursiveIterator}, optionally
1471 /// allows maintaining a string representing the current path with every iteration.
1472 ///
1473 /// \see
1474 /// Overloaded version <b>AssemblePath(AString&,TCursor<TConst>&,lang::CurrentData)</b>,
1475 /// which allows the creation a relative path from a parent node to this node.
1476 ///
1477 /// @param targetString The string buffer to append the path to.
1478 /// @param targetData Denotes whether \p{target} should be cleared before
1479 /// appending the path. Defaults to \b CurrentData::Clear.
1480 /// @return The given \b AString to allow concatenated operations.
1482 AssemblePath( strings::TAString<typename cmTree::CharacterType,
1483 lang::HeapAllocator >& targetString,
1484 lang::CurrentData targetData=
1486 {DCSSHRD
1487 if( targetData == lang::CurrentData::Clear )
1488 targetString.Reset();
1489
1490 return cmCursor::node->assemblePath( targetString, cmCursor::node, nullptr,
1491 cmCursor::tree->separator );
1492 }
1493
1494 /// Same as #AssemblePath but accepts a parent node to stop at, instead of the root node.
1495 /// The path created is a relative path from the \p{parent} to the represented node,
1496 /// hence it does \b not include the parent' name and also does \b not start with the
1497 /// separation character. The latter is true even if the given \p targetParent represents
1498 /// the root node. In this case the path is a relative path from the root node \c '/'
1499 /// to the child.
1500 ///
1501 /// If the given \p{parent} is not found within the list of parent nodes, then
1502 /// an absolute path from the tree's root to the represented node is returned.
1503 ///
1504 ///
1505 /// @param targetString The string buffer to append the path to.
1506 /// @param parent Denotes the parent node to start a relative path from.
1507 /// @param targetData Denotes whether \p{target} should be cleared before
1508 /// appending the path. Defaults to \b CurrentData::Clear.
1509 /// @return The given \b AString to allow concatenated operations.
1511 AssemblePath( strings::TAString<typename cmTree::CharacterType,
1512 lang::HeapAllocator >& targetString,
1513 const TCursor<true>& parent,
1514 lang::CurrentData targetData
1515 = lang::CurrentData::Clear ) const
1516 {DCSSHRD
1518 if( targetData == lang::CurrentData::Clear )
1519 targetString.Reset();
1520 return cmCursor::node->assemblePath( targetString, cmCursor::node, parent.node,
1521 cmCursor::tree->separator );
1522 }
1523
1524 //##### Cursor child creation #####################################################
1525 /// Creates and returns a child node. If a node already exists, nothing is done and
1526 /// \c nullptr is returned as this is considered an error.
1527 ///
1528 /// If the child name is illegal (equal to <c>"."</c> or <c>".."</c> or contains a
1529 /// separation character), an \alib warning is raised and an invalid cursor
1530 /// is returned.
1531 ///
1532 /// Template parameter \p{TCheck} may be used to suppress the search for an
1533 /// existing child with the same name, as well as the check for correctness of the
1534 /// given child name.
1535 /// This tremendously improves the execution performance of this method.
1536 ///
1537 /// \attention Setting template parameter \p{TCheck} to \alib{NC} and inserting
1538 /// child nodes with the same name, sets a \b %StringTree to an
1539 /// undefined state.
1540 ///
1541 /// @tparam TCheck If \alib{NC}, no check for an existing child with the same name
1542 /// is performed.
1543 /// @tparam TArgs Types of variadic parameters given with parameter \p{args}.
1544 /// @param childName The name of the child
1545 /// @param args Variadic parameters to be forwarded to the constructor of custom
1546 /// type \p{T} of the child created.
1547 ///
1548 /// @return A new cursor object representing the created child node.
1549 /// If the given \p{childName} was invalid or the child existed already,
1550 /// the returned object is invalid.
1551 template<typename TCheck =CHK, typename... TArgs>
1552 TCursor CreateChild( const NameType& childName, TArgs&&... args ) const
1553 {DCS
1555 if constexpr ( TCheck::value )
1556 {
1557 // check name
1558 if( !baseCursor::tree->checkChildName( childName ) )
1559 {
1560 ALIB_WARNING( "STRINGTREE", "Illegal child name {!Q}", childName )
1561 return Cursor( baseCursor::tree, nullptr );
1562 }
1563
1564 // check existence
1565 if( baseCursor::node->qtyChildren > 0
1566 && baseCursor::tree->nodeTable.Contains( baseNodeKey( baseCursor::node, childName) ))
1567 return Cursor( baseCursor::tree, nullptr );
1568 }
1569
1570 baseNode* child= &baseCursor::tree->nodeTable.EmplaceUnique( baseCursor::node, childName,
1571 std::forward<TArgs>(args)... )
1572 .Value();
1573 TNodeHandler::InitializeNode( *baseCursor::tree, *child );
1574
1575 baseCursor::node->children.pushEnd( child );
1576 ++baseCursor::node->qtyChildren;
1577 return TCursor( baseCursor::tree, child );
1578 }
1579
1580 //##### Cursor deletion #######################################################
1581 /// Searches and deletes the child named \p{childName} from the node that this object
1582 /// refers to. This object itself is not changed.
1583 ///
1584 /// \see
1585 /// Overloaded version of this method that accepts a cursor referring to
1586 /// the child in question.
1587 ///
1588 ///
1589 /// @param childName The name of the desired child.
1590 /// @return \c true if the child existed and was deleted, \c false otherwise.
1591 bool DeleteChild( const NameType& childName ) const
1592 {DCS
1594 if( baseCursor::node->qtyChildren == 0 )
1595 return false;
1596
1597 auto handle= baseCursor::tree->nodeTable.Extract( baseNodeKey( baseCursor::node, childName) );
1598 if( handle.IsEmpty() )
1599 return false;
1600 handle.Value().deleteChildren( baseCursor::tree );
1601 TNodeHandler::FreeNode( *baseCursor::tree, handle.Value() );
1602 handle.Value().remove();
1603
1604 --baseCursor::node->qtyChildren;
1605 return true;
1606 }
1607
1608 /// Deletes the child represented by the given cursor \p{child} from the node that this
1609 /// cursor refers to. After the invocation, the given \p{child} cursor refers to its
1610 /// next sibling. If no such sibling exists, \p{child} becomes invalid.
1611 /// This cursor itself is not changed.
1612 ///
1613 /// \note
1614 /// This method is useful to implement forward iterations through children of a parent
1615 /// node with the aim to delete certain child nodes. No corresponding version of this
1616 /// method exists that moves the given \p{child} pointer to its previous sibling.
1617 /// For reverse iterations, a copy of the \p{child} argument has to be passed.
1618 /// However, any overhead caused by such temporary object creation will be optimized
1619 /// out by common C++ compilers.
1620 ///
1621 /// @param child Deletes the child represented by the given node.
1622 void DeleteChild( TCursor& child ) const
1623 {DCS
1625 cmNode* nodeToDelete= child.node;
1626 child.GoToNextSibling();
1627 baseCursor::node->deleteChild( baseCursor::tree, nodeToDelete );
1628 }
1629
1630 /// Deletes the children of the node that this cursor refers to.
1631 /// This object itself is not changed.
1632 ///
1633 /// @return The number of children that were deleted.
1635 {DCS
1637 return baseCursor::node->deleteChildren( baseCursor::tree );
1638 }
1639
1640 /// Deletes the branch that this cursor refers to from the tree.
1641 /// If this cursor does not represent the root node, then after the operation,
1642 /// it refers to the parent of the current node.<br>
1643 /// If the represented node is the root node, only the children are deleted and this
1644 /// object remains representing the root node. Note that in this case any explicitly
1645 /// set custom value of the root node is \b not deleted. For this, exclusively methods
1646 /// #ConstructRootValue and #DestructRootValue are to be used.
1647 ///
1648 /// \note
1649 /// If this method is invoked on an object returned by method
1650 /// #RecursiveIterator::Node, the invoking iterator becomes invalid.<br>
1651 /// To avoid this, method #RecursiveIterator::DeleteNode is to be used.
1652 ///
1653 /// @return
1654 /// The total number of nodes deleted. Can be zero, in case this object represents
1655 /// the root node and this node has no children.
1657 {DCS
1659 if( baseCursor::node->isRoot() )
1660 return baseCursor::node->deleteChildren( baseCursor::tree );
1661
1662 cmNode * child= baseCursor::node;
1663 baseCursor::node= static_cast<cmNode*>(baseCursor::node->parent);
1664 return baseCursor::node->deleteChild( baseCursor::tree, child );
1665 }
1666 }; // inner class TCursor
1667
1668 /// The mutable version of type \alib{containers;StringTree::TCursor<TConst>}.
1670
1671 /// The constant version of type \alib{containers;StringTree::TCursor<TConst>}.
1673
1674 protected:
1675 /// Protected methods that allows derived types to create cursor instances from
1676 /// nodes received directly from the hashtable.
1677 /// @param node The base node.
1678 /// @return A valid cursor.
1679 Cursor createCursor(baseNode& node) { return Cursor(this, &node); }
1680
1681 public:
1682
1683 //==============================================================================================
1684 /// This public, inner class can be used to recursively iterate through the nodes of
1685 /// outer class \b StringTree.<br>
1686 /// The type does <b>not</b> apply to the concept of \c std::iterator_traits.
1687 /// The rationale for this is the fact that mechanics for sorting the child nodes are
1688 /// provided, which requires allocation of more resources than usual container iterators do.
1689 /// Therefore, objects of this type are not supposed to be temporary and
1690 /// created "on the fly", e.g., in C++ range based loops.
1691 /// Instead, instances should rather be created once and then re-used with later iterations.
1692 ///
1693 /// The sorting of child nodes is optional and can be changed before each recursion.
1694 /// A built-in comparison function which works on node names (path names) allows choosing
1695 /// ascending and descending order and to ignore or be sensitive about the letter case.
1696 /// Besides this, custom comparison functions that take a combination of arbitrary node
1697 /// attributes, including a node's value of template type \p{T} can be established.
1698 /// See overloaded methods #SetSorting for details on this topic.
1699 ///
1700 /// Objects of this type can be initialized, respectively reset to distinct start nodes by
1701 /// providing objects of
1702 /// - type \b %StringTree,
1703 /// - type \b %StringTree::Cursor or
1704 /// - other objects of this type itself,
1705 ///
1706 /// to overloaded methods #Initialize.
1707 ///
1708 /// The maximum depth of recursion may be limited with optional parameter \p{depth}
1709 /// found with each overloaded version of #Initialize.
1710 /// During the iteration, the recursion can be individually selected per node visited.
1711 /// This is done by using either of the methods #Next or #NextSibling to proceed.
1712 /// Furthermore, method #NextParentSibling allows skipping the rest of the current iteration
1713 /// branch.<br>
1714 /// The end of an iteration is detected with the method #IsValid.
1715 ///
1716 /// The children of a node can be iterated in a sorted fashion. To enable and disable
1717 /// sorting, various overloads of #SetSorting exist. These methods may be invoked any
1718 /// time during the iteration. Whenever a recursion in iteration occurs, the most recent
1719 /// settings of sorting are respected for the list of children of the node that is
1720 /// processed with that recursion.
1721 ///
1722 /// Finally, the generation of a string representing the actual path to the current
1723 /// iteration node, relative to the iteration's start node can be activated.
1724 /// See method #SetPathGeneration for mor e information about this feature.
1725 ///
1726 /// \see
1727 /// For more information on how this class is used, see paragraph
1728 /// \ref alib_ns_containers_stringtree_iterator "2.2 Inner Class RecursiveIterator"
1729 /// of the description of class \b %StringTree.
1730 ///
1731 /// ## Friends ##
1732 /// class \alib{containers;StringTree}
1733 //==============================================================================================
1734 template<bool TConst>
1736 {
1737 #if !DOXYGEN
1738 #if ALIB_DEBUG_CRITICAL_SECTIONS
1739 #undef DCS
1740 #undef DCSSHRD
1741 #define DCS ALIB_DCS_WITH(tree->nodeTable.dcs)
1742 #define DCSSHRD ALIB_DCS_SHARED_WITH(tree->nodeTable.dcs)
1743 #endif
1744 #endif
1745 protected:
1746
1747 /// Constant or mutable version of the base tree type, depending on template parameter
1748 /// \p{TConst}
1749 using cmTree = ATMP_IF_T_F(!TConst, StringTree , const StringTree );
1750
1751 /// Constant or mutable version of the base node type, depending on template parameter
1752 /// \p{TConst}
1753 using cmNodeBase= ATMP_IF_T_F(!TConst, baseNodeBase, const baseNodeBase );
1754
1755 /// Constant or mutable version of the base node type, depending on template parameter
1756 /// \p{TConst}
1757 using cmNode = ATMP_IF_T_F(!TConst, baseNode , const baseNode );
1758
1759 /// Constant or mutable version of the base Cursor type, depending on template parameter
1760 /// \p{TConst}
1762
1763 //######################################################################################
1764 // Inner type RecursionData
1765 //######################################################################################
1766 /// Protected, internal struct used to store the data of recursive iterations.
1768 {
1769 /// Combines a node hook and and a current vector index used to remember the
1770 /// current child in unsorted, respectively sorted mode.
1771 union
1772 {
1773 /// The current child of the current node in case of unsorted access
1774 /// If this is pointing to the end of the child map, then
1775 /// the actual node itself is selected by this RecursiveIterator.
1777
1778 /// The current child index in case of sorted access.
1779 /// A value of <c>size_t(-1)</c> indicates that
1780 /// the actual node itself is selected.
1781 size_t sorted;
1782
1783 } actChild;
1784
1785 #if DOXYGEN
1786 /// The child hook of the parent node, used with unsorted iteration.
1787 /// Note that this is declared \c const, in case template param \p{TConst} equals
1788 /// \c true.
1790 #else
1793 childrenUnsorted;
1794 #endif
1795
1796 /// A pointer to a dynamically allocated vector of children used with sorting.
1797 std::vector<cmNode*> childrenSorted;
1798
1799 /// Copied from \alib{containers::StringTree;TRecursiveIterator} with every
1800 /// recursion step.
1801 bool (*customSorter)(const cmCursor&, const cmCursor&);
1802
1803 /// Copied from \alib{containers::StringTree;TRecursiveIterator} with every
1804 /// recursion step.
1806
1807 /// Copied from \alib{containers::StringTree;TRecursiveIterator} with every
1808 /// recursion step.
1810
1811 /// Copied from \alib{containers::StringTree;TRecursiveIterator} with every
1812 /// recursion step.
1814
1815
1816 /// Trivial default constructor.
1817 RecursionData() noexcept = default;
1818
1819 /// Trivial default copy constructor.
1820 RecursionData( const RecursionData& ) = default;
1821
1822 /// Trivial default move constructor.
1823 RecursionData( RecursionData&& ) noexcept = default;
1824
1825 /// Trivial default copy assign operator.
1826 /// @return A reference to \c this.
1827 RecursionData& operator=( const RecursionData& ) = default;
1828
1829 /// Trivial default move assign operator.
1830 /// @return A reference to \c this.
1831 RecursionData& operator=( RecursionData&& ) noexcept = default;
1832
1833 /// Trival default destructor
1834 ~RecursionData() noexcept = default;
1835 }; // inner struct RecursionData
1836
1837 //##### RecursiveIterator members #####################################################
1838
1839 /// The \b %StringTree this iterator belongs to.
1840 cmTree* tree = nullptr;
1841
1842 /// The pointer to the actual node.
1843 cmNode* node;
1844
1845 /// A stack holding the recursive list of unsorted or sorted children and the
1846 /// hook to the current child. Implemented as a vector in combination with member #actDepth,
1847 /// to reuse allocated storage space during iteration and when this iterator is
1848 /// re-used (freshly initialized).
1849 std::vector<RecursionData> stack;
1850
1851 /// The current depth of the iteration (and usage but not size of field #stack).
1852 /// set to \c -1 to if iteration is finished, respectively this iterator was not
1853 /// initialized.
1854 size_t actDepth = size_t(-1);
1855
1856 /// The path to the actual node (excluding the name of the actual node).
1857 /// If this object is \e nulled, no paths are generated.
1858 AString actPath;
1859
1860 /// The requested depth of iteration recursion.
1861 unsigned int recursionDepth =(std::numeric_limits<unsigned int>::max)();
1862
1863 /// A pointer to a user-defined comparison function.
1864 bool (*nextCustomSorter)(const cmCursor&, const cmCursor&) = nullptr;
1865
1866 /// Denotes if the children are iterated in a sorting fashion or not.
1867 bool nextIsSorting = false;
1868
1869 /// The sort order (used with built-in sorting by node name).
1870 bool nextSortingIsDescending = false;
1871
1872 /// The case sensitivity of the sort (used with built-in sorting by node name).
1873 bool nextSortingIsCaseSensitive = false;
1874
1875 // #### RecursiveIterator Constructor/Destructor ########################################
1876 public:
1877 /// Default constructor.
1879
1880 /// Trivial copy constructor.
1882
1883 /// Trivial default move constructor.
1885
1886 /// Trivial default copy assign operator.
1887 /// @return A reference to \c this.
1888 TRecursiveIterator& operator=( const TRecursiveIterator& ) = default;
1889
1890 /// Trivial default move assign operator.
1891 /// @return A reference to \c this.
1892 TRecursiveIterator& operator=( TRecursiveIterator&& ) = default;
1893
1894
1895 /// Destructor.
1897
1898 // #### RecursiveIterator Interface ###################################################
1899 /// With this method, the assembly of a string representing the path from the
1900 /// node used to initialize this iterator to the actual node, is activated or
1901 /// deactivated.<br>
1902 /// If activated, the path to the current node can be received using overloaded
1903 /// methods #CurrentPath and #FullPath.
1904 ///
1905 /// The invocation of the method invalidates this iterator. Note that the
1906 /// path generation can be enabled and disabled with the optional parameter
1907 /// of the overloaded #Initialize methods.
1908 ///
1909 /// @param pathGeneration Denotes whether the path should be generated or not.
1910 void SetPathGeneration( lang::Switch pathGeneration )
1911 {
1912 Invalidate();
1913 actPath.Reset( pathGeneration == lang::Switch::On ? EMPTY_STRING
1914 : NULL_STRING );
1915 }
1916
1917 /// Resets this iterator to work with the given \b %StringTree.
1918 /// Initializes recursive iteration to the tree's root node.
1919 /// Optionally, a recursion depth can be set.
1920 ///
1921 /// @param pTree The \b %StringTree to use.
1922 /// @param depth Sets the recursion depth.
1923 /// A depth of \c 0 iterates only the direct children of the root node.
1924 /// Defaults to <c>std::numeric_limits<unsigned int>::max()</c>
1925 /// for "unlimited" recursion.
1926 void Initialize( cmTree& pTree,
1927 unsigned int depth= (std::numeric_limits<unsigned int>::max)() )
1928 {
1929 initialize( &pTree, &pTree.root.root, depth );
1930 }
1931
1932 /// Resets this iterator to the first child of the node that the given cursor
1933 /// object represents.
1934 /// If the cursor is invalid, the root node of the tree it represents is used.
1935 ///
1936 /// If the given node has no children, this iterator is marked invalid when this
1937 /// method returns.
1938 ///
1939 /// Optional parameter \p{depth} allows limiting the recursion depth.
1940 ///
1941 /// @param cursor The cursor to define the branch of the tree to iterate.
1942 /// @param depth Sets the recursion depth.
1943 /// A depth of \c 0 iterates only the direct children of the node
1944 /// represented by \p{cursor}.
1945 /// Defaults to <c>std::numeric_limits<unsigned int>::max()</c>
1946 /// for "unlimited" recursion.
1947 void Initialize( cmCursor cursor,
1948 unsigned int depth= (std::numeric_limits<unsigned int>::max)() )
1949 {
1950 initialize( static_cast<cmTree*>( cursor.tree ),
1951 cursor.IsValid() ? cursor.node : &cursor.tree->root.root,
1952 depth );
1953 }
1954
1955 /// Resets this iterator to the first child of the node that the given other iterator
1956 /// currently refers to. The given iterator has to be in a valid state.
1957 /// Optionally, a recursion depth can be set.
1958 ///
1959 /// @param other The iterator whose current node becomes the start node for this
1960 /// iterator.
1961 /// @param depth Sets the recursion depth.
1962 /// A depth of \c 0 iterates only the direct children of the node
1963 /// represented by \p{other}.
1964 /// Defaults to <c>std::numeric_limits<unsigned int>::max()</c>
1965 /// for "unlimited" recursion.
1966 void Initialize( const TRecursiveIterator& other,
1967 unsigned int depth= (std::numeric_limits<unsigned int>::max)() )
1968 {
1969 initialize( other.tree, other.node, depth );
1970 }
1971
1972 /// Invalidates this object. After invoking this method, this iterator cannot be
1973 /// used further, until one of the overloaded methods #Initialize is invoked.
1974 /// After the invocation, method #IsValid will return \c false.
1976 {
1977 actDepth= size_t(-1);
1978 }
1979
1980 /// Determines if this is a valid. \b RecursiveIterator instances may become invalid
1981 /// after invocations of one of the methods #Next, #NextSibling or #NextParentSibling
1982 /// (at the end of the iteration) and become valid with the invocation of one of the
1983 /// overloaded methods #Initialize.
1984 ///
1985 /// @return \c true if this is a valid iterator. If invalid, \c false is returned and
1986 /// the iterator must not be evaluated before being initialized.
1987 bool IsValid() const
1988 {
1989 return actDepth != size_t(-1);
1990 }
1991
1992 /// The negation of #IsValid.
1993 ///
1994 /// @return \c false if this is a valid iterator. If invalid, \c true is returned and
1995 /// the iterator must not be evaluated before being initialized.
1996 bool IsInvalid() const
1997 {
1998 return !IsValid();
1999 }
2000
2001
2002 /// Allows switching sorting on or off. If switched on, sorting is performed
2003 /// by the node names in ascending order.
2004 ///
2005 /// This and the overloaded versions of this method may be invoked at any time,
2006 /// even on invalid iterators and those that are not initialized.
2007 /// All that the methods do is store the given parameters for future use.
2008 /// Such a use happens whenever a recursive iteration over a list of child nodes is
2009 /// started. At that moment the current configuration of sorting is applied to
2010 /// the list of direct children.
2011 ///
2012 /// @param sorting The switch value.
2013 void SetSorting( lang::Switch sorting )
2014 {
2015 if( sorting == lang::Switch::Off )
2016 nextIsSorting= false;
2017 else
2018 SetSorting(lang::SortOrder::Ascending, lang::Case::Ignore );
2019 }
2020
2021 /// Sets the sorting of children by their path name, using the built-in comparison
2022 /// methods, which in turn use method \alib{strings;TString::Equals;String::Equals}.
2023 ///
2024 /// \see
2025 /// For more details on sorting see method \ref SetSorting(lang::Switch sorting).
2026 ///
2027 ///
2028 /// @param order The sort order.
2029 /// Defaults to \b %SortOrder::Ascending.
2030 /// @param sensitivity The case sensitivity when comparing path names.
2031 /// Defaults to \b %Case::Ignore.
2032 void SetSorting( lang::SortOrder order = lang::SortOrder::Ascending,
2033 lang::Case sensitivity = lang::Case::Ignore )
2034 {
2035 nextIsSorting = true;
2036 nextCustomSorter = nullptr;
2037 nextSortingIsDescending = ( order == lang::SortOrder::Descending );
2038 nextSortingIsCaseSensitive= ( sensitivity == lang:: Case::Sensitive );
2039 }
2040
2041 /// Sets the sorting of children by their template value, using the given
2042 /// callback function.
2043 ///
2044 /// \see
2045 /// For more details on sorting see method \ref SetSorting(lang::Switch sorting).
2046 ///
2047 /// @param customSorterFunction A custom comparison method used for sorting the children
2048 /// of nodes.
2049 void SetSorting( bool (*customSorterFunction)(const Cursor&, const Cursor&) )
2050 {
2051 nextIsSorting = true;
2052 nextCustomSorter = customSorterFunction;
2053 }
2054
2055 /// Iterates to the first child of the current node. If no such child exists,
2056 /// to the next sibling node. If also no sibling exists, iteration continues
2057 /// with the next available node of a previous recursion level.
2058 ///
2059 /// @return \c true if a next node was found, \c false otherwise.
2060 /// If \c false is returned, this iterator is invalid after the call.
2061 bool Next() {DCSSHRD return next(0); }
2062
2063 /// Omits recursion on the current node's children, even if the current depth
2064 /// is lower than #RequestedDepth.<br>
2065 ///
2066 /// If no sibling exists, iteration continues with the next available node of a
2067 /// previous recursion level.
2068 ///
2069 /// @return \c true if a next node was found, \c false otherwise.
2070 /// If \c false is returned, this iterator is invalid after the call.
2071 bool NextSibling() {DCSSHRD return next(1); }
2072
2073 /// Skips the remaining siblings of the current recursion level and continues with
2074 /// the next available sibling of a previous level.
2075 ///
2076 /// @return \c true if a next node was found, \c false otherwise.
2077 /// If \c false is returned, this iterator is invalid after the call.
2078 bool NextParentSibling() {DCSSHRD return next(2); }
2079
2080
2081 /// Retrieves the current path of walking as a string representation.
2082 /// The path returned is relative to the start node and does not contain a leading
2083 /// separator character. Also, it does not contain the name of the current node,
2084 /// which can be received by invoking method #TCursor::Name on the cursor returned by
2085 /// method #Node.
2086 ///
2087 /// Note that this method can be used only if path generation was activated
2088 /// before the current iteration. Activation is performed with method
2089 /// #SetPathGeneration.
2090 ///
2091 /// @return The path of the current node.
2092 const NameType& CurrentPath() const
2093 {
2094 ALIB_ASSERT_ERROR( actPath.IsNotNull(), "MONOMEM/STRINGTREE",
2095 "Path generation not activated" )
2096 return actPath;
2097 }
2098
2099 /// Writes the results of #CurrentPath and #TCursor::Name, separated by the separator
2100 /// character \p{TSeparator}.
2101 ///
2102 /// Note that this method can be used only if path generation was activated
2103 /// before the current iteration. Activation is performed with method
2104 /// #SetPathGeneration.
2105 ///
2106 /// @param target The target to append the path to.
2107 /// @param targetData Denotes whether \p{target} should be cleared before
2108 /// appending the path. Defaults to CurrentData::Clear.
2109 /// @return The given string to allow concatenated operations
2111 lang::CurrentData targetData= lang::CurrentData::Clear ) const
2112 {
2113 ALIB_ASSERT_ERROR( actPath.IsNotNull(), "MONOMEM/STRINGTREE",
2114 "Path generation not activated" )
2115
2116 if( targetData == lang::CurrentData::Clear )
2117 target.Reset();
2118
2119 if( actPath.IsNotEmpty() )
2120 target << actPath << tree->separator;
2121
2122 return target << node->name.key;
2123 }
2124
2125
2126 /// Returns the requested maximum depth of iteration, set with #Initialize.
2127 ///
2128 /// @see For the current iteration depth, use #CurrentDepth.
2129 ///
2130 ///
2131 /// @return The distance of the current node and the node of the start of the
2132 /// iteration.
2133 int RequestedDepth() const { return int(recursionDepth); }
2134
2135 /// Returns the depth of the current iteration. This is value is available to the
2136 /// algorithm which means this method executes in constant time.
2137 ///
2138 /// To get the absolute depth of the current node, method #TCursor::Depth may be used.
2139 ///
2140 /// @return The distance of the current node and the node of the start of the
2141 /// iteration.
2142 int CurrentDepth() const
2143 {
2144 ALIB_ASSERT_ERROR( IsValid(), "MONOMEM/STRINGTREE",
2145 "RecursiveIterator not initialized or exceeded (invalid)." )
2146 return int(actDepth);
2147 }
2148
2149 /// Returns the current node, encapsulated in a cursor object.
2150 ///
2151 /// \note
2152 /// It is \b not allowed to use method #TCursor::Delete on the node returned by
2153 /// this method. As a replacement, use method #DeleteNode implemented in this
2154 /// class.<br>
2155 /// However, methods #TCursor::DeleteChild and #TCursor::DeleteChildren are allowed
2156 /// to be invoked and therefore have no replacement in this class.
2157 ///
2158 /// @return An instance of the public node interface pointing to the currently
2159 /// referenced tree node.
2161 {
2162 ALIB_ASSERT_ERROR( IsValid(), "MONOMEM/STRINGTREE",
2163 "RecursiveIterator not initialized or exceeded (invalid)." )
2164 return cmCursor( tree, node );
2165 }
2166
2167 //#### node deletion (RecursiveIterator) #############################################
2168
2169 /// Deletes the node that this iterator currently refers to from the tree.
2170 /// After the operation, the iterator is moved forward to the next sibling
2171 /// of the current node, respectively of the first sibling found in the
2172 /// recursion stack.
2173 ///
2174 /// \note
2175 /// This method constitutes a legal alternative to method #TCursor::Delete, which is
2176 /// forbidden to be invoked on the node returned by method #Node as this would
2177 /// invalidate this iterator.<br>
2178 ///
2179 /// Methods #TCursor::DeleteChild and #TCursor::DeleteChildren are allowed with this
2180 /// iterator type. Consequently, no replacement method for those is given with this
2181 /// class.
2182 ///
2183 /// @return The total number of nodes deleted.
2185 {DCS
2186 ALIB_ASSERT_ERROR( IsValid(), "MONOMEM/STRINGTREE",
2187 "RecursiveIterator not initialized or exceeded (invalid)." )
2188 auto& nodeToDelete= *node;
2189 next( 1 ); // next sibling
2190 return nodeToDelete.parent->deleteChild( tree, &nodeToDelete );
2191 }
2192
2193 // #### RecursiveIterator Internals ###################################################
2194 protected:
2195 /// Resets this iterator to represent to the given node of the given tree.
2196 ///
2197 /// @param pTree The tree to iterate on.
2198 /// @param newnode The new node to start the iteration from.
2199 /// @param depth The requested recursion depth.
2200 void initialize( cmTree* pTree, cmNode* newnode, unsigned int depth )
2201 {
2202 this->tree= pTree;
2203 DCSSHRD
2204 if( actPath.IsNotNull() )
2205 {
2206 actPath.Reset();
2207 if( newnode->isRoot() )
2208 actPath << tree->separator;
2209 }
2210
2211 node= newnode;
2212 if( newnode->qtyChildren )
2213 {
2214 recursionDepth= depth;
2215 actDepth= size_t(-1);
2216 recursion();
2217 }
2218 else
2219 actDepth= size_t( -1 );
2220 }
2221
2222 /// Sets this iterator to point to the first child of the actual node.
2223 /// If sorting is enabled, copies all children from the map to a vector and sorts
2224 /// them there.
2226 {
2227 ++actDepth;
2228 if( stack.size() == actDepth )
2229 stack.emplace_back();
2230
2231 auto& rd= stack[actDepth];
2232 rd.customSorter = nextCustomSorter;
2233 rd.isSorting = nextIsSorting;
2234 rd.sortingIsDescending = nextSortingIsDescending;
2235 rd.sortingIsCaseSensitive= nextSortingIsCaseSensitive;
2236
2237 // no sorting: set link to node's child hook
2238 if (!rd.isSorting)
2239 {
2240 rd.childrenUnsorted= &node->children;
2241 node= static_cast<cmNode*>(rd.actChild.unsorted= rd.childrenUnsorted->first());
2242 return;
2243 }
2244
2245 // sorting: copy children to a sortable vector
2246 rd.childrenSorted.clear();
2247 rd.childrenSorted.reserve( size_t( node->qtyChildren ) );
2248 auto* copyIt= node->children.first();
2249 while( copyIt != &node->children.hook )
2250 {
2251 rd.childrenSorted.emplace_back( static_cast<cmNode*>(copyIt) );
2252 copyIt= copyIt->next();
2253 }
2254
2255 // sort
2256 if( rd.customSorter )
2257 {
2258 std::sort( rd.childrenSorted.begin(), rd.childrenSorted.end(),
2259 [this,&rd]( cmNode* lhs,
2260 cmNode* rhs )
2261 {
2262 return rd.customSorter( cmCursor(tree, lhs),
2263 cmCursor(tree, rhs) );
2264 }
2265 );
2266 }
2267 else
2268 {
2269 std::sort( rd.childrenSorted.begin(), rd.childrenSorted.end(),
2270 [&rd]( cmNode* lhs, cmNode* rhs)
2271 {
2272 int compResult= rd.sortingIsCaseSensitive
2273 ? lhs->name.key. template CompareTo<CHK, lang::Case::Sensitive>(rhs->name.key)
2274 : lhs->name.key. template CompareTo<CHK, lang::Case::Ignore >(rhs->name.key);
2275 return rd.sortingIsDescending ? compResult > 0
2276 : compResult < 0;
2277 }
2278 );
2279 }
2280
2281 // set to first child
2282 rd.actChild.sorted= 0;
2283 node= rd.childrenSorted[0];
2284 }
2285
2286
2287 /// Goes to the next node.
2288 /// This method is used with interface methods #Next, #NextSibling and
2289 /// #NextParentSibling, as well as with #DeleteNode}.
2290 ///
2291 /// @param skipMode \c 0 iterates to the first child (if available),
2292 /// \c 1 iterates to the next sibling (if available) and
2293 /// \c 2 to the next available sibling of the parent, respectively the
2294 /// current recursion stack.
2295 /// @return \c true if this iterator is valid (a next node was found), \c false
2296 /// otherwise.
2297 bool next(int skipMode)
2298 {
2299 ALIB_ASSERT_ERROR( actDepth != size_t(-1), "MONOMEM/STRINGTREE",
2300 "Invalid iterator" )
2301
2302 // recursion to first child of actual node?
2303 if( skipMode == 0
2304 && static_cast<unsigned int>( actDepth ) < recursionDepth
2305 && node->qtyChildren )
2306 {
2307 if( actPath.IsNotNull() )
2308 {
2309 if( actPath.IsNotEmpty()
2310 && (actPath.Length() != 1 || actPath.CharAtStart() != tree->separator ) )
2311 actPath << tree->separator;
2312
2313 actPath << node->name.key;
2314 }
2315
2316 // increase stack capacity
2317 if( stack.size() == actDepth + 1 )
2318 stack.emplace_back();
2319
2320 recursion();
2321
2322 return true;
2323 }
2324
2325 for(;;)
2326 {
2327 if( skipMode != 2 )
2328 {
2329 // next sibling
2330 bool foundNextChild;
2331 {
2332 RecursionData& rd= stack[ actDepth ];
2333 if( rd.isSorting )
2334 {
2335 ++rd.actChild.sorted;
2336
2337 if( (foundNextChild= rd.actChild.sorted < rd.childrenSorted.size())
2338 ==true )
2339 node= rd.childrenSorted[rd.actChild.sorted];
2340 }
2341 else
2342 {
2343 node = static_cast<cmNode*>(rd.actChild.unsorted= rd.actChild.unsorted->next());
2344 foundNextChild= (node != &rd.childrenUnsorted->hook);
2345 }
2346 }
2347
2348 if( foundNextChild )
2349 break;
2350 }
2351 skipMode= 0;
2352
2353 // climb down
2354 if( actDepth > 0 )
2355 {
2356 --actDepth;
2357
2358 // remove separator from path
2359 if( actPath.IsNotEmpty() )
2360 {
2361 character lastChar;
2362 do
2363 {
2364 lastChar= actPath.CharAtEnd<NC>();
2365 actPath.DeleteEnd<NC>( 1 );
2366 }
2367 while( lastChar != tree->separator && actPath.IsNotEmpty() );
2368 }
2369 }
2370 else
2371 {
2372 actDepth= size_t(-1);
2373 ALIB_ASSERT( actPath.IsEmpty()
2374 || (actPath.Length() == 1 && actPath.CharAtStart() == tree->separator) )
2375 break;
2376 }
2377 }
2378
2379 return actDepth != size_t(-1);
2380 }
2381
2382 }; // inner class "TRecursiveIterator"
2383
2384 /// The mutable version of type \alib{containers;StringTree::TRecursiveIterator<TConst>}.
2386
2387 /// The constant version of type \alib{containers;StringTree::TRecursiveIterator<TConst>}.
2389
2390
2391 // #############################################################################################
2392 // StringTree Main
2393 // #############################################################################################
2394 #if !DOXYGEN
2395 #if ALIB_DEBUG_CRITICAL_SECTIONS
2396 #undef DCS
2397 #undef DCSSHRD
2398 #define DCS ALIB_DCS_WITH(basetree::nodeTable.dcs)
2399 #define DCSSHRD ALIB_DCS_SHARED_WITH(basetree::nodeTable.dcs)
2400 #endif
2401 #endif
2402
2403 //==============================================================================================
2404 /// Constructor.
2405 /// @param allocator The allocator instance to use.
2406 /// @param pathSeparator The separation character used with path strings.
2407 //==============================================================================================
2408 StringTree( AllocatorType& allocator, CharacterType pathSeparator )
2409 : basetree( allocator, pathSeparator )
2410 {
2411 #if ALIB_DEBUG_CRITICAL_SECTIONS
2412 basetree::nodeTable.dcs.DCSName= "StringTree";
2413 #endif
2414 }
2415
2416 //==============================================================================================
2417 /// Constructor taking a shared recycler.
2418 /// @param pRecycler The shared recycler.
2419 /// @param pathSeparator The separation character used with path strings.
2420 //==============================================================================================
2421 template<typename TSharedRecycler= SharedRecyclerType,
2422 ATMP_T_IF(int, !ATMP_EQ(TSharedRecycler , void)) = 0 >
2423 StringTree( CharacterType pathSeparator, TSharedRecycler& pRecycler )
2424 : basetree( pRecycler, pathSeparator )
2425 {
2426 #if ALIB_DEBUG_CRITICAL_SECTIONS
2427 basetree::nodeTable.dcs.DCSName= "StringTree";
2428 #endif
2429 }
2430
2431 //==============================================================================================
2432 /// Destructor.
2433 /// Raises a warning if \alib{containers::StringTree;ConstructRootValue;a root value was} but
2434 /// not deleted accordingly.
2435 //==============================================================================================
2437 {
2438 for( auto& node : basetree::nodeTable )
2439 TNodeHandler::FreeNode( *this, *static_cast<baseNode*>(&node) );
2440
2441 ALIB_ASSERT_WARNING( basetree::dbgRootDataSet == 0, "MONOMEM/STRINGTREE",
2442 "The root node's value object was set but not deleted before destruction of this StringTree.\n"
2443 "Possible memory leak! To suppress this warning call DestructRootValue() before destruction.\n"
2444 "In case this is not necessary (because the stored type does not leak if not destructed),\n"
2445 "emplace it in macro ALIB_DBG() to remove the call in release compilations." )
2446 }
2447
2448 //==============================================================================================
2449 /// Shortcut to
2450 /// \alib{containers;HashTable::GetAllocator;NodeTable().GetAllocator()}.
2451 /// @return The allocator that was provided in the constructor and stored in the internal
2452 /// #NodeTable.
2453 //==============================================================================================
2455 { return basetree::nodeTable.GetAllocator(); }
2456
2457 //==============================================================================================
2458 /// Returns the path separator character that this string tree works with.
2459 /// @return The path separator character.
2460 //==============================================================================================
2461 constexpr CharacterType Separator() const noexcept
2462 { return basetree::separator; }
2463
2464 #if ALIB_DEBUG_CRITICAL_SECTIONS
2465 /// Sets the critical section name of this string tree. Empty and optimized out if compiler
2466 /// symbol \ref ALIB_DEBUG_CRITICAL_SECTIONS is not set.
2467 /// @param name The name to use with debug-assertions.
2468 void DbgSetDCSName(const char* name) const { basetree::nodeTable.dcs.DCSName= name; }
2469 #else
2470 constexpr void DbgSetDCSName(const char*) const {}
2471 #endif
2472
2473 //==============================================================================================
2474 /// Depending on the use case, it might be appropriate to attach a value of template type \p{T}
2475 /// to the root node of the tree. If so, this can be done with this method. If not done, in debug
2476 /// compilations, method #TCursor::Value will
2477 /// raise an \alib assertion if called on the root node.
2478 ///
2479 /// Custom data that is explicitly attached to the root node with this method has to be
2480 /// deleted explicitly by calling #DestructRootValue before deletion of the tree.
2481 ///
2482 /// @tparam TArgs Types of variadic parameters given with parameter \p{args}.
2483 /// @param args Variadic parameters to be forwarded to the constructor of custom
2484 /// type \p{T} of the child created.
2485 //==============================================================================================
2486 template<typename... TArgs>
2487 void ConstructRootValue( TArgs&&... args )
2488 {
2489 #if ALIB_DEBUG
2490 ALIB_ASSERT_WARNING( basetree::dbgRootDataSet != 1, "MONOMEM/STRINGTREE",
2491 "Root node value is set without prior deletion. Possible memory leak (depending on\n "
2492 "allocation of template type T). This warning is only printed on the first overwrite.")
2493 ++basetree::dbgRootDataSet;
2494 #endif
2495
2496 new (&basetree::root.root.data) T( std::forward<TArgs>(args)... );
2497 }
2498
2499 //==============================================================================================
2500 /// Calls the destructor of the custom data object of type \p{T}, which may explicitly set using
2501 /// #ConstructRootValue.\n
2502 /// If not done, in debug-compilations, an \alib warning is raised in the destructor
2503 /// of this tree.
2504 //==============================================================================================
2506 {
2507 #if ALIB_DEBUG
2508 ALIB_ASSERT_ERROR( basetree::dbgRootDataSet != 0, "MONOMEM/STRINGTREE",
2509 "Deletion of root node data without prior setting (or double deletion)." )
2510 --basetree::dbgRootDataSet;
2511 #endif
2512 basetree::root.root.data.~T();
2513 }
2514
2515 //==============================================================================================
2516 /// Removes all elements from this container. The use of this method is more efficient than
2517 /// deleting the children of the root node.
2518 ///
2519 /// Invokes \alib{containers;HashTable::Clear} on field
2520 /// \alib{containers::detail::StringTreeBase;nodeTable}. As documented with that method, the
2521 /// allocated nodes will be preserved for "recycling" with future insertions.
2522 ///
2523 /// The custom data of the root node is preserved.
2524 //==============================================================================================
2525 void Clear()
2526 {DCS
2527 // clear the nodes in the table, then the table itself
2528 for( auto& node : basetree::nodeTable )
2529 TNodeHandler::FreeNode( *this, *static_cast<baseNode*>(&node) );
2530 basetree::nodeTable.Clear();
2531
2532 // re-initialize root node
2533 basetree::root.root.children.reset();
2534 basetree::root.root.qtyChildren= 0;
2535 }
2536
2537 //==============================================================================================
2538 /// Clears all nodes and values. The use of this method is more efficient than deleting the
2539 /// children of the root node.<br>
2540 /// In addition, depending on template type \p{TNodeHandler}, it may also declare allocated
2541 /// memory for future reuse.<br>
2542 /// The latter is true for type \alib{containers;StringTreeNamesAlloc}.
2543 ///
2544 /// Invokes \alib{containers;HashTable::Reset} on field
2545 /// \alib{containers::detail::StringTreeBase;nodeTable}.
2546 /// As documented with that method, in the case of \alib{containers;Recycling;private recycling},
2547 /// all previously allocated recyclable instances of the internal element type are disposed.
2548 ///
2549 /// \note The value of the root-node, set with #ConstructRootValue is not deleted.
2550 //==============================================================================================
2551 void Reset()
2552 {
2553 {DCS
2554 for( auto& node : basetree::nodeTable )
2555 TNodeHandler::FreeNode( *this, *static_cast<baseNode*>(&node) );
2556 }
2557
2558 basetree::nodeTable.Reset();
2559 basetree::root.root.children.reset();
2560 basetree::root.root.qtyChildren= 0;
2561 }
2562
2563 //==============================================================================================
2564 /// Counts the number of currently allocated but unused (not contained) element nodes
2565 /// that will be recycled with upcoming insertions.
2566 ///
2567 /// \note
2568 /// This method is provided for completeness and unit-testing. It should not be of
2569 /// relevance for common usage.
2570 /// Furthermore, this method is not available (aka does not compile) with instantiations
2571 /// that specify template parameter \p{TRecycling} as
2572 /// \alib{containers;Recycling;None}.
2573 ///
2574 /// @return The number of removed and not yet recycled elements.
2575 //==============================================================================================
2577 { return basetree::nodeTable.RecyclablesCount(); }
2578
2579 //==============================================================================================
2580 /// Returns the overall number of elements contained in this tree.
2581 ///
2582 /// \note
2583 /// This method performs in constant time.
2584 ///
2585 /// @return The number elements contained in this tree.
2586 //==============================================================================================
2588 { return basetree::nodeTable.Size(); }
2589
2590 //==============================================================================================
2591 /// Tests for emptiness.
2592 ///
2593 /// @return \c true if this tree is empty, \c false otherwise.
2594 //==============================================================================================
2595 bool IsEmpty() const
2596 { return basetree::nodeTable.Size() == 0; }
2597
2598 //==============================================================================================
2599 /// Invokes \alib{containers;HashTable::ReserveRecyclables} on the internal hashtable.
2600 ///
2601 /// @see Chapter \ref alib_contmono_containers_recycling_reserving of the Programmer's
2602 /// Manual.
2603 ///
2604 /// @param qty The expected resulting number (or increase) of elements to be stored in
2605 /// this container.
2606 /// @param reference Denotes whether \p{qty} is meant as an absolute size or an
2607 /// increase.
2608 //==============================================================================================
2610 { basetree::nodeTable.ReserveRecyclables( qty, reference ); }
2611
2612 //==============================================================================================
2613 /// Returns the internal \alib{containers;HashTable} used for storing the tree nodes.
2614 /// This may be used to manipulate load factors, for direct iteration over all nodes, etc.<br>
2615 /// \note The returned object should be used with caution to keep the tree and its data
2616 /// consistent.
2617 /// @return The internal node table.
2618 //==============================================================================================
2620 { return basetree::nodeTable; }
2621
2622 //==============================================================================================
2623 /// Returns the internal \alib{containers;HashTable} used for storing the tree nodes.
2624 /// This may be used to manipulate load factors, for direct iteration over all nodes, etc.<br>
2625 /// \note The returned object should be used with caution to keep the tree and its data
2626 /// consistent.
2627 /// @return The internal node table.
2628 //==============================================================================================
2629 const auto& NodeTable() const
2630 { return basetree::nodeTable; }
2631
2632 //==============================================================================================
2633 /// Creates a cursor instance representing the root node.
2634 /// @return A cursor pointing to the root node of this \b %StringTree.
2635 //==============================================================================================
2637 { return Cursor( this, &(basetree::root.root) ); }
2638
2639 //==============================================================================================
2640 /// Creates a \c const cursor instance representing the root node.
2641 /// @return A read-only pointer, pointing to the root node of this \b %StringTree.
2642 //==============================================================================================
2643 const ConstCursor Root() const
2644 { return ConstCursor( this, &(basetree::root.root) ); }
2645
2646 /// Imports a cursor previously exported with #TCursor::Export.
2647 /// @param handle The handle value.
2648 /// @return The imported cursor value.
2650 { return Cursor( this, reinterpret_cast<typename basetree::Node*>(handle.value) ); }
2651
2652 /// Imports a cursor previously exported with #TCursor::Export.
2653 /// @param handle The handle value.
2654 /// @return The imported \c const cursor value.
2656 { return Cursor( this, reinterpret_cast<typename basetree::Node*>(handle.value) ); }
2657
2658 #if !DOXYGEN
2659 #if ALIB_DEBUG_CRITICAL_SECTIONS
2660 #undef DCS
2661 #undef DCSSHRD
2662 #endif
2663 #endif
2664
2665}; // StringTree
2666
2667
2668
2669} // namespace alib::[containers]
2670
2671/// Type alias in namespace \b alib.
2672template<typename TChar, integer TLocalCapacity= 32>
2674
2675/// Type alias in namespace \b alib.
2676template<typename TChar>
2678
2679/// Type alias in namespace \b alib.
2680template<typename TChar>
2682
2683/// Type alias in namespace \b alib.
2684template<typename TAllocator,
2685 typename T,
2686 typename TNodeHandler = StringTreeNamesDynamic<character>,
2687 Recycling TRecycling = Recycling::Private >
2689
2690
2691} // namespace [alib]
2692
2693
2694#endif // HPP_ALIB_MONOMEM_CONTAINERS_STRINGTREE
2695
strings::TAString< typename cmTree::CharacterType, lang::HeapAllocator > & AssemblePath(strings::TAString< typename cmTree::CharacterType, lang::HeapAllocator > &targetString, lang::CurrentData targetData=lang::CurrentData::Clear) const
TCursor CreateChild(const NameType &childName, TArgs &&... args) const
TCursor & operator=(TCursor &&) noexcept=default
bool DeleteChild(const NameType &childName) const
std::pair< TCursor, SubstringType > operator()(const NameType &path) const
std::pair< TCursor, bool > CreateChildIfNotExistent(const NameType &name, TArgs &&... args)
ATMP_IF_T_F(!TConst, StringTree, const StringTree) TStringTree
bool operator!=(const TCursor &other) const
bool GoToCreateChildIfNotExistent(const NameType &name, TArgs &&... args)
SubstringType GoTo(const NameType &path)
ATMP_IF_T_F(!TConst, basetree, const basetree) cmTree
ConstCursorHandle Export() const
int Distance(const TCursor< true > &other) const
TCursor & operator=(const TCursor &) noexcept=default
TCursor(cmTree *pTree, cmNode *pNode) noexcept
TCursor Child(const NameType &name) const
std::pair< TCursor, integer > CreatePathIfNotExistent(const NameType &path, TArgs &&... args)
bool operator==(const TCursor &other) const
integer GoToCreatedPathIfNotExistent(const NameType &path, TArgs &&... args)
ATMP_IF_T_F(!TConst, baseNode, const baseNode) cmNode
strings::TAString< typename cmTree::CharacterType, lang::HeapAllocator > & AssemblePath(strings::TAString< typename cmTree::CharacterType, lang::HeapAllocator > &targetString, const TCursor< true > &parent, lang::CurrentData targetData=lang::CurrentData::Clear) const
bool GoToChild(const NameType &name)
void DeleteChild(TCursor &child) const
ATMP_IF_T_F(!TConst, baseCursor, baseConstCursor) cmCursor
cmTree * tree
The StringTree this iterator belongs to.
ATMP_IF_T_F(!TConst, baseNodeBase, const baseNodeBase) cmNodeBase
void Initialize(cmCursor cursor, unsigned int depth=(std::numeric_limits< unsigned int >::max)())
ATMP_IF_T_F(!TConst, Cursor, ConstCursor) cmCursor
void SetSorting(lang::SortOrder order=lang::SortOrder::Ascending, lang::Case sensitivity=lang::Case::Ignore)
AString & FullPath(AString &target, lang::CurrentData targetData=lang::CurrentData::Clear) const
void initialize(cmTree *pTree, cmNode *newnode, unsigned int depth)
void Initialize(cmTree &pTree, unsigned int depth=(std::numeric_limits< unsigned int >::max)())
ATMP_IF_T_F(!TConst, StringTree, const StringTree) cmTree
ATMP_IF_T_F(!TConst, baseNode, const baseNode) cmNode
void Initialize(const TRecursiveIterator &other, unsigned int depth=(std::numeric_limits< unsigned int >::max)())
cmNode * node
The pointer to the actual node.
void SetSorting(bool(*customSorterFunction)(const Cursor &, const Cursor &))
TNodeHandler HandlerType
Type definition publishing template parameter TNodeHandler.
typename TNodeHandler::CharacterType CharacterType
const auto & NodeTable() const
AllocatorType & GetAllocator() noexcept
TAllocator AllocatorType
Type definition publishing template parameter TAllocator.
void ConstructRootValue(TArgs &&... args)
const ConstCursor Root() const
TCursor< false > Cursor
The mutable version of type StringTree::TCursor<TConst>.
StringTree(AllocatorType &allocator, CharacterType pathSeparator)
StringTree(CharacterType pathSeparator, TSharedRecycler &pRecycler)
Cursor createCursor(baseNode &node)
ConstCursor ImportCursor(ConstCursorHandle handle)
void DbgSetDCSName(const char *name) const
TCursor< true > ConstCursor
The constant version of type StringTree::TCursor<TConst>.
typename strings::TSubstring< CharacterType > SubstringType
constexpr CharacterType Separator() const noexcept
void ReserveRecyclables(integer qty, lang::ValueReference reference)
Cursor ImportCursor(CursorHandle handle)
typename basetree::SharedRecyclerType SharedRecyclerType
TChar CharAtStart() const
Definition string.hpp:466
#define ATMP_IF_T_F( Cond, T, F)
Definition tmp.hpp:50
#define ALIB_WARNING(...)
Definition alib.hpp:1268
#define ALIB_ASSERT_MODULE(modulename)
Definition alib.hpp:223
#define ATMP_ISOF( T, TBase)
Definition tmp.hpp:28
#define ALIB_API
Definition alib.hpp:639
#define ATMP_EQ( T, TEqual)
Definition tmp.hpp:27
#define ALIB_ASSERT_ERROR(cond,...)
Definition alib.hpp:1271
#define ALIB_ASSERT_WARNING(cond,...)
Definition alib.hpp:1272
#define ALIB_DBG(...)
Definition alib.hpp:390
#define ALIB_COMMA
Definition alib.hpp:982
#define ALIB_ASSERT(cond)
Definition alib.hpp:1270
#define ATMP_T_IF(T, Cond)
Definition tmp.hpp:49
ALIB_API uinteger DBG_STATS_STRINGTREE_NAMES
ALIB_API uinteger DBG_STATS_STRINGTREE_NAME_OVERFLOWS
ValueReference
Denotes if a value is interpreted as an absolute or relative number.
Switch
Denotes if sth. is switched on or off.
SortOrder
Denotes sort order.
@ Clear
Chooses to clear existing data.
Case
Denotes upper and lower case character treatment.
Definition alib.cpp:69
lang::uinteger uinteger
Type alias in namespace alib.
Definition integers.hpp:276
constexpr const String EMPTY_STRING
An empty string of the default character type.
Definition string.hpp:2529
characters::character character
Type alias in namespace alib.
constexpr String NULL_STRING
A nulled string of the default character type.
Definition string.hpp:2549
lang::integer integer
Type alias in namespace alib.
Definition integers.hpp:273
See sibling type NC.
Definition alib.hpp:1097
static void InitializeNode(TTree &tree, typename TTree::Node &node)
static void FreeNode(TTree &tree, typename TTree::baseNode &node)
TChar CharacterType
The character type that the StringTree uses for child name and path strings.
ATMP_IF_T_F((TLocalCapacity > 0), strings::TLocalString< TChar ALIB_COMMA TLocalCapacity ALIB_COMMA lang::HeapAllocator >, strings::TString< TChar >) NameStringType
The string-type of a node's name.
static void InitializeNode(TTree &tree, typename TTree::Node &node)
TChar CharacterType
The character type that the StringTree uses for child name and path strings.
static void FreeNode(TTree &tree, typename TTree::Node &node)
static void InitializeNode(TTree &tree, typename TTree::Node &node)
TChar CharacterType
The character type that the StringTree uses for child name and path strings.
static void FreeNode(TTree &tree, typename TTree::Node &node)
A handle type used with methods TCursor::Export and ImportCursor.
bool operator==(const ConstCursorHandle &other) const noexcept
uinteger value
The encapsulated value.
bool operator==(const CursorHandle &other) const noexcept
A handle type used with methods TCursor::Export and ImportCursor.
uinteger value
The encapsulated value.
bool operator==(const CursorHandle &other) const noexcept
Protected, internal struct used to store the data of recursive iterations.
union alib::containers::StringTree::TRecursiveIterator::RecursionData::@1 actChild
std::vector< cmNode * > childrenSorted
A pointer to a dynamically allocated vector of children used with sorting.
RecursionData() noexcept=default
Trivial default constructor.
bool checkChildName(const NameType &name) const
HashTable< TAllocator, typename NodeKey::ValueDescriptor, typename NodeKey::Hash, typename NodeKey::EqualTo, lang::Caching::Enabled, TRecycling > nodeTable
TNode hook
The root node. Points twice to itself when the list is empty.
Definition bidilist.hpp:144
Node root
Full version of the root node, without initialization of member T.