5.3.4
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 splay-tree
(data/splay-tree) 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 intervals.
Operations on interval-maps are not thread-safe.
Makes a new empty interval-map.
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.
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 initially 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.