Skip to Content
ReferenceLibrary

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

Source

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

Source

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 op traps on)

Examples:

  • var w = Window(max); w.push(3); w.push(5); w.all == Some(5)

Source

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)

Source

Window.all

fn all(self) -> ?T

The 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

Source

Window.len

fn len(self) -> Int

The 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

Source

Window.push_back

fn push_back(mut self, x: T)

Source

Window.drop_front

fn drop_front(mut self)

Source

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.

Source

Track.push

fn push(mut self, x: T)

Source

Track.pop

fn pop(mut self, x: T)

Source

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.

Source

Counter<K, Int>.push

fn push(mut self, x: K)

Source

Counter<K, Int>.pop

fn pop(mut self, x: K)

Source

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.

Source

Window<T, M>.push

fn push(mut self, x: T)

Source

Window<T, M>.pop

fn pop(mut self, x: T)

Source

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.

Source

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 add traps on)

Examples:

  • var t = track(0, (mut s, x) => s += x, (mut s, x) => s -= x); t.push(3); t.state == 3

Source

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 remove traps 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

Source

Tracked.state

fn state(self) -> S

The 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

Source

Undo

pub trait Undo

A structure that can return to an earlier state, newest change first: Dsu, ParityDsu, WeightedDsu, DsuWith, RollbackArray, and any user struct with these two methods.

Source

Undo.mark

fn mark(mut self) -> Mark

Source

Undo.undo_to

fn undo_to(mut self, snap: Mark)

Source

Dsu<V>

impl Undo for Dsu<V>

Source

Dsu<V>.mark

fn mark(mut self) -> Mark

Source

Dsu<V>.undo_to

fn undo_to(mut self, snap: Mark)

Source

DsuOf<V, T>

impl Undo for DsuOf<V, T>

Source

DsuOf<V, T>.mark

fn mark(mut self) -> Mark

Source

DsuOf<V, T>.undo_to

fn undo_to(mut self, snap: Mark)

Source

ParityDsu<V>

impl Undo for ParityDsu<V>

Source

ParityDsu<V>.mark

fn mark(mut self) -> Mark

Source

ParityDsu<V>.undo_to

fn undo_to(mut self, snap: Mark)

Source

PotentialDsu<V>

impl Undo for PotentialDsu<V>

Source

PotentialDsu<V>.mark

fn mark(mut self) -> Mark

Source

PotentialDsu<V>.undo_to

fn undo_to(mut self, snap: Mark)

Source

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.

Source

Undoing.push_entry

fn push_entry(mut self, x: T, b: Bool)

Source

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 add amortized
  • traps: never (beyond what add traps 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))

Source

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 add amortized
  • 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))

Source

Undoing.state

fn state(self) -> S

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

Source

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.

Source

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.len pushes when start is given
  • empty: an empty start is the same as None, but sits at start's cut
  • traps: never (beyond what state.push traps on)

Examples:

  • domain D = 0..5; let s = Sweep<D, Counter<D, Int>>(Counter<D, Int>(0)); s.range.len == 0
  • domain D = 0..5; let s = Sweep<D, Counter<D, Int>>(Counter<D, Int>(0), start: Some(1..3)); s.range == 1..3

Source

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 dl and dr are the moves of the two ends
  • empty: moving to an empty to pops 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

Source

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

Source

On this page