8.10
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:
Operations on interval-maps are not thread-safe.
Makes a new interval-map initialized with contents, which has the form
Examples:
Returns #t if v is an interval-map, #f
otherwise.
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.
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.
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).
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).
Removes the value associated with every position in [start,
end).
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.
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.
Same as the following:
Returns #t if v represents a position in an
interval-map, #f otherwise.