commit d155089de6402237d3921014d7d1d61a9372f6e0
parent 3f5fa3faed9434e1ea245518b8d3b1a010743c90
Author: Zack Newman <zack@philomathiclife.com>
Date: Tue, 30 Jan 2024 13:24:13 -0700
use updated cursor api
Diffstat:
3 files changed, 99 insertions(+), 94 deletions(-)
diff --git a/Cargo.toml b/Cargo.toml
@@ -9,7 +9,7 @@ license = "MIT OR Apache-2.0"
name = "superset_map"
readme = "README.md"
repository = "https://git.philomathiclife.com/repos/superset_map/"
-version = "0.2.1"
+version = "0.2.2"
[lib]
name = "superset_map"
diff --git a/src/superset_map.rs b/src/superset_map.rs
@@ -266,7 +266,7 @@ where
pub fn contains_proper_subset<Q>(&self, key: &Q) -> bool
where
K: Borrow<Q>,
- Q: SetOrd,
+ Q: SetOrd + ?Sized,
{
self.get_greatest_proper_subset(key).is_some()
}
@@ -276,7 +276,7 @@ where
pub fn contains_proper_superset<Q>(&self, key: &Q) -> bool
where
K: Borrow<Q>,
- Q: SetOrd,
+ Q: SetOrd + ?Sized,
{
self.get_least_proper_superset(key).is_some()
}
@@ -286,7 +286,7 @@ where
pub fn contains_subset<Q>(&self, key: &Q) -> bool
where
K: Borrow<Q>,
- Q: SetOrd,
+ Q: SetOrd + ?Sized,
{
self.get_greatest_subset(key).is_some()
}
@@ -296,7 +296,7 @@ where
pub fn contains_superset<Q>(&self, key: &Q) -> bool
where
K: Borrow<Q>,
- Q: SetOrd,
+ Q: SetOrd + ?Sized,
{
self.get_least_superset(key).is_some()
}
@@ -306,7 +306,7 @@ where
pub fn get_greatest_proper_subset<Q>(&self, key: &Q) -> Option<&V>
where
K: Borrow<Q>,
- Q: SetOrd,
+ Q: SetOrd + ?Sized,
{
self.get_greatest_proper_subset_key_value(key)
.map(|(_, val)| val)
@@ -317,11 +317,11 @@ where
pub fn get_greatest_proper_subset_key_value<Q>(&self, key: &Q) -> Option<(&K, &V)>
where
K: Borrow<Q>,
- Q: SetOrd,
+ Q: SetOrd + ?Sized,
{
self.map
.upper_bound(Bound::Excluded(key))
- .key_value()
+ .peek_prev()
.and_then(|pair| pair.0.borrow().is_proper_subset(key).then_some(pair))
}
/// Returns a reference to the value corresponding to the greatest subset of key.
@@ -330,7 +330,7 @@ where
pub fn get_greatest_subset<Q>(&self, key: &Q) -> Option<&V>
where
K: Borrow<Q>,
- Q: SetOrd,
+ Q: SetOrd + ?Sized,
{
self.get_greatest_subset_key_value(key).map(|(_, val)| val)
}
@@ -340,11 +340,11 @@ where
pub fn get_greatest_subset_key_value<Q>(&self, key: &Q) -> Option<(&K, &V)>
where
K: Borrow<Q>,
- Q: SetOrd,
+ Q: SetOrd + ?Sized,
{
self.map
.upper_bound(Bound::Included(key))
- .key_value()
+ .peek_prev()
.and_then(|pair| pair.0.borrow().is_subset(key).then_some(pair))
}
/// Returns a reference to the value corresponding to the least proper superset of key.
@@ -353,7 +353,7 @@ where
pub fn get_least_proper_superset<Q>(&self, key: &Q) -> Option<&V>
where
K: Borrow<Q>,
- Q: SetOrd,
+ Q: SetOrd + ?Sized,
{
self.get_least_proper_superset_key_value(key)
.map(|(_, val)| val)
@@ -364,11 +364,11 @@ where
pub fn get_least_proper_superset_key_value<Q>(&self, key: &Q) -> Option<(&K, &V)>
where
K: Borrow<Q>,
- Q: SetOrd,
+ Q: SetOrd + ?Sized,
{
self.map
.lower_bound(Bound::Excluded(key))
- .key_value()
+ .peek_next()
.and_then(|pair| pair.0.borrow().is_proper_superset(key).then_some(pair))
}
/// Returns a reference to the value corresponding to the least superset of key.
@@ -377,7 +377,7 @@ where
pub fn get_least_superset<Q>(&self, key: &Q) -> Option<&V>
where
K: Borrow<Q>,
- Q: SetOrd,
+ Q: SetOrd + ?Sized,
{
self.get_least_superset_key_value(key).map(|(_, val)| val)
}
@@ -387,11 +387,11 @@ where
pub fn get_least_superset_key_value<Q>(&self, key: &Q) -> Option<(&K, &V)>
where
K: Borrow<Q>,
- Q: SetOrd,
+ Q: SetOrd + ?Sized,
{
self.map
.lower_bound(Bound::Included(key))
- .key_value()
+ .peek_next()
.and_then(|pair| pair.0.borrow().is_superset(key).then_some(pair))
}
/// `(key, value)` is inserted iff there doesn't already
@@ -412,17 +412,22 @@ where
// the beginning of `map` or a `K` is not a subset of `key`
// removing all `(K, V)`s where the `K` is a subset before we insert `(key, value)`.
let mut cursor = self.map.lower_bound_mut(Bound::Included(&key));
- if let Some(ge) = cursor.key() {
- if ge.is_superset(&key) {
+ if let Some(ge) = cursor.peek_next() {
+ if ge.0.is_superset(&key) {
return false;
}
}
- cursor.move_prev();
- while let Some(lt) = cursor.key() {
- if key.is_proper_superset(lt) {
- cursor.remove_current_and_move_back();
- } else {
- break;
+ loop {
+ match cursor.prev() {
+ None => break,
+ Some(lt) => {
+ if key.is_proper_superset(lt.0) {
+ cursor.remove_next();
+ } else {
+ cursor.next();
+ break;
+ }
+ }
}
}
// SAFETY:
@@ -438,7 +443,7 @@ where
// Note that due to the requirements of `SetOrd`, a `K` that
// `is_proper_superset` another `K` is also strictly greater.
unsafe {
- cursor.insert_after_unchecked(key, value);
+ cursor.insert_before_unchecked(key, value);
}
true
}
@@ -447,7 +452,7 @@ where
pub(crate) fn lower_bound_mut<Q>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V>
where
K: Borrow<Q>,
- Q: SetOrd,
+ Q: SetOrd + ?Sized,
{
self.map.lower_bound_mut(bound)
}
@@ -457,12 +462,12 @@ where
pub fn remove_greatest_proper_subset<Q>(&mut self, key: &Q) -> Option<(K, V)>
where
K: Borrow<Q>,
- Q: SetOrd,
+ Q: SetOrd + ?Sized,
{
let mut cursor = self.map.upper_bound_mut(Bound::Excluded(key));
- if let Some(lt) = cursor.key() {
- if lt.borrow().is_proper_subset(key) {
- return cursor.remove_current();
+ if let Some(lt) = cursor.peek_prev() {
+ if lt.0.borrow().is_proper_subset(key) {
+ return cursor.remove_prev();
}
}
None
@@ -473,12 +478,12 @@ where
pub fn remove_greatest_subset<Q>(&mut self, key: &Q) -> Option<(K, V)>
where
K: Borrow<Q>,
- Q: SetOrd,
+ Q: SetOrd + ?Sized,
{
let mut cursor = self.map.upper_bound_mut(Bound::Included(key));
- if let Some(le) = cursor.key() {
- if le.borrow().is_subset(key) {
- return cursor.remove_current();
+ if let Some(le) = cursor.peek_prev() {
+ if le.0.borrow().is_subset(key) {
+ return cursor.remove_prev();
}
}
None
@@ -489,12 +494,12 @@ where
pub fn remove_least_proper_superset<Q>(&mut self, key: &Q) -> Option<(K, V)>
where
K: Borrow<Q>,
- Q: SetOrd,
+ Q: SetOrd + ?Sized,
{
let mut cursor = self.map.lower_bound_mut(Bound::Excluded(key));
- if let Some(gt) = cursor.key() {
- if gt.borrow().is_proper_superset(key) {
- return cursor.remove_current();
+ if let Some(gt) = cursor.peek_next() {
+ if gt.0.borrow().is_proper_superset(key) {
+ return cursor.remove_next();
}
}
None
@@ -505,12 +510,12 @@ where
pub fn remove_least_superset<Q>(&mut self, key: &Q) -> Option<(K, V)>
where
K: Borrow<Q>,
- Q: SetOrd,
+ Q: SetOrd + ?Sized,
{
let mut cursor = self.map.lower_bound_mut(Bound::Included(key));
- if let Some(ge) = cursor.key() {
- if ge.borrow().is_superset(key) {
- return cursor.remove_current();
+ if let Some(ge) = cursor.peek_next() {
+ if ge.0.borrow().is_superset(key) {
+ return cursor.remove_next();
}
}
None
@@ -528,13 +533,13 @@ where
pub fn remove_proper_subsets<Q>(&mut self, key: &Q) -> usize
where
K: Borrow<Q>,
- Q: SetOrd,
+ Q: SetOrd + ?Sized,
{
let mut cursor = self.map.upper_bound_mut(Bound::Excluded(key));
let mut count = 0;
- while let Some(lt) = cursor.key() {
- if lt.borrow().is_proper_subset(key) {
- cursor.remove_current_and_move_back();
+ while let Some(lt) = cursor.prev() {
+ if lt.0.borrow().is_proper_subset(key) {
+ cursor.remove_next();
count += 1;
} else {
return count;
@@ -555,13 +560,13 @@ where
pub fn remove_proper_supersets<Q>(&mut self, key: &Q) -> usize
where
K: Borrow<Q>,
- Q: SetOrd,
+ Q: SetOrd + ?Sized,
{
let mut cursor = self.map.lower_bound_mut(Bound::Excluded(key));
let mut count = 0;
- while let Some(gt) = cursor.key() {
- if gt.borrow().is_proper_superset(key) {
- cursor.remove_current();
+ while let Some(gt) = cursor.next() {
+ if gt.0.borrow().is_proper_superset(key) {
+ cursor.remove_prev();
count += 1;
} else {
return count;
@@ -582,20 +587,20 @@ where
pub fn remove_subsets<Q>(&mut self, key: &Q) -> usize
where
K: Borrow<Q>,
- Q: SetOrd,
+ Q: SetOrd + ?Sized,
{
let mut cursor = self.map.upper_bound_mut(Bound::Included(key));
let mut count = 0;
// To avoid unnecessary checks for equivalence,
// we separately call `is_subset` on the first element
// while calling `is_proper_subset` on the other elements.
- if let Some(le) = cursor.key() {
- if le.borrow().is_subset(key) {
- cursor.remove_current_and_move_back();
+ if let Some(le) = cursor.prev() {
+ if le.0.borrow().is_subset(key) {
+ cursor.remove_next();
count += 1;
- while let Some(lt) = cursor.key() {
- if lt.borrow().is_proper_subset(key) {
- cursor.remove_current_and_move_back();
+ while let Some(lt) = cursor.prev() {
+ if lt.0.borrow().is_proper_subset(key) {
+ cursor.remove_next();
count += 1;
} else {
return count;
@@ -620,20 +625,20 @@ where
pub fn remove_supersets<Q>(&mut self, key: &Q) -> usize
where
K: Borrow<Q>,
- Q: SetOrd,
+ Q: SetOrd + ?Sized,
{
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
// while calling `is_proper_superset` on the other elements.
- if let Some(ge) = cursor.key() {
- if ge.borrow().is_superset(key) {
- cursor.remove_current();
+ if let Some(ge) = cursor.next() {
+ if ge.0.borrow().is_superset(key) {
+ cursor.remove_prev();
count += 1;
- while let Some(gt) = cursor.key() {
- if gt.borrow().is_proper_superset(key) {
- cursor.remove_current();
+ while let Some(gt) = cursor.next() {
+ if gt.0.borrow().is_proper_superset(key) {
+ cursor.remove_prev();
count += 1;
} else {
return count;
diff --git a/src/superset_set.rs b/src/superset_set.rs
@@ -196,7 +196,7 @@ impl<'a, T> Default for Range<'a, T> {
impl<'a, T> DoubleEndedIterator for Range<'a, T> {
#[inline]
fn next_back(&mut self) -> Option<Self::Item> {
- self.iter.next_back().map(|(key, _)| key)
+ self.iter.next_back().map(|(key, &())| key)
}
}
impl<'a, T> FusedIterator for Range<'a, T> {}
@@ -204,7 +204,7 @@ impl<'a, T> Iterator for Range<'a, T> {
type Item = &'a T;
#[inline]
fn next(&mut self) -> Option<Self::Item> {
- self.iter.next().map(|(key, _)| key)
+ self.iter.next().map(|(key, &())| key)
}
}
/// A minimal collection of `T`s.
@@ -281,7 +281,7 @@ where
#[inline]
#[must_use]
pub fn first(&self) -> Option<&T> {
- self.map.first_key_value().map(|(key, _)| key)
+ self.map.first_key_value().map(|(key, &())| key)
}
/// Read [`BTreeSet::get`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html#method.get).
#[inline]
@@ -290,13 +290,13 @@ where
T: Borrow<Q>,
Q: Ord + ?Sized,
{
- self.map.get_key_value(value).map(|(key, _)| key)
+ self.map.get_key_value(value).map(|(key, &())| key)
}
/// Read [`BTreeSet::last`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html#method.last).
#[inline]
#[must_use]
pub fn last(&self) -> Option<&T> {
- self.map.last_key_value().map(|(key, _)| key)
+ self.map.last_key_value().map(|(key, &())| key)
}
/// Read [`BTreeSet::pop_first`](https://doc.rust-lang.org/alloc/collections/btree_set/struct.BTreeSet.html#method.pop_first).
#[inline]
@@ -369,7 +369,7 @@ where
pub fn contains_proper_subset<Q>(&self, value: &Q) -> bool
where
T: Borrow<Q>,
- Q: SetOrd,
+ Q: SetOrd + ?Sized,
{
self.map.contains_proper_subset(value)
}
@@ -379,7 +379,7 @@ where
pub fn contains_proper_superset<Q>(&self, value: &Q) -> bool
where
T: Borrow<Q>,
- Q: SetOrd,
+ Q: SetOrd + ?Sized,
{
self.map.contains_proper_superset(value)
}
@@ -389,7 +389,7 @@ where
pub fn contains_subset<Q>(&self, value: &Q) -> bool
where
T: Borrow<Q>,
- Q: SetOrd,
+ Q: SetOrd + ?Sized,
{
self.map.contains_subset(value)
}
@@ -399,7 +399,7 @@ where
pub fn contains_superset<Q>(&self, value: &Q) -> bool
where
T: Borrow<Q>,
- Q: SetOrd,
+ Q: SetOrd + ?Sized,
{
self.map.contains_superset(value)
}
@@ -409,11 +409,11 @@ where
pub fn get_greatest_proper_subset<Q>(&self, value: &Q) -> Option<&T>
where
T: Borrow<Q>,
- Q: SetOrd,
+ Q: SetOrd + ?Sized,
{
self.map
.get_greatest_proper_subset_key_value(value)
- .map(|(key, _)| key)
+ .map(|(key, &())| key)
}
/// Returns a reference to the value corresponding to the greatest subset of the passed value.
/// The value may be any borrowed form of the set’s value type, but the ordering on the borrowed form must match the ordering on the value type.
@@ -421,11 +421,11 @@ where
pub fn get_greatest_subset<Q>(&self, value: &Q) -> Option<&T>
where
T: Borrow<Q>,
- Q: SetOrd,
+ Q: SetOrd + ?Sized,
{
self.map
.get_greatest_subset_key_value(value)
- .map(|(key, _)| key)
+ .map(|(key, &())| key)
}
/// Returns a reference to the value corresponding to the least proper superset of the passed value.
/// The value may be any borrowed form of the set’s value type, but the ordering on the borrowed form must match the ordering on the value type.
@@ -433,11 +433,11 @@ where
pub fn get_least_proper_superset<Q>(&self, value: &Q) -> Option<&T>
where
T: Borrow<Q>,
- Q: SetOrd,
+ Q: SetOrd + ?Sized,
{
self.map
.get_least_proper_superset_key_value(value)
- .map(|(key, _)| key)
+ .map(|(key, &())| key)
}
/// Returns a reference to the value corresponding to the least superset of the passed value.
/// The value may be any borrowed form of the set’s value type, but the ordering on the borrowed form must match the ordering on the value type.
@@ -445,11 +445,11 @@ where
pub fn get_least_superset<Q>(&self, value: &Q) -> Option<&T>
where
T: Borrow<Q>,
- Q: SetOrd,
+ Q: SetOrd + ?Sized,
{
self.map
.get_least_superset_key_value(value)
- .map(|(key, _)| key)
+ .map(|(key, &())| key)
}
/// `value` is inserted iff there doesn't already
/// exist a `T` that is a superset of `value`.
@@ -478,7 +478,7 @@ where
pub fn remove_greatest_proper_subset<Q>(&mut self, value: &Q) -> Option<T>
where
T: Borrow<Q>,
- Q: SetOrd,
+ Q: SetOrd + ?Sized,
{
self.map
.remove_greatest_proper_subset(value)
@@ -490,7 +490,7 @@ where
pub fn remove_greatest_subset<Q>(&mut self, value: &Q) -> Option<T>
where
T: Borrow<Q>,
- Q: SetOrd,
+ Q: SetOrd + ?Sized,
{
self.map.remove_greatest_subset(value).map(|(key, ())| key)
}
@@ -500,7 +500,7 @@ where
pub fn remove_least_proper_superset<Q>(&mut self, value: &Q) -> Option<T>
where
T: Borrow<Q>,
- Q: SetOrd,
+ Q: SetOrd + ?Sized,
{
self.map
.remove_least_proper_superset(value)
@@ -512,7 +512,7 @@ where
pub fn remove_least_superset<Q>(&mut self, value: &Q) -> Option<T>
where
T: Borrow<Q>,
- Q: SetOrd,
+ Q: SetOrd + ?Sized,
{
self.map.remove_least_superset(value).map(|(key, ())| key)
}
@@ -528,7 +528,7 @@ where
pub fn remove_proper_subsets<Q>(&mut self, value: &Q) -> usize
where
T: Borrow<Q>,
- Q: SetOrd,
+ Q: SetOrd + ?Sized,
{
self.map.remove_proper_subsets(value)
}
@@ -544,7 +544,7 @@ where
pub fn remove_proper_supersets<Q>(&mut self, value: &Q) -> usize
where
T: Borrow<Q>,
- Q: SetOrd,
+ Q: SetOrd + ?Sized,
{
self.map.remove_proper_supersets(value)
}
@@ -560,7 +560,7 @@ where
pub fn remove_subsets<Q>(&mut self, value: &Q) -> usize
where
T: Borrow<Q>,
- Q: SetOrd,
+ Q: SetOrd + ?Sized,
{
self.map.remove_subsets(value)
}
@@ -576,7 +576,7 @@ where
pub fn remove_supersets<Q>(&mut self, value: &Q) -> usize
where
T: Borrow<Q>,
- Q: SetOrd,
+ Q: SetOrd + ?Sized,
{
self.map.remove_supersets(value)
}
@@ -587,9 +587,9 @@ where
pub fn replace(&mut self, value: T) -> Option<T> {
let prev = {
let mut cursor = self.map.lower_bound_mut(Bound::Included(&value));
- if let Some(ge) = cursor.key() {
- if *ge == value {
- cursor.remove_current().map(|(key, ())| key)
+ if let Some(ge) = cursor.next() {
+ if *ge.0 == value {
+ cursor.remove_prev().map(|(key, ())| key)
} else {
None
}
@@ -607,7 +607,7 @@ where
where
F: FnMut(&T) -> bool,
{
- self.map.retain(|key, _| f(key));
+ self.map.retain(|key, &mut ()| f(key));
}
/// Visits the elements representing the union, i.e., the supersets of elements that are in `self` or `other`, in ascending order.
/// For example if `self` contains a sequence of sets each of which being a subset of the same set in `other`, then only the superset in `other` will be iterated.
