bag
Read-only handle into a SortedBag<K> node, valid until the next mutation.
Generated from spec/std/bag.cp by cpl doc --format json.
BagCursor
pub struct BagCursor(idRead-only handle into a SortedBag<K> node, valid until the next mutation.
SortedBag
pub struct SortedBag<K>An ordered multiset (bag) of K backed by a randomized treap over a single flat node array
with recycled node slots and parent pointers for O(1) amortized cursor stepping.
Keeps one node per distinct key with its multiplicity and subtree element count.
add, add_many, remove, remove_all, contains, count,
pop_first, pop_last, rank, nth, first_true, last_true, and cursor_* are O(log n) expected;
range(r) returns an O(1) view whose .first, .last, .len, .is_empty are O(log n)
expected and whose iteration (for x in b.range(r) / .rev) is O(log n + k);
first, last, key_of and count_of are O(1); next_cursor and prev_cursor are O(1) amortized;
len, distinct, is_empty, clear, and take are O(1);
entries, entries_rev, and to_list are O(n).
Elements are ordered by K's <; copies of one key are equal and indistinguishable, so
no method here has a tie to break between them. n in every cost is len.
SortedBag.new
fn new() -> SortedBag<K>Create an empty SortedBag<K>.
- cost: O(1)
- traps: never
Examples:
var b: SortedBag<Int> = SortedBag(); b.len == 0
SortedBag.of
fn of(xs: List<K>) -> SortedBag<K>Build a SortedBag containing every element of xs.
Every copy counts: SortedBag.of([2, 2]) holds two elements.
- cost: O(n log n) expected
- empty: an empty bag
- traps: never
Examples:
SortedBag.of([3, 1, 3]).to_list() == [1, 3, 3]
SortedBag.len
fn len(self) -> IntTotal number of elements in the bag (counting duplicates).
- cost: O(1)
- traps: never
Examples:
SortedBag.of([3, 1, 3]).len == 3
SortedBag.distinct
fn distinct(self) -> IntNumber of distinct keys currently in the bag.
- cost: O(1)
- traps: never
Examples:
SortedBag.of([3, 1, 3]).distinct == 2
SortedBag.is_empty
fn is_empty(self) -> BoolWhether the bag has no elements.
- cost: O(1)
- traps: never
Examples:
SortedBag.of([1]).is_empty == false
SortedBag.clear
fn clear(mut self)Remove all elements from the bag.
The node array keeps its capacity.
- cost: O(1)
- traps: never
Examples:
var b = SortedBag.of([1, 2]); b.clear(); b.len == 0 and b.first == None
SortedBag.take
fn take(mut self) -> SortedBag<K>Move the bag's contents out in O(1), leaving self empty.
- cost: O(1)
- traps: never
Examples:
var b = SortedBag.of([1, 2]); let t = b.take(); b.is_empty and t.to_list() == [1, 2]
SortedBag.add
fn add(mut self, x: K) -> BoolInsert one copy of x into the bag. Always returns true.
The Bool matches SortedSet.add, so code can switch between the two.
- cost: O(log n) expected
- traps: never
Examples:
var b: SortedBag<Int> = SortedBag(); b.add(3) and b.add(3) and b.count(3) == 2
SortedBag.add_unique
fn add_unique(mut self, x: K) -> BoolSortedBag.add_many
fn add_many(mut self, x: K, c: Int)Insert c >= 0 copies of x into the bag.
c == 0 does nothing.
- cost: O(log n) expected, independent of
c - traps: when
c < 0
Examples:
var b = SortedBag.of([1]); b.add_many(5, 3); b.len == 4 and b.count(5) == 3
SortedBag.remove
fn remove(mut self, x: K) -> BoolRemove one copy of x if present; returns true if a copy was removed.
- cost: O(log n) expected
- traps: never
Examples:
var b = SortedBag.of([2, 2]); b.remove(2) and b.count(2) == 1 and not b.remove(7)
SortedBag.remove_all
fn remove_all(mut self, x: K) -> IntRemove all copies of x and return how many were removed.
- cost: O(log n) expected
- traps: never
Examples:
var b = SortedBag.of([2, 2, 3]); b.remove_all(2) == 2 and b.to_list() == [3]var b = SortedBag.of([3]); b.remove_all(2) == 0
SortedBag.count
fn count(self, x: K) -> IntHow many copies of x are currently in the bag.
- cost: O(log n) expected
- traps: never
Examples:
SortedBag.of([2, 2, 3]).count(2) == 2SortedBag.of([2, 2, 3]).count(4) == 0
SortedBag.contains
fn contains(self, x: K) -> BoolWhether at least one copy of x is in the bag.
x in b calls this.
- cost: O(log n) expected
- traps: never
Examples:
SortedBag.of([2, 3]).contains(3) == true
SortedBag.first
fn first(self) -> ?KThe smallest element, or None when empty. O(1), kept current by every update.
- cost: O(1)
- empty:
None - ties: none: copies of the least key are equal
- traps: never
Examples:
SortedBag.of([3, 1, 1]).first == Some(1)
SortedBag.last
fn last(self) -> ?KThe largest element, or None when empty. O(1), kept current by every update.
- cost: O(1)
- empty:
None - ties: none: copies of the greatest key are equal
- traps: never
Examples:
SortedBag.of([3, 1, 3]).last == Some(3)
SortedBag.pop_first
fn pop_first(mut self) -> ?KRemove and return one copy of the smallest element, or None when empty.
- cost: O(log n) expected
- empty:
None - traps: never
Examples:
var b = SortedBag.of([3, 1, 1]); b.pop_first() == Some(1) and b.count(1) == 1
SortedBag.take_first
fn take_first(mut self, ok: K -> Bool) -> ?KO(log n). Removes and returns the least element satisfying monotone ok (false then
true): "the shortest partner that completes this chain".
One copy is removed. None, and no change, when ok holds for no element. It is
first_true(ok) followed by remove of the result, in one descent.
- cost: O(log n) expected
- empty:
None - ties: none: copies of the answer are equal; one is removed
- traps: never in release; debug traps when
okis not false-then-true at the answer
Examples:
var b = SortedBag.of([1, 4, 4, 6]); b.take_first(x => x >= 3) == Some(4) and b.to_list() == [1, 4, 6]var b = SortedBag.of([1]); b.take_first(x => x >= 3) == None and b.len == 1
SortedBag.drain_range
fn drain_range(mut self, r: Range<K>) -> yields KO(log n + k). Removes the elements whose value lies in r, yielding them in order.
Each copy is yielded once, so a key with count c is yielded c times. A loop that
stops early leaves the elements not yet yielded in the bag. r may be any ordered range
(a..b, a..=b, ..b, a.., ..).
- cost: O(log n + k) expected for
kremoved - empty: yields nothing, for an empty bag or an empty
r - order: ascending
- traps: never
Examples:
var b = SortedBag.of([1, 3, 3, 5, 7]); b.drain_range(3..6).collect() == [3, 3, 5] and b.to_list() == [1, 7]
SortedBag.pop_last
fn pop_last(mut self) -> ?KRemove and return one copy of the largest element, or None when empty.
- cost: O(log n) expected
- empty:
None - traps: never
Examples:
var b = SortedBag.of([3, 3, 1]); b.pop_last() == Some(3) and b.to_list() == [1, 3]
SortedBag.rank
fn rank(self, k: K) -> IntNumber of elements strictly less than k (counting duplicates).
k need not be in the bag. b.nth(b.rank(k)) is the least element >= k.
- cost: O(log n) expected
- empty:
0 - traps: never
Examples:
SortedBag.of([1, 2, 2, 5]).rank(2) == 1SortedBag.of([1, 2, 2, 5]).rank(3) == 3
SortedBag.rank_le
fn rank_le(self, k: K) -> IntSortedBag.lo_ok
fn lo_ok(self, x: K, lo: ?K, lo_inc: Bool) -> BoolSortedBag.hi_ok
fn hi_ok(self, x: K, hi: ?K, hi_inc: Bool) -> BoolSortedBag.range
fn range(self, r: Range<K>) -> SortedRange<K>The keys of self inside r, as an O(1) view; replaces first_ge, first_gt, last_le,
last_lt and count_range (decision 103). r is any ordered range: a..b, a..=b, ..b,
..=b, a.. or ... The view lends self, so self cannot change while it is in use.
- cost: O(1) to make; see
SortedRangefor each query - empty: a range with no keys gives an empty view
- traps: never
Examples:
SortedBag.of([1, 3, 3, 7]).range(2..=7).len() == 3
SortedBag.range_first
fn range_first(self, lo: ?K, lo_inc: Bool, hi: ?K, hi_inc: Bool) -> ?KSortedBag.range_last
fn range_last(self, lo: ?K, lo_inc: Bool, hi: ?K, hi_inc: Bool) -> ?KSortedBag.range_len
fn range_len(self, lo: ?K, lo_inc: Bool, hi: ?K, hi_inc: Bool) -> IntSortedBag.range_each
fn range_each(self, lo: ?K, lo_inc: Bool, hi: ?K, hi_inc: Bool) -> yields KSortedBag.range_each_rev
fn range_each_rev(self, lo: ?K, lo_inc: Bool, hi: ?K, hi_inc: Bool) -> yields KSortedBag.nth
fn nth(self, i: Int) -> ?K0-indexed i-th smallest element (counting duplicates), or None if out of bounds.
It is b.to_list()[i] without the list; None for any i outside 0..len, negative
included.
- cost: O(log n) expected
- empty:
None - traps: never
Examples:
SortedBag.of([5, 2, 2, 1]).nth(2) == Some(2)SortedBag.of([5, 2, 2, 1]).nth(4) == None
SortedBag.first_true
fn first_true(self, ok: K -> Bool) -> ?KSmallest key where monotone ok(k) holds (false..false, true..true), or None.
Checks monotonicity at the boundary. O(log n) expected.
ok is called on keys along one root-to-leaf path. Debug builds check that ok is
false on the key just below the answer.
- cost: O(log n) expected calls of
ok - empty:
None - ties: none: copies of a key are one candidate; the least key wins
- traps: never in release; debug traps when
okis not false-then-true at the answer
Examples:
SortedBag.of([1, 4, 6]).first_true(x => x >= 3) == Some(4)SortedBag.of([1, 4, 6]).first_true(x => x > 9) == None
SortedBag.last_true
fn last_true(self, ok: K -> Bool) -> ?KLargest key where monotone ok(k) holds (true..true, false..false), or None.
Checks monotonicity at the boundary. O(log n) expected.
- cost: O(log n) expected calls of
ok - empty:
None - ties: none: copies of a key are one candidate; the greatest key wins
- traps: never in release; debug traps when
okis not true-then-false at the answer
Examples:
SortedBag.of([1, 4, 6]).last_true(x => x <= 5) == Some(4)SortedBag.of([1, 4, 6]).last_true(x => x < 1) == None
SortedBag.drain
fn drain(mut self; after: ?K = None, before: ?K = None, while ok: K -> Bool) -> List<K>Remove and return the maximal run of elements strictly after after (ascending),
strictly before before (descending), or from the smallest element (ascending)
while ok(k) holds. O(k log n) expected for k removed elements.
The walk starts at the first element past the bound and stops at the first element
where ok is false, which stays; each copy of a removed key is one element of the
result. Giving both after and before is an error.
- cost: O(k log n) expected for
kremoved elements - empty:
[] - order: ascending with
afteror no bound, descending withbefore; a newList, keyed from 0 - traps: when both
afterandbeforeare given
Examples:
var b = SortedBag.of([1, 2, 2, 5, 8]); b.drain(after: 1, while: x => x < 5) == [2, 2] and b.to_list() == [1, 5, 8]var b = SortedBag.of([1, 2, 5, 8]); b.drain(before: 8, while: x => x > 1) == [5, 2] and b.to_list() == [1, 8]var b = SortedBag.of([1, 2, 5]); b.drain(while: x => x < 3) == [1, 2]
SortedBag.cursor_first
fn cursor_first(self) -> ?BagCursorCursor to the smallest key, or None when empty.
- cost: O(log n) expected
- empty:
None - traps: never
Examples:
let b = SortedBag.of([5, 2, 2]); b.key_of(b.cursor_first()!) == 2
SortedBag.cursor_last
fn cursor_last(self) -> ?BagCursorCursor to the largest key, or None when empty.
- cost: O(log n) expected
- empty:
None - traps: never
Examples:
let b = SortedBag.of([5, 2, 2]); b.key_of(b.cursor_last()!) == 5
SortedBag.cursor_at
fn cursor_at(self, k: K) -> ?BagCursorCursor to exact key k, or None if absent.
- cost: O(log n) expected
- empty:
None - traps: never
Examples:
let b = SortedBag.of([2, 5]); b.cursor_at(5) != None and b.cursor_at(3) == None
SortedBag.cursor_ge
fn cursor_ge(self, k: K) -> ?BagCursorCursor to smallest key >= k, or None.
- cost: O(log n) expected
- empty:
None - traps: never
Examples:
let b = SortedBag.of([2, 5]); b.key_of(b.cursor_ge(3)!) == 5 and b.cursor_ge(6) == None
SortedBag.cursor_gt
fn cursor_gt(self, k: K) -> ?BagCursorCursor to smallest key > k, or None.
- cost: O(log n) expected
- empty:
None - traps: never
Examples:
let b = SortedBag.of([2, 5]); b.key_of(b.cursor_gt(2)!) == 5 and b.cursor_gt(5) == None
SortedBag.cursor_le
fn cursor_le(self, k: K) -> ?BagCursorCursor to largest key <= k, or None.
- cost: O(log n) expected
- empty:
None - traps: never
Examples:
let b = SortedBag.of([2, 5]); b.key_of(b.cursor_le(4)!) == 2 and b.cursor_le(1) == None
SortedBag.cursor_lt
fn cursor_lt(self, k: K) -> ?BagCursorCursor to largest key < k, or None.
- cost: O(log n) expected
- empty:
None - traps: never
Examples:
let b = SortedBag.of([2, 5]); b.key_of(b.cursor_lt(5)!) == 2 and b.cursor_lt(2) == None
SortedBag.key_of
fn key_of(self, c: BagCursor) -> KKey stored at cursor c.
c must come from this bag and no mutation may have happened since it was made.
- cost: O(1)
- traps: never in release (a stale cursor reads an unspecified key); debug traps when the node of
chas been freed
Examples:
let b = SortedBag.of([2, 2, 5]); b.key_of(b.cursor_first()!) == 2
SortedBag.count_of
fn count_of(self, c: BagCursor) -> IntMultiplicity stored at cursor c.
- cost: O(1)
- traps: never in release (a stale cursor reads an unspecified count); debug traps when the node of
chas been freed
Examples:
let b = SortedBag.of([2, 2, 5]); b.count_of(b.cursor_at(2)!) == 2
SortedBag.next_cursor
fn next_cursor(self, c: BagCursor) -> ?BagCursorCursor to the next larger distinct key, or None.
Steps over all copies of the current key at once.
- cost: O(1) amortized, O(log n) worst case
- traps: never in release; debug traps when the node of
chas been freed
Examples:
let b = SortedBag.of([2, 2, 5]); b.key_of(b.next_cursor(b.cursor_first()!)!) == 5let b = SortedBag.of([2, 5]); b.next_cursor(b.cursor_last()!) == None
SortedBag.prev_cursor
fn prev_cursor(self, c: BagCursor) -> ?BagCursorCursor to the next smaller distinct key, or None.
- cost: O(1) amortized, O(log n) worst case
- traps: never in release; debug traps when the node of
chas been freed
Examples:
let b = SortedBag.of([2, 5, 5]); b.key_of(b.prev_cursor(b.cursor_last()!)!) == 2let b = SortedBag.of([2, 5]); b.prev_cursor(b.cursor_first()!) == None
SortedBag.entries
fn entries(self) -> yields (key: K, count: Int)Visit every distinct (key, count) in ascending order.
- cost: O(1) amortized per step
- empty: yields nothing
- order: ascending key, one entry per distinct key
- traps: never
Examples:
[e.key for e in SortedBag.of([5, 2, 2]).entries()] == [2, 5][e.count for e in SortedBag.of([5, 2, 2]).entries()] == [2, 1]
SortedBag.entries_rev
fn entries_rev(self) -> yields (key: K, count: Int)Visit every distinct (key, count) in descending order.
Exactly the reverse of entries.
- cost: O(1) amortized per step
- empty: yields nothing
- order: descending key, one entry per distinct key
- traps: never
Examples:
[e.key for e in SortedBag.of([5, 2, 2]).entries_rev()] == [5, 2]
SortedBag.to_list
fn to_list(self) -> List<K>Every element in ascending order, repeated by multiplicity.
- cost: O(n)
- empty:
[] - order: ascending, each key repeated by its count; a new
List, keyed from 0 - traps: never
Examples:
SortedBag.of([3, 1, 3]).to_list() == [1, 3, 3]
SortedBag.reserve
fn reserve(mut self, cap: Int)Preallocate treap node pool for at least cap distinct keys.
- cost: O(cap) when the pool grows, O(1) otherwise
- traps: never
Examples:
var b = SortedBag.of([1]); b.reserve(100); b.to_list() == [1]
SortedBag.split_at
fn split_at(mut self, k: K) -> SortedBag<K>Split off and return all elements >= k, keeping < k in self.
Every copy of a key goes to the same side.
The larger side keeps the node array; the smaller side's keys move to a fresh one.
- cost: O(log n + s log n) expected,
sthe smaller side's distinct keys - empty: both sides empty
- traps: never
Examples:
var b = SortedBag.of([1, 3, 3, 5]); let hi = b.split_at(3); b.to_list() == [1] and hi.to_list() == [3, 3, 5]
SortedBag.join
fn join(mut self, other: SortedBag<K>)Concatenate other onto self when every key in self is < every key in other.
The inverse of split_at. The precondition is checked in O(1) against self.last and
other.first; either side may be empty.
- cost: O(log n) expected
- traps: when both are non-empty and
self.last >= other.first
Examples:
var a = SortedBag.of([1, 2]); a.join(SortedBag.of([4, 4])); a.to_list() == [1, 2, 4, 4]
SortedBag.absorb
fn absorb(mut self, mut other: SortedBag<K>)Merge all elements of other into self (small-to-large, emptying other).
Copies add up: a key with count a in self and b in other ends with a + b. The
smaller bag's elements are inserted into the larger, whichever side that is.
- cost: O(min(n, m) log(n + m)) expected
- empty: an empty
otherleavesselfunchanged - traps: never
Examples:
var a = SortedBag.of([1, 3]); var b = SortedBag.of([3, 2]); a.absorb(mut b); a.to_list() == [1, 2, 3, 3] and b.is_empty
SortedBag.sum
fn sum(self) -> KSum of all elements (for additive K). O(1) when augmented, O(n) otherwise.
Each copy is added. BagNode keeps no subtree sum, so this bag is never augmented and
the cost is O(n); AugSortedBag keeps sums.
- cost: O(n)
- empty:
K.zero - traps: never (overflow wraps in release, traps in debug)
Examples:
SortedBag.of([2, 2, 5]).sum() == 9
SortedBag.refresh
fn refresh(mut self)SortedBag.sub_of
fn sub_of(self, t: Int) -> IntSortedBag.pull
fn pull(mut self, u: Int)SortedBag.make_node
fn make_node(mut self, x: K, c: Int) -> IntSortedBag.insert_at
fn insert_at(mut self, u: Int, x: K, c: Int, unique: Bool) -> (Int, Bool)SortedBag.erase_at
fn erase_at(mut self, u: Int, x: K, all: Bool) -> (Int, Int)SortedBag.merge
fn merge(mut self, a: Int, b: Int) -> IntSortedBag.split_lt
fn split_lt(mut self, t: Int, k: K) -> (Int, Int)SortedBag.move_out
fn move_out(mut self, t: Int, mut into: SortedBag<K>)SortedSet
pub struct SortedSet<K>An ordered set of unique keys K with order statistics (rank, nth),
O(1) key-range views (range(r)), and monotone search (first_true/last_true). Backed by SortedBag<K>.
All single-key and range-summary operations are O(log n) expected;
range(r) is O(1); range iteration is O(log n + k);
len, is_empty, clear, take are O(1); each, each_rev, and to_list are O(n).
SortedSet.new
fn new() -> SortedSet<K>Create an empty SortedSet<K>.
- cost: O(1)
- traps: never
Examples:
var s: SortedSet<Int> = SortedSet(); s.len == 0
SortedSet.of
fn of(xs: List<K>) -> SortedSet<K>Build a SortedSet containing the distinct elements of xs.
- cost: O(n log n) expected
- empty: an empty set
- traps: never
Examples:
SortedSet.of([3, 1, 3]).to_list() == [1, 3]
SortedSet.len
fn len(self) -> IntNumber of keys in the set.
- cost: O(1)
- traps: never
Examples:
SortedSet.of([3, 1, 3]).len == 2
SortedSet.is_empty
fn is_empty(self) -> BoolWhether the set is empty.
- cost: O(1)
- traps: never
Examples:
SortedSet.of([1]).is_empty == false
SortedSet.clear
fn clear(mut self)Remove all keys from the set.
- cost: O(1)
- traps: never
Examples:
var s = SortedSet.of([1, 2]); s.clear(); s.len == 0
SortedSet.take
fn take(mut self) -> SortedSet<K>Move all keys out, leaving self empty.
- cost: O(1)
- traps: never
Examples:
var s = SortedSet.of([1, 2]); let t = s.take(); s.is_empty and t.to_list() == [1, 2]
SortedSet.add
fn add(mut self, x: K) -> BoolInsert x if absent; returns true when x was newly inserted.
- cost: O(log n) expected
- traps: never
Examples:
var s = SortedSet.of([1]); s.add(2) and not s.add(2) and s.len == 2
SortedSet.remove
fn remove(mut self, x: K) -> BoolRemove x if present; returns true if removed.
- cost: O(log n) expected
- traps: never
Examples:
var s = SortedSet.of([1, 2]); s.remove(2) and not s.remove(2) and s.to_list() == [1]
SortedSet.set
fn set(mut self, x: K, on: Bool)Add x when on is true, or remove it otherwise, matching Set.set and Bitset.set.
- cost: O(log n) expected
- traps: never
Examples:
var s = SortedSet.of([1]); s.set(2, true); s.set(1, false); s.to_list() == [2]
SortedSet.contains
fn contains(self, x: K) -> BoolWhether x is in the set.
x in s calls this.
- cost: O(log n) expected
- traps: never
Examples:
SortedSet.of([1, 4]).contains(4) and not SortedSet.of([1, 4]).contains(2)
SortedSet.first
fn first(self) -> ?KSmallest key in the set, or None. O(1), kept current by every update.
- cost: O(1)
- empty:
None - ties: none: keys are distinct
- traps: never
Examples:
SortedSet.of([4, 1, 9]).first == Some(1)
SortedSet.last
fn last(self) -> ?KLargest key in the set, or None. O(1), kept current by every update.
- cost: O(1)
- empty:
None - ties: none: keys are distinct
- traps: never
Examples:
SortedSet.of([4, 1, 9]).last == Some(9)
SortedSet.pop_first
fn pop_first(mut self) -> ?KRemove and return the smallest key, or None.
- cost: O(log n) expected
- empty:
None - traps: never
Examples:
var s = SortedSet.of([4, 1]); s.pop_first() == Some(1) and s.to_list() == [4]
SortedSet.pop_last
fn pop_last(mut self) -> ?KRemove and return the largest key, or None.
- cost: O(log n) expected
- empty:
None - traps: never
Examples:
var s = SortedSet.of([4, 1]); s.pop_last() == Some(4) and s.to_list() == [1]
SortedSet.rank
fn rank(self, k: K) -> IntNumber of keys strictly less than k.
k need not be in the set.
- cost: O(log n) expected
- empty:
0 - traps: never
Examples:
SortedSet.of([1, 4, 9]).rank(4) == 1SortedSet.of([1, 4, 9]).rank(5) == 2
SortedSet.nth
fn nth(self, i: Int) -> ?K0-indexed i-th smallest key, or None if out of range.
None for any i outside 0..len, negative included.
- cost: O(log n) expected
- empty:
None - traps: never
Examples:
SortedSet.of([9, 1, 4]).nth(1) == Some(4)SortedSet.of([9, 1, 4]).nth(-1) == None
SortedSet.sum
fn sum(self, keys: Range<K> = ..) -> KThe sum of the elements in keys (all of them by default), for additive K:
set.sum(..b) adds everything below b. O(log n): subtree sums are kept.
keys may be any ordered range (a..b, a..=b, ..b, a.., ..); its ends need
not be in the set.
- cost: O(log n) expected
- empty:
K.zero, for an empty set or an emptykeys - traps: never (overflow wraps in release, traps in debug)
Examples:
SortedSet.of([1, 2, 5]).sum() == 8SortedSet.of([1, 2, 5]).sum(..3) == 3SortedSet.of([1, 2, 5]).sum(2..=5) == 7
SortedSet.first_true
fn first_true(self, ok: K -> Bool) -> ?KSmallest key k where monotone ok(k) holds (false..false, true..true), or None.
- cost: O(log n) expected calls of
ok - empty:
None - ties: none: keys are distinct; the least key wins
- traps: never in release; debug traps when
okis not false-then-true at the answer
Examples:
SortedSet.of([1, 4, 6]).first_true(x => x >= 3) == Some(4)
SortedSet.last_true
fn last_true(self, ok: K -> Bool) -> ?KLargest key k where monotone ok(k) holds (true..true, false..false), or None.
- cost: O(log n) expected calls of
ok - empty:
None - ties: none: keys are distinct; the greatest key wins
- traps: never in release; debug traps when
okis not true-then-false at the answer
Examples:
SortedSet.of([1, 4, 6]).last_true(x => x <= 5) == Some(4)
SortedSet.drain
fn drain(mut self; after: ?K = None, before: ?K = None, while ok: K -> Bool) -> List<K>Remove and return the maximal run of keys strictly after after (ascending),
strictly before before (descending), or from the smallest key (ascending)
while ok(k) holds. O(k log n) expected for k removed keys.
The walk stops at the first key where ok is false, which stays. Giving both after
and before is an error.
- cost: O(k log n) expected for
kremoved keys - empty:
[] - order: ascending with
afteror no bound, descending withbefore; a newList, keyed from 0 - traps: when both
afterandbeforeare given
Examples:
var s = SortedSet.of([1, 2, 5, 8]); s.drain(after: 1, while: x => x < 6) == [2, 5] and s.to_list() == [1, 8]var s = SortedSet.of([1, 2, 5, 8]); s.drain(before: 8, while: x => x > 1) == [5, 2]
SortedSet.range
fn range(self, r: Range<K>) -> SortedRange<K>The keys of self inside r, as an O(1) view; replaces first_ge, first_gt, last_le,
last_lt and count_range (decision 103). r is any ordered range: a..b, a..=b, ..b,
..=b, a.. or ... The view lends self, so self cannot change while it is in use.
- cost: O(1) to make; see
SortedRangefor each query - empty: a range with no keys gives an empty view
- traps: never
Examples:
SortedSet.of([1, 3, 7]).range(..7).last() == Some(3)
SortedSet.range_first
fn range_first(self, lo: ?K, lo_inc: Bool, hi: ?K, hi_inc: Bool) -> ?KSortedSet.range_last
fn range_last(self, lo: ?K, lo_inc: Bool, hi: ?K, hi_inc: Bool) -> ?KSortedSet.range_len
fn range_len(self, lo: ?K, lo_inc: Bool, hi: ?K, hi_inc: Bool) -> IntSortedSet.range_each
fn range_each(self, lo: ?K, lo_inc: Bool, hi: ?K, hi_inc: Bool) -> yields KSortedSet.range_each_rev
fn range_each_rev(self, lo: ?K, lo_inc: Bool, hi: ?K, hi_inc: Bool) -> yields KSortedSet.each
fn each(self) -> yields KVisit every key in ascending order.
for x in s uses this.
- cost: O(1) amortized per step
- empty: yields nothing
- order: ascending
- traps: never
Examples:
SortedSet.of([3, 1, 2]).each().collect() == [1, 2, 3]
SortedSet.each_rev
fn each_rev(self) -> yields KVisit every key in descending order.
- cost: O(1) amortized per step
- empty: yields nothing
- order: descending
- traps: never
Examples:
SortedSet.of([3, 1, 2]).each_rev().collect() == [3, 2, 1]
SortedSet.to_list
fn to_list(self) -> List<K>Return all keys in ascending order as a List<K>.
- cost: O(n)
- empty:
[] - order: ascending; a new
List, keyed from 0 - traps: never
Examples:
SortedSet.of([3, 1, 2]).to_list() == [1, 2, 3]
SortedSet.reserve
fn reserve(mut self, cap: Int)Preallocate treap node pool for at least cap keys.
- cost: O(cap) when the pool grows, O(1) otherwise
- traps: never
Examples:
var s = SortedSet.of([1]); s.reserve(100); s.to_list() == [1]
SortedSet.split_at
fn split_at(mut self, k: K) -> SortedSet<K>Split off and return all keys >= k, keeping < k in self.
- cost: O(log n + s log n) expected,
sthe smaller side's size - empty: both sides empty
- traps: never
Examples:
var s = SortedSet.of([1, 3, 5]); let hi = s.split_at(3); s.to_list() == [1] and hi.to_list() == [3, 5]
SortedSet.join
fn join(mut self, other: SortedSet<K>)Concatenate other onto self when every key in self is < every key in other.
The precondition is checked in O(1) against self.last and other.first.
- cost: O(log n) expected
- traps: when both are non-empty and
self.last >= other.first
Examples:
var a = SortedSet.of([1, 2]); a.join(SortedSet.of([4])); a.to_list() == [1, 2, 4]
SortedSet.absorb
fn absorb(mut self, mut other: SortedSet<K>)Merge all keys of other into self (small-to-large, emptying other).
A key in both sets appears once.
- cost: O(min(n, m) log(n + m)) expected
- empty: an empty
otherleavesselfunchanged - traps: never
Examples:
var a = SortedSet.of([1, 3]); var b = SortedSet.of([3, 2]); a.absorb(mut b); a.to_list() == [1, 2, 3] and b.is_empty
SortedMap
pub struct SortedMap<K, V>Order-statistic ordered map from K to V backed by a randomized treap.
get, set, remove, rank, nth, first_ge/last_le, first_true/last_true, split_at, join are O(log n).
Entries are ordered by key; keys are distinct, so no lookup has a tie to break. Every
entry-returning method gives (key, val).
SortedMap.entry
fn entry(self, k: ?K) -> ?(K, V)SortedMap.at
fn at(self, c: ?BagCursor) -> ?(K, V)SortedMap.new
fn new() -> SortedMap<K, V>Create an empty SortedMap<K, V>.
- cost: O(1)
- traps: never
Examples:
var m: SortedMap<Int, Str> = SortedMap(); m.len == 0
SortedMap.reserve
fn reserve(mut self, cap: Int)Preallocate treap node pool for at least cap entries.
- cost: O(cap) when the pool grows, O(1) otherwise
- traps: never
Examples:
var m: SortedMap<Int, Str> = SortedMap(); m.reserve(100); m.is_empty
SortedMap.len
fn len(self) -> IntNumber of key-value pairs.
- cost: O(1)
- traps: never
Examples:
var m: SortedMap<Int, Str> = SortedMap(); m.set(1, "a"); m.set(1, "b"); m.len == 1
SortedMap.is_empty
fn is_empty(self) -> BoolWhether the map is empty.
- cost: O(1)
- traps: never
Examples:
var m: SortedMap<Int, Str> = SortedMap(); m.is_empty
SortedMap.clear
fn clear(mut self)Remove all entries.
- cost: O(1)
- traps: never
Examples:
var m: SortedMap<Int, Str> = SortedMap(); m.set(1, "a"); m.clear(); m.get(1) == None
SortedMap.take
fn take(mut self) -> SortedMap<K, V>Move contents out in O(1), leaving self empty.
- cost: O(1)
- traps: never
Examples:
var m: SortedMap<Int, Str> = SortedMap(); m.set(1, "a"); let t = m.take(); m.is_empty and t.get(1) == Some("a")
SortedMap.get
fn get(self, k: K) -> ?VLook up k, returning None if absent.
- cost: O(log n) expected
- traps: never
Examples:
var m: SortedMap<Int, Str> = SortedMap(); m.set(1, "a"); m.get(1) == Some("a") and m.get(2) == None
SortedMap.contains
fn contains(self, k: K) -> BoolWhether k is present.
- cost: O(log n) expected
- traps: never
Examples:
var m: SortedMap<Int, Str> = SortedMap(); m.set(1, "a"); m.contains(1) and not m.contains(2)
SortedMap.set
fn set(mut self, k: K, v: V)Insert or overwrite k -> v (W8 IndexSet backing m[k] = v).
- cost: O(log n) expected
- traps: never
Examples:
var m: SortedMap<Int, Str> = SortedMap(); m[1] = "a"; m[1] = "b"; m.get(1) == Some("b")
SortedMap.remove
fn remove(mut self, k: K) -> ?VRemove k and return its previous value, or None if absent.
- cost: O(log n) expected
- traps: never
Examples:
var m: SortedMap<Int, Str> = SortedMap(); m.set(1, "a"); m.remove(1) == Some("a") and m.remove(1) == None
SortedMap.first
fn first(self) -> ?(K, V)Smallest (key, val) pair, or None if empty. O(1), kept current by every update.
- cost: O(1)
- empty:
None - ties: none: keys are distinct
- traps: never
Examples:
var m: SortedMap<Int, Str> = SortedMap(); m.set(3, "c"); m.set(1, "a"); m.first == Some((1, "a"))
SortedMap.last
fn last(self) -> ?(K, V)Largest (key, val) pair, or None if empty. O(1), kept current by every update.
- cost: O(1)
- empty:
None - ties: none: keys are distinct
- traps: never
Examples:
var m: SortedMap<Int, Str> = SortedMap(); m.set(3, "c"); m.set(1, "a"); m.last == Some((3, "c"))
SortedMap.pop_first
fn pop_first(mut self) -> ?(K, V)Remove and return the smallest (key, val) pair, or None.
- cost: O(log n) expected
- empty:
None - traps: never
Examples:
var m: SortedMap<Int, Str> = SortedMap(); m.set(3, "c"); m.set(1, "a"); m.pop_first() == Some((1, "a")) and m.len == 1
SortedMap.pop_last
fn pop_last(mut self) -> ?(K, V)Remove and return the largest (key, val) pair, or None.
- cost: O(log n) expected
- empty:
None - traps: never
Examples:
var m: SortedMap<Int, Str> = SortedMap(); m.set(3, "c"); m.set(1, "a"); m.pop_last() == Some((3, "c")) and m.len == 1
SortedMap.first_ge
fn first_ge(self, k: K) -> ?(K, V)Smallest entry with key >= k, or None.
- cost: O(log n) expected
- empty:
None - ties: none: keys are distinct
- traps: never
Examples:
var m: SortedMap<Int, Str> = SortedMap(); m.set(1, "a"); m.set(3, "c"); m.first_ge(2) == Some((3, "c")) and m.first_ge(3) == Some((3, "c"))
SortedMap.first_gt
fn first_gt(self, k: K) -> ?(K, V)Smallest entry with key > k, or None.
- cost: O(log n) expected
- empty:
None - ties: none: keys are distinct
- traps: never
Examples:
var m: SortedMap<Int, Str> = SortedMap(); m.set(1, "a"); m.set(3, "c"); m.first_gt(1) == Some((3, "c")) and m.first_gt(3) == None
SortedMap.last_le
fn last_le(self, k: K) -> ?(K, V)Largest entry with key <= k, or None.
- cost: O(log n) expected
- empty:
None - ties: none: keys are distinct
- traps: never
Examples:
var m: SortedMap<Int, Str> = SortedMap(); m.set(1, "a"); m.set(3, "c"); m.last_le(2) == Some((1, "a")) and m.last_le(0) == None
SortedMap.last_lt
fn last_lt(self, k: K) -> ?(K, V)Largest entry with key < k, or None.
- cost: O(log n) expected
- empty:
None - ties: none: keys are distinct
- traps: never
Examples:
var m: SortedMap<Int, Str> = SortedMap(); m.set(1, "a"); m.set(3, "c"); m.last_lt(3) == Some((1, "a")) and m.last_lt(1) == None
SortedMap.rank
fn rank(self, k: K) -> IntNumber of entries with key strictly less than k.
- cost: O(log n) expected
- empty:
0 - traps: never
Examples:
var m: SortedMap<Int, Str> = SortedMap(); m.set(1, "a"); m.set(3, "c"); m.rank(3) == 1 and m.rank(9) == 2
SortedMap.nth
fn nth(self, i: Int) -> ?(K, V)The i-th entry in key order (0-based), or None.
None for any i outside 0..len, negative included.
- cost: O(log n) expected
- empty:
None - traps: never
Examples:
var m: SortedMap<Int, Str> = SortedMap(); m.set(3, "c"); m.set(1, "a"); m.nth(1) == Some((3, "c")) and m.nth(2) == None
SortedMap.first_true
fn first_true(self, ok: (K, V) -> Bool) -> ?(K, V)Smallest entry where monotone ok(k, v) becomes true, or None.
ok must be false-then-true along ascending keys.
- cost: O(log n) expected calls of
ok - empty:
None - ties: none: keys are distinct; the least key wins
- traps: never in release; debug traps when
okis not false-then-true at the answer
Examples:
var m: SortedMap<Int, Int> = SortedMap(); m.set(1, 10); m.set(4, 40); m.set(6, 60); m.first_true((k, v) => v >= 30) == Some((4, 40))
SortedMap.last_true
fn last_true(self, ok: (K, V) -> Bool) -> ?(K, V)Largest entry where monotone ok(k, v) still holds, or None.
ok must be true-then-false along ascending keys.
- cost: O(log n) expected calls of
ok - empty:
None - ties: none: keys are distinct; the greatest key wins
- traps: never in release; debug traps when
okis not true-then-false at the answer
Examples:
var m: SortedMap<Int, Int> = SortedMap(); m.set(1, 10); m.set(4, 40); m.set(6, 60); m.last_true((k, v) => k <= 5) == Some((4, 40))
SortedMap.drain
fn drain(mut self; after: ?K = None, before: ?K = None, while ok: (K, V) -> Bool) -> List<(K, V)>Remove and return entries after after (ascending) or before before (descending) while ok holds.
With neither bound the walk starts at the smallest key. It stops at the first entry
where ok is false, which stays; bounds are exclusive. Giving both is an error.
- cost: O(k log n) expected for
kremoved entries - empty:
[] - order: ascending key with
afteror no bound, descending withbefore; a newList, keyed from 0 - traps: when both
afterandbeforeare given
Examples:
var m: SortedMap<Int, Int> = SortedMap(); m.set(1, 10); m.set(4, 40); m.set(6, 60); m.drain(after: 1, while: (k, v) => v < 50) == [(4, 40)] and m.len == 2
SortedMap.split_at
fn split_at(mut self, k: K) -> SortedMap<K, V>Split off and return all entries with key >= k.
self keeps the entries with key < k.
- cost: O(log n) expected
- empty: both sides empty
- traps: never
Examples:
var m: SortedMap<Int, Str> = SortedMap(); m.set(1, "a"); m.set(3, "c"); let hi = m.split_at(2); m.len == 1 and hi.first == Some((3, "c"))
SortedMap.join
fn join(mut self, other: SortedMap<K, V>)Concatenate other onto self when every key in self is < every key in other.
The precondition is checked in O(1) against the last key of self and the first of
other.
- cost: O(log n) expected
- traps: when both are non-empty and the last key of
selfis>=the first key ofother
Examples:
var a: SortedMap<Int, Str> = SortedMap(); a.set(1, "a"); var b: SortedMap<Int, Str> = SortedMap(); b.set(3, "c"); a.join(b); a.len == 2
SortedMap.absorb
fn absorb(mut self, mut other: SortedMap<K, V>, join: ?((V, V) -> V) = None)Merge all entries of other into self (emptying other), combining collisions with join or overwriting.
For a key in both maps the result is join(self's value, other's value), or other's
value when join is None, whichever map is drained into the other.
- cost: O(min(n, m) log(n + m)) expected
- empty: an empty
otherleavesselfunchanged - traps: never
Examples:
var a: SortedMap<Int, Int> = SortedMap(); a.set(1, 10); var b: SortedMap<Int, Int> = SortedMap(); b.set(1, 5); b.set(2, 7); a.absorb(mut b, join: (x, y) => x + y); a.get(1) == Some(15) and a.get(2) == Some(7) and b.is_empty
SortedMap.items
fn items(self) -> yields (K, V)O(1) to make. Yields (key, val) pairs in ascending key order.
- cost: O(1) to make, O(1) amortized per step
- empty: yields nothing
- order: ascending key
- traps: never
Examples:
var m: SortedMap<Int, Str> = SortedMap(); m.set(3, "c"); m.set(1, "a"); m.items.collect() == [(1, "a"), (3, "c")]
SortedMap.each_rev
fn each_rev(self) -> yields (K, V)Yield (key, val) pairs in descending key order.
- cost: O(1) amortized per step
- empty: yields nothing
- order: descending key
- traps: never
Examples:
var m: SortedMap<Int, Str> = SortedMap(); m.set(3, "c"); m.set(1, "a"); m.each_rev().collect() == [(3, "c"), (1, "a")]
SortedMap.keys
fn keys(self) -> yields K- cost: O(1) to make, O(1) amortized per step
- empty: yields nothing
- order: ascending key
- traps: never
Examples:
var m: SortedMap<Int, Str> = SortedMap(); m.set(3, "c"); m.set(1, "a"); m.keys.collect() == [1, 3]
SortedMap.values
fn values(self) -> yields V- cost: O(1) to make, O(1) amortized per step
- empty: yields nothing
- order: ascending key
- traps: never
Examples:
var m: SortedMap<Int, Str> = SortedMap(); m.set(3, "c"); m.set(1, "a"); m.values.collect() == ["a", "c"]
AugSortedBag
pub struct AugSortedBag<K, T>Monoid-augmented ordered multiset maintaining op over leaf(k) on every subtree (W10 operation values).
Supports O(log n) add, remove, rank, nth, fold_lt, fold_le, fold_ge, fold_gt, fold_between, and O(1) all.
Every fold combines leaf(k) over the chosen elements in ascending key order, one leaf(k)
per copy, starting from id; op need not be commutative. An empty selection folds to id.
AugSortedBag.sub
fn sub(self, t: Int) -> TAugSortedBag.size
fn size(self, t: Int) -> IntAugSortedBag.pull
fn pull(mut self, t: Int)AugSortedBag.split
fn split(mut self, t: Int, x: K) -> (Int, Int)AugSortedBag.merge
fn merge(mut self, a: Int, b: Int) -> IntAugSortedBag.drop_min
fn drop_min(mut self, t: Int) -> IntAugSortedBag.extreme
fn extreme(self, right: Bool) -> ?KAugSortedBag.rank_le
fn rank_le(self, k: K) -> IntAugSortedBag.fold_from
fn fold_from(self, start: Int, lo: K, strict: Bool) -> TAugSortedBag.fold_upto
fn fold_upto(self, start: Int, hi: K, strict: Bool) -> TAugSortedBag.new
fn new(op: (T, T) -> T, id: T, leaf: K -> T) -> AugSortedBag<K, T>Create an empty AugSortedBag<K, T> with associative op, identity id, and key map leaf.
- cost: O(1)
- traps: never
Examples:
var b: AugSortedBag<Int, Int> = AugSortedBag((x, y) => x + y, 0, k => k); b.all == 0
AugSortedBag.reserve
fn reserve(mut self, cap: Int)Preallocate treap node pool for at least cap elements.
- cost: O(cap) when the pool grows, O(1) otherwise
- traps: never
Examples:
var b: AugSortedBag<Int, Int> = AugSortedBag((x, y) => x + y, 0, k => k); b.reserve(100); b.len == 0
AugSortedBag.len
fn len(self) -> IntTotal number of elements (with multiplicity).
- cost: O(1)
- traps: never
Examples:
var b: AugSortedBag<Int, Int> = AugSortedBag((x, y) => x + y, 0, k => k); b.add(3); b.add(3); b.len == 2
AugSortedBag.is_empty
fn is_empty(self) -> BoolWhether the bag is empty.
- cost: O(1)
- traps: never
Examples:
var b: AugSortedBag<Int, Int> = AugSortedBag((x, y) => x + y, 0, k => k); b.is_empty
AugSortedBag.all
fn all(self) -> TFold of all elements in the bag.
- cost: O(1)
- empty:
id - traps: never
Examples:
var b: AugSortedBag<Int, Int> = AugSortedBag((x, y) => x + y, 0, k => k); b.add(3); b.add(1); b.add(3); b.all == 7
AugSortedBag.add
fn add(mut self, x: K)Insert one copy of x.
- cost: O(log n) expected
- traps: never
Examples:
var b: AugSortedBag<Int, Int> = AugSortedBag((x, y) => x + y, 0, k => k); b.add(3); b.add(3); b.count(3) == 2
AugSortedBag.remove
fn remove(mut self, x: K) -> BoolRemove one copy of x; returns false if absent.
- cost: O(log n) expected
- traps: never
Examples:
var b: AugSortedBag<Int, Int> = AugSortedBag((x, y) => x + y, 0, k => k); b.add(3); b.add(1); b.add(3); b.remove(3) and b.all == 4 and not b.remove(2)
AugSortedBag.count
fn count(self, x: K) -> IntMultiplicity of x.
- cost: O(log n) expected
- traps: never
Examples:
var b: AugSortedBag<Int, Int> = AugSortedBag((x, y) => x + y, 0, k => k); b.add(3); b.add(3); b.count(3) == 2 and b.count(1) == 0
AugSortedBag.rank
fn rank(self, k: K) -> IntNumber of elements strictly less than k.
- cost: O(log n) expected
- empty:
0 - traps: never
Examples:
var b: AugSortedBag<Int, Int> = AugSortedBag((x, y) => x + y, 0, k => k); b.add(3); b.add(1); b.add(3); b.rank(3) == 1
AugSortedBag.nth
fn nth(self, i: Int) -> ?KThe i-th smallest element (0-based), or None.
Copies count; None for any i outside 0..len.
- cost: O(log n) expected
- empty:
None - traps: never
Examples:
var b: AugSortedBag<Int, Int> = AugSortedBag((x, y) => x + y, 0, k => k); b.add(3); b.add(1); b.add(3); b.nth(2) == Some(3) and b.nth(3) == None
AugSortedBag.first
fn first(self) -> ?KSmallest element, or None. O(1), kept current by every update.
- cost: O(1)
- empty:
None - ties: none: copies of the least key are equal
- traps: never
Examples:
var b: AugSortedBag<Int, Int> = AugSortedBag((x, y) => x + y, 0, k => k); b.add(3); b.add(1); b.first == Some(1)
AugSortedBag.last
fn last(self) -> ?KLargest element, or None. O(1), kept current by every update.
- cost: O(1)
- empty:
None - ties: none: copies of the greatest key are equal
- traps: never
Examples:
var b: AugSortedBag<Int, Int> = AugSortedBag((x, y) => x + y, 0, k => k); b.add(3); b.add(1); b.last == Some(3)
AugSortedBag.fold_lt
fn fold_lt(self, hi: K) -> TFold elements with key < hi.
- cost: O(log n) expected
- empty:
id - traps: never
Examples:
var b: AugSortedBag<Int, Int> = AugSortedBag((x, y) => x + y, 0, k => k); b.add(3); b.add(1); b.add(3); b.fold_lt(3) == 1
AugSortedBag.fold_le
fn fold_le(self, hi: K) -> TFold elements with key <= hi.
- cost: O(log n) expected
- empty:
id - traps: never
Examples:
var b: AugSortedBag<Int, Int> = AugSortedBag((x, y) => x + y, 0, k => k); b.add(3); b.add(1); b.add(3); b.fold_le(3) == 7
AugSortedBag.fold_ge
fn fold_ge(self, lo: K) -> TFold elements with key >= lo.
- cost: O(log n) expected
- empty:
id - traps: never
Examples:
var b: AugSortedBag<Int, Int> = AugSortedBag((x, y) => x + y, 0, k => k); b.add(3); b.add(1); b.add(3); b.fold_ge(2) == 6
AugSortedBag.fold_gt
fn fold_gt(self, lo: K) -> TFold elements with key > lo.
- cost: O(log n) expected
- empty:
id - traps: never
Examples:
var b: AugSortedBag<Int, Int> = AugSortedBag((x, y) => x + y, 0, k => k); b.add(3); b.add(1); b.add(3); b.fold_gt(1) == 6 and b.fold_gt(3) == 0
AugSortedBag.fold_between
fn fold_between(self, lo: K, hi: K) -> TFold elements with key in [lo, hi).
lo >= hi selects nothing and gives id.
- cost: O(log n) expected
- empty:
id, also whenlo >= hi - traps: never
Examples:
var b: AugSortedBag<Int, Int> = AugSortedBag((x, y) => x + y, 0, k => k); b.add(3); b.add(1); b.add(3); b.fold_between(1, 3) == 1 and b.fold_between(2, 4) == 6
AugSortedBag.each
fn each(self) -> yields KYield all elements in ascending order.
- cost: O(1) amortized per step
- empty: yields nothing
- order: ascending, each key repeated by its count
- traps: never
Examples:
var b: AugSortedBag<Int, Int> = AugSortedBag((x, y) => x + y, 0, k => k); b.add(3); b.add(1); b.add(3); b.each().collect() == [1, 3, 3]
AugSortedSet
pub struct AugSortedSet<K, T>Monoid-augmented ordered unique set maintaining op over leaf(k) on every subtree (W10 operation values).
Covers dynamic range sums and consecutive-gap monoids (cf2066e) in O(log n).
Every fold combines leaf(k) over the chosen keys in ascending order, starting from id;
op need not be commutative. An empty selection folds to id.
AugSortedSet.new
fn new(op: (T, T) -> T, id: T, leaf: K -> T) -> AugSortedSet<K, T>Create an empty AugSortedSet<K, T> with associative op, identity id, and key map leaf.
- cost: O(1)
- traps: never
Examples:
var s: AugSortedSet<Int, Int> = AugSortedSet((x, y) => x + y, 0, k => k); s.all == 0
AugSortedSet.reserve
fn reserve(mut self, cap: Int)Preallocate treap node pool for at least cap keys.
- cost: O(cap) when the pool grows, O(1) otherwise
- traps: never
Examples:
var s: AugSortedSet<Int, Int> = AugSortedSet((x, y) => x + y, 0, k => k); s.reserve(100); s.len == 0
AugSortedSet.len
fn len(self) -> IntNumber of distinct keys.
- cost: O(1)
- traps: never
Examples:
var s: AugSortedSet<Int, Int> = AugSortedSet((x, y) => x + y, 0, k => k); s.add(3); s.add(3); s.len == 1
AugSortedSet.is_empty
fn is_empty(self) -> BoolWhether the set is empty.
- cost: O(1)
- traps: never
Examples:
var s: AugSortedSet<Int, Int> = AugSortedSet((x, y) => x + y, 0, k => k); s.is_empty
AugSortedSet.all
fn all(self) -> TFold of all keys in the set.
- cost: O(1)
- empty:
id - traps: never
Examples:
var s: AugSortedSet<Int, Int> = AugSortedSet((x, y) => x + y, 0, k => k); s.add(3); s.add(1); s.add(3); s.all == 4
AugSortedSet.add
fn add(mut self, x: K) -> BoolInsert x; returns true if x was new.
- cost: O(log n) expected
- traps: never
Examples:
var s: AugSortedSet<Int, Int> = AugSortedSet((x, y) => x + y, 0, k => k); s.add(3) and not s.add(3)
AugSortedSet.remove
fn remove(mut self, x: K) -> BoolRemove x; returns true if x was present.
- cost: O(log n) expected
- traps: never
Examples:
var s: AugSortedSet<Int, Int> = AugSortedSet((x, y) => x + y, 0, k => k); s.add(3); s.remove(3) and not s.remove(3) and s.all == 0
AugSortedSet.contains
fn contains(self, x: K) -> BoolWhether x is present.
- cost: O(log n) expected
- traps: never
Examples:
var s: AugSortedSet<Int, Int> = AugSortedSet((x, y) => x + y, 0, k => k); s.add(3); s.contains(3) and not s.contains(1)
AugSortedSet.rank
fn rank(self, k: K) -> IntNumber of keys strictly less than k.
- cost: O(log n) expected
- empty:
0 - traps: never
Examples:
var s: AugSortedSet<Int, Int> = AugSortedSet((x, y) => x + y, 0, k => k); s.add(3); s.add(1); s.rank(3) == 1 and s.rank(4) == 2
AugSortedSet.nth
fn nth(self, i: Int) -> ?KThe i-th smallest key (0-based), or None.
None for any i outside 0..len.
- cost: O(log n) expected
- empty:
None - traps: never
Examples:
var s: AugSortedSet<Int, Int> = AugSortedSet((x, y) => x + y, 0, k => k); s.add(3); s.add(1); s.nth(1) == Some(3) and s.nth(2) == None
AugSortedSet.first
fn first(self) -> ?KSmallest key, or None. O(1), kept current by every update.
- cost: O(1)
- empty:
None - ties: none: keys are distinct
- traps: never
Examples:
var s: AugSortedSet<Int, Int> = AugSortedSet((x, y) => x + y, 0, k => k); s.add(3); s.add(1); s.first == Some(1)
AugSortedSet.last
fn last(self) -> ?KLargest key, or None. O(1), kept current by every update.
- cost: O(1)
- empty:
None - ties: none: keys are distinct
- traps: never
Examples:
var s: AugSortedSet<Int, Int> = AugSortedSet((x, y) => x + y, 0, k => k); s.add(3); s.add(1); s.last == Some(3)
AugSortedSet.fold_lt
fn fold_lt(self, hi: K) -> TFold keys < hi.
- cost: O(log n) expected
- empty:
id - traps: never
Examples:
var s: AugSortedSet<Int, Int> = AugSortedSet((x, y) => x + y, 0, k => k); s.add(1); s.add(3); s.add(5); s.fold_lt(5) == 4
AugSortedSet.fold_le
fn fold_le(self, hi: K) -> TFold keys <= hi.
- cost: O(log n) expected
- empty:
id - traps: never
Examples:
var s: AugSortedSet<Int, Int> = AugSortedSet((x, y) => x + y, 0, k => k); s.add(1); s.add(3); s.add(5); s.fold_le(5) == 9
AugSortedSet.fold_ge
fn fold_ge(self, lo: K) -> TFold keys >= lo.
- cost: O(log n) expected
- empty:
id - traps: never
Examples:
var s: AugSortedSet<Int, Int> = AugSortedSet((x, y) => x + y, 0, k => k); s.add(1); s.add(3); s.add(5); s.fold_ge(3) == 8
AugSortedSet.fold_gt
fn fold_gt(self, lo: K) -> TFold keys > lo.
- cost: O(log n) expected
- empty:
id - traps: never
Examples:
var s: AugSortedSet<Int, Int> = AugSortedSet((x, y) => x + y, 0, k => k); s.add(1); s.add(3); s.add(5); s.fold_gt(3) == 5
AugSortedSet.fold_between
fn fold_between(self, lo: K, hi: K) -> TFold keys in [lo, hi).
lo >= hi selects nothing and gives id.
- cost: O(log n) expected
- empty:
id, also whenlo >= hi - traps: never
Examples:
var s: AugSortedSet<Int, Int> = AugSortedSet((x, y) => x + y, 0, k => k); s.add(1); s.add(3); s.add(5); s.fold_between(1, 5) == 4 and s.fold_between(4, 2) == 0
AugSortedSet.each
fn each(self) -> yields KYield all keys in ascending order.
- cost: O(1) amortized per step
- empty: yields nothing
- order: ascending
- traps: never
Examples:
var s: AugSortedSet<Int, Int> = AugSortedSet((x, y) => x + y, 0, k => k); s.add(3); s.add(1); s.each().collect() == [1, 3]
BucketCount
pub struct BucketCountO(1) point add, O(sqrt(N)) k-th order statistic over an integer value range r.
Designed as a Mo's algorithm companion for value-range frequency tables.
N is r.len; the table keeps one count per value and one per block of about sqrt(N)
values. Writes outside r trap; reads outside r see a count of 0.
BucketCount.new
fn new(r: Range<Int>) -> BucketCountO(r.len). Create an empty bucketed frequency table over r.
- cost: O(r.len)
- empty: an empty
rgives a table every write traps on - traps: never
Examples:
var b = BucketCount(0..10); b.len == 0
BucketCount.add
fn add(mut self, x: Int, delta: Int = 1)O(1). Add delta (default 1; may be negative) copies of x.
A negative delta removes copies; the count of x may not go below 0.
- cost: O(1)
- traps: when
xis not inr; when the count ofxwould become negative
Examples:
var b = BucketCount(0..10); b.add(3); b.add(7, 2); b.count(7) == 2 and b.len == 3
BucketCount.remove
fn remove(mut self, x: Int, delta: Int = 1)O(1). Remove delta (default 1) copies of x.
The same as add(x, -delta).
- cost: O(1)
- traps: when
xis not inr; when the count ofxwould become negative
Examples:
var b = BucketCount(0..10); b.add(7, 2); b.remove(7); b.count(7) == 1
BucketCount.count
fn count(self, x: Int) -> IntO(1). Multiplicity of x.
- cost: O(1)
- traps: never; an
xoutsiderhas count 0
Examples:
var b = BucketCount(0..10); b.add(3); b.count(3) == 1 and b.count(4) == 0 and b.count(99) == 0
BucketCount.count_lt
fn count_lt(self, x: Int) -> IntO(sqrt(N)). Number of elements strictly less than x.
Any x works: below r gives 0, at or above r.end gives len.
- cost: O(sqrt(N))
- empty:
0 - traps: never
Examples:
var b = BucketCount(0..10); b.add(3); b.add(7, 2); b.count_lt(7) == 1 and b.count_lt(8) == 3
BucketCount.kth
fn kth(self, k: Int) -> IntO(sqrt(N)). The k-th smallest element, 0-based like nth: kth(0) is the smallest.
Copies count: with elements 3, 7, 7, kth(1) and kth(2) are both 7.
- cost: O(sqrt(N))
- ties: none: the
k-th element is one value - traps: when
kis not in0..len
Examples:
var b = BucketCount(0..10); b.add(3); b.add(7, 2); b.kth(0) == 3 and b.kth(1) == 7 and b.kth(2) == 7
BucketCount.len
fn len(self) -> Int- cost: O(1)
- traps: never
Examples:
var b = BucketCount(0..10); b.add(4, 3); b.len == 3
BucketCount.is_empty
fn is_empty(self) -> BoolO(1). Whether the table is empty.
- cost: O(1)
- traps: never
Examples:
var b = BucketCount(0..10); b.add(4); b.remove(4); b.is_empty
BucketCount.clear
fn clear(mut self)O(r.len). Reset all counts to zero.
- cost: O(r.len)
- traps: never
Examples:
var b = BucketCount(0..10); b.add(4); b.clear(); b.count(4) == 0 and b.len == 0
SortedRange
pub struct SortedRange<K>The keys of a SortedBag or SortedSet inside a range, made by range(r). A view: it stores
the bounds and lends the container, and allocates nothing. for x in s.range(r) iterates
each(). Copies of one key in a SortedBag are all inside or all outside, so nothing here
has a tie to break. n is the container's len, k the number of keys visited.
SortedRange.first
fn first(self) -> ?KThe smallest key in the range.
- cost: O(log n) expected
- empty:
None - ties: copies of a key are equal, so any is the answer
- traps: never
Examples:
SortedSet.of([1, 3, 7]).range(2..).first() == Some(3)
SortedRange.last
fn last(self) -> ?KThe largest key in the range.
- cost: O(log n) expected
- empty:
None - ties: copies of a key are equal, so any is the answer
- traps: never
Examples:
SortedSet.of([1, 3, 7]).range(..=6).last() == Some(3)
SortedRange.len
fn len(self) -> IntThe number of keys in the range, counting copies.
- cost: O(log n) expected
- empty: 0
- traps: never
Examples:
SortedBag.of([1, 3, 3, 7]).range(3..=3).len() == 2
SortedRange.is_empty
fn is_empty(self) -> BoolTrue when the range holds no key.
- cost: O(log n) expected
- empty:
true - traps: never
Examples:
SortedSet.of([1, 7]).range(2..7).is_empty()
SortedRange.each
fn each(self) -> yields KThe keys in ascending order, copies included.
- cost: O(log n + k) expected for
kkeys visited - empty: yields nothing
- order: ascending
- traps: never
Examples:
SortedBag.of([1, 3, 3, 7]).range(2..).each().collect() == [3, 3, 7]
SortedRange.rev
fn rev(self) -> yields KThe keys in descending order, copies included.
- cost: O(log n + k) expected for
kkeys visited - empty: yields nothing
- order: descending
- traps: never
Examples:
SortedSet.of([1, 3, 7]).range(..7).rev().collect() == [3, 1]