The bst Reference Manual

Table of Contents

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

The bst Reference Manual

This is the bst Reference Manual, version 1.0, generated automatically by Declt version 2.4 "Will Decker" on Wed Jun 20 10:50:44 2018 GMT+0.


Next: , Previous: , Up: Top   [Contents][Index]

1 Introduction

#+TITLE: BST
#+AUTHOR: Guillaume LE VAILLANT
#+DATE: 2017-06-18
#+EMAIL: glv@posteo.net
#+LANGUAGE: en
#+OPTIONS: num:nil toc:nil html-postamble:nil html-scripts:nil
#+HTML_DOCTYPE: html5

* Description

*BST* is a Common Lisp library for working with binary search trees that
can contain any kind of values.

* License

*BST* is released under the GPL-3 license. See the [[file:LICENSE][LICENSE]] file for details.

* API
** Values

By default, the library is set to work with trees containing numbers.

To work with another type of values, the parameters
~*bst-copy-function*~, ~*bst-equal-p-function*~ and
~*bst-lesser-p-function*~ must be set or bound.

~*bst-copy-function*~ should be a function to use instead of
~identity~ to make a copy of a value.

~*bst-equal-p-function*~ should be a function to use instead of ~=~ to
check if two values of a tree are equal.

~*bst-lesser-p-function*~ should be a function to use instead ot ~<~
to check if a value of a tree is lesser than another.

#+BEGIN_SRC lisp
(bst-copy value) => value
#+END_SRC

Make a copy of /value/ using ~*bst-copy-function*~ if defined or
~identity~ otherwise.

#+BEGIN_SRC lisp
(bst-equal-p value1 value2) => boolean
#+END_SRC

Check if /value1/ and /value2/ are equal using
~*bst-equal-p-function*~ if defined or ~=~ otherwise.

#+BEGIN_SRC lisp
(bst-lesser-p value1 value2) => boolean
#+END_SRC

Check if /value1/ is lesser than /value2/ using
~*bst-lesser-p-function*~ if defined or ~<~ otherwise.

** Trees

#+BEGIN_SRC lisp
+bst-empty+
#+END_SRC

~+bst-empty+~ represents the empty tree.

#+BEGIN_SRC lisp
(bst-empty-p tree) => boolean
#+END_SRC

Check wether a /tree/ is empty or not.

#+BEGIN_SRC lisp
(bst-add tree value) => tree
(bst-add! tree value) => tree
#+END_SRC

Insert a /value/ in a /tree/. If the /value/ is already in the /tree/,
the insertion has no effect (duplicates are discarded). ~bst-add!~ is
the destructive version of ~bst-add~ (it can destroy the /tree/ passed
as argument and take parts of it to build the result, and it inserts
the /value/ as is instead of inserting a copy of it).

#+BEGIN_SRC lisp
(bst-from-values values) => tree
#+END_SRC

Build a tree containing the /values/ passed as argument. /values/ must
be a sequence. ~bst-from-values~ uses ~bst-add!~ to build the tree.

#+BEGIN_SRC lisp
(bst-remove tree value) => tree
(bst-remove! tree value) => tree
#+END_SRC

Remove a /value/ from a /tree/. ~bst-remove!~ is the destructive
version of ~bst-remove~.

#+BEGIN_SRC lisp
(bst-balance tree) => tree
(bst-balance! tree) => tree
#+END_SRC

Balance a /tree/ to make searches more efficient. ~bst-balance!~ is
the destructive version of ~bst-balance~.

#+BEGIN_SRC lisp
(bst-search tree value) => value, value-p
#+END_SRC

Search a /value/ in a /tree/. The first returned value is /value/ if
it was found in the /tree/ and ~nil~ otherwise. The second returned
value is ~t~ if the value was found and ~nil~ otherwise.

#+BEGIN_SRC lisp
(bst-count tree) => integer
#+END_SRC

Return the number of values in a /tree/.

#+BEGIN_SRC lisp
(bst-max-depth tree) => integer
(bst-min-depth tree) => integer
#+END_SRC

Return the maximum or minimum depth of leaf nodes in a /tree/.

#+BEGIN_SRC lisp
(bst-tree-copy tree) => tree
#+END_SRC

Make a copy of a /tree/.

#+BEGIN_SRC lisp
(bst-tree-equal-p tree1 tree2) => boolean
#+END_SRC

Check if two trees have the same structure (nodes and edges).

#+BEGIN_SRC lisp
(bst-values tree) => vector
#+END_SRC

Return a /vector/ containing the sorted values of a /tree/.

#+BEGIN_SRC lisp
(bst-values-equal-p tree1 tree2) => boolean
#+END_SRC

Check if two trees contain the same values (even if they have
different structures).

* Examples

Tree using integer values:

#+BEGIN_SRC lisp
(defvar tree (bst:bst-from-values '(1 2 3 4)))
(setf tree (bst:bst-add tree 5))
(setf tree (bst:bst-remove tree 3))

(bst:bst-search tree 2)
2
T

(bst:bst-search tree 3)
NIL
NIL
#+END_SRC

Tree using string values:

#+BEGIN_SRC lisp
(let* ((bst:*bst-copy-function* #'copy-seq)
       (bst:*bst-equal-p-function* #'string=)
       (bst:*bst-lesser-p-function* #'string<)
       (tree (bst:bst-balance (bst:bst-from-values '("one" "two" "three")))))
  (bst:bst-count tree))
3
#+END_SRC

* Tests

The tests require the *FiveAM* package. They can be run with:

#+BEGIN_SRC lisp
(asdf:oos 'test-op 'bst)
#+END_SRC


Next: , Previous: , Up: Top   [Contents][Index]

2 Systems

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


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

2.1 bst

Author

Guillaume LE VAILLANT

License

GPL-3

Description

Binary search tree

Version

1.0

Source

bst.asd (file)

Component

bst.lisp (file)


Next: , Previous: , Up: Top   [Contents][Index]

3 Files

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


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

3.1 Lisp


Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.1 bst.asd

Location

bst.asd

Systems

bst (system)


Previous: , Up: Lisp files   [Contents][Index]

3.1.2 bst/bst.lisp

Parent

bst (system)

Location

bst.lisp

Packages

bst

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Top   [Contents][Index]

4 Packages

Packages are listed by definition order.


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

4.1 bst

Source

bst.lisp (file)

Use List

common-lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Top   [Contents][Index]

5 Definitions

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


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

5.1 Exported definitions


Next: , Previous: , Up: Exported definitions   [Contents][Index]

5.1.1 Constants

Constant: +bst-empty+

An empty tree is represented by NIL.

Package

bst

Source

bst.lisp (file)


Next: , Previous: , Up: Exported definitions   [Contents][Index]

5.1.2 Special variables

Special Variable: *bst-copy-function*

A function used instead of IDENTITY to copy a value of a tree.

Package

bst

Source

bst.lisp (file)

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

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

Package

bst

Source

bst.lisp (file)

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

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

Package

bst

Source

bst.lisp (file)


Previous: , Up: Exported definitions   [Contents][Index]

5.1.3 Functions

Function: bst-add TREE VALUE

Insert a VALUE in a TREE.

Package

bst

Source

bst.lisp (file)

Function: bst-add! TREE VALUE

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

Package

bst

Source

bst.lisp (file)

Function: bst-balance TREE

Balance a TREE.

Package

bst

Source

bst.lisp (file)

Function: bst-balance! TREE

Balance a TREE. The TREE argument is destroyed.

Package

bst

Source

bst.lisp (file)

Function: bst-copy VALUE

Return a copy of VALUE.

Package

bst

Source

bst.lisp (file)

Function: bst-count TREE

Return the number of nodes in a TREE.

Package

bst

Source

bst.lisp (file)

Function: bst-empty-p TREE

Return T if TREE is empty and NIL otherwise.

Package

bst

Source

bst.lisp (file)

Function: bst-equal-p VALUE1 VALUE2

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

Package

bst

Source

bst.lisp (file)

Function: bst-from-values VALUES

Make a tree from a sequence of values.

Package

bst

Source

bst.lisp (file)

Function: bst-lesser-p VALUE1 VALUE2

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

Package

bst

Source

bst.lisp (file)

Function: bst-max-depth TREE

Return the length of the longest branch in a TREE.

Package

bst

Source

bst.lisp (file)

Function: bst-min-depth TREE

Return the length of the shortest branch in a TREE.

Package

bst

Source

bst.lisp (file)

Function: bst-remove TREE VALUE

Delete a VALUE from a TREE.

Package

bst

Source

bst.lisp (file)

Function: bst-remove! TREE VALUE

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

Package

bst

Source

bst.lisp (file)

Function: bst-search TREE VALUE

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

Package

bst

Source

bst.lisp (file)

Function: bst-tree-copy TREE

Return a copy of a TREE.

Package

bst

Source

bst.lisp (file)

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 (file)

Function: bst-values TREE

Return all the values of a TREE in a vector.

Package

bst

Source

bst.lisp (file)

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 (file)


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

5.2 Internal definitions


Next: , Previous: , Up: Internal definitions   [Contents][Index]

5.2.1 Functions

Function: bst-left INSTANCE
Function: (setf bst-left) VALUE INSTANCE
Package

bst

Source

bst.lisp (file)

Function: bst-p OBJECT
Package

bst

Source

bst.lisp (file)

Function: bst-right INSTANCE
Function: (setf bst-right) VALUE INSTANCE
Package

bst

Source

bst.lisp (file)

Function: bst-value INSTANCE
Function: (setf bst-value) VALUE INSTANCE
Package

bst

Source

bst.lisp (file)

Function: copy-bst INSTANCE
Package

bst

Source

bst.lisp (file)

Function: make-bst &key (VALUE VALUE) (LEFT LEFT) (RIGHT RIGHT)
Package

bst

Source

bst.lisp (file)


Previous: , Up: Internal definitions   [Contents][Index]

5.2.2 Structures

Structure: bst ()
Package

bst

Source

bst.lisp (file)

Direct superclasses

structure-object (structure)

Direct slots
Slot: value
Readers

bst-value (function)

Writers

(setf bst-value) (function)

Slot: left
Initform

bst:+bst-empty+

Readers

bst-left (function)

Writers

(setf bst-left) (function)

Slot: right
Initform

bst:+bst-empty+

Readers

bst-right (function)

Writers

(setf bst-right) (function)


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

Appendix A Indexes


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

A.1 Concepts

Jump to:   B   F   L  
Index Entry  Section

B
bst.asd: The bst<dot>asd file
bst/bst.lisp: The bst/bst<dot>lisp file

F
File, Lisp, bst.asd: The bst<dot>asd file
File, Lisp, bst/bst.lisp: The bst/bst<dot>lisp file

L
Lisp File, bst.asd: The bst<dot>asd file
Lisp File, bst/bst.lisp: The bst/bst<dot>lisp file

Jump to:   B   F   L  

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

A.2 Functions

Jump to:   (  
B   C   F   M  
Index Entry  Section

(
(setf bst-left): Internal functions
(setf bst-right): Internal functions
(setf bst-value): Internal functions

B
bst-add: Exported functions
bst-add!: Exported functions
bst-balance: Exported functions
bst-balance!: Exported functions
bst-copy: Exported functions
bst-count: Exported functions
bst-empty-p: Exported functions
bst-equal-p: Exported functions
bst-from-values: Exported functions
bst-left: Internal functions
bst-lesser-p: Exported functions
bst-max-depth: Exported functions
bst-min-depth: Exported functions
bst-p: Internal functions
bst-remove: Exported functions
bst-remove!: Exported functions
bst-right: Internal functions
bst-search: Exported functions
bst-tree-copy: Exported functions
bst-tree-equal-p: Exported functions
bst-value: Internal functions
bst-values: Exported functions
bst-values-equal-p: Exported functions

C
copy-bst: Internal functions

F
Function, (setf bst-left): Internal functions
Function, (setf bst-right): Internal functions
Function, (setf bst-value): Internal functions
Function, bst-add: Exported functions
Function, bst-add!: Exported functions
Function, bst-balance: Exported functions
Function, bst-balance!: Exported functions
Function, bst-copy: Exported functions
Function, bst-count: Exported functions
Function, bst-empty-p: Exported functions
Function, bst-equal-p: Exported functions
Function, bst-from-values: Exported functions
Function, bst-left: Internal functions
Function, bst-lesser-p: Exported functions
Function, bst-max-depth: Exported functions
Function, bst-min-depth: Exported functions
Function, bst-p: Internal functions
Function, bst-remove: Exported functions
Function, bst-remove!: Exported functions
Function, bst-right: Internal functions
Function, bst-search: Exported functions
Function, bst-tree-copy: Exported functions
Function, bst-tree-equal-p: Exported functions
Function, bst-value: Internal functions
Function, bst-values: Exported functions
Function, bst-values-equal-p: Exported functions
Function, copy-bst: Internal functions
Function, make-bst: Internal functions

M
make-bst: Internal functions

Jump to:   (  
B   C   F   M  

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

A.3 Variables

Jump to:   *   +  
C   L   R   S   V  
Index Entry  Section

*
*bst-copy-function*: Exported special variables
*bst-equal-p-function*: Exported special variables
*bst-lesser-p-function*: Exported special variables

+
+bst-empty+: Exported constants

C
Constant, +bst-empty+: Exported constants

L
left: Internal structures

R
right: Internal structures

S
Slot, left: Internal structures
Slot, right: Internal structures
Slot, value: Internal structures
Special Variable, *bst-copy-function*: Exported special variables
Special Variable, *bst-equal-p-function*: Exported special variables
Special Variable, *bst-lesser-p-function*: Exported special variables

V
value: Internal structures

Jump to:   *   +  
C   L   R   S   V  

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

A.4 Data types

Jump to:   B   P   S  
Index Entry  Section

B
bst: The bst system
bst: The bst package
bst: Internal structures

P
Package, bst: The bst package

S
Structure, bst: Internal structures
System, bst: The bst system

Jump to:   B   P   S