superset_map 0.3.6

//! [![git]](https://git.philomathiclife.com/superset_map/log.html) [![crates-io]](https://crates.io/crates/superset_map) [![docs-rs]](crate)
//!
//! [git]: https://git.philomathiclife.com/git_badge.svg
//! [crates-io]: https://img.shields.io/badge/crates.io-fc8d62?style=for-the-badge&labelColor=555555&logo=rust
//! [docs-rs]: https://img.shields.io/badge/docs.rs-66c2a5?style=for-the-badge&labelColor=555555&logo=docs.rs
//!
//! `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
//!
//! ```
//! # 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> {}
//! 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());
//! ```
#![no_std]
#![expect(
    clippy::doc_paragraphs_missing_punctuation,
    reason = "false positive for crate documentation having image links"
)]
#![expect(
    unstable_features,
    reason = "whole reason we require nightly is for btree_cursors"
)]
#![feature(btree_cursors)]
#[cfg(doc)]
extern crate alloc;
#[cfg(doc)]
use alloc::collections::BTreeMap;
#[cfg(doc)]
use core::ops::RangeBounds;
pub use zfc;
use zfc::Set;
/// A map of keys and values where the keys implement [`SetOrd`]. The map is backed by a B-tree.
mod superset_map;
/// A set of values where the values implement [`SetOrd`]. The set is backed by a B-tree.
pub mod superset_set;
pub use superset_map::SupersetMap;
pub use superset_set::SupersetSet;
/// Must conform to the following properties ∀`a`, `b`, `c`: `Self`:
/// * `a.is_subset(b)` ⇒ `a <= b`.
/// * `a.is_subset(b) && !(a.is_subset(c) || c.is_subset(b))` ⇒ `c` `<` `a` `<=` `b` ∨ `a` `<=` `b` `<` `c`.
///
/// In American English prose, the above simply states that one only need to check for the "next" element of `a`
/// in an ordered sequence of `Self`s to determine if there exists any superset of `a` in the entire sequence beside
/// `a` itself. Put in a different way, the "distance" between a set and a proper supserset is "less" than the "distance"
/// between the same set and a non-superset that is greater.
pub trait SetOrd: Ord + Set {}