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.

Extending Intervals

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.

Reference: INTERVAL

Functions

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.