The cl-interval Reference Manual

Table of Contents

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

The cl-interval Reference Manual

This is the cl-interval Reference Manual, generated automatically by Declt version 3.0 "Montgomery Scott" on Tue Apr 28 11:02:09 2020 GMT+0.


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

1 Introduction

cl-interval

This is a simple, efficient implementation of intervals and interval trees for Common Lisp. This is useful if you wish to have a lot of start-end pairs, and find all overlapping intervals at a point, or within an interval:

(defvar *tree* (interval:make-tree))

(interval:insert *tree* '(1 . 1))
(interval:insert *tree* '(1 . 3))
(interval:insert *tree* '(2 . 4))
(interval:insert *tree* '(5 . 9))

(interval:find *tree* '(1 . 1)) ;; => #<1-1>
(interval:find *tree* '(1 . 2)) ;; => NIL

(interval:find-all *tree* '(1 . 1))
   ;; => (#<1-1> #<1-3>)

;;; Equivalent to:
(interval:find-all *tree* 1)
   ;; => (#<1-1> #<1-3>)

(interval:find-all *tree* '(1 . 2))
   ;; => (#<1-1> #<1-3> #<2-4>)

The implementation for this is based on an augmented AA tree as discussed in the following:

A short summary of this method can (at the time of writing) be found on wikipedia.

The full documentation can be found here.


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 cl-interval

Author

Ryan Pavlik

License

NewBSD, LLGPL

Description

Intervals, interval trees

Source

cl-interval.asd (file)

Components

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 cl-interval.asd

Location

cl-interval.asd

Systems

cl-interval (system)


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

3.1.2 cl-interval/package.lisp

Parent

cl-interval (system)

Location

package.lisp

Packages

interval


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

3.1.3 cl-interval/interval.lisp

Dependency

package.lisp (file)

Parent

cl-interval (system)

Location

interval.lisp

Exported Definitions
Internal Definitions

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

3.1.4 cl-interval/tree.lisp

Dependency

interval.lisp (file)

Parent

cl-interval (system)

Location

tree.lisp

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 interval

Source

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

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

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

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

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

Function: interval-end INSTANCE

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

Package

interval

Source

interval.lisp (file)

Writer

(setf interval-end) (function)

Function: (setf interval-end) VALUE INSTANCE
Package

interval

Source

interval.lisp (file)

Reader

interval-end (function)

Function: interval-start INSTANCE

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

Package

interval

Source

interval.lisp (file)

Writer

(setf interval-start) (function)

Function: (setf interval-start) VALUE INSTANCE
Package

interval

Source

interval.lisp (file)

Reader

interval-start (function)

Function: interval< I1 I2

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

Package

interval

Source

interval.lisp (file)

Function: interval= I1 I2

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

Package

interval

Source

interval.lisp (file)

Function: make-interval &key (START START) (END END)

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

Package

interval

Source

interval.lisp (file)

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

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

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

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

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

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


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

5.1.2 Structures

Structure: interval ()
Package

interval

Source

interval.lisp (file)

Direct superclasses

structure-object (structure)

Direct methods

print-object (method)

Direct slots
Slot: start
Readers

interval-start (function)

Writers

(setf interval-start) (function)

Slot: end
Readers

interval-end (function)

Writers

(setf interval-end) (function)

Structure: tree ()
Package

interval

Source

tree.lisp (file)

Direct superclasses

structure-object (structure)

Direct slots
Slot: root
Type

(or null interval::node)

Readers

tree-root (function)

Writers

(setf tree-root) (function)

Slot: beforep
Type

function

Readers

tree-beforep (function)

Writers

(setf tree-beforep) (function)

Slot: equalp
Type

function

Readers

tree-equalp (function)

Writers

(setf tree-equalp) (function)

Slot: value-before-p
Type

function

Readers

tree-value-before-p (function)

Writers

(setf tree-value-before-p) (function)


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

5.2 Internal definitions


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

5.2.1 Macros

Macro: if-node-fun (NODE FUNCTION) THEN &optional ELSE
Package

interval

Source

tree.lisp (file)


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

5.2.2 Functions

Function: %copy-tree INSTANCE
Package

interval

Source

tree.lisp (file)

Function: %make-tree &key (ROOT ROOT) (BEFOREP BEFOREP) (EQUALP EQUALP) (VALUE-BEFORE-P VALUE-BEFORE-P)
Package

interval

Source

tree.lisp (file)

Function: coerce-interval-designator DESIGNATOR ALLOW-SINGLE-VALUE-INTERVAL
Package

interval

Source

tree.lisp (file)

Function: copy-interval INSTANCE
Package

interval

Source

interval.lisp (file)

Function: copy-node INSTANCE
Package

interval

Source

tree.lisp (file)

Function: interval-intersects V<-FUN I1 I2
Package

interval

Source

interval.lisp (file)

Function: interval-p OBJECT
Package

interval

Source

interval.lisp (file)

Function: make-node &key (LEVEL LEVEL) (LEFT LEFT) (RIGHT RIGHT) (VALUE VALUE) (MAX-END MAX-END)
Package

interval

Source

tree.lisp (file)

Function: node-decrease-level NODE
Package

interval

Source

tree.lisp (file)

Function: node-delete TREE NODE VALUE
Package

interval

Source

tree.lisp (file)

Function: node-dump NODE
Package

interval

Source

tree.lisp (file)

Function: node-find TREE NODE VALUE
Package

interval

Source

tree.lisp (file)

Function: node-find-all TREE NODE INTERVAL
Package

interval

Source

tree.lisp (file)

Function: node-find-any TREE NODE INTERVAL
Package

interval

Source

tree.lisp (file)

Function: node-in-range-p V<-FUN NODE INTERVAL
Package

interval

Source

tree.lisp (file)

Function: node-insert TREE NODE VALUE
Package

interval

Source

tree.lisp (file)

Function: node-leaf-p NODE
Package

interval

Source

tree.lisp (file)

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

interval

Source

tree.lisp (file)

Function: node-left-level-p NODE
Package

interval

Source

tree.lisp (file)

Function: node-leftmost-child NODE
Package

interval

Source

tree.lisp (file)

Function: node-level INSTANCE
Function: (setf node-level) VALUE INSTANCE
Package

interval

Source

tree.lisp (file)

Function: node-max-end INSTANCE
Function: (setf node-max-end) VALUE INSTANCE
Package

interval

Source

tree.lisp (file)

Function: node-p OBJECT
Package

interval

Source

tree.lisp (file)

Function: node-predecessor NODE
Package

interval

Source

tree.lisp (file)

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

interval

Source

tree.lisp (file)

Function: node-rightmost-child NODE
Package

interval

Source

tree.lisp (file)

Function: node-skew TREE NODE
Package

interval

Source

tree.lisp (file)

Function: node-split TREE NODE
Package

interval

Source

tree.lisp (file)

Function: node-strictly-greater-p V<-FUN NODE INTERVAL
Package

interval

Source

tree.lisp (file)

Function: node-successor NODE
Package

interval

Source

tree.lisp (file)

Function: node-two-rights-level-p NODE
Package

interval

Source

tree.lisp (file)

Function: node-update-max TREE NODE
Package

interval

Source

tree.lisp (file)

Function: node-validate NODE &optional PREV
Package

interval

Source

tree.lisp (file)

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

interval

Source

tree.lisp (file)

Function: tree-p OBJECT
Package

interval

Source

tree.lisp (file)

Function: tree-root INSTANCE
Function: (setf tree-root) VALUE INSTANCE
Package

interval

Source

tree.lisp (file)


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

5.2.3 Structures

Structure: node ()
Package

interval

Source

tree.lisp (file)

Direct superclasses

structure-object (structure)

Direct methods

print-object (method)

Direct slots
Slot: level
Type

(unsigned-byte 16)

Initform

0

Readers

node-level (function)

Writers

(setf node-level) (function)

Slot: left
Type

(or null interval::node)

Readers

node-left (function)

Writers

(setf node-left) (function)

Slot: right
Type

(or null interval::node)

Readers

node-right (function)

Writers

(setf node-right) (function)

Slot: value
Type

interval:interval

Readers

node-value (function)

Writers

(setf node-value) (function)

Slot: max-end
Readers

node-max-end (function)

Writers

(setf node-max-end) (function)


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

Appendix A Indexes


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

A.1 Concepts

Jump to:   C   F   L  
Index Entry  Section

C
cl-interval.asd: The cl-interval․asd file
cl-interval/interval.lisp: The cl-interval/interval․lisp file
cl-interval/package.lisp: The cl-interval/package․lisp file
cl-interval/tree.lisp: The cl-interval/tree․lisp file

F
File, Lisp, cl-interval.asd: The cl-interval․asd file
File, Lisp, cl-interval/interval.lisp: The cl-interval/interval․lisp file
File, Lisp, cl-interval/package.lisp: The cl-interval/package․lisp file
File, Lisp, cl-interval/tree.lisp: The cl-interval/tree․lisp file

L
Lisp File, cl-interval.asd: The cl-interval․asd file
Lisp File, cl-interval/interval.lisp: The cl-interval/interval․lisp file
Lisp File, cl-interval/package.lisp: The cl-interval/package․lisp file
Lisp File, cl-interval/tree.lisp: The cl-interval/tree․lisp file

Jump to:   C   F   L  

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

A.2 Functions

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

%
%copy-tree: Internal functions
%make-tree: Internal functions

(
(setf interval-end): Exported functions
(setf interval-start): Exported functions
(setf node-left): Internal functions
(setf node-level): Internal functions
(setf node-max-end): Internal functions
(setf node-right): Internal functions
(setf node-value): Internal functions
(setf tree-root): Internal functions

C
coerce-interval-designator: Internal functions
copy-interval: Internal functions
copy-node: Internal functions

D
delete: Exported functions

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

I
if-node-fun: Internal macros
insert: Exported functions
interval-end: Exported functions
interval-intersects: Internal functions
interval-p: Internal functions
interval-start: Exported functions
interval<: Exported functions
interval=: Exported functions

M
Macro, if-node-fun: Internal macros
make-interval: Exported functions
make-node: Internal functions
make-tree: Exported functions

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

T
tree-beforep: Exported functions
tree-dump: Exported functions
tree-equalp: Exported functions
tree-p: Internal functions
tree-root: Internal functions
tree-validate: Exported functions
tree-value-before-p: Exported functions

Jump to:   %   (  
C   D   F   I   M   N   T  

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

A.3 Variables

Jump to:   B   E   L   M   R   S   V  
Index Entry  Section

B
beforep: Exported structures

E
end: Exported structures
equalp: Exported structures

L
left: Internal structures
level: Internal structures

M
max-end: Internal structures

R
right: Internal structures
root: Exported structures

S
Slot, beforep: Exported structures
Slot, end: Exported structures
Slot, equalp: Exported structures
Slot, left: Internal structures
Slot, level: Internal structures
Slot, max-end: Internal structures
Slot, right: Internal structures
Slot, root: Exported structures
Slot, start: Exported structures
Slot, value: Internal structures
Slot, value-before-p: Exported structures
start: Exported structures

V
value: Internal structures
value-before-p: Exported structures

Jump to:   B   E   L   M   R   S   V  

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

A.4 Data types

Jump to:   C   I   N   P   S   T  
Index Entry  Section

C
cl-interval: The cl-interval system

I
interval: The interval package
interval: Exported structures

N
node: Internal structures

P
Package, interval: The interval package

S
Structure, interval: Exported structures
Structure, node: Internal structures
Structure, tree: Exported structures
System, cl-interval: The cl-interval system

T
tree: Exported structures

Jump to:   C   I   N   P   S   T