[#BloombergLP-ball-CategoryManager_RadixTree]
= xref:BloombergLP.adoc[BloombergLP]::xref:BloombergLP/ball.adoc[ball]::CategoryManager_RadixTree
:relfileprefix: ../../
:mrdocs:

This class template implements a space‐efficient associative container that maps string keys to values of the specified `t_VALUE` type. The container uses a radix tree (compressed trie) data structure, which shares common prefixes among keys. The container provides O(k) insertion, lookup, and removal operations, where k is the key length.

== Synopsis

Declared in `<ball_categorymanager_radixtree.h>`

[source,cpp,subs="verbatim,replacements,macros,-callouts"]
----
template<class t_VALUE>
class CategoryManager_RadixTree;
----

== Type Aliases

[cols="1,4"]
|===
| Name| Description
| xref:BloombergLP/ball/CategoryManager_RadixTree/EmplaceResult.adoc[`EmplaceResult`] 
| The return type of adding a value to the tree with `emplace()`. It is _not_ the usual `insert` return type, because this data structure does not provide an iterator. The `.first` boolean is `true` if an element was inserted, and the `.second` data member is a reference to the (possibly newly created) value. Notice that if the value existed (`.first == false`) the reference wrapper will still give access to the value of that node; the `.second` is always a valid mutable reference to the value belonging to the key used in the `emplace` call.
| xref:BloombergLP/ball/CategoryManager_RadixTree/OptValueCRef.adoc[`OptValueCRef`] 
| Type for immutable access to the optional value. Used also as return type for immutable finders where empty optional signifies "not found".
| xref:BloombergLP/ball/CategoryManager_RadixTree/OptValueRef.adoc[`OptValueRef`] 
| Type for mutable access to the optional value. Used also as return type for mutable finders where empty optional signifies "not found".
| xref:BloombergLP/ball/CategoryManager_RadixTree/allocator_type.adoc[`allocator_type`] 
| `allocator_type` is an alias for the type of allocator used by this class.
| xref:BloombergLP/ball/CategoryManager_RadixTree/size_type.adoc[`size_type`] 
| `size_type` is an alias for the type used to represent sizes in this tree.
| xref:BloombergLP/ball/CategoryManager_RadixTree/value_type.adoc[`value_type`] 
| `value_type` is an alias for the value type stored in this tree.
|===


== Member Functions

[cols="1,4"]
|===
| Name| Description
| xref:BloombergLP/ball/CategoryManager_RadixTree/2constructor-0e.adoc[`CategoryManager_RadixTree`]         [.small]#[constructor]#
| Constructors
| xref:BloombergLP/ball/CategoryManager_RadixTree/operator_assign-0c.adoc[`operator=`] 
| Assignment operators
| xref:BloombergLP/ball/CategoryManager_RadixTree/clear.adoc[`clear`] 
| Remove all entries from this tree. After this call `empty()` will return `true`. After this call the tree will have 0 nodes.
| xref:BloombergLP/ball/CategoryManager_RadixTree/contains.adoc[`contains`] 
| Return `true` if this tree contains an entry for the specified `key`, and `false` otherwise.
| xref:BloombergLP/ball/CategoryManager_RadixTree/countNodes.adoc[`countNodes`] 
| Return the total number of nodes in this tree, including internal nodes without values. Note that this method has O(n) complexity where n is the number of nodes, and is intended for use in testing to verify tree structure invariants. In user code use `size()` that tells the actual number of entries with values.
| xref:BloombergLP/ball/CategoryManager_RadixTree/emplace.adoc[`emplace`] 
| Insert into this tree an entry with the specified `key` and a newly created `t_VALUE` object, constructed by forwarding `get_allocator()` (if required) and the specified (variable number of) `args` to the corresponding constructor of `t_VALUE`. Return a pair consisting of a reference to the value associated with `key` (whether newly inserted or already existing) and a boolean indicating whether insertion took place (`true` if the key was not already present, `false` otherwise). This method requires that `t_VALUE` be `emplace‐constructible` from `args`.
| xref:BloombergLP/ball/CategoryManager_RadixTree/empty.adoc[`empty`] 
| Return `true` if this tree contains no entries, and `false` otherwise.
| xref:BloombergLP/ball/CategoryManager_RadixTree/erase.adoc[`erase`] 
| Remove from this tree the entry with the specified `key`. Return `true` if the entry was removed (key existed), and `false` otherwise.
| xref:BloombergLP/ball/CategoryManager_RadixTree/eraseChildrenOfPrefix.adoc[`eraseChildrenOfPrefix`] 
| Remove all children of the entry matching the specified `prefix`, but not the entry with the prefix itself. If unused (no value, no children) nodes remain remove those, too. If no entry exists for `prefix` remove nothing. Return the number of entries removed.
| xref:BloombergLP/ball/CategoryManager_RadixTree/erasePrefix.adoc[`erasePrefix`] 
| Remove from this tree all entries with keys that have the specified `prefix`, including the entry for the `prefix` itself if it exists. Return the number of entries removed. Note that this method removes all nodes whose keys start with `prefix`, not just those that have a value.
| xref:BloombergLP/ball/CategoryManager_RadixTree/find-00.adoc[`find`] 
| `find` overloads
| xref:BloombergLP/ball/CategoryManager_RadixTree/findLongestCommonPrefix-0a.adoc[`findLongestCommonPrefix`] 
| `findLongestCommonPrefix` overloads
| xref:BloombergLP/ball/CategoryManager_RadixTree/forEach-0a.adoc[`forEach`] 
| `forEach` overloads
| xref:BloombergLP/ball/CategoryManager_RadixTree/forEachPrefix-0f.adoc[`forEachPrefix`] 
| `forEachPrefix` overloads
| xref:BloombergLP/ball/CategoryManager_RadixTree/get_allocator.adoc[`get_allocator`] 
| Return the allocator used by this object to supply memory. Note that if no allocator was supplied at construction the default allocator in effect at construction is used.
| xref:BloombergLP/ball/CategoryManager_RadixTree/printNodes.adoc[`printNodes`] 
| Write the value of this object to the specified output `stream` in a human‐readable format, and return a non‐`const` reference to `stream`. Optionally specify an initial indentation `level`, whose absolute value is incremented recursively for nested objects. If `level` is specified, optionally specify `spacesPerLevel`, whose absolute value indicates the number of spaces per indentation level for this and all of its nested objects. If `level` is negative, suppress indentation of the first line. If `spacesPerLevel` is negative, format the entire output on one line, suppressing all but the initial indentation (as governed by `level`). If `stream` is not valid on entry, this operation has no effect. Note that the format is not fully specified, and may change without notice.
| xref:BloombergLP/ball/CategoryManager_RadixTree/size.adoc[`size`] 
| Return the number of entries in this tree.
| xref:BloombergLP/ball/CategoryManager_RadixTree/swap.adoc[`swap`] 
| Efficiently exchange the value of this object with the value of the specified `other` object. This method provides the no‐throw exception‐safety guarantee. The behavior is undefined unless this object was created with the same allocator as `other`.
|===


== Friends

[cols="1,4"]
|===
| Name| Description
| `xref:BloombergLP/ball/swap-09.adoc[BloombergLP::ball::swap]`
| Exchange the values of the specified trees.
| `xref:BloombergLP/ball/operator_eq-03f.adoc[BloombergLP::ball::operator==]`
| Return `true` if the specified trees have the same value.
|===

== Non-Member Functions

[cols="1,4"]
|===
| Name| Description
| xref:BloombergLP/ball/operator_not_eq-0a7a.adoc[`operator!=`]
| Return `true` if the specified `lhs` and `rhs` objects do not have the same value, and `false` otherwise. Two `CategoryManager_RadixTree` objects do not have the same value if they differ in their number of entries or if any key maps to different values in the two objects.
| xref:BloombergLP/ball/operator_eq-05.adoc[`operator==`]
| Return `true` if the specified `lhs` and `rhs` objects have the same value, and `false` otherwise. Two `CategoryManager_RadixTree` objects have the same value if they have the same number of entries and each key in `lhs` maps to the same value as in `rhs`.
| xref:BloombergLP/ball/swap-06.adoc[`swap`]
| Exchange the values of the specified `a` and `b` objects. This function provides the no‐throw exception‐safety guarantee if the two objects were created with the same allocator and the basic guarantee otherwise.
|===


[.small]#Created with https://www.mrdocs.com[MrDocs]#