A trie library.
#include <algorithm>
#include <cassert>
#include <functional>
#include <iterator>
#include <memory>
#include <string>
#include <string_view>
#include <vector>
#include <boost/stl_interfaces/iterator_interface.hpp>
namespace usage_tetengo::trie
{
void search()
{
std::vector<std::string> building_observer_reports{};
[&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"); }
};
{ "tasakibashi", -5 },
{ "nihongiguchi", -3 },
{ "kumamotoekimae", 0 },
{ "gionbashi", 5 },
{ "gofukumachi", 10 },
{ "kawaramachi", 14 },
{ "keitokukoumae", 18 },
{ "karashimachou", 22 },
},
building_observer_set };
assert(
(building_observer_reports == std::vector<std::string>{
"gionbashi",
"gofukumachi",
"karashimachou",
"kawaramachi",
"keitokukoumae",
"kumamotoekimae",
"nihongiguchi",
"tasakibashi",
"DONE",
}));
[[maybe_unused]] const int* const p_found_for_gionbashi = trie_.find("gionbashi");
assert(p_found_for_gionbashi);
assert(*p_found_for_gionbashi == 5);
[[maybe_unused]] const int* const p_found_for_hanabatachou = trie_.find("hanabatachou");
assert(!p_found_for_hanabatachou);
const auto p_subtrie = trie_.subtrie("ka");
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,
14,
}));
}
}
A default serializer.
Definition default_serializer.hpp:36
A trie.
Definition trie.hpp:225
The building observer set type.
Definition trie.hpp:45
#include <assert.h>
#include <string.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()
{
const int initial_values[] = {
-5, -3, 0, 5, 10, 14, 18, 22,
};
{ "tasakibashi", NULL },
{ "nihongiguchi", NULL },
{ "kumamotoekimae", NULL },
{ "gionbashi", NULL },
{ "gofukumachi", NULL },
{ "kawaramachi", NULL },
{ "keitokukoumae", NULL },
{ "karashimachou", NULL },
};
{
initial_elements[i].
p_value = &initial_values[i];
}
char building_observer_reports[128] = { '\0' };
initial_elements,
sizeof(int),
adding_observer,
building_observer_reports,
done_observer,
building_observer_reports,
assert(
strcmp(
building_observer_reports,
"gionbashi\n"
"gofukumachi\n"
"karashimachou\n"
"kawaramachi\n"
"keitokukoumae\n"
"kumamotoekimae\n"
"nihongiguchi\n"
"tasakibashi\n"
"DONE") == 0);
{
(void)p_found_for_gionbashi;
assert(p_found_for_gionbashi);
assert(*p_found_for_gionbashi == 5);
}
{
(void)p_found_for_hanabatachou;
assert(!p_found_for_hanabatachou);
}
size_t subtrie_value_count = 0;
{
subtrie_values[subtrie_value_count] = *p_value;
++subtrie_value_count;
}
assert(subtrie_value_count == 2U);
assert(subtrie_values[0] == 22);
assert(subtrie_values[1] == 14);
}
An element type.
Definition trie.h:38
const void * p_value
Definition trie.h:43
void tetengo_trie_trieIterator_destroy(const tetengo_trie_trieIterator_t *p_iterator)
Destroys an iterator.
const void * tetengo_trie_trieIterator_get(const tetengo_trie_trieIterator_t *p_iterator)
Dereferences the iterator.
void tetengo_trie_trieIterator_next(tetengo_trie_trieIterator_t *p_iterator)
Increments the iterator.
bool tetengo_trie_trieIterator_hasNext(const tetengo_trie_trieIterator_t *p_iterator)
Returns true when the iterator will return more elements.
tetengo_trie_trie_t * tetengo_trie_trie_create(const tetengo_trie_trieElement_t *p_elements, size_t element_count, size_t element_value_size, tetengo_trie_trie_addingObserver_t adding_observer, void *p_adding_observer_context, tetengo_trie_trie_doneObserver_t done_observer, void *p_done_observer_context, size_t double_array_density_factor)
Creates a trie.
void tetengo_trie_trie_destroy(const tetengo_trie_trie_t *p_trie)
Destroys a trie.
size_t tetengo_trie_trie_defaultDoubleArrayDensityFactor(void)
Returns the default double array density factor.
tetengo_trie_trieIterator_t * tetengo_trie_trie_createIterator(const tetengo_trie_trie_t *p_trie)
Creates an iterator.
const void * tetengo_trie_trie_find(const tetengo_trie_trie_t *p_trie, const char *key)
Finds the value object correspoinding the given key.
const tetengo_trie_trie_t * tetengo_trie_trie_subtrie(const tetengo_trie_trie_t *p_trie, const char *key_prefix)
Creates a subtrie.