RadixTrie JS

Introduction

RadixTrie JS is a compressed trie data structure extending the @webkrafters/trie package class.

Name:

@webkrafters/radix-trie
Alternate: radix-trie.js

Installation

npm install --save @webkrafters/radix-trie

Usage

// imports default implementation of the radix-trie core.
import { DefaultImpl } from '@webkrafters/radix-trie';

const trie = new DefaultImpl<...>(...);

// imports string-only implementation of the radix-trie core.
import { StringImpl } from '@webkrafters/radix-trie';

const trie = new StringImpl(...);

// imports core radix-trie abstract class
import { Core } from '@webkrafters/radix-trie';

class CustomImpl<T> extends Core<T> {
  matches(...) : boolean { ... }
  merge(...) : void { ... }
}
const trie = new CustomImpl<number>(
    [[1,2,3,4,5,6],[1,2,6,3,8],...]
);

Implementations

This package contains 3 major items:

• A radix-trie core abstract class - to be exended as needed.
• Two out-of-the-box implementations:
  1. a default implementation and
  2. a string-only implementation
  of the abstract class.

New method

ViewInternalsAsNode Method.

viewInternalsAsNode(): TrieableNode<T>;

This method produces a TrieableNode representation holding the data exactly as stored in the trie.

Caveat:

The returned trieable node is not the real value of the trie. Therefore, with the exeception of the StringImpl trie instance, it cannot be guaranteed to recreate an identical trie instance.

Pro-tip:

To obtain trieable node corresponding to the real value of the trie, please use the asTrieableNode() method.

Abstract methods

The core abstract class contains two abstract methods. Although not expressly designated as abstract in the package due to Typescript and Javascript limitations, they require custom implementations.

This custom implementation requirement is enforced at runtime.

1. Matches Method.

matches(...): boolean;

This method matches any body of data which can be supplied to the implementation's constructor to create a new instance identical to this instance.

2. Merge Method.

merge(...): void;

This method merges any Trie instance and TrieableNode object into this instance as deemed compatible by its implementation.

More Reading

For the documentation on the rest of the properties and methods, please visit the base package documentation here:

https://github.com/webKrafters/trie.js/blob/master/docs.md

License

MIT