The cl-interval Reference Manual

This is the cl-interval Reference Manual, generated automatically by Declt version 4.0 beta 2 "William Riker" on Wed May 15 04:07:32 2024 GMT+0.

Table of Contents


1 Introduction


2 Systems

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


2.1 cl-interval

Intervals, interval trees

Author

Ryan Pavlik

License

NewBSD, LLGPL

Source

cl-interval.asd.

Child Components

3 Files

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


3.1 Lisp


3.1.1 cl-interval/cl-interval.asd

Source

cl-interval.asd.

Parent Component

cl-interval (system).

ASDF Systems

cl-interval.


3.1.2 cl-interval/package.lisp

Source

cl-interval.asd.

Parent Component

cl-interval (system).

Packages

interval.


3.1.3 cl-interval/interval.lisp

Dependency

package.lisp (file).

Source

cl-interval.asd.

Parent Component

cl-interval (system).

Public Interface
Internals

3.1.4 cl-interval/tree.lisp

Dependency

interval.lisp (file).

Source

cl-interval.asd.

Parent Component

cl-interval (system).

Public Interface
Internals

4 Packages

Packages are listed by definition order.


4.1 interval

Source

package.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 Ordinary functions

Function: delete (tree interval)

=> INTERVAL, deleted-p

Delete an interval that is interval-equal-p to ‘INTERVAL‘ from ‘TREE‘.

‘INTERVAL‘ may be any type of interval, or a cons in the form ‘(START . END)‘.

Package

interval.

Source

tree.lisp.

Function: find (tree interval)

=> interval-in-tree or NIL

Find a specific interval that is :interval-equal-p to ‘INTERVAL‘ in ‘TREE‘ and return it, or NIL.

‘INTERVAL‘ may be any type of interval, or a cons in the form ‘(START . END)‘.

Package

interval.

Source

tree.lisp.

Function: find-all (tree interval)

=> list-of-intervals or NIL

Find all intervals intersecting ‘INTERVAL‘ in ‘TREE‘. ‘INTERVAL‘ does not have to be matched exactly in ‘TREE‘.

Alternatively, ‘INTERVAL‘ may be either a cons of ‘(START . END)‘, or a single value, which will be used as both the start and the
end (effectively finding intervals at a point).

Package

interval.

Source

tree.lisp.

Function: find-any (tree interval)

=> interval-in-tree or NIL

Find any one interval in ‘TREE‘ intersecting ‘INTERVAL‘.

Alternatively, ‘INTERVAL‘ may be either a cons of ‘(START . END)‘, or a single value, which will be used as both the start and the
end (effectively finding intervals at a point).

Package

interval.

Source

tree.lisp.

Function: insert (tree interval)

=> interval, inserted-p

Insert ‘INTERVAL‘ into ‘TREE‘, if an equivalent interval (by interval-equal-p) is not already in ‘TREE‘, returning ‘INTERVAL‘. Otherwise, return the existing interval.

‘INSERTED-P‘ is ‘T‘ if there was no existing interval, or ‘NIL‘ if the existing interval was returned.

‘INTERVAL‘ may alternatively be a cons in the form ‘(START . END)‘. In this case, a simple interval is created and inserted.

Package

interval.

Source

tree.lisp.

Reader: interval-end (instance)

=> end
Return the ‘END‘ value of the interval.

Package

interval.

Source

interval.lisp.

Target Slot

end.

Writer: (setf interval-end) (instance)
Package

interval.

Source

interval.lisp.

Target Slot

end.

Reader: interval-start (instance)

=> start
Return the ‘START‘ value of the interval.

Package

interval.

Source

interval.lisp.

Target Slot

start.

Writer: (setf interval-start) (instance)
Package

interval.

Source

interval.lisp.

Target Slot

start.

Function: interval< (i1 i2)

=> boolean
A simple example (also used in tests) which compares interval starts numerically by ‘#’<‘.

Package

interval.

Source

interval.lisp.

Function: interval= (i1 i2)

=> boolean
A simple example (also used in tests) which compares interval equality numerically by ‘#’=‘.

Package

interval.

Source

interval.lisp.

Function: make-interval (&key start end)

=> INTERVAL
Returns a simple interval with specified ‘START‘ and ‘END‘.

Package

interval.

Source

interval.lisp.

Function: make-tree (&key interval-before-p interval-equal-p value-before-p)

=> INTERVAL:TREE

Make an interval tree given the specified functions. By default, these are simple numeric comparisons.

‘INTERVAL-BEFORE-P‘ should take two intervals, ‘A‘ and ‘B‘, and test whether the *start* of ‘A‘ comes before the *start* of ‘B‘. This is used solely for tree placement. ‘A‘ and ‘B‘ might be equal, but the test may be a less-than-not-equal test.

‘INTERVAL-EQUAL-P‘ should take two intervals, ‘A‘ and ‘B‘, and test whether they are equal (e.g., the starts and ends are the same). This should *not* be an identity test (i.e., not ‘EQ‘).

‘VALUE-BEFORE-P‘ should take two *values*, ‘A‘ and ‘B‘, which are used as start or end values, and compare whether ‘A‘ comes before ‘B‘. For closed intervals, use a less-than-or-equal function. For open intervals, use a less-than function. Half-open intervals are currently not supported.

Package

interval.

Source

tree.lisp.

Reader: tree-beforep (instance)

=> FUNCTION
Return the function used to compare *intervals*. It should return whether one interval ‘START‘ comes before another interval ‘START‘.

Package

interval.

Source

tree.lisp.

Target Slot

beforep.

Function: tree-dump (tree)

=> list
Return a tree dumped into a list form. This is currently only useful for testing.

Package

interval.

Source

tree.lisp.

Reader: tree-equalp (instance)

=> FUNCTION
Return the function used to compare *intervals*. It should return whether one interval is equal to another. It should not be an identity comparison (i.e., not ‘EQ‘).

Package

interval.

Source

tree.lisp.

Target Slot

equalp.

Function: tree-validate (tree)

=> T
Tests ‘TREE‘ for AA-tree and interval-tree invariants, to make sure the tree is valid. It returns ‘T‘, or raises an error if the invariants are not met.

Package

interval.

Source

tree.lisp.

Reader: tree-value-before-p (instance)

=> FUNCTION
Return the function used to compare *values* (i.e., start and end). For closed intervals, use a less-than-or-equal function. For open intervals, use a less-than function. Half-open intervals are currently not supported.

Package

interval.

Source

tree.lisp.

Target Slot

value-before-p.


5.1.2 Standalone methods

Method: print-object ((i interval) stream)
Source

interval.lisp.

Method: print-object ((object node) stream)
Source

tree.lisp.


5.1.3 Structures

Structure: interval
Package

interval.

Source

interval.lisp.

Direct superclasses

structure-object.

Direct methods

print-object.

Direct slots
Slot: start
Readers

interval-start.

Writers

(setf interval-start).

Slot: end
Readers

interval-end.

Writers

(setf interval-end).

Structure: tree
Package

interval.

Source

tree.lisp.

Direct superclasses

structure-object.

Direct slots
Slot: root
Type

(or null interval::node)

Readers

tree-root.

Writers

(setf tree-root).

Slot: beforep
Type

function

Readers

tree-beforep.

Writers

This slot is read-only.

Slot: equalp
Package

common-lisp.

Type

function

Readers

tree-equalp.

Writers

This slot is read-only.

Slot: value-before-p
Type

function

Readers

tree-value-before-p.

Writers

This slot is read-only.


5.2 Internals


5.2.1 Macros

Macro: if-node-fun ((node function) then &optional else)
Package

interval.

Source

tree.lisp.


5.2.2 Ordinary functions

Function: %copy-tree (instance)
Package

interval.

Source

tree.lisp.

Function: %make-tree (&key root beforep equalp value-before-p)
Package

interval.

Source

tree.lisp.

Function: coerce-interval-designator (designator allow-single-value-interval)
Package

interval.

Source

tree.lisp.

Function: copy-interval (instance)
Package

interval.

Source

interval.lisp.

Function: copy-node (instance)
Package

interval.

Source

tree.lisp.

Function: interval-intersects (v<-fun i1 i2)
Package

interval.

Source

interval.lisp.

Function: interval-p (object)
Package

interval.

Source

interval.lisp.

Function: make-node (&key level left right value max-end)
Package

interval.

Source

tree.lisp.

Function: node-decrease-level (node)
Package

interval.

Source

tree.lisp.

Function: node-delete (tree node value)
Package

interval.

Source

tree.lisp.

Function: node-dump (node)
Package

interval.

Source

tree.lisp.

Function: node-find (tree node value)
Package

interval.

Source

tree.lisp.

Function: node-find-all (tree node interval)
Package

interval.

Source

tree.lisp.

Function: node-find-any (tree node interval)
Package

interval.

Source

tree.lisp.

Function: node-in-range-p (v<-fun node interval)
Package

interval.

Source

tree.lisp.

Function: node-insert (tree node value)
Package

interval.

Source

tree.lisp.

Function: node-leaf-p (node)
Package

interval.

Source

tree.lisp.

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

interval.

Source

tree.lisp.

Target Slot

left.

Function: node-left-level-p (node)
Package

interval.

Source

tree.lisp.

Function: node-leftmost-child (node)
Package

interval.

Source

tree.lisp.

Reader: node-level (instance)
Writer: (setf node-level) (instance)
Package

interval.

Source

tree.lisp.

Target Slot

level.

Reader: node-max-end (instance)
Writer: (setf node-max-end) (instance)
Package

interval.

Source

tree.lisp.

Target Slot

max-end.

Function: node-p (object)
Package

interval.

Source

tree.lisp.

Function: node-predecessor (node)
Package

interval.

Source

tree.lisp.

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

interval.

Source

tree.lisp.

Target Slot

right.

Function: node-rightmost-child (node)
Package

interval.

Source

tree.lisp.

Function: node-skew (tree node)
Package

interval.

Source

tree.lisp.

Function: node-split (tree node)
Package

interval.

Source

tree.lisp.

Function: node-strictly-greater-p (v<-fun node interval)
Package

interval.

Source

tree.lisp.

Function: node-successor (node)
Package

interval.

Source

tree.lisp.

Function: node-two-rights-level-p (node)
Package

interval.

Source

tree.lisp.

Function: node-update-max (tree node)
Package

interval.

Source

tree.lisp.

Function: node-validate (node &optional prev)
Package

interval.

Source

tree.lisp.

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

interval.

Source

tree.lisp.

Target Slot

value.

Function: tree-p (object)
Package

interval.

Source

tree.lisp.

Reader: tree-root (instance)
Writer: (setf tree-root) (instance)
Package

interval.

Source

tree.lisp.

Target Slot

root.


5.2.3 Structures

Structure: node
Package

interval.

Source

tree.lisp.

Direct superclasses

structure-object.

Direct methods

print-object.

Direct slots
Slot: level
Type

(unsigned-byte 16)

Initform

0

Readers

node-level.

Writers

(setf node-level).

Slot: left
Type

(or null interval::node)

Readers

node-left.

Writers

(setf node-left).

Slot: right
Type

(or null interval::node)

Readers

node-right.

Writers

(setf node-right).

Slot: value
Type

interval:interval

Readers

node-value.

Writers

(setf node-value).

Slot: max-end
Readers

node-max-end.

Writers

(setf node-max-end).


Appendix A Indexes


A.1 Concepts


A.2 Functions

Jump to:   %   (  
C   D   F   I   M   N   P   T  
Index Entry  Section

%
%copy-tree: Private ordinary functions
%make-tree: Private ordinary functions

(
(setf interval-end): Public ordinary functions
(setf interval-start): Public ordinary functions
(setf node-left): Private ordinary functions
(setf node-level): Private ordinary functions
(setf node-max-end): Private ordinary functions
(setf node-right): Private ordinary functions
(setf node-value): Private ordinary functions
(setf tree-root): Private ordinary functions

C
coerce-interval-designator: Private ordinary functions
copy-interval: Private ordinary functions
copy-node: Private ordinary functions

D
delete: Public ordinary functions

F
find: Public ordinary functions
find-all: Public ordinary functions
find-any: Public ordinary functions
Function, %copy-tree: Private ordinary functions
Function, %make-tree: Private ordinary functions
Function, (setf interval-end): Public ordinary functions
Function, (setf interval-start): Public ordinary functions
Function, (setf node-left): Private ordinary functions
Function, (setf node-level): Private ordinary functions
Function, (setf node-max-end): Private ordinary functions
Function, (setf node-right): Private ordinary functions
Function, (setf node-value): Private ordinary functions
Function, (setf tree-root): Private ordinary functions
Function, coerce-interval-designator: Private ordinary functions
Function, copy-interval: Private ordinary functions
Function, copy-node: Private ordinary functions
Function, delete: Public ordinary functions
Function, find: Public ordinary functions
Function, find-all: Public ordinary functions
Function, find-any: Public ordinary functions
Function, insert: Public ordinary functions
Function, interval-end: Public ordinary functions
Function, interval-intersects: Private ordinary functions
Function, interval-p: Private ordinary functions
Function, interval-start: Public ordinary functions
Function, interval<: Public ordinary functions
Function, interval=: Public ordinary functions
Function, make-interval: Public ordinary functions
Function, make-node: Private ordinary functions
Function, make-tree: Public ordinary functions
Function, node-decrease-level: Private ordinary functions
Function, node-delete: Private ordinary functions
Function, node-dump: Private ordinary functions
Function, node-find: Private ordinary functions
Function, node-find-all: Private ordinary functions
Function, node-find-any: Private ordinary functions
Function, node-in-range-p: Private ordinary functions
Function, node-insert: Private ordinary functions
Function, node-leaf-p: Private ordinary functions
Function, node-left: Private ordinary functions
Function, node-left-level-p: Private ordinary functions
Function, node-leftmost-child: Private ordinary functions
Function, node-level: Private ordinary functions
Function, node-max-end: Private ordinary functions
Function, node-p: Private ordinary functions
Function, node-predecessor: Private ordinary functions
Function, node-right: Private ordinary functions
Function, node-rightmost-child: Private ordinary functions
Function, node-skew: Private ordinary functions
Function, node-split: Private ordinary functions
Function, node-strictly-greater-p: Private ordinary functions
Function, node-successor: Private ordinary functions
Function, node-two-rights-level-p: Private ordinary functions
Function, node-update-max: Private ordinary functions
Function, node-validate: Private ordinary functions
Function, node-value: Private ordinary functions
Function, tree-beforep: Public ordinary functions
Function, tree-dump: Public ordinary functions
Function, tree-equalp: Public ordinary functions
Function, tree-p: Private ordinary functions
Function, tree-root: Private ordinary functions
Function, tree-validate: Public ordinary functions
Function, tree-value-before-p: Public ordinary functions

I
if-node-fun: Private macros
insert: Public ordinary functions
interval-end: Public ordinary functions
interval-intersects: Private ordinary functions
interval-p: Private ordinary functions
interval-start: Public ordinary functions
interval<: Public ordinary functions
interval=: Public ordinary functions

M
Macro, if-node-fun: Private macros
make-interval: Public ordinary functions
make-node: Private ordinary functions
make-tree: Public ordinary functions
Method, print-object: Public standalone methods
Method, print-object: Public standalone methods

N
node-decrease-level: Private ordinary functions
node-delete: Private ordinary functions
node-dump: Private ordinary functions
node-find: Private ordinary functions
node-find-all: Private ordinary functions
node-find-any: Private ordinary functions
node-in-range-p: Private ordinary functions
node-insert: Private ordinary functions
node-leaf-p: Private ordinary functions
node-left: Private ordinary functions
node-left-level-p: Private ordinary functions
node-leftmost-child: Private ordinary functions
node-level: Private ordinary functions
node-max-end: Private ordinary functions
node-p: Private ordinary functions
node-predecessor: Private ordinary functions
node-right: Private ordinary functions
node-rightmost-child: Private ordinary functions
node-skew: Private ordinary functions
node-split: Private ordinary functions
node-strictly-greater-p: Private ordinary functions
node-successor: Private ordinary functions
node-two-rights-level-p: Private ordinary functions
node-update-max: Private ordinary functions
node-validate: Private ordinary functions
node-value: Private ordinary functions

P
print-object: Public standalone methods
print-object: Public standalone methods

T
tree-beforep: Public ordinary functions
tree-dump: Public ordinary functions
tree-equalp: Public ordinary functions
tree-p: Private ordinary functions
tree-root: Private ordinary functions
tree-validate: Public ordinary functions
tree-value-before-p: Public ordinary functions