Skip to Content
ReferenceLibrary

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.

Source

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

Source

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

Source

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

Source

Subset.contains

fn contains(self, b: B) -> Bool

Whether 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

Source

Subset.len

fn len(self) -> Int

The 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

Source

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

Source

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 == 3
  • domain B = 0..4; Subset<B>.empty.without(B(2)) == Subset<B>.empty

Source

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

Source

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

Source

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 == 3
  • domain B = 0..4; Subset<B>.empty.complement() == Subset<B>.full

Source

Subset.first

fn first(self) -> ?B

The 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

Source

Subset.items

fn items(self) -> yields B

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

Source

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.len subsets
  • empty: {}.subsets yields {} once
  • order: decreasing as words: self first, {} 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]

Source

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: {}.supersets yields every subset of B, {} first
  • order: increasing as words: self first, Subset<B>.full last
  • traps: never

Examples:

  • domain B = 0..3; Subset<B>.single(B(1)).supersets.map(g => g.len).collect() == [1, 2, 2, 3]

Source

Subset<B>

impl BitOr for Subset<B>

Source

Subset<B>.bitor

fn bitor(a, b)

Source

Subset<B>

impl BitAnd for Subset<B>

Source

Subset<B>.bitand

fn bitand(a, b)

Source

Subset<B>

impl BitXor for Subset<B>

Source

Subset<B>.bitxor

fn bitxor(a, b)

Source

Subset<B>

impl Sub for Subset<B>

Source

Subset<B>.sub

fn sub(a, b)

Source

On this page