short-tree
ShortTree
is a class extending RBTree
from bintrees, and works explicitly on nodes of arrays.
The ShortTree< T >
class extends RBTree< Array< T > >
.
insert
is overloaded and behaves differently. When adding a node, it will first check if there is another shorter node being the beginning of the to-be-inserted node, and if so, won't insert. It also checks if there are existing longer nodes which begin with the newly inserted node, and deletes them.
A new function is added values()
which returns Array< Array< T > >
, i.e. an array of all nodes (and again, each node is an array of T
).
Algorithm
When inserting [ 'a', 'b', 'c', 'd' ]
, one node is inserted with this value.
Inserting [ 'x', 'y' ]
, will insert one new node.
If later, [ 'a', 'b', 'c', 'd', 'e' ]
is inserted, it won't be - there's already a "shorter" version of this node (the first one inserted).
If later, [ 'a', 'b' ]
is inserted, the first node [ 'a', 'b', 'c', 'd' ]
will be removed (or "chopped off" after b
).
API
Construct a ShortTree
by giving the comparison function for T
.
If T
is number
e.g., this could be (a, b) => a - b
.
Example
import { ShortTree } from 'short-tree'
const tree = new ShortTree( ( a: string, b: string ) => a.localeCompare( b ) );
tree.insert( [ 'a', 'b', 'c', 'd' ] );
tree.insert( [ 'x', 'y' ] );
tree.insert( [ 'a', 'b' ] );
tree.values( );