superset_map

superset_map is a library for Sets that have an order defined on them. Its 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.

Nightly Rust is required. Once BTreeMap cursors are stabilized, stable Rust will work.

Example

use core::{borrow::Borrow, cmp::Ordering};
use superset_map::{zfc::{num_bigint::BigUint, BoundedCardinality, Cardinality, Set}, SetOrd, SupersetSet};
#[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());
}

License

Licensed under either of

• Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0).
• MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT).

at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

Status

The crate is only tested on x86_64-unknown-linux-gnu and x86_64-unknown-openbsd targets, but it should work on most platforms.