summaryrefslogtreecommitdiffstats
path: root/test/trie_map/test_main.cpp
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--test/trie_map/test_main.cpp1909
1 files changed, 1909 insertions, 0 deletions
diff --git a/test/trie_map/test_main.cpp b/test/trie_map/test_main.cpp
new file mode 100644
index 0000000..3b7aa19
--- /dev/null
+++ b/test/trie_map/test_main.cpp
@@ -0,0 +1,1909 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*************************************************************************
+ *
+ * Copyright (c) 2015-2018 Kohei Yoshida
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+ * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ * OTHER DEALINGS IN THE SOFTWARE.
+ *
+ ************************************************************************/
+
+#define MDDS_TRIE_MAP_DEBUG 1
+#include "test_global.hpp" // This must be the first header to be included.
+//#define MDDS_TRIE_MAP_DEBUG_DUMP_TRIE 1
+//#define MDDS_TRIE_MAP_DEBUG_DUMP_PACKED 1
+
+#include "mdds/trie_map.hpp"
+#include "mdds/global.hpp"
+
+#include <iterator>
+#include <fstream>
+#include <vector>
+#include <list>
+
+using namespace std;
+using namespace mdds;
+
+using packed_int_map_type = packed_trie_map<trie::std_string_traits, int>;
+using packed_str_map_type = packed_trie_map<trie::std_string_traits, std::string>;
+
+bool verify_entries(const packed_int_map_type& db, const packed_int_map_type::entry* entries, size_t entry_size)
+{
+ auto results = db.prefix_search(nullptr, 0);
+ for (auto it = results.begin(), ite = results.end(); it != ite; ++it)
+ cout << it->first << ": " << it->second << endl;
+
+ const packed_int_map_type::entry* p = entries;
+ const packed_int_map_type::entry* p_end = p + entry_size;
+ for (; p != p_end; ++p)
+ {
+ auto it = db.find(p->key, p->keylen);
+ if (it == db.end() || it->second != p->value)
+ return false;
+ }
+
+ return true;
+}
+
+template<typename T>
+bool check_equal(const T& left, const T& right)
+{
+ if (left.first != right.first)
+ {
+ cout << "left: " << left.first << "; right: " << right.first << endl;
+ return false;
+ }
+
+ if (left.second != right.second)
+ {
+ cout << "left: " << left.second << "; right: " << right.second << endl;
+ return false;
+ }
+
+ return true;
+}
+
+void trie_packed_test1()
+{
+ stack_printer __stack_printer__("::trie_packed_test1");
+
+ packed_int_map_type::entry entries[] = {
+ {MDDS_ASCII("a"), 13},
+ {MDDS_ASCII("aa"), 10},
+ {MDDS_ASCII("ab"), 3},
+ {MDDS_ASCII("b"), 7},
+ };
+
+ size_t entry_size = std::size(entries);
+ packed_int_map_type db(entries, entry_size);
+ assert(db.size() == 4);
+ assert(verify_entries(db, entries, entry_size));
+
+ // invalid keys
+ assert(db.find(MDDS_ASCII("ac")) == db.end());
+ assert(db.find(MDDS_ASCII("c")) == db.end());
+
+ {
+ // Get all key-value pairs.
+ auto results = db.prefix_search(nullptr, 0);
+ size_t n = std::distance(results.begin(), results.end());
+ assert(n == 4);
+ auto it = results.begin();
+ assert(it->first == "a");
+ assert(it->second == 13);
+ ++it;
+ assert(it->first == "aa");
+ assert(it->second == 10);
+ ++it;
+ assert(it->first == "ab");
+ assert(it->second == 3);
+ ++it;
+ assert(it->first == "b");
+ assert(it->second == 7);
+ ++it;
+ assert(it == results.end());
+ }
+
+ {
+ auto it = db.find(MDDS_ASCII("a"));
+ assert(it->first == "a");
+ assert(it->second == 13);
+ ++it;
+ assert(it->first == "aa");
+ assert(it->second == 10);
+ ++it;
+ assert(it->first == "ab");
+ assert(it->second == 3);
+ ++it;
+ assert(it->first == "b");
+ assert(it->second == 7);
+ ++it;
+ assert(it == db.end());
+ }
+}
+
+void trie_packed_test2()
+{
+ stack_printer __stack_printer__("::trie_packed_test2");
+
+ packed_int_map_type::entry entries[] = {
+ {MDDS_ASCII("aaron"), 0}, {MDDS_ASCII("al"), 1}, {MDDS_ASCII("aldi"), 2}, {MDDS_ASCII("andy"), 3},
+ {MDDS_ASCII("bison"), 4}, {MDDS_ASCII("bruce"), 5}, {MDDS_ASCII("charlie"), 6}, {MDDS_ASCII("charlotte"), 7},
+ {MDDS_ASCII("david"), 8}, {MDDS_ASCII("dove"), 9}, {MDDS_ASCII("e"), 10}, {MDDS_ASCII("eva"), 11},
+ };
+
+ size_t entry_size = std::size(entries);
+ packed_int_map_type db(entries, entry_size);
+ assert(db.size() == 12);
+ assert(verify_entries(db, entries, entry_size));
+
+ // invalid keys
+ assert(db.find(MDDS_ASCII("aarons")) == db.end());
+ assert(db.find(MDDS_ASCII("a")) == db.end());
+ assert(db.find(MDDS_ASCII("biso")) == db.end());
+ assert(db.find(MDDS_ASCII("dAvid")) == db.end());
+}
+
+void trie_packed_test3()
+{
+ stack_printer __stack_printer__("::trie_packed_test3");
+
+ packed_int_map_type::entry entries[] = {
+ {MDDS_ASCII("NULL"), 1},
+ {MDDS_ASCII("Null"), 2},
+ {MDDS_ASCII("null"), 3},
+ {MDDS_ASCII("~"), 4},
+ };
+
+ size_t entry_size = std::size(entries);
+ packed_int_map_type db(entries, entry_size);
+ assert(db.size() == 4);
+ assert(verify_entries(db, entries, entry_size));
+
+ // invalid keys
+ assert(db.find(MDDS_ASCII("NUll")) == db.end());
+ assert(db.find(MDDS_ASCII("Oull")) == db.end());
+ assert(db.find(MDDS_ASCII("Mull")) == db.end());
+ assert(db.find(MDDS_ASCII("hell")) == db.end());
+}
+
+void trie_packed_test4()
+{
+ stack_printer __stack_printer__("::trie_packed_test4");
+
+ enum name_type
+ {
+ name_none = 0,
+ name_andy,
+ name_bruce,
+ name_charlie,
+ name_david
+ };
+
+ packed_int_map_type::entry entries[] = {
+ {MDDS_ASCII("andy"), name_andy}, {MDDS_ASCII("andy1"), name_andy}, {MDDS_ASCII("andy13"), name_andy},
+ {MDDS_ASCII("bruce"), name_bruce}, {MDDS_ASCII("charlie"), name_charlie}, {MDDS_ASCII("david"), name_david},
+ };
+
+ size_t entry_size = std::size(entries);
+ packed_int_map_type db(entries, entry_size);
+ assert(db.size() == 6);
+ assert(verify_entries(db, entries, entry_size));
+
+ // Try invalid keys.
+ assert(db.find("foo", 3) == db.end());
+ assert(db.find("andy133", 7) == db.end());
+
+ // Test prefix search on 'andy'.
+ auto results = db.prefix_search(MDDS_ASCII("andy"));
+ size_t n = std::distance(results.begin(), results.end());
+ assert(n == 3);
+ auto it = results.begin();
+ assert(it->first == "andy");
+ ++it;
+ assert(it->first == "andy1");
+ ++it;
+ assert(it->first == "andy13");
+ ++it;
+ assert(it == results.end());
+
+ results = db.prefix_search(MDDS_ASCII("andy's toy"));
+ n = std::distance(results.begin(), results.end());
+ assert(n == 0);
+
+ results = db.prefix_search(MDDS_ASCII("e"));
+ n = std::distance(results.begin(), results.end());
+ assert(n == 0);
+
+ results = db.prefix_search(MDDS_ASCII("b"));
+ n = std::distance(results.begin(), results.end());
+ assert(n == 1);
+ it = results.begin();
+ assert(it->first == "bruce");
+ assert(it->second == name_bruce);
+ ++it;
+ assert(it == results.end());
+}
+
+struct value_wrapper
+{
+ int value;
+
+ value_wrapper() : value(0)
+ {}
+ value_wrapper(int _value) : value(_value)
+ {}
+};
+
+std::ostream& operator<<(std::ostream& os, const value_wrapper& vw)
+{
+ os << vw.value;
+ return os;
+}
+
+typedef packed_trie_map<trie::std_string_traits, value_wrapper> packed_value_map_type;
+
+void trie_packed_test_value_life_cycle()
+{
+ stack_printer __stack_printer__("::trie_packed_test_value_life_cycle");
+
+ using entry = packed_value_map_type::entry;
+
+ // Entries must be sorted by the key!
+ std::unique_ptr<vector<entry>> entries(new vector<entry>);
+ entries->push_back(entry(MDDS_ASCII("fifteen"), value_wrapper(15)));
+ entries->push_back(entry(MDDS_ASCII("ten"), value_wrapper(10)));
+ entries->push_back(entry(MDDS_ASCII("twelve"), value_wrapper(12)));
+ entries->push_back(entry(MDDS_ASCII("two"), value_wrapper(2)));
+
+ packed_value_map_type db(entries->data(), entries->size());
+
+ // Delete the original entry store.
+ entries.reset();
+
+ auto results = db.prefix_search(nullptr, 0);
+ std::for_each(results.begin(), results.end(), [](const packed_value_map_type::const_iterator::value_type& v) {
+ cout << v.first << ": " << v.second.value << endl;
+ });
+
+ auto it = db.find(MDDS_ASCII("twelve"));
+ assert(it->second.value == 12);
+
+ it = db.find(MDDS_ASCII("two"));
+ assert(it->second.value == 2);
+
+ it = db.find(MDDS_ASCII("foo"));
+ assert(it == db.end());
+}
+
+struct custom_string
+{
+ std::string data;
+
+ custom_string()
+ {}
+ custom_string(const std::string& _data) : data(_data)
+ {}
+};
+
+struct custom_string_trait
+{
+ typedef uint16_t key_unit_type;
+ typedef custom_string key_type;
+ typedef std::vector<key_unit_type> key_buffer_type;
+
+ static key_buffer_type to_key_buffer(const key_unit_type* str, size_t length)
+ {
+ key_buffer_type buf;
+ const key_unit_type* str_end = str + length;
+ for (; str != str_end; ++str)
+ buf.push_back(*str);
+
+ return buf;
+ }
+
+ static void push_back(key_buffer_type& buffer, key_unit_type c)
+ {
+ buffer.push_back(c);
+ }
+
+ static void pop_back(key_buffer_type& buffer)
+ {
+ buffer.pop_back();
+ }
+
+ static key_type to_key(const key_buffer_type& buf)
+ {
+ // Cast all uint16_t chars to regular chars.
+ key_type s;
+
+ std::for_each(buf.begin(), buf.end(), [&](key_unit_type c) { s.data.push_back(static_cast<char>(c)); });
+ return s;
+ }
+};
+
+typedef packed_trie_map<custom_string_trait, std::string> packed_custom_str_map_type;
+
+void trie_packed_test_custom_string()
+{
+ stack_printer __stack_printer__("::trie_packed_test_custom_string");
+
+ const uint16_t key_alex[] = {0x41, 0x6C, 0x65, 0x78};
+ const uint16_t key_bob[] = {0x42, 0x6F, 0x62};
+ const uint16_t key_max[] = {0x4D, 0x61, 0x78};
+ const uint16_t key_ming[] = {0x4D, 0x69, 0x6E, 0x67};
+
+ const packed_custom_str_map_type::entry entries[] = {
+ {key_alex, 4, "Alex"},
+ {key_bob, 3, "Bob"},
+ {key_max, 3, "Max"},
+ {key_ming, 4, "Ming"},
+ };
+
+ size_t n_entries = std::size(entries);
+ packed_custom_str_map_type db(entries, n_entries);
+ for (size_t i = 0; i < n_entries; ++i)
+ {
+ auto it = db.find(entries[i].key, entries[i].keylen);
+ cout << it->second << endl;
+ assert(it->second == entries[i].value);
+ }
+
+ // Find all keys that start with 'M'.
+ auto results = db.prefix_search(key_max, 1);
+ size_t n = std::distance(results.begin(), results.end());
+ assert(n == 2);
+ auto it = results.begin();
+ assert(it->first.data == it->second);
+ assert(it->second == "Max");
+ ++it;
+ assert(it->first.data == it->second);
+ assert(it->second == "Ming");
+ ++it;
+ assert(it == results.end());
+}
+
+void trie_packed_test_iterator_empty()
+{
+ stack_printer __stack_printer__("::trie_packed_test_iterator_empty");
+ packed_int_map_type db(nullptr, 0);
+
+ // empty container
+ packed_int_map_type::const_iterator it = db.begin();
+ packed_int_map_type::const_iterator ite = db.end();
+
+ assert(it == ite);
+}
+
+void trie_packed_test_iterator()
+{
+ stack_printer __stack_printer__("::trie_packed_test_iterator");
+
+ using trie_map_type = trie_map<trie::std_string_traits, int>;
+ using packed_type = trie_map_type::packed_type;
+ using kv = packed_type::key_value_type;
+
+ trie_map_type db;
+
+ db.insert(MDDS_ASCII("a"), 1);
+ packed_type packed = db.pack();
+ assert(db.size() == packed.size());
+ packed_type::const_iterator it = packed.begin();
+ packed_type::const_iterator ite = packed.end();
+ assert(it != ite);
+ assert(it->first == "a");
+ assert(it->second == 1);
+
+ db.insert(MDDS_ASCII("ab"), 2);
+ packed = db.pack(); // this invalidates the end position.
+ assert(db.size() == packed.size());
+
+ it = packed.begin();
+ ite = packed.end();
+ assert(it != ite);
+ assert(it->first == "a");
+ assert(it->second == 1);
+
+ ++it;
+ bool check_true = check_equal(*it++, kv("ab", 2));
+ assert(check_true);
+ assert(it == ite);
+
+ db.insert(MDDS_ASCII("aba"), 3);
+ db.insert(MDDS_ASCII("abb"), 4);
+ db.insert(MDDS_ASCII("abc"), 5);
+ db.insert(MDDS_ASCII("bc"), 6);
+ db.insert(MDDS_ASCII("bcd"), 7);
+
+ packed = db.pack();
+ assert(db.size() == packed.size());
+
+ it = packed.begin();
+ ite = packed.end();
+
+ assert(*it == kv("a", 1));
+ assert(check_equal(*(++it), kv("ab", 2)));
+ assert(check_equal(*(++it), kv("aba", 3)));
+ assert(check_equal(*(++it), kv("abb", 4)));
+ assert(check_equal(*(++it), kv("abc", 5)));
+ assert(check_equal(*(++it), kv("bc", 6)));
+ assert(check_equal(*(++it), kv("bcd", 7)));
+ assert(it->first == "bcd");
+ assert(it->second == 7);
+ ++it;
+ assert(it == ite);
+
+ --it;
+ assert(it != ite);
+ assert(check_equal(*it, kv("bcd", 7)));
+ --it;
+ assert(check_equal(*it, kv("bc", 6)));
+ --it;
+ assert(check_equal(*it, kv("abc", 5)));
+ --it;
+ assert(check_equal(*it, kv("abb", 4)));
+ --it;
+ assert(check_equal(*it, kv("aba", 3)));
+ --it;
+ assert(check_equal(*it, kv("ab", 2)));
+ assert(check_equal(*(--it), kv("a", 1)));
+ assert(it == packed.begin());
+
+ assert(check_equal(*(++it), kv("ab", 2)));
+ assert(check_equal(*(++it), kv("aba", 3)));
+ --it;
+ assert(check_equal(*it, kv("ab", 2)));
+ --it;
+ assert(check_equal(*it, kv("a", 1)));
+ ++it;
+ assert(check_equal(*it, kv("ab", 2)));
+ ++it;
+ assert(check_equal(*it, kv("aba", 3)));
+
+ // Post-decrement operator.
+ assert(check_equal(*it--, kv("aba", 3)));
+ assert(check_equal(*it, kv("ab", 2)));
+}
+
+void trie_packed_test_prefix_search1()
+{
+ stack_printer __stack_printer__("::trie_packed_test_prefix_search1");
+
+ using trie_map_type = trie_map<trie::std_string_traits, int>;
+ using packed_type = trie_map_type::packed_type;
+
+ trie_map_type db;
+ db.insert(MDDS_ASCII("andy"), 1);
+ db.insert(MDDS_ASCII("andy1"), 2);
+ db.insert(MDDS_ASCII("andy12"), 3);
+
+ {
+ auto results = db.prefix_search(MDDS_ASCII("andy"));
+ auto it = results.begin();
+ assert(it != results.end());
+ assert(it->first == "andy");
+ ++it;
+ assert(it->first == "andy1");
+ ++it;
+ assert(it->first == "andy12");
+ ++it;
+ assert(it == results.end());
+
+ size_t n = std::distance(results.begin(), results.end());
+ assert(n == 3);
+ }
+
+ packed_type packed = db.pack();
+ {
+ auto results = packed.prefix_search(MDDS_ASCII("andy"));
+ auto it = results.begin();
+ assert(it != results.end());
+ assert(it->first == "andy");
+ ++it;
+ assert(it->first == "andy1");
+ ++it;
+ assert(it->first == "andy12");
+ ++it;
+ assert(it == results.end());
+
+ size_t n = std::distance(results.begin(), results.end());
+ assert(n == 3);
+ }
+}
+
+void trie_packed_test_key_as_input()
+{
+ stack_printer __stack_printer__("::trie_packed_test_key_as_input");
+
+ typedef trie_map<trie::std_string_traits, int> trie_map_type;
+ trie_map_type db;
+
+ db.insert(std::string("string as key"), 1);
+ db.insert("literal as key", 2);
+ auto packed = db.pack();
+
+ auto it = packed.find("literal as key");
+ assert(it != packed.end());
+ assert(it->first == "literal as key");
+ assert(it->second == 2);
+
+ auto results = packed.prefix_search("str");
+ auto rit = results.begin();
+ assert(rit != results.end());
+ assert(rit->first == "string as key");
+ assert(rit->second == 1);
+ ++rit;
+ assert(rit == results.end());
+}
+
+void trie_packed_test_copying()
+{
+ stack_printer __stack_printer__("::trie_packed_test_copying");
+ using map_type = packed_trie_map<trie::std_string_traits, int>;
+
+ map_type::entry entries[] = {
+ {MDDS_ASCII("aaron"), 0}, {MDDS_ASCII("al"), 1}, {MDDS_ASCII("aldi"), 2}, {MDDS_ASCII("andy"), 3},
+ {MDDS_ASCII("bison"), 4}, {MDDS_ASCII("bruce"), 5}, {MDDS_ASCII("charlie"), 6}, {MDDS_ASCII("charlotte"), 7},
+ {MDDS_ASCII("david"), 8}, {MDDS_ASCII("dove"), 9}, {MDDS_ASCII("e"), 10}, {MDDS_ASCII("eva"), 11},
+ };
+
+ auto verify_content = [&entries](const map_type& db) {
+ auto it = db.begin();
+ const map_type::entry* p_entries = entries;
+ const map_type::entry* p_entries_end = p_entries + db.size();
+ size_t n = std::distance(p_entries, p_entries_end);
+ assert(db.size() == n);
+ assert(!db.empty());
+
+ for (; p_entries != p_entries_end; ++p_entries, ++it)
+ {
+ std::string key_expected(p_entries->key, p_entries->keylen);
+ assert(key_expected == it->first);
+ assert(p_entries->value == it->second);
+ }
+ };
+
+ auto db = std::make_unique<map_type>(entries, std::size(entries));
+ auto db_copied(*db);
+ assert(*db == db_copied);
+ assert(db->size() == db_copied.size());
+ db.reset();
+
+ auto it = db_copied.find("charlie");
+ assert(it != db_copied.end());
+ assert(it->first == "charlie");
+ assert(it->second == 6);
+
+ verify_content(db_copied);
+
+ auto db_moved(std::move(db_copied));
+ assert(db_copied.empty());
+ assert(!db_moved.empty());
+ assert(db_moved.size() == std::size(entries));
+
+ it = db_copied.find("bison");
+ assert(it == db_copied.end());
+ it = db_moved.find("bison");
+ assert(it != db_moved.end());
+ assert(it->first == "bison");
+ assert(it->second == 4);
+
+ verify_content(db_moved);
+
+ map_type db_copy_assigned;
+ assert(db_copy_assigned.empty());
+ db_copy_assigned = db_moved;
+ assert(db_copy_assigned == db_moved);
+
+ verify_content(db_moved);
+ verify_content(db_copy_assigned);
+
+ map_type db_move_assigned;
+ assert(db_move_assigned.empty());
+ db_move_assigned = std::move(db_moved);
+ assert(db_move_assigned != db_moved);
+
+ verify_content(db_move_assigned);
+ assert(db_moved.empty());
+}
+
+void trie_packed_test_non_equal()
+{
+ stack_printer __stack_printer__("::trie_packed_test_non_equal");
+
+ using map_type = packed_trie_map<trie::std_string_traits, int>;
+
+ map_type::entry entries1[] = {
+ {MDDS_ASCII("aaron"), 0}, {MDDS_ASCII("al"), 1}, {MDDS_ASCII("aldi"), 2}, {MDDS_ASCII("andy"), 3},
+ {MDDS_ASCII("bison"), 4}, {MDDS_ASCII("bruce"), 5}, {MDDS_ASCII("charlie"), 6}, {MDDS_ASCII("charlotte"), 7},
+ {MDDS_ASCII("david"), 8}, {MDDS_ASCII("dove"), 9}, {MDDS_ASCII("e"), 10}, {MDDS_ASCII("eva"), 11},
+ };
+
+ map_type::entry entries2[] = {
+ {MDDS_ASCII("aaron"), 0}, {MDDS_ASCII("al"), 1}, {MDDS_ASCII("aldi"), 2},
+ {MDDS_ASCII("andy"), 3}, {MDDS_ASCII("bison"), 4}, {MDDS_ASCII("bruce"), 2}, // different value
+ {MDDS_ASCII("charlie"), 6}, {MDDS_ASCII("charlotte"), 7}, {MDDS_ASCII("david"), 8},
+ {MDDS_ASCII("dove"), 9}, {MDDS_ASCII("e"), 10}, {MDDS_ASCII("eva"), 11},
+ };
+
+ // fewer entries
+ map_type::entry entries3[] = {
+ {MDDS_ASCII("aaron"), 0}, {MDDS_ASCII("al"), 1}, {MDDS_ASCII("aldi"), 2}, {MDDS_ASCII("andy"), 3},
+ {MDDS_ASCII("bison"), 4}, {MDDS_ASCII("bruce"), 5}, {MDDS_ASCII("charlie"), 6}, {MDDS_ASCII("charlotte"), 7},
+ {MDDS_ASCII("david"), 8}, {MDDS_ASCII("dove"), 9}, {MDDS_ASCII("e"), 10},
+ };
+
+ map_type db1(entries1, std::size(entries1));
+ map_type db2(entries2, std::size(entries2));
+ map_type db3(entries3, std::size(entries3));
+ assert(db1 != db2);
+ assert(db1 != db3);
+ assert(db2 != db3);
+
+ map_type db4(entries1, std::size(entries1));
+ map_type db5(entries2, std::size(entries2));
+ map_type db6(entries3, std::size(entries3));
+
+ assert(db1 == db4);
+ assert(db2 == db5);
+ assert(db3 == db6);
+}
+
+namespace trie_packed_test_save_and_load_state {
+
+struct _custom_variable_value
+{
+ enum class v_type
+ {
+ unknown,
+ fp32,
+ int64
+ };
+
+ v_type type;
+
+ union
+ {
+ float fp32;
+ int64_t int64;
+ } value;
+
+ _custom_variable_value() : type(v_type::unknown)
+ {}
+
+ _custom_variable_value(float v) : type(v_type::fp32)
+ {
+ value.fp32 = v;
+ }
+
+ _custom_variable_value(int v) : type(v_type::int64)
+ {
+ value.int64 = v;
+ }
+
+ _custom_variable_value(const _custom_variable_value& other) : type(other.type)
+ {
+ switch (type)
+ {
+ case v_type::fp32:
+ value.fp32 = other.value.fp32;
+ break;
+ case v_type::int64:
+ value.int64 = other.value.int64;
+ break;
+ default:;
+ }
+ }
+
+ bool operator==(const _custom_variable_value& other) const
+ {
+ if (type != other.type)
+ return false;
+
+ switch (type)
+ {
+ case v_type::fp32:
+ return value.fp32 == other.value.fp32;
+ case v_type::int64:
+ return value.int64 == other.value.int64;
+ default:;
+ }
+
+ return true;
+ }
+
+ bool operator!=(const _custom_variable_value& other) const
+ {
+ return !operator==(other);
+ }
+};
+
+struct _custom_variable_serializer
+{
+ union bin_value
+ {
+ char buffer[8];
+ float fp32;
+ int64_t int64;
+ };
+
+ static constexpr bool variable_size = true;
+
+ static void write(std::ostream& os, const _custom_variable_value& v)
+ {
+ bin_value bv;
+
+ switch (v.type)
+ {
+ case _custom_variable_value::v_type::unknown:
+ {
+ char c = 0;
+ os.write(&c, 1);
+ break;
+ }
+ case _custom_variable_value::v_type::fp32:
+ {
+ char c = 1;
+ os.write(&c, 1);
+ bv.fp32 = v.value.fp32;
+ os.write(bv.buffer, 4);
+ break;
+ }
+ case _custom_variable_value::v_type::int64:
+ {
+ char c = 2;
+ os.write(&c, 1);
+ bv.int64 = v.value.int64;
+ os.write(bv.buffer, 8);
+ break;
+ }
+ }
+ }
+
+ static void read(std::istream& is, size_t n, _custom_variable_value& v)
+ {
+ assert(n > 0);
+ char c;
+ is.read(&c, 1);
+
+ switch (c)
+ {
+ case 0:
+ v.type = _custom_variable_value::v_type::unknown;
+ break;
+ case 1:
+ v.type = _custom_variable_value::v_type::fp32;
+ break;
+ case 2:
+ v.type = _custom_variable_value::v_type::int64;
+ break;
+ default:
+ assert(!"invalid value type");
+ }
+
+ n -= 1;
+ bin_value bv;
+
+ switch (v.type)
+ {
+ case _custom_variable_value::v_type::fp32:
+ assert(n == 4);
+ is.read(bv.buffer, 4);
+ v.value.fp32 = bv.fp32;
+ break;
+ case _custom_variable_value::v_type::int64:
+ assert(n == 8);
+ is.read(bv.buffer, 8);
+ v.value.int64 = bv.int64;
+ break;
+ case _custom_variable_value::v_type::unknown:
+ break;
+ default:
+ assert(!"invalid value type");
+ }
+ }
+};
+
+/**
+ * mock value struct containing one value string that only stores "zero",
+ * "one", "two" or "three". We use a custom serializer to store the value
+ * using only 1 byte each.
+ */
+struct _custom_fixed_value
+{
+ std::string value_string; // only stores "zero", "one", "two" or "three".
+
+ _custom_fixed_value()
+ {}
+
+ _custom_fixed_value(const char* p) : value_string(p, std::strlen(p))
+ {}
+
+ bool operator==(const _custom_fixed_value& other) const
+ {
+ return value_string == other.value_string;
+ }
+
+ bool operator!=(const _custom_fixed_value& other) const
+ {
+ return !operator==(other);
+ }
+};
+
+struct _custom_fixed_serializer
+{
+ static constexpr bool variable_size = false;
+ static constexpr size_t value_size = 1;
+
+ static void write(std::ostream& os, const _custom_fixed_value& v)
+ {
+ char bv = -1;
+
+ if (v.value_string == "zero")
+ bv = 0;
+ else if (v.value_string == "one")
+ bv = 1;
+ else if (v.value_string == "two")
+ bv = 2;
+ else if (v.value_string == "three")
+ bv = 3;
+
+ os.write(&bv, 1);
+ }
+
+ static void read(std::istream& is, size_t n, _custom_fixed_value& v)
+ {
+ assert(n == 1);
+ char bv = -1;
+ is.read(&bv, 1);
+
+ switch (bv)
+ {
+ case 0:
+ v.value_string = "zero";
+ break;
+ case 1:
+ v.value_string = "one";
+ break;
+ case 2:
+ v.value_string = "two";
+ break;
+ case 3:
+ v.value_string = "three";
+ break;
+ default:
+ v.value_string = "???";
+ }
+ }
+};
+
+void test1()
+{
+ stack_printer __stack_printer__("trie_packed_test_save_and_load_state::test1");
+ packed_int_map_type empty_db;
+
+ std::string saved_state;
+
+ {
+ std::ostringstream state;
+ empty_db.save_state(state);
+ saved_state = state.str();
+ }
+
+ packed_int_map_type restored;
+
+ {
+ std::istringstream state(saved_state);
+ restored.load_state(state);
+ }
+
+ assert(restored == empty_db);
+}
+
+void test2()
+{
+ stack_printer __stack_printer__("trie_packed_test_save_and_load_state::test2");
+ packed_int_map_type::entry entries[] = {
+ {MDDS_ASCII("bruce"), 5}, {MDDS_ASCII("charlie"), 6}, {MDDS_ASCII("charlotte"), 7},
+ {MDDS_ASCII("david"), 8}, {MDDS_ASCII("dove"), 9},
+ };
+
+ packed_int_map_type db(entries, std::size(entries));
+
+ std::string saved_state;
+
+ {
+ std::ostringstream state;
+ db.save_state(state);
+ saved_state = state.str();
+ }
+
+ packed_int_map_type restored;
+ assert(restored != db);
+
+ {
+ std::istringstream state(saved_state);
+ restored.load_state(state);
+ }
+
+ assert(restored == db);
+}
+
+void test3()
+{
+ stack_printer __stack_printer__("trie_packed_test_save_and_load_state::test3");
+ std::vector<packed_str_map_type::entry> entries = {
+ {MDDS_ASCII("Abby"), "ABBY"},
+ {MDDS_ASCII("Ashley"), "ASHLEY"},
+ {MDDS_ASCII("Candelaria"), "CANDELARIA"},
+ {MDDS_ASCII("Carita"), "CARITA"},
+ {MDDS_ASCII("Christal"), "CHRISTAL"},
+ {MDDS_ASCII("Cory"), "CORY"},
+ {MDDS_ASCII("Estrella"), "ESTRELLA"},
+ {MDDS_ASCII("Etha"), "ETHA"},
+ {MDDS_ASCII("Harley"), "HARLEY"},
+ {MDDS_ASCII("Irish"), "IRISH"},
+ {MDDS_ASCII("Kiara"), "KIARA"},
+ {MDDS_ASCII("Korey"), "KOREY"},
+ {MDDS_ASCII("Laurene"), "LAURENE"},
+ {MDDS_ASCII("Michiko"), "MICHIKO"},
+ {MDDS_ASCII("Miriam"), "MIRIAM"},
+ {MDDS_ASCII("Mitzi"), "MITZI"},
+ {MDDS_ASCII("Seth"), "SETH"},
+ {MDDS_ASCII("Sindy"), "SINDY"},
+ {MDDS_ASCII("Tawanna"), "TAWANNA"},
+ {MDDS_ASCII("Tyra"), "TYRA"},
+ };
+
+ packed_str_map_type db(entries.data(), entries.size());
+
+ // Run some search.
+ auto results = db.prefix_search("Mi");
+ auto it = results.begin();
+ assert(it != results.end());
+ assert(it->first == "Michiko");
+ assert(it->second == "MICHIKO");
+ ++it;
+ assert(it != results.end());
+ assert(it->first == "Miriam");
+ assert(it->second == "MIRIAM");
+ ++it;
+ assert(it != results.end());
+ assert(it->first == "Mitzi");
+ assert(it->second == "MITZI");
+ ++it;
+ assert(it == results.end());
+
+ std::string saved_state;
+
+ {
+ std::ostringstream state;
+ db.save_state(state);
+ saved_state = state.str();
+ }
+
+ packed_str_map_type restored;
+
+ {
+ std::istringstream state(saved_state);
+ restored.load_state(state);
+ }
+
+ assert(db == restored);
+}
+
+void test4()
+{
+ stack_printer __stack_printer__("trie_packed_test_save_and_load_state::test4");
+ using map_type = packed_trie_map<trie::std_string_traits, std::vector<int64_t>>;
+
+ std::vector<map_type::entry> entries = {
+ {MDDS_ASCII("Abby"), {65, 98, 98, 121}},
+ {MDDS_ASCII("Ashley"), {65, 115, 104, 108, 101, 121}},
+ {MDDS_ASCII("Christal"), {67, 104, 114, 105, 115, 116, 97, 108}},
+ {MDDS_ASCII("Cory"), {67, 111, 114, 121}},
+ {MDDS_ASCII("Harley"), {72, 97, 114, 108, 101, 121}},
+ {MDDS_ASCII("Kiara"), {75, 105, 97, 114, 97}},
+ {MDDS_ASCII("Mitzi"), {77, 105, 116, 122, 105}},
+ };
+
+ map_type db(entries.data(), entries.size());
+ assert(db.size() == entries.size());
+
+ std::string saved_state;
+ {
+ std::ostringstream state;
+ db.save_state(state);
+ saved_state = state.str();
+ }
+
+ map_type restored;
+
+ {
+ std::istringstream state(saved_state);
+ restored.load_state(state);
+ }
+
+ assert(db == restored);
+}
+
+void test5()
+{
+ stack_printer __stack_printer__("trie_packed_test_save_and_load_state::test5");
+ using map_type = packed_trie_map<trie::std_string_traits, float>;
+
+ std::vector<map_type::entry> entries = {
+ {MDDS_ASCII("Abby"), 1.0f}, {MDDS_ASCII("Ashley"), 1.1f}, {MDDS_ASCII("Christal"), 1.2f},
+ {MDDS_ASCII("Cory"), 1.3f}, {MDDS_ASCII("Harley"), 1.4f}, {MDDS_ASCII("Kiara"), 1.5f},
+ {MDDS_ASCII("Mitzi"), 1.6f},
+ };
+
+ map_type db(entries.data(), entries.size());
+ assert(db.size() == entries.size());
+
+ std::string saved_state;
+ {
+ std::ostringstream state;
+ db.save_state(state);
+ saved_state = state.str();
+ }
+
+ map_type restored;
+
+ {
+ std::istringstream state(saved_state);
+ restored.load_state(state);
+ }
+
+ assert(db == restored);
+}
+
+template<typename SeqT>
+void test6()
+{
+ stack_printer __stack_printer__("trie_packed_test_save_and_load_state::test6");
+ using map_type = packed_trie_map<trie::std_string_traits, SeqT>;
+
+ std::vector<typename map_type::entry> entries = {
+ {MDDS_ASCII("Abby"), {65.0, 98.1, 98.2, 121.3}},
+ {MDDS_ASCII("Ashley"), {65.0, 11.5, 1.04, 1.08, .101, .12586}},
+ {MDDS_ASCII("Christal"), {67.0, -10.4, -114.236}},
+ {MDDS_ASCII("Cory"), {67.0, 122.111}},
+ {MDDS_ASCII("Harley"), {72.0, 97.12, -1.114}},
+ {MDDS_ASCII("Kiara"), {75.0, 1.05, 9.7, 1.14, -97.5}},
+ {MDDS_ASCII("Mitzi"), {77.0, 10.5, 11.6, 1.22, 10.5}},
+ };
+
+ map_type db(entries.data(), entries.size());
+ assert(db.size() == entries.size());
+
+ std::string saved_state;
+ {
+ std::ostringstream state;
+ db.save_state(state);
+ saved_state = state.str();
+ }
+
+ map_type restored;
+
+ {
+ std::istringstream state(saved_state);
+ restored.load_state(state);
+ }
+
+ assert(db == restored);
+}
+
+void test7()
+{
+ stack_printer __stack_printer__("trie_packed_test_save_and_load_state::test7");
+ using map_type = packed_trie_map<trie::std_string_traits, _custom_variable_value>;
+
+ std::vector<map_type::entry> entries = {
+ {MDDS_ASCII("Alan"), 1.2f}, {MDDS_ASCII("Cory"), -125}, {MDDS_ASCII("Eleni"), 966},
+ {MDDS_ASCII("Evia"), -0.987f}, {MDDS_ASCII("Nathaniel"), 0}, {MDDS_ASCII("Rebbecca"), 1.234f},
+ {MDDS_ASCII("Rodrick"), 34253536}, {MDDS_ASCII("Stuart"), 12}, {MDDS_ASCII("Verline"), 56},
+ };
+
+ map_type db(entries.data(), entries.size());
+ assert(db.size() == entries.size());
+
+ std::string saved_state;
+ {
+ std::ostringstream state;
+ db.save_state<_custom_variable_serializer>(state);
+ saved_state = state.str();
+ }
+
+ map_type restored;
+
+ {
+ std::istringstream state(saved_state);
+ restored.load_state<_custom_variable_serializer>(state);
+ }
+
+ assert(db == restored);
+}
+
+void test8()
+{
+ stack_printer __stack_printer__("trie_packed_test_save_and_load_state::test8");
+ using map_type = packed_trie_map<trie::std_string_traits, _custom_fixed_value>;
+
+ std::vector<map_type::entry> entries = {
+ {MDDS_ASCII("Bernardine"), "zero"}, {MDDS_ASCII("Donny"), "two"}, {MDDS_ASCII("Julia"), "one"},
+ {MDDS_ASCII("Lindsy"), "three"}, {MDDS_ASCII("Martine"), "three"}, {MDDS_ASCII("Shana"), "two"},
+ {MDDS_ASCII("Sonia"), "zero"}, {MDDS_ASCII("Tracie"), "one"}, {MDDS_ASCII("Vanita"), "two"},
+ {MDDS_ASCII("Yung"), "zero"},
+ };
+
+ map_type db(entries.data(), entries.size());
+ assert(db.size() == entries.size());
+
+ std::string saved_state;
+ {
+ std::ostringstream state;
+ db.save_state<_custom_fixed_serializer>(state);
+ saved_state = state.str();
+ }
+
+ map_type restored;
+
+ {
+ std::istringstream state(saved_state);
+ restored.load_state<_custom_fixed_serializer>(state);
+ }
+
+ assert(db == restored);
+
+ // Run some query to make sure it is still functional.
+ auto it = restored.find("Tracie");
+ assert(it->first == "Tracie");
+ assert(it->second.value_string == "one");
+}
+
+void run()
+{
+ test1();
+ test2();
+ test3();
+ test4();
+ test5();
+ test6<std::vector<double>>();
+ test6<std::deque<double>>();
+ test6<std::list<double>>();
+ test7();
+ test8();
+}
+
+} // namespace trie_packed_test_save_and_load_state
+
+void trie_test1()
+{
+ stack_printer __stack_printer__("::trie_test1");
+
+ typedef trie_map<trie::std_string_traits, custom_string> trie_map_type;
+ typedef packed_trie_map<trie::std_string_traits, custom_string> packed_trie_map_type;
+
+ trie_map_type db;
+ const trie_map_type& dbc = db;
+
+ assert(db.size() == 0);
+ db.insert(MDDS_ASCII("Barak"), custom_string("Obama"));
+ assert(db.size() == 1);
+ db.insert(MDDS_ASCII("Bob"), custom_string("Marley"));
+ assert(db.size() == 2);
+ db.insert(MDDS_ASCII("Hideki"), custom_string("Matsui"));
+ assert(db.size() == 3);
+
+ auto it = dbc.find(MDDS_ASCII("Barak"));
+ assert(it->first == "Barak");
+ custom_string res = it->second;
+ assert(res.data == "Obama");
+
+ res = dbc.find(MDDS_ASCII("Bob"))->second;
+ assert(res.data == "Marley");
+ res = dbc.find(MDDS_ASCII("Hideki"))->second;
+ assert(res.data == "Matsui");
+
+ // Non-existent key.
+ it = dbc.find(MDDS_ASCII("Von"));
+ assert(it == dbc.end());
+ it = dbc.find(MDDS_ASCII("Bar"));
+ assert(it == dbc.end());
+
+ // Perform prefix search on "B", which should return both "Barak" and "Bob".
+ // The results should be sorted.
+ {
+ auto matches = dbc.prefix_search(MDDS_ASCII("B"));
+ size_t n = std::distance(matches.begin(), matches.end());
+ assert(n == 2);
+ auto it2 = matches.begin();
+ assert(it2->first == "Barak");
+ assert(it2->second.data == "Obama");
+ ++it2;
+ assert(it2->first == "Bob");
+ assert(it2->second.data == "Marley");
+
+ matches = dbc.prefix_search(MDDS_ASCII("Hi"));
+ n = std::distance(matches.begin(), matches.end());
+ assert(n == 1);
+ it2 = matches.begin();
+ assert(it2->first == "Hideki");
+ assert(it2->second.data == "Matsui");
+
+ // Invalid prefix searches.
+ matches = dbc.prefix_search(MDDS_ASCII("Bad"));
+ assert(matches.begin() == matches.end());
+ matches = dbc.prefix_search(MDDS_ASCII("Foo"));
+ assert(matches.begin() == matches.end());
+ }
+
+ {
+ // Create a packed version from it, and make sure it still generates the
+ // same results.
+ packed_trie_map_type packed(dbc);
+ assert(packed.size() == dbc.size());
+
+ {
+ auto results = packed.prefix_search(MDDS_ASCII("B"));
+ size_t n = std::distance(results.begin(), results.end());
+ assert(n == 2);
+ auto it2 = results.begin();
+ assert(it2->first == "Barak");
+ assert(it2->second.data == "Obama");
+ ++it2;
+ assert(it2->first == "Bob");
+ assert(it2->second.data == "Marley");
+ ++it2;
+ assert(it2 == results.end());
+ }
+
+ {
+ auto results = dbc.prefix_search(MDDS_ASCII("Hi"));
+ size_t n = std::distance(results.begin(), results.end());
+ assert(n == 1);
+ auto it2 = results.begin();
+ assert(it2->first == "Hideki");
+ assert(it2->second.data == "Matsui");
+ }
+
+ // Invalid prefix searches.
+ auto results = dbc.prefix_search(MDDS_ASCII("Bad"));
+ assert(results.begin() == results.end());
+ results = dbc.prefix_search(MDDS_ASCII("Foo"));
+ assert(results.begin() == results.end());
+ }
+
+ {
+ auto packed = dbc.pack();
+ auto results = packed.prefix_search(MDDS_ASCII("B"));
+ size_t n = std::distance(results.begin(), results.end());
+ assert(n == 2);
+ auto it2 = results.begin();
+ assert(it2->first == "Barak");
+ assert(it2->second.data == "Obama");
+ ++it2;
+ assert(it2->first == "Bob");
+ assert(it2->second.data == "Marley");
+ }
+
+ // Erase an existing key.
+ bool erased = db.erase(MDDS_ASCII("Hideki"));
+ assert(erased);
+ assert(db.size() == 2);
+
+ it = dbc.find(MDDS_ASCII("Hideki"));
+ assert(it == dbc.end());
+
+ // Try to erase a key that doesn't exist.
+ erased = db.erase(MDDS_ASCII("Foo"));
+ assert(!erased);
+ assert(db.size() == 2);
+
+ // Clear the whole thing.
+ db.clear();
+ assert(db.size() == 0);
+}
+
+void trie_test2()
+{
+ stack_printer __stack_printer__("::trie_test2");
+ using key_trait = trie::std_container_traits<std::vector<uint16_t>>;
+ using map_type = trie_map<key_trait, int>;
+ using key_type = map_type::key_type;
+
+ auto print_key = [](const std::vector<uint16_t>& key, const char* msg) {
+ cout << msg << ": ";
+ std::copy(key.begin(), key.end(), std::ostream_iterator<uint16_t>(std::cout, " "));
+ cout << endl;
+ };
+
+ map_type db;
+ key_type key = {2393, 99, 32589, 107, 0, 65535};
+ print_key(key, "original");
+ int value = 1;
+ db.insert(key, value);
+ assert(db.size() == 1);
+ {
+ auto it = db.begin();
+ assert(it != db.end());
+ assert(it->first == key);
+
+ print_key(it->first, "from trie_map");
+ }
+
+ auto packed = db.pack();
+ assert(packed.size() == 1);
+
+ {
+ auto it = packed.begin();
+ assert(it != packed.end());
+ print_key(it->first, "from packed_trie_map");
+ assert(it->first == key);
+ }
+}
+
+void trie_test_iterator_empty()
+{
+ stack_printer __stack_printer__("::trie_test_iterator_empty");
+ typedef trie_map<trie::std_string_traits, int> trie_map_type;
+ trie_map_type db;
+ const trie_map_type& dbc = db;
+
+ // empty container
+ trie_map_type::const_iterator it = dbc.begin();
+ trie_map_type::const_iterator ite = dbc.end();
+
+ assert(it == ite);
+ assert(db.begin() == dbc.begin()); // non-const vs const iterators
+ assert(dbc.end() == db.end()); // const vs non-const iterators
+}
+
+void trie_test_iterator()
+{
+ stack_printer __stack_printer__("::trie_test_iterator");
+ typedef trie_map<trie::std_string_traits, int> trie_map_type;
+ using kv = trie_map_type::key_value_type;
+ trie_map_type db;
+ const trie_map_type& dbc = db;
+
+ cout << "empty container" << endl;
+
+ // empty container
+ trie_map_type::const_iterator it = dbc.begin();
+ trie_map_type::const_iterator ite = dbc.end();
+
+ // The end iterator will never get invalidated since it only references
+ // the root node which will never get modified as long as the parent
+ // container is alive.
+
+ assert(it == ite);
+
+ cout << "one element" << endl;
+
+ db.insert(MDDS_ASCII("a"), 1);
+ it = dbc.begin();
+ assert(it != ite);
+ assert(*it == kv("a", 1));
+ ++it;
+ assert(it == ite);
+
+ cout << "two elements" << endl;
+
+ db.insert(MDDS_ASCII("ab"), 2);
+ it = dbc.begin();
+ assert(it != ite);
+ assert(*it == kv("a", 1));
+ ++it;
+ assert(it != ite);
+ assert(*it == kv("ab", 2));
+ ++it;
+ assert(it == ite);
+
+ cout << "more than two elements" << endl;
+
+ db.insert(MDDS_ASCII("aba"), 3);
+ db.insert(MDDS_ASCII("abb"), 4);
+ db.insert(MDDS_ASCII("abc"), 5);
+ db.insert(MDDS_ASCII("bc"), 6);
+ db.insert(MDDS_ASCII("bcd"), 7);
+
+ it = dbc.begin();
+ assert(*it == kv("a", 1));
+ ++it;
+ assert(*it == kv("ab", 2));
+ ++it;
+ assert(*it == kv("aba", 3));
+ ++it;
+ assert(*it == kv("abb", 4));
+ ++it;
+ assert(*it == kv("abc", 5));
+ ++it;
+ assert(*it == kv("bc", 6));
+ ++it;
+ assert(*it == kv("bcd", 7));
+ assert(it->first == "bcd");
+ assert(it->second == 7);
+ ++it;
+ assert(it == ite);
+
+ --it;
+ assert(it != ite);
+ assert(*it == kv("bcd", 7));
+ --it;
+ assert(*it == kv("bc", 6));
+ --it;
+ assert(*it == kv("abc", 5));
+ --it;
+ assert(*it == kv("abb", 4));
+ --it;
+ assert(*it == kv("aba", 3));
+ --it;
+ assert(*it == kv("ab", 2));
+ --it;
+ assert(*it == kv("a", 1));
+ assert(it == dbc.begin());
+ ++it;
+ assert(*it == kv("ab", 2));
+ ++it;
+ assert(*it == kv("aba", 3));
+ --it;
+ assert(*it == kv("ab", 2));
+ --it;
+ assert(*it == kv("a", 1));
+ ++it;
+ assert(*it == kv("ab", 2));
+ ++it;
+ assert(*it == kv("aba", 3));
+
+ assert(db.begin() != dbc.end()); // non-const vs const iterators
+ assert(dbc.begin() != db.end()); // const vs non-const iterators
+}
+
+void trie_test_iterator_with_erase()
+{
+ stack_printer __stack_printer__("::trie_test_iterator_with_erase");
+ typedef trie_map<trie::std_string_traits, int> trie_map_type;
+ using kv = trie_map_type::key_value_type;
+ trie_map_type db;
+ const trie_map_type& dbc = db;
+ bool check_true = false;
+
+ db.insert(MDDS_ASCII("Python"), 1);
+ db.insert(MDDS_ASCII("C++"), 2);
+
+ auto it = dbc.begin(), ite = dbc.end();
+ check_true = (*it++ == kv("C++", 2));
+ assert(check_true);
+ check_true = (*it++ == kv("Python", 1));
+ assert(check_true);
+ assert(it == ite);
+
+ db.erase(MDDS_ASCII("C++"));
+ it = dbc.begin();
+ check_true = (*it++ == kv("Python", 1));
+ assert(check_true);
+ assert(it == ite);
+ check_true = (*(--it) == kv("Python", 1));
+ assert(check_true);
+ assert(it == dbc.begin());
+
+ db.clear();
+ assert(dbc.begin() == dbc.end());
+
+ db.insert(MDDS_ASCII("A"), 1);
+ db.insert(MDDS_ASCII("AB"), 2);
+ db.insert(MDDS_ASCII("ABC"), 3);
+ db.erase(MDDS_ASCII("AB"));
+
+ it = dbc.begin();
+ check_true = (*it++ == kv("A", 1));
+ assert(check_true);
+ check_true = (*it++ == kv("ABC", 3));
+ assert(check_true);
+ assert(it == ite);
+
+ check_true = (*(--it) == kv("ABC", 3));
+ assert(check_true);
+ check_true = (*(--it) == kv("A", 1));
+ assert(check_true);
+ assert(it == dbc.begin());
+
+ db.clear();
+ db.insert(MDDS_ASCII("A"), 1);
+ db.insert(MDDS_ASCII("AB"), 2);
+ db.insert(MDDS_ASCII("ABC"), 3);
+ db.erase(MDDS_ASCII("ABC"));
+
+ it = dbc.begin();
+ check_true = (*it++ == kv("A", 1));
+ assert(check_true);
+ check_true = (*it++ == kv("AB", 2));
+ assert(check_true);
+ assert(it == ite);
+
+ check_true = (*(--it) == kv("AB", 2));
+ assert(check_true);
+ check_true = (*(--it) == kv("A", 1));
+ assert(check_true);
+ assert(it == dbc.begin());
+
+ it = ite;
+ --it;
+ assert(*it-- == kv("AB", 2)); // test post-decrement operator.
+ assert(*it == kv("A", 1));
+}
+
+void trie_test_find_iterator()
+{
+ stack_printer __stack_printer__("::trie_test_find_iterator");
+ typedef trie_map<trie::std_string_traits, int> trie_map_type;
+ trie_map_type db;
+ const trie_map_type& dbc = db;
+
+ db.insert(MDDS_ASCII("a"), 1);
+ db.insert(MDDS_ASCII("aa"), 2);
+ db.insert(MDDS_ASCII("ab"), 3);
+ db.insert(MDDS_ASCII("b"), 4);
+ {
+ auto it = dbc.find(MDDS_ASCII("a"));
+ assert(it->first == "a");
+ assert(it->second == 1);
+ ++it;
+ assert(it->first == "aa");
+ assert(it->second == 2);
+ ++it;
+ assert(it->first == "ab");
+ assert(it->second == 3);
+ ++it;
+ assert(it->first == "b");
+ assert(it->second == 4);
+ ++it;
+ assert(it == dbc.end());
+
+ it = dbc.find(MDDS_ASCII("aa"));
+ assert(it->first == "aa");
+ assert(it->second == 2);
+ ++it;
+ assert(it->first == "ab");
+ assert(it->second == 3);
+ ++it;
+ assert(it->first == "b");
+ assert(it->second == 4);
+ ++it;
+ assert(it == dbc.end());
+
+ it = dbc.find(MDDS_ASCII("ab"));
+ assert(it->first == "ab");
+ assert(it->second == 3);
+ ++it;
+ assert(it->first == "b");
+ assert(it->second == 4);
+ ++it;
+ assert(it == dbc.end());
+
+ it = dbc.find(MDDS_ASCII("b"));
+ assert(it->first == "b");
+ assert(it->second == 4);
+ ++it;
+ assert(it == dbc.end());
+ }
+
+ trie_map_type::packed_type packed = db.pack();
+ {
+ auto it = packed.find(MDDS_ASCII("a"));
+ assert(it->first == "a");
+ assert(it->second == 1);
+ ++it;
+ assert(it->first == "aa");
+ assert(it->second == 2);
+ ++it;
+ assert(it->first == "ab");
+ assert(it->second == 3);
+ ++it;
+ assert(it->first == "b");
+ assert(it->second == 4);
+ ++it;
+ assert(it == packed.end());
+
+ it = packed.find(MDDS_ASCII("aa"));
+ assert(it->first == "aa");
+ assert(it->second == 2);
+ ++it;
+ assert(it->first == "ab");
+ assert(it->second == 3);
+ ++it;
+ assert(it->first == "b");
+ assert(it->second == 4);
+ ++it;
+ assert(it == packed.end());
+
+ it = packed.find(MDDS_ASCII("ab"));
+ assert(it->first == "ab");
+ assert(it->second == 3);
+ ++it;
+ assert(it->first == "b");
+ assert(it->second == 4);
+ ++it;
+ assert(it == packed.end());
+
+ it = packed.find(MDDS_ASCII("b"));
+ assert(it->first == "b");
+ assert(it->second == 4);
+ ++it;
+ assert(it == packed.end());
+ }
+}
+
+void trie_test_prefix_search()
+{
+ stack_printer __stack_printer__("::trie_test_prefix_search");
+
+ typedef trie_map<trie::std_string_traits, int> trie_map_type;
+ trie_map_type db;
+ const trie_map_type& dbc = db;
+
+ db.insert(MDDS_ASCII("a"), 1);
+ db.insert(MDDS_ASCII("aa"), 2);
+ db.insert(MDDS_ASCII("ab"), 3);
+ db.insert(MDDS_ASCII("b"), 4);
+
+ cout << "Performing prefix search on 'a'..." << endl;
+
+ trie_map_type::search_results results = dbc.prefix_search(MDDS_ASCII("a"));
+ auto it = results.begin();
+ auto ite = results.end();
+ assert(it != ite);
+ assert(it->first == "a");
+ assert(it->second == 1);
+ ++it;
+ assert(it->first == "aa");
+ assert(it->second == 2);
+ ++it;
+ assert(it->first == "ab");
+ assert(it->second == 3);
+ ++it;
+ assert(it == ite);
+ size_t n = std::distance(results.begin(), results.end());
+ assert(n == 3);
+
+ cout << "Performing prefix search on 'b'..." << endl;
+
+ results = dbc.prefix_search(MDDS_ASCII("b"));
+ it = results.begin();
+ ite = results.end();
+ assert(it != ite);
+ assert(it->first == "b");
+ assert(it->second == 4);
+ ++it;
+ assert(it == ite);
+ --it;
+ assert(it->first == "b");
+ assert(it->second == 4);
+ n = std::distance(results.begin(), results.end());
+ assert(n == 1);
+
+ // Only one element.
+ db.clear();
+ db.insert(MDDS_ASCII("dust"), 10);
+
+ cout << "Performing prefix search on 'du'..." << endl;
+
+ results = dbc.prefix_search(MDDS_ASCII("du"));
+ it = results.begin();
+ assert(it->first == "dust");
+ assert(it->second == 10);
+ bool check_true = (++it == results.end());
+ assert(check_true);
+ --it;
+ assert(it->first == "dust");
+ assert(it->second == 10);
+ n = std::distance(results.begin(), results.end());
+ assert(n == 1);
+}
+
+void trie_test_key_as_input()
+{
+ stack_printer __stack_printer__("::trie_test_key_as_input");
+
+ typedef trie_map<trie::std_string_traits, int> trie_map_type;
+ trie_map_type db;
+ const trie_map_type& dbc = db;
+
+ db.insert(std::string("string as key"), 1);
+ db.insert("literal as key", 2);
+
+ auto it = dbc.find("literal as key");
+ assert(it != dbc.end());
+ assert(it->first == "literal as key");
+ assert(it->second == 2);
+
+ auto results = dbc.prefix_search("str");
+ auto rit = results.begin();
+ assert(rit != results.end());
+ assert(rit->first == "string as key");
+ assert(rit->second == 1);
+ ++rit;
+ assert(rit == results.end());
+}
+
+void trie_test_copying()
+{
+ stack_printer __stack_printer__("::trie_test_copying");
+
+ typedef trie_map<trie::std_string_traits, int> trie_map_type;
+ trie_map_type db;
+ assert(db.empty());
+
+ {
+ auto db_copied(db);
+ assert(db_copied.empty());
+ }
+
+ db.insert("twenty", 20);
+ db.insert("twelve", 12);
+ assert(db.size() == 2);
+
+ {
+ // copy constructor
+ auto db_copied(db);
+ const trie_map_type& dbc_copied = db_copied;
+ assert(db_copied.size() == 2);
+
+ auto it = dbc_copied.find("twenty");
+ assert(it != dbc_copied.end());
+ assert(it->first == "twenty");
+ assert(it->second == 20);
+
+ it = dbc_copied.find("twelve");
+ assert(it != dbc_copied.end());
+ assert(it->first == "twelve");
+ assert(it->second == 12);
+ }
+
+ {
+ // copy assignment
+ trie_map_type db_copied;
+ db_copied = db;
+ const trie_map_type& dbc_copied = db_copied;
+ assert(db_copied.size() == 2);
+
+ auto it = dbc_copied.find("twenty");
+ assert(it != dbc_copied.end());
+ assert(it->first == "twenty");
+ assert(it->second == 20);
+
+ it = dbc_copied.find("twelve");
+ assert(it != dbc_copied.end());
+ assert(it->first == "twelve");
+ assert(it->second == 12);
+ }
+
+ {
+ // move constructor
+ auto db_copied(db);
+ auto db_moved(std::move(db_copied));
+ const trie_map_type& dbc_moved = db_moved;
+ assert(db_moved.size() == 2);
+ assert(db_copied.empty());
+
+ auto it = dbc_moved.find("twenty");
+ assert(it != dbc_moved.end());
+ assert(it->first == "twenty");
+ assert(it->second == 20);
+
+ it = dbc_moved.find("twelve");
+ assert(it != dbc_moved.end());
+ assert(it->first == "twelve");
+ assert(it->second == 12);
+ }
+
+ {
+ // move assignment
+ auto db_copied(db);
+ trie_map_type db_moved;
+ db_moved = std::move(db_copied);
+ const trie_map_type& dbc_moved = db_moved;
+ assert(db_moved.size() == 2);
+ assert(db_copied.empty());
+
+ auto it = dbc_moved.find("twenty");
+ assert(it != dbc_moved.end());
+ assert(it->first == "twenty");
+ assert(it->second == 20);
+
+ it = dbc_moved.find("twelve");
+ assert(it != dbc_moved.end());
+ assert(it->first == "twelve");
+ assert(it->second == 12);
+ }
+}
+
+void trie_test_value_update_from_iterator()
+{
+ stack_printer __stack_printer__("::trie_test_value_update_from_iterator");
+
+ typedef trie_map<trie::std_string_traits, int> trie_map_type;
+ trie_map_type db;
+ db.insert("one", 1);
+ db.insert("two", 2);
+ db.insert("three", 3);
+
+ trie_map_type::iterator it = db.begin();
+ assert(it->first == "one");
+ assert(it->second == 1);
+ it->second = 10; // update the value.
+ it = db.begin();
+ assert(it->first == "one");
+ assert(it->second == 10);
+
+ it = db.find("three");
+ assert(it->first == "three");
+ assert(it->second == 3);
+ it->second = 345; // update the value again.
+ it = db.find("three");
+ assert(it->first == "three");
+ assert(it->second == 345);
+}
+
+int main()
+{
+ try
+ {
+ trie_packed_test1();
+ trie_packed_test2();
+ trie_packed_test3();
+ trie_packed_test4();
+ trie_packed_test_value_life_cycle();
+ trie_packed_test_custom_string();
+ trie_packed_test_iterator_empty();
+ trie_packed_test_iterator();
+ trie_packed_test_prefix_search1();
+ trie_packed_test_key_as_input();
+ trie_packed_test_copying();
+ trie_packed_test_non_equal();
+ trie_packed_test_save_and_load_state::run();
+
+ trie_test1();
+ trie_test2();
+
+ trie_test_iterator_empty();
+ trie_test_iterator();
+ trie_test_iterator_with_erase();
+ trie_test_find_iterator();
+ trie_test_prefix_search();
+ trie_test_key_as_input();
+ trie_test_copying();
+ trie_test_value_update_from_iterator();
+ }
+ catch (const std::exception& e)
+ {
+ cout << "Test failed: " << e.what() << endl;
+ return EXIT_FAILURE;
+ }
+
+ cout << "Test finished successfully!" << endl;
+
+ return EXIT_SUCCESS;
+}
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-22 22:26:00 +0000