//! # `superset_map`
//!
//! `superset_map` is a library for [`Set`]s that have an order defined on them.
//! It's main data structure is [`SupersetMap`] which is a specialized version of
//! [`BTreeMap`](https://doc.rust-lang.org/alloc/collections/btree_map/struct.BTreeMap.html)
//! where only supersets are stored. This can be useful when the keys don't fit well or at all with the concept of
//! [`RangeBounds`](https://doc.rust-lang.org/stable/core/ops/trait.RangeBounds.html).
//!
//! Version `1.69.0` or newer of nightly `rustc` is required. Once
//! [`BTreeMap` cursors are stabilized](https://github.com/rust-lang/rust/issues/107540), stable `rustc` will work.
//!
//! ## Example
//!
//! ```rust
//! 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());
//! }
//! ```
#![no_std]
#![feature(btree_cursors)]
#![deny(
    unsafe_code,
    unused,
    warnings,
    clippy::all,
    clippy::cargo,
    clippy::complexity,
    clippy::correctness,
    clippy::nursery,
    clippy::pedantic,
    clippy::perf,
    clippy::restriction,
    clippy::style,
    clippy::suspicious
)]
#![allow(
    clippy::blanket_clippy_restriction_lints,
    clippy::needless_doctest_main,
    clippy::pub_use
)]
use zfc::Set;
/// A map of keys and values where the keys implement [`SetOrd`]. The map is backed by a B-tree.
pub 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 {}