Common Lisp Package: NU.COMPOSED.BTRIE

Branch trie – an implementation of tries with branch widths.

README:

FUNCTION

Public

LEAFP (NODE)

Predicate to tell if there are no branches for a node.

MAKE-NODE (&KEY (KEY ) (WIDTH 0) (BRANCHES NIL) (LEAF NIL))

Utility function to make a trie instance.

MAKE-TRIE (&OPTIONAL (SEQS NIL))

Make a trie with letters as keys.

MAKE-WORD-TRIE (SEQS)

Make a test trie with words as keys.

ONLY-TERMINAL-P (NODE)

This predicate tells if node has only terminal as a child.

SORT-TRIE (TRIE PREDICATE &REST ARGS)

Sort a trie recursively with a predicate function.

SORT-TRIE-BRANCH (TRIE PREDICATE &KEY (KEY #'KEY) (STABLE NIL))

Sort a trie node’s branches with a predicate function.

WORDP (NODE)

Predicate to tell whether this node ends any words.

Undocumented

MAKE-LEAF (&KEY (WIDTH 1))

NODES-EQUALP (A B)

Private

MAKE-TRIE-WITH-FN (&OPTIONAL (FN #'ADD-SEQS) (SEQS NIL))

Simple utility function to build a trie from a sequence.

Undocumented

CUT-SEQUENCE (SEQ TIMES)

INTERLEAVE (SEQ NUM-PARTS)

SUBSEQS (SEQ LENGTH)

GENERIC-FUNCTION

Public

Undocumented

ADD (TRIE SEQ &OPTIONAL (COUNT))

ADD-SEQS (TRIE SEQS &OPTIONAL (COUNT))

ADD-SEQS-AS-KEYS (TRIE SEQS &OPTIONAL (COUNT))

ADD-SUBSEQS (TRIE SEQ LEN)

FIND-KEY (TRIE KEY)

OBTAIN-SEQ (TRIE SEQ)

TRAVERSE (TRIE FUN &KEY (DO-LEAFS NIL))

TRIE-PROB (ROOT SUFFIX)

Private

Undocumented

ADD-KEY (TRIE KEY &OPTIONAL (COUNT))

CREATE-NODE (TRIE KEY &OPTIONAL (COUNT))

REMOVE-KEY (TRIE KEY &OPTIONAL (COUNT))

REMOVE-NODE (TRIE KEY)

SYM-INTERVAL (TRIE KEY)

SYM-LOW (TRIE KEY)

SLOT-ACCESSOR

Public

KEY (OBJECT)

Can be any type for generality.

Undocumented

BRANCHES (OBJECT)

SETFBRANCHES (NEW-VALUE OBJECT)

WIDTH (OBJECT)

SETFWIDTH (NEW-VALUE OBJECT)

VARIABLE

Public

Undocumented

+WORD-MARKER+

Private

Undocumented

*DEBUG*

CLASS

Public

TRIE

Trie data structure, see package documentation for more info.