The clump Reference Manual

Table of Contents

The clump Reference Manual

This is the clump Reference Manual, generated automatically by Declt version 3.0 "Montgomery Scott" on Mon Apr 19 15:40:11 2021 GMT+0.

1 Introduction

The purpose of this repository is to provide a collection of
implementations of trees.

In contrast to existing libraries such as cl-containers, we do not
want to impose a particular use for the trees.  Instead, we aim for a
stratified design, allowing client code to choose between different
levels of abstraction.

As a consequence of this policy, we provide low-level interfaces where
the concrete representation is exposed, but also high level interfaces
where the trees can be used as search trees or as trees that represent
sequences of objects.

2 Systems

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

2.1 clump

Author

Robert Strandh <robert.strandh@gmail.com>

License

FreeBSD, see file LICENSE.text

Description

Library for operations on different kinds of trees

Dependencies

• clump-binary-tree (system)
• clump-2-3-tree (system)

Source

clump.asd (file)

2.2 clump-binary-tree

Dependency

acclimation

Source

clump-binary-tree.asd (file)

Components

• packages.lisp (file)
• binary-tree.lisp (file)
• link-unlink.lisp (file)
• conditions.lisp (file)
• replace-child.lisp (file)
• rotation.lisp (file)
• recursive-traversal.lisp (file)
• iterative-traversal.lisp (file)
• splay.lisp (file)
• docstrings-english.lisp (file)
• condition-reporters-english.lisp (file)

2.3 clump-2-3-tree

Dependency

acclimation

Source

clump-2-3-tree.asd (file)

Components

• packages.lisp (file)
• 2-3-tree.lisp (file)
• insertion.lisp (file)
• deletion.lisp (file)
• conditions.lisp (file)
• docstrings-english.lisp (file)
• condition-reporters-english.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 clump.asd

Location

clump.asd

Systems

clump (system)

3.1.2 clump-binary-tree.asd

Location

Binary-tree/clump-binary-tree.asd

Systems

clump-binary-tree (system)

3.1.3 clump-2-3-tree.asd

Location

2-3-tree/clump-2-3-tree.asd

Systems

clump-2-3-tree (system)

3.1.4 clump-binary-tree/packages.lisp

Parent

clump-binary-tree (system)

Location

Binary-tree/packages.lisp

Packages

clump-binary-tree

3.1.5 clump-binary-tree/binary-tree.lisp

Dependency

packages.lisp (file)

Parent

clump-binary-tree (system)

Location

Binary-tree/binary-tree.lisp

Exported Definitions

• left (generic function)
• left (method)
• (setf left) (method)
• (setf left) (generic function)
• (setf left) (method)
• node (class)
• node-with-parent (class)
• parent (method)
• (setf parent) (method)
• right (generic function)
• right (method)
• (setf right) (method)
• (setf right) (generic function)
• (setf right) (method)
• simple-node (class)

Internal Definitions

• node-p (generic function)
• node-p (method)
• node-p (method)

3.1.6 clump-binary-tree/link-unlink.lisp

Dependency

binary-tree.lisp (file)

Parent

clump-binary-tree (system)

Location

Binary-tree/link-unlink.lisp

Internal Definitions

• link-left (generic function)
• link-left (method)
• link-left (method)
• link-right (generic function)
• link-right (method)
• link-right (method)
• unlink-left (generic function)
• unlink-left (method)
• unlink-left (method)
• unlink-right (generic function)
• unlink-right (method)
• unlink-right (method)

3.1.7 clump-binary-tree/conditions.lisp

Dependency

link-unlink.lisp (file)

Parent

clump-binary-tree (system)

Location

Binary-tree/conditions.lisp

Exported Definitions

• invalid-binary-tree (condition)
• left-subtree-must-be-non-nil (condition)
• right-subtree-must-be-non-nil (condition)

Internal Definitions

• binary-tree-error (condition)
• child (method)
• must-be-child (condition)
• tree (method)
• tree (method)
• tree (method)
• tree (method)

3.1.8 clump-binary-tree/replace-child.lisp

Dependency

conditions.lisp (file)

Parent

clump-binary-tree (system)

Location

Binary-tree/replace-child.lisp

Exported Definitions

• replace-child (generic function)
• replace-child (method)
• replace-child (method)

3.1.9 clump-binary-tree/rotation.lisp

Dependency

replace-child.lisp (file)

Parent

clump-binary-tree (system)

Location

Binary-tree/rotation.lisp

Exported Definitions

• rotate-left (generic function)
• rotate-left (method)
• rotate-left (method)
• rotate-left-with-child (generic function)
• rotate-left-with-child (method)
• rotate-left-with-child (method)
• rotate-left-with-child (method)
• rotate-right (generic function)
• rotate-right (method)
• rotate-right (method)
• rotate-right-with-child (generic function)
• rotate-right-with-child (method)
• rotate-right-with-child (method)
• rotate-right-with-child (method)

3.1.10 clump-binary-tree/recursive-traversal.lisp

Dependency

rotation.lisp (file)

Parent

clump-binary-tree (system)

Location

Binary-tree/recursive-traversal.lisp

Exported Definitions

• recursive-traversal (generic function)
• recursive-traversal (method)

3.1.11 clump-binary-tree/iterative-traversal.lisp

Dependency

recursive-traversal.lisp (file)

Parent

clump-binary-tree (system)

Location

Binary-tree/iterative-traversal.lisp

Exported Definitions

• iterative-traversal (generic function)
• iterative-traversal (method)
• iterative-traversal (method)

3.1.12 clump-binary-tree/splay.lisp

Dependency

iterative-traversal.lisp (file)

Parent

clump-binary-tree (system)

Location

Binary-tree/splay.lisp

Exported Definitions

• splay (generic function)
• splay (method)
• splay-step (generic function)
• splay-step (method)
• splay-step-with-left-parent (generic function)
• splay-step-with-left-parent (method)
• splay-step-with-left-parent-and-left-grandparent (generic function)
• splay-step-with-left-parent-and-left-grandparent (method)
• splay-step-with-left-parent-and-right-grandparent (generic function)
• splay-step-with-left-parent-and-right-grandparent (method)
• splay-step-with-parent (generic function)
• splay-step-with-parent (method)
• splay-step-with-parent (method)
• splay-step-with-right-parent (generic function)
• splay-step-with-right-parent (method)
• splay-step-with-right-parent-and-left-grandparent (generic function)
• splay-step-with-right-parent-and-left-grandparent (method)
• splay-step-with-right-parent-and-right-grandparent (generic function)
• splay-step-with-right-parent-and-right-grandparent (method)

Internal Definitions

• splay-step-with-left-parent-and-grandparent (generic function)
• splay-step-with-left-parent-and-grandparent (method)
• splay-step-with-left-parent-and-grandparent (method)
• splay-step-with-right-parent-and-grandparent (generic function)
• splay-step-with-right-parent-and-grandparent (method)
• splay-step-with-right-parent-and-grandparent (method)

3.1.13 clump-binary-tree/docstrings-english.lisp

Dependency

splay.lisp (file)

Parent

clump-binary-tree (system)

Location

Binary-tree/docstrings-english.lisp

3.1.14 clump-binary-tree/condition-reporters-english.lisp

Dependency

docstrings-english.lisp (file)

Parent

clump-binary-tree (system)

Location

Binary-tree/condition-reporters-english.lisp

3.1.15 clump-2-3-tree/packages.lisp

Parent

clump-2-3-tree (system)

Location

2-3-tree/packages.lisp

Packages

clump-2-3-tree

3.1.16 clump-2-3-tree/2-3-tree.lisp

Dependency

packages.lisp (file)

Parent

clump-2-3-tree (system)

Location

2-3-tree/2-3-tree.lisp

Exported Definitions

• 2-node (class)
• 2-node-class (method)
• 3-node (class)
• 3-node-class (method)
• contents (method)
• (setf contents) (method)
• contents (method)
• (setf contents) (method)
• leaf (class)
• leaf-class (method)
• left (method)
• left (method)
• middle (method)
• parent (method)
• (setf parent) (method)
• right (method)
• right (method)
• tree (method)
• tree (class)

Internal Definitions

• (setf %left) (method)
• (setf %left) (method)
• (setf %middle) (method)
• (setf %right) (method)
• (setf %right) (method)
• 2-node-p (generic function)
• 2-node-p (method)
• 2-node-p (method)
• 3-node-p (generic function)
• 3-node-p (method)
• 3-node-p (method)
• node (class)

3.1.17 clump-2-3-tree/insertion.lisp

Dependency

2-3-tree.lisp (file)

Parent

clump-2-3-tree (system)

Location

2-3-tree/insertion.lisp

Exported Definitions

• insert (generic function)
• insert (method)
• insert (method)
• insert-after (generic function)
• insert-after (method)
• insert-before (generic function)
• insert-before (method)
• replace (generic function)
• replace (method)
• replace (method)
• replace (method)
• split (generic function)
• split (method)
• split (method)
• split (method)

3.1.18 clump-2-3-tree/deletion.lisp

Dependency

insertion.lisp (file)

Parent

clump-2-3-tree (system)

Location

2-3-tree/deletion.lisp

Exported Definitions

• delete (generic function)
• delete (method)
• delete-child (generic function)
• delete-child (method)
• delete-child (method)
• delete-child (method)
• replace-and-shrink (generic function)
• replace-and-shrink (method)
• replace-and-shrink (method)
• replace-and-shrink (method)

3.1.19 clump-2-3-tree/conditions.lisp

Dependency

deletion.lisp (file)

Parent

clump-2-3-tree (system)

Location

2-3-tree/conditions.lisp

Exported Definitions

tree (method)

Internal Definitions

• 2-3-tree-error (condition)
• tree-for-insertion-must-be-empty (condition)

3.1.20 clump-2-3-tree/docstrings-english.lisp

Dependency

conditions.lisp (file)

Parent

clump-2-3-tree (system)

Location

2-3-tree/docstrings-english.lisp

3.1.21 clump-2-3-tree/condition-reporters-english.lisp

Dependency

docstrings-english.lisp (file)

Parent

clump-2-3-tree (system)

Location

2-3-tree/condition-reporters-english.lisp

4 Packages

Packages are listed by definition order.

4.1 clump-binary-tree

Source

packages.lisp (file)

Use List

common-lisp

Exported Definitions

• invalid-binary-tree (condition)
• iterative-traversal (generic function)
• iterative-traversal (method)
• iterative-traversal (method)
• left (generic function)
• left (method)
• (setf left) (method)
• (setf left) (generic function)
• (setf left) (method)
• left-subtree-must-be-non-nil (condition)
• node (class)
• node-with-parent (class)
• parent (generic function)
• parent (method)
• (setf parent) (method)
• (setf parent) (generic function)
• recursive-traversal (generic function)
• recursive-traversal (method)
• replace-child (generic function)
• replace-child (method)
• replace-child (method)
• right (generic function)
• right (method)
• (setf right) (method)
• (setf right) (generic function)
• (setf right) (method)
• right-subtree-must-be-non-nil (condition)
• rotate-left (generic function)
• rotate-left (method)
• rotate-left (method)
• rotate-left-with-child (generic function)
• rotate-left-with-child (method)
• rotate-left-with-child (method)
• rotate-left-with-child (method)
• rotate-right (generic function)
• rotate-right (method)
• rotate-right (method)
• rotate-right-with-child (generic function)
• rotate-right-with-child (method)
• rotate-right-with-child (method)
• rotate-right-with-child (method)
• simple-node (class)
• splay (generic function)
• splay (method)
• splay-step (generic function)
• splay-step (method)
• splay-step-with-left-parent (generic function)
• splay-step-with-left-parent (method)
• splay-step-with-left-parent-and-left-grandparent (generic function)
• splay-step-with-left-parent-and-left-grandparent (method)
• splay-step-with-left-parent-and-right-grandparent (generic function)
• splay-step-with-left-parent-and-right-grandparent (method)
• splay-step-with-parent (generic function)
• splay-step-with-parent (method)
• splay-step-with-parent (method)
• splay-step-with-right-parent (generic function)
• splay-step-with-right-parent (method)
• splay-step-with-right-parent-and-left-grandparent (generic function)
• splay-step-with-right-parent-and-left-grandparent (method)
• splay-step-with-right-parent-and-right-grandparent (generic function)
• splay-step-with-right-parent-and-right-grandparent (method)

Internal Definitions

• binary-tree-error (condition)
• child (generic function)
• child (method)
• link-left (generic function)
• link-left (method)
• link-left (method)
• link-right (generic function)
• link-right (method)
• link-right (method)
• must-be-child (condition)
• node-p (generic function)
• node-p (method)
• node-p (method)
• splay-step-with-left-parent-and-grandparent (generic function)
• splay-step-with-left-parent-and-grandparent (method)
• splay-step-with-left-parent-and-grandparent (method)
• splay-step-with-right-parent-and-grandparent (generic function)
• splay-step-with-right-parent-and-grandparent (method)
• splay-step-with-right-parent-and-grandparent (method)
• tree (generic function)
• tree (method)
• tree (method)
• tree (method)
• tree (method)
• unlink-left (generic function)
• unlink-left (method)
• unlink-left (method)
• unlink-right (generic function)
• unlink-right (method)
• unlink-right (method)

4.2 clump-2-3-tree

Source

packages.lisp (file)

Use List

common-lisp

Exported Definitions

• 2-node (class)
• 2-node-class (generic function)
• 2-node-class (method)
• 3-node (class)
• 3-node-class (generic function)
• 3-node-class (method)
• contents (generic function)
• contents (method)
• (setf contents) (method)
• contents (method)
• (setf contents) (method)
• (setf contents) (generic function)
• delete (generic function)
• delete (method)
• delete-child (generic function)
• delete-child (method)
• delete-child (method)
• delete-child (method)
• insert (generic function)
• insert (method)
• insert (method)
• insert-after (generic function)
• insert-after (method)
• insert-before (generic function)
• insert-before (method)
• leaf (class)
• leaf-class (generic function)
• leaf-class (method)
• left (generic function)
• left (method)
• left (method)
• middle (generic function)
• middle (method)
• parent (generic function)
• parent (method)
• (setf parent) (method)
• (setf parent) (generic function)
• replace (generic function)
• replace (method)
• replace (method)
• replace (method)
• replace-and-shrink (generic function)
• replace-and-shrink (method)
• replace-and-shrink (method)
• replace-and-shrink (method)
• right (generic function)
• right (method)
• right (method)
• split (generic function)
• split (method)
• split (method)
• split (method)
• tree (generic function)
• tree (method)
• tree (method)
• tree (class)

Internal Definitions

• (setf %left) (generic function)
• (setf %left) (method)
• (setf %left) (method)
• (setf %middle) (generic function)
• (setf %middle) (method)
• (setf %right) (generic function)
• (setf %right) (method)
• (setf %right) (method)
• 2-3-tree-error (condition)
• 2-node-p (generic function)
• 2-node-p (method)
• 2-node-p (method)
• 3-node-p (generic function)
• 3-node-p (method)
• 3-node-p (method)
• node (class)
• tree-for-insertion-must-be-empty (condition)

5 Definitions

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

5.1 Exported definitions

5.1.1 Generic functions

Generic Function: 2-node-class OBJECT

Package

clump-2-3-tree

Methods

Method: 2-node-class (TREE tree)

automatically generated reader method

Source

2-3-tree.lisp (file)

Generic Function: 3-node-class OBJECT

Package

clump-2-3-tree

Methods

Method: 3-node-class (TREE tree)

automatically generated reader method

Source

2-3-tree.lisp (file)

Generic Function: contents OBJECT

Generic Function: (setf contents) NEW-VALUE OBJECT

Package

clump-2-3-tree

Methods

Method: contents (LEAF leaf)

automatically generated reader method

Source

2-3-tree.lisp (file)

Method: (setf contents) NEW-VALUE (LEAF leaf)

automatically generated writer method

Source

2-3-tree.lisp (file)

Method: contents (TREE tree)

automatically generated reader method

Source

2-3-tree.lisp (file)

Method: (setf contents) NEW-VALUE (TREE tree)

automatically generated writer method

Source

2-3-tree.lisp (file)

Generic Function: delete LEAF

Package

clump-2-3-tree

Source

deletion.lisp (file)

Methods

Method: delete (LEAF leaf)

Generic Function: delete-child PARENT CHILD

Package

clump-2-3-tree

Source

deletion.lisp (file)

Methods

Method: delete-child (NODE 3-node) CHILD

Method: delete-child (NODE 2-node) CHILD

Method: delete-child (TREE tree) CHILD

Generic Function: insert OBJECT TREE

Package

clump-2-3-tree

Source

insertion.lisp (file)

Methods

Method: insert OBJECT (TREE tree)

Method: insert OBJECT (TREE tree) before

Generic Function: insert-after OBJECT LEAF

Package

clump-2-3-tree

Source

insertion.lisp (file)

Methods

Method: insert-after OBJECT (LEAF leaf)

Generic Function: insert-before OBJECT LEAF

Package

clump-2-3-tree

Source

insertion.lisp (file)

Methods

Method: insert-before OBJECT (LEAF leaf)

Generic Function: iterative-traversal TREE PRE IN POST

Package

clump-binary-tree

Source

iterative-traversal.lisp (file)

Methods

Method: iterative-traversal (TREE simple-node) PRE IN POST

Method: iterative-traversal (TREE node-with-parent) PRE IN POST

Generic Function: leaf-class OBJECT

Package

clump-2-3-tree

Methods

Method: leaf-class (TREE tree)

automatically generated reader method

Source

2-3-tree.lisp (file)

Generic Function: left NODE

Given a binary tree, return the left child of that tree. If an object other than a binary tree is given,
then an error of type INVALID-BINARY-TREE is signaled.

Package

clump-binary-tree

Source

binary-tree.lisp (file)

Writer

(setf left) (generic function)

Methods

Method: left (NODE node)

automatically generated reader method

Generic Function: (setf left) NEW-LEFT NODE

Given two binary trees, NEW and TREE, make NEW the new left child of TREE. NEW may be a node or NIL.
If TREE is NIL an error of type, INVALID-BINARY-TREE is signaled.

Package

clump-binary-tree

Source

binary-tree.lisp (file)

Reader

left (generic function)

Methods

Method: (setf left) NEW-VALUE (NODE node)

automatically generated writer method

Method: (setf left) (NEW-LEFT node-with-parent) (NODE node-with-parent) after

Generic Function: left OBJECT

Package

clump-2-3-tree

Methods

Method: left (3-NODE 3-node)

automatically generated reader method

Source

2-3-tree.lisp (file)

Method: left (2-NODE 2-node)

automatically generated reader method

Source

2-3-tree.lisp (file)

Generic Function: middle OBJECT

Package

clump-2-3-tree

Methods

Method: middle (3-NODE 3-node)

automatically generated reader method

Source

2-3-tree.lisp (file)

Generic Function: parent OBJECT

Generic Function: (setf parent) NEW-VALUE OBJECT

Package

clump-binary-tree

Methods

Method: parent (NODE-WITH-PARENT node-with-parent)

automatically generated reader method

Source

binary-tree.lisp (file)

Method: (setf parent) NEW-VALUE (NODE-WITH-PARENT node-with-parent)

automatically generated writer method

Source

binary-tree.lisp (file)

Generic Function: parent OBJECT

Generic Function: (setf parent) NEW-VALUE OBJECT

Package

clump-2-3-tree

Methods

Method: parent (NODE node)

automatically generated reader method

Source

2-3-tree.lisp (file)

Method: (setf parent) NEW-VALUE (NODE node)

automatically generated writer method

Source

2-3-tree.lisp (file)

Generic Function: recursive-traversal TREE PRE IN POST

Package

clump-binary-tree

Source

recursive-traversal.lisp (file)

Methods

Method: recursive-traversal (TREE node) PRE IN POST

Generic Function: replace NODE OLD-CHILD NEW-CHILD

Package

clump-2-3-tree

Source

insertion.lisp (file)

Methods

Method: replace (TREE tree) OLD-CHILD NEW-CHILD

Method: replace (NODE 3-node) OLD-CHILD NEW-CHILD

Method: replace (NODE 2-node) OLD-CHILD NEW-CHILD

Generic Function: replace-and-shrink PARENT OLD-CHILD NEW-CHILD

Package

clump-2-3-tree

Source

deletion.lisp (file)

Methods

Method: replace-and-shrink (NODE 3-node) OLD-CHILD NEW-CHILD

Method: replace-and-shrink (NODE 2-node) OLD-CHILD NEW-CHILD

Method: replace-and-shrink (TREE tree) OLD-CHILD NEW-CHILD

Generic Function: replace-child NODE OLD-CHILD NEW-CHILD

Package

clump-binary-tree

Source

replace-child.lisp (file)

Methods

Method: replace-child (NODE node) (OLD-CHILD node) NEW-CHILD

Method: replace-child (NODE null) (OLD-CHILD node) NEW-CHILD

Generic Function: right NODE

Given a binary tree, return the right child of that tree. If an object other than a binary tree is given,
then an error of type INVALID-BINARY-TREE is signaled.

Package

clump-binary-tree

Source

binary-tree.lisp (file)

Writer

(setf right) (generic function)

Methods

Method: right (NODE node)

automatically generated reader method

Generic Function: (setf right) NEW-RIGHT NODE

Given two binary trees, NEW and TREE, make NEW the new right child of TREE. NEW may be a node or NIL.
If TREE is NIL an error of type, INVALID-BINARY-TREE is signaled.

Package

clump-binary-tree

Source

binary-tree.lisp (file)

Reader

right (generic function)

Methods

Method: (setf right) NEW-VALUE (NODE node)

automatically generated writer method

Method: (setf right) (NEW-RIGHT node-with-parent) (NODE node-with-parent) after

Generic Function: right OBJECT

Package

clump-2-3-tree

Methods

Method: right (3-NODE 3-node)

automatically generated reader method

Source

2-3-tree.lisp (file)

Method: right (2-NODE 2-node)

automatically generated reader method

Source

2-3-tree.lisp (file)

Generic Function: rotate-left TREE

Given a binary tree TREE, apply a left rotation to it. If TREE is not a node, an error of type, INVALID-BINARY-TREE is signaled.
If the right child of TREE is not a node, an error of type RIGHT-SUBTREE-MUST-BE-NON-NIL is signaled.
The new root of the tree is returned.
If TREE has a parent node, no provision is made
for replacing TREE with the return value of this function. Client code is responsible for doing that.

Package

clump-binary-tree

Source

rotation.lisp (file)

Methods

Method: rotate-left (TREE node)

Method: rotate-left TREE

Generic Function: rotate-left-with-child NODE CHILD

Package

clump-binary-tree

Source

rotation.lisp (file)

Methods

Method: rotate-left-with-child (NODE node-with-parent) (CHILD node-with-parent) around

Method: rotate-left-with-child (NODE node) (CHILD node)

Method: rotate-left-with-child (NODE node) (CHILD null)

Generic Function: rotate-right TREE

Given a binary tree TREE, apply a right rotation to it. If TREE is not a node, an error of type, INVALID-BINARY-TREE is signaled.
If the left child of TREE is not a node, an error of type LEFT-SUBTREE-MUST-BE-NON-NIL is signaled.
The new root of the tree is returned.
If TREE has a parent node, no provision is made
for replacing TREE with the return value of this function. Client code is responsible for doing that.

Package

clump-binary-tree

Source

rotation.lisp (file)

Methods

Method: rotate-right (TREE node)

Method: rotate-right TREE

Generic Function: rotate-right-with-child NODE CHILD

Package

clump-binary-tree

Source

rotation.lisp (file)

Methods

Method: rotate-right-with-child (NODE node-with-parent) (CHILD node-with-parent) around

Method: rotate-right-with-child (NODE node) (CHILD node)

Method: rotate-right-with-child (NODE node) (CHILD null)

Generic Function: splay NODE

Package

clump-binary-tree

Source

splay.lisp (file)

Methods

Method: splay (NODE node-with-parent)

Generic Function: splay-step NODE

Package

clump-binary-tree

Source

splay.lisp (file)

Methods

Method: splay-step (NODE node-with-parent)

Generic Function: splay-step-with-left-parent NODE PARENT

Package

clump-binary-tree

Source

splay.lisp (file)

Methods

Method: splay-step-with-left-parent (NODE node-with-parent) (PARENT node-with-parent)

Generic Function: splay-step-with-left-parent-and-left-grandparent NODE PARENT GRANDPARENT

Package

clump-binary-tree

Source

splay.lisp (file)

Methods

Method: splay-step-with-left-parent-and-left-grandparent (NODE node-with-parent) (PARENT node-with-parent) (GRANDPARENT node-with-parent)

Generic Function: splay-step-with-left-parent-and-right-grandparent NODE PARENT GRANDPARENT

Package

clump-binary-tree

Source

splay.lisp (file)

Methods

Method: splay-step-with-left-parent-and-right-grandparent (NODE node-with-parent) (PARENT node-with-parent) (GRANDPARENT node-with-parent)

Generic Function: splay-step-with-parent NODE PARENT

Package

clump-binary-tree

Source

splay.lisp (file)

Methods

Method: splay-step-with-parent (NODE node-with-parent) (PARENT null)

Method: splay-step-with-parent (NODE node-with-parent) (PARENT node-with-parent)

Generic Function: splay-step-with-right-parent NODE PARENT

Package

clump-binary-tree

Source

splay.lisp (file)

Methods

Method: splay-step-with-right-parent (NODE node-with-parent) (PARENT node-with-parent)

Generic Function: splay-step-with-right-parent-and-left-grandparent NODE PARENT GRANDPARENT

Package

clump-binary-tree

Source

splay.lisp (file)

Methods

Method: splay-step-with-right-parent-and-left-grandparent (NODE node-with-parent) (PARENT node-with-parent) (GRANDPARENT node-with-parent)

Generic Function: splay-step-with-right-parent-and-right-grandparent NODE PARENT GRANDPARENT

Package

clump-binary-tree

Source

splay.lisp (file)

Methods

Method: splay-step-with-right-parent-and-right-grandparent (NODE node-with-parent) (PARENT node-with-parent) (GRANDPARENT node-with-parent)

Generic Function: split NODE OLD-CHILD NEW-CHILD-1 NEW-CHILD-2

Package

clump-2-3-tree

Source

insertion.lisp (file)

Methods

Method: split (TREE tree) OLD-CHILD NEW-CHILD-1 NEW-CHILD-2

Method: split (NODE 3-node) OLD-CHILD NEW-CHILD-1 NEW-CHILD-2

Method: split (NODE 2-node) OLD-CHILD NEW-CHILD-1 NEW-CHILD-2

Generic Function: tree OBJECT

Package

clump-2-3-tree

Methods

Method: tree (CONDITION tree-for-insertion-must-be-empty)

Source

conditions.lisp (file)

Method: tree (NODE node)

automatically generated reader method

Source

2-3-tree.lisp (file)

5.1.2 Conditions

Condition: invalid-binary-tree ()

Package

clump-binary-tree

Source

conditions.lisp (file)

Direct superclasses

binary-tree-error (condition)

Direct methods

• report-condition (method)
• tree (method)

Direct slots

Slot: %tree

Initargs

:tree

Readers

tree (generic function)

Condition: left-subtree-must-be-non-nil ()

Package

clump-binary-tree

Source

conditions.lisp (file)

Direct superclasses

binary-tree-error (condition)

Direct methods

• report-condition (method)
• tree (method)

Direct slots

Slot: %tree

Initargs

:tree

Readers

tree (generic function)

Condition: right-subtree-must-be-non-nil ()

Package

clump-binary-tree

Source

conditions.lisp (file)

Direct superclasses

binary-tree-error (condition)

Direct methods

• report-condition (method)
• tree (method)

Direct slots

Slot: %tree

Initargs

:tree

Readers

tree (generic function)

5.1.3 Classes

Class: 2-node ()

Package

clump-2-3-tree

Source

2-3-tree.lisp (file)

Direct superclasses

node (class)

Direct methods

• replace-and-shrink (method)
• delete-child (method)
• split (method)
• replace (method)
• 2-node-p (method)
• initialize-instance (method)
• (setf %right) (method)
• right (method)
• (setf %left) (method)
• left (method)

Direct slots

Slot: %left

Initargs

:left

Readers

left (generic function)

Writers

(setf %left) (generic function)

Slot: %right

Initargs

:right

Readers

right (generic function)

Writers

(setf %right) (generic function)

Class: 3-node ()

Package

clump-2-3-tree

Source

2-3-tree.lisp (file)

Direct superclasses

node (class)

Direct methods

• replace-and-shrink (method)
• delete-child (method)
• split (method)
• replace (method)
• 3-node-p (method)
• initialize-instance (method)
• (setf %right) (method)
• right (method)
• (setf %middle) (method)
• middle (method)
• (setf %left) (method)
• left (method)

Direct slots

Slot: %left

Initargs

:left

Readers

left (generic function)

Writers

(setf %left) (generic function)

Slot: %middle

Initargs

:middle

Readers

middle (generic function)

Writers

(setf %middle) (generic function)

Slot: %right

Initargs

:right

Readers

right (generic function)

Writers

(setf %right) (generic function)

Class: leaf ()

Package

clump-2-3-tree

Source

2-3-tree.lisp (file)

Direct superclasses

node (class)

Direct methods

• delete (method)
• insert-after (method)
• insert-before (method)
• contents (method)
• contents (method)

Direct slots

Slot: %contents

Initargs

:contents

Readers

contents (generic function)

Writers

(setf contents) (generic function)

Class: node ()

Package

clump-binary-tree

Source

binary-tree.lisp (file)

Direct superclasses

standard-object (class)

Direct subclasses

• simple-node (class)
• node-with-parent (class)

Direct methods

• recursive-traversal (method)
• rotate-right (method)
• rotate-right-with-child (method)
• rotate-right-with-child (method)
• rotate-left (method)
• rotate-left-with-child (method)
• rotate-left-with-child (method)
• replace-child (method)
• replace-child (method)
• unlink-right (method)
• unlink-left (method)
• link-right (method)
• link-left (method)
• initialize-instance (method)
• node-p (method)
• right (method)
• right (method)
• left (method)
• left (method)

Direct slots

Slot: %left

Initargs

:left

Readers

left (generic function)

Writers

(setf left) (generic function)

Slot: %right

Initargs

:right

Readers

right (generic function)

Writers

(setf right) (generic function)

Class: node-with-parent ()

Package

clump-binary-tree

Source

binary-tree.lisp (file)

Direct superclasses

node (class)

Direct methods

• splay (method)
• splay-step (method)
• splay-step-with-parent (method)
• splay-step-with-parent (method)
• splay-step-with-right-parent (method)
• splay-step-with-left-parent (method)
• splay-step-with-right-parent-and-grandparent (method)
• splay-step-with-right-parent-and-grandparent (method)
• splay-step-with-left-parent-and-grandparent (method)
• splay-step-with-left-parent-and-grandparent (method)
• splay-step-with-right-parent-and-left-grandparent (method)
• splay-step-with-right-parent-and-right-grandparent (method)
• splay-step-with-left-parent-and-right-grandparent (method)
• splay-step-with-left-parent-and-left-grandparent (method)
• iterative-traversal (method)
• rotate-right-with-child (method)
• rotate-left-with-child (method)
• unlink-right (method)
• unlink-left (method)
• link-right (method)
• link-left (method)
• (setf right) (method)
• (setf left) (method)
• parent (method)
• parent (method)

Direct slots

Slot: %parent

Initargs

:parent

Readers

parent (generic function)

Writers

(setf parent) (generic function)

Class: simple-node ()

Package

clump-binary-tree

Source

binary-tree.lisp (file)

Direct superclasses

node (class)

Direct methods

iterative-traversal (method)

Class: tree ()

Package

clump-2-3-tree

Source

2-3-tree.lisp (file)

Direct superclasses

standard-object (class)

Direct methods

• replace-and-shrink (method)
• delete-child (method)
• split (method)
• replace (method)
• insert (method)
• insert (method)
• 3-node-class (method)
• 2-node-class (method)
• leaf-class (method)
• contents (method)
• contents (method)

Direct slots

Slot: %contents

Readers

contents (generic function)

Writers

(setf contents) (generic function)

Slot: %leaf-class

Initargs

:leaf-class

Readers

leaf-class (generic function)

Slot: %2-node-class

Initargs

:2-node-class

Readers

2-node-class (generic function)

Slot: %3-node-class

Initargs

:3-node-class

Readers

3-node-class (generic function)

5.2 Internal definitions

5.2.1 Generic functions

Generic Function: (setf %left) NEW-VALUE OBJECT

Package

clump-2-3-tree

Methods

Method: (setf %left) NEW-VALUE (3-NODE 3-node)

automatically generated writer method

Source

2-3-tree.lisp (file)

Method: (setf %left) NEW-VALUE (2-NODE 2-node)

automatically generated writer method

Source

2-3-tree.lisp (file)

Generic Function: (setf %middle) NEW-VALUE OBJECT

Package

clump-2-3-tree

Methods

Method: (setf %middle) NEW-VALUE (3-NODE 3-node)

automatically generated writer method

Source

2-3-tree.lisp (file)

Generic Function: (setf %right) NEW-VALUE OBJECT

Package

clump-2-3-tree

Methods

Method: (setf %right) NEW-VALUE (3-NODE 3-node)

automatically generated writer method

Source

2-3-tree.lisp (file)

Method: (setf %right) NEW-VALUE (2-NODE 2-node)

automatically generated writer method

Source

2-3-tree.lisp (file)

Generic Function: 2-node-p OBJECT

Package

clump-2-3-tree

Source

2-3-tree.lisp (file)

Methods

Method: 2-node-p OBJECT

Method: 2-node-p (NODE 2-node)

Generic Function: 3-node-p OBJECT

Package

clump-2-3-tree

Source

2-3-tree.lisp (file)

Methods

Method: 3-node-p OBJECT

Method: 3-node-p (NODE 3-node)

Generic Function: child CONDITION

Package

clump-binary-tree

Methods

Method: child (CONDITION must-be-child)

Source

conditions.lisp (file)

Generic Function: link-left PARENT CHILD

Package

clump-binary-tree

Source

link-unlink.lisp (file)

Methods

Method: link-left (PARENT node-with-parent) (CHILD node-with-parent)

Method: link-left (PARENT node) CHILD

Generic Function: link-right PARENT CHILD

Package

clump-binary-tree

Source

link-unlink.lisp (file)

Methods

Method: link-right (PARENT node-with-parent) (CHILD node-with-parent)

Method: link-right (PARENT node) CHILD

Generic Function: node-p TREE

Package

clump-binary-tree

Source

binary-tree.lisp (file)

Methods

Method: node-p TREE

Method: node-p (TREE node)

Generic Function: splay-step-with-left-parent-and-grandparent NODE PARENT GRANDPARENT

Package

clump-binary-tree

Source

splay.lisp (file)

Methods

Method: splay-step-with-left-parent-and-grandparent (NODE node-with-parent) (PARENT node-with-parent) (GRANDPARENT null)

Method: splay-step-with-left-parent-and-grandparent (NODE node-with-parent) (PARENT node-with-parent) (GRANDPARENT node-with-parent)

Generic Function: splay-step-with-right-parent-and-grandparent NODE PARENT GRANDPARENT

Package

clump-binary-tree

Source

splay.lisp (file)

Methods

Method: splay-step-with-right-parent-and-grandparent (NODE node-with-parent) (PARENT node-with-parent) (GRANDPARENT null)

Method: splay-step-with-right-parent-and-grandparent (NODE node-with-parent) (PARENT node-with-parent) (GRANDPARENT node-with-parent)

Generic Function: tree CONDITION

Package

clump-binary-tree

Methods

Method: tree (CONDITION must-be-child)

Source

conditions.lisp (file)

Method: tree (CONDITION left-subtree-must-be-non-nil)

Source

conditions.lisp (file)

Method: tree (CONDITION right-subtree-must-be-non-nil)

Source

conditions.lisp (file)

Method: tree (CONDITION invalid-binary-tree)

Source

conditions.lisp (file)

Generic Function: unlink-left PARENT CHILD

Package

clump-binary-tree

Source

link-unlink.lisp (file)

Methods

Method: unlink-left (PARENT node-with-parent) (CHILD node-with-parent)

Method: unlink-left (PARENT node) CHILD

Generic Function: unlink-right PARENT CHILD

Package

clump-binary-tree

Source

link-unlink.lisp (file)

Methods

Method: unlink-right (PARENT node-with-parent) (CHILD node-with-parent)

Method: unlink-right (PARENT node) CHILD

5.2.2 Conditions

Condition: 2-3-tree-error ()

Package

clump-2-3-tree

Source

conditions.lisp (file)

Direct superclasses

• condition (condition)
• error (condition)

Direct subclasses

tree-for-insertion-must-be-empty (condition)

Condition: binary-tree-error ()

Package

clump-binary-tree

Source

conditions.lisp (file)

Direct superclasses

• condition (condition)
• error (condition)

Direct subclasses

• invalid-binary-tree (condition)
• right-subtree-must-be-non-nil (condition)
• left-subtree-must-be-non-nil (condition)
• must-be-child (condition)

Condition: must-be-child ()

Package

clump-binary-tree

Source

conditions.lisp (file)

Direct superclasses

binary-tree-error (condition)

Direct methods

• report-condition (method)
• child (method)
• tree (method)

Direct slots

Slot: %tree

Initargs

:tree

Readers

tree (generic function)

Slot: %child

Initargs

:child

Readers

child (generic function)

Condition: tree-for-insertion-must-be-empty ()

Package

clump-2-3-tree

Source

conditions.lisp (file)

Direct superclasses

2-3-tree-error (condition)

Direct methods

• report-condition (method)
• tree (method)

Direct slots

Slot: %tree

Initargs

:tree

Readers

tree (generic function)

5.2.3 Classes

Class: node ()

Package

clump-2-3-tree

Source

2-3-tree.lisp (file)

Direct superclasses

standard-object (class)

Direct subclasses

• leaf (class)
• 2-node (class)
• 3-node (class)

Direct methods

• tree (method)
• parent (method)
• parent (method)

Direct slots

Slot: %parent

Initargs

:parent

Readers

parent (generic function)

Writers

(setf parent) (generic function)

Slot: %tree

Initargs

:tree

Readers

tree (generic function)

Appendix A Indexes

A.1 Concepts

A.2 Functions