Common Lisp interval tables with fast search for all intervals containing a point or intersecting an interval.

Construct a new interval table given a comparison predicate for interval bounds:

(defvar *table* (make-interval-table #'<))

Put in some values:

(setf (get-interval 1 10 *table*) "E1")
(setf (get-interval 11 20 *table*) "E2")
(setf (get-interval 5 15 *table*) "E3")
(setf (get-interval 0 2 *table*) "E4")
(setf (get-interval 5 15 *table*) "E5")   ; will overwrite "E3"

Getting the size and checking if a table is empty:

(interval-table-count *table*) => 4
(interval-table-empty-p *table*) => nil

Look up intervals:

(get-interval 5 15 *table*) => "E5", t
(get-interval 1 4 *table*) => nil, nil
(get-interval 1 4 *table* "Nope") => "Nope", nil

Search for intervals containing a point or intersecting a given interval with map-intervals:

(map-intervals 'list #'list *table* :containing 9)
    => ((1 10 "E1") (5 15 "E5"))
(map-intervals 'vector #'(lambda (lo hi val) val) *table* :intersecting '(13 50))
    => #("E5" "E2")

Or you can use do-intervals:

(do-intervals (((lo hi) value) *table* :containing 0)
  (format t "~A~%" value))

will print

E4

Both map-intervals and do-intervals process the entries in ascending order. You can use :from-end t to use descending order instead. If you do not use :containing or :intersecting, all intervals in the table will be processed:

(defun arg3 (a b c) (declare (ignore a b)) c)
(map-intervals 'list #'arg3 *table*) => ("E4" "E1" "E5" "E2")
(map-intervals 'list #'arg3 *table* :from-end t) => ("E2" "E5" "E1" "E4")

As the table is sorted by the intervals, there are also the functions get-min and get-max to get the lowest / highest interval, and delete-min to delete and return the lowest interval from the table:

(get-min *table*) => 0, 2, "E4"
(delete-min *table*) => 0, 2, "E4"
(get-min *table*) => 1, 10, "E1"

A sorted table of non-empty intervals to values.

Predicate for interval-table.

(make-interval-table less &key (bounds :closed) initial-contents initial-contents*)

Create a new interval table.

• less must be a binary predicate that defines a strict total ordering on the set of interval bounds.
• bounds must be one of :closed, :open, :closed-open, :open-closed. Defaults to :closed.
• initial-contents is a list of (lo hi value) lists that become the initial elements of the table.
• initial-contents* is a list of (lo hi . value) dotted lists that become the initial elements of the table.

(interval-table-bounds table)

Returns the bounds type of table.

(interval-table-count table)

The number of entries in table. O(n).

(interval-table-empty-p table)

Is table empty? O(1).

(get-interval lo hi table &optional default)

Look up the interval with bounds lo, hi in table. If table contains the interval, return its value and true.
If not, return default and false. O(log n).

(get-min table)
(get-max table)

Get the minimum/maximum interval in TABLE.
Return three values: lower bound, upper bound, value.
If the table is empty, return three nil values.
O(log n).

Get the maximum interval in the table.
Return three values: lower bound, upper bound, value.
If the table is empty, return three nil values.
O(log n).

Set value for an interval in the table.

(delete-interval lo hi table)

Delete the entry for interval lo, hi in table, if any.
Returns the entry's value and true if there was such an entry, or nil and false otherwise.
O(log n).

(delete-min table)
(delete-max table)

Delete the minimum/maximum interval from table.
Return the deleted interval as three values: lower bound, upper bound, value.
If the table is empty, return three nil values.
O(log n).

(do-intervals ((lower upper value) table &rest options) &body body)
(do-intervals ((lower upper) table &rest options) &body body)
(do-intervals (value table &rest options) &body body)

Iterate over the entries in table. options may be the same keyword arguments as in map-intervals.

(map-intervals result-type function table &key containing intersecting above below from-end)

Map function over entries of table.

• result-type gives the type of the result sequence, as in the standard function map.
• function is called for each entry with three arguments: the lower bound, upper bound, value.
• Entries are processed in order. If from-end is true, they are processed in reverse order.
• The entries to include are selected by one of the following keyword arguments:
  • :CONTAINING POINT -- all intervals containing POINT
  • :INTERSECTING (LO HI) -- all intervals intersecting LO, HI
  • :ABOVE POINT -- all intervals with lower bound > point
  • :BELOW POINT -- all intervals with upper bound < point
• Only one of :CONTAINING, :INTERSECTING, or :ABOVE+:BELOW may be used.

(map-values function table)

Update all values in table by the result of calling function with the lower bound, upper bound, and value.

(subtable table &key containing intersecting above below)

Create a new interval table containing a subset of the entries in table. Keyword arguments have the same meaning as in map-intervals.

(every-interval predicate table)

Check that predicate is true for each interval in TABLE.
predicated is called with three arguments: lower bound, upper bound, value.

(some-interval predicate table &key from-end)

Return the first non-nil result from predicate applied to the elements of table.
predicate is called with three arguments: lower bound, upper bound, value.
If from-end is true, entries are processed in reverse order.