module type M =sig
..end
type ('k, +'v, 'cmp)
t
val compare : ('v -> 'v -> int) ->
('k, 'v, 'cmp) t ->
('k, 'v, 'cmp) t -> int
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);
val create : left_of_leftmost:'v ->
value_right_of:('k, 'v, 'cmp) Core_kernel.Std.Map.t ->
('k, 'v, 'cmp) t
O(1).
val always : 'v ->
comparator:('k, 'cmp) Core_kernel.Std.Comparator.t ->
('k, 'v, 'cmp) t
O(1).
val find : ('k, 'v, 'cmp) t -> 'k -> 'v
O(log n).
val change : ('k, 'v, 'cmp) t ->
at:'k -> 'v -> ('k, 'v, 'cmp) t
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).
val map : ('k, 'a, 'cmp) t ->
f:('a -> 'b) -> ('k, 'b, 'cmp) t
O(n).
val map2 : ('k, 'a, 'cmp) t ->
('k, 'b, 'cmp) t ->
f:('a -> 'b -> 'c) -> ('k, 'c, 'cmp) t
O(n + m).
val remove_changes_within : ('k, 'v, 'cmp) t ->
'k Interval_map_intf.Interval.t -> ('k, 'v, 'cmp) t
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).
val set_within : ('k, 'v, 'cmp) t ->
'k Interval_map_intf.Interval.t -> 'v -> ('k, 'v, 'cmp) t
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.
Complexity is O(log(n) + n'), where n' is the number of change points
within the specified interval (not the whole sequence).
val map_within : ('k, 'v, 'cmp) t ->
'k Interval_map_intf.Interval.t ->
f:('v -> 'v) -> ('k, 'v, 'cmp) t
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).
val construct_preimage : ('k, 'v, 'cmp) t ->
('v * 'k Interval_map_intf.Interval.t) Core_kernel.Std.Sequence.t
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)];
module Make:functor (
T
:
Interval_map_intf.Type_with_map_module
) ->
Interval_map_intf.S
with type Key.t = T.Map.Key.t and type Key.comparator_witness = T.Map.Key.comparator_witness and type ('k, 'v, 'cmp) interval_map := ('k, 'v, 'cmp) t
module Make_with_boundary:functor (
Key
:
Interval_map_intf.Key
) ->
Interval_map_intf.S_with_boundary
with type key := Key.t and type ('k, 'v, 'cmp) interval_map := ('k, 'v, 'cmp) t