Up

Module Interval_map

Signature

include Interval_map_intf.M
include Interval_map_intf.Operations
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).

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

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"

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.

find (always ~comparator x) k = x

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.

find (map x ~f) k = f (find x k)

O(n).

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

Apply a function to values from two sequences.

find (map2 x y ~f) = f (find x k) (find y k)

O(n + m).

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

Flatten a sequence of sequences.

find (flatten x) k = find (find x k) k

O(sum(k)) where k is the size/number of changes of each inner sequence, of which there will be n.

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.

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

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_with_boundary (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