The clump Reference Manual

Source

Methods

Reader Method: left ((node node)) ¶

automatically generated reader method

Target Slot: %left.

Generic Function: (setf 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

Source

Methods

Method: (setf left) :after ((node node-with-parent)) ¶

Writer Method: (setf left) ((node node)) ¶

automatically generated writer method

Target Slot: %left.

Generic Reader: left (object) ¶

Package

Methods

Reader Method: left ((3-node 3-node)) ¶

automatically generated reader method

Source: 2-3-tree.lisp.
Target Slot: %left.

Reader Method: left ((2-node 2-node)) ¶

automatically generated reader method

Source: 2-3-tree.lisp.
Target Slot: %left.

Generic Reader: middle (object) ¶

Package

Methods

Reader Method: middle ((3-node 3-node)) ¶

automatically generated reader method

Source: 2-3-tree.lisp.
Target Slot: %middle.

Generic Reader: parent (object) ¶

Package

Methods

Reader Method: parent ((node-with-parent node-with-parent)) ¶

automatically generated reader method

Source: binary-tree.lisp.
Target Slot: %parent.

Generic Writer: (setf parent) (object) ¶

Package

Methods

Writer Method: (setf parent) ((node-with-parent node-with-parent)) ¶

automatically generated writer method

Source: binary-tree.lisp.
Target Slot: %parent.

Generic Reader: parent (object) ¶

Package

Methods

Reader Method: parent ((node node)) ¶

automatically generated reader method

Source: 2-3-tree.lisp.
Target Slot: %parent.

Generic Writer: (setf parent) (object) ¶

Package

Methods

Writer Method: (setf parent) ((node node)) ¶

automatically generated writer method

Source: 2-3-tree.lisp.
Target Slot: %parent.

Generic Function: recursive-traversal (tree pre in post) ¶

Package

recursive-traversal.lisp.

Source

Methods

Method: recursive-traversal ((tree node) pre in post) ¶

Generic Function: replace (node old-child new-child) ¶

Package

Source

insertion.lisp.

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

Source

deletion.lisp.

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

Source

replace-child.lisp.

Methods

Method: replace-child ((node node) (old-child node) new-child) ¶

Method: replace-child ((node null) (old-child node) new-child) ¶

Generic Reader: 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

Source

Methods

Reader Method: right ((node node)) ¶

automatically generated reader method

Target Slot: %right.

Generic Function: (setf 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

Source

Methods

Method: (setf right) :after ((node node-with-parent)) ¶

Writer Method: (setf right) ((node node)) ¶

automatically generated writer method

Target Slot: %right.

Generic Reader: right (object) ¶

Package

Methods

Reader Method: right ((3-node 3-node)) ¶

automatically generated reader method

Source: 2-3-tree.lisp.
Target Slot: %right.

Reader Method: right ((2-node 2-node)) ¶

automatically generated reader method

Source: 2-3-tree.lisp.
Target Slot: %right.

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

Source

Methods

Method: rotate-left ((tree node)) ¶

Method: rotate-left (tree) ¶

Generic Function: rotate-left-with-child (node child) ¶

Package

Source

Methods

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

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

Source

Methods

Method: rotate-right ((tree node)) ¶

Method: rotate-right (tree) ¶

Generic Function: rotate-right-with-child (node child) ¶

Package

Source

Methods

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

Method: rotate-right-with-child ((node node) (child node)) ¶

Method: rotate-right-with-child ((node node) (child null)) ¶

Generic Function: splay (node) ¶

Package

Source

Methods

Method: splay ((node node-with-parent)) ¶

Generic Function: splay-step (node) ¶

Package

Source

Methods

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

Generic Function: splay-step-with-left-parent (node parent) ¶

Package

Source

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

Source

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

Source

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

Source

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

Source

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

Source

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

Source

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

Source

insertion.lisp.

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 Reader: tree (object) ¶

Package

Methods

Reader Method: tree ((condition tree-for-insertion-must-be-empty)) ¶

Source: conditions.lisp.
Target Slot: %tree.

Reader Method: tree ((node node)) ¶

automatically generated reader method

Source: 2-3-tree.lisp.
Target Slot: %tree.

Next: Conditions, Previous: Generic functions, Up: Public Interface [Contents][Index]

5.1.2 Standalone methods

Method: initialize-instance :before ((object node) &key left right) ¶

Source: binary-tree.lisp.

Method: initialize-instance :after ((node 2-node) &key) ¶

Source: 2-3-tree.lisp.

Method: initialize-instance :after ((node 3-node) &key) ¶

Source: 2-3-tree.lisp.

Method: report-condition ((condition left-subtree-must-be-non-nil) stream (language english)) ¶

Package: acclimation.
Source: condition-reporters-english.lisp.

Method: report-condition ((condition right-subtree-must-be-non-nil) stream (language english)) ¶

Package: acclimation.
Source: condition-reporters-english.lisp.

Method: report-condition ((condition invalid-binary-tree) stream (language english)) ¶

Package: acclimation.
Source: condition-reporters-english.lisp.

Method: report-condition ((condition must-be-child) stream (language english)) ¶

Package: acclimation.
Source: condition-reporters-english.lisp.

Method: report-condition ((condition tree-for-insertion-must-be-empty) stream (language english)) ¶

Package: acclimation.
Source: condition-reporters-english.lisp.

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

5.1.3 Conditions

Condition: invalid-binary-tree ¶

Package

Source

Direct superclasses

Direct methods

report-condition.
tree.

Direct slots

Slot: %tree ¶

Initargs: :tree
Readers: tree.
Writers: This slot is read-only.

Condition: left-subtree-must-be-non-nil ¶

Package

Source

Direct superclasses

Direct methods

report-condition.
tree.

Direct slots

Slot: %tree ¶

Initargs: :tree
Readers: tree.
Writers: This slot is read-only.

Condition: right-subtree-must-be-non-nil ¶

Package

Source

Direct superclasses

Direct methods

report-condition.
tree.

Direct slots

Slot: %tree ¶

Initargs: :tree
Readers: tree.
Writers: This slot is read-only.

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

5.1.4 Classes

Class: 2-node ¶

Package

Source

Direct superclasses

Direct methods

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

Direct slots

Slot: %left ¶

Initargs: :left
Readers: left.
Writers: (setf %left).

Slot: %right ¶

Initargs: :right
Readers: right.
Writers: (setf %right).

Class: 3-node ¶

Package

Source

Direct superclasses

Direct methods

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

Direct slots

Slot: %left ¶

Initargs: :left
Readers: left.
Writers: (setf %left).

Slot: %middle ¶

Initargs: :middle
Readers: middle.
Writers: (setf %middle).

Slot: %right ¶

Initargs: :right
Readers: right.
Writers: (setf %right).

Class: leaf ¶

Package

Source

Direct superclasses

Direct methods

(setf contents).
contents.
delete.
insert-after.
insert-before.

Direct slots

Slot: %contents ¶

Initargs: :contents
Readers: contents.
Writers: (setf contents).

Class: node ¶

Package

Source

Direct subclasses

node-with-parent.
simple-node.

Direct methods

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

Direct slots

Slot: %left ¶

Initargs: :left
Readers: left.
Writers: (setf left).

Slot: %right ¶

Initargs: :right
Readers: right.
Writers: (setf right).

Class: node-with-parent ¶

Package

Source

Direct superclasses

Direct methods

Direct slots

Slot: %parent ¶

Initargs: :parent
Readers: parent.
Writers: (setf parent).

Class: simple-node ¶

Package: clump-binary-tree.
Source: binary-tree.lisp.
Direct superclasses: node.
Direct methods: iterative-traversal.

Class: tree ¶

Package

Source

Direct methods

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

Direct slots

Slot: %contents ¶

Readers: contents.
Writers: (setf contents).

Slot: %leaf-class ¶

Initargs: :leaf-class
Readers: leaf-class.
Writers: This slot is read-only.

Slot: %2-node-class ¶

Initargs: :2-node-class
Readers: 2-node-class.
Writers: This slot is read-only.

Slot: %3-node-class ¶

Initargs: :3-node-class
Readers: 3-node-class.
Writers: This slot is read-only.

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

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

5.2.1 Generic functions

Generic Writer: (setf %left) (object) ¶

Package

Methods

Writer Method: (setf %left) ((3-node 3-node)) ¶

automatically generated writer method

Source: 2-3-tree.lisp.
Target Slot: %left.

Writer Method: (setf %left) ((2-node 2-node)) ¶

automatically generated writer method

Source: 2-3-tree.lisp.
Target Slot: %left.

Generic Writer: (setf %middle) (object) ¶

Package

Methods

Writer Method: (setf %middle) ((3-node 3-node)) ¶

automatically generated writer method

Source: 2-3-tree.lisp.
Target Slot: %middle.

Generic Writer: (setf %right) (object) ¶

Package

Methods

Writer Method: (setf %right) ((3-node 3-node)) ¶

automatically generated writer method

Source: 2-3-tree.lisp.
Target Slot: %right.

Writer Method: (setf %right) ((2-node 2-node)) ¶

automatically generated writer method

Source: 2-3-tree.lisp.
Target Slot: %right.

Generic Function: 2-node-p (object) ¶

Package

Source

Methods

Method: 2-node-p (object) ¶

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

Generic Function: 3-node-p (object) ¶

Package

Source

Methods

Method: 3-node-p (object) ¶

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

Generic Reader: child (condition) ¶

Package

Methods

Reader Method: child ((condition must-be-child)) ¶

Source: conditions.lisp.
Target Slot: %child.

Generic Function: link-left (parent child) ¶

Package

Source

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

Source

Methods

Method: link-right ((parent node-with-parent) (child node-with-parent)) ¶

Method: link-right ((parent node) child) ¶

Generic Function: node-p (tree) ¶

Package

Source

Methods

Method: node-p (tree) ¶

Method: node-p ((tree node)) ¶

Generic Function: splay-step-with-left-parent-and-grandparent (node parent grandparent) ¶

Package

Source

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

Source

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 Reader: tree (condition) ¶

Package

Methods

Reader Method: tree ((condition must-be-child)) ¶

Source: conditions.lisp.
Target Slot: %tree.

Reader Method: tree ((condition left-subtree-must-be-non-nil)) ¶

Source: conditions.lisp.
Target Slot: %tree.

Reader Method: tree ((condition right-subtree-must-be-non-nil)) ¶

Source: conditions.lisp.
Target Slot: %tree.

Reader Method: tree ((condition invalid-binary-tree)) ¶

Source: conditions.lisp.
Target Slot: %tree.

Generic Function: unlink-left (parent child) ¶

Package

Source

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

Source

Methods

Method: unlink-right ((parent node-with-parent) (child node-with-parent)) ¶

Method: unlink-right ((parent node) child) ¶

Next: Classes, Previous: Generic functions, Up: Internals [Contents][Index]

5.2.2 Conditions

Condition: 2-3-tree-error ¶

Package

Source

tree-for-insertion-must-be-empty.

Direct superclasses

condition.
error.

Direct subclasses

Condition: binary-tree-error ¶

Package

Source

Direct superclasses

condition.
error.

Direct subclasses

invalid-binary-tree.
left-subtree-must-be-non-nil.
must-be-child.
right-subtree-must-be-non-nil.

Condition: must-be-child ¶

Package

Source

Direct superclasses

Direct methods

child.
report-condition.
tree.

Direct slots

Slot: %tree ¶

Initargs: :tree
Readers: tree.
Writers: This slot is read-only.

Slot: %child ¶

Initargs: :child
Readers: child.
Writers: This slot is read-only.

Condition: tree-for-insertion-must-be-empty ¶

Package

Source

Direct superclasses

2-3-tree-error.

Direct methods

report-condition.
tree.

Direct slots

Slot: %tree ¶

Initargs: :tree
Readers: tree.
Writers: This slot is read-only.

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

5.2.3 Classes

Class: node ¶

Package

Source