trie data structure
npm install digital-treeA trie data structure implementation.
- thorough testing
- utility: clonable and serializable (to/from json)
- search values by prefix
npm install --save digital-tree
version 2.0.0 is almost a complete rewrite and mostly not backwards compatible
using create() is the recommended way to construct new digital trees:
`javascript`
const Trie = require('digital-tree')
const trie = Trie.create()
Put something in the tree
`javascript`
trie.put(['a', 'path', 'to'], 'something')
trie.put(['another', 'thing']) // equivalent to trie.put(['another', 'thing'], true)
trie.put('strings also', 'work') // equivalent to trie.put('strings also'.split(''), 'work')
// this only work with the exact key (reference)
const objectKey = [{ foo: 'bar' }, { bar: 'foo'}]
trie.put(objectKey, { some: 'thing'})
Get something from the tree
`javascript
const trie = Trie.create()
trie.put(['a', 'path', 'to'], 'v1')
trie.put('also strings', 'v2')
console.log(trie.get([])) // prints 'foo'
console.log(trie.get(Trie.root)) // prints 'foo'
console.log(trie.get(['a', 'path', 'to'])) // prints 'v1'
console.log(trie.get('also strings')) // prints 'v2'
`
A trie is iterable. Iteration order is either DFS or BFS
`javascript
const Trie = require('digital-tree')
const trie = Trie.create()
trie.put('abc', 1)
trie.put('abd', 2)
trie.put('abe', 3)
for (let value of trie) {
}
`
Search and return all the values in the tree that are nested under the provided prefix.
The results will be an Iterator over the matching values. The order of iteration is defined based on the default ordering of the trie (BFS/DFS)
`javascript
const trie = Trie.create()
trie.put('abc', 1)
trie.put('abd', 2)
trie.put('abe', 3)
console.log(Array.from(trie.search('ab'))) // prints [ 3, 2, 1 ]
console.log(Array.from(trie.search('ab', { includeKeys: true }))) // prints [ [['a','b','e'], 3 ], [['a','b','d'], 2], [['a','b','c'], 1] ]
`
Obtain either a cloned, or shallow copy of a subtree.
`javascript
trie.put('abc', 1)
trie.put('abd', 2)
const subTrie = trie.getSubTrie('ab')
console.log(subTrie.get('c')) // prints 1
console.log(subTrie.get('d')) // prints 2
console.log(subTrie.get('ab')) // prints undefined
`
setting to true will create a view rather than cloning the sub trie
Remove something from the tree. This will remove the entire subtree that exists under this specified key and return it
as a new trie.
`javascript
trie.put(['a', 'b'], 'ab')
trie.put(['a', 'b', 'c'], 'abc')
trie.put(['a', 'b', 'c', 1], 'abc1')
trie.put(['a', 'b', 'c', 2], 'abc2')
const removed = trie.remove(['a', 'b', 'c'])
console.log(removed.get([1])) // prints 'abc1'
console.log(removed.get([2])) // prints 'abc2'
console.log(trie.get(['a', 'b', 'c', 1])) // prints 'undefined'
console.log(trie.get(['a', 'b'])) // prints 'ab'
``