Version: 5.0
22 Interval Maps
This library is
unstable;
compatibility will not be maintained.
See
Unstable for more information.
An interval-map is a mutable dictionary-like data structure where
mappings are added by half-open intervals and queried by
discrete points. Interval-maps can be used with any total
order. Internally, an interval-map uses a skip-list
(unstable/skip-list) of intervals for efficient query
and update.
Interval-maps implement the dictionary (racket/dict)
interface to a limited extent. Only dict-ref and the
iteraction-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.
Makes a new empty interval-map. The interval-map uses =? and
<? to order the endpoints of intervals.
If translate is a procedure, the interval-map supports
contraction and expansion of regions of its domain via
interval-map-contract! and interval-map-expand!. See
also make-numeric-interval-map.
Makes a new empty interval-map suitable for representing numeric
ranges.
Equivalent to
Returns #t if v is an interval-map, #f
otherwise.
Returns #t if v is an interval-map constructed with
support for translation of keys, #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).
Expands interval-map’s domain by introducing a gap
[start, end) and adjusting intervals after
start using (translate start end).
If interval-map was not constructed with a
translate argument, an exception is raised. If
start is not less than end, an exception is raised.
Contracts interval-map’s domain by removing all mappings on
the interval [start, end) and adjusting intervals
after end using (translate end start).
If interval-map was not constructed with a
translate argument, an exception is raised. 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.