The bst Reference Manual

This is the bst Reference Manual, version 2.0, generated automatically by Declt version 4.0 beta 2 "William Riker" on Mon Feb 26 14:46:35 2024 GMT+0.

Table of Contents


1 Introduction


2 Systems

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


2.1 bst

Binary search tree

Author

Guillaume LE VAILLANT

License

GPL-3

Version

2.0

Source

bst.asd.

Child Component

bst.lisp (file).


3 Files

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


3.1 Lisp


3.1.1 bst/bst.asd

Source

bst.asd.

Parent Component

bst (system).

ASDF Systems

bst.


3.1.2 bst/bst.lisp

Source

bst.asd.

Parent Component

bst (system).

Packages

bst.

Public Interface
Internals

4 Packages

Packages are listed by definition order.


4.1 bst

Source

bst.lisp.

Use List

common-lisp.

Public Interface
Internals

5 Definitions

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


5.1 Public Interface


5.1.1 Constants

Constant: +bst-empty+

An empty tree is represented by NIL.

Package

bst.

Source

bst.lisp.


5.1.2 Special variables

Special Variable: *bst-copy-function*

A function used to copy a value of a tree.

Package

bst.

Source

bst.lisp.

Special Variable: *bst-equal-p-function*

A function used to check if two values of a tree are equal.

Package

bst.

Source

bst.lisp.

Special Variable: *bst-lesser-p-function*

A function used to check if a value of a tree is lesser than another.

Package

bst.

Source

bst.lisp.


5.1.3 Ordinary functions

Function: bst-add (tree value)

Insert a VALUE in a TREE.

Package

bst.

Source

bst.lisp.

Function: bst-add! (tree value)

Insert a VALUE in a TREE. The TREE argument is destroyed.

Package

bst.

Source

bst.lisp.

Function: bst-balance (tree)

Balance a TREE.

Package

bst.

Source

bst.lisp.

Function: bst-copy (value)

Return a copy of VALUE.

Package

bst.

Source

bst.lisp.

Function: bst-count (tree)

Return the number of nodes in a TREE.

Package

bst.

Source

bst.lisp.

Function: bst-empty-p (tree)

Return T if TREE is empty and NIL otherwise.

Package

bst.

Source

bst.lisp.

Function: bst-equal-p (value1 value2)

Return T if VALUE1 and VALUE2 are equal, and NIL otherwise.

Package

bst.

Source

bst.lisp.

Function: bst-from-sorted-values (values)

Make a balanced tree from a vector of sorted values.

Package

bst.

Source

bst.lisp.

Function: bst-from-values (values)

Make a tree from a sequence of values.

Package

bst.

Source

bst.lisp.

Function: bst-lesser-p (value1 value2)

Return T if VALUE1 is lesser than VALUE2, and NIL otherwise.

Package

bst.

Source

bst.lisp.

Function: bst-map (tree function)

Apply a FUNCTION to each value of a TREE in ascending order.

Package

bst.

Source

bst.lisp.

Function: bst-max-depth (tree)

Return the length of the longest branch in a TREE.

Package

bst.

Source

bst.lisp.

Function: bst-max-value (tree)

If TREE is not empty, return its maximum value and T, otherwise return NIL and NIL.

Package

bst.

Source

bst.lisp.

Function: bst-min-depth (tree)

Return the length of the shortest branch in a TREE.

Package

bst.

Source

bst.lisp.

Function: bst-min-value (tree)

If TREE is not empty, return its minimum value and T, otherwise return NIL and NIL.

Package

bst.

Source

bst.lisp.

Function: bst-remove (tree value)

Delete a VALUE from a TREE.

Package

bst.

Source

bst.lisp.

Function: bst-remove! (tree value)

Delete a VALUE from a TREE. The TREE argument is destroyed.

Package

bst.

Source

bst.lisp.

Function: bst-search (tree value)

If VALUE is present in TREE, return VALUE and T, otherwise return NIL and NIL.

Package

bst.

Source

bst.lisp.

Function: bst-search-max-value-below (tree value)

Search the maximum value in TREE lesser that VALUE. If such a value is found, return it and T, otherwise return NIL and NIL.

Package

bst.

Source

bst.lisp.

Function: bst-search-min-value-above (tree value)

Search the minimum value in TREE greater that VALUE. If such a value is found, return it and T, otherwise return NIL and NIL.

Package

bst.

Source

bst.lisp.

Function: bst-tree-copy (tree)

Return a copy of a TREE.

Package

bst.

Source

bst.lisp.

Function: bst-tree-equal-p (tree1 tree2)

Return T if TREE1 and TREE2 have the same structure, and NIL otherwise.

Package

bst.

Source

bst.lisp.

Function: bst-values (tree)

Return all the values of a TREE in a vector.

Package

bst.

Source

bst.lisp.

Function: bst-values-equal-p (tree1 tree2)

Return T if TREE1 and TREE2 contain the same values, and NIL otherwise.

Package

bst.

Source

bst.lisp.


5.2 Internals


5.2.1 Ordinary functions

Reader: bst-left (instance)
Writer: (setf bst-left) (instance)
Package

bst.

Source

bst.lisp.

Target Slot

left.

Function: bst-p (object)
Package

bst.

Source

bst.lisp.

Reader: bst-right (instance)
Writer: (setf bst-right) (instance)
Package

bst.

Source

bst.lisp.

Target Slot

right.

Reader: bst-value (instance)
Writer: (setf bst-value) (instance)
Package

bst.

Source

bst.lisp.

Target Slot

value.

Function: copy-bst (instance)
Package

bst.

Source

bst.lisp.

Function: make-bst (&key value left right)
Package

bst.

Source

bst.lisp.


5.2.2 Structures

Structure: bst
Package

bst.

Source

bst.lisp.

Direct superclasses

structure-object.

Direct slots
Slot: value
Readers

bst-value.

Writers

(setf bst-value).

Slot: left
Initform

bst:+bst-empty+

Readers

bst-left.

Writers

(setf bst-left).

Slot: right
Initform

bst:+bst-empty+

Readers

bst-right.

Writers

(setf bst-right).


Appendix A Indexes


A.1 Concepts


A.2 Functions

Jump to:   (  
B   C   F   M  
Index Entry  Section

(
(setf bst-left): Private ordinary functions
(setf bst-right): Private ordinary functions
(setf bst-value): Private ordinary functions

B
bst-add: Public ordinary functions
bst-add!: Public ordinary functions
bst-balance: Public ordinary functions
bst-copy: Public ordinary functions
bst-count: Public ordinary functions
bst-empty-p: Public ordinary functions
bst-equal-p: Public ordinary functions
bst-from-sorted-values: Public ordinary functions
bst-from-values: Public ordinary functions
bst-left: Private ordinary functions
bst-lesser-p: Public ordinary functions
bst-map: Public ordinary functions
bst-max-depth: Public ordinary functions
bst-max-value: Public ordinary functions
bst-min-depth: Public ordinary functions
bst-min-value: Public ordinary functions
bst-p: Private ordinary functions
bst-remove: Public ordinary functions
bst-remove!: Public ordinary functions
bst-right: Private ordinary functions
bst-search: Public ordinary functions
bst-search-max-value-below: Public ordinary functions
bst-search-min-value-above: Public ordinary functions
bst-tree-copy: Public ordinary functions
bst-tree-equal-p: Public ordinary functions
bst-value: Private ordinary functions
bst-values: Public ordinary functions
bst-values-equal-p: Public ordinary functions

C
copy-bst: Private ordinary functions

F
Function, (setf bst-left): Private ordinary functions
Function, (setf bst-right): Private ordinary functions
Function, (setf bst-value): Private ordinary functions
Function, bst-add: Public ordinary functions
Function, bst-add!: Public ordinary functions
Function, bst-balance: Public ordinary functions
Function, bst-copy: Public ordinary functions
Function, bst-count: Public ordinary functions
Function, bst-empty-p: Public ordinary functions
Function, bst-equal-p: Public ordinary functions
Function, bst-from-sorted-values: Public ordinary functions
Function, bst-from-values: Public ordinary functions
Function, bst-left: Private ordinary functions
Function, bst-lesser-p: Public ordinary functions
Function, bst-map: Public ordinary functions
Function, bst-max-depth: Public ordinary functions
Function, bst-max-value: Public ordinary functions
Function, bst-min-depth: Public ordinary functions
Function, bst-min-value: Public ordinary functions
Function, bst-p: Private ordinary functions
Function, bst-remove: Public ordinary functions
Function, bst-remove!: Public ordinary functions
Function, bst-right: Private ordinary functions
Function, bst-search: Public ordinary functions
Function, bst-search-max-value-below: Public ordinary functions
Function, bst-search-min-value-above: Public ordinary functions
Function, bst-tree-copy: Public ordinary functions
Function, bst-tree-equal-p: Public ordinary functions
Function, bst-value: Private ordinary functions
Function, bst-values: Public ordinary functions
Function, bst-values-equal-p: Public ordinary functions
Function, copy-bst: Private ordinary functions
Function, make-bst: Private ordinary functions

M
make-bst: Private ordinary functions