window
A sliding fold queue over op.
Generated from spec/std/window.cp by cpl doc --format json.
Window
pub struct Window<T, M>(op: M)A sliding fold queue over op. push and pop are O(1) amortized; all is O(1).
Window.new
fn new(op: M) -> Window<T, M>An empty window over op. The strategy comes from op's laws: a Group keeps a running
total and subtracts on pop, a Selective op (min, max, min(by:)) keeps a monotone
deque, and anything else keeps two stacks.
- cost: O(1)
- traps: never
Examples:
var w = Window(+); w.all == None
Window.push
fn push(mut self, x: T)Push x at the back, as the newest element.
- cost: O(1) amortized calls of
op - traps: never (beyond what
optraps on)
Examples:
var w = Window(max); w.push(3); w.push(5); w.all == Some(5)
Window.pop
fn pop(mut self)Pop the front: remove the oldest element.
- cost: O(1) amortized calls of
op - traps: on an empty window
Examples:
var w = Window(min); w.push(3); w.push(1); w.push(2); w.pop(); w.all == Some(1)var w = Window(min); w.push(1); w.push(2); w.pop(); w.all == Some(2)
Window.all
fn all(self) -> ?TThe fold of the current contents, oldest first (op(op(x1, x2), x3) for pushes x1, x2,
x3), so a non-commutative op folds in push order; None when empty.
- cost: O(1)
- empty:
None - traps: never
Examples:
var w = Window(+); w.push(2); w.push(3); w.all == Some(5)var w = Window(+); w.push(2); w.pop(); w.all == None
Window.len
fn len(self) -> IntThe number of elements in the window: pushes minus pops.
- cost: O(1)
- traps: never
Examples:
var w = Window(+); w.push(2); w.push(3); w.pop(); w.len == 1
Window.push_back
fn push_back(mut self, x: T)Window.drop_front
fn drop_front(mut self)Track
pub trait Track<T>State a window can add to at the back and remove from at the front. pop(x) is passed the
element leaving the front. Window(op), Counter<K, Int>, Tracked and Undoing implement it.
Track.push
fn push(mut self, x: T)Track.pop
fn pop(mut self, x: T)Counter<K, Int>
impl Track<K> for Counter<K, Int>push(x) adds 1 to x's count and pop(x) takes 1 away, so len is the number of distinct
values in the window.
Counter<K, Int>.push
fn push(mut self, x: K)Counter<K, Int>.pop
fn pop(mut self, x: K)Window<T, M>
impl Track<T> for Window<T, M>push(x) is Window.push(x); pop(x) is Window.pop(), which already knows the front.
Window<T, M>.push
fn push(mut self, x: T)Window<T, M>.pop
fn pop(mut self, x: T)Tracked
pub struct Tracked<S, T>(state: S, add: (mut S, T) -> (), remove: (mut S, T) -> ())A Track built from a structure and two closures.
Tracked.push
fn push(mut self, x: T)Apply x at the back: one call of add(state, x).
- cost: one call of
add - traps: never (beyond what
addtraps on)
Examples:
var t = track(0, (mut s, x) => s += x, (mut s, x) => s -= x); t.push(3); t.state == 3
Tracked.pop
fn pop(mut self, x: T)Take the front element x back out: one call of remove(state, x). x is passed through
as given; nothing checks that it is the oldest element.
- cost: one call of
remove - traps: never (beyond what
removetraps on)
Examples:
var t = track(0, (mut s, x) => s += x, (mut s, x) => s -= x); t.push(3); t.push(4); t.pop(3); t.state == 4
Tracked.state
fn state(self) -> SThe structure with exactly the window's elements applied.
- cost: O(1)
- traps: never
Examples:
track(7, (mut s, x) => s += x, (mut s, x) => s -= x).state == 7
Undo
pub trait UndoA structure that can return to an earlier state, newest change first: Dsu, ParityDsu,
WeightedDsu, DsuWith, RollbackArray, and any user struct with these two methods.
Undo.mark
fn mark(mut self) -> MarkUndo.undo_to
fn undo_to(mut self, snap: Mark)Dsu<V>
impl Undo for Dsu<V>Dsu<V>.mark
fn mark(mut self) -> MarkDsu<V>.undo_to
fn undo_to(mut self, snap: Mark)DsuOf<V, T>
impl Undo for DsuOf<V, T>DsuOf<V, T>.mark
fn mark(mut self) -> MarkDsuOf<V, T>.undo_to
fn undo_to(mut self, snap: Mark)ParityDsu<V>
impl Undo for ParityDsu<V>ParityDsu<V>.mark
fn mark(mut self) -> MarkParityDsu<V>.undo_to
fn undo_to(mut self, snap: Mark)PotentialDsu<V>
impl Undo for PotentialDsu<V>PotentialDsu<V>.mark
fn mark(mut self) -> MarkPotentialDsu<V>.undo_to
fn undo_to(mut self, snap: Mark)Undoing
pub struct Undoing<S: Undo, T>(state: S, add: (mut S, T) -> ())The queue-undo trick: a Track over an Undo structure, so a window that adds at the back
and drops from the front runs on a structure that can only undo its newest change (a
rollback DSU in a two-pointer pass). add(mut state, x) applies one element; state
always holds exactly the window's elements. Each element is applied O(log n) times
amortized, so a pass of n pushes and pops costs O(n log n) applications.
Undoing.push_entry
fn push_entry(mut self, x: T, b: Bool)Undoing.push
fn push(mut self, x: T)Push x at the back: one add on top of the current state.
- cost: O(1) applications of
addamortized - traps: never (beyond what
addtraps on)
Examples:
domain V = 0..3; var u = undoing(Dsu<V>(rollback: true), (mut d, e) => d.unite(e.0, e.1)); u.push((V(0), V(1))); u.state.same(V(0), V(1))
Undoing.pop
fn pop(mut self, x: T)Drop the front element, which must be x. The element removed is the stored oldest one;
x names it for the Track protocol and is not compared. Undoes back past the oldest
change and re-applies the rest (the queue-undo trick).
- cost: O(log n) applications of
addamortized - traps: on an empty
Undoing
Examples:
domain V = 0..3; var u = undoing(Dsu<V>(rollback: true), (mut d, e) => d.unite(e.0, e.1)); u.push((V(0), V(1))); u.push((V(1), V(2))); u.pop((V(0), V(1))); u.state.same(V(1), V(2)) and not u.state.same(V(0), V(1))
Undoing.state
fn state(self) -> SThe structure with exactly the window's elements applied.
- cost: O(1)
- traps: never
Examples:
domain V = 0..3; let u = undoing(Dsu<V>(rollback: true), (mut d, e) => d.unite(e.0, e.1)); not u.state.same(V(0), V(1))
Sweep
pub struct Sweep<D, S>(state: S)A movable interval over D feeding a Track, for Mo and divide-and-conquer DP. Moving
expands before shrinking. O(|change|) pushes and pops per move.
Sweep.new
fn new(state: S, start: ?Range<D> = None) -> Sweep<D, S>A sweep over state, starting empty (or at start). Empty means the range is empty at the
first cut of D; with start, each position of start is pushed in increasing order.
- cost: O(1), plus
start.lenpushes whenstartis given - empty: an empty
startis the same as None, but sits atstart's cut - traps: never (beyond what
state.pushtraps on)
Examples:
domain D = 0..5; let s = Sweep<D, Counter<D, Int>>(Counter<D, Int>(0)); s.range.len == 0domain D = 0..5; let s = Sweep<D, Counter<D, Int>>(Counter<D, Int>(0), start: Some(1..3)); s.range == 1..3
Sweep.move
fn move(mut self, to: Range<D>)Slide to to, feeding state the positions that enter and leave. Moving expands before
shrinking, in this order: grow the right end (push each new position, increasing), grow the
left end (push, decreasing), shrink the right end (pop, decreasing), shrink the left end
(pop, increasing). The state never sees a negative-length interval, but growing on the left
and shrinking on the right touch the "wrong" end of the Track, so as with Mo the state's
answer must ignore order.
- cost: O(|dl| + |dr|) pushes and pops, where
dlanddrare the moves of the two ends - empty: moving to an empty
topops everything - traps: never (beyond what the state traps on)
Examples:
domain D = 0..5; var s = Sweep<D, Counter<D, Int>>(Counter<D, Int>(0)); s.move(1..4); s.move(2..5); s.range == 2..5
Sweep.range
fn range(self) -> Range<D>The current interval: the positions whose pushes the state holds.
- cost: O(1)
- traps: never
- order: increasing positions of
D
Examples:
domain D = 0..5; var s = Sweep<D, Counter<D, Int>>(Counter<D, Int>(0)); s.move(0..2); s.range.len == 2