subset
A subset of a domain B of at most 64 members, stored as one word (bit k for B's k-th position).
Generated from spec/std/subset.cp by cpl doc --format json.
Subset
pub struct Subset<B>(bits: U64)A subset of a domain B of at most 64 members, stored as one word (bit k for B's k-th
position). B.subsets is the domain of all 2^|B| of them, so [B.subsets]T is a mask-DP
table, and {} is the empty subset. Every operation here is O(1) unless it says otherwise.
Subset.empty
fn empty() -> Subset<B>The empty subset, also written {}.
- cost: O(1)
- traps: never
Examples:
domain B = 0..4; Subset<B>.empty.len == 0
Subset.full
fn full() -> Subset<B>Every member of B: the word with its low |B| bits set.
- cost: O(1)
- traps: never
Examples:
domain B = 0..4; Subset<B>.full.len == 4
Subset.single
fn single(b: B) -> Subset<B>{b}: the subset whose only member is b.
- cost: O(1)
- traps: never
Examples:
domain B = 0..4; Subset<B>.single(B(2)).items.collect() == [B(2)]
Subset.contains
fn contains(self, b: B) -> BoolWhether b is a member; b in s calls it and b not in s negates it.
- cost: O(1)
- traps: never
Examples:
domain B = 0..4; let s = Subset<B>.single(B(1)); B(1) in s and B(2) not in s
Subset.len
fn len(self) -> IntThe number of members (a popcount).
- cost: O(1)
- traps: never
Examples:
domain B = 0..4; Subset<B>.single(B(0)).with(B(3)).len == 2
Subset.with
fn with(self, b: B) -> Subset<B>self with b added. Adding a member already present returns self unchanged.
- cost: O(1)
- traps: never
Examples:
domain B = 0..4; Subset<B>.empty.with(B(1)).with(B(1)) == Subset<B>.single(B(1))
Subset.without
fn without(self, b: B) -> Subset<B>self with b removed. Removing a non-member returns self unchanged.
- cost: O(1)
- traps: never
Examples:
domain B = 0..4; Subset<B>.full.without(B(0)).len == 3domain B = 0..4; Subset<B>.empty.without(B(2)) == Subset<B>.empty
Subset.set
fn set(mut self, b: B, on: Bool)Add b when on, remove it otherwise, in place (as Bitset.set).
- cost: O(1)
- traps: never
Examples:
domain B = 0..4; var s = Subset<B>.empty; s.set(B(2), true); s.set(B(0), false); s == Subset<B>.single(B(2))
Subset.shifted
fn shifted(self, k: Int) -> Subset<B>A new set with every member k places up (down for a negative k); members that leave B
are dropped (as Bitset.shifted).
- cost: O(1)
- traps: never
Examples:
domain B = 0..4; Subset<B>.single(B(1)).with(B(3)).shifted(1) == Subset<B>.single(B(2))domain B = 0..4; Subset<B>.single(B(1)).shifted(-2) == Subset<B>.empty
Subset.complement
fn complement(self) -> Subset<B>The members of B not in self; no bit at or above |B| is ever set.
- cost: O(1)
- traps: never
Examples:
domain B = 0..4; Subset<B>.single(B(0)).complement().len == 3domain B = 0..4; Subset<B>.empty.complement() == Subset<B>.full
Subset.first
fn first(self) -> ?BThe least member in B's order (the lowest set bit, by count-trailing-zeros), None
for {}. Peels one member per step in a mask DP: s.first() then s.without(b).
- cost: O(1)
- empty:
None - ties: None possible; members are distinct, and the least in
B's order wins - traps: never
Examples:
domain B = 0..4; Subset<B>.single(B(3)).with(B(1)).first() == Some(B(1))domain B = 0..4; Subset<B>.empty.first() == None
Subset.items
fn items(self) -> yields BThe members in B's order; for b in s walks the same sequence.
- cost: O(1) per member
- empty: yields nothing
- order: increasing in
B's order (increasing bit index) - traps: never
Examples:
domain B = 0..4; Subset<B>.single(B(3)).with(B(1)).items.collect() == [B(1), B(3)]
Subset.subsets
fn subsets(self) -> yields Subset<B>Every subset of self, self first and {} last: the submask walk
g = (g - 1) & self, so the masks come in decreasing order as words. 2^s.len subsets.
- cost: O(1) per subset,
2^s.lensubsets - empty:
{}.subsetsyields{}once - order: decreasing as words:
selffirst,{}last - traps: never
Examples:
domain B = 0..3; let s = Subset<B>.single(B(0)).with(B(1)); s.subsets.map(g => g.first()).collect() == [Some(B(0)), Some(B(1)), Some(B(0)), None]
Subset.supersets
fn supersets(self) -> yields Subset<B>Every superset of self within B, self first and B last: the walk
g = (g + 1) | self, so the masks come in increasing order as words. 2^(|B| - s.len)
supersets.
- cost: O(1) per superset,
2^(|B| - s.len)supersets - empty:
{}.supersetsyields every subset ofB,{}first - order: increasing as words:
selffirst,Subset<B>.fulllast - traps: never
Examples:
domain B = 0..3; Subset<B>.single(B(1)).supersets.map(g => g.len).collect() == [1, 2, 2, 3]
Subset<B>
impl BitOr for Subset<B>Subset<B>.bitor
fn bitor(a, b)Subset<B>
impl BitAnd for Subset<B>Subset<B>.bitand
fn bitand(a, b)Subset<B>
impl BitXor for Subset<B>Subset<B>.bitxor
fn bitxor(a, b)Subset<B>
impl Sub for Subset<B>Subset<B>.sub
fn sub(a, b)