commit c4f58b7ffcea7d0563649cc1e0368f0c183e9e1b
parent ed95bb90160c4586f3b58d43e6bce2c5ffbbd7c5
Author: Zack Newman <zack@philomathiclife.com>
Date: Fri, 6 Sep 2024 11:34:52 -0600
update deps. address lints
Diffstat:
| M | Cargo.toml | | | 18 | +++--------------- |
| M | README.md | | | 58 | ++++++++++++++++++++++++++++++++-------------------------- |
| M | src/lib.rs | | | 65 | ++++++++++++++++++++++++++++++++++++----------------------------- |
| M | src/superset_map.rs | | | 137 | ++++++++++++++++++++++++++++++------------------------------------------------- |
| M | src/superset_set.rs | | | 85 | ++++++++++++++++++++++++++++--------------------------------------------------- |
5 files changed, 153 insertions(+), 210 deletions(-)
diff --git a/Cargo.toml b/Cargo.toml
@@ -9,22 +9,10 @@ license = "MIT OR Apache-2.0"
name = "superset_map"
readme = "README.md"
repository = "https://git.philomathiclife.com/repos/superset_map/"
-version = "0.2.3"
-
-[lib]
-name = "superset_map"
-path = "src/lib.rs"
-
-[dependencies]
-zfc = { version = "0.3.2", default-features = false }
-
-[dev-dependencies]
-num-bigint = { version = "0.4.4", default-features = false }
+version = "0.3.0"
[badges]
maintenance = { status = "actively-developed" }
-[profile.release]
-lto = true
-panic = 'abort'
-strip = true
+[dependencies]
+zfc = { version = "0.4.0", default-features = false }
diff --git a/README.md b/README.md
@@ -1,19 +1,17 @@
-# `superset_map`
-
-`superset_map` is a library for [`Set`](https://docs.rs/zfc/latest/zfc/trait.Set.html)s that have an order defined on them.
-Its main data structure is [`SupersetMap`](https://docs.rs/superset_map/latest/superset_map/struct.SupersetMap.html)
-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).
-
-## Example
-
+# `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`.
+
+Nightly Rust is required. Once
+[`BTreeMap` cursors are stabilized](https://github.com/rust-lang/rust/issues/107540), stable Rust 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};
+use core::{borrow::Borrow, cmp::Ordering};
+use superset_map::{zfc::{num_bigint::BigUint, BoundedCardinality, Cardinality, Set}, SetOrd, SupersetSet};
#[derive(Clone, Copy, Eq, PartialEq)]
struct ShortAscii<'a> {
val: &'a [u8],
@@ -130,14 +128,22 @@ fn main() {
assert!(iter.next().is_none());
}
```
-
-### Status
-
-This package will be actively maintained until it is deemed “feature complete”.
-
-The crates are only tested on the `x86_64-unknown-linux-gnu` and `x86_64-unknown-openbsd` targets, but
-they should work on any [Tier 1 with Host Tools](https://doc.rust-lang.org/beta/rustc/platform-support.html)
-target.
-
-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.
+
+## License
+
+Licensed under either of
+
+* Apache License, Version 2.0 ([LICENSE-APACHE](LICENSE-APACHE) or http://www.apache.org/licenses/LICENSE-2.0).
+* MIT license ([LICENSE-MIT](LICENSE-MIT) or http://opensource.org/licenses/MIT).
+
+at your option.
+
+## Contribution
+
+Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you,
+as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.
+
+### Status
+
+The crate is only tested on `x86_64-unknown-linux-gnu` and `x86_64-unknown-openbsd` targets, but it should work
+on most platforms.
diff --git a/src/lib.rs b/src/lib.rs
@@ -1,22 +1,17 @@
//! # `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`](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).
+//! `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](https://github.com/rust-lang/rust/issues/107540), stable `rustc` will work.
+//! Nightly Rust is required. Once
+//! [`BTreeMap` cursors are stabilized](https://github.com/rust-lang/rust/issues/107540), stable Rust 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};
+//! ```
+//! # use core::{borrow::Borrow, cmp::Ordering};
+//! # use superset_map::{zfc::{num_bigint::BigUint, BoundedCardinality, Cardinality, Set}, SetOrd, SupersetSet};
//! #[derive(Clone, Copy, Eq, PartialEq)]
//! struct ShortAscii<'a> {
//! val: &'a [u8],
@@ -119,27 +114,27 @@
//! }
//! }
//! 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());
-//! }
+//! 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(
+ unknown_lints,
future_incompatible,
let_underscore,
missing_docs,
nonstandard_style,
+ refining_impl_trait,
rust_2018_compatibility,
rust_2018_idioms,
rust_2021_compatibility,
@@ -158,11 +153,23 @@
clippy::style,
clippy::suspicious
)]
-#![allow(
+#![expect(
clippy::blanket_clippy_restriction_lints,
- clippy::needless_doctest_main,
- clippy::pub_use
+ clippy::implicit_return,
+ clippy::min_ident_chars,
+ clippy::missing_trait_methods,
+ clippy::pub_use,
+ clippy::semicolon_outside_block,
+ clippy::single_char_lifetime_names,
+ reason = "noisy, opinionated, and likely doesn't prevent bugs or improve APIs"
)]
+#[cfg(doc)]
+extern crate alloc;
+#[cfg(doc)]
+use alloc::collections::BTreeMap;
+#[cfg(doc)]
+use core::ops::RangeBounds;
+pub use zfc;
use zfc::Set;
/// A map of keys and values where the keys implement [`SetOrd`]. The map is backed by a B-tree.
mod superset_map;
diff --git a/src/superset_map.rs b/src/superset_map.rs
@@ -1,50 +1,22 @@
-#![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::implicit_return,
- clippy::min_ident_chars,
- clippy::missing_trait_methods,
- clippy::semicolon_outside_block,
- clippy::single_char_lifetime_names
-)]
extern crate alloc;
use crate::SetOrd;
use alloc::collections::btree_map::{
BTreeMap, CursorMut, IntoIter, IntoKeys, IntoValues, Iter, IterMut, Keys, OccupiedEntry, Range,
RangeMut, Values, ValuesMut,
};
-use core::borrow::Borrow;
-use core::ops::{Bound, Index, RangeBounds};
+use core::{
+ borrow::Borrow,
+ ops::{Bound, Index, RangeBounds},
+};
/// A minimal collection of `(K, V)`s.
-/// Internally it is based on a [`BTreeMap`].
-/// When a `(K, V)` is [`SupersetMap::insert`]ed,
-/// it won't actually be inserted unless
-/// there isn't a `K` already in
-/// the map that is a superset of it.
-/// In such event, all `K`s that
-/// are subsets of the to-be-inserted `K`
-/// are removed before inserting the `K`.
-/// 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.
+///
+/// Internally it is based on a [`BTreeMap`]. When a `(K, V)` is [`SupersetMap::insert`]ed, it won't actually be
+/// inserted unless there isn't a `K` already in the map that is a superset of it. In such event, all `K`s that
+/// are subsets of the to-be-inserted `K` are removed before inserting the `K`.
+///
+/// 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.
#[derive(Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
pub struct SupersetMap<K, V> {
/// Collection of `(K, V)`s.
@@ -399,8 +371,11 @@ where
/// In the event `(key, value)` will be inserted, all `(K, V)`s
/// where the `K` is a subset of `key` are first removed before
/// inserting.
+ #[expect(
+ unsafe_code,
+ reason = "we rely on CursorMut::insert_before_unchecked since we verify it is safe to do so"
+ )]
#[inline]
- #[allow(unsafe_code)]
pub fn insert(&mut self, key: K, value: V) -> bool {
// Since the only way to `insert` a `(K, V)` is via this function,
// the following is true:
@@ -521,15 +496,13 @@ where
None
}
/// Removes all proper subsets of key from the map, returning the count removed.
- /// The key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match the ordering on the key type.
- /// # Overflow Behavior
- ///
- /// The method does no guarding against overflows, so the removal of more than `usize::MAX` elements either produces the wrong result or panics. If debug assertions are enabled, a panic is guaranteed.
- /// # Panics
- ///
- /// This function might panic if the number of elements removed is greater than `usize::MAX`.
- #[inline]
- #[allow(clippy::arithmetic_side_effects)]
+ /// The key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match
+ /// the ordering on the key type.
+ #[expect(
+ clippy::arithmetic_side_effects,
+ reason = "we count how many items are removed which can never exceed the length"
+ )]
+ #[inline]
pub fn remove_proper_subsets<Q>(&mut self, key: &Q) -> usize
where
K: Borrow<Q>,
@@ -548,15 +521,13 @@ where
count
}
/// Removes all proper supersets of key from the map, returning the count removed.
- /// The key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match the ordering on the key type.
- /// # Overflow Behavior
- ///
- /// The method does no guarding against overflows, so the removal of more than `usize::MAX` elements either produces the wrong result or panics. If debug assertions are enabled, a panic is guaranteed.
- /// # Panics
- ///
- /// This function might panic if the number of elements removed is greater than `usize::MAX`.
- #[inline]
- #[allow(clippy::arithmetic_side_effects)]
+ /// The key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match
+ /// the ordering on the key type.
+ #[expect(
+ clippy::arithmetic_side_effects,
+ reason = "we count how many items are removed which can never exceed the length"
+ )]
+ #[inline]
pub fn remove_proper_supersets<Q>(&mut self, key: &Q) -> usize
where
K: Borrow<Q>,
@@ -575,15 +546,13 @@ where
count
}
/// Removes all subsets of key from the map, returning the count removed.
- /// The key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match the ordering on the key type.
- /// # Overflow Behavior
- ///
- /// The method does no guarding against overflows, so the removal of more than `usize::MAX` elements either produces the wrong result or panics. If debug assertions are enabled, a panic is guaranteed.
- /// # Panics
- ///
- /// This function might panic if the number of elements removed is greater than `usize::MAX`.
- #[inline]
- #[allow(clippy::arithmetic_side_effects)]
+ /// The key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match
+ /// the ordering on the key type.
+ #[expect(
+ clippy::arithmetic_side_effects,
+ reason = "we count how many items are removed which can never exceed the length"
+ )]
+ #[inline]
pub fn remove_subsets<Q>(&mut self, key: &Q) -> usize
where
K: Borrow<Q>,
@@ -613,15 +582,13 @@ where
count
}
/// Removes all supersets of key from the map, returning the count removed.
- /// The key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match the ordering on the key type.
- /// # Overflow Behavior
- ///
- /// The method does no guarding against overflows, so the removal of more than `usize::MAX` elements either produces the wrong result or panics. If debug assertions are enabled, a panic is guaranteed.
- /// # Panics
- ///
- /// This function might panic if the number of elements removed is greater than `usize::MAX`.
- #[inline]
- #[allow(clippy::arithmetic_side_effects)]
+ /// The key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must
+ /// match the ordering on the key type.
+ #[expect(
+ clippy::arithmetic_side_effects,
+ reason = "we count how many items are removed which can never exceed the length"
+ )]
+ #[inline]
pub fn remove_supersets<Q>(&mut self, key: &Q) -> usize
where
K: Borrow<Q>,
@@ -629,16 +596,17 @@ where
{
let mut cursor = self.map.lower_bound_mut(Bound::Included(key));
let mut count = 0;
- // To avoid unnecessary checks for equivalence,
- // we separately call `is_superset` on the first element
+ // To avoid unnecessary checks for equivalence, // we separately call `is_superset` on the first element
// while calling `is_proper_superset` on the other elements.
if let Some(ge) = cursor.next() {
if ge.0.borrow().is_superset(key) {
cursor.remove_prev();
+ // `count` never exceeds `self.map.len()`; thus overflow is no worry.
count += 1;
while let Some(gt) = cursor.next() {
if gt.0.borrow().is_proper_superset(key) {
cursor.remove_prev();
+ // `count` never exceeds `self.map.len()`; thus overflow is no worry.
count += 1;
} else {
return count;
@@ -742,12 +710,11 @@ impl<'a, K, V> IntoIterator for &'a mut SupersetMap<K, V> {
}
#[cfg(test)]
mod tests {
- use super::SupersetMap;
- use crate::SetOrd;
- use core::borrow::Borrow;
- use core::cmp::Ordering;
- use num_bigint::BigUint;
- use zfc::{BoundedCardinality, Cardinality, Set};
+ use super::{
+ super::zfc::{num_bigint::BigUint, BoundedCardinality, Cardinality, Set},
+ SetOrd, SupersetMap,
+ };
+ use core::{borrow::Borrow, cmp::Ordering};
#[derive(Eq, PartialEq)]
struct ClosedInterval {
min: usize,
diff --git a/src/superset_set.rs b/src/superset_set.rs
@@ -1,36 +1,15 @@
-#![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::implicit_return,
- clippy::min_ident_chars,
- clippy::missing_trait_methods,
- clippy::same_name_method,
- clippy::semicolon_outside_block,
- clippy::shadow_unrelated,
- clippy::single_char_lifetime_names
-)]
extern crate alloc;
-use crate::{SetOrd, SupersetMap};
+use crate::{
+ zfc::{BoundedCardinality, Cardinality, Set},
+ SetOrd, SupersetMap,
+};
use alloc::collections::btree_map::{self, IntoKeys, Keys};
-use core::borrow::Borrow;
-use core::hash::{Hash, Hasher};
-use core::iter::FusedIterator;
-use core::ops::{BitAnd, BitOr, Bound, RangeBounds};
-use zfc::{BoundedCardinality, Cardinality, Set};
+use core::{
+ borrow::Borrow,
+ hash::{Hash, Hasher},
+ iter::FusedIterator,
+ ops::{BitAnd, BitOr, Bound, RangeBounds},
+};
/// A lazy iterator producing elements in the intersection of `SupersetSet`s.
///
/// This `struct` is created by [`SupersetSet::intersection`].
@@ -52,7 +31,6 @@ where
T: SetOrd,
{
type Item = &'a T;
- #[allow(clippy::else_if_without_else)]
#[inline]
fn next(&mut self) -> Option<Self::Item> {
loop {
@@ -66,6 +44,8 @@ where
}
} else if cur2.is_proper_subset(prev1) {
return Some(cur2);
+ } else {
+ // Do nothing.
}
} else {
self.prev_1 = None;
@@ -81,6 +61,8 @@ where
}
} else if cur1.is_proper_subset(prev2) {
return Some(cur1);
+ } else {
+ // Do nothing.
}
} else {
self.prev_1 = None;
@@ -96,6 +78,8 @@ where
} else if cur2.is_proper_subset(cur1) {
self.prev_1 = Some(cur1);
return Some(cur2);
+ } else {
+ // Do nothing.
}
} else {
return None;
@@ -208,21 +192,14 @@ impl<'a, T> Iterator for Range<'a, T> {
}
}
/// A minimal collection of `T`s.
-/// Internally it is based on a [`SupersetMap`].
-/// When a `T` is [`SupersetSet::insert`]ed,
-/// it won't actually be inserted unless
-/// there isn't a `T` already in
-/// the set that is a superset of it.
-/// In such event, all `T`s that
-/// are subsets of the to-be-inserted `T`
-/// are removed before inserting the `T`.
-/// 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 value
-/// will be inserted, a simple linear scan is sufficient
-/// to remove subsets avoiding the need to search
-/// the entire set.
+///
+/// Internally it is based on a [`SupersetMap`]. When a `T` is [`SupersetSet::insert`]ed, it won't actually be
+/// inserted unless there isn't a `T` already in the set that is a superset of it. In such event, all `T`s that
+/// are subsets of the to-be-inserted `T` are removed before inserting the `T`.
+///
+/// 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 value will be inserted,
+/// a simple linear scan is sufficient to remove subsets avoiding the need to search the entire set.
#[derive(Clone, Debug, Eq, Ord, PartialEq, PartialOrd)]
pub struct SupersetSet<T> {
/// Collection of `T`s.
@@ -269,6 +246,7 @@ where
T: Ord,
{
/// Read [`BTreeSet::contains`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html#method.contains).
+ #[expect(clippy::same_name_method, reason = "consistent with BTreeSet")]
#[inline]
pub fn contains<Q>(&self, value: &Q) -> bool
where
@@ -582,7 +560,6 @@ where
}
/// Adds a value to the set iff there doesn't already exist a proper superset of it.
/// In the event a value that is equal to it already exists, then it is replaced and returned.
- #[allow(clippy::option_if_let_else)]
#[inline]
pub fn replace(&mut self, value: T) -> Option<T> {
let prev = {
@@ -766,7 +743,6 @@ where
T: SetOrd,
{
type Item = &'a T;
- #[allow(clippy::else_if_without_else)]
#[inline]
fn next(&mut self) -> Option<Self::Item> {
loop {
@@ -826,12 +802,11 @@ where
}
#[cfg(test)]
mod tests {
- use super::SupersetSet;
- use crate::SetOrd;
- use core::borrow::Borrow;
- use core::cmp::Ordering;
- use num_bigint::BigUint;
- use zfc::{BoundedCardinality, Cardinality, Set};
+ use super::{
+ super::zfc::{num_bigint::BigUint, BoundedCardinality, Cardinality, Set},
+ SetOrd, SupersetSet,
+ };
+ use core::{borrow::Borrow, cmp::Ordering};
#[derive(Eq, PartialEq)]
struct ClosedInterval {
min: usize,
