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.