bitset
One bit per position of D, in ceil(K / 64) words.
Generated from spec/std/bitset.cp by cpl doc --format json.
Bitset
pub struct Bitset<D>One bit per position of D, in ceil(K / 64) words.
Bitset<D> is an explicit type you ask for; [D]Bool stays one byte
per element and never turns into this behind your back.
Single-bit operations are O(1); whole-set operations are O(K / 64).
Bitset.new
fn new() -> Bitset<D>The empty set, every word zero; the same set as empty().
- cost: O(K / 64) time and space
- traps: never
Examples:
domain D = 0..10; Bitset<D>().len == 0
Bitset.empty
fn empty() -> Bitset<D>The empty set, matching Subset<D>.empty (a call here: it is O(K / 64)); the same as new().
- cost: O(K / 64) time and space
- traps: never
Examples:
domain D = 0..10; Bitset<D>.empty().is_empty
Bitset.full
fn full() -> Bitset<D>The full set containing every position of D, matching Subset<D>.full. No bit past the last
position is ever set, so len is D.K.
- cost: O(K / 64) time and space
- traps: never
Examples:
domain D = 0..10; Bitset<D>.full().len == 10
Bitset.single
fn single(i: D) -> Bitset<D>The singleton set {i}, matching Subset<D>.single(i).
- cost: O(K / 64) time and space
- traps: never
Examples:
domain D = 0..10; Bitset<D>.single(D(4)).each().collect() == [D(4)]
Bitset.from
fn from(a: [D]Bool) -> Bitset<D>The set of positions where a is true.
- cost: O(K) time, O(K / 64) space
- empty: the empty set when no element is true
- traps: never
Examples:
domain D = 0..10; Bitset<D>.from([D] v => Int(v) % 4 == 0).each().collect() == [D(0), D(4), D(8)]
Bitset.of
fn of(xs: List<D>) -> Bitset<D>Build a bitset from a list or generator of positions D. Repeated positions are set once.
- cost: O(K / 64 + xs.len) time, O(K / 64) space
- empty: the empty set
- traps: never
Examples:
domain D = 0..10; Bitset<D>.of([D(3), D(1), D(3)]).each().collect() == [D(1), D(3)]
Bitset.contains
fn contains(self, i: D) -> BoolWhether position i is set; i in b calls it.
- cost: O(1)
- traps: never
Examples:
domain D = 0..10; let b = Bitset<D>.single(D(4)); b.contains(D(4)) and not b.contains(D(5))
Bitset.add
fn add(mut self, i: D) -> BoolSet the bit at position i; returns true if i was not already set (matches Set.add).
- cost: O(1)
- traps: never
Examples:
domain D = 0..10; var b = Bitset<D>(); let x = b.add(D(2)); let y = b.add(D(2)); x and not y and b.len == 1
Bitset.remove
fn remove(mut self, i: D) -> BoolClear the bit at position i; returns true if i was set (matches Set.remove).
- cost: O(1)
- traps: never
Examples:
domain D = 0..10; var b = Bitset<D>.single(D(2)); let x = b.remove(D(2)); let y = b.remove(D(2)); x and not y and b.is_empty
Bitset.toggle
fn toggle(mut self, i: D)Flip the bit at position i: set it if clear, clear it if set.
- cost: O(1)
- traps: never
Examples:
domain D = 0..10; var b = Bitset<D>.single(D(2)); b.toggle(D(2)); b.toggle(D(5)); b.each().collect() == [D(5)]
Bitset.with
fn with(self, i: D) -> Bitset<D>A copy of self with i added; self is unchanged.
- cost: O(K / 64) time and space
- traps: never
Examples:
domain D = 0..10; Bitset<D>.single(D(1)).with(D(3)).each().collect() == [D(1), D(3)]
Bitset.without
fn without(self, i: D) -> Bitset<D>A copy of self with i removed; self is unchanged. Removing a non-member copies.
- cost: O(K / 64) time and space
- traps: never
Examples:
domain D = 0..10; Bitset<D>.full().without(D(0)).len == 9
Bitset.set
fn set(self, i: D, on: Bool) -> Bitset<D>A copy of self with i added if on or removed otherwise, matching Subset<D>.set.
- cost: O(K / 64) time and space
- traps: never
Examples:
domain D = 0..10; Bitset<D>.single(D(1)).set(D(1), false).is_emptydomain D = 0..10; Bitset<D>().set(D(7), true).each().collect() == [D(7)]
Bitset.complement
fn complement(self) -> Bitset<D>The complement of self within D, matching Subset<D>.complement; bits past the last position
stay clear.
- cost: O(K / 64) time and space
- traps: never
Examples:
domain D = 0..10; Bitset<D>.of([D(1), D(3), D(8)]).complement().len == 7
Bitset.clear
fn clear(mut self)Remove every position from the set.
- cost: O(K / 64)
- traps: never
Examples:
domain D = 0..10; var b = Bitset<D>.full(); b.clear(); b.is_empty
Bitset.any
fn any(self, pred: D -> Bool) -> BoolTrue when some position in this set satisfies pred. Visits members in increasing order and stops
at the first that satisfies it.
- cost: O(K / 64 + visited) words scanned and calls of
pred - empty:
false - traps: never (beyond what
predtraps on)
Examples:
domain D = 0..10; Bitset<D>.of([D(1), D(3), D(8)]).any(d => Int(d) > 5)domain D = 0..10; not Bitset<D>().any(d => true)
Bitset.len
fn len(self) -> IntThe number of positions in the set; the count is kept current by every update.
- cost: O(1)
- traps: never
Examples:
domain D = 0..10; Bitset<D>.of([D(1), D(3), D(8)]).len == 3
Bitset.count
fn count(self) -> IntThe same number as len, under the name C++ gives it.
- cost: O(1)
- traps: never
Examples:
domain D = 0..10; Bitset<D>.of([D(1), D(3), D(8)]).count == 3
Bitset.is_empty
fn is_empty(self) -> BoolWhether the set has no members. O(1): the count is kept current by every update.
- cost: O(1)
- traps: never
Examples:
domain D = 0..10; Bitset<D>().is_empty and not Bitset<D>.full().is_empty
Bitset.first
fn first(self) -> ?DThe smallest position in the set, or None.
- cost: O(K / 64)
- empty:
None - ties: None possible; positions are distinct
- traps: never
Examples:
domain D = 0..10; Bitset<D>.of([D(1), D(3), D(8)]).first() == Some(D(1))
Bitset.find
fn find(self, pred: D -> Bool) -> ?DThe smallest position in the set satisfying pred, or None, as seq.find. Members are
visited in increasing order, so pred is called only up to the answer.
- cost: O(K / 64 + visited)
- empty:
None - ties: None possible; the smallest qualifying position wins
- traps: never (beyond what
predtraps on)
Examples:
domain D = 0..10; Bitset<D>.of([D(1), D(3), D(8)]).find(d => Int(d) > 2) == Some(D(3))
Bitset.rfind
fn rfind(self, pred: D -> Bool) -> ?DThe largest position in the set satisfying pred, or None. Members are
visited in decreasing order.
- cost: O(K / 64 + visited)
- empty:
None - ties: None possible; the largest qualifying position wins
- traps: never (beyond what
predtraps on)
Examples:
domain D = 0..10; Bitset<D>.of([D(1), D(3), D(8)]).rfind(d => Int(d) < 8) == Some(D(3))
Bitset.union
fn union(mut self, o: Bitset<D>)Replace self with self | o in place, with no allocation.
- cost: O(K / 64)
- traps: never
Examples:
domain D = 0..10; var b = Bitset<D>.single(D(1)); b.union(Bitset<D>.single(D(2))); b.len == 2
Bitset.intersect
fn intersect(mut self, o: Bitset<D>)Replace self with self & o in place, with no allocation.
- cost: O(K / 64)
- traps: never
Examples:
domain D = 0..10; var b = Bitset<D>.of([D(1), D(2)]); b.intersect(Bitset<D>.single(D(2))); b.each().collect() == [D(2)]
Bitset.subtract
fn subtract(mut self, o: Bitset<D>)Clear every bit set in o from self in place: self - o.
- cost: O(K / 64)
- traps: never
Examples:
domain D = 0..10; var b = Bitset<D>.of([D(1), D(2)]); b.subtract(Bitset<D>.single(D(2))); b.each().collect() == [D(1)]
Bitset.symmetric
fn symmetric(mut self, o: Bitset<D>)Replace self with self ^ o in place.
- cost: O(K / 64)
- traps: never
Examples:
domain D = 0..10; var b = Bitset<D>.of([D(1), D(2)]); b.symmetric(Bitset<D>.of([D(2), D(3)])); b.each().collect() == [D(1), D(3)]
Bitset.bitor
fn bitor(self, o: Bitset<D>) -> Bitset<D>a | b: a new set of the positions in either set.
- cost: O(K / 64) time and space
- traps: never
Examples:
domain D = 0..10; (Bitset<D>.single(D(1)) | Bitset<D>.single(D(2))).len == 2
Bitset.bitand
fn bitand(self, o: Bitset<D>) -> Bitset<D>a & b: a new set of the positions in both sets.
- cost: O(K / 64) time and space
- traps: never
Examples:
domain D = 0..10; (Bitset<D>.of([D(1), D(2)]) & Bitset<D>.of([D(2), D(3)])).each().collect() == [D(2)]
Bitset.bitxor
fn bitxor(self, o: Bitset<D>) -> Bitset<D>a ^ b: a new set of the positions in exactly one of the sets.
- cost: O(K / 64) time and space
- traps: never
Examples:
domain D = 0..10; (Bitset<D>.of([D(1), D(2)]) ^ Bitset<D>.of([D(2), D(3)])).each().collect() == [D(1), D(3)]
Bitset.meets
fn meets(self, o: Bitset<D>) -> BoolDo the two sets share a position? Stops at the first shared word; (a & b).len > 0 without
building a & b.
- cost: O(K / 64), less on an early hit
- traps: never
Examples:
domain D = 0..10; Bitset<D>.of([D(1), D(2)]).meets(Bitset<D>.of([D(2), D(3)]))domain D = 0..10; not Bitset<D>.single(D(1)).meets(Bitset<D>.single(D(2)))
Bitset.shifted
fn shifted(self, k: Int) -> Bitset<D>A new set with every position k places up (down for a negative k); positions that leave D
are dropped. Position v moves to the position whose ordinal is v's plus k.
- cost: O(K / 64) time and space, for any
k - traps: never
Examples:
domain D = 0..10; Bitset<D>.of([D(1), D(3), D(8)]).shifted(2).each().collect() == [D(3), D(5)]domain D = 0..10; Bitset<D>.of([D(1), D(3), D(8)]).shifted(-2).each().collect() == [D(1), D(6)]
Bitset.shift_up
fn shift_up(mut self, k: Int)Shift every position k >= 0 places up in place; bits past D drop.
- cost: O(K / 64)
- traps: when
k < 0
Examples:
domain D = 0..10; var b = Bitset<D>.of([D(1), D(3), D(8)]); b.shift_up(1); b.each().collect() == [D(2), D(4), D(9)]
Bitset.shift_or
fn shift_or(mut self, k: Int)In-place self |= self << k for k >= 0, with zero allocation: the knapsack step "every
reachable sum, and every reachable sum plus k". Bits past D drop.
- cost: O(K / 64)
- traps: when
k < 0
Examples:
domain D = 0..10; var b = Bitset<D>.of([D(1), D(3), D(8)]); b.shift_or(2); b.each().collect() == [D(1), D(3), D(5), D(8)]
Bitset.each
fn each(self) -> yields DThe positions in the set, in increasing order; for v in b walks the same sequence.
- cost: O(K / 64 + len) to walk, O(1) per member amortized
- empty: yields nothing
- order: increasing
- traps: never
Examples:
domain D = 0..10; Bitset<D>.of([D(8), D(1)]).each().collect() == [D(1), D(8)]
Bitset.next
fn next(self, i: D) -> ?DThe first position in the set at or after i, or None.
- cost: O(K / 64)
- empty:
None - traps: never
Examples:
domain D = 0..10; Bitset<D>.of([D(1), D(3), D(8)]).next(D(3)) == Some(D(3))domain D = 0..10; Bitset<D>.of([D(1), D(3), D(8)]).next(D(4)) == Some(D(8))domain D = 0..10; Bitset<D>.of([D(1), D(3), D(8)]).next(D(9)) == None
Bitset.prev
fn prev(self, i: D) -> ?DThe last position in the set at or before i, or None (the mirror of next).
- cost: O(K / 64)
- empty:
None - traps: never
Examples:
domain D = 0..10; Bitset<D>.of([D(1), D(3), D(8)]).prev(D(3)) == Some(D(3))domain D = 0..10; Bitset<D>.of([D(1), D(3), D(8)]).prev(D(2)) == Some(D(1))domain D = 0..10; Bitset<D>.of([D(1), D(3), D(8)]).prev(D(0)) == None
Bitset.count_below
fn count_below(self, i: D) -> IntThe number of positions in the set strictly before i.
- cost: O(K / 64)
- empty: zero
- traps: never
Examples:
domain D = 0..10; Bitset<D>.of([D(1), D(3), D(8)]).count_below(D(8)) == 2
Bitset.subset_sums
fn subset_sums(weights: List<Int>) -> Bitset<D>All subset sums in 0..D.K reachable from non-negative weights: the position with ordinal s
is set exactly when some sub-multiset of weights sums to s. The empty sub-multiset makes 0
reachable; sums of D.K or more are dropped.
Groups duplicate weights with binary carries so the work is O(K sqrt(S) / 64).
- cost: O(K sqrt(S) / 64) time, where S is the sum of
weights; O(K / 64) space - empty:
{D.first}(just the sum 0), or the empty set whenDis empty - traps: when a weight is negative
Examples:
domain S = 0..=10; Bitset<S>.subset_sums([3, 5, 5]).each().map(s => Int(s)).collect() == [0, 3, 5, 8, 10]
Bitset.shift_down
fn shift_down(mut self, k: Int)Shift all bits down by k >= 0 positions in place (i -> i - k); bits below D drop.
- cost: O(K / 64)
- traps: when
k < 0
Examples:
domain D = 0..10; var b = Bitset<D>.of([D(1), D(3), D(8)]); b.shift_down(1); b.each().collect() == [D(0), D(2), D(7)]
Bitset.count_range
fn count_range(self, r: Range<D>) -> IntCount set bits in r (accepts cut ranges via decision 124).
- cost: O(r.len / 64 + 1)
- empty: zero
- traps: never
Examples:
domain D = 0..10; Bitset<D>.of([D(1), D(3), D(8)]).count_range(1..8) == 2
Bitset.set_range
fn set_range(mut self, r: Range<D>, on: Bool = true)Set (or, with on: false, clear) every bit in r in place.
- cost: O(r.len / 64 + 1)
- empty: no effect
- traps: never
Examples:
domain D = 0..10; var b = Bitset<D>.of([D(1), D(3), D(8)]); b.set_range(2..5); b.len == 5domain D = 0..10; var b = Bitset<D>.of([D(1), D(3), D(8)]); b.set_range(0..4, on: false); b.each().collect() == [D(8)]
Bitset.flip_range
fn flip_range(mut self, r: Range<D>)Flip every bit in r in place.
- cost: O(r.len / 64 + 1)
- empty: no effect
- traps: never
Examples:
domain D = 0..10; var b = Bitset<D>.of([D(1), D(3), D(8)]); b.flip_range(0..4); b.each().collect() == [D(0), D(2), D(8)]
Bitset.nth
fn nth(self, k: Int) -> ?DThe k-th set position (0-based, in increasing order), or None if k >= len.
- cost: O(K / 64)
- empty:
None - traps: when
k < 0
Examples:
domain D = 0..10; Bitset<D>.of([D(1), D(3), D(8)]).nth(2) == Some(D(8))domain D = 0..10; Bitset<D>.of([D(1), D(3), D(8)]).nth(3) == None
Bitset.each_rev
fn each_rev(self) -> yields DThe set positions in descending order.
- cost: O(K / 64 + len) to walk
- empty: yields nothing
- order: decreasing
- traps: never
Examples:
domain D = 0..10; Bitset<D>.of([D(1), D(3), D(8)]).each_rev().collect() == [D(8), D(3), D(1)]
Bitset.recount
fn recount(mut self)Bitset.trim
fn trim(mut self)DynBitset
pub struct DynBitsetRuntime-sized 64-bit word bitset over 0..cap when the width is computed dynamically without a domain.
Single-bit ops are O(1); word-parallel ops are O(cap / 64).
DynBitset.recount
fn recount(mut self)DynBitset.trim
fn trim(mut self)DynBitset.new
fn new(cap: Int) -> DynBitsetCreate an all-zero DynBitset of width cap: bits 0..cap.
- cost: O(cap / 64) time and space
- traps: when
cap < 0
Examples:
DynBitset(10).len == 0
DynBitset.full
fn full(cap: Int) -> DynBitsetCreate an all-one DynBitset of width cap; bits at or above cap stay clear.
- cost: O(cap / 64) time and space
- traps: when
cap < 0
Examples:
DynBitset.full(10).len == 10
DynBitset.cap
fn cap(self) -> IntThe bit capacity: valid indices are 0..cap.
- cost: O(1)
- traps: never
Examples:
DynBitset(10).cap == 10
DynBitset.len
fn len(self) -> IntThe number of set bits, kept current by every update.
- cost: O(1)
- traps: never
Examples:
var d = DynBitset(10); d.add(1); d.add(3); d.len == 2
DynBitset.is_empty
fn is_empty(self) -> BoolWhether no bits are set, kept current by every update.
- cost: O(1)
- traps: never
Examples:
DynBitset(10).is_empty and not DynBitset.full(1).is_empty
DynBitset.contains
fn contains(self, i: Int) -> BoolWhether bit i is set.
- cost: O(1)
- traps: when
iis not in0..cap
Examples:
var d = DynBitset(10); d.add(3); d.contains(3) and not d.contains(4)
DynBitset.set
fn set(mut self, i: Int, on: Bool = true)Set bit i to on in place (W8 IndexSet backing b[i] = on).
- cost: O(1)
- traps: when
iis not in0..cap
Examples:
var d = DynBitset(10); d.set(4); d.set(5, true); d.set(4, false); d.each().collect() == [5]
DynBitset.add
fn add(mut self, i: Int) -> BoolSet bit i to 1; returns true if bit i was previously 0 (matches Bitset.add).
- cost: O(1)
- traps: when
iis not in0..cap
Examples:
var d = DynBitset(10); let x = d.add(2); let y = d.add(2); x and not y
DynBitset.remove
fn remove(mut self, i: Int) -> BoolClear bit i to 0; returns true if bit i was previously 1 (matches Bitset.remove).
- cost: O(1)
- traps: when
iis not in0..cap
Examples:
var d = DynBitset(10); d.add(2); let x = d.remove(2); let y = d.remove(2); x and not y and d.is_empty
DynBitset.toggle
fn toggle(mut self, i: Int)Flip bit i.
- cost: O(1)
- traps: when
iis not in0..cap
Examples:
var d = DynBitset(10); d.toggle(6); d.toggle(6); d.toggle(7); d.each().collect() == [7]
DynBitset.clear
fn clear(mut self)Clear all bits; the capacity is unchanged.
- cost: O(cap / 64)
- traps: never
Examples:
var d = DynBitset.full(10); d.clear(); d.is_empty and d.cap == 10
DynBitset.resize
fn resize(mut self, new_cap: Int)Resize to new_cap bits, zero-filling any new high bits. Shrinking drops the bits at or above
new_cap (and len drops with them).
- cost: O(new_cap / 64) time and space
- traps: when
new_cap < 0
Examples:
var d = DynBitset(10); d.add(1); d.add(8); d.resize(4); d.len == 1 and d.cap == 4var d = DynBitset.full(2); d.resize(5); d.each().collect() == [0, 1]
DynBitset.first
fn first(self) -> ?IntThe smallest set bit index, or None if empty.
- cost: O(cap / 64)
- empty:
None - ties: None possible; the smallest index wins
- traps: never
Examples:
var d = DynBitset(10); d.add(8); d.add(3); d.first() == Some(3)DynBitset(10).first() == None
DynBitset.last
fn last(self) -> ?IntThe largest set bit index, or None if empty.
- cost: O(cap / 64)
- empty:
None - ties: None possible; the largest index wins
- traps: never
Examples:
var d = DynBitset(10); d.add(8); d.add(3); d.last() == Some(8)
DynBitset.next
fn next(self, i: Int) -> ?IntThe smallest set bit >= i, or None.
- cost: O(cap / 64)
- empty:
None - traps: when
iis not in0..=cap
Examples:
var d = DynBitset(10); d.add(3); d.add(8); d.next(3) == Some(3) and d.next(4) == Some(8) and d.next(9) == None
DynBitset.prev
fn prev(self, i: Int) -> ?IntThe largest set bit <= i, or None; i itself counts, as in Bitset.prev.
- cost: O(cap / 64)
- empty:
None - traps: when
iis not in0..cap
Examples:
var d = DynBitset(10); d.add(1); d.add(3); d.prev(3) == Some(3) and d.prev(2) == Some(1) and d.prev(0) == None
DynBitset.count_below
fn count_below(self, i: Int) -> IntThe number of set bits strictly below i.
- cost: O(cap / 64)
- empty: zero
- traps: when
iis not in0..=cap
Examples:
var d = DynBitset(10); d.add(1); d.add(3); d.add(8); d.count_below(8) == 2
DynBitset.count_range
fn count_range(self, r: Range<Int>) -> IntThe number of set bits in r.
- cost: O(r.len / 64 + 1)
- empty: zero
- traps: when
ris non-empty and reaches outside0..cap
Examples:
var d = DynBitset(10); d.add(1); d.add(3); d.add(8); d.count_range(1..8) == 2
DynBitset.nth
fn nth(self, k: Int) -> ?IntThe k-th set bit index (0-based, in increasing order), or None if k >= len.
- cost: O(cap / 64)
- empty:
None - traps: when
k < 0
Examples:
var d = DynBitset(10); d.add(1); d.add(3); d.add(8); d.nth(1) == Some(3) and d.nth(3) == None
DynBitset.union
fn union(mut self, other: DynBitset)In-place bitwise OR (self |= other).
- cost: O(cap / 64)
- traps: when
other.cap != self.cap
Examples:
var a = DynBitset(4); a.add(0); var b = DynBitset(4); b.add(2); a.union(b); a.each().collect() == [0, 2]
DynBitset.intersect
fn intersect(mut self, other: DynBitset)In-place bitwise AND (self &= other).
- cost: O(cap / 64)
- traps: when
other.cap != self.cap
Examples:
var a = DynBitset.full(4); var b = DynBitset(4); b.add(2); a.intersect(b); a.each().collect() == [2]
DynBitset.subtract
fn subtract(mut self, other: DynBitset)In-place set difference (self &= ~other).
- cost: O(cap / 64)
- traps: when
other.cap != self.cap
Examples:
var a = DynBitset.full(4); var b = DynBitset(4); b.add(2); a.subtract(b); a.each().collect() == [0, 1, 3]
DynBitset.symmetric
fn symmetric(mut self, other: DynBitset)In-place bitwise XOR (self ^= other).
- cost: O(cap / 64)
- traps: when
other.cap != self.cap
Examples:
var a = DynBitset(4); a.add(1); a.add(2); var b = DynBitset(4); b.add(2); b.add(3); a.symmetric(b); a.each().collect() == [1, 3]
DynBitset.meets
fn meets(self, other: DynBitset) -> BoolWhether self and other share a set bit; stops at the first shared word.
- cost: O(cap / 64), less on an early hit
- traps: when
other.cap != self.cap
Examples:
var a = DynBitset(4); a.add(1); var b = DynBitset.full(4); a.meets(b) and not a.meets(DynBitset(4))
DynBitset.shift_up
fn shift_up(mut self, k: Int)Shift all bits up by k >= 0 in place (i -> i + k); bits reaching cap or beyond drop.
- cost: O(cap / 64)
- traps: when
k < 0
Examples:
var d = DynBitset(10); d.add(1); d.add(3); d.add(8); d.shift_up(2); d.each().collect() == [3, 5]
DynBitset.shift_down
fn shift_down(mut self, k: Int)Shift all bits down by k >= 0 in place (i -> i - k); bits falling below 0 drop.
- cost: O(cap / 64)
- traps: when
k < 0
Examples:
var d = DynBitset(10); d.add(1); d.add(3); d.add(8); d.shift_down(2); d.each().collect() == [1, 6]
DynBitset.shift_or
fn shift_or(mut self, k: Int)In-place self |= (self << k) for k >= 0, with zero allocation; bits reaching cap drop.
- cost: O(cap / 64)
- traps: when
k < 0
Examples:
var d = DynBitset(10); d.add(1); d.add(3); d.add(8); d.shift_or(2); d.each().collect() == [1, 3, 5, 8]
DynBitset.each
fn each(self) -> yields IntThe set bit indices in ascending order; for i in d walks the same sequence.
- cost: O(cap / 64 + len) to walk
- empty: yields nothing
- order: increasing
- traps: never
Examples:
var d = DynBitset(10); d.add(8); d.add(1); d.each().collect() == [1, 8]
DynBitset.each_rev
fn each_rev(self) -> yields IntThe set bit indices in descending order.
- cost: O(cap / 64 + len) to walk
- empty: yields nothing
- order: decreasing
- traps: never
Examples:
var d = DynBitset(10); d.add(8); d.add(1); d.each_rev().collect() == [8, 1]
DynBitset.subset_sums
fn subset_sums(cap: Int, weights: List<Int>) -> DynBitsetAll subset sums in 0..cap reachable from weights: bit s is set exactly when some
sub-multiset of weights sums to s. The empty sub-multiset makes 0 reachable (when
cap > 0); sums of cap or more drop. Duplicate weights are grouped with binary carries, as in
Bitset.subset_sums.
- cost: O(cap sqrt(S) / 64) time, where S is the sum of
weights; O(cap / 64) space - empty: just bit 0 (None when
cap == 0) - traps: when
cap < 0or a weight is negative
Examples:
DynBitset.subset_sums(11, [3, 5, 5]).each().collect() == [0, 3, 5, 8, 10]
XorTrie
pub struct XorTrieO(bits) per op. Dynamic binary bitwise XOR trie multiset over non-negative bits-bit integers (default 60 bits).
XorTrie.child
fn child(self, node: Int, b: Int) -> IntXorTrie.leaf
fn leaf(self, x: Int) -> IntXorTrie.walk
fn walk(mut self, x: Int, d: Int, dd: Int)XorTrie.new
fn new(bits: Int = 60) -> XorTrieCreate an empty XorTrie over bits-bit non-negative integers (default 60): values in
0..2^bits.
- cost: O(1)
- traps: when
bitsis not in1..=62
Examples:
XorTrie(3).is_empty
XorTrie.reserve
fn reserve(mut self, nodes: Int)Reserve pool capacity for at least nodes trie nodes, so later adds do not reallocate; the
contents are unchanged.
- cost: O(nodes) time and space
- traps: when
nodes < 0
Examples:
var t = XorTrie(3); t.reserve(100); t.len == 0
XorTrie.len
fn len(self) -> IntThe total number of stored integers, with multiplicity.
- cost: O(1)
- traps: never
Examples:
var t = XorTrie(3); t.add(5); t.add(5); t.len == 2
XorTrie.is_empty
fn is_empty(self) -> BoolTrue when the trie holds no integers.
- cost: O(1)
- traps: never
Examples:
var t = XorTrie(3); t.add(5); t.remove(5); t.is_empty
XorTrie.add
fn add(mut self, x: Int)Insert one copy of x. x is stored as given, after any earlier xor_all: the mask applies
only to elements already present.
- cost: O(bits) time, up to
bitsnew nodes - traps: when
xis not in0..2^bits
Examples:
var t = XorTrie(3); t.add(5); t.add(5); t.count(5) == 2
XorTrie.remove
fn remove(mut self, x: Int) -> BoolRemove one copy of x; returns false if absent, leaving the trie unchanged.
- cost: O(bits)
- traps: never
Examples:
var t = XorTrie(3); t.add(5); let x = t.remove(5); let y = t.remove(5); x and not y
XorTrie.contains
fn contains(self, x: Int) -> BoolWhether x is present at least once.
- cost: O(bits)
- traps: never
Examples:
var t = XorTrie(3); t.add(5); t.contains(5) and not t.contains(4)
XorTrie.count
fn count(self, x: Int) -> IntThe multiplicity of x currently stored; zero when absent.
- cost: O(bits)
- traps: never
Examples:
var t = XorTrie(3); t.add(5); t.add(5); t.add(1); t.count(5) == 2 and t.count(2) == 0
XorTrie.xor_all
fn xor_all(mut self, mask: Int)Apply a lazy global XOR mask: every stored y becomes y ^ mask. Masks compose (xor_all(a)
then xor_all(b) is xor_all(a ^ b)).
- cost: O(1)
- traps: when
maskis not in0..2^bits
Examples:
var t = XorTrie(3); t.add(1); t.add(5); t.xor_all(1); t.contains(0) and t.contains(4) and not t.contains(1)
XorTrie.max_xor
fn max_xor(self, x: Int) -> ?IntThe maximum value of x ^ y over stored y, or None if empty.
- cost: O(bits)
- empty:
None - ties: None possible; the value is unique even when several
yreach it - traps: when
xis not in0..2^bits
Examples:
var t = XorTrie(3); t.add(1); t.add(5); t.add(6); t.max_xor(2) == Some(7)XorTrie(3).max_xor(2) == None
XorTrie.min_xor
fn min_xor(self, x: Int) -> ?IntThe minimum value of x ^ y over stored y, or None if empty.
- cost: O(bits)
- empty:
None - ties: None possible; the value is unique even when several
yreach it - traps: when
xis not in0..2^bits
Examples:
var t = XorTrie(3); t.add(1); t.add(5); t.add(6); t.min_xor(2) == Some(3)
XorTrie.count_xor_less
fn count_xor_less(self, x: Int, limit: Int) -> IntThe number of stored y (with multiplicity) with (x ^ y) < limit. A limit <= 0 gives 0 and
a limit >= 2^bits gives len.
- cost: O(bits)
- traps: when
xis not in0..2^bits
Examples:
var t = XorTrie(3); t.add(1); t.add(5); t.add(6); t.count_xor_less(2, 5) == 2
XorTrie.kth_xor
fn kth_xor(self, x: Int, k: Int) -> ?IntThe k-th smallest value of x ^ y over stored y (0-based, with multiplicity), or None if
k >= len.
- cost: O(bits)
- empty:
None - ties: equal values
x ^ y(copies of oney) each take their own rank - traps: when
k < 0orxis not in0..2^bits
Examples:
var t = XorTrie(3); t.add(1); t.add(5); t.add(6); t.kth_xor(2, 1) == Some(4)var t = XorTrie(3); t.add(1); t.add(5); t.add(6); t.kth_xor(2, 3) == None
XorTrie.mex_xor
fn mex_xor(self, x: Int = 0) -> IntThe smallest non-negative integer not present under XOR mask x (mex of {y ^ x}); 2^bits
when every value is present.
- cost: O(bits)
- empty: zero
- traps: when
xis not in0..2^bits
Examples:
var t = XorTrie(3); t.add(1); t.add(5); t.add(6); t.mex_xor() == 0 and t.mex_xor(1) == 1
XorTrie.extreme_xor
fn extreme_xor(self, x: Int, want: Int) -> ?IntXorTrie.clear
fn clear(mut self)Remove all elements and the global mask, keeping bits and the reserved pool.
- cost: O(1)
- traps: never
Examples:
var t = XorTrie(3); t.add(5); t.clear(); t.is_empty and not t.contains(5)
Bitset<D>
impl Sub for Bitset<D>a - b: the positions in a that are not in b.
Bitset<D>.sub
fn sub(a, b)Bitset<D>
impl Show for Bitset<D>Bitset<D>.show
fn show(a)