basic-trie

A tiny TypeScript trie implementation with limited wildcards support.

Installation

npm add basic-trie

Usage

import Trie from 'basic-trie';

// Create a new trie.
const trie = new Trie<number, string>();

trie.get([1, 2, 3]);
// undefined

// Set a value.
trie.set([1, 2, 3], '123');

trie.get([1, 2, 3]);
// '123'

trie.get([1, 2]);
// null
// Returns null instead of undefined as [1, 2] matches a part of a record path [1, 2, 3].

trie.get([1, 2, 3, 4]);
// undefined

trie.get([1]);
// null (partial match)

trie.get([2, 1]);
// undefined

Wildcards support

Wildcards are supported by overriding a few methods of Trie class, example:

import Trie, { PayloadType } from 'basic-trie';

class MyTrie extends Trie<string, string> {
  isKeyWildcard(key: string): boolean {
    return key.startsWith(':');
  }

  getWildcardPayload(
    key: string,
    wildcardName: string,
    _wildcardValue: string | null,
  ): PayloadType | undefined {
    return {
      [wildcardName.substr(1)]: key,
    };
  }
}

// Helper funcs to demonstrate uses of wildcards.
function splitPathString(s: string): string[] {
  return s.split('/');
}

function addMyPath(trie: MyTrie, s: string) {
  trie.set(splitPathString(s), s);
}

const trie = new MyTrie();
addMyPath(trie, ':a');
addMyPath(trie, ':b');
addMyPath(trie, ':c/:sub1');
addMyPath(trie, 'imp/:sub2');
trie.getWithPayload(['a']);
// ['a'] matches wildcard ':a'
// Prints [':a', { a: 'a' }]

trie.getWithPayload(['a', 'b', 'c']);
// No match
// Prints [undefined, undefined]

trie.getWithPayload(['a', 'b']);
// ['a', 'b'] matches two consecutive wildcards ':c/:sub1'.
// Prints [':c/:sub1', { c: 'a', sub1: 'b' }]

trie.getWithPayload(['imp', 'b']);
// ['imp', 'b'] actually matches both ':c/:sub1' and 'imp/:sub2',
// but 'imp/:sub2' takes precedence as 'imp' is not a wildcard.
// Prints ['imp/:sub2', { sub2: 'b' }]