# Module type Interval_map_intf.M

    module type M = sig .. end

    type ('k, +'v, 'cmp) t

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.

    val compare : ('v -> 'v -> int) ->
           ('k, 'v, 'cmp) t ->
           ('k, 'v, 'cmp) t -> int

Comparison works lexicographically pointwise across the whole sequence (from -infty to +infty).

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

Create a sequence with a specified far-leftmost value, and sequence of change points.

O(1).

    val always : 'v ->
           comparator:('k, 'cmp) Core_kernel.Std.Comparator.t ->
           ('k, 'v, 'cmp) t

Create a sequence which has a single constant value across the whole sequence of keys.

O(1).

    val find : ('k, 'v, 'cmp) t -> 'k -> 'v

Find the value associated with some point along the sequence of keys.

O(log n).

    val change : ('k, 'v, 'cmp) t ->
           at:'k -> 'v -> ('k, 'v, 'cmp) t

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).

    val map : ('k, 'a, 'cmp) t ->
           f:('a -> 'b) -> ('k, 'b, 'cmp) t

Apply a function to all values within the sequence.

O(n).

    val map2 : ('k, 'a, 'cmp) t ->
           ('k, 'b, 'cmp) t ->
           f:('a -> 'b -> 'c) -> ('k, 'c, 'cmp) t

Create a sequence whose value at all points is taken by applying a function to the values of two other sequences at that point.

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

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)];

    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