tetengo::trie Namespace Reference

A trie library. More...

Classes
class	default_deserializer
	A default deserializer. More...
class	default_serializer
	A default serializer. More...
class	double_array
	A double array. More...
class	double_array_iterator
	A double array iterator. More...
class	memory_storage
	A memory storage. More...
class	mmap_storage
	An mmap storage. More...
class	shared_storage
	A shared storage. More...
class	storage
	A storage. More...
class	trie
	A trie. More...
class	trie_impl
	An implementation of trie. More...
class	trie_iterator
	A trie iterator. More...
class	trie_iterator_impl
	An implementation of trie iterator. More...
class	value_deserializer
	A value deserializer. More...
class	value_serializer
	A value serializer. More...

Detailed Description

A trie library.

Usage

Search

C++

#include <algorithm>
#include <cassert>
#include <functional>
#include <iterator>
#include <memory>
#include <string>
#include <string_view>
#include <vector>
 
#include <boost/stl_interfaces/iterator_interface.hpp> // IWYU pragma: keep
 
#include <tetengo/trie/default_serializer.hpp>
#include <tetengo/trie/trie.hpp>
#include <tetengo/trie/trie_iterator.hpp>
 
 
namespace usage_tetengo::trie
{
    void search()
    {
        // Prepares a trie building observer set.
        // The observer set records the inserted keys and the end.
        std::vector<std::string>                                                building_observer_reports{};
        const tetengo::trie::trie<std::string, int>::building_observer_set_type building_observer_set{
            [&building_observer_reports](const std::string_view& key) {
                building_observer_reports.push_back(std::string{ key });
            },
            [&building_observer_reports]() { building_observer_reports.push_back("DONE"); }
        };
 
        // Builds a trie with initial elements.
        const tetengo::trie::trie<std::string, int> trie_{ {
                                                               { "tasakibashi", -5 },
                                                               { "nihongiguchi", -3 },
                                                               { "kumamotoekimae", 0 },
                                                               { "gionbashi", 5 },
                                                               { "gofukumachi", 10 },
                                                               { "kawaramachi", 14 },
                                                               { "keitokukoumae", 18 },
                                                               { "karashimachou", 22 },
                                                           },
                                                           tetengo::trie::default_serializer<std::string>{ true },
                                                           building_observer_set };
        assert(
            (building_observer_reports == std::vector<std::string>{
                                              "gionbashi",
                                              "gofukumachi",
                                              "karashimachou",
                                              "kawaramachi",
                                              "keitokukoumae",
                                              "kumamotoekimae",
                                              "nihongiguchi",
                                              "tasakibashi",
                                              "DONE",
                                          }));
 
        // Searches the trie.
        // If a perfect-matching key is found, its value is returned.
        [[maybe_unused]] const int* const p_found_for_gionbashi = trie_.find("gionbashi");
        assert(p_found_for_gionbashi);
        assert(*p_found_for_gionbashi == 5);
 
        // If not found, nullptr is returned.
        [[maybe_unused]] const int* const p_found_for_hanabatachou = trie_.find("hanabatachou");
        assert(!p_found_for_hanabatachou);
 
        // Creates a subtrie consisting of the elements with the common key prefix.
        const auto p_subtrie = trie_.subtrie("ka");
 
        // Enumerates the values in the subtrie.
        std::vector<int> subtrie_values{};
        std::copy(std::begin(*p_subtrie), std::end(*p_subtrie), std::back_inserter(subtrie_values));
        assert(
            (subtrie_values == std::vector<int>{
                                   22, // karashimachou
                                   14, // kawaramachi
                               }));
    }
}

C

#include <assert.h>
#include <string.h>
 
#include <tetengo/trie/trie.h>
#include <tetengo/trie/trieIterator.h>
 
 
static void adding_observer(const char* const serialized_key, void* const p_context)
{
    strcat((char*)p_context, serialized_key);
    strcat((char*)p_context, "\n");
}
 
static void done_observer(void* const p_context)
{
    strcat((char*)p_context, "DONE");
}
 
void usage_tetengo_trie_search()
{
    // Prepares initial elements.
    const int initial_values[] = {
        -5, -3, 0, 5, 10, 14, 18, 22,
    };
    tetengo_trie_trieElement_t initial_elements[] = {
        // clang-format off
        { "tasakibashi", NULL },
        { "nihongiguchi", NULL },
        { "kumamotoekimae", NULL },
        { "gionbashi", NULL },
        { "gofukumachi", NULL },
        { "kawaramachi", NULL },
        { "keitokukoumae", NULL },
        { "karashimachou", NULL },
        // clang-format on
    };
    for (size_t i = 0; i < sizeof(initial_elements) / sizeof(tetengo_trie_trieElement_t); ++i)
    {
        initial_elements[i].p_value = &initial_values[i];
    }
 
    // Builds a trie with the initial elements.
    char                             building_observer_reports[128] = { '\0' };
    const tetengo_trie_trie_t* const p_trie = tetengo_trie_trie_create(
        initial_elements,
        sizeof(initial_elements) / sizeof(tetengo_trie_trieElement_t),
        sizeof(int),
        adding_observer,
        building_observer_reports,
        done_observer,
        building_observer_reports,
        tetengo_trie_trie_defaultDoubleArrayDensityFactor());
    assert(
        strcmp(
            building_observer_reports,
            "gionbashi\n"
            "gofukumachi\n"
            "karashimachou\n"
            "kawaramachi\n"
            "keitokukoumae\n"
            "kumamotoekimae\n"
            "nihongiguchi\n"
            "tasakibashi\n"
            "DONE") == 0);
 
    // Searches the trie.
    {
        // If a perfect-matching key is found, its value is returned.
        const int* const p_found_for_gionbashi = (const int*)tetengo_trie_trie_find(p_trie, "gionbashi");
        (void)p_found_for_gionbashi;
        assert(p_found_for_gionbashi);
        assert(*p_found_for_gionbashi == 5);
    }
    {
        // If not found, NULL is returned.
        const int* const p_found_for_hanabatachou = (const int*)tetengo_trie_trie_find(p_trie, "hanabatachou");
        (void)p_found_for_hanabatachou;
        assert(!p_found_for_hanabatachou);
    }
 
    // Creates a subtrie consisting of the elements with the common key prefix.
    const tetengo_trie_trie_t* const p_subtrie = tetengo_trie_trie_subtrie(p_trie, "ka");
 
    // Enumerates the values in the subtrie.
    int    subtrie_values[sizeof(initial_elements) / sizeof(tetengo_trie_trieElement_t)] = { 0 };
    size_t subtrie_value_count = 0;
    tetengo_trie_trieIterator_t* const p_iterator = tetengo_trie_trie_createIterator(p_subtrie);
    while (tetengo_trie_trieIterator_hasNext(p_iterator))
    {
        const int* const p_value = (const int*)tetengo_trie_trieIterator_get(p_iterator);
        subtrie_values[subtrie_value_count] = *p_value;
        ++subtrie_value_count;
        tetengo_trie_trieIterator_next(p_iterator);
    }
    tetengo_trie_trieIterator_destroy(p_iterator);
    assert(subtrie_value_count == 2U);
    assert(subtrie_values[0] == 22); // karashimachou
    assert(subtrie_values[1] == 14); // kawaramachi
 
    // Destroys the subtrie.
    tetengo_trie_trie_destroy(p_subtrie);
 
    // Destroys the trie.
    tetengo_trie_trie_destroy(p_trie);
}