Package COM.INFORMATIMAGO.COMMON-LISP.CESARUM.LLRBTREE

Nicknames: COM.INFORMATIMAGO.COMMON-LISP.CESARUM.LEFT-LEANING-RED-BLACK-TREE
Implementation of Left Leaning Red Black Trees.
Robert Sedgewick's algorithms.
http://www.cs.princeton.edu/~rs



License:

    AGPL3
    
    Copyright Pascal J. Bourguignon 2009 - 2015
    
    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/>

(make-tree &key lessp)
function
RETURN: a new empty TREE.
(map-tree fun tree &key start end from-end)
function
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)
function
DO:     Remove all the entries in the TREE.
RETURN: TREE
(tree-count tree)
function
The number of nodes in the tree.
(tree-delete key tree)
function
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)
function
DO:      Delete the maximum entry of the TREE.
RETURN:  Whether an entry has been deleted.
(tree-delete-min tree)
function
DO:      Delete the minimum entry of the TREE.
RETURN:  Whether an entry has been deleted.
(tree-empty-p tree)
function
RETURN: Whether the TREE contains no element.
(tree-get key tree &optional default)
function
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.
(setf (tree-get key tree &optional default) new-value)
function
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 tree)
function
The key order.
(treep x)
function
Whether the object is a left leaning red-black tree.
(with-tree-iterator (name tree &rest args &key from-end) &body body)
macro
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.