superset_map

README.md (5511B)

---

 # `superset_map`
 
 `superset_map` is a library for `Set`s 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](https://github.com/rust-lang/rust/issues/107540), stable Rust will work.
 
 ## Example
 
 ```rust
 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](LICENSE-APACHE) or http://www.apache.org/licenses/LICENSE-2.0).
 * MIT license ([LICENSE-MIT](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.