superset_map

B-tree-backed map whose keys are distinct supersets.
git clone https://git.philomathiclife.com/repos/superset_map
Log | Files | Refs | README

README.md (6727B)

      1 # `superset_map`
      2 
      3 [<img alt="git" src="https://git.philomathiclife.com/badges/superset_map.svg" height="20">](https://git.philomathiclife.com/superset_map/log.html)
      4 [<img alt="crates.io" src="https://img.shields.io/crates/v/superset_map.svg?style=for-the-badge&color=fc8d62&logo=rust" height="20">](https://crates.io/crates/superset_map)
      5 [<img alt="docs.rs" src="https://img.shields.io/badge/docs.rs-superset_map-66c2a5?style=for-the-badge&labelColor=555555&logo=docs.rs" height="20">](https://docs.rs/superset_map/latest/superset_map/)
      6 
      7 `superset_map` is a library for `Set`s that have an order defined on them. Its main data structure is
      8 `SupersetMap` which is a specialized version of `BTreeMap` where only supersets are stored. This can be
      9 useful when the keys don't fit well or at all with the concept of `RangeBounds`.
     10 
     11 Nightly Rust is required. Once
     12 [`BTreeMap` cursors are stabilized](https://github.com/rust-lang/rust/issues/107540), stable Rust will work.
     13 
     14 ## Example
     15 
     16 ```rust
     17 use core::{borrow::Borrow, cmp::Ordering};
     18 use superset_map::{zfc::{num_bigint::BigUint, BoundedCardinality, Cardinality, Set}, SetOrd, SupersetSet};
     19 #[derive(Clone, Copy, Eq, PartialEq)]
     20 struct ShortAscii<'a> {
     21     val: &'a [u8],
     22 }
     23 impl<'a> ShortAscii<'a> {
     24     fn new(val: &'a [u8]) -> Option<ShortAscii<'a>> {
     25         (val.len() <= 255 && val.is_ascii()).then_some(Self { val })
     26     }
     27     fn len(self) -> u8 {
     28         self.val.len().try_into().expect("The ShortAscii instance was not constructed properly and contains more than 255 bytes.")
     29     }
     30 }
     31 #[derive(Clone, Copy, Eq, PartialEq)]
     32 enum WildcardAscii<'a> {
     33     Plain(ShortAscii<'a>),
     34     // Represents a ShortAscii<'a> with an implicit wildcard at the end
     35     // meaning it's all ShortAscii<'a>s that begin with the contained ShortAscii<'a>.val.
     36     Wildcard(ShortAscii<'a>),
     37 }
     38 impl<'a> WildcardAscii<'a> {
     39     const fn val(self) -> ShortAscii<'a> {
     40         match self {
     41             WildcardAscii::Plain(s) | WildcardAscii::Wildcard(s) => s,
     42         }
     43     }
     44     const fn is_plain(self) -> bool {
     45         match self {
     46             WildcardAscii::Plain(_) => true,
     47             WildcardAscii::Wildcard(_) => false,
     48         }
     49     }
     50     const fn is_wildcard(self) -> bool {
     51         !self.is_plain()
     52     }
     53 }
     54 impl<'a> PartialOrd<Self> for WildcardAscii<'a> {
     55     fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
     56         Some(self.cmp(other))
     57     }
     58 }
     59 impl<'a> Ord for WildcardAscii<'a> {
     60     fn cmp(&self, other: &Self) -> Ordering {
     61         let len = u8::min(self.val().len(), other.val().len()) as usize;
     62         match self.val().val[..len].cmp(&other.val().val[..len]) {
     63             Ordering::Less => Ordering::Less,
     64             Ordering::Equal => {
     65                 if self.is_wildcard() {
     66                     if other.is_wildcard() {
     67                         self.val().len().cmp(&other.val().len()).reverse()
     68                     } else {
     69                         Ordering::Greater
     70                     }
     71                 } else if other.is_wildcard() {
     72                     Ordering::Less
     73                 } else {
     74                     self.val().len().cmp(&other.val().len())
     75                 }
     76             }
     77             Ordering::Greater => Ordering::Greater,
     78         }
     79     }
     80 }
     81 impl<'a> Set for WildcardAscii<'a> {
     82     type Elem = ShortAscii<'a>;
     83     fn bounded_cardinality(&self) -> BoundedCardinality {
     84         BoundedCardinality::new_exact(self.cardinality().unwrap())
     85     }
     86     fn cardinality(&self) -> Option<Cardinality> {
     87         Some(Cardinality::Finite(match *self {
     88             WildcardAscii::Plain(_) => BigUint::new(vec![1]),
     89             // Geometric series.
     90             WildcardAscii::Wildcard(v) => {
     91                 (BigUint::new(vec![128]).pow((u8::MAX - v.len()) as u32 + 1)
     92                     - BigUint::new(vec![1]))
     93                     / BigUint::new(vec![127])
     94             }
     95         }))
     96     }
     97     fn contains<Q>(&self, elem: &Q) -> bool
     98     where
     99         Q: Borrow<Self::Elem> + Eq + ?Sized,
    100     {
    101         match *self {
    102             WildcardAscii::Plain(v) => v == *elem.borrow(),
    103             WildcardAscii::Wildcard(v) => {
    104                 v.len() <= elem.borrow().len() && *v.val == elem.borrow().val[..v.len() as usize]
    105             }
    106         }
    107     }
    108     fn is_proper_subset(&self, val: &Self) -> bool {
    109         val.is_wildcard()
    110             && match val.val().len().cmp(&self.val().len()) {
    111                 Ordering::Less => val.val().val == &self.val().val[..val.val().len() as usize],
    112                 Ordering::Equal => self.is_plain() && self.val() == val.val(),
    113                 Ordering::Greater => false,
    114             }
    115     }
    116     fn is_subset(&self, val: &Self) -> bool {
    117         self == val || self.is_proper_subset(val)
    118     }
    119 }
    120 impl<'a> SetOrd for WildcardAscii<'a> {}
    121 fn main() {
    122     let mut set = SupersetSet::new();
    123     set.insert(WildcardAscii::Plain(ShortAscii::new(b"foo").unwrap()));
    124     set.insert(WildcardAscii::Plain(ShortAscii::new(b"bar").unwrap()));
    125     set.insert(WildcardAscii::Wildcard(ShortAscii::new(b"b").unwrap()));
    126     set.insert(WildcardAscii::Wildcard(ShortAscii::new(b"bar").unwrap()));
    127     let mut iter = set.into_iter();
    128     assert!(iter.next().map_or(false, |s| s
    129         == WildcardAscii::Wildcard(ShortAscii::new(b"b").unwrap())));
    130     assert!(iter.next().map_or(false, |s| s
    131         == WildcardAscii::Plain(ShortAscii::new(b"foo").unwrap())));
    132     assert!(iter.next().is_none());
    133 }
    134 ```
    135 
    136 ## Minimum Supported Rust Version (MSRV)
    137 
    138 This will frequently be updated to be the same as stable. Specifically, any time stable is updated and that
    139 update has "useful" features or compilation no longer succeeds (e.g., due to new compiler lints), then MSRV
    140 will be updated.
    141 
    142 MSRV changes will correspond to a SemVer patch version bump pre-`1.0.0`; otherwise a minor version bump.
    143 
    144 ## SemVer Policy
    145 
    146 * All on-by-default features of this library are covered by SemVer
    147 * MSRV is considered exempt from SemVer as noted above
    148 
    149 ## License
    150 
    151 Licensed under either of
    152 
    153 * Apache License, Version 2.0 ([LICENSE-APACHE](https://www.apache.org/licenses/LICENSE-2.0))
    154 * MIT license ([LICENSE-MIT](https://opensource.org/licenses/MIT))
    155 
    156 at your option.
    157 
    158 ## Contribution
    159 
    160 Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you,
    161 as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.
    162 
    163 Before any PR is sent, `cargo clippy` and `cargo t` should be run for both. Additionally
    164 `RUSTDOCFLAGS="--cfg docsrs" cargo +nightly doc --all-features` should be run to ensure documentation can be built.
    165 
    166 ### Status
    167 
    168 The crate is only tested on `x86_64-unknown-linux-gnu` and `x86_64-unknown-openbsd` targets, but it should work
    169 on most platforms.