Crate superset_map

superset_map

superset_map is a library for Sets that have an order defined on them. It’s main data structure is SupersetMap which is a specialized version of BTreeMap where only supersets are stored. This can be useful when the keys don’t fit well or at all with the concept of RangeBounds.

Version 1.69.0 or newer of nightly rustc is required. Once BTreeMap cursors are stabilized, stable rustc will work.

Example

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());
}

Re-exports

• pub use superset_map::SupersetMap;
• pub use superset_set::SupersetSet;

Modules

• superset_map
  A map of keys and values where the keys implement SetOrd. The map is backed by a B-tree.
• superset_set
  A set of values where the values implement SetOrd. The set is backed by a B-tree.

Traits

• SetOrd
  Must conform to the following properties ∀a, b, c: Self: