Sign Up for Free

RunKit +

Try any Node.js package right in your browser

This is a playground to test code. It runs a full Node.js environment and already has all of npm’s 1,000,000+ packages pre-installed, including digital-tree with all npm packages installed. Try it out:

var digitalTree = require("digital-tree")

This service is provided by RunKit and is not affiliated with npm, Inc or the package authors.

digital-tree v2.0.1

trie data structure

digital tree

A trie data structure implementation.

  • thorough testing
  • utility: clonable and serializable (to/from json)
  • search values by prefix

Install

npm install --save digital-tree

version 2.0.0 is almost a complete rewrite and mostly not backwards compatible

API

create() / Ctor

using `create()`` is the recommended way to construct new digital trees:

    const Trie = require('digital-tree')
    const trie = Trie.create()

put(key, value)

Put something in the tree

    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(key)

Get something from the tree

    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'

Iteration

A trie is iterable. Iteration order is either DFS or BFS

    const Trie = require('digital-tree')
    const trie = Trie.create()
    trie.put('abc', 1)
    trie.put('abd', 2)
    trie.put('abe', 3)

    for (let [key, value] of trie) {

    }

search(prefix)

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)

    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] ]

getSubTrie(key, [shallow=false])

Obtain an either cloned or shallow copy of a subtree.

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 shallow to true will create a view rather than cloning the sub trie

remove(key)

Remove something from the tree. This will remove the entire subtree that exists under this specified key and return it as a new trie.

    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'
RunKit is a free, in-browser JavaScript dev environment for prototyping Node.js code, with every npm package installed. Sign up to share your code.
Sign Up for Free