Common Lisp Package: COM.INFORMATIMAGO.COMMON-LISP.CESARUM.LLRBTREE

Implementation of Left Leaning Red Black Trees. Robert Sedgewick's algorithms. http://www.cs.princeton.edu/~rs License: AGPL3 Copyright Pascal J. Bourguignon 2009 - 2012 This program is free software: you can redistribute it and/or modify it under the terms of the GNU Affero General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Affero General Public License for more details. You should have received a copy of the GNU Affero General Public License along with this program. If not, see <http://www.gnu.org/licenses/>

README:

FUNCTION

Public

MAKE-TREE (&KEY (LESSP #'<))

RETURN: a new empty TREE.

MAP-TREE (FUN TREE &KEY (START NIL STARTP) (END NIL ENDP) FROM-END)

DO: Calls (funcall FUN key value) for the entries in the TREE, by increasing, when (NOT FROM-END), or decreasing when FROM-END, key order. FROM-END: Whether the we start from the end. START, END: Limiting values for the key. Only entries whose key k is such as START <= k < END are passed to FUN. RETURN: Nothing.

TREE-CLEAR (TREE)

DO: Remove all the entries in the TREE. RETURN: TREE

TREE-COUNT (INSTANCE)

The number of nodes in the tree.

TREE-DELETE (KEY TREE)

DO: Removes the entry for KEY in TREE, if any. RETURN: true if there was such an entry, or false otherwise.

TREE-DELETE-MAX (TREE)

DO: Delete the maximum entry of the TREE. RETURN: Whether an entry has been deleted.

TREE-DELETE-MIN (TREE)

DO: Delete the minimum entry of the TREE. RETURN: Whether an entry has been deleted.

TREE-EMPTY-P (TREE)

RETURN: Whether the TREE contains no element.

TREE-GET (KEY TREE &OPTIONAL DEFAULT)

RETURN: the object in TREE whose key is the same as KEY under the tree's equivalence test (implied by TREE-LESSP). If there is no such entry, DEFAULT is returned ; PRESENT-P is true if an entry is found; otherwise, it is false. NOTE: SETF may be used with TREE-GET to modify the value associated with a given key, or to add a new entry. When a TREE-GET form is used as a SETF place, any default which is supplied is evaluated according to normal left-to-right evaluation rules, but its value is ignored.

SETFTREE-GET (NEW-VALUE KEY TREE &OPTIONAL DEFAULT)

DO: SETF may be used with TREE-GET to modify the value associated with a given key, or to add a new entry. When a TREE-GET form is used as a SETF place, any default which is supplied is evaluated according to normal left-to-right evaluation rules, but its value is ignored. RETURN: NEW-VALUE.

TREE-LESSP (INSTANCE)

The key order.

TREEP (OBJECT)

Whether the object is a left leaning red-black tree.

Undocumented

SETFTREE-COUNT (NEW-VALUE INSTANCE)

Private

LEAN-LEFT (H)

Samre as rotate-left, plus update colors.

LEAN-RIGHT (H)

Same as rotate-right, plus update colors.

MAKE-ITERATOR (TREE &REST ARGS &KEY FROM-END)

RETURN: An iterator to walk the nodes of the TREE. This iterator is a function that called repeatitively will return successively each key value pairs in the tree (as three values, T; key; value), and when done, returns NIL. NOTE: The data is collected before iterating, so you can modify the tree at will during iteration.

NODE-COLOR (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.

SEARCH-NODE-FOR-KEY (NODE KEY LESSP)

DO: Search the node with the key, or the parent where a node with key would be inserted. NODE: The root node of the tree. KEY: The key of the object to search. RETURN: found-node ; foundp NODE: (not foundp) => NIL ; foundp => the node such as (and (not (funcall lessp key (node-key node)) (not (funcall lessp (node-key node) key)) FOUNDP: Whether a node with the KEY was found from NODE.

TREE-ROOT (INSTANCE)

The root node.

Undocumented

%COPY-TREE (INSTANCE)

%MAKE-TREE (&KEY ((ROOT DUM78) NIL) ((COUNT DUM79) 0) ((LESSP DUM80) #'<))

CONCAT (&REST ARGS)

COPY-NODE (INSTANCE)

COUNT-NODES (NODE)

DELETE-MAX (H)

DELETE-MIN (H)

DELETE-NODE (H KEY TREE LESSP)

EQUIV (A B)

INDENTATION (LEVEL LEFTP)

INSERT-NODE (H KEY VALUE TREE LESSP)

INVARIANT (TREE)

LEFT-MOST-NODE (H)

MAKE-NODE (&KEY ((COLOR DUM0) RED) ((LEFT DUM1) NIL) ((RIGHT DUM2) NIL) ((KEY DUM3) NIL) ((VALUE DUM4) NIL))

MOVE-RED-LEFT (H)

MOVE-RED-RIGHT (H)

SETFNODE-COLOR (NEW-VALUE INSTANCE)

SETFNODE-KEY (NEW-VALUE INSTANCE)

SETFNODE-LEFT (NEW-VALUE INSTANCE)

NODE-P (OBJECT)

NODE-RED-P (NODE)

SETFNODE-RIGHT (NEW-VALUE INSTANCE)

SETFNODE-VALUE (NEW-VALUE INSTANCE)

ROTATE-LEFT (H)

ROTATE-RIGHT (H)

SPLIT-FOUR-NODE (H)

STRING-BUTLAST (STR)

TEST

TEST-ITERATOR

TEST-NODE-ERASE

TEST-TREE-CREATION

TEST-TREE-ERASE

SETFTREE-ROOT (NEW-VALUE INSTANCE)

WALK-NODES-INFIX (NODE FUN)

WALK-NODES-INFIX/FROM-END (NODE FUN)

WALK-NODES-SUFFIX (NODE FUN)

MACRO

Public

WITH-TREE-ITERATOR ((NAME TREE &REST ARGS &KEY FROM-END) &BODY BODY)

Within the lexical scope of the BODY, NAME is defined via macrolet such that successive invocations of (NAME) return the items, one by one, from the LLRBL:TREE that is obtained by evaluating TREE only once. An invocation (NAME) returns three values as follows: 1. A generalized boolean that is true if an entry is returned. 2. The key from the tree entry. 3. The value from the tree entry. After all entries have been returned by successive invocations of (NAME), then only one value is returned, namely nil. It is unspecified what happens if any of the implicit interior state of an iteration is returned outside the dynamic extent of the WITH-TREE-ITERATOR form such as by returning some closure over the invocation form. Any number of invocations of WITH-TREE-ITERATOR can be nested, and the BODY of the innermost one can invoke all of the locally established macros, provided all of those macros have distinct NAMEs.

Private

Undocumented

IMPLY (P Q)

GENERIC-FUNCTION

Private

Undocumented

DUMP (SELF &OPTIONAL (INDENTATION) (BAR))

GENERATE-DOT (SELF)

VARIABLE

Private

Undocumented

*BLACK*

*DOT-COUNTER*

*NORMAL*

*RED*

CLASS

Private

Undocumented

NODE

TREE