use crate::linear::occurrences::{Member, OccId};
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub(crate) struct Multiset<T = OccId>(Vec<T>);
impl<T> Default for Multiset<T> {
fn default() -> Self {
Self(Vec::new())
}
}
impl<T: Copy + Ord> Multiset<T> {
#[cfg(any(test, feature = "interactive"))]
pub(crate) const fn new() -> Self {
Self(Vec::new())
}
pub(crate) fn of(ids: impl IntoIterator<Item = T>) -> Self {
let mut ids: Vec<T> = ids.into_iter().collect();
ids.sort_unstable();
Self(ids)
}
pub(crate) fn as_slice(&self) -> &[T] {
&self.0
}
pub(crate) fn into_members(self) -> Vec<Member>
where
T: Into<Member>,
{
self.0.into_iter().map(Into::into).collect()
}
pub(crate) fn is_empty(&self) -> bool {
self.0.is_empty()
}
pub(crate) fn position(&self, o: T) -> Option<usize> {
let i = self.0.partition_point(|&x| x < o);
(self.0.get(i) == Some(&o)).then_some(i)
}
pub(crate) fn contains(&self, o: T) -> bool {
self.position(o).is_some()
}
pub(crate) fn insert(&mut self, o: T) {
let i = self.0.partition_point(|&x| x <= o);
self.0.insert(i, o);
}
pub(crate) fn ensure(&mut self, o: T) {
if !self.contains(o) {
self.insert(o);
}
}
pub(crate) fn remove(&mut self, o: T) -> bool {
match self.position(o) {
Some(i) => {
self.0.remove(i);
true
}
None => false,
}
}
fn merge(&self, other: &Self, f: impl Fn(usize, usize) -> usize) -> Self {
let (a, b) = (&self.0, &other.0);
let mut out = Vec::with_capacity(a.len() + b.len());
let (mut i, mut j) = (0, 0);
while i < a.len() || j < b.len() {
let o = match (a.get(i), b.get(j)) {
(Some(&x), Some(&y)) => x.min(y),
(Some(&x), None) => x,
(None, Some(&y)) => y,
(None, None) => unreachable!(),
};
let run = |v: &[T], k: usize| v[k..].iter().take_while(|&&x| x == o).count();
let (ca, cb) = (run(a, i), run(b, j));
out.extend(std::iter::repeat_n(o, f(ca, cb)));
i += ca;
j += cb;
}
Self(out)
}
pub(crate) fn sum(&self, other: &Self) -> Self {
self.merge(other, |a, b| a + b)
}
#[cfg(test)]
pub(crate) fn union(&self, other: &Self) -> Self {
self.merge(other, usize::max)
}
pub(crate) fn difference(&self, other: &Self) -> Self {
self.merge(other, usize::saturating_sub)
}
pub(crate) fn is_subset(&self, other: &Self) -> bool {
self.difference(other).is_empty()
}
}
#[cfg(test)]
mod tests {
use super::*;
const fn o(id: u32) -> OccId {
OccId::new(id)
}
#[test]
fn counts() {
let mut m = Multiset::of([o(5), o(2), o(5)]);
assert_eq!(m.as_slice(), [o(2), o(5), o(5)]);
assert_eq!(m.position(o(5)), Some(1));
assert_eq!(m.position(o(3)), None);
m.insert(o(3));
m.ensure(o(3));
m.ensure(o(9));
assert_eq!(m.as_slice(), [o(2), o(3), o(5), o(5), o(9)]);
assert!(m.remove(o(5)));
assert!(m.remove(o(5)));
assert!(!m.remove(o(5)));
assert_eq!(m.as_slice(), [o(2), o(3), o(9)]);
let a = Multiset::of([o(1), o(1), o(2)]);
let b = Multiset::of([o(1), o(2), o(2), o(4)]);
assert_eq!(
a.sum(&b).as_slice(),
[o(1), o(1), o(1), o(2), o(2), o(2), o(4)]
);
assert_eq!(a.union(&b).as_slice(), [o(1), o(1), o(2), o(2), o(4)]);
assert_eq!(a.difference(&b).as_slice(), [o(1)]);
assert_eq!(b.difference(&a).as_slice(), [o(2), o(4)]);
assert!(!a.is_subset(&b));
assert!(a.difference(&b).is_subset(&a));
assert!(Multiset::<OccId>::new().is_subset(&a));
assert!(Multiset::<OccId>::new().is_empty());
}
}