Package Exports

@kamilmielnik/trie

This package does not declare an exports field, so the exports above have been automatically detected and optimized by JSPM instead. If any package subpath is missing, it is recommended to post an issue to the original package (@kamilmielnik/trie) to support the "exports" field. If that is not possible, create a JSPM override to customize the exports field for this package.

Readme

@kamilmielnik/trie

Version Dependencies Vulnerabilities

Trie data structure implementation (in TypeScript). Highly performant. No dependencies. Built for a Scrabble Solver.

Installation

npm install @kamilmielnik/trie --save

Usage

import { Trie } from '@kamilmielnik/trie';

const trie = new Trie();
trie.add('word');
console.log(trie.has('word')); // true

API

See full API Docs - generated by typedoc.

Good to know:

all objects are mutable
every class, interface, type, constant and function is exported
all exports are named (there is no default export)

There are 2 ways to use API.

Object-oriented API

Create Trie instance and use its' methods.

Usage

import { Trie } from '@kamilmielnik/trie';

const trie = new Trie();
trie.add('master');
trie.add('mask');
console.log(trie.hasPrefix('man')); // false
console.log(trie.hasPrefix('mas')); // true
console.log(trie.has('mas')); // false
console.log(trie.remove('mas')); // false
console.log(trie.has('master')); // true
console.log(trie.serialize()); // "(m(a(s(t(e(r))k))))"
console.log(trie.remove('master')); // true
console.log(trie.serialize()); // "(m(a(s(k))))"

Functional API

Manipulate existing instances of Node with functions.

Usage

The following snippet works identical to the object-oriented example above.

import { add, has, hasPrefix, Node, remove, serialize } from '@kamilmielnik/trie';

const root: Node = {};

add(root, 'master');
add(root, 'mask');
console.log(hasPrefix(root, 'man')); // false
console.log(hasPrefix(root, 'mas')); // true
console.log(has(root, 'mas')); // false
console.log(remove(root, 'mas')); // false
console.log(has(root, 'master')); // true
console.log(serialize(root)); // "(m(a(s(t(e(r))k))))"
console.log(remove(root, 'master')); // true
console.log(serialize(root)); // "(m(a(s(k))))"

Examples

Load dictionary from file

import { fromArray, Node } from '@kamilmielnik/trie';
import fs from 'fs';

const fromFile = (filepath: string): Node => {
  const file = fs.readFileSync(filepath, 'utf-8');
  // Assuming file contains 1 word per line
  const words = file.split('\n').filter(Boolean);
  const node = fromArray(words);
  return node;
};

Load serialized `Node` from a file

import { deserialize, Node } from '@kamilmielnik/trie';
import fs from 'fs';

const fromFile = (filepath: string): Node => {
  const file = fs.readFileSync(filepath, 'utf-8');
  const node = deserialize(words);
  return node;
};

Serialize `Node` to a file

import { serialize, Trie } from '@kamilmielnik/trie';
import fs from 'fs';

const toFile = (trie: Trie): void => {
  const serialized = trie.serialize();
  fs.writeFileSync(filepath, serialized);
};

Find all words with given prefix

import { find, Node, toArray } from '@kamilmielnik/trie';

const findWordsWithPrefix = (node: Node, prefix: string): string[] => {
  const prefixNode = find(node, prefix) || {};
  const descendants = toArray(prefixNode, { prefix, sort: true, wordsOnly: true });
  const words = descendants.map(({ prefix: word }) => word);
  return words;
};