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]VEvery value of V once, in some order. cpl stress makes and shrinks it as a permutation.
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.
Compressed.get
fn get(self, i: D) -> TO(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
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 emptyr - 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]
Compressed.len
fn len(self) -> IntHow many distinct values there are.
- cost: O(1)
- traps: never
Examples:
compress([5, 5, 7]).1.len == 2
Compressed.at
fn at(self, val: T) -> DThe index of val, which must be one of the compressed values.
- cost: O(log n)
- ties: none: values are distinct
- traps: when
valwas not compressed
Examples:
let (domain C, xs) = compress([30, 10]); xs.at(30) == C.last!
Compressed.try_at
fn try_at(self, val: T) -> ?DThe index of val if it was compressed, or None.
- cost: O(log n)
- traps: never
Examples:
compress([30, 10]).1.try_at(20) == None
Compressed.contains
fn contains(self, val: T) -> BoolWhether val is one of the compressed values.
- cost: O(log n)
- traps: never
Examples:
compress([30, 10]).1.contains(10) == true
Compressed.first_ge
fn first_ge(self, val: T) -> ?DThe 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!)
Compressed.first_gt
fn first_gt(self, val: T) -> ?DThe 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
Compressed.last_le
fn last_le(self, val: T) -> ?DThe 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!)
Compressed.last_lt
fn last_lt(self, val: T) -> ?DThe 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
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).
Filtered.src
fn src(self) -> SO(1). The source sequence this view filters.
- cost: O(1)
- traps: never
Examples:
let a = [1, 2]; a.filter(x => x > 1).src == a
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.
Mapped.src
fn src(self) -> SO(1). The source sequence this view maps.
- cost: O(1)
- traps: never
Examples:
let a = [1, 2]; a.map(x => x * 2).src == a
Rev
pub struct Rev<S>()O(1) to make. The view s.rev: s walked backwards, keys unchanged.
Rev.src
fn src(self) -> SO(1). The source sequence this view reverses.
- cost: O(1)
- traps: never
Examples:
let a = [1, 2]; a.rev.src == a
Items
pub struct Items<S>()O(1) to make. The view s.items: (key, element) pairs in s's order.
Items.src
fn src(self) -> SO(1). The source sequence whose items this view walks.
- cost: O(1)
- traps: never
Examples:
let a = [1, 2]; a.items.src == a
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.
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
Slice.len
fn len(self) -> Int- cost: O(1)
- traps: never
Examples:
[1, 2, 3][1..].len == 2
Slice.is_empty
fn is_empty(self) -> Bool- cost: O(1)
- traps: never
Examples:
[1, 2][2..].is_empty == true
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]
Rebased
pub struct Rebased<S>(srcThe view rebase returns.
Keys
pub struct Keys<S, I, K>(src: S, keys: I, byThe view keyed returns.
SubseqStep
pub struct SubseqStep<T>(items: List<T>, pruned: Bool = false)O(1). Steerable item yielded by subsequences (decision 126, W6).
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
OnlineLis
pub struct OnlineLis<T>(strict: Bool = true)O(1) construction; O(log n) push, O(1) amortized rollback. Online patience-sorting LIS tracker.
OnlineLis.push
fn push(mut self, x: T) -> IntO(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
OnlineLis.len
fn len(self) -> IntO(1). Current global LIS length.
- cost: O(1)
- traps: never
Examples:
var t = OnlineLis<Int>(); t.push(1); t.push(3); t.len == 2
OnlineLis.is_empty
fn is_empty(self) -> BoolO(1). Whether no elements have been pushed.
- cost: O(1)
- traps: never
Examples:
OnlineLis<Int>().is_empty == true
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
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]
OnlineLis.mark
fn mark(self) -> IntO(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
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
mis 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
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.
MonoStack.pops
fn pops(self, top: T, x: T) -> BoolMonoStack.push
fn push(mut self, i: D, x: T) -> ?DO(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)
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))
MonoStack.len
fn len(self) -> IntO(1). Current stack depth.
- cost: O(1)
- traps: never
Examples:
var s = MonoStack<Int, Int>(); s.push(0, 5); s.len == 1
MonoStack.is_empty
fn is_empty(self) -> BoolO(1). Whether the stack is empty.
- cost: O(1)
- traps: never
Examples:
MonoStack<Int, Int>().is_empty == true
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
MonoStack.mark
fn mark(self) -> IntO(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
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
mis 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
Anchor
pub enum Anchor = Start | EndWhich end of a piece a two-pointer result is keyed by.
Anchor.Start
StartAnchor.End
EndRing
pub struct Ring<D, T>(src: [D]T)a.ring; see ring.
Ring.step
fn step(self, i: D, d: Int) -> DThe 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
Ring.next
fn next(self, i: D) -> DThe position after i, wrapping.
- cost: O(1)
- traps: never
Examples:
[1, 2, 3].ring.next(2) == 0
Ring.prev
fn prev(self, i: D) -> DThe position before i, wrapping.
- cost: O(1)
- traps: never
Examples:
[1, 2, 3].ring.prev(0) == 2
Ring.from
fn from(self, i: D) -> yields DAll 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]
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
lenis not in0..=n
Examples:
[1, 2, 3].ring.span(2, 2).end == 0
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
kis not in1..=n
Examples:
[1, 2, 3].ring.windows(2).count() == 3
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]
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)]
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.
RingRange.len
fn len(self) -> Int- cost: O(1)
- traps: never
Examples:
[1, 2, 3].ring.span(2, 2).len == 2
RingRange.start
fn start(self) -> DO(1). The first position.
- cost: O(1)
- traps: never
Examples:
[1, 2, 3].ring.span(2, 2).start == 2
RingRange.end
fn end(self) -> DO(1). The last position.
- cost: O(1)
- traps: on an empty span
Examples:
[1, 2, 3].ring.span(2, 2).end == 0
RingRange.keys
fn keys(self) -> yields DO(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]
RingRange.contains
fn contains(self, i: D) -> Bool- cost: O(1)
- traps: never
Examples:
[1, 2, 3].ring.span(2, 2).contains(0) == true
RingSlice
pub struct RingSlice<D, T>()A contiguous piece of a ring, possibly wrapping past the end, at most n elements.
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
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]
RingSlice.start
fn start(self) -> DO(1). The first position.
- cost: O(1)
- traps: never
Examples:
[1, 2, 3].ring.windows(2).first!.start == 0
RingSlice.end
fn end(self) -> DO(1). The last position.
- cost: O(1)
- traps: never
Examples:
[1, 2, 3].ring.windows(2).first!.end == 1
RingSlice.keys
fn keys(self) -> yields DO(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]