Common Lisp Package: DARTS.LIB.PTREE

Provides a simple binary search tree implementation, which uses strings as keys. The tree is balanced. This code is based on the paper Implementing Sets Efficiently in a Functional Language by S. Adams. Short of renaming a few things and adapting the code to Common Lisp, the algorithms presented there were used pretty much as-is.

README:

FUNCTION

Public

Undocumented

PTREE (&REST PAIRS)

PTREE-DIFFERENCE (TREE1 TREE2)

PTREE-EMPTY-P (OBJECT)

PTREE-EQUAL (TREE1 TREE2)

PTREE-FIND (KEY TREE)

PTREE-FOLD (FUNCTION INITIAL-VALUE TREE &KEY (DIRECTION FORWARD HAVE-DIR) (START NIL HAVE-START) (END NIL HAVE-END))

PTREE-GET (KEY TREE &OPTIONAL DEFAULT)

PTREE-INSERT (KEY VALUE TREE &OPTIONAL (TEST #'EQ))

PTREE-INTERSECTION (TREE1 TREE2)

PTREE-ITERATOR (TREE &KEY (DIRECTION FORWARD))

PTREE-KEY (TREE)

PTREE-KEYS (TREE)

PTREE-LARGEST (KEY TREE)

PTREE-LEFT (TREE)

PTREE-MAP (FUNCTION TREE &KEY (DIRECTION FORWARD) (COLLECTP NIL) (START NIL HAVE-START) (END NIL HAVE-END))

PTREE-MAXIMUM (TREE)

PTREE-MINIMUM (TREE)

PTREE-PAIRS (TREE)

PTREE-REMOVE (KEY TREE)

PTREE-RIGHT (TREE)

PTREE-SIZE (TREE)

PTREE-SMALLEST (KEY TREE)

PTREE-UNION (TREE1 TREE2)

PTREE-UPDATE (KEY TREE UPDATE)

PTREE-VALUE (TREE)

PTREE-VALUES (TREE)

PTREEP (OBJECT)

Private

NODE-COUNT (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

NODE-KEY (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

NODE-LEFT (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

NODE-RIGHT (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

NODE-VALUE (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

Undocumented

CONCAT (TREE1 TREE2)

CONCAT-3 (KEY VALUE LEFT RIGHT)

COPY-EMPTY (INSTANCE)

COPY-NODE (INSTANCE)

DELETE* (LEFT RIGHT)

DELETE-MINIMUM (NODE)

MAKE-EMPTY (&KEY)

MAKE-NODE (KEY VALUE &OPTIONAL (LEFT +EMPTY-PTREE+) (RIGHT +EMPTY-PTREE+) &AUX (COUNT (+ (IF (PTREE-EMPTY-P LEFT) 0 (NODE-COUNT LEFT)) (IF (PTREE-EMPTY-P RIGHT) 0 (NODE-COUNT RIGHT)) 1)))

MAKE-PTREE (&KEY)

NODE-P (OBJECT)

PTREE-CHECK-INVARIANTS (TREE)

REBALANCE (KEY VALUE LEFT RIGHT)

ROTATE-ONCE (DIRECTION KEY VALUE LEFT RIGHT)

ROTATE-TWICE (DIRECTION KEY VALUE LEFT RIGHT)

SPLIT-GT (KEY TREE)

SPLIT-LT (KEY TREE)

MACRO

Private

Undocumented

WITH-NODE ((KEY VALUE COUNT LEFT RIGHT) NODE &BODY BODY)

VARIABLE

Public

Undocumented

+EMPTY-PTREE+

CLASS

Public

Undocumented

PTREE (&REST PAIRS)

Private

Undocumented

EMPTY

NODE

CONSTANT

Private

Undocumented

+WEIGHT+