1f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath#include <sstream> 2f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 3f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath#include <marisa.h> 4f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 5f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath#include "assert.h" 6f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 7f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamathnamespace { 8f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 9f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamathclass FindCallback { 10f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath public: 11f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath FindCallback(std::vector<marisa::UInt32> *key_ids, 12f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath std::vector<std::size_t> *key_lengths) 13f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath : key_ids_(key_ids), key_lengths_(key_lengths) {} 14f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath FindCallback(const FindCallback &callback) 15f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath : key_ids_(callback.key_ids_), key_lengths_(callback.key_lengths_) {} 16f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 17f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath bool operator()(marisa::UInt32 key_id, std::size_t key_length) const { 18f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath key_ids_->push_back(key_id); 19f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath key_lengths_->push_back(key_length); 20f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath return true; 21f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath } 22f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 23f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath private: 24f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath std::vector<marisa::UInt32> *key_ids_; 25f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath std::vector<std::size_t> *key_lengths_; 26f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 27f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath // Disallows assignment. 28f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath FindCallback &operator=(const FindCallback &); 29f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath}; 30f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 31f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamathclass PredictCallback { 32f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath public: 33f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath PredictCallback(std::vector<marisa::UInt32> *key_ids, 34f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath std::vector<std::string> *keys) 35f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath : key_ids_(key_ids), keys_(keys) {} 36f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath PredictCallback(const PredictCallback &callback) 37f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath : key_ids_(callback.key_ids_), keys_(callback.keys_) {} 38f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 39f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath bool operator()(marisa::UInt32 key_id, const std::string &key) const { 40f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath key_ids_->push_back(key_id); 41f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath keys_->push_back(key); 42f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath return true; 43f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath } 44f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 45f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath private: 46f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath std::vector<marisa::UInt32> *key_ids_; 47f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath std::vector<std::string> *keys_; 48f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 49f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath // Disallows assignment. 50f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath PredictCallback &operator=(const PredictCallback &); 51f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath}; 52f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 53f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamathvoid TestTrie() { 54f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath TEST_START(); 55f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 56f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath marisa::Trie trie; 57f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 58f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_tries() == 0); 59f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_keys() == 0); 60f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_nodes() == 0); 61f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.total_size() == (sizeof(marisa::UInt32) * 23)); 62f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 63f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath std::vector<std::string> keys; 64f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath trie.build(keys); 65f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_tries() == 1); 66f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_keys() == 0); 67f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_nodes() == 1); 68f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 69f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath keys.push_back("apple"); 70f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath keys.push_back("and"); 71f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath keys.push_back("Bad"); 72f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath keys.push_back("apple"); 73f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath keys.push_back("app"); 74f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 75f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath std::vector<marisa::UInt32> key_ids; 76f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath trie.build(keys, &key_ids, 1 | MARISA_WITHOUT_TAIL | MARISA_LABEL_ORDER); 77f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 78f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_tries() == 1); 79f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_keys() == 4); 80f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_nodes() == 11); 81f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 82f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(key_ids.size() == 5); 83f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(key_ids[0] == 3); 84f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(key_ids[1] == 1); 85f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(key_ids[2] == 0); 86f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(key_ids[3] == 3); 87f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(key_ids[4] == 2); 88f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 89f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath char key_buf[256]; 90f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath std::size_t key_length; 91f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath for (std::size_t i = 0; i < keys.size(); ++i) { 92f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf)); 93f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 94f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie[keys[i]] == key_ids[i]); 95f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie[key_ids[i]] == keys[i]); 96f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(key_length == keys[i].length()); 97f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(keys[i] == key_buf); 98f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath } 99f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 100f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath trie.clear(); 101f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 102f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_tries() == 0); 103f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_keys() == 0); 104f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_nodes() == 0); 105f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.total_size() == (sizeof(marisa::UInt32) * 23)); 106f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 107f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath trie.build(keys, &key_ids, 1 | MARISA_WITHOUT_TAIL | MARISA_WEIGHT_ORDER); 108f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 109f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_tries() == 1); 110f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_keys() == 4); 111f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_nodes() == 11); 112f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 113f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(key_ids.size() == 5); 114f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(key_ids[0] == 3); 115f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(key_ids[1] == 1); 116f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(key_ids[2] == 2); 117f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(key_ids[3] == 3); 118f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(key_ids[4] == 0); 119f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 120f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath for (std::size_t i = 0; i < keys.size(); ++i) { 121f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie[keys[i]] == key_ids[i]); 122f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie[key_ids[i]] == keys[i]); 123f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath } 124f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 125f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie["appl"] == trie.notfound()); 126f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie["applex"] == trie.notfound()); 127f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.find_first("ap") == trie.notfound()); 128f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.find_first("applex") == trie["app"]); 129f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.find_last("ap") == trie.notfound()); 130f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.find_last("applex") == trie["apple"]); 131f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 132f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath std::vector<marisa::UInt32> ids; 133f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.find("ap", &ids) == 0); 134f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.find("applex", &ids) == 2); 135f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids.size() == 2); 136f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids[0] == trie["app"]); 137f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids[1] == trie["apple"]); 138f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 139f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath std::vector<std::size_t> lengths; 140f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.find("Baddie", &ids, &lengths) == 1); 141f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids.size() == 3); 142f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids[2] == trie["Bad"]); 143f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(lengths.size() == 1); 144f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(lengths[0] == 3); 145f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 146f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.find_callback("anderson", FindCallback(&ids, &lengths)) == 1); 147f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids.size() == 4); 148f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids[3] == trie["and"]); 149f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(lengths.size() == 2); 150f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(lengths[1] == 3); 151f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 152f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.predict("") == 4); 153f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.predict("a") == 3); 154f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.predict("ap") == 2); 155f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.predict("app") == 2); 156f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.predict("appl") == 1); 157f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.predict("apple") == 1); 158f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.predict("appleX") == 0); 159f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.predict("X") == 0); 160f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 161f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ids.clear(); 162f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.predict("a", &ids) == 3); 163f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids.size() == 3); 164f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids[0] == trie["app"]); 165f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids[1] == trie["and"]); 166f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids[2] == trie["apple"]); 167f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 168f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath std::vector<std::string> strs; 169f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.predict("a", &ids, &strs) == 3); 170f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids.size() == 6); 171f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids[3] == trie["app"]); 172f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids[4] == trie["apple"]); 173f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids[5] == trie["and"]); 174f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(strs[0] == "app"); 175f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(strs[1] == "apple"); 176f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(strs[2] == "and"); 177f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 178f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath TEST_END(); 179f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath} 180f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 181f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamathvoid TestPrefixTrie() { 182f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath TEST_START(); 183f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 184f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath std::vector<std::string> keys; 185f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath keys.push_back("after"); 186f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath keys.push_back("bar"); 187f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath keys.push_back("car"); 188f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath keys.push_back("caster"); 189f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 190f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath marisa::Trie trie; 191f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath std::vector<marisa::UInt32> key_ids; 192f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath trie.build(keys, &key_ids, 1 | MARISA_PREFIX_TRIE 193f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath | MARISA_TEXT_TAIL | MARISA_LABEL_ORDER); 194f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 195f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_tries() == 1); 196f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_keys() == 4); 197f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_nodes() == 7); 198f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 199f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath char key_buf[256]; 200f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath std::size_t key_length; 201f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath for (std::size_t i = 0; i < keys.size(); ++i) { 202f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf)); 203f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 204f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie[keys[i]] == key_ids[i]); 205f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie[key_ids[i]] == keys[i]); 206f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(key_length == keys[i].length()); 207f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(keys[i] == key_buf); 208f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath } 209f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 210f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath key_length = trie.restore(key_ids[0], NULL, 0); 211f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 212f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(key_length == keys[0].length()); 213f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath EXCEPT(trie.restore(key_ids[0], NULL, 5), MARISA_PARAM_ERROR); 214f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 215f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath key_length = trie.restore(key_ids[0], key_buf, 5); 216f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 217f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(key_length == keys[0].length()); 218f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 219f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath key_length = trie.restore(key_ids[0], key_buf, 6); 220f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 221f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(key_length == keys[0].length()); 222f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 223f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath trie.build(keys, &key_ids, 2 | MARISA_PREFIX_TRIE 224f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath | MARISA_WITHOUT_TAIL | MARISA_WEIGHT_ORDER); 225f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 226f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_tries() == 2); 227f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_keys() == 4); 228f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_nodes() == 16); 229f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 230f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath for (std::size_t i = 0; i < keys.size(); ++i) { 231f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf)); 232f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 233f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie[keys[i]] == key_ids[i]); 234f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie[key_ids[i]] == keys[i]); 235f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(key_length == keys[i].length()); 236f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(keys[i] == key_buf); 237f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath } 238f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 239f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath key_length = trie.restore(key_ids[0], NULL, 0); 240f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 241f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(key_length == keys[0].length()); 242f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath EXCEPT(trie.restore(key_ids[0], NULL, 5), MARISA_PARAM_ERROR); 243f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 244f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath key_length = trie.restore(key_ids[0], key_buf, 5); 245f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 246f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(key_length == keys[0].length()); 247f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 248f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath key_length = trie.restore(key_ids[0], key_buf, 6); 249f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 250f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(key_length == keys[0].length()); 251f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 252f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath trie.build(keys, &key_ids, 2 | MARISA_PREFIX_TRIE 253f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath | MARISA_TEXT_TAIL | MARISA_LABEL_ORDER); 254f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 255f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_tries() == 2); 256f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_keys() == 4); 257f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_nodes() == 14); 258f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 259f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath for (std::size_t i = 0; i < keys.size(); ++i) { 260f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf)); 261f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 262f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie[keys[i]] == key_ids[i]); 263f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie[key_ids[i]] == keys[i]); 264f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(key_length == keys[i].length()); 265f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(keys[i] == key_buf); 266f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath } 267f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 268f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath trie.save("trie-test.dat"); 269f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath trie.clear(); 270f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath marisa::Mapper mapper; 271f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath trie.mmap(&mapper, "trie-test.dat"); 272f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 273f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(mapper.is_open()); 274f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_tries() == 2); 275f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_keys() == 4); 276f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_nodes() == 14); 277f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 278f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath for (std::size_t i = 0; i < keys.size(); ++i) { 279f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf)); 280f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 281f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie[keys[i]] == key_ids[i]); 282f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie[key_ids[i]] == keys[i]); 283f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(key_length == keys[i].length()); 284f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(keys[i] == key_buf); 285f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath } 286f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 287f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath std::stringstream stream; 288f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath trie.write(stream); 289f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath trie.clear(); 290f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath trie.read(stream); 291f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 292f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_tries() == 2); 293f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_keys() == 4); 294f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_nodes() == 14); 295f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 296f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath for (std::size_t i = 0; i < keys.size(); ++i) { 297f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf)); 298f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 299f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie[keys[i]] == key_ids[i]); 300f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie[key_ids[i]] == keys[i]); 301f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(key_length == keys[i].length()); 302f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(keys[i] == key_buf); 303f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath } 304f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 305f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath trie.build(keys, &key_ids, 3 | MARISA_PREFIX_TRIE 306f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath | MARISA_WITHOUT_TAIL | MARISA_WEIGHT_ORDER); 307f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 308f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_tries() == 3); 309f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_keys() == 4); 310f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_nodes() == 19); 311f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 312f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath for (std::size_t i = 0; i < keys.size(); ++i) { 313f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf)); 314f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 315f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie[keys[i]] == key_ids[i]); 316f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie[key_ids[i]] == keys[i]); 317f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(key_length == keys[i].length()); 318f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(keys[i] == key_buf); 319f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath } 320f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 321f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie["ca"] == trie.notfound()); 322f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie["card"] == trie.notfound()); 323f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 324f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath std::size_t length = 0; 325f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.find_first("ca") == trie.notfound()); 326f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.find_first("car") == trie["car"]); 327f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.find_first("card", &length) == trie["car"]); 328f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(length == 3); 329f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 330f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.find_last("afte") == trie.notfound()); 331f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.find_last("after") == trie["after"]); 332f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.find_last("afternoon", &length) == trie["after"]); 333f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(length == 5); 334f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 335f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath { 336f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath std::vector<marisa::UInt32> ids; 337f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath std::vector<std::size_t> lengths; 338f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.find("card", &ids, &lengths) == 1); 339f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids.size() == 1); 340f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids[0] == trie["car"]); 341f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(lengths.size() == 1); 342f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(lengths[0] == 3); 343f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 344f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.predict("ca", &ids) == 2); 345f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids.size() == 3); 346f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids[1] == trie["car"]); 347f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids[2] == trie["caster"]); 348f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 349f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.predict("ca", &ids, NULL, 1) == 1); 350f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids.size() == 4); 351f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids[3] == trie["car"]); 352f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 353f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath std::vector<std::string> strs; 354f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.predict("ca", &ids, &strs, 1) == 1); 355f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids.size() == 5); 356f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids[4] == trie["car"]); 357f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(strs.size() == 1); 358f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(strs[0] == "car"); 359f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 360f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.predict_callback("", PredictCallback(&ids, &strs)) == 4); 361f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids.size() == 9); 362f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids[5] == trie["car"]); 363f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids[6] == trie["caster"]); 364f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids[7] == trie["after"]); 365f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids[8] == trie["bar"]); 366f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(strs.size() == 5); 367f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(strs[1] == "car"); 368f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(strs[2] == "caster"); 369f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(strs[3] == "after"); 370f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(strs[4] == "bar"); 371f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath } 372f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 373f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath { 374f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath marisa::UInt32 ids[10]; 375f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath std::size_t lengths[10]; 376f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.find("card", ids, lengths, 10) == 1); 377f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids[0] == trie["car"]); 378f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(lengths[0] == 3); 379f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 380f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.predict("ca", ids, NULL, 10) == 2); 381f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids[0] == trie["car"]); 382f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids[1] == trie["caster"]); 383f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 384f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.predict("ca", ids, NULL, 1) == 1); 385f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids[0] == trie["car"]); 386f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 387f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath std::string strs[10]; 388f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.predict("ca", ids, strs, 1) == 1); 389f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids[0] == trie["car"]); 390f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(strs[0] == "car"); 391f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 392f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.predict("", ids, strs, 10) == 4); 393f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids[0] == trie["car"]); 394f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids[1] == trie["caster"]); 395f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids[2] == trie["after"]); 396f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids[3] == trie["bar"]); 397f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(strs[0] == "car"); 398f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(strs[1] == "caster"); 399f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(strs[2] == "after"); 400f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(strs[3] == "bar"); 401f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath } 402f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 403f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath TEST_END(); 404f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath} 405f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 406f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamathvoid TestPatriciaTrie() { 407f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath TEST_START(); 408f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 409f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath std::vector<std::string> keys; 410f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath keys.push_back("bach"); 411f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath keys.push_back("bet"); 412f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath keys.push_back("chat"); 413f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath keys.push_back("check"); 414f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath keys.push_back("check"); 415f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 416f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath marisa::Trie trie; 417f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath std::vector<marisa::UInt32> key_ids; 418f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath trie.build(keys, &key_ids, 1); 419f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 420f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_tries() == 1); 421f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_keys() == 4); 422f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_nodes() == 7); 423f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 424f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(key_ids.size() == 5); 425f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(key_ids[0] == 2); 426f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(key_ids[1] == 3); 427f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(key_ids[2] == 1); 428f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(key_ids[3] == 0); 429f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(key_ids[4] == 0); 430f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 431f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath char key_buf[256]; 432f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath std::size_t key_length; 433f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath for (std::size_t i = 0; i < keys.size(); ++i) { 434f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf)); 435f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 436f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie[keys[i]] == key_ids[i]); 437f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie[key_ids[i]] == keys[i]); 438f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(key_length == keys[i].length()); 439f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(keys[i] == key_buf); 440f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath } 441f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 442f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath trie.build(keys, &key_ids, 2 | MARISA_WITHOUT_TAIL); 443f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 444f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_tries() == 2); 445f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_keys() == 4); 446f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_nodes() == 17); 447f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 448f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath for (std::size_t i = 0; i < keys.size(); ++i) { 449f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf)); 450f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 451f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie[keys[i]] == key_ids[i]); 452f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie[key_ids[i]] == keys[i]); 453f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(key_length == keys[i].length()); 454f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(keys[i] == key_buf); 455f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath } 456f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 457f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath trie.build(keys, &key_ids, 2); 458f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 459f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_tries() == 2); 460f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_keys() == 4); 461f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_nodes() == 14); 462f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 463f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath for (std::size_t i = 0; i < keys.size(); ++i) { 464f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf)); 465f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 466f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie[keys[i]] == key_ids[i]); 467f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie[key_ids[i]] == keys[i]); 468f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(key_length == keys[i].length()); 469f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(keys[i] == key_buf); 470f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath } 471f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 472f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath trie.build(keys, &key_ids, 3 | MARISA_WITHOUT_TAIL); 473f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 474f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_tries() == 3); 475f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_keys() == 4); 476f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_nodes() == 20); 477f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 478f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath for (std::size_t i = 0; i < keys.size(); ++i) { 479f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf)); 480f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 481f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie[keys[i]] == key_ids[i]); 482f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie[key_ids[i]] == keys[i]); 483f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(key_length == keys[i].length()); 484f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(keys[i] == key_buf); 485f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath } 486f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 487f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath std::stringstream stream; 488f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath trie.write(stream); 489f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath trie.clear(); 490f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath trie.read(stream); 491f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 492f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_tries() == 3); 493f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_keys() == 4); 494f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_nodes() == 20); 495f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 496f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath for (std::size_t i = 0; i < keys.size(); ++i) { 497f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath key_length = trie.restore(key_ids[i], key_buf, sizeof(key_buf)); 498f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 499f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie[keys[i]] == key_ids[i]); 500f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie[key_ids[i]] == keys[i]); 501f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(key_length == keys[i].length()); 502f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(keys[i] == key_buf); 503f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath } 504f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 505f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath TEST_END(); 506f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath} 507f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 508f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamathvoid TestEmptyString() { 509f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath TEST_START(); 510f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 511f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath std::vector<std::string> keys; 512f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath keys.push_back(""); 513f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 514f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath marisa::Trie trie; 515f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath std::vector<marisa::UInt32> key_ids; 516f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath trie.build(keys, &key_ids); 517f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 518f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_tries() == 1); 519f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_keys() == 1); 520f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_nodes() == 1); 521f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 522f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(key_ids.size() == 1); 523f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(key_ids[0] == 0); 524f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 525f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie[""] == 0); 526f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie[(marisa::UInt32)0] == ""); 527f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 528f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie["x"] == trie.notfound()); 529f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.find_first("") == 0); 530f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.find_first("x") == 0); 531f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.find_last("") == 0); 532f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.find_last("x") == 0); 533f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 534f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath std::vector<marisa::UInt32> ids; 535f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.find("xyz", &ids) == 1); 536f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids.size() == 1); 537f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids[0] == trie[""]); 538f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 539f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath std::vector<std::size_t> lengths; 540f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.find("xyz", &ids, &lengths) == 1); 541f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids.size() == 2); 542f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids[0] == trie[""]); 543f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids[1] == trie[""]); 544f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(lengths.size() == 1); 545f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(lengths[0] == 0); 546f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 547f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.find_callback("xyz", FindCallback(&ids, &lengths)) == 1); 548f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids.size() == 3); 549f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids[2] == trie[""]); 550f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(lengths.size() == 2); 551f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(lengths[1] == 0); 552f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 553f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.predict("xyz", &ids) == 0); 554f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 555f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.predict("", &ids) == 1); 556f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids.size() == 4); 557f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids[3] == trie[""]); 558f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 559f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath std::vector<std::string> strs; 560f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.predict("", &ids, &strs) == 1); 561f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids.size() == 5); 562f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids[4] == trie[""]); 563f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(strs[0] == ""); 564f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 565f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath TEST_END(); 566f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath} 567f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 568f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamathvoid TestBinaryKey() { 569f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath TEST_START(); 570f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 571f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath std::string binary_key = "NP"; 572f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath binary_key += '\0'; 573f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath binary_key += "Trie"; 574f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 575f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath std::vector<std::string> keys; 576f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath keys.push_back(binary_key); 577f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 578f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath marisa::Trie trie; 579f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath std::vector<marisa::UInt32> key_ids; 580f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath trie.build(keys, &key_ids, 1 | MARISA_WITHOUT_TAIL); 581f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 582f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_tries() == 1); 583f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_keys() == 1); 584f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_nodes() == 8); 585f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(key_ids.size() == 1); 586f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 587f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath char key_buf[256]; 588f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath std::size_t key_length; 589f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath key_length = trie.restore(0, key_buf, sizeof(key_buf)); 590f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 591f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie[keys[0]] == key_ids[0]); 592f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie[key_ids[0]] == keys[0]); 593f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(std::string(key_buf, key_length) == keys[0]); 594f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 595f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath trie.build(keys, &key_ids, 1 | MARISA_PREFIX_TRIE | MARISA_BINARY_TAIL); 596f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 597f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_tries() == 1); 598f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_keys() == 1); 599f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_nodes() == 2); 600f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(key_ids.size() == 1); 601f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 602f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath key_length = trie.restore(0, key_buf, sizeof(key_buf)); 603f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 604f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie[keys[0]] == key_ids[0]); 605f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie[key_ids[0]] == keys[0]); 606f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(std::string(key_buf, key_length) == keys[0]); 607f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 608f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath trie.build(keys, &key_ids, 1 | MARISA_PREFIX_TRIE | MARISA_TEXT_TAIL); 609f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 610f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_tries() == 1); 611f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_keys() == 1); 612f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.num_nodes() == 2); 613f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(key_ids.size() == 1); 614f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 615f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath key_length = trie.restore(0, key_buf, sizeof(key_buf)); 616f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 617f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie[keys[0]] == key_ids[0]); 618f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie[key_ids[0]] == keys[0]); 619f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(std::string(key_buf, key_length) == keys[0]); 620f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 621f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath std::vector<marisa::UInt32> ids; 622f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.predict_breadth_first("", &ids) == 1); 623f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids.size() == 1); 624f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids[0] == key_ids[0]); 625f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 626f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath std::vector<std::string> strs; 627f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(trie.predict_depth_first("NP", &ids, &strs) == 1); 628f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids.size() == 2); 629f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(ids[1] == key_ids[0]); 630f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath ASSERT(strs[0] == keys[0]); 631f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 632f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath TEST_END(); 633f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath} 634f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 635f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath} // namespace 636f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 637f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamathint main() { 638f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath TestTrie(); 639f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath TestPrefixTrie(); 640f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath TestPatriciaTrie(); 641f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath TestEmptyString(); 642f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath TestBinaryKey(); 643f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath 644f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath return 0; 645f163f6985a63328d07e3de249ad3daf4a0c67d8aNarayan Kamath} 646