Crate superset_map

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.

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_set::SupersetSet;

Modules

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

Structs

• SupersetMap
  A minimal collection of (K, V)s. Internally it is based on a BTreeMap. When a (K, V) is SupersetMap::inserted, it won’t actually be inserted unless there isn’t a K already in the map that is a superset of it. In such event, all Ks that are subsets of the to-be-inserted K are removed before inserting the K. Note this can have quite good performance due to the fact that a single search is necessary to detect if insertion should occur; furthermore since all subsets occur immediately before where the key will be inserted, a simple linear scan is sufficient to remove subsets avoiding the need to search the entire map.

Traits

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