lib.rs (7318B)
1 //! # `superset_map` 2 //! 3 //! `superset_map` is a library for [`Set`]s that have an order defined on them. Its main data structure is 4 //! [`SupersetMap`] which is a specialized version of [`BTreeMap`] where only supersets are stored. This can be 5 //! useful when the keys don't fit well or at all with the concept of [`RangeBounds`]. 6 //! 7 //! Nightly Rust is required. Once 8 //! [`BTreeMap` cursors are stabilized](https://github.com/rust-lang/rust/issues/107540), stable Rust will work. 9 //! 10 //! ## Example 11 //! 12 //! ``` 13 //! # use core::{borrow::Borrow, cmp::Ordering}; 14 //! # use superset_map::{zfc::{num_bigint::BigUint, BoundedCardinality, Cardinality, Set}, SetOrd, SupersetSet}; 15 //! #[derive(Clone, Copy, Eq, PartialEq)] 16 //! struct ShortAscii<'a> { 17 //! val: &'a [u8], 18 //! } 19 //! impl<'a> ShortAscii<'a> { 20 //! fn new(val: &'a [u8]) -> Option<ShortAscii<'a>> { 21 //! (val.len() <= 255 && val.is_ascii()).then_some(Self { val }) 22 //! } 23 //! fn len(self) -> u8 { 24 //! self.val.len().try_into().expect("The ShortAscii instance was not constructed properly and contains more than 255 bytes.") 25 //! } 26 //! } 27 //! #[derive(Clone, Copy, Eq, PartialEq)] 28 //! enum WildcardAscii<'a> { 29 //! Plain(ShortAscii<'a>), 30 //! // Represents a ShortAscii<'a> with an implicit wildcard at the end 31 //! // meaning it's all ShortAscii<'a>s that begin with the contained ShortAscii<'a>.val. 32 //! Wildcard(ShortAscii<'a>), 33 //! } 34 //! impl<'a> WildcardAscii<'a> { 35 //! const fn val(self) -> ShortAscii<'a> { 36 //! match self { 37 //! WildcardAscii::Plain(s) | WildcardAscii::Wildcard(s) => s, 38 //! } 39 //! } 40 //! const fn is_plain(self) -> bool { 41 //! match self { 42 //! WildcardAscii::Plain(_) => true, 43 //! WildcardAscii::Wildcard(_) => false, 44 //! } 45 //! } 46 //! const fn is_wildcard(self) -> bool { 47 //! !self.is_plain() 48 //! } 49 //! } 50 //! impl<'a> PartialOrd<Self> for WildcardAscii<'a> { 51 //! fn partial_cmp(&self, other: &Self) -> Option<Ordering> { 52 //! Some(self.cmp(other)) 53 //! } 54 //! } 55 //! impl<'a> Ord for WildcardAscii<'a> { 56 //! fn cmp(&self, other: &Self) -> Ordering { 57 //! let len = u8::min(self.val().len(), other.val().len()) as usize; 58 //! match self.val().val[..len].cmp(&other.val().val[..len]) { 59 //! Ordering::Less => Ordering::Less, 60 //! Ordering::Equal => { 61 //! if self.is_wildcard() { 62 //! if other.is_wildcard() { 63 //! self.val().len().cmp(&other.val().len()).reverse() 64 //! } else { 65 //! Ordering::Greater 66 //! } 67 //! } else if other.is_wildcard() { 68 //! Ordering::Less 69 //! } else { 70 //! self.val().len().cmp(&other.val().len()) 71 //! } 72 //! } 73 //! Ordering::Greater => Ordering::Greater, 74 //! } 75 //! } 76 //! } 77 //! impl<'a> Set for WildcardAscii<'a> { 78 //! type Elem = ShortAscii<'a>; 79 //! fn bounded_cardinality(&self) -> BoundedCardinality { 80 //! BoundedCardinality::new_exact(self.cardinality().unwrap()) 81 //! } 82 //! fn cardinality(&self) -> Option<Cardinality> { 83 //! Some(Cardinality::Finite(match *self { 84 //! WildcardAscii::Plain(_) => BigUint::new(vec![1]), 85 //! // Geometric series. 86 //! WildcardAscii::Wildcard(v) => { 87 //! (BigUint::new(vec![128]).pow((u8::MAX - v.len()) as u32 + 1) 88 //! - BigUint::new(vec![1])) 89 //! / BigUint::new(vec![127]) 90 //! } 91 //! })) 92 //! } 93 //! fn contains<Q>(&self, elem: &Q) -> bool 94 //! where 95 //! Q: Borrow<Self::Elem> + Eq + ?Sized, 96 //! { 97 //! match *self { 98 //! WildcardAscii::Plain(v) => v == *elem.borrow(), 99 //! WildcardAscii::Wildcard(v) => { 100 //! v.len() <= elem.borrow().len() && *v.val == elem.borrow().val[..v.len() as usize] 101 //! } 102 //! } 103 //! } 104 //! fn is_proper_subset(&self, val: &Self) -> bool { 105 //! val.is_wildcard() 106 //! && match val.val().len().cmp(&self.val().len()) { 107 //! Ordering::Less => val.val().val == &self.val().val[..val.val().len() as usize], 108 //! Ordering::Equal => self.is_plain() && self.val() == val.val(), 109 //! Ordering::Greater => false, 110 //! } 111 //! } 112 //! fn is_subset(&self, val: &Self) -> bool { 113 //! self == val || self.is_proper_subset(val) 114 //! } 115 //! } 116 //! impl<'a> SetOrd for WildcardAscii<'a> {} 117 //! let mut set = SupersetSet::new(); 118 //! set.insert(WildcardAscii::Plain(ShortAscii::new(b"foo").unwrap())); 119 //! set.insert(WildcardAscii::Plain(ShortAscii::new(b"bar").unwrap())); 120 //! set.insert(WildcardAscii::Wildcard(ShortAscii::new(b"b").unwrap())); 121 //! set.insert(WildcardAscii::Wildcard(ShortAscii::new(b"bar").unwrap())); 122 //! let mut iter = set.into_iter(); 123 //! assert!(iter.next().map_or(false, |s| s 124 //! == WildcardAscii::Wildcard(ShortAscii::new(b"b").unwrap()))); 125 //! assert!(iter.next().map_or(false, |s| s 126 //! == WildcardAscii::Plain(ShortAscii::new(b"foo").unwrap()))); 127 //! assert!(iter.next().is_none()); 128 //! ``` 129 #![no_std] 130 #![feature(btree_cursors)] 131 #![deny( 132 unknown_lints, 133 future_incompatible, 134 let_underscore, 135 missing_docs, 136 nonstandard_style, 137 refining_impl_trait, 138 rust_2018_compatibility, 139 rust_2018_idioms, 140 rust_2021_compatibility, 141 rust_2024_compatibility, 142 unsafe_code, 143 unused, 144 warnings, 145 clippy::all, 146 clippy::cargo, 147 clippy::complexity, 148 clippy::correctness, 149 clippy::nursery, 150 clippy::pedantic, 151 clippy::perf, 152 clippy::restriction, 153 clippy::style, 154 clippy::suspicious 155 )] 156 #![expect( 157 clippy::blanket_clippy_restriction_lints, 158 clippy::implicit_return, 159 clippy::min_ident_chars, 160 clippy::missing_trait_methods, 161 clippy::pub_use, 162 clippy::semicolon_outside_block, 163 clippy::single_char_lifetime_names, 164 reason = "noisy, opinionated, and likely doesn't prevent bugs or improve APIs" 165 )] 166 #[cfg(doc)] 167 extern crate alloc; 168 #[cfg(doc)] 169 use alloc::collections::BTreeMap; 170 #[cfg(doc)] 171 use core::ops::RangeBounds; 172 pub use zfc; 173 use zfc::Set; 174 /// A map of keys and values where the keys implement [`SetOrd`]. The map is backed by a B-tree. 175 mod superset_map; 176 /// A set of values where the values implement [`SetOrd`]. The set is backed by a B-tree. 177 pub mod superset_set; 178 pub use superset_map::SupersetMap; 179 pub use superset_set::SupersetSet; 180 /// Must conform to the following properties ∀`a`, `b`, `c`: `Self`: 181 /// * `a.is_subset(b)` ⇒ `a <= b`. 182 /// * `a.is_subset(b) && !(a.is_subset(c) || c.is_subset(b))` ⇒ `c` `<` `a` `<=` `b` ∨ `a` `<=` `b` `<` `c`. 183 /// 184 /// In American English prose, the above simply states that one only need to check for the "next" element of `a` 185 /// in an ordered sequence of `Self`s to determine if there exists any superset of `a` in the entire sequence beside 186 /// `a` itself. Put in a different way, the "distance" between a set and a proper supserset is "less" than the "distance" 187 /// between the same set and a non-superset that is greater. 188 pub trait SetOrd: Ord + Set {}