superset_map/
lib.rs

1//! [![git]](https://git.philomathiclife.com/superset_map/log.html)&ensp;[![crates-io]](https://crates.io/crates/superset_map)&ensp;[![docs-rs]](crate)
2//!
3//! [git]: https://git.philomathiclife.com/git_badge.svg
4//! [crates-io]: https://img.shields.io/badge/crates.io-fc8d62?style=for-the-badge&labelColor=555555&logo=rust
5//! [docs-rs]: https://img.shields.io/badge/docs.rs-66c2a5?style=for-the-badge&labelColor=555555&logo=docs.rs
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//! ```
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//! let mut set = SupersetSet::new();
122//! set.insert(WildcardAscii::Plain(ShortAscii::new(b"foo").unwrap()));
123//! set.insert(WildcardAscii::Plain(ShortAscii::new(b"bar").unwrap()));
124//! set.insert(WildcardAscii::Wildcard(ShortAscii::new(b"b").unwrap()));
125//! set.insert(WildcardAscii::Wildcard(ShortAscii::new(b"bar").unwrap()));
126//! let mut iter = set.into_iter();
127//! assert!(iter.next().map_or(false, |s| s
128//!     == WildcardAscii::Wildcard(ShortAscii::new(b"b").unwrap())));
129//! assert!(iter.next().map_or(false, |s| s
130//!     == WildcardAscii::Plain(ShortAscii::new(b"foo").unwrap())));
131//! assert!(iter.next().is_none());
132//! ```
133#![no_std]
134#![expect(
135    clippy::doc_paragraphs_missing_punctuation,
136    reason = "false positive for crate documentation having image links"
137)]
138#![expect(
139    unstable_features,
140    reason = "whole reason we require nightly is for btree_cursors"
141)]
142#![feature(btree_cursors)]
143#[cfg(doc)]
144extern crate alloc;
145#[cfg(doc)]
146use alloc::collections::BTreeMap;
147#[cfg(doc)]
148use core::ops::RangeBounds;
149pub use zfc;
150use zfc::Set;
151/// A map of keys and values where the keys implement [`SetOrd`]. The map is backed by a B-tree.
152mod superset_map;
153/// A set of values where the values implement [`SetOrd`]. The set is backed by a B-tree.
154pub mod superset_set;
155pub use superset_map::SupersetMap;
156pub use superset_set::SupersetSet;
157/// Must conform to the following properties ∀`a`, `b`, `c`: `Self`:
158/// * `a.is_subset(b)` ⇒ `a <= b`.
159/// * `a.is_subset(b) && !(a.is_subset(c) || c.is_subset(b))` ⇒ `c` `<` `a` `<=` `b` ∨ `a` `<=` `b` `<` `c`.
160///
161/// In American English prose, the above simply states that one only need to check for the "next" element of `a`
162/// in an ordered sequence of `Self`s to determine if there exists any superset of `a` in the entire sequence beside
163/// `a` itself. Put in a different way, the "distance" between a set and a proper supserset is "less" than the "distance"
164/// between the same set and a non-superset that is greater.
165pub trait SetOrd: Ord + Set {}
superset_map/lib.rs

superset_map/
lib.rs
