Next: Introduction, Previous: (dir), Up: (dir) [Contents][Index]

The red-black-tree Reference Manual

This is the red-black-tree Reference Manual, version 0.1.0, generated automatically by Declt version 4.0 beta 2 "William Riker" on Mon Feb 26 17:46:56 2024 GMT+0.

Next: Systems, Previous: The red-black-tree Reference Manual, Up: The red-black-tree Reference Manual [Contents][Index]

1 Introduction

Next: Files, Previous: Introduction, Up: The red-black-tree Reference Manual [Contents][Index]

2 Systems

The main system appears first, followed by any subsystem dependency.

red-black-tree

Previous: Systems, Up: Systems [Contents][Index]

2.1 `red-black-tree`

An implementation of the red-black search tree data structure.

Author

Michael Fiano <mail@mfiano.net>

Home Page

https://git.mfiano.net/mfiano/red-black-tree

License

MIT

Version

0.1.0

Dependency

mfiano-utils (system).

Source

red-black-tree.asd.

Child Components

package.lisp (file).
red-black-tree.lisp (file).

Next: Packages, Previous: Systems, Up: The red-black-tree Reference Manual [Contents][Index]

3 Files

Files are sorted by type and then listed depth-first from the systems components trees.

Lisp

Previous: Files, Up: Files [Contents][Index]

Next: red-black-tree/package.lisp, Previous: Lisp, Up: Lisp [Contents][Index]

3.1.1 `red-black-tree/red-black-tree.asd`

Source: red-black-tree.asd.
Parent Component: red-black-tree (system).
ASDF Systems: red-black-tree.

Next: red-black-tree/red-black-tree.lisp, Previous: red-black-tree/red-black-tree.asd, Up: Lisp [Contents][Index]

3.1.2 `red-black-tree/package.lisp`

Source: red-black-tree.asd.
Parent Component: red-black-tree (system).
Packages: red-black-tree.

Previous: red-black-tree/package.lisp, Up: Lisp [Contents][Index]

3.1.3 `red-black-tree/red-black-tree.lisp`

Dependency

package.lisp (file).

Source

red-black-tree.asd.

Parent Component

red-black-tree (system).

Public Interface

delete (function).
delete-node (function).
find (function).
insert (function).
make-tree (function).
max (function).
min (function).
next (function).
node (structure).
previous (function).
print-object (method).
print-object (method).
tree (reader).
(setf tree) (writer).
tree (structure).
valid-p (function).
walk (function).

Internals

%make-node (function).
%make-tree (function).
%walk/in-order (function).
%walk/post-order (function).
%walk/pre-order (function).
color (reader).
(setf color) (writer).
delete/fixup (function).
insert-fixup (function).
key (reader).
(setf key) (writer).
key-func (reader).
(setf key-func) (writer).
left (reader).
(setf left) (writer).
make-node (function).
node-p (function).
parent (reader).
(setf parent) (writer).
right (reader).
(setf right) (writer).
root (reader).
(setf root) (writer).
rotate/left (function).
rotate/right (function).
sentinel (reader).
(setf sentinel) (writer).
sort-func (reader).
(setf sort-func) (writer).
transplant (function).
value (reader).
(setf value) (writer).

Next: Definitions, Previous: Files, Up: The red-black-tree Reference Manual [Contents][Index]

4 Packages

Packages are listed by definition order.

red-black-tree

Previous: Packages, Up: Packages [Contents][Index]

4.1 `red-black-tree`

Source

package.lisp.

Use List

common-lisp.

Public Interface

delete (function).
delete-node (function).
find (function).
insert (function).
make-tree (function).
max (function).
min (function).
next (function).
node (structure).
previous (function).
tree (reader).
(setf tree) (writer).
tree (structure).
valid-p (function).
walk (function).

Internals

%make-node (function).
%make-tree (function).
%walk/in-order (function).
%walk/post-order (function).
%walk/pre-order (function).
color (reader).
(setf color) (writer).
delete/fixup (function).
insert-fixup (function).
key (reader).
(setf key) (writer).
key-func (reader).
(setf key-func) (writer).
left (reader).
(setf left) (writer).
make-node (function).
node-p (function).
parent (reader).
(setf parent) (writer).
right (reader).
(setf right) (writer).
root (reader).
(setf root) (writer).
rotate/left (function).
rotate/right (function).
sentinel (reader).
(setf sentinel) (writer).
sort-func (reader).
(setf sort-func) (writer).
transplant (function).
value (reader).
(setf value) (writer).

Next: Indexes, Previous: Packages, Up: The red-black-tree Reference Manual [Contents][Index]

5 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.

Public Interface
Internals

Next: Internals, Previous: Definitions, Up: Definitions [Contents][Index]

5.1 Public Interface

Ordinary functions
Standalone methods
Structures

Next: Standalone methods, Previous: Public Interface, Up: Public Interface [Contents][Index]

5.1.1 Ordinary functions

Function: delete (tree item) ¶

Package: red-black-tree.
Source: red-black-tree.lisp.

Function: delete-node (tree node) ¶

Package: red-black-tree.
Source: red-black-tree.lisp.

Function: find (tree item) ¶

Package: red-black-tree.
Source: red-black-tree.lisp.

Function: insert (tree item) ¶

Package: red-black-tree.
Source: red-black-tree.lisp.

Function: make-tree (&key key-func sort-func) ¶

Package: red-black-tree.
Source: red-black-tree.lisp.

Function: max (node) ¶

Package: red-black-tree.
Source: red-black-tree.lisp.

Function: min (node) ¶

Package: red-black-tree.
Source: red-black-tree.lisp.

Function: next (node) ¶

Package: red-black-tree.
Source: red-black-tree.lisp.

Function: previous (node) ¶

Package: red-black-tree.
Source: red-black-tree.lisp.

Reader: tree (instance) ¶

Writer: (setf tree) (instance) ¶

Package: red-black-tree.
Source: red-black-tree.lisp.
Target Slot: tree.

Function: valid-p (tree) ¶

Package: red-black-tree.
Source: red-black-tree.lisp.

Function: walk (tree func &key order) ¶

Package: red-black-tree.
Source: red-black-tree.lisp.

Next: Structures, Previous: Ordinary functions, Up: Public Interface [Contents][Index]

5.1.2 Standalone methods

Method: print-object ((node node) stream) ¶

Source: red-black-tree.lisp.

Method: print-object ((tree tree) stream) ¶

Source: red-black-tree.lisp.

Previous: Standalone methods, Up: Public Interface [Contents][Index]

5.1.3 Structures

Structure: node ¶

Package

red-black-tree.

Source

red-black-tree.lisp.

Direct superclasses

structure-object.

Direct methods

print-object.

Direct slots

Slot: tree ¶

Type: (or red-black-tree:tree null)
Readers: tree.
Writers: (setf tree).

Slot: parent ¶

Type: (or red-black-tree:node null)
Readers: parent.
Writers: (setf parent).

Slot: left ¶

Type: (or red-black-tree:node null)
Readers: left.
Writers: (setf left).

Slot: right ¶

Type: (or red-black-tree:node null)
Readers: right.
Writers: (setf right).

Slot: color ¶

Type: (member :red :black)
Initform: :black
Readers: color.
Writers: (setf color).

Slot: key ¶

Readers: key.
Writers: (setf key).

Slot: value ¶

Readers: value.
Writers: (setf value).

Structure: tree ¶

Package

red-black-tree.

Source

red-black-tree.lisp.

Direct superclasses

structure-object.

Direct methods

print-object.

Direct slots

Slot: sentinel ¶

Type: (or red-black-tree:node null)
Readers: sentinel.
Writers: (setf sentinel).

Slot: root ¶

Type: (or red-black-tree:node null)
Readers: root.
Writers: (setf root).

Slot: key-func ¶

Type: function
Initform: (function identity)
Readers: key-func.
Writers: (setf key-func).

Slot: sort-func ¶

Type: function
Initform: (function <)
Readers: sort-func.
Writers: (setf sort-func).

Previous: Public Interface, Up: Definitions [Contents][Index]

5.2 Internals

Ordinary functions

Previous: Internals, Up: Internals [Contents][Index]

5.2.1 Ordinary functions

Function: %make-node (&key tree parent left right color key value) ¶

Package: red-black-tree.
Source: red-black-tree.lisp.

Function: %make-tree (&key sentinel root key-func sort-func) ¶

Package: red-black-tree.
Source: red-black-tree.lisp.

Function: %walk/in-order (node func) ¶

Package: red-black-tree.
Source: red-black-tree.lisp.

Function: %walk/post-order (node func) ¶

Package: red-black-tree.
Source: red-black-tree.lisp.

Function: %walk/pre-order (node func) ¶

Package: red-black-tree.
Source: red-black-tree.lisp.

Reader: color (instance) ¶

Writer: (setf color) (instance) ¶

Package: red-black-tree.
Source: red-black-tree.lisp.
Target Slot: color.

Function: delete/fixup (tree node) ¶

Package: red-black-tree.
Source: red-black-tree.lisp.

Function: insert-fixup (tree node) ¶

Package: red-black-tree.
Source: red-black-tree.lisp.

Reader: key (instance) ¶

Writer: (setf key) (instance) ¶

Package: red-black-tree.
Source: red-black-tree.lisp.
Target Slot: key.

Reader: key-func (instance) ¶

Writer: (setf key-func) (instance) ¶

Package: red-black-tree.
Source: red-black-tree.lisp.
Target Slot: key-func.

Reader: left (instance) ¶

Writer: (setf left) (instance) ¶

Package: red-black-tree.
Source: red-black-tree.lisp.
Target Slot: left.

Function: make-node (tree item) ¶

Package: red-black-tree.
Source: red-black-tree.lisp.

Function: node-p (node) ¶

Package: red-black-tree.
Source: red-black-tree.lisp.

Reader: parent (instance) ¶

Writer: (setf parent) (instance) ¶

Package: red-black-tree.
Source: red-black-tree.lisp.
Target Slot: parent.

Reader: right (instance) ¶

Writer: (setf right) (instance) ¶

Package: red-black-tree.
Source: red-black-tree.lisp.
Target Slot: right.

Reader: root (instance) ¶

Writer: (setf root) (instance) ¶

Package: red-black-tree.
Source: red-black-tree.lisp.
Target Slot: root.

Function: rotate/left (tree node) ¶

Package: red-black-tree.
Source: red-black-tree.lisp.

Function: rotate/right (tree node) ¶

Package: red-black-tree.
Source: red-black-tree.lisp.

Reader: sentinel (instance) ¶

Writer: (setf sentinel) (instance) ¶

Package: red-black-tree.
Source: red-black-tree.lisp.
Target Slot: sentinel.

Reader: sort-func (instance) ¶

Writer: (setf sort-func) (instance) ¶

Package: red-black-tree.
Source: red-black-tree.lisp.
Target Slot: sort-func.

Function: transplant (tree u v) ¶

Package: red-black-tree.
Source: red-black-tree.lisp.

Reader: value (instance) ¶

Writer: (setf value) (instance) ¶

Package: red-black-tree.
Source: red-black-tree.lisp.
Target Slot: value.

Previous: Definitions, Up: The red-black-tree Reference Manual [Contents][Index]

Appendix A Indexes

Concepts
Functions
Variables
Data types

Next: Functions, Previous: Indexes, Up: Indexes [Contents][Index]

A.1 Concepts

Next: Variables, Previous: Concepts, Up: Indexes [Contents][Index]

A.2 Functions

Jump to:	% ( C D F I K L M N P R S T V W

	Index Entry	Section

%
	`%make-node`:	Private ordinary functions
	`%make-tree`:	Private ordinary functions
	`%walk/in-order`:	Private ordinary functions
	`%walk/post-order`:	Private ordinary functions
	`%walk/pre-order`:	Private ordinary functions

(
	`(setf color)`:	Private ordinary functions
	`(setf key)`:	Private ordinary functions
	`(setf key-func)`:	Private ordinary functions
	`(setf left)`:	Private ordinary functions
	`(setf parent)`:	Private ordinary functions
	`(setf right)`:	Private ordinary functions
	`(setf root)`:	Private ordinary functions
	`(setf sentinel)`:	Private ordinary functions
	`(setf sort-func)`:	Private ordinary functions
	`(setf tree)`:	Public ordinary functions
	`(setf value)`:	Private ordinary functions

C
	`color`:	Private ordinary functions

D
	`delete`:	Public ordinary functions
	`delete-node`:	Public ordinary functions
	`delete/fixup`:	Private ordinary functions

F
	`find`:	Public ordinary functions
	`Function, %make-node`:	Private ordinary functions
	`Function, %make-tree`:	Private ordinary functions
	`Function, %walk/in-order`:	Private ordinary functions
	`Function, %walk/post-order`:	Private ordinary functions
	`Function, %walk/pre-order`:	Private ordinary functions
	`Function, (setf color)`:	Private ordinary functions
	`Function, (setf key)`:	Private ordinary functions
	`Function, (setf key-func)`:	Private ordinary functions
	`Function, (setf left)`:	Private ordinary functions
	`Function, (setf parent)`:	Private ordinary functions
	`Function, (setf right)`:	Private ordinary functions
	`Function, (setf root)`:	Private ordinary functions
	`Function, (setf sentinel)`:	Private ordinary functions
	`Function, (setf sort-func)`:	Private ordinary functions
	`Function, (setf tree)`:	Public ordinary functions
	`Function, (setf value)`:	Private ordinary functions
	`Function, color`:	Private ordinary functions
	`Function, delete`:	Public ordinary functions
	`Function, delete-node`:	Public ordinary functions
	`Function, delete/fixup`:	Private ordinary functions
	`Function, find`:	Public ordinary functions
	`Function, insert`:	Public ordinary functions
	`Function, insert-fixup`:	Private ordinary functions
	`Function, key`:	Private ordinary functions
	`Function, key-func`:	Private ordinary functions
	`Function, left`:	Private ordinary functions
	`Function, make-node`:	Private ordinary functions
	`Function, make-tree`:	Public ordinary functions
	`Function, max`:	Public ordinary functions
	`Function, min`:	Public ordinary functions
	`Function, next`:	Public ordinary functions
	`Function, node-p`:	Private ordinary functions
	`Function, parent`:	Private ordinary functions
	`Function, previous`:	Public ordinary functions
	`Function, right`:	Private ordinary functions
	`Function, root`:	Private ordinary functions
	`Function, rotate/left`:	Private ordinary functions
	`Function, rotate/right`:	Private ordinary functions
	`Function, sentinel`:	Private ordinary functions
	`Function, sort-func`:	Private ordinary functions
	`Function, transplant`:	Private ordinary functions
	`Function, tree`:	Public ordinary functions
	`Function, valid-p`:	Public ordinary functions
	`Function, value`:	Private ordinary functions
	`Function, walk`:	Public ordinary functions

I
	`insert`:	Public ordinary functions
	`insert-fixup`:	Private ordinary functions

K
	`key`:	Private ordinary functions
	`key-func`:	Private ordinary functions

L
	`left`:	Private ordinary functions

M
	`make-node`:	Private ordinary functions
	`make-tree`:	Public ordinary functions
	`max`:	Public ordinary functions
	`Method, print-object`:	Public standalone methods
	`Method, print-object`:	Public standalone methods
	`min`:	Public ordinary functions

N
	`next`:	Public ordinary functions
	`node-p`:	Private ordinary functions

P
	`parent`:	Private ordinary functions
	`previous`:	Public ordinary functions
	`print-object`:	Public standalone methods
	`print-object`:	Public standalone methods

R
	`right`:	Private ordinary functions
	`root`:	Private ordinary functions
	`rotate/left`:	Private ordinary functions
	`rotate/right`:	Private ordinary functions

S
	`sentinel`:	Private ordinary functions
	`sort-func`:	Private ordinary functions

T
	`transplant`:	Private ordinary functions
	`tree`:	Public ordinary functions

V
	`valid-p`:	Public ordinary functions
	`value`:	Private ordinary functions

W
	`walk`:	Public ordinary functions

Next: Data types, Previous: Functions, Up: Indexes [Contents][Index]

A.3 Variables

Jump to:	C K L P R S T V

	Index Entry	Section

C
	`color`:	Public structures

K
	`key`:	Public structures
	`key-func`:	Public structures

L
	`left`:	Public structures

P
	`parent`:	Public structures

R
	`right`:	Public structures
	`root`:	Public structures

S
	`sentinel`:	Public structures
	`Slot, color`:	Public structures
	`Slot, key`:	Public structures
	`Slot, key-func`:	Public structures
	`Slot, left`:	Public structures
	`Slot, parent`:	Public structures
	`Slot, right`:	Public structures
	`Slot, root`:	Public structures
	`Slot, sentinel`:	Public structures
	`Slot, sort-func`:	Public structures
	`Slot, tree`:	Public structures
	`Slot, value`:	Public structures
	`sort-func`:	Public structures

T
	`tree`:	Public structures

V
	`value`:	Public structures

Previous: Variables, Up: Indexes [Contents][Index]

A.4 Data types

Jump to:	F N P R S T

	Index Entry	Section

F
	`File, package.lisp`:	The red-black-tree/package․lisp file
	`File, red-black-tree.asd`:	The red-black-tree/red-black-tree․asd file
	`File, red-black-tree.lisp`:	The red-black-tree/red-black-tree․lisp file

N
	`node`:	Public structures

P
	`Package, red-black-tree`:	The red-black-tree package
	`package.lisp`:	The red-black-tree/package․lisp file

R
	`red-black-tree`:	The red-black-tree system
	`red-black-tree`:	The red-black-tree package
	`red-black-tree.asd`:	The red-black-tree/red-black-tree․asd file
	`red-black-tree.lisp`:	The red-black-tree/red-black-tree․lisp file

S
	`Structure, node`:	Public structures
	`Structure, tree`:	Public structures
	`System, red-black-tree`:	The red-black-tree system

T
	`tree`:	Public structures

The red-black-tree Reference Manual

Table of Contents

1 Introduction

2 Systems

2.1 red-black-tree

3 Files

3.1 Lisp

3.1.1 red-black-tree/red-black-tree.asd

3.1.2 red-black-tree/package.lisp

3.1.3 red-black-tree/red-black-tree.lisp

4 Packages

4.1 red-black-tree

5 Definitions

5.1 Public Interface

5.1.1 Ordinary functions

5.1.2 Standalone methods

5.1.3 Structures

5.2 Internals

5.2.1 Ordinary functions

Appendix A Indexes

A.1 Concepts

A.2 Functions

A.3 Variables

A.4 Data types

2.1 `red-black-tree`

3.1.1 `red-black-tree/red-black-tree.asd`

3.1.2 `red-black-tree/package.lisp`

3.1.3 `red-black-tree/red-black-tree.lisp`

4.1 `red-black-tree`