The core operations of interval maps.
Note on complexities: As the mappings are for ranges, where complexities are given they are given in terms of variables (n, m) which are the number of change points that have been inserted into the sequence.
Comparison works lexicographically pointwise across the whole sequence (from -infty to +infty).
This means that x = y ⇔ (∀k. find x k = find y k)
.
Complexity is O(n + m).
Note that this is a normalising comparison (a change point which changes
the value to the same value is treated as if it does not exist), which means
that it is not entirely extensional. In particular, two equal sequences may
be distinguished by converting to sexps or using construct_preimage
, both
of which do not perform normalisation. In example:
let module Int_interval_map = Interval_map.Make(Int) in
let compare = Int_interval_map.compare Int.compare in
let sexp_of_t = Int_interval_map.sexp_of_t Int.sexp_of_t in
let list_preimage t =
Sequence.to_list (Int_interval_map.construct_preimage t)
in
let x = Int_interval_map.always 42 in
let y = Int_interval_map.change x ~at:0 42 in
assert (compare x y = 0);
assert (sexp_of_t x <> sexp_of_t y);
assert (list_preimage x <> list_preimage y);
Create a sequence with a specified far-leftmost value, and sequence of change points.
Complexity is O(1), as the primary cost is in construction of the map which is passed into this function.
e.g. suppose that
let x = create ~left_of_leftmost:"A"
~value_right_of:Int.Map.of_alist_exn [
0, "B"; 2, "C"; 4, "D"; ]
Then x
will be an interval map such that:
∀ k < 0. find x k = "A"
∀ 0 <= k < 2. find x k = "B"
∀ 2 <= k < 4. find x k = "C"
∀ 4 <= k . find x k = "D"
Create a sequence which has a single constant value across the whole sequence of keys.
find (always ~comparator x) k = x
O(1).
Find the value associated with some point along the sequence of keys.
O(log n).
Insert a change point into the sequence of changes.
The precise effect on the values along the sequence depends on what other change points are present, notionally inserting a change point means the value prior to this point is unchanged, then at this point the value becomes the supplied value, and then continues to be that value until the next change point which had already been inserted.
If you want to control values directly within bounded intervals,
set_within
may be simpler to use.
O(log n).
remove_changes_within t interval
removes any change points within
the specified interval.
By removing these points of change, the value within the interval will become whatever the value already was outside the left-boundary of the interval.
Some intervals are open on the left (e.g. `Always
or `Until k
),
and in these cases the value in the interval will become t.left_of_leftmost
.
Complexity is O(log(n) + n'), where n' is the number of change points within the specified interval (not the whole sequence).
set_within t interval v
modifies the sequence so that all values
within the specified interval are v
, and values outside the interval
are not modified.
find (set_within t interval x) k =
(if Interval.contains interval k then x else find t k)
Complexity is O(log(n) + n'), where n' is the number of change points within the specified interval (not the whole sequence).
map_within t interval ~f
modifies the sequence similarly to set_within,
except that it applies a function to the range rather than a constant value
(i.e. map_within t interval ~f:(Fn.const x) = set_within t interval x
).
Complexity is O(log(n) + n'), where n' is the number of change points within the specified interval (not the whole sequence).
Construct a preimage of the sequence. This is a series of pairs of a value and an interval of keys within which the sequence has that value.
O(n).
Importantly note that: 1) A particular value may be output many times with different intervals. 2) Each interval output will be unique and not overlap with any other. 3) As noted above, this is one of the areas where extensionality breaks down.
In example of the last point:
let x = Int_interval_map.always 42 in
let y = Int_interval_map.change x ~at:0 42 in
let list_preimage t =
Sequence.to_list (Int_interval_map.construct_preimage t)
in
assert (list_preimage x = [(42, `Always)]);
assert (list_preimage y = [(42, `Until 0); (42, `From 0)];