lib.rs (7804B)
1 //! [![git]](https://git.philomathiclife.com/superset_map/log.html) [![crates-io]](https://crates.io/crates/superset_map) [![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 #![feature(btree_cursors)] 135 #![deny( 136 unknown_lints, 137 future_incompatible, 138 let_underscore, 139 missing_docs, 140 nonstandard_style, 141 refining_impl_trait, 142 rust_2018_compatibility, 143 rust_2018_idioms, 144 rust_2021_compatibility, 145 rust_2024_compatibility, 146 unsafe_code, 147 unused, 148 warnings, 149 clippy::all, 150 clippy::cargo, 151 clippy::complexity, 152 clippy::correctness, 153 clippy::nursery, 154 clippy::pedantic, 155 clippy::perf, 156 clippy::restriction, 157 clippy::style, 158 clippy::suspicious 159 )] 160 #![expect( 161 clippy::arbitrary_source_item_ordering, 162 clippy::blanket_clippy_restriction_lints, 163 clippy::implicit_return, 164 clippy::min_ident_chars, 165 clippy::missing_trait_methods, 166 clippy::pub_use, 167 clippy::return_and_then, 168 clippy::semicolon_outside_block, 169 clippy::single_char_lifetime_names, 170 reason = "noisy, opinionated, and likely doesn't prevent bugs or improve APIs" 171 )] 172 #[cfg(doc)] 173 extern crate alloc; 174 #[cfg(doc)] 175 use alloc::collections::BTreeMap; 176 #[cfg(doc)] 177 use core::ops::RangeBounds; 178 pub use zfc; 179 use zfc::Set; 180 /// A map of keys and values where the keys implement [`SetOrd`]. The map is backed by a B-tree. 181 mod superset_map; 182 /// A set of values where the values implement [`SetOrd`]. The set is backed by a B-tree. 183 pub mod superset_set; 184 pub use superset_map::SupersetMap; 185 pub use superset_set::SupersetSet; 186 /// Must conform to the following properties ∀`a`, `b`, `c`: `Self`: 187 /// * `a.is_subset(b)` ⇒ `a <= b`. 188 /// * `a.is_subset(b) && !(a.is_subset(c) || c.is_subset(b))` ⇒ `c` `<` `a` `<=` `b` ∨ `a` `<=` `b` `<` `c`. 189 /// 190 /// In American English prose, the above simply states that one only need to check for the "next" element of `a` 191 /// in an ordered sequence of `Self`s to determine if there exists any superset of `a` in the entire sequence beside 192 /// `a` itself. Put in a different way, the "distance" between a set and a proper supserset is "less" than the "distance" 193 /// between the same set and a non-superset that is greater. 194 pub trait SetOrd: Ord + Set {}