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:

- Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L. (1990). Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill. ISBN 0-262-03141-8.

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

Plain numeric intervals are not terribly useful on their own. Thus,
intervals are represented in the structure `interval:interval`

, which
you can extend as you please:

`(`*defstruct* (my-interval (:include interval:interval))

my-data)

(*defun* my-interval< (i1 i2)

(char< (interval:interval-start i1) (interval:interval-start i2)))

(*defun* my-interval= (i1 i2)

(and (char= (interval:interval-start i1) (interval:interval-start i2))

(char= (interval:interval-end i1) (interval:interval-end i2))))

(setf *mytree* (interval:make-tree :interval-before-p #'my-interval<

:interval-equal-p #'my-interval=

:value-before-p #'char<=))

(interval:insert *mytree* (make-my-interval :start #\a :end #\c))

(interval:insert *mytree* (make-my-interval :start #\b :end #\m))

(interval:find *mytree* '(#\a . #\c))

;; => (#<a-c>)

(interval:find-all *mytree* #\b)

;; => (#<a-c> #<b-m>)

(setf (my-interval-my-data (interval:find *mytree* '(#\a . #\c)))

"something useful for later retrieval")

(mapcar #'my-interval-my-data

(interval:find-all *mytree* #\b))

;; => ("something useful for later retrieval" NIL)

As you can see in this example, we've made a new interval which compares alphabetically, and where we can attach data.

One thing of note is that `INTERVAL:INTERVAL-START`

and
`INTERVAL:INTERVAL-END`

are used instead of `MY-INTERVAL-START`

and
`MY-INTERVAL-END`

. This is not strictly necessary; however, you will
not be able to search or delete based on "plain" intervals, or use the
`(START . END)`

or single-value syntax.

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)
```

.

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)
```

.

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).

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.

INTERVAL-END

(SB-KERNEL:INSTANCE)

=> end

Return the `END`

value of the interval.

INTERVAL-START

(SB-KERNEL:INSTANCE)

=> start

Return the `START`

value of the interval.

INTERVAL<

(I1 I2)

=> boolean

A simple example (also used in tests) which compares interval starts
numerically by `#'<`

.

INTERVAL=

(I1 I2)

=> boolean

A simple example (also used in tests) which compares interval equality
numerically by `#'=`

.

MAKE-INTERVAL

(&KEY ((:START #:DUM0) NIL) ((:END #:DUM1) NIL))

=> INTERVAL

Returns a simple interval with specified `START`

and `END`

.

MAKE-TREE

(&KEY (INTERVAL-BEFORE-P 'INTERVAL<) (INTERVAL-EQUAL-P 'INTERVAL=)
(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.

TREE-BEFOREP

(SB-KERNEL:INSTANCE)

=> FUNCTION

Return the function used to compare *intervals*. It should return
whether one interval `START`

comes before another interval `START`

.

TREE-DUMP

(TREE)

=> list

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

TREE-EQUALP

(SB-KERNEL: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`

).

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.

TREE-VALUE-BEFORE-P

(SB-KERNEL: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.