Crate superset_map
source ·Expand description
§superset_map
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
.
Version 1.69.0
or newer of nightly rustc
is required. Once
BTreeMap
cursors are stabilized, stable rustc
will work.
§Example
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());
}
Re-exports§
pub use superset_set::SupersetSet;
Modules§
- A set of values where the values implement
SetOrd
. The set is backed by a B-tree.
Structs§
- A minimal collection of
(K, V)
s. Internally it is based on aBTreeMap
. When a(K, V)
isSupersetMap::insert
ed, it won’t actually be inserted unless there isn’t aK
already in the map that is a superset of it. In such event, allK
s that are subsets of the to-be-insertedK
are removed before inserting theK
. Note this can have quite good performance due to the fact that a single search is necessary to detect if insertion should occur; furthermore since all subsets occur immediately before where the key will be inserted, a simple linear scan is sufficient to remove subsets avoiding the need to search the entire map.
Traits§
- Must conform to the following properties ∀
a
,b
,c
:Self
: