ball_categorymanager_radixtree

Detailed Description

Provide a space-efficient associative container for string keys.

Outline

• Purpose
• Classes
• Description
  • Features
  • Usage
    • Example 1: Basic Usage

Purpose

Provide a space-efficient associative container for string keys.

Classes

• ball::CategoryManager_RadixTree: space-efficient string-key assoc container

Description

This component implements ball::CategoryManager_RadixTree, a space-efficient associative container that stores key-value pairs where keys are strings (or string-like types). A radix tree (also known as a compressed trie or prefix tree) achieves space efficiency by sharing common prefixes among keys, making it particularly suitable for storing large sets of strings with common prefixes.

Features

The ball::CategoryManager_RadixTree provides the following features:

• Space-efficient storage of string keys with common prefixes
• O(k) insertion, lookup, and removal where k is the key length
• Support for custom value types
• Visitor pattern for traversing all key-value pairs
• Full allocator support for value-semantic behavior

Usage

This section illustrates intended use of this component.

Example 1: Basic Usage

Suppose we want to store a mapping of words to their definitions. Using ball::CategoryManager_RadixTree allows us to efficiently store many words that share common prefixes.

First, we create a radix tree:

ball::CategoryManager_RadixTree<bsl::string> dictionary;

Then, we insert some words and their definitions:

dictionary.emplace("car",  "a road vehicle with four wheels");
dictionary.emplace("card", "a piece of stiff paper");
dictionary.emplace("care", "the provision of what is needed");
dictionary.emplace("cat",  "a small domesticated carnivorous mammal");

Next, we can look up definitions:

bsl::optional<bsl::reference_wrapper<bsl::string> > definition =
                                                dictionary.find("car");
assert(definition.has_value());
assert(definition->get() == "a road vehicle with four wheels");

We can also check if a key exists:

assert(dictionary.contains("card"));
assert(!dictionary.contains("dog"));

We can find the longest prefix of a key that exists in the tree:

ball::CategoryManager_RadixTree<bsl::string>::OptValueRef optValue;
bsl::string_view prefix = dictionary.findLongestCommonPrefix(&optValue,
                                                             "cards");
assert(prefix == "card");
assert(optValue.has_value() && optValue->get() == "a piece of stiff paper");
prefix = dictionary.findLongestCommonPrefix(&optValue, "carpet");
assert(prefix == "car");
assert(optValue.has_value()
    && optValue->get() == "a road vehicle with four wheels");
prefix = dictionary.findLongestCommonPrefix(&optValue, "dog");
assert(prefix == "");
assert(!optValue.has_value());

We can run a functor for all entries:

struct Printer {
    void operator()(const bsl::string_view& key,
                    const bsl::string&      value) const {
        bsl::cout << key << ": " << value << bsl::endl;
    }
};
dictionary.forEach(Printer());

We can run a functor for all entries with a given prefix:

struct PrefixCollector {
    bsl::vector<bsl::string> *d_vec_p;
    PrefixCollector(bsl::vector<bsl::string> *vec) : d_vec_p(vec) {}
    void operator()(const bsl::string_view& key,
                    const bsl::string&      value) const {
        d_vec_p->push_back(bsl::string(key));
    }
};
bsl::vector<bsl::string> found;
PrefixCollector          collector(&found);
dictionary.forEachPrefix("car", collector);
assert(found.size() == 3);
bool foundCar  = false;
bool foundCard = false;
bool foundCare = false;
for (bsl::size_t i = 0; i < found.size(); ++i) {
    if (found[i] == "car") {
        foundCar = true;
    } else if (found[i] == "card") {
        foundCard = true;
    } else if (found[i] == "care") {
        foundCare = true;
    }
}
assert(foundCar);
assert(foundCard);
assert(foundCare);

We can also mutate values for all entries with a given prefix:

struct SuffixAppender {
    void operator()(const bsl::string_view&, bsl::string& value) const {
        value += "!";
    }
};
dictionary.forEachPrefix("car", SuffixAppender());
assert(dictionary.find("car")->get() ==
                                        "a road vehicle with four wheels!");
assert(dictionary.find("card")->get() ==         "a piece of stiff paper!");
assert(dictionary.find("care")->get() ==
                                        "the provision of what is needed!");

Finally, we can remove entries:

dictionary.erase("card"); assert(!dictionary.contains("card"));