interval
A total partition of domain D into maximal contiguous half-open runs, each carrying a value of type T.
Generated from spec/std/interval.cp by cpl doc --format json.
IntervalMap
pub struct IntervalMap<D, T>A total partition of domain D into maximal contiguous half-open runs,
each carrying a value of type T.
Adjacent runs always have distinct values (== runs coalesce automatically).
new is O(1); from is O(D.K); at, run_at, and assign_point are
O(log runs); assign is amortized O((1 + overwritten) log runs);
each is O(runs); runs is O(1).
IntervalMap.new
fn new(init: T) -> IntervalMap<D, T>A map that gives every position of D the value init: one run, or None when D is empty.
- cost: O(1)
- empty: an empty
Dgives zero runs - traps: never
Examples:
IntervalMap<0..5, Int>(0).runs == 1
IntervalMap.from
fn from(a: [D]T) -> IntervalMap<D, T>The map holding a[i] at every position i, stored as maximal runs of equal values.
- cost: O(|D|)
- empty: an empty
agives zero runs - order: positions keep the domain
Dofa - traps: never
Examples:
IntervalMap.from([1, 1, 2]).runs == 2
IntervalMap.runs
fn runs(self) -> IntThe number of maximal runs, i.e. one more than the number of adjacent positions whose
values differ (zero for an empty D).
- cost: O(1)
- traps: never
Examples:
IntervalMap.from([1, 2, 2, 1]).runs == 3
IntervalMap.get
fn get(self, i: D) -> TThe value at position i.
- cost: O(log runs)
- traps: when
iis outsideD
Examples:
IntervalMap.from([1, 1, 2]).get(2) == 2
IntervalMap.run_at
fn run_at(self, i: D) -> (range: Range<D>, val: T)The maximal run containing position i and its value.
- cost: O(log runs)
- order: the run's positions in ascending order
- traps: when
iis outsideD
Examples:
IntervalMap.from([1, 1, 2]).run_at(1).range == 0..2IntervalMap.from([1, 1, 2]).run_at(1).val == 1
IntervalMap.assign
fn assign(mut self, r: Range<D>, val: T, on_old: (Range<D>, T) -> () = (_, _) => ())Give every position of r the value val, then merge it with equal neighbouring runs so all
runs stay maximal. on_old is called with each overwritten piece (an old run overlapping
r, clipped to r) and its old value; the map is fully repainted when assign returns.
- cost: O((1 + overwritten) log runs) amortized
- empty: changes nothing and calls
on_oldnever - order:
on_oldsees pieces in ascending positions - traps: when a non-empty
rreaches outsideD
Examples:
var m = IntervalMap<0..5, Int>(0); m.assign(1..3, 7); m.runs == 3var m = IntervalMap<0..5, Int>(0); m.assign(1..3, 7); m.assign(1..3, 0); m.runs == 1var m = IntervalMap.from([1, 1, 2, 2]); var old: List<Int> = []; m.assign(1..3, 9, on_old: (_, v) => old.push(v)); old == [1, 2]
IntervalMap.assign_point
fn assign_point(mut self, i: D, val: T) -> TGive position i the value val and return the value it had.
- cost: O(log runs)
- traps: when
iis outsideD
Examples:
var m = IntervalMap.from([1, 2]); m.assign_point(0, 5) == 1 and m.get(0) == 5
IntervalMap.each
fn each(self) -> yields (range: Range<D>, val: T)Every maximal run with its value.
- cost: O(1) per run
- empty: yields nothing for an empty
D - order: ascending positions
- traps: never
Examples:
IntervalMap.from([1, 1, 2]).each().map(p => p.val).collect() == [1, 2]
IntervalMap.set
fn set(mut self, i: D, val: T)Give position i the value val; assign_point without the old value, and the
write-through place for m[i] = val.
- cost: O(log runs)
- traps: when
iis outsideD
Examples:
var m = IntervalMap.from([1, 1]); m.set(1, 3); m.runs == 2
IntervalMap.range
fn range(self, r: Range<D>) -> yields (range: Range<D>, val: T)Every run overlapping r, clipped to r, with its value. Clipping can make the first and
last pieces shorter than their runs; they are not merged with anything.
- cost: O(log runs + k) for
kpieces - empty: yields nothing
- order: ascending positions
- traps: when a non-empty
rreaches outsideD
Examples:
IntervalMap.from([1, 1, 2]).range(1..3).map(p => p.range).collect() == [1..2, 2..3]
IntervalMap.each_rev
fn each_rev(self) -> yields (range: Range<D>, val: T)Every maximal run with its value, last first.
- cost: O(1) per run
- empty: yields nothing for an empty
D - order: descending positions
- traps: never
Examples:
IntervalMap.from([1, 1, 2]).each_rev().map(p => p.val).collect() == [2, 1]
IntervalMap.first_where
fn first_where(self, from: Cut<D>, ok: T -> Bool) -> ?DThe first position right of the cut from whose value satisfies ok, or None. Calls
ok once per run, not per position.
- cost: O(log runs + skipped) for
skippedruns that failok - ties: the first position in key order
- traps: never
Examples:
IntervalMap.from([1, 1, 2]).first_where((0..0).r, v => v == 2) == Some(2)IntervalMap.from([1, 1, 2]).first_where((0..1).r, v => v == 1) == Some(1)IntervalMap.from([1, 1, 2]).first_where((0..3).r, v => true) == None
IntervalSet
pub struct IntervalSet<D>O(runs) space. Dynamic union of disjoint maximal half-open intervals over domain D
(KACTL IntervalContainer). Maintains total covered length in O(1).
IntervalSet.new
fn new() -> IntervalSet<D>An empty set of positions of D.
- cost: O(1)
- traps: never
Examples:
IntervalSet<0..10>().covered == 0
IntervalSet.add
fn add(mut self, r: Range<D>)Add every position of r, merging runs that overlap or touch it into one maximal run.
- cost: O((1 + merged) log runs) amortized
- empty: changes nothing
- traps: when a non-empty
rreaches outsideD
Examples:
var s = IntervalSet<0..10>(); s.add(1..3); s.add(3..5); s.runs == 1 and s.covered == 4
IntervalSet.remove
fn remove(mut self, r: Range<D>)Remove every position of r; a run straddling an end of r is cut there.
- cost: O((1 + split) log runs) amortized
- empty: changes nothing
- traps: when a non-empty
rreaches outsideD
Examples:
var s = IntervalSet<0..10>(); s.add(0..5); s.remove(1..2); s.runs == 2 and s.covered == 4
IntervalSet.contains
fn contains(self, i: D) -> BoolWhether position i is in the set.
- cost: O(log runs)
- traps: when
iis outsideD
Examples:
var s = IntervalSet<0..10>(); s.add(2..4); s.contains(3) and not s.contains(4)
IntervalSet.contains_range
fn contains_range(self, r: Range<D>) -> BoolWhether every position of r is in the set, i.e. one run covers r.
- cost: O(log runs)
- empty:
true - traps: when a non-empty
rreaches outsideD
Examples:
var s = IntervalSet<0..10>(); s.add(2..4); s.add(4..6); s.contains_range(3..6) == truevar s = IntervalSet<0..10>(); s.add(2..4); s.contains_range(3..5) == false
IntervalSet.run_at
fn run_at(self, i: D) -> ?Range<D>The maximal run containing position i, or None when i is not in the set.
- cost: O(log runs)
- order: the run's positions in ascending order
- traps: when
iis outsideD
Examples:
var s = IntervalSet<0..10>(); s.add(2..4); s.run_at(3) == Some(2..4)var s = IntervalSet<0..10>(); s.add(2..4); s.run_at(4) == None
IntervalSet.next_covered
fn next_covered(self, from: D) -> ?DThe first position at or after from that is in the set, or None.
- cost: O(log runs)
- traps: when
fromis outsideD
Examples:
var s = IntervalSet<0..10>(); s.add(5..7); s.next_covered(2) == Some(5)var s = IntervalSet<0..10>(); s.add(5..7); s.next_covered(7) == None
IntervalSet.next_gap
fn next_gap(self, from: D) -> ?DThe first position at or after from that is not in the set (a dynamic mex), or None
when every position from from to the end of D is covered.
- cost: O(log runs)
- traps: when
fromis outsideD
Examples:
var s = IntervalSet<0..10>(); s.add(0..3); s.next_gap(1) == Some(3)var s = IntervalSet<0..10>(); s.add(5..10); s.next_gap(6) == None
IntervalSet.covered
fn covered(self) -> IntThe number of positions in the set.
- cost: O(1)
- traps: never
Examples:
var s = IntervalSet<0..10>(); s.add(1..3); s.add(6..7); s.covered == 3
IntervalSet.runs
fn runs(self) -> IntThe number of maximal runs.
- cost: O(1)
- traps: never
Examples:
var s = IntervalSet<0..10>(); s.add(1..3); s.add(6..7); s.runs == 2
IntervalSet.each
fn each(self) -> yields Range<D>Every maximal run.
- cost: O(1) per run
- empty: yields nothing for an empty set
- order: ascending positions
- traps: never
Examples:
var s = IntervalSet<0..10>(); s.add(6..7); s.add(1..3); s.each().collect() == [1..3, 6..7]
SparseIntervalSet
pub struct SparseIntervalSetO(runs) space. Dynamic union of disjoint half-open integer intervals [lo, hi) over unbounded Int coordinates.
SparseIntervalSet.new
fn new() -> SparseIntervalSetAn empty set of Int coordinates, unbounded in both directions.
- cost: O(1)
- traps: never
Examples:
SparseIntervalSet().covered == 0
SparseIntervalSet.add
fn add(mut self, r: Range<Int>)Add every coordinate of the half-open r, merging runs that overlap or touch it.
- cost: O((1 + merged) log runs) amortized
- empty: changes nothing
- traps: never
Examples:
var s = SparseIntervalSet(); s.add(-5..0); s.add(0..5); s.runs == 1 and s.covered == 10
SparseIntervalSet.remove
fn remove(mut self, r: Range<Int>)Remove every coordinate of the half-open r; a run straddling an end of r is cut there.
- cost: O((1 + split) log runs) amortized
- empty: changes nothing
- traps: never
Examples:
var s = SparseIntervalSet(); s.add(0..10); s.remove(3..4); s.runs == 2 and s.covered == 9
SparseIntervalSet.contains
fn contains(self, x: Int) -> BoolWhether the coordinate x is in the set.
- cost: O(log runs)
- traps: never
Examples:
var s = SparseIntervalSet(); s.add(10..20); s.contains(19) and not s.contains(20)
SparseIntervalSet.next_gap
fn next_gap(self, x: Int) -> IntThe least coordinate >= x that is not in the set; always exists, since the set is finite.
- cost: O(log runs)
- traps: never
Examples:
var s = SparseIntervalSet(); s.add(0..3); s.next_gap(1) == 3SparseIntervalSet().next_gap(-7) == -7
SparseIntervalSet.covered
fn covered(self) -> IntThe total number of coordinates in the set.
- cost: O(1)
- traps: never
Examples:
var s = SparseIntervalSet(); s.add(0..3); s.add(10..12); s.covered == 5
SparseIntervalSet.runs
fn runs(self) -> IntThe number of maximal intervals.
- cost: O(1)
- traps: never
Examples:
var s = SparseIntervalSet(); s.add(0..3); s.add(10..12); s.runs == 2
SparseIntervalSet.each
fn each(self) -> yields Range<Int>Every maximal interval.
- cost: O(1) per interval
- empty: yields nothing for an empty set
- order: ascending coordinates
- traps: never
Examples:
var s = SparseIntervalSet(); s.add(10..12); s.add(0..3); s.each().collect() == [0..3, 10..12]
SparseIntervalMap
pub struct SparseIntervalMap<T>Interval partition map over unbounded Int coordinates [lo, hi) (ODT without coordinate compression).
Maintains maximal constant runs; assign is O((1 + removed) log runs) amortized.
SparseIntervalMap.split
fn split(mut self, x: Int)SparseIntervalMap.merge_at
fn merge_at(mut self, x: Int)SparseIntervalMap.new
fn new(lo: Int, hi: Int, init: T) -> SparseIntervalMap<T>A map giving every coordinate of lo..hi the value init: one run, or None when lo == hi.
- cost: O(1)
- traps: when
lo > hi
Examples:
SparseIntervalMap(0, 1_000_000_000, 0).runs == 1
SparseIntervalMap.runs
fn runs(self) -> IntThe number of maximal runs of equal values.
- cost: O(1)
- traps: never
Examples:
var m = SparseIntervalMap(0, 10, 0); m.assign(3..5, 1); m.runs == 3
SparseIntervalMap.get
fn get(self, i: Int) -> TThe value at coordinate i.
- cost: O(log runs)
- traps: when
iis outsidelo..hi
Examples:
var m = SparseIntervalMap(0, 10, 0); m.assign(3..5, 1); m.get(4) == 1
SparseIntervalMap.run_at
fn run_at(self, i: Int) -> (range: Range<Int>, val: T)The maximal run containing coordinate i and its value.
- cost: O(log runs)
- order: the run's coordinates in ascending order
- traps: when
iis outsidelo..hi
Examples:
var m = SparseIntervalMap(0, 10, 0); m.assign(3..5, 1); m.run_at(7).range == 5..10
SparseIntervalMap.assign
fn assign(mut self, r: Range<Int>, val: T, on_old: (Range<Int>, T) -> () = (_, _) => ())Give every coordinate of r the value val, then merge with equal neighbouring runs.
on_old is called with each old run overlapping r, clipped to r, and its old value; the
map is fully repainted when assign returns.
- cost: O((1 + removed) log runs) amortized
- empty: changes nothing and calls
on_oldnever - order:
on_oldsees pieces in ascending coordinates - traps: when a non-empty
rreaches outsidelo..hi
Examples:
var m = SparseIntervalMap(0, 10, 0); m.assign(3..5, 1); m.assign(5..7, 1); m.runs == 3var m = SparseIntervalMap(0, 10, 0); m.assign(3..5, 1); var old: List<Int> = []; m.assign(4..6, 2, on_old: (_, v) => old.push(v)); old == [1, 0]
SparseIntervalMap.update
fn update(mut self, r: Range<Int>, f: T -> T)Replace the value v of every run overlapping r, clipped to r, with f(v), then merge
equal neighbours. f is called once per piece, in ascending order.
- cost: O((1 + touched) log runs)
- empty: changes nothing and calls
fnever - traps: when a non-empty
rreaches outsidelo..hi
Examples:
var m = SparseIntervalMap(0, 10, 0); m.assign(3..5, 1); m.update(0..4, v => v + 1); m.get(0) == 1 and m.get(3) == 2 and m.get(4) == 1
SparseIntervalMap.range
fn range(self, r: Range<Int>) -> yields (range: Range<Int>, val: T)Every run overlapping r, clipped to r, with its value.
- cost: O(log runs + k) for
kpieces - empty: yields nothing
- order: ascending coordinates
- traps: when a non-empty
rreaches outsidelo..hi
Examples:
var m = SparseIntervalMap(0, 10, 0); m.assign(3..5, 1); m.range(4..6).map(p => p.range).collect() == [4..5, 5..6]
SparseIntervalMap.each
fn each(self) -> yields (range: Range<Int>, val: T)Every maximal run with its value.
- cost: O(1) per run
- empty: yields nothing when
lo == hi - order: ascending coordinates
- traps: never
Examples:
var m = SparseIntervalMap(0, 10, 0); m.assign(3..5, 1); m.each().map(p => p.val).collect() == [0, 1, 0]
SparseIntervalMap.each_rev
fn each_rev(self) -> yields (range: Range<Int>, val: T)Every maximal run with its value, last first.
- cost: O(1) per run
- empty: yields nothing when
lo == hi - order: descending coordinates
- traps: never
Examples:
var m = SparseIntervalMap(0, 10, 0); m.assign(3..5, 1); m.each_rev().map(p => p.range).collect() == [5..10, 3..5, 0..3]