superset_map

superset_map 是一个用于具有定义顺序的 Set 的库。它主要的数据结构是 SupersetMap，这是 BTreeMap 的一个特殊版本，只存储超集。当键不适合或完全不适用于 RangeBounds 的概念时，这可能很有用。

示例

use core::borrow::Borrow;
use core::cmp::Ordering;
use num_bigint::BigUint;
use superset_map::{SetOrd, SupersetSet};
use zfc::{BoundedCardinality, Cardinality, Set};
#[derive(Clone, Copy, Eq, PartialEq)]
struct ShortAscii<'a> {
    val: &'a [u8],
}
impl<'a> ShortAscii<'a> {
    fn new(val: &'a [u8]) -> Option<ShortAscii<'a>> {
        (val.len() <= 255 && val.is_ascii()).then_some(Self { val })
    }
    fn len(self) -> u8 {
        self.val.len().try_into().expect("The ShortAscii instance was not constructed properly and contains more than 255 bytes.")
    }
}
#[derive(Clone, Copy, Eq, PartialEq)]
enum WildcardAscii<'a> {
    Plain(ShortAscii<'a>),
    // Represents a ShortAscii<'a> with an implicit wildcard at the end
    // meaning it's all ShortAscii<'a>s that begin with the contained ShortAscii<'a>.val.
    Wildcard(ShortAscii<'a>),
}
impl<'a> WildcardAscii<'a> {
    const fn val(self) -> ShortAscii<'a> {
        match self {
            WildcardAscii::Plain(s) | WildcardAscii::Wildcard(s) => s,
        }
    }
    const fn is_plain(self) -> bool {
        match self {
            WildcardAscii::Plain(_) => true,
            WildcardAscii::Wildcard(_) => false,
        }
    }
    const fn is_wildcard(self) -> bool {
        !self.is_plain()
    }
}
impl<'a> PartialOrd<Self> for WildcardAscii<'a> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}
impl<'a> Ord for WildcardAscii<'a> {
    fn cmp(&self, other: &Self) -> Ordering {
        let len = u8::min(self.val().len(), other.val().len()) as usize;
        match self.val().val[..len].cmp(&other.val().val[..len]) {
            Ordering::Less => Ordering::Less,
            Ordering::Equal => {
                if self.is_wildcard() {
                    if other.is_wildcard() {
                        self.val().len().cmp(&other.val().len()).reverse()
                    } else {
                        Ordering::Greater
                    }
                } else if other.is_wildcard() {
                    Ordering::Less
                } else {
                    self.val().len().cmp(&other.val().len())
                }
            }
            Ordering::Greater => Ordering::Greater,
        }
    }
}
impl<'a> Set for WildcardAscii<'a> {
    type Elem = ShortAscii<'a>;
    fn bounded_cardinality(&self) -> BoundedCardinality {
        BoundedCardinality::new_exact(self.cardinality().unwrap())
    }
    fn cardinality(&self) -> Option<Cardinality> {
        Some(Cardinality::Finite(match *self {
            WildcardAscii::Plain(_) => BigUint::new(vec![1]),
            // Geometric series.
            WildcardAscii::Wildcard(v) => {
                (BigUint::new(vec![128]).pow((u8::MAX - v.len()) as u32 + 1)
                    - BigUint::new(vec![1]))
                    / BigUint::new(vec![127])
            }
        }))
    }
    fn contains<Q>(&self, elem: &Q) -> bool
    where
        Q: Borrow<Self::Elem> + Eq + ?Sized,
    {
        match *self {
            WildcardAscii::Plain(v) => v == *elem.borrow(),
            WildcardAscii::Wildcard(v) => {
                v.len() <= elem.borrow().len() && *v.val == elem.borrow().val[..v.len() as usize]
            }
        }
    }
    fn is_proper_subset(&self, val: &Self) -> bool {
        val.is_wildcard()
            && match val.val().len().cmp(&self.val().len()) {
                Ordering::Less => val.val().val == &self.val().val[..val.val().len() as usize],
                Ordering::Equal => self.is_plain() && self.val() == val.val(),
                Ordering::Greater => false,
            }
    }
    fn is_subset(&self, val: &Self) -> bool {
        self == val || self.is_proper_subset(val)
    }
}
impl<'a> SetOrd for WildcardAscii<'a> {}
fn main() {
    let mut set = SupersetSet::new();
    set.insert(WildcardAscii::Plain(ShortAscii::new(b"foo").unwrap()));
    set.insert(WildcardAscii::Plain(ShortAscii::new(b"bar").unwrap()));
    set.insert(WildcardAscii::Wildcard(ShortAscii::new(b"b").unwrap()));
    set.insert(WildcardAscii::Wildcard(ShortAscii::new(b"bar").unwrap()));
    let mut iter = set.into_iter();
    assert!(iter.next().map_or(false, |s| s
        == WildcardAscii::Wildcard(ShortAscii::new(b"b").unwrap())));
    assert!(iter.next().map_or(false, |s| s
        == WildcardAscii::Plain(ShortAscii::new(b"foo").unwrap())));
    assert!(iter.next().is_none());
}

状态

此包将积极维护，直到它被认为是“功能完整”。

仅对 x86_64-unknown-linux-gnu 和 x86_64-unknown-openbsd 目标进行测试，但它们应该适用于任何 具有主机工具的第一级 目标。

需要 nightly rustc 的 1.69.0 或更高版本。一旦 BTreeMap 游标稳定下来，稳定的 rustc 将会工作。