use super::{Forest, OccId};
use std::fmt::{Debug, Formatter, Result as FmtResult};
use std::ops::{BitAnd, BitAndAssign, BitOr, BitOrAssign, Sub, SubAssign};
#[derive(PartialEq, Eq, Hash, PartialOrd, Ord)]
pub(crate) struct OccSet {
words: Box<[u64]>,
}
impl Clone for OccSet {
fn clone(&self) -> Self {
Self {
words: self.words.clone(),
}
}
fn clone_from(&mut self, source: &Self) {
if self.words.len() == source.words.len() {
self.words.copy_from_slice(&source.words);
} else {
self.words = source.words.clone();
}
}
}
impl OccSet {
pub(crate) fn empty(len: usize) -> Self {
Self {
words: vec![0; len.div_ceil(64)].into_boxed_slice(),
}
}
pub(crate) fn of(len: usize, ids: impl IntoIterator<Item = OccId>) -> Self {
let mut set = Self::empty(len);
set.extend(ids);
set
}
pub(crate) fn capacity(&self) -> usize {
self.words.len() * 64
}
pub(crate) fn words(&self) -> &[u64] {
&self.words
}
fn locate(o: OccId) -> (usize, u64) {
(o.index() / 64, 1 << (o.get() % 64))
}
pub(crate) fn insert(&mut self, o: OccId) -> bool {
let (w, bit) = Self::locate(o);
let absent = self.words[w] & bit == 0;
self.words[w] |= bit;
absent
}
pub(crate) fn remove(&mut self, o: OccId) -> bool {
let (w, bit) = Self::locate(o);
let present = self.words[w] & bit != 0;
self.words[w] &= !bit;
present
}
#[cfg(test)]
pub(crate) fn toggle(&mut self, o: OccId) {
let (w, bit) = Self::locate(o);
self.words[w] ^= bit;
}
pub(crate) fn contains(&self, o: OccId) -> bool {
let (w, bit) = Self::locate(o);
self.words[w] & bit != 0
}
pub(crate) fn clear(&mut self) {
self.words.fill(0);
}
pub(crate) fn is_empty(&self) -> bool {
self.words.iter().all(|&w| w == 0)
}
pub(crate) fn len(&self) -> usize {
self.words.iter().map(|w| w.count_ones() as usize).sum()
}
#[cfg(test)]
pub(crate) fn first(&self) -> Option<OccId> {
self.iter().next()
}
pub(crate) fn iter_words(&self, lo: usize, hi: usize) -> Iter<'_> {
let words = &self.words[..hi];
Iter {
words,
index: lo,
current: words.get(lo).copied().unwrap_or(0),
}
}
pub(crate) fn clear_words(&mut self, lo: usize, hi: usize) {
self.words[lo..hi].fill(0);
}
pub(crate) fn copy_words(&mut self, other: &Self, lo: usize, hi: usize) {
self.words[lo..hi].copy_from_slice(&other.words[lo..hi]);
}
pub(crate) fn iter(&self) -> Iter<'_> {
Iter {
words: &self.words,
index: 0,
current: self.words.first().copied().unwrap_or(0),
}
}
pub(crate) fn union_with(&mut self, other: &Self) {
let beyond = other.beyond(self);
if let Some(i) = beyond.iter().position(|&w| w != 0) {
let member = (self.words.len() + i) * 64 + beyond[i].trailing_zeros() as usize;
panic!(
"a union with occurrence {member}, which a set of {} ids cannot hold",
self.capacity()
);
}
self.zip_with(other, |a, b| a | b);
}
pub(crate) fn intersect_with(&mut self, other: &Self) {
self.zip_with(other, |a, b| a & b);
let shared = self.words.len().min(other.words.len());
self.words[shared..].fill(0);
}
pub(crate) fn difference_with(&mut self, other: &Self) {
self.zip_with(other, |a, b| a & !b);
}
fn zip_with(&mut self, other: &Self, f: impl Fn(u64, u64) -> u64) {
for (a, b) in self.words.iter_mut().zip(&other.words) {
*a = f(*a, *b);
}
}
fn beyond(&self, other: &Self) -> &[u64] {
self.words.get(other.words.len()..).unwrap_or_default()
}
#[cfg(test)]
pub(crate) fn is_subset(&self, other: &Self) -> bool {
let mut shared = self.words.iter().zip(&other.words);
shared.all(|(a, b)| a & !b == 0) && self.beyond(other).iter().all(|&w| w == 0)
}
#[cfg(test)]
pub(crate) fn is_disjoint(&self, other: &Self) -> bool {
self.words.iter().zip(&other.words).all(|(a, b)| a & b == 0)
}
}
impl Extend<OccId> for OccSet {
fn extend<I: IntoIterator<Item = OccId>>(&mut self, ids: I) {
for o in ids {
self.insert(o);
}
}
}
impl<'a> IntoIterator for &'a OccSet {
type Item = OccId;
type IntoIter = Iter<'a>;
fn into_iter(self) -> Iter<'a> {
self.iter()
}
}
impl Debug for OccSet {
fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
f.debug_set().entries(self.iter().map(|o| o.get())).finish()
}
}
impl BitOrAssign<&OccSet> for OccSet {
fn bitor_assign(&mut self, other: &OccSet) {
self.union_with(other);
}
}
impl BitAndAssign<&OccSet> for OccSet {
fn bitand_assign(&mut self, other: &OccSet) {
self.intersect_with(other);
}
}
impl SubAssign<&OccSet> for OccSet {
fn sub_assign(&mut self, other: &OccSet) {
self.difference_with(other);
}
}
impl BitOr for &OccSet {
type Output = OccSet;
fn bitor(self, other: Self) -> OccSet {
let (wider, narrower) = if self.words.len() < other.words.len() {
(other, self)
} else {
(self, other)
};
let mut set = wider.clone();
set |= narrower;
set
}
}
impl BitAnd for &OccSet {
type Output = OccSet;
fn bitand(self, other: Self) -> OccSet {
let mut set = self.clone();
set &= other;
set
}
}
impl Sub for &OccSet {
type Output = OccSet;
fn sub(self, other: Self) -> OccSet {
let mut set = self.clone();
set -= other;
set
}
}
#[derive(Clone, Debug)]
pub(crate) struct Iter<'a> {
words: &'a [u64],
index: usize,
current: u64,
}
impl Iterator for Iter<'_> {
type Item = OccId;
fn next(&mut self) -> Option<OccId> {
while self.current == 0 {
self.index += 1;
self.current = *self.words.get(self.index)?;
}
let bit = self.current.trailing_zeros();
self.current &= self.current - 1;
Some(OccId::new((self.index * 64) as u32 + bit))
}
fn size_hint(&self) -> (usize, Option<usize>) {
let rest = self.words.get(self.index + 1..).unwrap_or_default();
let n = self.current.count_ones() as usize
+ rest.iter().map(|w| w.count_ones() as usize).sum::<usize>();
(n, Some(n))
}
}
impl ExactSizeIterator for Iter<'_> {}
impl Forest {
pub(crate) fn empty_set(&self) -> OccSet {
OccSet::empty(self.len())
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::hash::HashSet;
const fn o(id: u32) -> OccId {
OccId::new(id)
}
#[test]
fn membership() {
let mut s = OccSet::empty(130);
assert_eq!(s.capacity(), 192);
assert!(s.is_empty());
assert_eq!(s.len(), 0);
assert_eq!(s.first(), None);
assert!(s.insert(o(129)));
assert!(s.insert(o(64)));
assert!(s.insert(o(3)));
assert!(!s.insert(o(3)));
assert!(s.contains(o(3)) && s.contains(o(64)) && s.contains(o(129)));
assert!(!s.contains(o(63)) && !s.contains(o(65)));
assert_eq!(s.len(), 3);
assert_eq!(s.first(), Some(o(3)));
assert_eq!(s.iter().collect::<Vec<_>>(), [o(3), o(64), o(129)]);
assert_eq!(s.iter().len(), 3);
assert_eq!(format!("{s:?}"), "{3, 64, 129}");
assert!(s.remove(o(64)));
assert!(!s.remove(o(64)));
s.toggle(o(0));
s.toggle(o(3));
assert_eq!(s.iter().collect::<Vec<_>>(), [o(0), o(129)]);
s.clear();
assert!(s.is_empty());
assert_eq!(OccSet::empty(0).iter().count(), 0);
}
#[test]
fn algebra() {
let a = OccSet::of(70, [o(1), o(2), o(65)]);
let b = OccSet::of(70, [o(2), o(3), o(69)]);
assert_eq!(
(&a | &b).iter().collect::<Vec<_>>(),
[o(1), o(2), o(3), o(65), o(69)]
);
assert_eq!((&a & &b).iter().collect::<Vec<_>>(), [o(2)]);
assert_eq!((&a - &b).iter().collect::<Vec<_>>(), [o(1), o(65)]);
assert!(!a.is_subset(&b));
assert!((&a & &b).is_subset(&a));
assert!(!a.is_disjoint(&b));
assert!((&a - &b).is_disjoint(&b));
let mut c = a.clone();
c |= &b;
assert_eq!(c, &a | &b);
c &= &b;
assert_eq!(c, b);
c -= &a;
assert_eq!(c, &b - &a);
let mut d = OccSet::empty(70);
d.extend([o(65), o(1), o(2)]);
assert_eq!(d, a);
}
#[test]
fn different_widths() {
let narrow = OccSet::of(64, [o(1), o(2)]);
let wide = OccSet::of(200, [o(2), o(130)]);
let members = |s: &OccSet| s.iter().map(OccId::get).collect::<Vec<_>>();
assert!(
!wide.is_subset(&narrow),
"130 is no member of the narrow set"
);
assert!(!narrow.is_subset(&wide));
assert!(OccSet::of(200, [o(2)]).is_subset(&narrow));
assert!(OccSet::of(64, [o(2)]).is_subset(&wide));
assert!(!wide.is_disjoint(&narrow) && !narrow.is_disjoint(&wide));
assert!(OccSet::of(200, [o(130)]).is_disjoint(&narrow));
assert!(narrow.is_disjoint(&OccSet::of(200, [o(130)])));
let (meet, other) = (&wide & &narrow, &narrow & &wide);
assert_eq!((members(&meet), meet.capacity()), (vec![2], 256));
assert_eq!((members(&other), other.capacity()), (vec![2], 64));
let (rest, other) = (&wide - &narrow, &narrow - &wide);
assert_eq!((members(&rest), rest.capacity()), (vec![130], 256));
assert_eq!((members(&other), other.capacity()), (vec![1], 64));
let (join, other) = (&wide | &narrow, &narrow | &wide);
assert_eq!((members(&join), join.capacity()), (vec![1, 2, 130], 256));
assert_eq!(join, other);
let mut fits = narrow.clone();
fits |= &OccSet::of(200, [o(3)]);
assert_eq!((members(&fits), fits.capacity()), (vec![1, 2, 3], 64));
}
#[test]
#[should_panic(expected = "a union with occurrence 130, which a set of 64 ids cannot hold")]
fn a_union_loses_no_member() {
let mut narrow = OccSet::of(64, [o(1)]);
narrow |= &OccSet::of(200, [o(2), o(130)]);
}
#[test]
fn hashing() {
let mut seen = HashSet::default();
assert!(seen.insert(OccSet::of(100, [o(5), o(80)])));
assert!(!seen.insert(OccSet::of(100, [o(80), o(5)])));
assert!(seen.insert(OccSet::of(100, [o(5)])));
assert_eq!(OccSet::of(100, [o(5), o(80)]).words(), [1 << 5, 1 << 16]);
}
}