im-rc - cargo Package Compare versions

Comparing version 14.2.0 to 14.3.0

src/proptest.rs

+//! Proptest strategies.
+//!
+//! These are only available when using the `proptest` feature flag.
+
+use crate::{HashMap, HashSet, OrdMap, OrdSet, Vector};
+use ::proptest::collection::vec;
+use ::proptest::strategy::{BoxedStrategy, Strategy, ValueTree};
+use std::hash::Hash;
+use std::iter::FromIterator;
+use std::ops::Range;
+
+/// A strategy for generating a [`Vector`][Vector] of a certain size.
+///
+/// # Examples
+///
+/// ```rust,no_run
+/// # use ::proptest::proptest;
+/// proptest! {
+///     #[test]
+///     fn proptest_a_vector(ref l in vector(".*", 10..100)) {
+///         assert!(l.len() < 100);
+///         assert!(l.len() >= 10);
+///     }
+/// }
+/// ```
+///
+/// [Vector]: ../struct.Vector.html
+pub fn vector<A: Strategy + 'static>(
+    element: A,
+    size: Range<usize>,
+) -> BoxedStrategy<Vector<<A::Tree as ValueTree>::Value>>
+where
+    <A::Tree as ValueTree>::Value: Clone,
+{
+    vec(element, size).prop_map(Vector::from_iter).boxed()
+}
+
+/// A strategy for an [`OrdMap`][OrdMap] of a given size.
+///
+/// # Examples
+///
+/// ```rust,no_run
+/// # use ::proptest::proptest;
+/// proptest! {
+///     #[test]
+///     fn proptest_works(ref m in ord_map(0..9999, ".*", 10..100)) {
+///         assert!(m.len() < 100);
+///         assert!(m.len() >= 10);
+///     }
+/// }
+/// ```
+///
+/// [OrdMap]: ../struct.OrdMap.html
+pub fn ord_map<K: Strategy + 'static, V: Strategy + 'static>(
+    key: K,
+    value: V,
+    size: Range<usize>,
+) -> BoxedStrategy<OrdMap<<K::Tree as ValueTree>::Value, <V::Tree as ValueTree>::Value>>
+where
+    <K::Tree as ValueTree>::Value: Ord + Clone,
+    <V::Tree as ValueTree>::Value: Clone,
+{
+    ::proptest::collection::vec((key, value), size.clone())
+        .prop_map(OrdMap::from)
+        .prop_filter("OrdMap minimum size".to_owned(), move |m| {
+            m.len() >= size.start
+        })
+        .boxed()
+}
+
+/// A strategy for an [`OrdSet`][OrdSet] of a given size.
+///
+/// # Examples
+///
+/// ```rust,no_run
+/// # use ::proptest::proptest;
+/// proptest! {
+///     #[test]
+///     fn proptest_a_set(ref s in ord_set(".*", 10..100)) {
+///         assert!(s.len() < 100);
+///         assert!(s.len() >= 10);
+///     }
+/// }
+/// ```
+///
+/// [OrdSet]: ../struct.OrdSet.html
+pub fn ord_set<A: Strategy + 'static>(
+    element: A,
+    size: Range<usize>,
+) -> BoxedStrategy<OrdSet<<A::Tree as ValueTree>::Value>>
+where
+    <A::Tree as ValueTree>::Value: Ord + Clone,
+{
+    ::proptest::collection::vec(element, size.clone())
+        .prop_map(OrdSet::from)
+        .prop_filter("OrdSet minimum size".to_owned(), move |s| {
+            s.len() >= size.start
+        })
+        .boxed()
+}
+
+/// A strategy for a [`HashMap`][HashMap] of a given size.
+///
+/// # Examples
+///
+/// ```rust,no_run
+/// # use ::proptest::proptest;
+/// proptest! {
+///     #[test]
+///     fn proptest_works(ref m in hash_map(0..9999, ".*", 10..100)) {
+///         assert!(m.len() < 100);
+///         assert!(m.len() >= 10);
+///     }
+/// }
+/// ```
+///
+/// [HashMap]: ../struct.HashMap.html
+pub fn hash_map<K: Strategy + 'static, V: Strategy + 'static>(
+    key: K,
+    value: V,
+    size: Range<usize>,
+) -> BoxedStrategy<HashMap<<K::Tree as ValueTree>::Value, <V::Tree as ValueTree>::Value>>
+where
+    <K::Tree as ValueTree>::Value: Hash + Eq + Clone,
+    <V::Tree as ValueTree>::Value: Clone,
+{
+    ::proptest::collection::vec((key, value), size.clone())
+        .prop_map(HashMap::from)
+        .prop_filter("Map minimum size".to_owned(), move |m| {
+            m.len() >= size.start
+        })
+        .boxed()
+}
+
+/// A strategy for a [`HashSet`][HashSet] of a given size.
+///
+/// # Examples
+///
+/// ```rust,no_run
+/// # use ::proptest::proptest;
+/// proptest! {
+///     #[test]
+///     fn proptest_a_set(ref s in hash_set(".*", 10..100)) {
+///         assert!(s.len() < 100);
+///         assert!(s.len() >= 10);
+///     }
+/// }
+/// ```
+///
+/// [HashSet]: ../struct.HashSet.html
+pub fn hash_set<A: Strategy + 'static>(
+    element: A,
+    size: Range<usize>,
+) -> BoxedStrategy<HashSet<<A::Tree as ValueTree>::Value>>
+where
+    <A::Tree as ValueTree>::Value: Hash + Eq + Clone,
+{
+    ::proptest::collection::vec(element, size.clone())
+        .prop_map(HashSet::from)
+        .prop_filter("HashSet minimum size".to_owned(), move |s| {
+            s.len() >= size.start
+        })
+        .boxed()
+}

src/quickcheck.rs

+use crate::{HashMap, HashSet, OrdMap, OrdSet, Vector};
+use ::quickcheck::{Arbitrary, Gen};
+use std::hash::{BuildHasher, Hash};
+use std::iter::FromIterator;
+
+impl<A: Arbitrary + Sync + Clone> Arbitrary for Vector<A> {
+    fn arbitrary<G: Gen>(g: &mut G) -> Self {
+        Vector::from_iter(Vec::<A>::arbitrary(g))
+    }
+}
+
+impl<K: Ord + Clone + Arbitrary + Sync, V: Clone + Arbitrary + Sync> Arbitrary for OrdMap<K, V> {
+    fn arbitrary<G: Gen>(g: &mut G) -> Self {
+        OrdMap::from_iter(Vec::<(K, V)>::arbitrary(g))
+    }
+}
+
+impl<A: Ord + Clone + Arbitrary + Sync> Arbitrary for OrdSet<A> {
+    fn arbitrary<G: Gen>(g: &mut G) -> Self {
+        OrdSet::from_iter(Vec::<A>::arbitrary(g))
+    }
+}
+
+impl<A, S> Arbitrary for HashSet<A, S>
+where
+    A: Hash + Eq + Arbitrary + Sync,
+    S: BuildHasher + Default + Send + Sync + 'static,
+{
+    fn arbitrary<G: Gen>(g: &mut G) -> Self {
+        HashSet::from_iter(Vec::<A>::arbitrary(g))
+    }
+}
+
+impl<K, V, S> Arbitrary for HashMap<K, V, S>
+where
+    K: Hash + Eq + Arbitrary + Sync,
+    V: Arbitrary + Sync,
+    S: BuildHasher + Default + Send + Sync + 'static,
+{
+    fn arbitrary<G: Gen>(g: &mut G) -> Self {
+        HashMap::from(Vec::<(K, V)>::arbitrary(g))
+    }
+}

src/vector/rayon.rs

+//! Parallel iterators.
+//!
+//! These are only available when using the `rayon` feature flag.
+
+use super::*;
+use ::rayon::iter::plumbing::{bridge, Consumer, Producer, ProducerCallback, UnindexedConsumer};
+use ::rayon::iter::{
+    IndexedParallelIterator, IntoParallelRefIterator, IntoParallelRefMutIterator, ParallelIterator,
+};
+
+impl<'a, A> IntoParallelRefIterator<'a> for Vector<A>
+where
+    A: Clone + Send + Sync + 'a,
+{
+    type Item = &'a A;
+    type Iter = ParIter<'a, A>;
+
+    fn par_iter(&'a self) -> Self::Iter {
+        ParIter {
+            focus: self.focus(),
+        }
+    }
+}
+
+impl<'a, A> IntoParallelRefMutIterator<'a> for Vector<A>
+where
+    A: Clone + Send + Sync + 'a,
+{
+    type Item = &'a mut A;
+    type Iter = ParIterMut<'a, A>;
+
+    fn par_iter_mut(&'a mut self) -> Self::Iter {
+        ParIterMut {
+            focus: self.focus_mut(),
+        }
+    }
+}
+
+/// A parallel iterator for [`Vector`][Vector].
+///
+/// [Vector]: ../struct.Vector.html
+pub struct ParIter<'a, A>
+where
+    A: Clone + Send + Sync,
+{
+    focus: Focus<'a, A>,
+}
+
+impl<'a, A> ParallelIterator for ParIter<'a, A>
+where
+    A: Clone + Send + Sync + 'a,
+{
+    type Item = &'a A;
+
+    fn drive_unindexed<C>(self, consumer: C) -> C::Result
+    where
+        C: UnindexedConsumer<Self::Item>,
+    {
+        bridge(self, consumer)
+    }
+}
+
+impl<'a, A> IndexedParallelIterator for ParIter<'a, A>
+where
+    A: Clone + Send + Sync + 'a,
+{
+    fn drive<C>(self, consumer: C) -> C::Result
+    where
+        C: Consumer<Self::Item>,
+    {
+        bridge(self, consumer)
+    }
+
+    fn len(&self) -> usize {
+        self.focus.len()
+    }
+
+    fn with_producer<CB>(self, callback: CB) -> CB::Output
+    where
+        CB: ProducerCallback<Self::Item>,
+    {
+        callback.callback(VectorProducer { focus: self.focus })
+    }
+}
+
+/// A mutable parallel iterator for [`Vector`][Vector].
+///
+/// [Vector]: ../struct.Vector.html
+pub struct ParIterMut<'a, A>
+where
+    A: Clone + Send + Sync,
+{
+    focus: FocusMut<'a, A>,
+}
+
+impl<'a, A> ParallelIterator for ParIterMut<'a, A>
+where
+    A: Clone + Send + Sync + 'a,
+{
+    type Item = &'a mut A;
+
+    fn drive_unindexed<C>(self, consumer: C) -> C::Result
+    where
+        C: UnindexedConsumer<Self::Item>,
+    {
+        bridge(self, consumer)
+    }
+}
+
+impl<'a, A> IndexedParallelIterator for ParIterMut<'a, A>
+where
+    A: Clone + Send + Sync + 'a,
+{
+    fn drive<C>(self, consumer: C) -> C::Result
+    where
+        C: Consumer<Self::Item>,
+    {
+        bridge(self, consumer)
+    }
+
+    fn len(&self) -> usize {
+        self.focus.len()
+    }
+
+    fn with_producer<CB>(self, callback: CB) -> CB::Output
+    where
+        CB: ProducerCallback<Self::Item>,
+    {
+        callback.callback(VectorMutProducer { focus: self.focus })
+    }
+}
+
+struct VectorProducer<'a, A>
+where
+    A: Clone + Send + Sync,
+{
+    focus: Focus<'a, A>,
+}
+
+impl<'a, A> Producer for VectorProducer<'a, A>
+where
+    A: Clone + Send + Sync + 'a,
+{
+    type Item = &'a A;
+    type IntoIter = Iter<'a, A>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        self.focus.into_iter()
+    }
+
+    fn split_at(self, index: usize) -> (Self, Self) {
+        let (left, right) = self.focus.split_at(index);
+        (
+            VectorProducer { focus: left },
+            VectorProducer { focus: right },
+        )
+    }
+}
+
+struct VectorMutProducer<'a, A>
+where
+    A: Clone + Send + Sync,
+{
+    focus: FocusMut<'a, A>,
+}
+
+impl<'a, A> Producer for VectorMutProducer<'a, A>
+where
+    A: Clone + Send + Sync + 'a,
+{
+    type Item = &'a mut A;
+    type IntoIter = IterMut<'a, A>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        self.focus.into_iter()
+    }
+
+    fn split_at(self, index: usize) -> (Self, Self) {
+        let (left, right) = self.focus.split_at(index);
+        (
+            VectorMutProducer { focus: left },
+            VectorMutProducer { focus: right },
+        )
+    }
+}
+
+#[cfg(test)]
+mod test {
+    use super::super::*;
+    use super::proptest::vector;
+    use ::proptest::num::i32;
+    use ::proptest::proptest;
+    use ::rayon::iter::{IntoParallelRefIterator, IntoParallelRefMutIterator, ParallelIterator};
+
+    proptest! {
+        #[test]
+        fn par_iter(ref mut input in vector(i32::ANY, 0..10000)) {
+            assert_eq!(input.iter().max(), input.par_iter().max())
+        }
+
+        #[test]
+        fn par_mut_iter(ref mut input in vector(i32::ANY, 0..10000)) {
+            let mut vec = input.clone();
+            vec.par_iter_mut().for_each(|i| *i = i.overflowing_add(1).0);
+            let expected: Vector<i32> = input.clone().into_iter().map(|i| i.overflowing_add(1).0).collect();
+            assert_eq!(expected, vec);
+        }
+    }
+}

Cargo.toml

@@ -16,3 +16,3 @@ # THIS FILE IS AUTOMATICALLY GENERATED BY CARGO
 name = "im-rc"
-version = "14.2.0"
+version = "14.3.0"
 authors = ["Bodil Stokke <[e-mail]>"]
@@ -34,3 +34,3 @@ build = "./build.rs"
 [dependencies.arbitrary]
-version = "0.3"
+version = "0.4"
 optional = true
@@ -37,0 +37,0 @@

CHANGELOG.md

@@ -8,2 +8,19 @@ # Changelog
 
+## [14.3.0] - 2020-03-03
+
+### Changed
+
+-   `proptest` strategies have been moved to `im::proptest`. The previous locations of the
+    strategies (`im::vector::proptest` etc) are still available, but have been deprecated.
+
+### Added
+
+-   `OrdSet` and `OrdMap` now have `get_prev` and `get_next` methods (with equivalent `get_prev_mut`
+    and `get_next_mut` methods for `OrdMap`) which will return the closest key match to the
+    requested key in the specified direction if the key isn't in the set. (#95)
+-   The `retain` method, inexplicably missing from `HashMap` but not `HashSet`, has been added.
+    (#120)
+-   The `get_mut` method on `OrdMap` was, equally inexplicably, private. It has now been made
+    public.
+
 ## [14.2.0] - 2020-01-17
@@ -10,0 +27,0 @@

src/arbitrary.rs

@@ -54,4 +54,6 @@ // This Source Code Form is subject to the terms of the Mozilla Public
 
-    fn size_hint() -> (usize, Option<usize>) {
-        size_hint::and(<usize as Arbitrary>::size_hint(), (0, None))
+    fn size_hint(depth: usize) -> (usize, Option<usize>) {
+        size_hint::recursion_guard(depth, |depth| {
+            size_hint::and(<usize as Arbitrary>::size_hint(depth), (0, None))
+        })
     }
@@ -74,4 +76,6 @@
 
-    fn size_hint() -> (usize, Option<usize>) {
-        size_hint::and(<usize as Arbitrary>::size_hint(), (0, None))
+    fn size_hint(depth: usize) -> (usize, Option<usize>) {
+        size_hint::recursion_guard(depth, |depth| {
+            size_hint::and(<usize as Arbitrary>::size_hint(depth), (0, None))
+        })
     }
@@ -95,4 +99,6 @@
 
-    fn size_hint() -> (usize, Option<usize>) {
-        size_hint::and(<usize as Arbitrary>::size_hint(), (0, None))
+    fn size_hint(depth: usize) -> (usize, Option<usize>) {
+        size_hint::recursion_guard(depth, |depth| {
+            size_hint::and(<usize as Arbitrary>::size_hint(depth), (0, None))
+        })
     }
@@ -120,4 +126,6 @@
 
-    fn size_hint() -> (usize, Option<usize>) {
-        size_hint::and(<usize as Arbitrary>::size_hint(), (0, None))
+    fn size_hint(depth: usize) -> (usize, Option<usize>) {
+        size_hint::recursion_guard(depth, |depth| {
+            size_hint::and(<usize as Arbitrary>::size_hint(depth), (0, None))
+        })
     }
@@ -145,4 +153,6 @@
 
-    fn size_hint() -> (usize, Option<usize>) {
-        size_hint::and(<usize as Arbitrary>::size_hint(), (0, None))
+    fn size_hint(depth: usize) -> (usize, Option<usize>) {
+        size_hint::recursion_guard(depth, |depth| {
+            size_hint::and(<usize as Arbitrary>::size_hint(depth), (0, None))
+        })
     }
@@ -149,0 +159,0 @@

src/hash/set.rs

@@ -491,2 +491,13 @@ // This Source Code Form is subject to the terms of the Mozilla Public
     /// Time: O(n log n)
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// # #[macro_use] extern crate im_rc as im;
+    /// # use im::HashSet;
+    /// let mut set = hashset![1, 2, 3];
+    /// set.retain(|v| *v > 1);
+    /// let expected = hashset![2, 3];
+    /// assert_eq!(expected, set);
+    /// ```
     pub fn retain<F>(&mut self, mut f: F)
@@ -845,3 +856,3 @@ where
 
-// An iterator over the elements of a set.
+/// An iterator over the elements of a set.
 pub struct Iter<'a, A> {
@@ -870,3 +881,3 @@ it: NodeIter<'a, Value<A>>,
 
-// A mutable iterator over the elements of a set.
+/// A mutable iterator over the elements of a set.
 pub struct IterMut<'a, A> {
@@ -895,3 +906,3 @@ it: NodeIterMut<'a, Value<A>>,
 
-// A consuming iterator over the elements of a set.
+/// A consuming iterator over the elements of a set.
 pub struct ConsumingIter<A>
@@ -1064,54 +1075,11 @@ where
 
-// QuickCheck
-#[cfg(all(threadsafe, feature = "quickcheck"))]
-mod quickcheck {
-    use super::*;
-    use ::quickcheck::{Arbitrary, Gen};
-
-    impl<A, S> Arbitrary for HashSet<A, S>
-    where
-        A: Hash + Eq + Arbitrary + Sync,
-        S: BuildHasher + Default + Send + Sync + 'static,
-    {
-        fn arbitrary<G: Gen>(g: &mut G) -> Self {
-            HashSet::from_iter(Vec::<A>::arbitrary(g))
-        }
-    }
-}
-
 // Proptest
 #[cfg(any(test, feature = "proptest"))]
+#[doc(hidden)]
 pub mod proptest {
-    //! Proptest strategies.
-    use super::*;
-    use ::proptest::strategy::{BoxedStrategy, Strategy, ValueTree};
-    use std::ops::Range;
-
-    /// A strategy for a hash set of a given size.
-    ///
-    /// # Examples
-    ///
-    /// ```rust,ignore
-    /// proptest! {
-    ///     #[test]
-    ///     fn proptest_a_set(ref s in hashset(".*", 10..100)) {
-    ///         assert!(s.len() < 100);
-    ///         assert!(s.len() >= 10);
-    ///     }
-    /// }
-    /// ```
-    pub fn hash_set<A: Strategy + 'static>(
-        element: A,
-        size: Range<usize>,
-    ) -> BoxedStrategy<HashSet<<A::Tree as ValueTree>::Value>>
-    where
-        <A::Tree as ValueTree>::Value: Hash + Eq + Clone,
-    {
-        ::proptest::collection::vec(element, size.clone())
-            .prop_map(HashSet::from)
-            .prop_filter("HashSet minimum size".to_owned(), move |s| {
-                s.len() >= size.start
-            })
-            .boxed()
-    }
+    #[deprecated(
+        since = "14.3.0",
+        note = "proptest strategies have moved to im::proptest"
+    )]
+    pub use crate::proptest::hash_set;
 }
@@ -1118,0 +1086,0 @@

src/lib.rs

@@ -340,3 +340,3 @@ // This Source Code Form is subject to the terms of the Mozilla Public
 #![deny(unsafe_code, nonstandard_style)]
-#![warn(unreachable_pub)]
+#![warn(unreachable_pub, missing_docs)]
 #![cfg_attr(has_specialisation, feature(specialization))]
@@ -371,2 +371,5 @@
 
+#[cfg(any(test, feature = "proptest"))]
+pub mod proptest;
+
 #[cfg(any(test, feature = "serde"))]
@@ -380,2 +383,6 @@ #[doc(hidden)]
 
+#[cfg(all(threadsafe, feature = "quickcheck"))]
+#[doc(hidden)]
+pub mod quickcheck;
+
 #[cfg(not(feature = "pool"))]
@@ -382,0 +389,0 @@ mod fakepool;

src/nodes/btree.rs

@@ -238,2 +238,94 @@ // This Source Code Form is subject to the terms of the Mozilla Public
 
+    pub(crate) fn lookup_prev<'a, BK>(&'a self, key: &BK) -> Option<&A>
+    where
+        BK: Ord + ?Sized,
+        A::Key: Borrow<BK>,
+    {
+        if self.keys.is_empty() {
+            return None;
+        }
+        match A::search_key(&self.keys, key) {
+            Ok(index) => Some(&self.keys[index]),
+            Err(index) => match self.children[index] {
+                None if index == 0 => None,
+                None => match self.keys.get(index - 1) {
+                    Some(_) => Some(&self.keys[index - 1]),
+                    None => None,
+                },
+                Some(ref node) => node.lookup_prev(key),
+            },
+        }
+    }
+
+    pub(crate) fn lookup_next<'a, BK>(&'a self, key: &BK) -> Option<&A>
+    where
+        BK: Ord + ?Sized,
+        A::Key: Borrow<BK>,
+    {
+        if self.keys.is_empty() {
+            return None;
+        }
+        match A::search_key(&self.keys, key) {
+            Ok(index) => Some(&self.keys[index]),
+            Err(index) => match self.children[index] {
+                None => match self.keys.get(index) {
+                    Some(_) => Some(&self.keys[index]),
+                    None => None,
+                },
+                Some(ref node) => node.lookup_next(key),
+            },
+        }
+    }
+
+    pub(crate) fn lookup_prev_mut<'a, BK>(
+        &'a mut self,
+        pool: &Pool<Node<A>>,
+        key: &BK,
+    ) -> Option<&mut A>
+    where
+        A: Clone,
+        BK: Ord + ?Sized,
+        A::Key: Borrow<BK>,
+    {
+        if self.keys.is_empty() {
+            return None;
+        }
+        match A::search_key(&self.keys, key) {
+            Ok(index) => Some(&mut self.keys[index]),
+            Err(index) => match self.children[index] {
+                None if index == 0 => None,
+                None => match self.keys.get(index - 1) {
+                    Some(_) => Some(&mut self.keys[index - 1]),
+                    None => None,
+                },
+                Some(ref mut node) => PoolRef::make_mut(pool, node).lookup_prev_mut(pool, key),
+            },
+        }
+    }
+
+    pub(crate) fn lookup_next_mut<'a, BK>(
+        &'a mut self,
+        pool: &Pool<Node<A>>,
+        key: &BK,
+    ) -> Option<&mut A>
+    where
+        A: Clone,
+        BK: Ord + ?Sized,
+        A::Key: Borrow<BK>,
+    {
+        if self.keys.is_empty() {
+            return None;
+        }
+        match A::search_key(&self.keys, key) {
+            Ok(index) => Some(&mut self.keys[index]),
+            Err(index) => match self.children[index] {
+                None => match self.keys.get(index) {
+                    Some(_) => Some(&mut self.keys[index]),
+                    None => None,
+                },
+                Some(ref mut node) => PoolRef::make_mut(pool, node).lookup_next_mut(pool, key),
+            },
+        }
+    }
+
     pub(crate) fn path_first<'a, BK>(
@@ -819,2 +911,3 @@ &'a self,
 
+/// An iterator over an ordered set.
 pub struct Iter<'a, A> {
@@ -1007,2 +1100,3 @@ fwd_path: Vec<(&'a Node<A>, usize)>,
 
+/// A consuming iterator over an ordered set.
 pub struct ConsumingIter<A> {
@@ -1132,2 +1226,3 @@ fwd_last: Option<A>,
 
+/// An iterator over the differences between two ordered sets.
 pub struct DiffIter<'a, A> {
@@ -1138,6 +1233,15 @@ old_stack: Vec<IterItem<'a, A>>,
 
+/// A description of a difference between two ordered sets.
 #[derive(PartialEq, Eq)]
 pub enum DiffItem<'a, A> {
+    /// This value has been added to the new set.
     Add(&'a A),
-    Update { old: &'a A, new: &'a A },
+    /// This value has been changed between the two sets.
+    Update {
+        /// The old value.
+        old: &'a A,
+        /// The new value.
+        new: &'a A,
+    },
+    /// This value has been removed from the new set.
     Remove(&'a A),
@@ -1144,0 +1248,0 @@ }

src/nodes/rrb.rs

@@ -1016,2 +1016,3 @@ // This Source Code Form is subject to the terms of the Mozilla Public
 
+    #[cfg(any(test, feature = "debug"))]
     pub(crate) fn assert_invariants(&self, level: usize) -> usize {
@@ -1018,0 +1019,0 @@ // Verifies that the size table matches reality.

src/ord/set.rs

@@ -337,3 +337,3 @@ // This Source Code Form is subject to the terms of the Mozilla Public
 
-    // Create an iterator over the contents of the set.
+    /// Create an iterator over the contents of the set.
     #[must_use]
@@ -346,3 +346,3 @@ pub fn iter(&self) -> Iter<'_, A> {
 
-    // Create an iterator over a range inside the set.
+    /// Create an iterator over a range inside the set.
     #[must_use]
@@ -401,2 +401,42 @@ pub fn range<R, BA>(&self, range: R) -> RangedIter<'_, A>
 
+    /// Get the closest smaller value in a set to a given value.
+    ///
+    /// If the set contains the given value, this is returned.
+    /// Otherwise, the closest value in the set smaller than the
+    /// given value is returned. If the smallest value in the set
+    /// is larger than the given value, `None` is returned.
+    ///
+    /// # Examples
+    ///
+    /// ```rust
+    /// # #[macro_use] extern crate im_rc as im;
+    /// # use im::OrdSet;
+    /// let set = ordset![1, 3, 5, 7, 9];
+    /// assert_eq!(Some(&5), set.get_prev(&6));
+    /// ```
+    #[must_use]
+    pub fn get_prev(&self, key: &A) -> Option<&A> {
+        self.root.lookup_prev(key).map(|v| &v.0)
+    }
+
+    /// Get the closest larger value in a set to a given value.
+    ///
+    /// If the set contains the given value, this is returned.
+    /// Otherwise, the closest value in the set larger than the
+    /// given value is returned. If the largest value in the set
+    /// is smaller than the given value, `None` is returned.
+    ///
+    /// # Examples
+    ///
+    /// ```rust
+    /// # #[macro_use] extern crate im_rc as im;
+    /// # use im::OrdSet;
+    /// let set = ordset![1, 3, 5, 7, 9];
+    /// assert_eq!(Some(&5), set.get_next(&4));
+    /// ```
+    #[must_use]
+    pub fn get_next(&self, key: &A) -> Option<&A> {
+        self.root.lookup_next(key).map(|v| &v.0)
+    }
+
     /// Test whether a set is a subset of another set, meaning that
@@ -903,3 +943,3 @@ /// all values in our set must also be in the other set.
 
-// An iterator over the elements of a set.
+/// An iterator over the elements of a set.
 pub struct Iter<'a, A> {
@@ -938,7 +978,7 @@ it: NodeIter<'a, Value<A>>,
 
-// A ranged iterator over the elements of a set.
-//
-// The only difference from `Iter` is that this one doesn't implement
-// `ExactSizeIterator` because we can't know the size of the range without first
-// iterating over it to count.
+/// A ranged iterator over the elements of a set.
+///
+/// The only difference from `Iter` is that this one doesn't implement
+/// `ExactSizeIterator` because we can't know the size of the range without first
+/// iterating over it to count.
 pub struct RangedIter<'a, A> {
@@ -975,3 +1015,3 @@ it: NodeIter<'a, Value<A>>,
 
-// A consuming iterator over the elements of a set.
+/// A consuming iterator over the elements of a set.
 pub struct ConsumingIter<A> {
@@ -995,3 +1035,3 @@ it: ConsumingNodeIter<Value<A>>,
 
-// An iterator over the difference between two sets.
+/// An iterator over the difference between two sets.
 pub struct DiffIter<'a, A> {
@@ -1133,50 +1173,11 @@ it: NodeDiffIter<'a, Value<A>>,
 
-// QuickCheck
-#[cfg(all(threadsafe, feature = "quickcheck"))]
-mod quickcheck {
-    use super::*;
-    use ::quickcheck::{Arbitrary, Gen};
-
-    impl<A: Ord + Clone + Arbitrary + Sync> Arbitrary for OrdSet<A> {
-        fn arbitrary<G: Gen>(g: &mut G) -> Self {
-            OrdSet::from_iter(Vec::<A>::arbitrary(g))
-        }
-    }
-}
-
 // Proptest
 #[cfg(any(test, feature = "proptest"))]
+#[doc(hidden)]
 pub mod proptest {
-    //! Proptest strategies.
-    use super::*;
-    use ::proptest::strategy::{BoxedStrategy, Strategy, ValueTree};
-    use std::ops::Range;
-
-    /// A strategy for a set of a given size.
-    ///
-    /// # Examples
-    ///
-    /// ```rust,ignore
-    /// proptest! {
-    ///     #[test]
-    ///     fn proptest_a_set(ref s in set(".*", 10..100)) {
-    ///         assert!(s.len() < 100);
-    ///         assert!(s.len() >= 10);
-    ///     }
-    /// }
-    /// ```
-    pub fn ord_set<A: Strategy + 'static>(
-        element: A,
-        size: Range<usize>,
-    ) -> BoxedStrategy<OrdSet<<A::Tree as ValueTree>::Value>>
-    where
-        <A::Tree as ValueTree>::Value: Ord + Clone,
-    {
-        ::proptest::collection::vec(element, size.clone())
-            .prop_map(OrdSet::from)
-            .prop_filter("OrdSet minimum size".to_owned(), move |s| {
-                s.len() >= size.start
-            })
-            .boxed()
-    }
+    #[deprecated(
+        since = "14.3.0",
+        note = "proptest strategies have moved to im::proptest"
+    )]
+    pub use crate::proptest::ord_set;
 }
@@ -1186,4 +1187,4 @@
 mod test {
-    use super::proptest::*;
     use super::*;
+    use crate::proptest::*;
     use ::proptest::proptest;
@@ -1190,0 +1191,0 @@

src/ser.rs

@@ -262,7 +262,3 @@ // This Source Code Form is subject to the terms of the Mozilla Public
     use super::*;
-    use crate::hashmap::proptest::hash_map;
-    use crate::hashset::proptest::hash_set;
-    use crate::ordmap::proptest::ord_map;
-    use crate::ordset::proptest::ord_set;
-    use crate::vector::proptest::vector;
+    use crate::proptest::{hash_map, hash_set, ord_map, ord_set, vector};
     use ::proptest::num::i32;
@@ -269,0 +265,0 @@ use ::proptest::proptest;

No alert changes

No metric changes