From: Jean Privat <jean@pryen.org>
Date: Mon, 15 Aug 2016 17:18:24 +0000 (-0400)
Subject: Merge: lib/trees: introduce Trie
X-Git-Url: http://nitlanguage.org

Merge: lib/trees: introduce Trie

### A trie (or prefix tree) is a datastructure used to perform prefix searches.

The trie uses an arborescent datastructure to perform searches on a prefix.
With this version of the trie, you can link data to nodes so the trie can
be used as a kind of Map by prefix.

~~~nit
# Associate some integers to Map keys
var trie = new Trie[Int]
trie["foo"] = 1
trie["fooo"] = 2
trie["foooo"] = 3
trie["bar"] = 4
trie["baz"] = 5

# Get stored values by key
print trie.has_key("foo")
print trie["foo"] == 1

# Get stored values by prefix
assert trie.has_prefix("fo")
assert not trie.has_prefix("z")
assert trie.find_by_prefix("foo") == [1, 2, 3]
assert trie.find_by_prefix("bar") == [4]
assert trie.find_by_prefix("z").is_empty
~~~

Signed-off-by: Alexandre Terrasa <alexandre@moz-code.org>

Pull-Request: #2261
Reviewed-by: Jean Privat <jean@pryen.org>
Reviewed-by: Lucas Bajolet <r4pass@hotmail.com>
---

7b2cab80fa08e87067b257f618870623d6b6fa3a