[proof-of-concept] Compact trie

CompactTrie.cpp

Index: CompactTrie.cpp
===================================================================
new file mode 100644
--- /dev/null
+++ b/CompactTrie.cpp
@@ -0,0 +1,144 @@
+#include <emscripten/bind.h>
+
+using namespace emscripten;
+
+class CompactTrieNode {
+ public:
+  ~CompactTrieNode() {
+    CompactTrieNode* child = last_child;
+
+    while (child) {
+      CompactTrieNode* sibling = child->previous_sibling;
+      delete child;
+      child = sibling;
+    }
+  }
+
+  std::string bytes() const {
+    std::string str;
+    const CompactTrieNode* node = this;
+
+    do {
+      str = node->key + str;
+      node = node->parent;
+    } while (node);
+
+    return str;
+  }
+
+ private:
+  std::string key;
+  int value = 0;
+
+  CompactTrieNode* parent = nullptr;
+  CompactTrieNode* last_child = nullptr;
+  CompactTrieNode* previous_sibling = nullptr;
+
+  friend class CompactTrie;
+};
+
+class CompactTrie {
+ public:
+  CompactTrie() {}
+
+  CompactTrieNode* set(const std::string& key, int value) {
+    std::string key_ = key;
+    CompactTrieNode* node = &this->root;
+
+    while (!key_.empty()) {
+      CompactTrieNode* child = node->last_child;
+
+      while (child && child->key[0] != key_[0])
+        child = child->previous_sibling;
+
+      if (child) {
+        size_t n = std::max(child->key.length(), key_.length());

[Manish Jethani, 2018/05/30 11:49:27]

This should be std::min

+        size_t i = 0;

[Manish Jethani, 2018/05/30 14:47:13]

This could start at 1 instead of 0.

+
+        for (; i < n && child->key[i] == key_[i]; i++);
+
+        if (i < child->key.length()) {
+          CompactTrieNode* grandchild = new CompactTrieNode();

[Manish Jethani, 2018/05/30 14:47:13]

Here we're basically splitting a child node into child and grandchild as we
realize that we have run into a substring of the node's key. "foobar" must be
split into "foo" (child) and "bar" (grandchild) when we come across "food"; the
end result is "foo", "bar", and "d". When "foist" is added, "foo" is again split
up into "fo" and "o" so "ist" can be introduced as a child of "fo".

+          grandchild->key = child->key.substr(i);
+          grandchild->last_child = child->last_child;
+          grandchild->parent = child;
+
+          CompactTrieNode* great_grandchild = grandchild->last_child;
+
+          while (great_grandchild) {
+            great_grandchild->parent = grandchild;
+            great_grandchild = great_grandchild->previous_sibling;
+          }
+
+          child->key = child->key.substr(0, i);
+          child->last_child = grandchild;
+        }
+
+        key_ = key_.substr(i);
+
+      } else {
+        child = new CompactTrieNode();
+        child->key = key_;
+        child->previous_sibling = node->last_child;
+        child->parent = node;
+
+        node->last_child = child;
+
+        key_.clear();
+      }
+
+      node = child;
+    }
+
+    node->value = value;
+    return node;
+  }
+
+  int get(const std::string& key) const {
+    std::string key_ = key;
+    const CompactTrieNode* node = &this->root;
+
+    while (!key_.empty()) {
+      CompactTrieNode* child = node->last_child;
+
+      while (child && child->key[0] != key_[0])
+        child = child->previous_sibling;
+
+      if (child) {
+        size_t n = std::max(child->key.length(), key_.length());

[Manish Jethani, 2018/05/30 11:49:27]

This should be std::min

+        size_t i = 0;

[Manish Jethani, 2018/05/30 14:47:13]

This could start at 1 instead of 0.

+
+        for (; i < n && child->key[i] == key_[i]; i++);
+
+        if (i < child->key.length())
+          return 0;
+
+        key_ = key_.substr(i);
+
+      } else {
+        return 0;
+      }
+
+      node = child;
+    }
+
+    return node->value;
+  }
+
+ private:
+  CompactTrieNode root;
+};
+
+EMSCRIPTEN_BINDINGS(CompactTrieNode) {
+  class_<CompactTrieNode>("CompactTrieNode")
+    .function("bytes", &CompactTrieNode::bytes)
+    ;
+}
+
+EMSCRIPTEN_BINDINGS(CompactTrie) {
+  class_<CompactTrie>("CompactTrie")
+    .constructor()
+    .function("set", &CompactTrie::set, allow_raw_pointers())
+    .function("get", &CompactTrie::get)
+    ;
+}