6 Interval Maps

8.15

6 Interval Maps🔗ℹ

An interval-map is a mutable data structure that maps half-open intervals of exact integers to values. An interval-map is queried at a discrete point, and the result of the query is the value mapped to the interval containing the point.

Internally, interval-maps use a skip-list (data/skip-list) of intervals for efficient query and update, including efficient contraction and expansion of intervals.

Interval-maps implement the dictionary (racket/dict) interface to a limited extent. Only dict-ref and the iteration-based methods (dict-iterate-first, dict-map, etc) are supported. For the iteration-based methods, the mapping’s keys are considered the pairs of the start and end positions of the mapping’s (half-open) intervals.

Examples:

> (define r (make-interval-map))
> (interval-map-set! r 1 5 'apple)
> (interval-map-set! r 6 10 'pear)
> (interval-map-set! r 3 7 'banana)
> r
(make-interval-map '(((1 . 3) . apple) ((3 . 7) . banana) ((7 . 10) . pear)))
> (interval-map-ref r 1 #f)
'apple
> (interval-map-ref r 3 #f)
'banana
> (interval-map-ref r 10 #f)
#f

Operations on interval-maps are not thread-safe.

procedure
(make-interval-map [ contents
#:key-contract key-contract
#:value-contract value-contract])
→ interval-map?
   contents : (listof (cons/c (cons/c exact-integer? exact-integer?) any/c))
= null
  key-contract : contract? = any/c
  value-contract : contract? = any/c

Makes a new interval-map initialized with contents, which has the form

(list (cons (cons start end) value) ...)

Examples:

> (define r (make-interval-map '(((0 . 5) . apple) ((5 . 10) . banana))))
> (interval-map-ref r 2)
'apple
> (interval-map-ref r 5)
'banana

procedure
(interval-map? v) → boolean?
v : any/c

Returns #t if v is an interval-map, #f otherwise.

procedure
(interval-map-ref interval-map
position
[ default]) → any/c
  interval-map : interval-map?
  position : exact-integer?
  default : any/c = (lambda () (error ....))

Return the value associated with position in interval-map. If no mapping is found, default is applied if it is a procedure, or returned otherwise.

Added in version 1.1 of package data-lib.

procedure
(interval-map-ref/bounds interval-map
position
[ default])
→
(or/c #f exact-integer?)
(or/c #f exact-integer?)
any/c
  interval-map : interval-map?
  position : exact-integer?
  default : any/c = (lambda () (error ....))

Like interval-map-ref, but also returns the bounds of the interval associated with position. If no mapping is found and default is a procedure, it is applied. If no mapping is found and default is not a procedure, #f is returned for the start and end positions and default is returned as the value.

procedure
(interval-map-set! interval-map
start
end
value) → void?
  interval-map : interval-map?
  start : exact-integer?
  end : exact-integer?
  value : any/c

Updates interval-map, associating every position in [start, end) with value.

Existing interval mappings contained in [start, end) are destroyed, and partly overlapping intervals are truncated. See interval-map-update*! for an updating procedure that preserves distinctions within [start, end).

procedure
(interval-map-update*! interval-map
start
end
updater
[ default]) → void?
  interval-map : interval-map?
  start : exact-integer?
  end : exact-integer?
  updater : (-> any/c any/c)
  default : any/c = (lambda () (error ....))

Updates interval-map, associating every position in [start, end) with the result of applying updater to the position’s previously associated value, or to the default value produced by default if no mapping exists.

Unlike interval-map-set!, interval-map-update*! preserves existing distinctions within [start, end).

procedure
(interval-map-remove! interval-map
start
end) → void?
  interval-map : interval-map?
  start : (or/c exact-integer? -inf.0)
  end : (or/c exact-integer? +inf.0)

Removes the value associated with every position in [start, end).

procedure
(interval-map-contract! interval-map
start
end) → void?
  interval-map : interval-map?
  start : exact-integer?
  end : exact-integer?

Contracts interval-map’s domain by removing all mappings on the interval [start, end) and decreasing intervals initally after end by (- end start).

If start is not less than end, an exception is raised.

procedure
(interval-map-expand! interval-map
start
end) → void?
  interval-map : interval-map?
  start : exact-integer?
  end : exact-integer?

Expands interval-map’s domain by introducing a gap [start, end) and increasing intervals starting at or after start by (- end start).

If start is not less than end, an exception is raised.

procedure
(interval-map-cons*! interval-map
start
end
v
[ default]) → void?
  interval-map : interval-map?
  start : any/c
  end : any/c
  v : any/c
  default : any/c = null

Same as the following:

(interval-map-update*! interval-map start end
(lambda (old) (cons v old))
default)

procedure
(interval-map-iterate-first interval-map)
→ (or/c interval-map-iter? #f)
  interval-map : interval-map?
procedure
(interval-map-iterate-next interval-map
iter)
→ (or/c interval-map-iter? #f)
  interval-map : interval-map?
  iter : interval-map-iter?
procedure
(interval-map-iterate-key interval-map
iter) → pair?
  interval-map : interval-map?
  iter : interval-map-iter?
procedure
(interval-map-iterate-value interval-map
iter) → any
  interval-map : interval-map?
  iter : interval-map-iter?

Implementations of dict-iterate-first, dict-iterate-next, dict-iterate-key, and dict-iterate-value, respectively.

procedure
(interval-map-iterate-least interval-map)
→ (or/c interval-map-iter? #f)
interval-map : interval-map?
procedure
(interval-map-iterate-greatest interval-map)
→ (or/c interval-map-iter? #f)
interval-map : interval-map?

Like dict-iterate-least and dict-iterate-greatest, respectively, though interval maps do not implement the gen:ordered-dict interface.

Added in version 1.2 of package data-lib.

procedure
(interval-map-iterate-least/start>? interval-map
start)
→ (or/c interval-map-iter? #f)
  interval-map : interval-map?
  start : exact-integer?
procedure
(interval-map-iterate-least/start>=? interval-map
start)
→ (or/c interval-map-iter? #f)
  interval-map : interval-map?
  start : exact-integer?
procedure
(interval-map-iterate-greatest/start<? interval-map
start)
→ (or/c interval-map-iter? #f)
  interval-map : interval-map?
  start : exact-integer?
procedure
(interval-map-iterate-greatest/start<=? interval-map
start)
→ (or/c interval-map-iter? #f)
  interval-map : interval-map?
  start : exact-integer?
procedure
(interval-map-iterate-least/end>? interval-map
end)
→ (or/c interval-map-iter? #f)
  interval-map : interval-map?
  end : exact-integer?
procedure
(interval-map-iterate-least/end>=? interval-map
end)
→ (or/c interval-map-iter? #f)
  interval-map : interval-map?
  end : exact-integer?
procedure
(interval-map-iterate-greatest/end<? interval-map
end)
→ (or/c interval-map-iter? #f)
  interval-map : interval-map?
  end : exact-integer?
procedure
(interval-map-iterate-greatest/end<=? interval-map
end)
→ (or/c interval-map-iter? #f)
  interval-map : interval-map?
  end : exact-integer?

Like dict-iterate-least/>?, dict-iterate-least/>=?, dict-iterate-greatest/<?, and dict-iterate-greatest/<=?, but each function comes in a start and an end variant corresponding to the start or end of each interval, respectively.

Note that interval maps do not implement the gen:ordered-dict interface, as these operations accept individual bounds rather than the pairs returned by interval-map-iterate-key. Therefore, these operations must be used directly.

Added in version 1.2 of package data-lib.

procedure
(interval-map-iter? v) → boolean?
v : any/c

Returns #t if v represents a position in an interval-map, #f otherwise.

1	Imperative Queues
2	Growable Vectors
3	Orders and Ordered Dictionaries
4	Splay Trees
5	Skip Lists
6	Interval Maps
7	Binary Heaps
8	Integer Sets
9	Bit Vectors
10	Union-Find: Sets with only Canonical Elements
11	Enumerations
	Bibliography