Skip to Content
ReferenceLibrary

seq

Every value of V once, in some order.

Generated from spec/std/seq.cp by cpl doc --format json.

Perm

pub type Perm<V> = [V]V

Every value of V once, in some order. cpl stress makes and shrinks it as a permutation.

Source

Compressed

pub struct Compressed<D, T>(vals: [D]T)

The distinct values of a coordinate compression, in increasing order, indexed by their own domain D. xs[i] is the value at index i, xs.at(val) the index of a value that was compressed, and xs.first_ge(val) / xs.last_le(val) the nearest index (?D) for any value.

Source

Compressed.get

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

O(1). The value at index i; slice takes a Range<D>.

  • cost: O(1)
  • traps: never

Examples:

  • let (domain C, xs) = compress([30, 10]); xs.get(C.first!) == 10

Source

Compressed.slice

fn slice(self, r: Range<D>) -> List<T>

The compressed values over a range r of xs.D, as a list.

  • cost: O(r.len)
  • empty: [] for an empty r
  • order: increasing values; a new List, keyed from 0
  • traps: never

Examples:

  • let (domain C, xs) = compress([3, 1, 2]); xs.slice(C.all) == [1, 2, 3]

Source

Compressed.len

fn len(self) -> Int

How many distinct values there are.

  • cost: O(1)
  • traps: never

Examples:

  • compress([5, 5, 7]).1.len == 2

Source

Compressed.at

fn at(self, val: T) -> D

The index of val, which must be one of the compressed values.

  • cost: O(log n)
  • ties: none: values are distinct
  • traps: when val was not compressed

Examples:

  • let (domain C, xs) = compress([30, 10]); xs.at(30) == C.last!

Source

Compressed.try_at

fn try_at(self, val: T) -> ?D

The index of val if it was compressed, or None.

  • cost: O(log n)
  • traps: never

Examples:

  • compress([30, 10]).1.try_at(20) == None

Source

Compressed.contains

fn contains(self, val: T) -> Bool

Whether val is one of the compressed values.

  • cost: O(log n)
  • traps: never

Examples:

  • compress([30, 10]).1.contains(10) == true

Source

Compressed.first_ge

fn first_ge(self, val: T) -> ?D

The first index whose value is >= val, or None.

  • cost: O(log n)
  • ties: none: values are distinct
  • traps: never

Examples:

  • let (domain C, xs) = compress([10, 30]); xs.first_ge(20) == Some(C.last!)

Source

Compressed.first_gt

fn first_gt(self, val: T) -> ?D

The first index whose value is > val, or None.

  • cost: O(log n)
  • ties: none: values are distinct
  • traps: never

Examples:

  • let (domain C, xs) = compress([10, 30]); xs.first_gt(30) == None

Source

Compressed.last_le

fn last_le(self, val: T) -> ?D

The last index whose value is <= val, or None.

  • cost: O(log n)
  • ties: none: values are distinct
  • traps: never

Examples:

  • let (domain C, xs) = compress([10, 30]); xs.last_le(20) == Some(C.first!)

Source

Compressed.last_lt

fn last_lt(self, val: T) -> ?D

The last index whose value is < val, or None.

  • cost: O(log n)
  • ties: none: values are distinct
  • traps: never

Examples:

  • let (domain C, xs) = compress([10, 30]); xs.last_lt(10) == None

Source

Filtered

pub struct Filtered<S>()

O(1) to make. The view s.filter(p): walks s, skipping elements that fail p, with s's keys. A lent value (R07.1.5).

Source

Filtered.src

fn src(self) -> S

O(1). The source sequence this view filters.

  • cost: O(1)
  • traps: never

Examples:

  • let a = [1, 2]; a.filter(x => x > 1).src == a

Source

Mapped

pub struct Mapped<S, U>()

O(1) to make. The view s.map(f): f of each element, with s's keys; Indexed when s is.

Source

Mapped.src

fn src(self) -> S

O(1). The source sequence this view maps.

  • cost: O(1)
  • traps: never

Examples:

  • let a = [1, 2]; a.map(x => x * 2).src == a

Source

Rev

pub struct Rev<S>()

O(1) to make. The view s.rev: s walked backwards, keys unchanged.

Source

Rev.src

fn src(self) -> S

O(1). The source sequence this view reverses.

  • cost: O(1)
  • traps: never

Examples:

  • let a = [1, 2]; a.rev.src == a

Source

Items

pub struct Items<S>()

O(1) to make. The view s.items: (key, element) pairs in s's order.

Source

Items.src

fn src(self) -> S

O(1). The source sequence whose items this view walks.

  • cost: O(1)
  • traps: never

Examples:

  • let a = [1, 2]; a.items.src == a

Source

Slice

pub struct Slice<S>()

O(1) to make. s[r]: a borrowed view of s over the range r. Every slice keeps its source's keys: a[l..=r][i] is a[i] and i must lie in l..=r; for a List or Str, s[2..5][3] is s[3] and s[2..5][0] traps. w.first, w.nth(k) and w.rebase() give offsets. Writable through a var source; the source's length can't change while it is alive. See spec/core/04b-keys.md.

Source

Slice.keys

fn keys<K>(self) -> Range<K>

O(1). The slice's keys: a sub-range of the source's keys.

  • cost: O(1)
  • traps: never
  • order: increasing

Examples:

  • [5, 6, 7][1..].keys == 1..3

Source

Slice.len

fn len(self) -> Int
  • cost: O(1)
  • traps: never

Examples:

  • [1, 2, 3][1..].len == 2

Source

Slice.is_empty

fn is_empty(self) -> Bool
  • cost: O(1)
  • traps: never

Examples:

  • [1, 2][2..].is_empty == true

Source

Slice.iter

fn iter(self) -> yields Int
  • cost: O(1) per step
  • empty: yields nothing
  • order: the slice's keys, increasing
  • traps: never

Examples:

  • [5, 6, 7][1..].iter().collect() == [1, 2]

Source

Rebased

pub struct Rebased<S>(src

The view rebase returns.

Source

Keys

pub struct Keys<S, I, K>(src: S, keys: I, by

The view keyed returns.

Source

SubseqStep

pub struct SubseqStep<T>(items: List<T>, pruned: Bool = false)

O(1). Steerable item yielded by subsequences (decision 126, W6).

Source

SubseqStep.prune

fn prune(mut self)

O(1). Skip extending this prefix in the subsequences search tree.

  • cost: O(1)
  • traps: never

Examples:

  • [1, 2].subsequences().filter(s => s.items.len <= 1 or { s.prune(); false }).count() == 3

Source

OnlineLis

pub struct OnlineLis<T>(strict: Bool = true)

O(1) construction; O(log n) push, O(1) amortized rollback. Online patience-sorting LIS tracker.

Source

OnlineLis.push

fn push(mut self, x: T) -> Int

O(log n). Append x and return the length of the longest increasing subsequence ending at x.

  • cost: O(log n)
  • traps: never

Examples:

  • var t = OnlineLis<Int>(); t.push(5); t.push(1); t.push(7) == 2

Source

OnlineLis.len

fn len(self) -> Int

O(1). Current global LIS length.

  • cost: O(1)
  • traps: never

Examples:

  • var t = OnlineLis<Int>(); t.push(1); t.push(3); t.len == 2

Source

OnlineLis.is_empty

fn is_empty(self) -> Bool

O(1). Whether no elements have been pushed.

  • cost: O(1)
  • traps: never

Examples:

  • OnlineLis<Int>().is_empty == true

Source

OnlineLis.clear

fn clear(mut self)

O(1). Reset all state.

  • cost: O(1)
  • traps: never

Examples:

  • var t = OnlineLis<Int>(); t.push(1); t.clear(); t.len == 0

Source

OnlineLis.reconstruct

fn reconstruct(self) -> List<Int>

O(n), O(n) memory. Reconstruct one global LIS as 0-based push indices.

  • cost: O(n), O(n) memory
  • empty: []
  • ties: the subsequence ending at the latest push of maximal length
  • order: increasing push indices
  • traps: never

Examples:

  • var t = OnlineLis<Int>(); for x in [3, 1, 2]: t.push(x); t.reconstruct() == [1, 2]

Source

OnlineLis.mark

fn mark(self) -> Int

O(1). Save a rollback checkpoint for DFS-on-tree LIS.

  • cost: O(1)
  • traps: never

Examples:

  • var t = OnlineLis<Int>(); let m = t.mark(); t.push(1); t.undo_to(m); t.len == 0

Source

OnlineLis.undo_to

fn undo_to(mut self, m: Int)

O(1) amortized. Roll back all pushes since checkpoint m.

  • cost: O(1) amortized per undone push
  • traps: when m is not a live mark of this tracker

Examples:

  • var t = OnlineLis<Int>(); t.push(2); let m = t.mark(); t.push(5); t.undo_to(m); t.len == 1

Source

MonoStack

pub struct MonoStack<D, T>(keep_smaller: Bool = true, strict: Bool = true)

O(1) construction; O(1) amortized push and rollback. Online monotone stack returning nearest dominating index.

Source

MonoStack.pops

fn pops(self, top: T, x: T) -> Bool

Source

MonoStack.push

fn push(mut self, i: D, x: T) -> ?D

O(1) amortized. Push (i, x), pop dominated entries, and return the nearest dominating index (or None).

  • cost: O(1) amortized
  • ties: equal values pop unless strict: false
  • traps: never

Examples:

  • var s = MonoStack<Int, Int>(); s.push(0, 5); s.push(1, 3) == Some(0)

Source

MonoStack.top

fn top(self) -> ?(index: D, val: T)

O(1). Current top (index, val), or None when empty.

  • cost: O(1)
  • traps: never
  • ties: none: the stack has one top

Examples:

  • var s = MonoStack<Int, Int>(); s.push(3, 8); s.top == Some((index: 3, val: 8))

Source

MonoStack.len

fn len(self) -> Int

O(1). Current stack depth.

  • cost: O(1)
  • traps: never

Examples:

  • var s = MonoStack<Int, Int>(); s.push(0, 5); s.len == 1

Source

MonoStack.is_empty

fn is_empty(self) -> Bool

O(1). Whether the stack is empty.

  • cost: O(1)
  • traps: never

Examples:

  • MonoStack<Int, Int>().is_empty == true

Source

MonoStack.clear

fn clear(mut self)

O(1). Empty the stack and rollback log.

  • cost: O(1)
  • traps: never

Examples:

  • var s = MonoStack<Int, Int>(); s.push(0, 1); s.clear(); s.is_empty

Source

MonoStack.mark

fn mark(self) -> Int

O(1). Save a rollback checkpoint for DFS-on-tree monotone stacks.

  • cost: O(1)
  • traps: never

Examples:

  • var s = MonoStack<Int, Int>(); let m = s.mark(); s.push(0, 1); s.undo_to(m); s.is_empty

Source

MonoStack.undo_to

fn undo_to(mut self, m: Int)

O(1) amortized. Roll back all pushes since checkpoint m.

  • cost: O(1) amortized per undone push
  • traps: when m is not a live mark of this stack

Examples:

  • var s = MonoStack<Int, Int>(); s.push(0, 5); let m = s.mark(); s.push(1, 9); s.undo_to(m); s.len == 1

Source

Anchor

pub enum Anchor = Start | End

Which end of a piece a two-pointer result is keyed by.

Source

Anchor.Start

Start

Source

Anchor.End

End

Source

Ring

pub struct Ring<D, T>(src: [D]T)

a.ring; see ring.

Source

Ring.step

fn step(self, i: D, d: Int) -> D

The position d steps after i (before it when d < 0), wrapping: a forced-online decode (v + last - 1) % n + 1 is V.ring.step(v, last). O(1).

  • cost: O(1)
  • traps: never

Examples:

  • [1, 2, 3].ring.step(0, -1) == 2

Source

Ring.next

fn next(self, i: D) -> D

The position after i, wrapping.

  • cost: O(1)
  • traps: never

Examples:

  • [1, 2, 3].ring.next(2) == 0

Source

Ring.prev

fn prev(self, i: D) -> D

The position before i, wrapping.

  • cost: O(1)
  • traps: never

Examples:

  • [1, 2, 3].ring.prev(0) == 2

Source

Ring.from

fn from(self, i: D) -> yields D

All n positions, starting at i and wrapping. O(n) to walk.

  • cost: O(1) per step
  • empty: yields nothing on an empty ring
  • order: i, then each next position, n in all
  • traps: never

Examples:

  • [1, 2, 3].ring.from(1).collect() == [1, 2, 0]

Source

Ring.span

fn span(self, start: D, len: Int) -> RingRange<D>

The len positions from start on, wrapping (len <= n).

  • cost: O(1)
  • empty: an empty span when len == 0
  • traps: when len is not in 0..=n

Examples:

  • [1, 2, 3].ring.span(2, 2).end == 0

Source

Ring.windows

fn windows(self, k: Int) -> yields RingSlice<D, T>

The n windows of k elements, one starting at each position, wrapping. O(n) to walk.

  • cost: O(1) per window
  • empty: yields nothing
  • order: by start position, increasing
  • traps: when k is not in 1..=n

Examples:

  • [1, 2, 3].ring.windows(2).count() == 3

Source

Ring.maximal

fn maximal<St>(self, state: St, ok: St -> Bool) -> [D]RingSlice<D, T>

Two pointers round the cycle: for each position as the last element, the longest wrapping piece (at most n elements) ending there that is ok, fed through state: Track. O(n) pushes and pops (two laps).

  • cost: O(n) pushes and pops on state
  • empty: an empty array
  • order: keyed by D, by last element
  • traps: never
  • ties: none: each last element has one longest piece

Examples:

  • [1, 1, 2].ring.maximal(state: Counter<Int, Int>(0), ok: c => c.len <= 2).map(w => w.len) == [3, 3, 3]

Source

Ring.minimal

fn minimal<St>(self, state: St, ok: St -> Bool) -> [D]?RingSlice<D, T>

For each position as the last element, the shortest wrapping piece ending there that is ok, or None. O(n) pushes and pops (two laps).

  • cost: O(n) pushes and pops on state
  • empty: an empty array
  • order: keyed by D, by last element
  • traps: never
  • ties: none: each last element has one shortest piece

Examples:

  • [2, 0, 1].ring.minimal(state: Window(+), ok: w => (w.all ?? 0) >= 3).map(w => w.map(.len)) == [Some(2), Some(3), Some(3)]

Source

RingRange

pub struct RingRange<D>()

A run of positions of D read cyclically, possibly wrapping past the last position, at most D.count of them. The keys-only half of a RingSlice, so it needs no array.

Source

RingRange.len

fn len(self) -> Int
  • cost: O(1)
  • traps: never

Examples:

  • [1, 2, 3].ring.span(2, 2).len == 2

Source

RingRange.start

fn start(self) -> D

O(1). The first position.

  • cost: O(1)
  • traps: never

Examples:

  • [1, 2, 3].ring.span(2, 2).start == 2

Source

RingRange.end

fn end(self) -> D

O(1). The last position.

  • cost: O(1)
  • traps: on an empty span

Examples:

  • [1, 2, 3].ring.span(2, 2).end == 0

Source

RingRange.keys

fn keys(self) -> yields D

O(1) to make. Its positions in ring order.

  • cost: O(1) to make, O(1) per step
  • order: ring order from start
  • traps: never

Examples:

  • [1, 2, 3].ring.span(2, 2).keys.collect() == [2, 0]

Source

RingRange.contains

fn contains(self, i: D) -> Bool
  • cost: O(1)
  • traps: never

Examples:

  • [1, 2, 3].ring.span(2, 2).contains(0) == true

Source

RingSlice

pub struct RingSlice<D, T>()

A contiguous piece of a ring, possibly wrapping past the end, at most n elements.

Source

RingSlice.range

fn range(self) -> RingRange<D>

O(1). Its positions, without the array.

  • cost: O(1)
  • traps: never

Examples:

  • [1, 2, 3].ring.windows(2).first!.range.len == 2

Source

RingSlice.len

fn len(self) -> Int
  • cost: O(1)
  • traps: never

Examples:

  • [w.len for w in [1, 2, 3].ring.windows(2)] == [2, 2, 2]

Source

RingSlice.start

fn start(self) -> D

O(1). The first position.

  • cost: O(1)
  • traps: never

Examples:

  • [1, 2, 3].ring.windows(2).first!.start == 0

Source

RingSlice.end

fn end(self) -> D

O(1). The last position.

  • cost: O(1)
  • traps: never

Examples:

  • [1, 2, 3].ring.windows(2).first!.end == 1

Source

RingSlice.keys

fn keys(self) -> yields D

O(1) to make. Its positions in ring order.

  • cost: O(1) to make, O(1) per step
  • order: ring order from start
  • traps: never

Examples:

  • [1, 2, 3].ring.windows(2).first!.keys.collect() == [0, 1]

Source

On this page