Package Exports
- xradix
- xradix/out/src/index.js
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 (xradix) to support the "exports" field. If that is not possible, create a JSPM override to customize the exports field for this package.
Readme
xradix
A fast, clean, tested, and documented implementation of the Radix Tree data structure.
Also, comes with special hooks for various tree-traversals starting at the first node matching a given prefix. These include depth-first (pre-order and post-order) and breadth-first.
This data structure is a performant and simple choice for implementing autocomplete.
Examples
const { RadixTree } = require('xradix');
const rt = new RadixTree<number>();
rt.set("xx", 1); // equivalently,
rt.set("xxA", 2); //
rt.set("xxB", 3); //
rt.set("xxC", 4); // new RadixTree([
rt.set("xxCxxA", 5); // ["xx", 1], ["xxA", 2], ["xxB", 3], ["xxC", 4],
rt.set("xxCxxB", 6); // ["xxCxxA", 5], ["xxCxxB", 6], ["xxCx", 7]
rt.set("xxCx", 7); // ])which creates this tree, whose node depths are marked above it
0 1 2 3 4 5
┌──A──( 2 )
├──B──( 3 )
( root )──xx──( 1 )─┤ ┌──A──( 5 )
└──C──( 4 )──x──( 7 )──x──( _ )─┤
└──B──( 6 )this tree now has the following behaviour:
rt.get("xxCx").value;// 7
rt.get("xxCx").depth;// 3
rt.get("not in the tree");// undefined
rt.getAll("");
/* generator* [
{ key: "xx", value: 1, depth: 1, ... }, default traversal: DFS pre-order
{ key: "xxA", value: 2, depth: 2, ... }, notice the node with no value is skipped
{ key: "xxB", value: 3, depth: 2, ... },
{ key: "xxC", value: 4, depth: 2, ... },
{ key: "xxCx", value: 7, depth: 3, ... },
{ key: "xxCxxA", value: 5, depth: 4, ... },
{ key: "xxCxxB", value: 6, depth: 4, ... },
] */
rt.get("xxCxx");// undefined
rt.get("xxCxx", { allNodes: true });// {key: "xxCxx", value: undefined, depth: 4, ...}
rt.getAll("xxCxx", { allNodes: true });
/* generator* [
{ key: "xxCxx", value: undefined, depth: 0, ... },
{ key: "xxcxxA", value: 6, depth: 1, ... },
{ key: "xxCxxB", value: 5, depth: 1, ... }, sibling nodes in random order
] */Support
