The binomial-heap Reference Manual

This is the binomial-heap Reference Manual, generated automatically by Declt version 4.0 beta 2 "William Riker" on Mon Feb 26 14:43:22 2024 GMT+0.

Table of Contents


1 Introduction


2 Systems

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


2.1 binomial-heap

A compact binomial heap implementation.

Author

Volkan YAZICI <>

License

BSD

Source

binomial-heap.asd.

Child Component

src (module).


3 Modules

Modules are listed depth-first from the system components tree.


3.1 binomial-heap/src

Source

binomial-heap.asd.

Parent Component

binomial-heap (system).

Child Components

4 Files

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


4.1 Lisp


4.1.1 binomial-heap/binomial-heap.asd

Source

binomial-heap.asd.

Parent Component

binomial-heap (system).

ASDF Systems

binomial-heap.

Packages

binomial-heap-system.


4.1.2 binomial-heap/src/packages.lisp

Source

binomial-heap.asd.

Parent Component

src (module).

Packages

binomial-heap.


4.1.3 binomial-heap/src/specials.lisp

Dependency

packages.lisp (file).

Source

binomial-heap.asd.

Parent Component

src (module).

Public Interface
Internals

4.1.4 binomial-heap/src/utils.lisp

Dependency

specials.lisp (file).

Source

binomial-heap.asd.

Parent Component

src (module).

Internals

4.1.5 binomial-heap/src/operations.lisp

Dependency

utils.lisp (file).

Source

binomial-heap.asd.

Parent Component

src (module).

Public Interface
Internals

5 Packages

Packages are listed by definition order.


5.1 binomial-heap

Source

packages.lisp.

Nickname

bh

Use List

common-lisp.

Public Interface
Internals

5.2 binomial-heap-system

Source

binomial-heap.asd.

Use List
  • asdf/interface.
  • common-lisp.

6 Definitions

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


6.1 Public Interface


6.1.1 Ordinary functions

Function: extract-extremum-key (heap)

Extracts the extremum value from the ‘BINOMIAL-HEAP’ pointed by ‘HEAP’. Function returns the ‘KEY’ field of the extracted ‘BINOMIAL-TREE’ instance.

Package

binomial-heap.

Source

operations.lisp.

Function: get-extremum-key (heap)

Finds the ‘BINOMIAL-TREE’ with the extremum value and its ‘KEY’ field. Function returns ‘NIL’ in case of no items found.

Package

binomial-heap.

Source

operations.lisp.

Function: insert-key (heap key)

Creates a new ‘BINOMIAL-TREE’ for ‘KEY’ and inserts this node to the ‘BINOMIAL-HEAP’ pointed by ‘HEAP’. Function returns the ‘KEY’.

Package

binomial-heap.

Source

operations.lisp.

Function: unite-heaps (x y)

Unites given two heaps of type ‘BINOMIAL-HEAP’ into a single one. (Assuming ‘TEST’ functions of each heap are equivalent.)

Package

binomial-heap.

Source

operations.lisp.


6.1.2 Generic functions

Generic Reader: test-of (object)
Package

binomial-heap.

Methods
Reader Method: test-of ((binomial-heap binomial-heap))

automatically generated reader method

Source

specials.lisp.

Target Slot

test.

Generic Writer: (setf test-of) (object)
Package

binomial-heap.

Methods
Writer Method: (setf test-of) ((binomial-heap binomial-heap))

automatically generated writer method

Source

specials.lisp.

Target Slot

test.


6.1.3 Standalone methods

Method: print-object ((self binomial-tree) stream)
Source

specials.lisp.


6.1.4 Classes

Class: binomial-heap

Binomial heap container.

Package

binomial-heap.

Source

specials.lisp.

Direct methods
Direct slots
Slot: head
Type

list

Initargs

:head

Readers

head-of.

Writers

(setf head-of).

Slot: test
Type

function

Initargs

:test

Readers

test-of.

Writers

(setf test-of).


6.2 Internals


6.2.1 Macros

Macro: prog1-let ((var val) &body body)
Package

binomial-heap.

Source

utils.lisp.

Macro: when-let ((var val) &body body)
Package

binomial-heap.

Source

utils.lisp.


6.2.2 Ordinary functions

Function: get-prior-to-extremum (head test)

Finds the ‘BINOMIAL-TREE’ prior to the extremum in the sibling list pointed by ‘HEAD’. Function returns ‘NIL’ in case of no extremum or extremum at the beginning.

Package

binomial-heap.

Source

operations.lisp.

Constructs ‘SIBLING’ slots of given list of ‘BINOMIAL-TREE’s to provide given order.

Package

binomial-heap.

Source

operations.lisp.

Makes ‘X’ the child of ‘Y’.

Package

binomial-heap.

Source

operations.lisp.

Function: merge-siblings (x y)

Merges given two ‘BINOMIAL-TREE’s and their related siblings into a single ‘BINOMIAL-TREE’ sibling list.

Package

binomial-heap.

Source

operations.lisp.

Function: print-tree (x)

Utility function to print binomial tree in a human-readable(?) format.

Package

binomial-heap.

Source

operations.lisp.

Function: sexp->tree (sexp)

Converts supplied ‘SEXP’ of ‘(KEY &KEY SIBLING CHILD)’ form into appropriate ‘BINOMIAL-TREE’ instance.

Package

binomial-heap.

Source

operations.lisp.

Function: sibling-list (tree)

Returns reversed list of child and its consequent siblings of supplied ‘TREE’ of type ‘BINOMIAL-TREE’.

Package

binomial-heap.

Source

operations.lisp.

Function: tree->sexp (tree)

Converts supplied ‘BINOMIAL-TREE’ into ‘(KEY &KEY SIBLING CHILD)’ compound form.

Package

binomial-heap.

Source

operations.lisp.

Function: unite-root-lists (test x y)

Unites given ‘X’ and ‘Y’ ‘BINOMIAL-TREE’s and their related siblings into a single ‘BINOMIAL-TREE’.

Package

binomial-heap.

Source

operations.lisp.

Function: unsafe-unite-root-lists (test x y)

Identical to ‘UNITE-ROOT-LISTS’ except that this function doesn’t handle Case 2 condition and break the loop in Case 1. (Case 1 & 2 are redundant while adding a single node to a root list.)

Package

binomial-heap.

Source

operations.lisp.


6.2.3 Generic functions

Generic Reader: child-of (object)
Package

binomial-heap.

Methods
Reader Method: child-of ((binomial-tree binomial-tree))

automatically generated reader method

Source

specials.lisp.

Target Slot

child.

Generic Writer: (setf child-of) (object)
Package

binomial-heap.

Methods
Writer Method: (setf child-of) ((binomial-tree binomial-tree))

automatically generated writer method

Source

specials.lisp.

Target Slot

child.

Generic Reader: degree-of (object)
Package

binomial-heap.

Methods
Reader Method: degree-of ((binomial-tree binomial-tree))

automatically generated reader method

Source

specials.lisp.

Target Slot

degree.

Generic Writer: (setf degree-of) (object)
Package

binomial-heap.

Methods
Writer Method: (setf degree-of) ((binomial-tree binomial-tree))

automatically generated writer method

Source

specials.lisp.

Target Slot

degree.

Generic Reader: head-of (object)
Package

binomial-heap.

Methods
Reader Method: head-of ((binomial-heap binomial-heap))

automatically generated reader method

Source

specials.lisp.

Target Slot

head.

Generic Writer: (setf head-of) (object)
Package

binomial-heap.

Methods
Writer Method: (setf head-of) ((binomial-heap binomial-heap))

automatically generated writer method

Source

specials.lisp.

Target Slot

head.

Generic Reader: key-of (object)
Package

binomial-heap.

Methods
Reader Method: key-of ((binomial-tree binomial-tree))

automatically generated reader method

Source

specials.lisp.

Target Slot

key.

Generic Writer: (setf key-of) (object)
Package

binomial-heap.

Methods
Writer Method: (setf key-of) ((binomial-tree binomial-tree))

automatically generated writer method

Source

specials.lisp.

Target Slot

key.

Generic Reader: parent-of (object)
Package

binomial-heap.

Methods
Reader Method: parent-of ((binomial-tree binomial-tree))

automatically generated reader method

Source

specials.lisp.

Target Slot

parent.

Generic Writer: (setf parent-of) (object)
Package

binomial-heap.

Methods
Writer Method: (setf parent-of) ((binomial-tree binomial-tree))

automatically generated writer method

Source

specials.lisp.

Target Slot

parent.

Generic Reader: sibling-of (object)
Package

binomial-heap.

Methods
Reader Method: sibling-of ((binomial-tree binomial-tree))

automatically generated reader method

Source

specials.lisp.

Target Slot

sibling.

Generic Writer: (setf sibling-of) (object)
Package

binomial-heap.

Methods
Writer Method: (setf sibling-of) ((binomial-tree binomial-tree))

automatically generated writer method

Source

specials.lisp.

Target Slot

sibling.


6.2.4 Classes

Class: binomial-tree

Binomial tree container.

Package

binomial-heap.

Source

specials.lisp.

Direct methods
Direct slots
Slot: parent
Type

binomial-heap::binomial-tree

Initargs

:parent

Readers

parent-of.

Writers

(setf parent-of).

Slot: degree
Type

(integer 0 *)

Initform

0

Initargs

:degree

Readers

degree-of.

Writers

(setf degree-of).

Slot: child
Type

binomial-heap::binomial-tree

Initargs

:child

Readers

child-of.

Writers

(setf child-of).

Slot: sibling
Type

binomial-heap::binomial-tree

Initargs

:sibling

Readers

sibling-of.

Writers

(setf sibling-of).

Slot: key
Initargs

:key

Readers

key-of.

Writers

(setf key-of).


Appendix A Indexes


A.1 Concepts


A.2 Functions

Jump to:   (  
C   D   E   F   G   H   I   K   L   M   P   S   T   U   W  
Index Entry  Section

(
(setf child-of): Private generic functions
(setf child-of): Private generic functions
(setf degree-of): Private generic functions
(setf degree-of): Private generic functions
(setf head-of): Private generic functions
(setf head-of): Private generic functions
(setf key-of): Private generic functions
(setf key-of): Private generic functions
(setf parent-of): Private generic functions
(setf parent-of): Private generic functions
(setf sibling-of): Private generic functions
(setf sibling-of): Private generic functions
(setf test-of): Public generic functions
(setf test-of): Public generic functions

C
child-of: Private generic functions
child-of: Private generic functions

D
degree-of: Private generic functions
degree-of: Private generic functions

E
extract-extremum-key: Public ordinary functions

F
Function, extract-extremum-key: Public ordinary functions
Function, get-extremum-key: Public ordinary functions
Function, get-prior-to-extremum: Private ordinary functions
Function, insert-key: Public ordinary functions
Function, link-siblings: Private ordinary functions
Function, link-trees: Private ordinary functions
Function, merge-siblings: Private ordinary functions
Function, print-tree: Private ordinary functions
Function, sexp->tree: Private ordinary functions
Function, sibling-list: Private ordinary functions
Function, tree->sexp: Private ordinary functions
Function, unite-heaps: Public ordinary functions
Function, unite-root-lists: Private ordinary functions
Function, unsafe-unite-root-lists: Private ordinary functions

G
Generic Function, (setf child-of): Private generic functions
Generic Function, (setf degree-of): Private generic functions
Generic Function, (setf head-of): Private generic functions
Generic Function, (setf key-of): Private generic functions
Generic Function, (setf parent-of): Private generic functions
Generic Function, (setf sibling-of): Private generic functions
Generic Function, (setf test-of): Public generic functions
Generic Function, child-of: Private generic functions
Generic Function, degree-of: Private generic functions
Generic Function, head-of: Private generic functions
Generic Function, key-of: Private generic functions
Generic Function, parent-of: Private generic functions
Generic Function, sibling-of: Private generic functions
Generic Function, test-of: Public generic functions
get-extremum-key: Public ordinary functions
get-prior-to-extremum: Private ordinary functions

H
head-of: Private generic functions
head-of: Private generic functions

I
insert-key: Public ordinary functions

K
key-of: Private generic functions
key-of: Private generic functions

L
link-siblings: Private ordinary functions
link-trees: Private ordinary functions

M
Macro, prog1-let: Private macros
Macro, when-let: Private macros
merge-siblings: Private ordinary functions
Method, (setf child-of): Private generic functions
Method, (setf degree-of): Private generic functions
Method, (setf head-of): Private generic functions
Method, (setf key-of): Private generic functions
Method, (setf parent-of): Private generic functions
Method, (setf sibling-of): Private generic functions
Method, (setf test-of): Public generic functions
Method, child-of: Private generic functions
Method, degree-of: Private generic functions
Method, head-of: Private generic functions
Method, key-of: Private generic functions
Method, parent-of: Private generic functions
Method, print-object: Public standalone methods
Method, sibling-of: Private generic functions
Method, test-of: Public generic functions

P
parent-of: Private generic functions
parent-of: Private generic functions
print-object: Public standalone methods
print-tree: Private ordinary functions
prog1-let: Private macros

S
sexp->tree: Private ordinary functions
sibling-list: Private ordinary functions
sibling-of: Private generic functions
sibling-of: Private generic functions

T
test-of: Public generic functions
test-of: Public generic functions
tree->sexp: Private ordinary functions

U
unite-heaps: Public ordinary functions
unite-root-lists: Private ordinary functions
unsafe-unite-root-lists: Private ordinary functions

W
when-let: Private macros