Module Core_extended.Interval_map

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

Apply a function to all values within the sequence.

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

O(n).

Apply a function to values from two sequences.

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

O(n + m).

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.

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