Skip to Content
ReferenceLibrary

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

Source

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 D gives zero runs
  • traps: never

Examples:

  • IntervalMap<0..5, Int>(0).runs == 1

Source

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 a gives zero runs
  • order: positions keep the domain D of a
  • traps: never

Examples:

  • IntervalMap.from([1, 1, 2]).runs == 2

Source

IntervalMap.runs

fn runs(self) -> Int

The 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

Source

IntervalMap.get

fn get(self, i: D) -> T

The value at position i.

  • cost: O(log runs)
  • traps: when i is outside D

Examples:

  • IntervalMap.from([1, 1, 2]).get(2) == 2

Source

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 i is outside D

Examples:

  • IntervalMap.from([1, 1, 2]).run_at(1).range == 0..2
  • IntervalMap.from([1, 1, 2]).run_at(1).val == 1

Source

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_old never
  • order: on_old sees pieces in ascending positions
  • traps: when a non-empty r reaches outside D

Examples:

  • var m = IntervalMap<0..5, Int>(0); m.assign(1..3, 7); m.runs == 3
  • var m = IntervalMap<0..5, Int>(0); m.assign(1..3, 7); m.assign(1..3, 0); m.runs == 1
  • var 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]

Source

IntervalMap.assign_point

fn assign_point(mut self, i: D, val: T) -> T

Give position i the value val and return the value it had.

  • cost: O(log runs)
  • traps: when i is outside D

Examples:

  • var m = IntervalMap.from([1, 2]); m.assign_point(0, 5) == 1 and m.get(0) == 5

Source

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]

Source

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 i is outside D

Examples:

  • var m = IntervalMap.from([1, 1]); m.set(1, 3); m.runs == 2

Source

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 k pieces
  • empty: yields nothing
  • order: ascending positions
  • traps: when a non-empty r reaches outside D

Examples:

  • IntervalMap.from([1, 1, 2]).range(1..3).map(p => p.range).collect() == [1..2, 2..3]

Source

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]

Source

IntervalMap.first_where

fn first_where(self, from: Cut<D>, ok: T -> Bool) -> ?D

The 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 skipped runs that fail ok
  • 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

Source

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

Source

IntervalSet.new

fn new() -> IntervalSet<D>

An empty set of positions of D.

  • cost: O(1)
  • traps: never

Examples:

  • IntervalSet<0..10>().covered == 0

Source

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 r reaches outside D

Examples:

  • var s = IntervalSet<0..10>(); s.add(1..3); s.add(3..5); s.runs == 1 and s.covered == 4

Source

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 r reaches outside D

Examples:

  • var s = IntervalSet<0..10>(); s.add(0..5); s.remove(1..2); s.runs == 2 and s.covered == 4

Source

IntervalSet.contains

fn contains(self, i: D) -> Bool

Whether position i is in the set.

  • cost: O(log runs)
  • traps: when i is outside D

Examples:

  • var s = IntervalSet<0..10>(); s.add(2..4); s.contains(3) and not s.contains(4)

Source

IntervalSet.contains_range

fn contains_range(self, r: Range<D>) -> Bool

Whether 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 r reaches outside D

Examples:

  • var s = IntervalSet<0..10>(); s.add(2..4); s.add(4..6); s.contains_range(3..6) == true
  • var s = IntervalSet<0..10>(); s.add(2..4); s.contains_range(3..5) == false

Source

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 i is outside D

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

Source

IntervalSet.next_covered

fn next_covered(self, from: D) -> ?D

The first position at or after from that is in the set, or None.

  • cost: O(log runs)
  • traps: when from is outside D

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

Source

IntervalSet.next_gap

fn next_gap(self, from: D) -> ?D

The 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 from is outside D

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

Source

IntervalSet.covered

fn covered(self) -> Int

The 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

Source

IntervalSet.runs

fn runs(self) -> Int

The 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

Source

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]

Source

SparseIntervalSet

pub struct SparseIntervalSet

O(runs) space. Dynamic union of disjoint half-open integer intervals [lo, hi) over unbounded Int coordinates.

Source

SparseIntervalSet.new

fn new() -> SparseIntervalSet

An empty set of Int coordinates, unbounded in both directions.

  • cost: O(1)
  • traps: never

Examples:

  • SparseIntervalSet().covered == 0

Source

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

Source

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

Source

SparseIntervalSet.contains

fn contains(self, x: Int) -> Bool

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

Source

SparseIntervalSet.next_gap

fn next_gap(self, x: Int) -> Int

The 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) == 3
  • SparseIntervalSet().next_gap(-7) == -7

Source

SparseIntervalSet.covered

fn covered(self) -> Int

The 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

Source

SparseIntervalSet.runs

fn runs(self) -> Int

The number of maximal intervals.

  • cost: O(1)
  • traps: never

Examples:

  • var s = SparseIntervalSet(); s.add(0..3); s.add(10..12); s.runs == 2

Source

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]

Source

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.

Source

SparseIntervalMap.split

fn split(mut self, x: Int)

Source

SparseIntervalMap.merge_at

fn merge_at(mut self, x: Int)

Source

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

Source

SparseIntervalMap.runs

fn runs(self) -> Int

The 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

Source

SparseIntervalMap.get

fn get(self, i: Int) -> T

The value at coordinate i.

  • cost: O(log runs)
  • traps: when i is outside lo..hi

Examples:

  • var m = SparseIntervalMap(0, 10, 0); m.assign(3..5, 1); m.get(4) == 1

Source

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 i is outside lo..hi

Examples:

  • var m = SparseIntervalMap(0, 10, 0); m.assign(3..5, 1); m.run_at(7).range == 5..10

Source

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_old never
  • order: on_old sees pieces in ascending coordinates
  • traps: when a non-empty r reaches outside lo..hi

Examples:

  • var m = SparseIntervalMap(0, 10, 0); m.assign(3..5, 1); m.assign(5..7, 1); m.runs == 3
  • var 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]

Source

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 f never
  • traps: when a non-empty r reaches outside lo..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

Source

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 k pieces
  • empty: yields nothing
  • order: ascending coordinates
  • traps: when a non-empty r reaches outside lo..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]

Source

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]

Source

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]

Source

On this page