use crate::linear::occurrences::{OccId, OccSet};
#[derive(Debug)]
pub(crate) struct Context {
set: OccSet,
extra: Vec<(OccId, u32)>,
lo: usize,
hi: usize,
}
const NARROW: usize = 8;
impl Clone for Context {
fn clone(&self) -> Self {
Self {
set: self.set.clone(),
extra: self.extra.clone(),
lo: self.lo,
hi: self.hi,
}
}
fn clone_from(&mut self, other: &Self) {
debug_assert_eq!(self.set.capacity(), other.set.capacity(), "one forest");
let (lo, hi) = if self.lo == self.hi {
(other.lo, other.hi)
} else if other.lo == other.hi {
(self.lo, self.hi)
} else {
(self.lo.min(other.lo), self.hi.max(other.hi))
};
self.set.copy_words(&other.set, lo, hi);
(self.lo, self.hi) = (other.lo, other.hi);
self.extra.clone_from(&other.extra);
}
}
impl PartialEq for Context {
fn eq(&self, other: &Self) -> bool {
self.set == other.set && self.extra == other.extra
}
}
impl Eq for Context {}
impl Context {
pub(crate) fn empty(len: usize) -> Self {
let mut zone = Self {
set: OccSet::empty(len),
extra: Vec::new(),
lo: 0,
hi: 0,
};
zone.clear();
zone
}
#[cfg(test)]
pub(crate) fn extra(&self) -> &[(OccId, u32)] {
&self.extra
}
fn slot(&self, o: OccId) -> Result<usize, usize> {
self.extra.binary_search_by_key(&o, |&(x, _)| x)
}
#[inline]
fn reach(&mut self, o: OccId) {
if self.hi - self.lo == self.set.words().len() {
return;
}
let word = o.index() / 64;
if self.lo == self.hi {
(self.lo, self.hi) = (word, word + 1);
} else {
self.lo = self.lo.min(word);
self.hi = self.hi.max(word + 1);
}
}
pub(crate) fn insert(&mut self, o: OccId) {
if self.set.insert(o) {
self.reach(o);
return;
}
match self.slot(o) {
Ok(i) => self.extra[i].1 += 1,
Err(i) => self.extra.insert(i, (o, 1)),
}
}
pub(crate) fn remove(&mut self, o: OccId) {
debug_assert!(self.set.contains(o), "removing a member");
if let Ok(i) = self.slot(o) {
if self.extra[i].1 == 1 {
self.extra.remove(i);
} else {
self.extra[i].1 -= 1;
}
} else {
self.set.remove(o);
}
}
pub(crate) fn contains(&self, o: OccId) -> bool {
self.set.contains(o)
}
#[cfg(test)]
pub(crate) fn count(&self, o: OccId) -> u32 {
if !self.set.contains(o) {
return 0;
}
1 + self.slot(o).map_or(0, |i| self.extra[i].1)
}
pub(crate) fn clear(&mut self) {
self.set.clear_words(self.lo, self.hi);
let width = self.set.words().len();
(self.lo, self.hi) = if width <= NARROW { (0, width) } else { (0, 0) };
self.extra.clear();
}
pub(crate) fn meets(&self, set: &OccSet) -> bool {
let (ours, theirs) = (self.set.words(), set.words());
ours[self.lo..self.hi]
.iter()
.zip(&theirs[self.lo..self.hi])
.any(|(a, b)| a & b != 0)
}
pub(crate) fn is_empty(&self) -> bool {
self.set.words()[self.lo..self.hi].iter().all(|&w| w == 0)
}
#[cfg(test)]
pub(crate) fn len(&self) -> usize {
self.set.words()[self.lo..self.hi]
.iter()
.map(|w| w.count_ones() as usize)
.sum::<usize>()
+ self.extra.iter().map(|&(_, n)| n as usize).sum::<usize>()
}
pub(crate) fn iter(&self) -> impl Iterator<Item = OccId> + '_ {
self.with_copies()
.flat_map(|(o, copies)| std::iter::repeat_n(o, copies as usize))
}
fn with_copies(&self) -> impl Iterator<Item = (OccId, u32)> + '_ {
let mut extra = self.extra.iter().peekable();
self.set.iter_words(self.lo, self.hi).map(move |o| {
let extras = extra.next_if(|&&(x, _)| x == o).map_or(0, |&(_, n)| n);
(o, 1 + extras)
})
}
pub(crate) fn repeats(&self) -> bool {
!self.extra.is_empty()
}
pub(crate) fn key_into(&self, list: &mut Vec<OccId>) {
use super::memo::REPEATED;
for (o, copies) in self.with_copies() {
debug_assert_eq!(o.get() & REPEATED, 0, "an occurrence below 2³¹");
if copies == 1 {
list.push(o);
} else {
list.extend([OccId::new(o.get() | REPEATED), OccId::new(copies)]);
}
}
}
pub(crate) fn list_into(&self, list: &mut Vec<OccId>) {
if self.extra.is_empty() {
list.extend(self.set.iter_words(self.lo, self.hi));
} else {
list.extend(self.iter());
}
}
}
#[cfg(test)]
mod tests {
use super::*;
const fn o(id: u32) -> OccId {
OccId::new(id)
}
#[test]
fn copies() {
let mut c = Context::empty(70);
assert!(c.is_empty());
c.insert(o(65));
c.insert(o(3));
assert_eq!(c.extra(), []);
c.insert(o(3));
c.insert(o(3));
assert_eq!(c.extra(), [(o(3), 2)]);
assert_eq!(c.count(o(3)), 3);
assert_eq!(c.count(o(65)), 1);
assert_eq!(c.count(o(4)), 0);
assert_eq!(c.len(), 4);
assert_eq!(c.iter().collect::<Vec<_>>(), [o(3), o(3), o(3), o(65)]);
c.remove(o(3));
assert_eq!(c.extra(), [(o(3), 1)]);
c.remove(o(3));
assert_eq!(c.extra(), []);
assert!(c.contains(o(3)));
c.remove(o(3));
assert!(!c.contains(o(3)));
assert_eq!(c.iter().collect::<Vec<_>>(), [o(65)]);
let mut d = Context::empty(70);
d.clone_from(&c);
assert_eq!(c, d);
d.insert(o(65));
d.insert(o(4));
assert_eq!(d.iter().collect::<Vec<_>>(), [o(4), o(65), o(65)]);
c.clear();
assert!(c.is_empty());
}
}