[#BloombergLP-ball-CategoryManager_RadixTree]
= xref:BloombergLP.adoc[BloombergLP]::xref:BloombergLP/ball.adoc[ball]::CategoryManager&lowbar;RadixTree
:relfileprefix: ../../
:mrdocs:

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

== Synopsis

Declared in `&lt;ball&lowbar;categorymanager&lowbar;radixtree&period;h&gt;`

[source,cpp,subs="verbatim,replacements,macros,-callouts"]
----
template&lt;class t&lowbar;VALUE&gt;
class CategoryManager&lowbar;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()`&period; It is _not_ the usual `insert` return type, because this data structure does not provide an iterator&period; The `&period;first` boolean is `true` if an element was inserted, and the `&period;second` data member is a reference to the (possibly newly created) value&period; Notice that if the value existed (`&period;first &equals;&equals; false`) the reference wrapper will still give access to the value of that node&semi; the `&period;second` is always a valid mutable reference to the value belonging to the key used in the `emplace` call&period;
| xref:BloombergLP/ball/CategoryManager_RadixTree/OptValueCRef.adoc[`OptValueCRef`] 
| Type for immutable access to the optional value&period; Used also as return type for immutable finders where empty optional signifies &quot;not found&quot;&period;
| xref:BloombergLP/ball/CategoryManager_RadixTree/OptValueRef.adoc[`OptValueRef`] 
| Type for mutable access to the optional value&period; Used also as return type for mutable finders where empty optional signifies &quot;not found&quot;&period;
| xref:BloombergLP/ball/CategoryManager_RadixTree/allocator_type.adoc[`allocator&lowbar;type`] 
| `allocator&lowbar;type` is an alias for the type of allocator used by this class&period;
| xref:BloombergLP/ball/CategoryManager_RadixTree/size_type.adoc[`size&lowbar;type`] 
| `size&lowbar;type` is an alias for the type used to represent sizes in this tree&period;
| xref:BloombergLP/ball/CategoryManager_RadixTree/value_type.adoc[`value&lowbar;type`] 
| `value&lowbar;type` is an alias for the value type stored in this tree&period;
|===


== Member Functions

[cols="1,4"]
|===
| Name| Description
| xref:BloombergLP/ball/CategoryManager_RadixTree/2constructor-0e.adoc[`CategoryManager&lowbar;RadixTree`]         [.small]#[constructor]#
| Constructors
| xref:BloombergLP/ball/CategoryManager_RadixTree/operator_assign-0c.adoc[`operator&equals;`] 
| Assignment operators
| xref:BloombergLP/ball/CategoryManager_RadixTree/clear.adoc[`clear`] 
| Remove all entries from this tree&period; After this call `empty()` will return `true`&period; After this call the tree will have 0 nodes&period;
| xref:BloombergLP/ball/CategoryManager_RadixTree/contains.adoc[`contains`] 
| Return `true` if this tree contains an entry for the specified `key`, and `false` otherwise&period;
| xref:BloombergLP/ball/CategoryManager_RadixTree/countNodes.adoc[`countNodes`] 
| Return the total number of nodes in this tree, including internal nodes without values&period; 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&period; In user code use `size()` that tells the actual number of entries with values&period;
| xref:BloombergLP/ball/CategoryManager_RadixTree/emplace.adoc[`emplace`] 
| Insert into this tree an entry with the specified `key` and a newly created `t&lowbar;VALUE` object, constructed by forwarding `get&lowbar;allocator()` (if required) and the specified (variable number of) `args` to the corresponding constructor of `t&lowbar;VALUE`&period; 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)&period; This method requires that `t&lowbar;VALUE` be `emplace&hyphen;constructible` from `args`&period;
| xref:BloombergLP/ball/CategoryManager_RadixTree/empty.adoc[`empty`] 
| Return `true` if this tree contains no entries, and `false` otherwise&period;
| xref:BloombergLP/ball/CategoryManager_RadixTree/erase.adoc[`erase`] 
| Remove from this tree the entry with the specified `key`&period; Return `true` if the entry was removed (key existed), and `false` otherwise&period;
| 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&period; If unused (no value, no children) nodes remain remove those, too&period; If no entry exists for `prefix` remove nothing&period; Return the number of entries removed&period;
| 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&period; Return the number of entries removed&period; Note that this method removes all nodes whose keys start with `prefix`, not just those that have a value&period;
| 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&lowbar;allocator`] 
| Return the allocator used by this object to supply memory&period; Note that if no allocator was supplied at construction the default allocator in effect at construction is used&period;
| xref:BloombergLP/ball/CategoryManager_RadixTree/printNodes.adoc[`printNodes`] 
| Write the value of this object to the specified output `stream` in a human&hyphen;readable format, and return a non&hyphen;`const` reference to `stream`&period; Optionally specify an initial indentation `level`, whose absolute value is incremented recursively for nested objects&period; 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&period; If `level` is negative, suppress indentation of the first line&period; If `spacesPerLevel` is negative, format the entire output on one line, suppressing all but the initial indentation (as governed by `level`)&period; If `stream` is not valid on entry, this operation has no effect&period; Note that the format is not fully specified, and may change without notice&period;
| xref:BloombergLP/ball/CategoryManager_RadixTree/size.adoc[`size`] 
| Return the number of entries in this tree&period;
| xref:BloombergLP/ball/CategoryManager_RadixTree/swap.adoc[`swap`] 
| Efficiently exchange the value of this object with the value of the specified `other` object&period; This method provides the no&hyphen;throw exception&hyphen;safety guarantee&period; The behavior is undefined unless this object was created with the same allocator as `other`&period;
|===


== Friends

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

== Non-Member Functions

[cols="1,4"]
|===
| Name| Description
| xref:BloombergLP/ball/operator_not_eq-0a7a.adoc[`operator!&equals;`]
| Return `true` if the specified `lhs` and `rhs` objects do not have the same value, and `false` otherwise&period; Two `CategoryManager&lowbar;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&period;
| xref:BloombergLP/ball/operator_eq-05.adoc[`operator&equals;&equals;`]
| Return `true` if the specified `lhs` and `rhs` objects have the same value, and `false` otherwise&period; Two `CategoryManager&lowbar;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`&period;
| xref:BloombergLP/ball/swap-06.adoc[`swap`]
| Exchange the values of the specified `a` and `b` objects&period; This function provides the no&hyphen;throw exception&hyphen;safety guarantee if the two objects were created with the same allocator and the basic guarantee otherwise&period;
|===


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