lazy
Paired aggregate (now, flipped) for range-toggle / complement updates (SegTree(op, a, act: flip)).
Generated from spec/std/lazy.cp by cpl doc --format json.
Flip
pub struct Flip<T>(now: T, flipped: T)Paired aggregate (now, flipped) for range-toggle / complement updates (SegTree(op, a, act: flip)).
Build the toggle action with flip_action(m) (tag Bool: true swaps now and flipped).
Flip.of
fn of(on: Bool, x: T, id: T) -> Flip<T>The leaf for one element that is currently on or off: Flip(x, id) when on, else
Flip(id, x). now is the value the element contributes as it stands and flipped what it
would contribute after one toggle.
- cost: O(1)
- traps: never
Examples:
Flip.of(true, 5, 0).now == 5Flip.of(false, 5, 0).flipped == 5
Flip.op
fn op<M>(m: M) -> Monoid<Flip<T>>The monoid on pairs that folds both halves with m independently:
op(a, b) == Flip(m(a.now, b.now), m(a.flipped, b.flipped)), identity Flip(id, id) with
id from Monoid.of(m).
- cost: O(1)
- traps: never (an
mwithout a known identity is a compile-time error)
Examples:
Flip.op(+).op(Flip(1, 0), Flip(0, 1)).now == 1Flip.op(+).id.flipped == 0
LazyTreap
pub struct LazyTreap<T, F>(Arena-backed randomized treap with subtree-size-aware lazy tag propagation.
Supports value-ordered insertion (insert, using before) for slope-trick / priority
structures with lazy updates, and 0-based implicit sequence operations (push, insert_at,
apply_range, get).
apply(v, left_sz, f) updates a node's value given its left subtree size;
split(f, left_sz) splits a tag f for the left and right subtrees (default (f, f));
compose(new_f, old_f) applies old_f first then new_f.
insert, insert_at, push, apply_range, get are O(log n) expected; apply_all is O(1);
take(k) is O(k + log n); to_list is O(n). Memory is O(n) in a contiguous node arena;
sizes and priorities are 0..2^31, so a treap holds fewer than 2^31 elements.
LazyTreap.new
fn new( apply: (T, Int, F) -> T, compose: (F, F) -> F, split: (F, Int) -> (F, F) = (f, _) => (f, f), before: (T, T) -> Bool = (_, _) => false, ) -> LazyTreap<T, F>An empty treap. apply(v, k, f) is element v after tag f, where k is the number of
elements before it in the run the tag was applied to (so tags may depend on rank);
compose(new_f, old_f) is old_f then new_f; split(f, k) gives the tags for the left
child and for the right child of a node with k elements on its left (default (f, f), for
tags that ignore rank; a rank-dependent tag needs a split that shifts the right child's ranks
by k + 1); before(x, y) orders value insertion (default never, so insert appends).
- cost: O(1)
- empty: the new treap is empty
- traps: never
Examples:
LazyTreap<Int, Int>(apply: (v, k, f) => v + f, compose: (g, f) => g + f).len == 0
LazyTreap.priority
fn priority(mut self) -> IntLazyTreap.sz_of
fn sz_of(self, u: ?Int) -> IntLazyTreap.len
fn len(self) -> IntThe number of elements stored.
- cost: O(1)
- traps: never
Examples:
var t = LazyTreap<Int, Int>(apply: (v, k, f) => v + f, compose: (g, f) => g + f); t.push(4); t.len == 1
LazyTreap.reserve
fn reserve(mut self, n: Int)Make room for n elements in total, so pushes up to that size never regrow the node arena.
A smaller n than the current capacity changes nothing.
- cost: O(n) when it grows, else O(1)
- traps: when
n >= 2^31(the size bound)
Examples:
var t = LazyTreap<Int, Int>(apply: (v, k, f) => v + f, compose: (g, f) => g + f); t.reserve(10); t.len == 0
LazyTreap.is_empty
fn is_empty(self) -> BoolWhether the treap holds no elements.
- cost: O(1)
- traps: never
Examples:
LazyTreap<Int, Int>(apply: (v, k, f) => v + f, compose: (g, f) => g + f).is_empty == true
LazyTreap.put
fn put(mut self, u: ?Int, f: F)LazyTreap.down
fn down(mut self, i: Int)LazyTreap.pull
fn pull(mut self, i: Int)LazyTreap.split_val
fn split_val(mut self, u: ?Int, x: T) -> (?Int, ?Int)LazyTreap.ins
fn ins(mut self, u: ?Int, idx: Int, x: T, p: Int) -> IntLazyTreap.split_pos
fn split_pos(mut self, u: ?Int, k: Int) -> (?Int, ?Int)LazyTreap.merge
fn merge(mut self, a: ?Int, b: ?Int) -> ?IntLazyTreap.insert
fn insert(mut self, x: T)Insert x before the first element e with before(x, e), or at the end when there is
None. With a strict order for before, a sorted treap stays sorted and x goes after the
elements equal to it.
- cost: O(log n) expected
- ties: after every equal element
- traps: when the treap already holds
2^31 - 1elements
Examples:
var t = LazyTreap<Int, Int>(apply: (v, k, f) => v + f, compose: (g, f) => g + f, before: (x, y) => x < y); t.insert(3); t.insert(1); t.insert(2); t.to_list() == [1, 2, 3]
LazyTreap.push
fn push(mut self, x: T)Append x at the end of the sequence.
- cost: O(log n) expected
- traps: when the treap already holds
2^31 - 1elements
Examples:
var t = LazyTreap<Int, Int>(apply: (v, k, f) => v + f, compose: (g, f) => g + f); t.push(1); t.push(2); t.to_list() == [1, 2]
LazyTreap.insert_at
fn insert_at(mut self, pos: Int, x: T)Insert x so that it becomes the element at 0-based position pos; pos == len appends.
- cost: O(log n) expected
- traps: when
pos < 0orpos > len
Examples:
var t = LazyTreap<Int, Int>(apply: (v, k, f) => v + f, compose: (g, f) => g + f); t.push(1); t.push(3); t.insert_at(1, 2); t.to_list() == [1, 2, 3]
LazyTreap.apply_all
fn apply_all(mut self, f: F)Apply tag f to every element, as one tag on the root; ranks k count from the first element.
- cost: O(1)
- empty: changes nothing
- traps: never
Examples:
var t = LazyTreap<Int, Int>(apply: (v, k, f) => v + f, compose: (g, f) => g + f); t.push(1); t.push(2); t.apply_all(10); t.to_list() == [11, 12]
LazyTreap.apply_range
fn apply_range(mut self, lo: Int, hi: Int, f: F)Apply tag f to the elements at positions lo..hi; ranks k count from position lo.
- cost: O(log n) expected
- empty:
lo == hichanges nothing - traps: when
lo < 0,hi > lenorlo > hi
Examples:
var t = LazyTreap<Int, Int>(apply: (v, k, f) => v + f, compose: (g, f) => g + f); t.push(0); t.push(0); t.push(0); t.apply_range(1, 3, 5); t.to_list() == [0, 5, 5]
LazyTreap.apply
fn apply(mut self, r: Range<Int>, f: F)Apply tag f to the elements at the positions of r; apply_range with a range.
- cost: O(log n) expected
- empty: changes nothing
- traps: when a non-empty
rreaches outside0..len
Examples:
var t = LazyTreap<Int, Int>(apply: (v, k, f) => v + f, compose: (g, f) => g + f); t.push(1); t.push(2); t.apply(1..2, 10); t.to_list() == [1, 12]
LazyTreap.reverse
fn reverse(mut self, r: Range<Int>)Reverse the order of the elements at positions r. Tags applied earlier keep their effect
on the elements they reached; a later tag sees the new order.
- cost: O(log n) expected
- empty: changes nothing
- traps: when a non-empty
rreaches outside0..len
Examples:
var t = LazyTreap<Int, Int>(apply: (v, k, f) => v + f, compose: (g, f) => g + f); t.push(1); t.push(2); t.push(3); t.reverse(0..2); t.to_list() == [2, 1, 3]
LazyTreap.erase_at
fn erase_at(mut self, pos: Int) -> TRemove the element at 0-based position pos and return it with every pending tag applied.
- cost: O(log n) expected
- traps: when
pos < 0orpos >= len
Examples:
var t = LazyTreap<Int, Int>(apply: (v, k, f) => v + f, compose: (g, f) => g + f); t.push(1); t.push(2); t.apply_all(5); t.erase_at(0) == 6 and t.to_list() == [7]
LazyTreap.erase_range
fn erase_range(mut self, r: Range<Int>)Remove the elements at positions r; later elements move down by r.len.
- cost: O(log n) expected
- empty: changes nothing
- traps: when a non-empty
rreaches outside0..len
Examples:
var t = LazyTreap<Int, Int>(apply: (v, k, f) => v + f, compose: (g, f) => g + f); t.push(1); t.push(2); t.push(3); t.erase_range(0..2); t.to_list() == [3]
LazyTreap.split_at
fn split_at(mut self, k: Int) -> LazyTreap<T, F>Split off the elements at positions k..len into a new treap with the same apply,
compose, split and before, and return it; self keeps positions 0..k. Pending
tags travel with the elements they cover.
- cost: O(log n) expected
- traps: when
k < 0ork > len
Examples:
var t = LazyTreap<Int, Int>(apply: (v, k, f) => v + f, compose: (g, f) => g + f); t.push(1); t.push(2); t.push(3); let u = t.split_at(1); t.to_list() == [1] and u.to_list() == [2, 3]
LazyTreap.copy_from
fn copy_from(mut self, src: LazyTreap<T, F>, u: ?Int) -> ?IntLazyTreap.append
fn append(mut self, mut other: LazyTreap<T, F>)Move every element of other onto the end of self, in order, leaving other empty. Both
treaps must use the same functions; self's are kept.
- cost: O(log n) expected
- empty: an empty
otherchanges nothing - traps: when the total reaches
2^31elements
Examples:
var t = LazyTreap<Int, Int>(apply: (v, k, f) => v + f, compose: (g, f) => g + f); t.push(1); var u = t.split_at(1); u.push(5); t.append(mut u); t.to_list() == [1, 5] and u.is_empty
LazyTreap.get
fn get(mut self, pos: Int) -> TThe element at 0-based position pos with every pending tag on its path applied. Tags are
pushed down along the path, which is why it takes mut self; the sequence does not change.
- cost: O(log n) expected
- traps: when
pos < 0orpos >= len
Examples:
var t = LazyTreap<Int, Int>(apply: (v, k, f) => v + f, compose: (g, f) => g + f); t.push(1); t.push(2); t.apply(0..1, 4); t.get(0) == 5
LazyTreap.walk
fn walk(self, u: ?Int, pend: ?F, lim: Int, mut out: List<T>)LazyTreap.take
fn take(self, k: Int) -> List<T>The first min(k, len) elements in order, with pending tags applied. Reads without pushing
tags, so the tree is unchanged.
- cost: O(k + log n)
- empty:
[]whenk == 0or the treap is empty - order: sequence order
- traps: when
k < 0
Examples:
var t = LazyTreap<Int, Int>(apply: (v, k, f) => v + f, compose: (g, f) => g + f); t.push(1); t.push(2); t.push(3); t.take(2) == [1, 2]var t = LazyTreap<Int, Int>(apply: (v, k, f) => v + f, compose: (g, f) => g + f); t.push(1); t.take(5) == [1]
LazyTreap.to_list
fn to_list(self) -> List<T>Every element in order, with pending tags applied; take(len).
- cost: O(n)
- empty:
[] - order: sequence order
- traps: never
Examples:
LazyTreap<Int, Int>(apply: (v, k, f) => v + f, compose: (g, f) => g + f).to_list() == []
Rope
pub struct Rope<D, T>O(n) space. Implicit-key rope over a domain D supporting O(log n) expected cut, paste,
reverse, range tag apply, path queries, and point get.
Rope.size
fn size(self, t: Int) -> IntRope.pull
fn pull(mut self, t: Int)Rope.tag_node
fn tag_node(mut self, t: Int, x: T)Rope.down
fn down(mut self, t: Int)Rope.split
fn split(mut self, t: Int, k: Int) -> (Int, Int)Rope.join
fn join(mut self, a: Int, b: Int) -> IntRope.find
fn find(mut self, k0: Int) -> IntRope.emit
fn emit(mut self, t: Int, mut out: [D]T, mut k: Int)Rope.new
fn new(a: ?[D]T = None, fill: ?T = None, merge: ?((T, T) -> T) = None) -> Rope<D, T>A rope over D holding the values of a, or fill at every position. merge(tag, x) is
how a tag from apply combines into a value; without it, a tag overwrites the values it covers.
Positions keep their domain D; reverse moves values, not positions.
- cost: O(|D|)
- empty: an empty
Dbuilds an empty rope - order: positions keep the domain
D(ofa, when given) - traps: when neither or both of
aandfillare given
Examples:
Rope([1, 2, 3]).to_array() == [1, 2, 3]Rope<0..2, Int>(fill: 7).get(1) == 7
Rope.apply
fn apply(mut self, r: Range<D>, tag: T)Apply tag to every value at positions r: each becomes merge(tag, x), or tag when
no merge was given. Stored lazily on the covering nodes.
- cost: O(log n) expected
- empty: changes nothing
- traps: when a non-empty
rreaches outsideD
Examples:
var r = Rope([1, 2, 3], merge: (t, x) => t + x); r.apply(1..3, 10); r.to_array() == [1, 12, 13]var r = Rope([1, 2, 3]); r.apply(0..2, 7); r.to_array() == [7, 7, 3]
Rope.reverse
fn reverse(mut self, r: Range<D>)Reverse the order of the values at positions r; pending tags stay with their values.
- cost: O(log n) expected
- empty: changes nothing
- traps: when a non-empty
rreaches outsideD
Examples:
var r = Rope([1, 2, 3]); r.reverse(0..3); r.get(0) == 3
Rope.get
fn get(mut self, i: D) -> TThe value currently at position i, with pending tags merged in.
- cost: O(log n) expected
- traps: when
iis outsideD
Examples:
var r = Rope([1, 2, 3]); r.reverse(1..3); r.get(1) == 3
Rope.set
fn set(mut self, i: D, x: T)Overwrite the value currently at position i with x, replacing any pending tags on it.
- cost: O(log n) expected
- traps: when
iis outsideD
Examples:
var r = Rope([1, 2, 3]); r.set(1, 9); r.to_array() == [1, 9, 3]
Rope.to_array
fn to_array(mut self) -> [D]TThe current values in position order, with every pending tag merged in.
- cost: O(|D|)
- empty: an empty array for an empty
D - order: position order of
D - traps: never
Examples:
var r = Rope([1, 2, 3]); r.reverse(0..2); r.to_array() == [2, 1, 3]