Next: Introduction, Previous: (dir), Up: (dir) [Contents][Index]
This is the cl-interval Reference Manual, generated automatically by Declt version 3.0 "Montgomery Scott" on Tue Dec 22 12:25:11 2020 GMT+0.
| • Introduction | What cl-interval is all about | |
| • Systems | The systems documentation | |
| • Files | The files documentation | |
| • Packages | The packages documentation | |
| • Definitions | The symbols documentation | |
| • Indexes | Concepts, functions, variables and data types |
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: Files, Previous: Introduction, Up: Top [Contents][Index]
The main system appears first, followed by any subsystem dependency.
| • The cl-interval system |
Ryan Pavlik
NewBSD, LLGPL
Intervals, interval trees
cl-interval.asd (file)
Files are sorted by type and then listed depth-first from the systems components trees.
| • Lisp files |
| • The cl-interval.asd file | ||
| • The cl-interval/package.lisp file | ||
| • The cl-interval/interval.lisp file | ||
| • The cl-interval/tree.lisp file |
Next: The cl-interval/package․lisp file, Previous: Lisp files, Up: Lisp files [Contents][Index]
cl-interval.asd
cl-interval (system)
Next: The cl-interval/interval․lisp file, Previous: The cl-interval․asd file, Up: Lisp files [Contents][Index]
cl-interval (system)
package.lisp
Next: The cl-interval/tree․lisp file, Previous: The cl-interval/package․lisp file, Up: Lisp files [Contents][Index]
package.lisp (file)
cl-interval (system)
interval.lisp
Previous: The cl-interval/interval․lisp file, Up: Lisp files [Contents][Index]
interval.lisp (file)
cl-interval (system)
tree.lisp
Next: Definitions, Previous: Files, Up: Top [Contents][Index]
Packages are listed by definition order.
| • The interval package |
package.lisp (file)
common-lisp
Definitions are sorted by export status, category, package, and then by lexicographic order.
| • Exported definitions | ||
| • Internal definitions |
Next: Internal definitions, Previous: Definitions, Up: Definitions [Contents][Index]
| • Exported functions | ||
| • Exported structures |
Next: Exported structures, Previous: Exported definitions, Up: Exported definitions [Contents][Index]
=> 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)‘.
=> 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)‘.
=> 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).
=> 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).
=> 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.
=> end
Return the ‘END‘ value of the interval.
interval.lisp (file)
(setf interval-end) (function)
interval.lisp (file)
interval-end (function)
=> start
Return the ‘START‘ value of the interval.
interval.lisp (file)
(setf interval-start) (function)
interval.lisp (file)
interval-start (function)
=> boolean
A simple example (also used in tests) which compares interval starts
numerically by ‘#’<‘.
interval.lisp (file)
=> boolean
A simple example (also used in tests) which compares interval equality
numerically by ‘#’=‘.
interval.lisp (file)
=> INTERVAL
Returns a simple interval with specified ‘START‘ and ‘END‘.
interval.lisp (file)
=> 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.
=> FUNCTION
Return the function used to compare *intervals*. It should return
whether one interval ‘START‘ comes before another interval ‘START‘.
=> list
Return a tree dumped into a list form. This is currently only useful for
testing.
=> 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‘).
=> 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.
=> 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.
Previous: Exported functions, Up: Exported definitions [Contents][Index]
interval.lisp (file)
structure-object (structure)
print-object (method)
interval-start (function)
(setf interval-start) (function)
interval-end (function)
(setf interval-end) (function)
tree.lisp (file)
structure-object (structure)
(or null interval::node)
tree-root (function)
(setf tree-root) (function)
function
tree-beforep (function)
(setf tree-beforep) (function)
function
tree-equalp (function)
(setf tree-equalp) (function)
function
tree-value-before-p (function)
(setf tree-value-before-p) (function)
Previous: Exported definitions, Up: Definitions [Contents][Index]
| • Internal macros | ||
| • Internal functions | ||
| • Internal structures |
Next: Internal functions, Previous: Internal definitions, Up: Internal definitions [Contents][Index]
Next: Internal structures, Previous: Internal macros, Up: Internal definitions [Contents][Index]
interval.lisp (file)
interval.lisp (file)
interval.lisp (file)
Previous: Internal functions, Up: Internal definitions [Contents][Index]
tree.lisp (file)
structure-object (structure)
print-object (method)
(unsigned-byte 16)
0
node-level (function)
(setf node-level) (function)
(or null interval::node)
node-left (function)
(setf node-left) (function)
(or null interval::node)
node-right (function)
(setf node-right) (function)
interval:interval
node-value (function)
(setf node-value) (function)
node-max-end (function)
(setf node-max-end) (function)
Previous: Definitions, Up: Top [Contents][Index]
| • Concept index | ||
| • Function index | ||
| • Variable index | ||
| • Data type index |
Next: Function index, Previous: Indexes, Up: Indexes [Contents][Index]
| Jump to: | C F L |
|---|
| Jump to: | C F L |
|---|
Next: Variable index, Previous: Concept index, Up: Indexes [Contents][Index]
| Jump to: | %
(
C D F I M N T |
|---|
| Jump to: | %
(
C D F I M N T |
|---|
Next: Data type index, Previous: Function index, Up: Indexes [Contents][Index]
| Jump to: | B E L M R S V |
|---|
| Jump to: | B E L M R S V |
|---|
Previous: Variable index, Up: Indexes [Contents][Index]
| Jump to: | C I N P S T |
|---|
| Jump to: | C I N P S T |
|---|