im-rc - cargo Package Compare versions

Comparing version 14.1.0 to 14.2.0

src/arbitrary.rs

+// This Source Code Form is subject to the terms of the Mozilla Public
+// License, v. 2.0. If a copy of the MPL was not distributed with this
+// file, You can obtain one at http://mozilla.org/MPL/2.0/.
+
+use std::hash::{BuildHasher, Hash};
+use std::iter;
+
+use ::arbitrary::{size_hint, Arbitrary, Result, Unstructured};
+
+use crate::{HashMap, HashSet, OrdMap, OrdSet, Vector};
+
+fn empty<T: 'static>() -> Box<dyn Iterator<Item = T>> {
+    Box::new(iter::empty())
+}
+
+fn shrink_collection<T: Clone, A: Clone + Arbitrary>(
+    entries: impl Iterator<Item = T>,
+    f: impl Fn(&T) -> Box<dyn Iterator<Item = A>>,
+) -> Box<dyn Iterator<Item = Vec<A>>> {
+    let entries: Vec<_> = entries.collect();
+    if entries.is_empty() {
+        return empty();
+    }
+
+    let mut shrinkers: Vec<Vec<_>> = vec![];
+    let mut i = entries.len();
+    loop {
+        shrinkers.push(entries.iter().take(i).map(&f).collect());
+        i /= 2;
+        if i == 0 {
+            break;
+        }
+    }
+    Box::new(iter::once(Vec::new()).chain(iter::from_fn(move || loop {
+        let mut shrinker = shrinkers.pop()?;
+        let x: Option<Vec<A>> = shrinker.iter_mut().map(|s| s.next()).collect();
+        if x.is_none() {
+            continue;
+        }
+        shrinkers.push(shrinker);
+        return x;
+    })))
+}
+
+impl<A: Arbitrary + Clone> Arbitrary for Vector<A> {
+    fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+        u.arbitrary_iter()?.collect()
+    }
+
+    fn arbitrary_take_rest(u: Unstructured<'_>) -> Result<Self> {
+        u.arbitrary_take_rest_iter()?.collect()
+    }
+
+    fn size_hint() -> (usize, Option<usize>) {
+        size_hint::and(<usize as Arbitrary>::size_hint(), (0, None))
+    }
+
+    fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
+        let collections = shrink_collection(self.iter(), |x| x.shrink());
+        Box::new(collections.map(|entries| entries.into_iter().collect()))
+    }
+}
+
+impl<K: Arbitrary + Ord + Clone, V: Arbitrary + Clone> Arbitrary for OrdMap<K, V> {
+    fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+        u.arbitrary_iter()?.collect()
+    }
+
+    fn arbitrary_take_rest(u: Unstructured<'_>) -> Result<Self> {
+        u.arbitrary_take_rest_iter()?.collect()
+    }
+
+    fn size_hint() -> (usize, Option<usize>) {
+        size_hint::and(<usize as Arbitrary>::size_hint(), (0, None))
+    }
+
+    fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
+        let collections =
+            shrink_collection(self.iter(), |(k, v)| Box::new(k.shrink().zip(v.shrink())));
+        Box::new(collections.map(|entries| entries.into_iter().collect()))
+    }
+}
+
+impl<A: Arbitrary + Ord + Clone> Arbitrary for OrdSet<A> {
+    fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+        u.arbitrary_iter()?.collect()
+    }
+
+    fn arbitrary_take_rest(u: Unstructured<'_>) -> Result<Self> {
+        u.arbitrary_take_rest_iter()?.collect()
+    }
+
+    fn size_hint() -> (usize, Option<usize>) {
+        size_hint::and(<usize as Arbitrary>::size_hint(), (0, None))
+    }
+
+    fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
+        let collections = shrink_collection(self.iter(), |v| v.shrink());
+        Box::new(collections.map(|entries| entries.into_iter().collect()))
+    }
+}
+
+impl<K, V, S> Arbitrary for HashMap<K, V, S>
+where
+    K: Arbitrary + Hash + Eq + Clone,
+    V: Arbitrary + Clone,
+    S: BuildHasher + Default + 'static,
+{
+    fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+        u.arbitrary_iter()?.collect()
+    }
+
+    fn arbitrary_take_rest(u: Unstructured<'_>) -> Result<Self> {
+        u.arbitrary_take_rest_iter()?.collect()
+    }
+
+    fn size_hint() -> (usize, Option<usize>) {
+        size_hint::and(<usize as Arbitrary>::size_hint(), (0, None))
+    }
+
+    fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
+        let collections =
+            shrink_collection(self.iter(), |(k, v)| Box::new(k.shrink().zip(v.shrink())));
+        Box::new(collections.map(|entries| entries.into_iter().collect()))
+    }
+}
+
+impl<A, S> Arbitrary for HashSet<A, S>
+where
+    A: Arbitrary + Hash + Eq + Clone,
+    S: BuildHasher + Default + 'static,
+{
+    fn arbitrary(u: &mut Unstructured<'_>) -> Result<Self> {
+        u.arbitrary_iter()?.collect()
+    }
+
+    fn arbitrary_take_rest(u: Unstructured<'_>) -> Result<Self> {
+        u.arbitrary_take_rest_iter()?.collect()
+    }
+
+    fn size_hint() -> (usize, Option<usize>) {
+        size_hint::and(<usize as Arbitrary>::size_hint(), (0, None))
+    }
+
+    fn shrink(&self) -> Box<dyn Iterator<Item = Self>> {
+        let collections = shrink_collection(self.iter(), |v| v.shrink());
+        Box::new(collections.map(|entries| entries.into_iter().collect()))
+    }
+}

Cargo.toml

@@ -16,3 +16,3 @@ # THIS FILE IS AUTOMATICALLY GENERATED BY CARGO
 name = "im-rc"
-version = "14.1.0"
+version = "14.2.0"
 authors = ["Bodil Stokke <[e-mail]>"]
@@ -33,2 +33,6 @@ build = "./build.rs"
 path = "./src/lib.rs"
+[dependencies.arbitrary]
+version = "0.3"
+optional = true
+
 [dependencies.bitmaps]
@@ -35,0 +39,0 @@ version = "2.0.0"

CHANGELOG.md

@@ -5,6 +5,24 @@ # Changelog
 
-The format is based on [Keep a Changelog](http://keepachangelog.com/en/1.0.0/)
-and this project adheres to [Semantic
-Versioning](http://semver.org/spec/v2.0.0.html).
+The format is based on [Keep a Changelog](http://keepachangelog.com/en/1.0.0/) and this project
+adheres to [Semantic Versioning](http://semver.org/spec/v2.0.0.html).
 
+## [14.2.0] - 2020-01-17
+
+### Added
+
+-   Both map types now have the `get_key_value()` method, corresponding to the equivalent
+    [additions](https://doc.rust-lang.org/std/collections/struct.BTreeMap.html#method.get_key_value)
+    to the standard library.
+-   The `ptr_eq` method has been added to all data types, allowing you to test whether two values
+    refer to the same content in memory, by testing for pointer equality. (#117)
+-   `HashMap` had lost its `Arbitrary` implementation for the `quickcheck` feature flag. It's now
+    been restored. (#118)
+-   Implementations for `Arbitrary` from the [`arbitrary`](https://crates.io/crates/arbitrary/)
+    crate have been added behind the `arbitrary` feature flag.
+
+### Fixed
+
+-   Fixed a bug when reversing a consuming iterator over a `Vector` by replacing the consuming
+    iterator with a much simpler and slightly more efficient version. (#116)
+
 ## [14.1.0] - 2019-12-16
@@ -14,11 +32,9 @@
 
-- If you enable the `pool` feature flag, im now supports constructing data types
-  using [`refpool`](https://crates.io/crates/refpool) to speed up chunk
-  allocation. The performance boost will vary between use cases and operating
-  systems, but generally at least a 10% speedup can be expected when
-  constructing a data type from an iterator, and the more complex an operation
-  is, the more likely it is to benefit from being able to quickly reallocate
-  chunks. Note that in order to use this feature, you have to construct your
-  data types using the `with_pool(&pool)` constructor, it's not enough just to
-  enable the feature flag.
+-   If you enable the `pool` feature flag, im now supports constructing data types using
+    [`refpool`](https://crates.io/crates/refpool) to speed up chunk allocation. The performance
+    boost will vary between use cases and operating systems, but generally at least a 10% speedup
+    can be expected when constructing a data type from an iterator, and the more complex an
+    operation is, the more likely it is to benefit from being able to quickly reallocate chunks.
+    Note that in order to use this feature, you have to construct your data types using the
+    `with_pool(&pool)` constructor, it's not enough just to enable the feature flag.
 
@@ -29,11 +45,10 @@ ## [14.0.0] - 2019-11-19
 
-- As `sized-chunks` now requires a slightly more recent version of `rustc` to
-  compile, specifically version 1.36.0, so does `im`. This is a breaking change,
-  but will of course only affect your code if you're using an older `rustc`.
+-   As `sized-chunks` now requires a slightly more recent version of `rustc` to compile,
+    specifically version 1.36.0, so does `im`. This is a breaking change, but will of course only
+    affect your code if you're using an older `rustc`.
 
 ### Fixed
 
-- Fixed a quadratic time worst case scenario in the quicksort implementation for
-  `Vector`. (#101)
-- Fixed an edge case bug when splitting and joining large `Vector`s. (#105, #107)
+-   Fixed a quadratic time worst case scenario in the quicksort implementation for `Vector`. (#101)
+-   Fixed an edge case bug when splitting and joining large `Vector`s. (#105, #107)
 
@@ -46,30 +61,26 @@ ## [13.0.0] - 2019-05-18
 
-- `im::iter::unfold` now gives you the owned state value rather than an
-  immutable reference to it, which makes it a little more useful.
+-   `im::iter::unfold` now gives you the owned state value rather than an immutable reference to it,
+    which makes it a little more useful.
 
 ### Removed
 
-- The deprecated `singleton` constructors have been removed. Please use `unit`
-  instead.
-- The deprecated methods `Vector::chunks` and `Vector::chunks_mut` have been
-  removed in favour of `Vector::leaves` and `Vector::leaves_mut` respectively.
-  (#50)
-- The deprecated reference to [`sized-chunks`](https://crates.io/crates/sized-chunks)
-  has been removed. If you need it, please use the `sized-chunks` crate directly.
-- `im::iter::unfold_mut` has been removed, as there's no meaningful difference
-  between it and rust-std 1.34.0's `std::iter::from_fn` with a captured state
-  variable.
+-   The deprecated `singleton` constructors have been removed. Please use `unit` instead.
+-   The deprecated methods `Vector::chunks` and `Vector::chunks_mut` have been removed in favour of
+    `Vector::leaves` and `Vector::leaves_mut` respectively. (#50)
+-   The deprecated reference to [`sized-chunks`](https://crates.io/crates/sized-chunks) has been
+    removed. If you need it, please use the `sized-chunks` crate directly.
+-   `im::iter::unfold_mut` has been removed, as there's no meaningful difference between it and
+    rust-std 1.34.0's `std::iter::from_fn` with a captured state variable.
 
 ### Fixed
 
-- `Vector` now uses
-  [`sized_chunks::InlineArray`](https://docs.rs/sized-chunks/0.3.0/sized_chunks/inline_array/struct.InlineArray.html)
-  instead of an `Empty` enum case to avoid allocation at very small sizes,
-  letting you store a handful of elements on the stack before needing to grow
-  into a full chunk. This has a beneficial effect on performance as well, as
-  there's no pointer into the heap to dereference, making it faster than
-  `std::vec::Vec` in this configuration.
-- Some complexity timings have been added and corrected. (#87)
-- `OrdSet::is_subset(&self, other)` now returns immediately when `self` is
-  larger than `other` and thus could not possibly be a subset of it. (#87)
+-   `Vector` now uses
+    [`sized_chunks::InlineArray`](https://docs.rs/sized-chunks/0.3.0/sized_chunks/inline_array/struct.InlineArray.html)
+    instead of an `Empty` enum case to avoid allocation at very small sizes, letting you store a
+    handful of elements on the stack before needing to grow into a full chunk. This has a beneficial
+    effect on performance as well, as there's no pointer into the heap to dereference, making it
+    faster than `std::vec::Vec` in this configuration.
+-   Some complexity timings have been added and corrected. (#87)
+-   `OrdSet::is_subset(&self, other)` now returns immediately when `self` is larger than `other` and
+    thus could not possibly be a subset of it. (#87)
 
@@ -80,11 +91,10 @@ ## [12.3.4] - 2019-04-08
 
-- `Clone` constraints have been further relaxed on maps and sets, so that you
-  can now lookup and iterate over them without requiring a `Clone` constraint
-  (though you do still need `Clone` to actually insert data into them to lookup
-  or iterate over). (#81)
+-   `Clone` constraints have been further relaxed on maps and sets, so that you can now lookup and
+    iterate over them without requiring a `Clone` constraint (though you do still need `Clone` to
+    actually insert data into them to lookup or iterate over). (#81)
 
 ### Fixed
 
-- Enforces the latest bugfix release of sized-chunks. (#78)
-- Another edge case bugfix to `Vector`'s size table handling. (#79)
+-   Enforces the latest bugfix release of sized-chunks. (#78)
+-   Another edge case bugfix to `Vector`'s size table handling. (#79)
 
@@ -95,7 +105,6 @@ ## [12.3.3] - 2019-03-11
 
-- A number of issues were fixed where `Vector`'s size table would get out of
-  sync with the node structure if exercised too much and cause erroneous
-  behaviour. (#72, #74)
-- Comprehensive generative tests were added to test all data structures through
-  more unexpected code paths.
+-   A number of issues were fixed where `Vector`'s size table would get out of sync with the node
+    structure if exercised too much and cause erroneous behaviour. (#72, #74)
+-   Comprehensive generative tests were added to test all data structures through more unexpected
+    code paths.
 
@@ -106,14 +115,11 @@ ## [12.3.2] - 2019-03-05
 
-- `Clone` constraints on all data structures, as well as relevant constraints on
-  maps and sets, have been relaxed where possible, so that you can now construct
-  empty instances and call most query methods without requiring values implement
-  `Clone` etc. (#63)
+-   `Clone` constraints on all data structures, as well as relevant constraints on maps and sets,
+    have been relaxed where possible, so that you can now construct empty instances and call most
+    query methods without requiring values implement `Clone` etc. (#63)
 
 ### Fixed
 
-- Constructing an empty `Vector` will not allocate any heap memory, instead
-  deferring allocation until you perform an operation that would increase its
-  length. (#65)
-- Some bugs arising when using `Vector::append` repeatedly were fixed. (#67,
-  #70)
+-   Constructing an empty `Vector` will not allocate any heap memory, instead deferring allocation
+    until you perform an operation that would increase its length. (#65)
+-   Some bugs arising when using `Vector::append` repeatedly were fixed. (#67, #70)
 
@@ -124,4 +130,4 @@ ## [12.3.1] - 2019-02-19
 
-- Unsafe chunks have been separated out into the `sized-chunks` crate, which is
-  now a dependency of `im`.
+-   Unsafe chunks have been separated out into the `sized-chunks` crate, which is now a dependency
+    of `im`.
 
@@ -132,12 +138,12 @@ ## [12.3.0] - 2019-01-15
 
-- `singleton` methods have been deprecated and renamed to `unit`.
-- `Vector::chunks` and `Vector::chunks_mut` have been deprecated and renamed to
-  `leaves` and `leaves_mut` to avoid confusion with `Vec::chunks`. (#50)
+-   `singleton` methods have been deprecated and renamed to `unit`.
+-   `Vector::chunks` and `Vector::chunks_mut` have been deprecated and renamed to `leaves` and
+    `leaves_mut` to avoid confusion with `Vec::chunks`. (#50)
 
 ### Fixed
 
-- Fixed an issue where the `HashMap` draining iterator might access uninitialised memory leading to
-  undefined behaviour. (#60)
-- Fixed multiple issues in `Vector::split_off` and `Vector::append` that would cause lookup errors
-  and unexpectedly unbalanced trees. (#55).
+-   Fixed an issue where the `HashMap` draining iterator might access uninitialised memory leading
+    to undefined behaviour. (#60)
+-   Fixed multiple issues in `Vector::split_off` and `Vector::append` that would cause lookup errors
+    and unexpectedly unbalanced trees. (#55).
 
@@ -147,77 +153,76 @@ ## [12.2.0] - 2018-10-12
 ### Added
-- `OrdMap` and `OrdSet` now have a `range()` method which makes an iterator over
-  a bounded subset of the values. The improved iterator implementation is also
-  considerably more efficient than the previous (about an order of magnitude
-  faster for nontrivial data sets). `iter()` has been updated to take advantage
-  of this, and is now just an alias for `range(..)`. (#27)
-- `FocusMut` now has an `unmut` method to turn it into an immutable `Focus`,
-  releasing its exclusive hold on the underlying `Vector`.
-- `Focus` now implements `Clone`.
 
+-   `OrdMap` and `OrdSet` now have a `range()` method which makes an iterator over a bounded subset
+    of the values. The improved iterator implementation is also considerably more efficient than the
+    previous (about an order of magnitude faster for nontrivial data sets). `iter()` has been
+    updated to take advantage of this, and is now just an alias for `range(..)`. (#27)
+-   `FocusMut` now has an `unmut` method to turn it into an immutable `Focus`, releasing its
+    exclusive hold on the underlying `Vector`.
+-   `Focus` now implements `Clone`.
+
 ## [12.1.0] - 2018-09-25
 
 ### Added
-- Maps and sets now have the `clear` method just like `Vector`. (#46)
 
+-   Maps and sets now have the `clear` method just like `Vector`. (#46)
+
 ### Changed
-- Single chunk `Vector`s are no longer allocated directly on the stack, meaning
-  that they're now comparable in performance to `std::vec::Vec` rather than
-  slightly faster, but they also won't eat up your stack space quite as quickly,
-  and they'll clone without copying and share structure with clones as you'd
-  expect.
 
+-   Single chunk `Vector`s are no longer allocated directly on the stack, meaning that they're now
+    comparable in performance to `std::vec::Vec` rather than slightly faster, but they also won't
+    eat up your stack space quite as quickly, and they'll clone without copying and share structure
+    with clones as you'd expect.
+
 ## [12.0.0] - 2018-08-30
 
-Starting with this release, the `arc` flag is gone, in favour of publishing `im`
-as two separate crates: `im` (using `Arc`) and `im-rc` (using `Rc`). They're
-identical (and built from the same code), except that `im` is thread safe and
-`im-rc` is a little bit more performant.
+Starting with this release, the `arc` flag is gone, in favour of publishing `im` as two separate
+crates: `im` (using `Arc`) and `im-rc` (using `Rc`). They're identical (and built from the same
+code), except that `im` is thread safe and `im-rc` is a little bit more performant.
 
-This is a major release as a consequence, but there should be no breaking code
-changes other than the new default choice of reference counter.
+This is a major release as a consequence, but there should be no breaking code changes other than
+the new default choice of reference counter.
 
 ### Added
-- The `Chunk` datatype that's used to build `Vector` and `OrdMap` has been
-  exposed and made generally usable. It's somewhere between a
-  [`GenericArray`](https://crates.io/crates/generic-array) and a ring buffer,
-  offers O(1)* push in either direction, and is generally hyperoptimised for its
-  purpose of serving as nodes for Bagwell tries, but it's also a powered up
-  version of [`GenericArray`](https://crates.io/crates/generic-array) that might
-  be useful to others, hence the public API.
-- `Vector` now has `Focus` and `FocusMut` APIs for caching index lookups,
-  yielding huge performance gains when performing multiple adjacent index
-  lookups.  `Vector::iter` has been reimplemented using this API, and is now
-  much simpler and about twice as fast as a result, and `Vector::iter_mut` now
-  runs nearly an order of magnitude faster. Likewise, `Vector::sort` and
-  `Vector::retain` are now using `FocusMut` and run considerably faster as a
-  result.
-- `Focus` and `FocusMut` can also be used as stand ins for subslices through the
-  `narrow` and `split_at` methods. You can also iterate over foci, making this
-  the most efficient way to iterate over a subset of a `Vector`.
-- `Vector` now implements [Rayon](https://crates.io/crates/rayon)'s parallel
-  iterators behind the `rayon` feature flag.
 
+-   The `Chunk` datatype that's used to build `Vector` and `OrdMap` has been exposed and made
+    generally usable. It's somewhere between a
+    [`GenericArray`](https://crates.io/crates/generic-array) and a ring buffer, offers O(1)\* push
+    in either direction, and is generally hyperoptimised for its purpose of serving as nodes for
+    Bagwell tries, but it's also a powered up version of
+    [`GenericArray`](https://crates.io/crates/generic-array) that might be useful to others, hence
+    the public API.
+-   `Vector` now has `Focus` and `FocusMut` APIs for caching index lookups, yielding huge
+    performance gains when performing multiple adjacent index lookups. `Vector::iter` has been
+    reimplemented using this API, and is now much simpler and about twice as fast as a result, and
+    `Vector::iter_mut` now runs nearly an order of magnitude faster. Likewise, `Vector::sort` and
+    `Vector::retain` are now using `FocusMut` and run considerably faster as a result.
+-   `Focus` and `FocusMut` can also be used as stand ins for subslices through the `narrow` and
+    `split_at` methods. You can also iterate over foci, making this the most efficient way to
+    iterate over a subset of a `Vector`.
+-   `Vector` now implements [Rayon](https://crates.io/crates/rayon)'s parallel iterators behind the
+    `rayon` feature flag.
+
 ### Changed
-- As `std::ops::RangeBounds` is now stabilised in Rust 1.28, the `Vector::slice`
-  method is now unconditionally available on the stable channel.
-- Union/difference/intersection/is_submap methods on `HashMap` and `OrdMap` that
-  take functions now take `FnMut` instead of `Fn`. This should not affect any
-  existing code. (#34)
-- `Vector::split_off` can now take an index equal to the length of the vector,
-  yielding an empty vector as the split result. (#33)
-- `Vector::set` now returns the replaced value.
 
+-   As `std::ops::RangeBounds` is now stabilised in Rust 1.28, the `Vector::slice` method is now
+    unconditionally available on the stable channel.
+-   Union/difference/intersection/is_submap methods on `HashMap` and `OrdMap` that take functions
+    now take `FnMut` instead of `Fn`. This should not affect any existing code. (#34)
+-   `Vector::split_off` can now take an index equal to the length of the vector, yielding an empty
+    vector as the split result. (#33)
+-   `Vector::set` now returns the replaced value.
+
 ### Fixed
-- `Vector` is now represented as a single inline chunk until it grows larger
-  than the chunk size, making it even faster than `Vec` at small sizes, though
-  `clone` could now be slower if the clone is expensive (it's still absurdly
-  fast for `A: Copy`).
 
+-   `Vector` is now represented as a single inline chunk until it grows larger than the chunk size,
+    making it even faster than `Vec` at small sizes, though `clone` could now be slower if the clone
+    is expensive (it's still absurdly fast for `A: Copy`).
+
 ## [11.0.1] - 2018-07-23
 
 ### Fixed
-- Various performance improvements, amounting to a 5-10% speedup for both kinds
-  of map/set.
-- Fixed an edge case bug in `sort::quicksort`.
 
+-   Various performance improvements, amounting to a 5-10% speedup for both kinds of map/set.
+-   Fixed an edge case bug in `sort::quicksort`.
+
 ## [11.0.0] - 2018-07-10
@@ -227,39 +232,33 @@
 
-This is a major release with many breaking changes, and is intended to stabilise
-the API more than to denote that the rewrite is now production ready. You should
-expect future releases with significant performance improvements as well as
-additional APIs, but there should be no further major release with breaking
-changes in the immediate future, barring very serious unforeseen issues.
+This is a major release with many breaking changes, and is intended to stabilise the API more than
+to denote that the rewrite is now production ready. You should expect future releases with
+significant performance improvements as well as additional APIs, but there should be no further
+major release with breaking changes in the immediate future, barring very serious unforeseen issues.
 
-Specifically, you should expect imminent minor releases with performance
-improvements for `Vector` and `OrdMap`, for which I have a number of known
-optimisations that remain unimplemented.
+Specifically, you should expect imminent minor releases with performance improvements for `Vector`
+and `OrdMap`, for which I have a number of known optimisations that remain unimplemented.
 
 #### No More `Arc`
 
-All data structures have been reworked to take values of `A: Clone` instead of
-`Arc<A>`, meaning that there's less performance overhead (as well as mental
-overhead) when using values that clone cheaply. The performance gain when values
-are `A: Copy` is a factor of two or more. It's expected that users should wrap
-values in `Arc` themselves when using values which are expensive to clone.
+All data structures have been reworked to take values of `A: Clone` instead of `Arc<A>`, meaning
+that there's less performance overhead (as well as mental overhead) when using values that clone
+cheaply. The performance gain when values are `A: Copy` is a factor of two or more. It's expected
+that users should wrap values in `Arc` themselves when using values which are expensive to clone.
 
-Data structures still use reference counters internally to reference nodes, but
-values are stored directly in the nodes with no further indirection. This is
-also good for cache locality.
+Data structures still use reference counters internally to reference nodes, but values are stored
+directly in the nodes with no further indirection. This is also good for cache locality.
 
-Data structures now use `Rc` instead of `Arc` by default to do reference
-counting. If you need a thread safe version that implements `Send` and `Sync`,
-you can enable the `arc` feature on the package to compile with `Arc` instead.
+Data structures now use `Rc` instead of `Arc` by default to do reference counting. If you need a
+thread safe version that implements `Send` and `Sync`, you can enable the `arc` feature on the
+package to compile with `Arc` instead.
 
 #### `std::collections` Compatible API
 
-The API has been reworked to align more closely with `std::collections`,
-favouring mutable operations by default, so that operations that were previously
-suffixed with `_mut` are now the standard operations, and immutable operations
-which return a modified copy have been given different names altogether. In
-short, all your code using previous versions of this library will no longer
-work, and if it was relying heavily on immutable operations, it's recommended
-that you rewrite it to be mutable by preference, but you should generally be
-able to make it work again by using the new method names for the immutable
-operations.
+The API has been reworked to align more closely with `std::collections`, favouring mutable
+operations by default, so that operations that were previously suffixed with `_mut` are now the
+standard operations, and immutable operations which return a modified copy have been given different
+names altogether. In short, all your code using previous versions of this library will no longer
+work, and if it was relying heavily on immutable operations, it's recommended that you rewrite it to
+be mutable by preference, but you should generally be able to make it work again by using the new
+method names for the immutable operations.
 
@@ -274,26 +273,23 @@ Here is a list of the most notable changed method names for maps and sets:
 
-You should expect to be able to rewrite code using `std::collections::HashMap`
-and `std::collections::BTreeMap` with minimal or no changes using `im::HashMap`
-and `im::OrdMap` respectively.
+You should expect to be able to rewrite code using `std::collections::HashMap` and
+`std::collections::BTreeMap` with minimal or no changes using `im::HashMap` and `im::OrdMap`
+respectively.
 
 `Vector` has been completely rewritten and has an API that aligns closely with
-`std::collections::VecDeque`, with very few immutable equivalents. It's expected
-that you should use `Vector::clone()` to take a snapshot when you need it rather
-than cause an implicit clone for each operation. (It's still O(1) and
-practically instant.)
+`std::collections::VecDeque`, with very few immutable equivalents. It's expected that you should use
+`Vector::clone()` to take a snapshot when you need it rather than cause an implicit clone for each
+operation. (It's still O(1) and practically instant.)
 
-I'm considering adding back some of the immutable operations if I can come up
-with good names for them, but for now, just `clone` it if you need it.
+I'm considering adding back some of the immutable operations if I can come up with good names for
+them, but for now, just `clone` it if you need it.
 
 #### RRB Vector
 
-`Vector` is now implemented as an [RRB
-tree](https://infoscience.epfl.ch/record/213452/files/rrbvector.pdf) with [smart
-head/tail chunking](http://gallium.inria.fr/~rainey/chunked_seq.pdf), obsoleting
-the previous [Hickey
-trie](https://hypirion.com/musings/understanding-persistent-vector-pt-1)
-implementation.
+`Vector` is now implemented as an
+[RRB tree](https://infoscience.epfl.ch/record/213452/files/rrbvector.pdf) with
+[smart head/tail chunking](http://gallium.inria.fr/~rainey/chunked_seq.pdf), obsoleting the previous
+[Hickey trie](https://hypirion.com/musings/understanding-persistent-vector-pt-1) implementation.
 
-RRB trees have generally similar performance characteristics to the Hickey trie,
-with the added benefit of having O(log n) splitting and concatenation.
+RRB trees have generally similar performance characteristics to the Hickey trie, with the added
+benefit of having O(log n) splitting and concatenation.
 
@@ -310,29 +306,25 @@ | Operation       | RRB tree | Hickey trie | Vec    | VecDeque |
 
-(Please note that the timings above are for the `im` version of the Hickey trie,
-based on the [Immutable.js](https://facebook.github.io/immutable-js/)
-implementation, which performs better than the original Clojure version on
-splits and push/pop front, but worse on push/pop back).
+(Please note that the timings above are for the `im` version of the Hickey trie, based on the
+[Immutable.js](https://facebook.github.io/immutable-js/) implementation, which performs better than
+the original Clojure version on splits and push/pop front, but worse on push/pop back).
 
-The RRB tree is the most generally efficient list like data structure currently
-known, to my knowledge, but obviously it does not and cannot perform as well as
-a simple `Vec` on certain operations. It makes up for that by having no
-operations you need to worry about the performance complexity of: nothing you
-can do to an RRB tree is going to be more expensive than just iterating over it.
-For larger data sets, being able to concatenate (and, by extension, insert and
-remove at arbitrary locations) several orders of magnitude faster than `Vec`
-could also be considered a selling point.
+The RRB tree is the most generally efficient list like data structure currently known, to my
+knowledge, but obviously it does not and cannot perform as well as a simple `Vec` on certain
+operations. It makes up for that by having no operations you need to worry about the performance
+complexity of: nothing you can do to an RRB tree is going to be more expensive than just iterating
+over it. For larger data sets, being able to concatenate (and, by extension, insert and remove at
+arbitrary locations) several orders of magnitude faster than `Vec` could also be considered a
+selling point.
 
 #### No More `CatList` And `ConsList`
 
-`CatList` has been superseded by `Vector`, and `ConsList` was generally not very
-useful except in the more peculiar edge cases where memory consumption matters
-more than performance, and keeping it in line with current API changes wasn't
-practical.
+`CatList` has been superseded by `Vector`, and `ConsList` was generally not very useful except in
+the more peculiar edge cases where memory consumption matters more than performance, and keeping it
+in line with current API changes wasn't practical.
 
 #### No More Funny Words
 
-Though it breaks my heart, words like `cons`, `snoc`, `car`, `cdr` and `uncons`
-are no longer used in the `im` API, to facilitiate closer alignment with
-`std::collections`. Even the `head`/`tail` pair is gone, though `head` and
-`last` remain as aliases for `front` and `back`.
+Though it breaks my heart, words like `cons`, `snoc`, `car`, `cdr` and `uncons` are no longer used
+in the `im` API, to facilitiate closer alignment with `std::collections`. Even the `head`/`tail`
+pair is gone, though `head` and `last` remain as aliases for `front` and `back`.
 
@@ -343,9 +335,8 @@ ## [10.2.0] - 2018-04-15
 
--   Map/set methods which accept references to keys will now also take any value
-    that's borrowable to the key's type, ie. it will take a reference to a type
-    `Borrowable` where the key implements `Borrow<Borrowable>`. This is
-    particularly handy for types such as `String` because you can now pass `&str`
-    to key lookups instead of `&String`. So, instead of the incredibly cumbersome
-    `map.get(&"foo".to_string())` you can just do `map.get("foo")` when looking up
-    a mapping for a string literal.
+-   Map/set methods which accept references to keys will now also take any value that's borrowable
+    to the key's type, ie. it will take a reference to a type `Borrowable` where the key implements
+    `Borrow<Borrowable>`. This is particularly handy for types such as `String` because you can now
+    pass `&str` to key lookups instead of `&String`. So, instead of the incredibly cumbersome
+    `map.get(&"foo".to_string())` you can just do `map.get("foo")` when looking up a mapping for a
+    string literal.
 
@@ -356,4 +347,4 @@ ## [10.1.0] - 2018-04-12
 
--   `Vector`, `OrdMap` and `HashMap` now implement `Index` and `IndexMut`,
-    allowing for syntax like `map[key] = value`.
+-   `Vector`, `OrdMap` and `HashMap` now implement `Index` and `IndexMut`, allowing for syntax like
+    `map[key] = value`.
 -   Added `cons`, `snoc`, `uncons` and `unsnoc` aliases where they were missing.
@@ -364,18 +355,16 @@ -   Everything now implements `Sum` and `Extend` where possible.
 
--   Generalised `OrdMap`/`OrdSet`'s internal nodes so `OrdSet` now only needs to
-    store pointers to its values, not pairs of pointers to value and `Unit`. This
-    has caused `OrdMap/Set`'s type constraints to tighten somewhat - in
-    particular, iteration over maps/sets whose keys don't implement `Ord` is no
-    longer possible, but as you would only have been able to create empty
+-   Generalised `OrdMap`/`OrdSet`'s internal nodes so `OrdSet` now only needs to store pointers to
+    its values, not pairs of pointers to value and `Unit`. This has caused `OrdMap/Set`'s type
+    constraints to tighten somewhat - in particular, iteration over maps/sets whose keys don't
+    implement `Ord` is no longer possible, but as you would only have been able to create empty
     instances of these, no sensible code should break because of this.
--   `HashMap`/`HashSet` now also cannot be iterated over unless they implement
-    `Hash + Eq`, with the same note as above.
--   Constraints on single operations that take closures on `HashMap` and `OrdMap`
-    have been relaxed from `Fn` to `FnOnce`. (Fixes #7.)
+-   `HashMap`/`HashSet` now also cannot be iterated over unless they implement `Hash + Eq`, with the
+    same note as above.
+-   Constraints on single operations that take closures on `HashMap` and `OrdMap` have been relaxed
+    from `Fn` to `FnOnce`. (Fixes #7.)
 
 ### Fixed
 
--   Hashes are now stored in `HashMap`s along with their associated values,
-    removing the need to recompute the hash when a value is reordered inside the
-    tree.
+-   Hashes are now stored in `HashMap`s along with their associated values, removing the need to
+    recompute the hash when a value is reordered inside the tree.
 
@@ -386,3 +375,2 @@ ## [10.0.0] - 2018-03-25
 
-This is the first release to be considered reasonably stable. No changelog has
-been kept until now.
+This is the first release to be considered reasonably stable. No changelog has been kept until now.

src/config.rs

@@ -8,10 +8,10 @@ // This Source Code Form is subject to the terms of the Mozilla Public
 /// The branching factor of RRB-trees
-pub type VectorChunkSize = U64;
+pub(crate) type VectorChunkSize = U64;
 
 /// The branching factor of B-trees
-pub type OrdChunkSize = U64; // Must be an even number!
+pub(crate) type OrdChunkSize = U64; // Must be an even number!
 
 /// The level size of HAMTs, in bits
 /// Branching factor is 2 ^ HashLevelSize.
-pub type HashLevelSize = U5;
+pub(crate) type HashLevelSize = U5;
 
@@ -21,2 +21,2 @@ /// The size of per-instance memory pools if the `pool` feature is enabled.
 /// with eg. `Vector::with_pool(pool)` even if the `pool` feature is enabled.
-pub const POOL_SIZE: usize = 0;
+pub(crate) const POOL_SIZE: usize = 0;

src/fakepool.rs

@@ -14,4 +14,4 @@ // This Source Code Form is subject to the terms of the Mozilla Public
 
-pub trait PoolDefault: Default {}
-pub trait PoolClone: Clone {}
+pub(crate) trait PoolDefault: Default {}
+pub(crate) trait PoolClone: Clone {}
 
@@ -21,14 +21,14 @@ impl<A> PoolDefault for Chunk<A> {}
 
-pub struct Pool<A>(PhantomData<A>);
+pub(crate) struct Pool<A>(PhantomData<A>);
 
 impl<A> Pool<A> {
-    pub fn new(_size: usize) -> Self {
+    pub(crate) fn new(_size: usize) -> Self {
         Pool(PhantomData)
     }
 
-    pub fn get_pool_size(&self) -> usize {
+    pub(crate) fn get_pool_size(&self) -> usize {
         0
     }
 
-    pub fn fill(&self) {}
+    pub(crate) fn fill(&self) {}
 }
@@ -45,7 +45,7 @@
 #[derive(Default)]
-pub struct Rc<A>(RRc<A>);
+pub(crate) struct Rc<A>(RRc<A>);
 
 impl<A> Rc<A> {
     #[inline(always)]
-    pub fn default(_pool: &Pool<A>) -> Self
+    pub(crate) fn default(_pool: &Pool<A>) -> Self
     where
@@ -58,3 +58,3 @@ A: PoolDefault,
     #[inline(always)]
-    pub fn new(_pool: &Pool<A>, value: A) -> Self {
+    pub(crate) fn new(_pool: &Pool<A>, value: A) -> Self {
         Rc(RRc::new(value))
@@ -64,3 +64,3 @@ }
     #[inline(always)]
-    pub fn clone_from(_pool: &Pool<A>, value: &A) -> Self
+    pub(crate) fn clone_from(_pool: &Pool<A>, value: &A) -> Self
     where
@@ -73,3 +73,3 @@ A: PoolClone,
     #[inline(always)]
-    pub fn make_mut<'a>(_pool: &Pool<A>, this: &'a mut Self) -> &'a mut A
+    pub(crate) fn make_mut<'a>(_pool: &Pool<A>, this: &'a mut Self) -> &'a mut A
     where
@@ -82,7 +82,7 @@ A: PoolClone,
     #[inline(always)]
-    pub fn ptr_eq(left: &Self, right: &Self) -> bool {
+    pub(crate) fn ptr_eq(left: &Self, right: &Self) -> bool {
         RRc::ptr_eq(&left.0, &right.0)
     }
 
-    pub fn unwrap_or_clone(this: Self) -> A
+    pub(crate) fn unwrap_or_clone(this: Self) -> A
     where
@@ -127,3 +127,3 @@ A: PoolClone,
     #[inline(always)]
-    fn fmt(&self, f: &mut std::fmt::Formatter) -> Result<(), std::fmt::Error> {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
         self.0.fmt(f)
@@ -136,7 +136,7 @@ }
 #[derive(Default)]
-pub struct Arc<A>(RArc<A>);
+pub(crate) struct Arc<A>(RArc<A>);
 
 impl<A> Arc<A> {
     #[inline(always)]
-    pub fn default(_pool: &Pool<A>) -> Self
+    pub(crate) fn default(_pool: &Pool<A>) -> Self
     where
@@ -149,3 +149,3 @@ A: PoolDefault,
     #[inline(always)]
-    pub fn new(_pool: &Pool<A>, value: A) -> Self {
+    pub(crate) fn new(_pool: &Pool<A>, value: A) -> Self {
         Self(RArc::new(value))
@@ -155,3 +155,3 @@ }
     #[inline(always)]
-    pub fn clone_from(_pool: &Pool<A>, value: &A) -> Self
+    pub(crate) fn clone_from(_pool: &Pool<A>, value: &A) -> Self
     where
@@ -164,3 +164,3 @@ A: PoolClone,
     #[inline(always)]
-    pub fn make_mut<'a>(_pool: &Pool<A>, this: &'a mut Self) -> &'a mut A
+    pub(crate) fn make_mut<'a>(_pool: &Pool<A>, this: &'a mut Self) -> &'a mut A
     where
@@ -173,7 +173,7 @@ A: PoolClone,
     #[inline(always)]
-    pub fn ptr_eq(left: &Self, right: &Self) -> bool {
+    pub(crate) fn ptr_eq(left: &Self, right: &Self) -> bool {
         RArc::ptr_eq(&left.0, &right.0)
     }
 
-    pub fn unwrap_or_clone(this: Self) -> A
+    pub(crate) fn unwrap_or_clone(this: Self) -> A
     where
@@ -218,5 +218,5 @@ A: PoolClone,
     #[inline(always)]
-    fn fmt(&self, f: &mut std::fmt::Formatter) -> Result<(), std::fmt::Error> {
+    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
         self.0.fmt(f)
     }
 }

src/hash/set.rs

@@ -211,2 +211,15 @@ // This Source Code Form is subject to the terms of the Mozilla Public
 
+    /// Test whether two sets refer to the same content in memory.
+    ///
+    /// This is true if the two sides are references to the same set,
+    /// or if the two sets refer to the same root node.
+    ///
+    /// This would return true if you're comparing a set to itself, or
+    /// if you're comparing a set to a fresh clone of itself.
+    ///
+    /// Time: O(1)
+    pub fn ptr_eq(&self, other: &Self) -> bool {
+        std::ptr::eq(self, other) || PoolRef::ptr_eq(&self.root, &other.root)
+    }
+
     /// Get a reference to the memory pool used by this set.
@@ -629,2 +642,6 @@ ///
 {
+    /// Clone a set.
+    ///
+    /// Time: O(1)
+    #[inline]
     fn clone(&self) -> Self {
@@ -800,3 +817,3 @@ HashSet {
 {
-    fn fmt(&self, f: &mut Formatter) -> Result<(), Error> {
+    fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> {
         f.debug_set().entries(self.iter()).finish()
@@ -812,3 +829,3 @@ }
 {
-    default fn fmt(&self, f: &mut Formatter) -> Result<(), Error> {
+    default fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> {
         f.debug_set().entries(self.iter()).finish()
@@ -824,3 +841,3 @@ }
 {
-    fn fmt(&self, f: &mut Formatter) -> Result<(), Error> {
+    fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> {
         f.debug_set().entries(self.iter()).finish()
@@ -833,6 +850,3 @@ }
 // An iterator over the elements of a set.
-pub struct Iter<'a, A>
-where
-    A: 'a,
-{
+pub struct Iter<'a, A> {
     it: NodeIter<'a, Value<A>>,
@@ -861,6 +875,3 @@ }
 // A mutable iterator over the elements of a set.
-pub struct IterMut<'a, A>
-where
-    A: 'a,
-{
+pub struct IterMut<'a, A> {
     it: NodeIterMut<'a, Value<A>>,
@@ -1057,14 +1068,15 @@ }
 // QuickCheck
-
 #[cfg(all(threadsafe, feature = "quickcheck"))]
-use quickcheck::{Arbitrary, Gen};
+mod quickcheck {
+    use super::*;
+    use ::quickcheck::{Arbitrary, Gen};
 
-#[cfg(all(threadsafe, feature = "quickcheck"))]
-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<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))
+        }
     }
@@ -1074,3 +1086,2 @@ }
 // Proptest
-
 #[cfg(any(test, feature = "proptest"))]
@@ -1077,0 +1088,0 @@ pub mod proptest {

src/lib.rs

@@ -308,5 +308,6 @@ // This Source Code Form is subject to the terms of the Mozilla Public
 //! | [`proptest`](https://crates.io/crates/proptest) | Strategies for all `im` datatypes under a `proptest` namespace, eg. `im::vector::proptest::vector()` |
-//! | [`quickcheck`](https://crates.io/crates/quickcheck) | [`Arbitrary`](https://docs.rs/quickcheck/latest/quickcheck/trait.Arbitrary.html) implementations for all `im` datatypes (not available in `im-rc`) |
+//! | [`quickcheck`](https://crates.io/crates/quickcheck) | [`quickcheck::Arbitrary`](https://docs.rs/quickcheck/latest/quickcheck/trait.Arbitrary.html) implementations for all `im` datatypes (not available in `im-rc`) |
 //! | [`rayon`](https://crates.io/crates/rayon) | parallel iterator implementations for [`Vector`][vector::Vector] (not available in `im-rc`) |
 //! | [`serde`](https://crates.io/crates/serde) | [`Serialize`](https://docs.rs/serde/latest/serde/trait.Serialize.html) and [`Deserialize`](https://docs.rs/serde/latest/serde/trait.Deserialize.html) implementations for all `im` datatypes |
+//! | [`arbitrary`](https://crates.io/crates/arbitrary/) | [`arbitrary::Arbitrary`](https://docs.rs/arbitrary/latest/arbitrary/trait.Arbitrary.html) implementations for all `im` datatypes |
 //!
@@ -338,3 +339,5 @@ //! [std::collections]: https://doc.rust-lang.org/std/collections/index.html
 
-#![deny(unsafe_code)]
+#![forbid(rust_2018_idioms)]
+#![deny(unsafe_code, nonstandard_style)]
+#![warn(unreachable_pub)]
 #![cfg_attr(has_specialisation, feature(specialization))]
@@ -373,2 +376,6 @@
 
+#[cfg(feature = "arbitrary")]
+#[doc(hidden)]
+pub mod arbitrary;
+
 #[cfg(not(feature = "pool"))]
@@ -375,0 +382,0 @@ mod fakepool;

src/nodes/btree.rs

@@ -40,3 +40,3 @@ // This Source Code Form is subject to the terms of the Mozilla Public
 
-pub struct Node<A> {
+pub(crate) struct Node<A> {
     keys: Chunk<A, NodeSize>,
@@ -77,6 +77,5 @@ children: Chunk<Option<PoolRef<Node<A>>>, Add1<NodeSize>>,
 
-pub enum Insert<A> {
+pub(crate) enum Insert<A> {
     Added,
     Replaced(A),
-    Update(Node<A>),
     Split(Node<A>, A, Node<A>),
@@ -92,3 +91,3 @@ }
 
-pub enum Remove<A> {
+pub(crate) enum Remove<A> {
     NoChange,
@@ -147,8 +146,3 @@ Removed(A),
     #[inline]
-    pub fn new() -> Self {
-        Self::default()
-    }
-
-    #[inline]
-    pub fn unit(value: A) -> Self {
+    pub(crate) fn unit(value: A) -> Self {
         Node {
@@ -161,3 +155,8 @@ keys: Chunk::unit(value),
     #[inline]
-    pub fn new_from_split(pool: &Pool<Node<A>>, left: Node<A>, median: A, right: Node<A>) -> Self {
+    pub(crate) fn new_from_split(
+        pool: &Pool<Node<A>>,
+        left: Node<A>,
+        median: A,
+        right: Node<A>,
+    ) -> Self {
         Node {
@@ -172,3 +171,3 @@ keys: Chunk::unit(median),
 
-    pub fn min(&self) -> Option<&A> {
+    pub(crate) fn min(&self) -> Option<&A> {
         match self.children.first().unwrap() {
@@ -180,3 +179,3 @@ None => self.keys.first(),
 
-    pub fn max(&self) -> Option<&A> {
+    pub(crate) fn max(&self) -> Option<&A> {
         match self.children.last().unwrap() {
@@ -202,3 +201,3 @@ None => self.keys.last(),
 
-    pub fn lookup<BK>(&self, key: &BK) -> Option<&A>
+    pub(crate) fn lookup<BK>(&self, key: &BK) -> Option<&A>
     where
@@ -223,3 +222,3 @@ BK: Ord + ?Sized,
 
-    pub fn lookup_mut<BK>(&mut self, pool: &Pool<Node<A>>, key: &BK) -> Option<&mut A>
+    pub(crate) fn lookup_mut<BK>(&mut self, pool: &Pool<Node<A>>, key: &BK) -> Option<&mut A>
     where
@@ -248,3 +247,3 @@ A: Clone,
 
-    pub fn path_first<'a, BK>(
+    pub(crate) fn path_first<'a, BK>(
         &'a self,
@@ -273,3 +272,3 @@ mut path: Vec<(&'a Node<A>, usize)>,
 
-    pub fn path_last<'a, BK>(
+    pub(crate) fn path_last<'a, BK>(
         &'a self,
@@ -299,3 +298,3 @@ mut path: Vec<(&'a Node<A>, usize)>,
 
-    pub fn path_next<'a, BK>(
+    pub(crate) fn path_next<'a, BK>(
         &'a self,
@@ -334,3 +333,3 @@ key: &BK,
 
-    pub fn path_prev<'a, BK>(
+    pub(crate) fn path_prev<'a, BK>(
         &'a self,
@@ -480,3 +479,3 @@ key: &BK,
 
-    pub fn insert(&mut self, pool: &Pool<Node<A>>, value: A) -> Insert<A>
+    pub(crate) fn insert(&mut self, pool: &Pool<Node<A>>, value: A) -> Insert<A>
     where
@@ -507,3 +506,2 @@ A: Clone,
                             Insert::Replaced(value) => ReplacedAction(value),
-                            Insert::Update(_) => unreachable!(),
                             Insert::Split(left, median, right) => InsertSplit(left, median, right),
@@ -544,3 +542,3 @@ }
 
-    pub fn remove<BK>(&mut self, pool: &Pool<Node<A>>, key: &BK) -> Remove<A>
+    pub(crate) fn remove<BK>(&mut self, pool: &Pool<Node<A>>, key: &BK) -> Remove<A>
     where
@@ -836,3 +834,3 @@ A: Clone,
 
-pub struct Iter<'a, A: 'a> {
+pub struct Iter<'a, A> {
     fwd_path: Vec<(&'a Node<A>, usize)>,
@@ -843,4 +841,4 @@ back_path: Vec<(&'a Node<A>, usize)>,
 
-impl<'a, A: 'a + BTreeValue> Iter<'a, A> {
-    pub fn new<R, BK>(root: &'a Node<A>, size: usize, range: R) -> Self
+impl<'a, A: BTreeValue> Iter<'a, A> {
+    pub(crate) fn new<R, BK>(root: &'a Node<A>, size: usize, range: R) -> Self
     where
@@ -1034,3 +1032,3 @@ R: RangeBounds<BK>,
 impl<A: Clone> ConsumingIter<A> {
-    pub fn new(root: &Node<A>, total: usize) -> Self {
+    pub(crate) fn new(root: &Node<A>, total: usize) -> Self {
         ConsumingIter {
@@ -1150,3 +1148,3 @@ fwd_last: None,
 
-pub struct DiffIter<'a, A: 'a> {
+pub struct DiffIter<'a, A> {
     old_stack: Vec<IterItem<'a, A>>,
@@ -1157,3 +1155,3 @@ new_stack: Vec<IterItem<'a, A>>,
 #[derive(PartialEq, Eq)]
-pub enum DiffItem<'a, A: 'a> {
+pub enum DiffItem<'a, A> {
     Add(&'a A),
@@ -1164,3 +1162,3 @@ Update { old: &'a A, new: &'a A },
 
-enum IterItem<'a, A: 'a> {
+enum IterItem<'a, A> {
     Consider(&'a Node<A>),
@@ -1171,3 +1169,3 @@ Yield(&'a A),
 impl<'a, A: 'a> DiffIter<'a, A> {
-    pub fn new(old: &'a Node<A>, new: &'a Node<A>) -> Self {
+    pub(crate) fn new(old: &'a Node<A>, new: &'a Node<A>) -> Self {
         DiffIter {
@@ -1223,15 +1221,17 @@ old_stack: if old.keys.is_empty() {
                     (IterItem::Consider(old), IterItem::Consider(new)) => {
-                        match old.keys[0].cmp_values(&new.keys[0]) {
-                            Ordering::Less => {
-                                Self::push(&mut self.old_stack, &old);
-                                self.new_stack.push(IterItem::Consider(new));
+                        if !std::ptr::eq(old, new) {
+                            match old.keys[0].cmp_values(&new.keys[0]) {
+                                Ordering::Less => {
+                                    Self::push(&mut self.old_stack, &old);
+                                    self.new_stack.push(IterItem::Consider(new));
+                                }
+                                Ordering::Greater => {
+                                    self.old_stack.push(IterItem::Consider(old));
+                                    Self::push(&mut self.new_stack, &new);
+                                }
+                                Ordering::Equal => {
+                                    Self::push(&mut self.old_stack, &old);
+                                    Self::push(&mut self.new_stack, &new);
+                                }
                             }
-                            Ordering::Greater => {
-                                self.old_stack.push(IterItem::Consider(old));
-                                Self::push(&mut self.new_stack, &new);
-                            }
-                            Ordering::Equal => {
-                                Self::push(&mut self.old_stack, &old);
-                                Self::push(&mut self.new_stack, &new);
-                            }
                         }
@@ -1238,0 +1238,0 @@ }

src/nodes/hamt.rs

@@ -19,9 +19,9 @@ // This Source Code Form is subject to the terms of the Mozilla Public
 
-pub type HashWidth = <U2 as Pow<HashLevelSize>>::Output;
-pub type HashBits = <HashWidth as Bits>::Store; // a uint of HASH_SIZE bits
-pub const HASH_SHIFT: usize = HashLevelSize::USIZE;
-pub const HASH_WIDTH: usize = HashWidth::USIZE;
-pub const HASH_MASK: HashBits = (HASH_WIDTH - 1) as HashBits;
+pub(crate) type HashWidth = <U2 as Pow<HashLevelSize>>::Output;
+pub(crate) type HashBits = <HashWidth as Bits>::Store; // a uint of HASH_SIZE bits
+pub(crate) const HASH_SHIFT: usize = HashLevelSize::USIZE;
+pub(crate) const HASH_WIDTH: usize = HashWidth::USIZE;
+pub(crate) const HASH_MASK: HashBits = (HASH_WIDTH - 1) as HashBits;
 
-pub fn hash_key<K: Hash + ?Sized, S: BuildHasher>(bh: &S, key: &K) -> HashBits {
+pub(crate) fn hash_key<K: Hash + ?Sized, S: BuildHasher>(bh: &S, key: &K) -> HashBits {
     let mut hasher = bh.build_hasher();
@@ -45,3 +45,3 @@ key.hash(&mut hasher);
 #[derive(Clone)]
-pub struct Node<A> {
+pub(crate) struct Node<A> {
     data: SparseChunk<Entry<A>, HashWidth>,
@@ -82,3 +82,3 @@ }
 #[derive(Clone)]
-pub struct CollisionNode<A> {
+pub(crate) struct CollisionNode<A> {
     hash: HashBits,
@@ -88,3 +88,3 @@ data: Vec<A>,
 
-pub enum Entry<A> {
+pub(crate) enum Entry<A> {
     Value(A, HashBits),
@@ -139,3 +139,3 @@ Collision(Ref<CollisionNode<A>>),
     #[inline]
-    pub fn new() -> Self {
+    pub(crate) fn new() -> Self {
         Node {
@@ -152,3 +152,3 @@ data: SparseChunk::new(),
     #[inline]
-    pub fn unit(index: usize, value: Entry<A>) -> Self {
+    pub(crate) fn unit(index: usize, value: Entry<A>) -> Self {
         Node {
@@ -160,3 +160,3 @@ data: SparseChunk::unit(index, value),
     #[inline]
-    pub fn pair(index1: usize, value1: Entry<A>, index2: usize, value2: Entry<A>) -> Self {
+    pub(crate) fn pair(index1: usize, value1: Entry<A>, index2: usize, value2: Entry<A>) -> Self {
         Node {
@@ -168,3 +168,3 @@ data: SparseChunk::pair(index1, value1, index2, value2),
     #[inline]
-    pub fn single_child(pool: &Pool<Node<A>>, index: usize, node: Self) -> Self {
+    pub(crate) fn single_child(pool: &Pool<Node<A>>, index: usize, node: Self) -> Self {
         Node {
@@ -212,3 +212,3 @@ data: SparseChunk::unit(index, Entry::from_node(pool, node)),
 
-    pub fn get<BK>(&self, hash: HashBits, shift: usize, key: &BK) -> Option<&A>
+    pub(crate) fn get<BK>(&self, hash: HashBits, shift: usize, key: &BK) -> Option<&A>
     where
@@ -236,3 +236,3 @@ BK: Eq + ?Sized,
 
-    pub fn get_mut<BK>(
+    pub(crate) fn get_mut<BK>(
         &mut self,
@@ -273,3 +273,3 @@ pool: &Pool<Node<A>>,
 
-    pub fn insert(
+    pub(crate) fn insert(
         &mut self,
@@ -350,3 +350,3 @@ pool: &Pool<Node<A>>,
 
-    pub fn remove<BK>(
+    pub(crate) fn remove<BK>(
         &mut self,
@@ -487,6 +487,3 @@ pool: &Pool<Node<A>>,
 
-pub struct Iter<'a, A>
-where
-    A: 'a,
-{
+pub(crate) struct Iter<'a, A> {
     count: usize,
@@ -502,3 +499,3 @@ stack: Vec<ChunkIter<'a, Entry<A>, HashWidth>>,
 {
-    pub fn new(root: &'a Node<A>, size: usize) -> Self {
+    pub(crate) fn new(root: &'a Node<A>, size: usize) -> Self {
         Iter {
@@ -571,6 +568,3 @@ count: size,
 
-pub struct IterMut<'a, A>
-where
-    A: 'a,
-{
+pub(crate) struct IterMut<'a, A> {
     count: usize,
@@ -587,3 +581,3 @@ pool: Pool<Node<A>>,
 {
-    pub fn new(pool: &Pool<Node<A>>, root: &'a mut Node<A>, size: usize) -> Self {
+    pub(crate) fn new(pool: &Pool<Node<A>>, root: &'a mut Node<A>, size: usize) -> Self {
         IterMut {
@@ -659,3 +653,3 @@ count: size,
 
-pub struct Drain<A>
+pub(crate) struct Drain<A>
 where
@@ -675,3 +669,3 @@ A: HashValue,
 {
-    pub fn new(pool: &Pool<Node<A>>, root: PoolRef<Node<A>>, size: usize) -> Self {
+    pub(crate) fn new(pool: &Pool<Node<A>>, root: PoolRef<Node<A>>, size: usize) -> Self {
         Drain {
@@ -741,3 +735,3 @@ count: size,
 impl<A: HashValue + fmt::Debug> fmt::Debug for Node<A> {
-    fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
         write!(f, "Node[ ")?;
@@ -744,0 +738,0 @@ for i in self.data.indices() {

src/nodes/mod.rs

@@ -5,7 +5,7 @@ // This Source Code Form is subject to the terms of the Mozilla Public
 
-pub mod btree;
-pub mod hamt;
-pub mod rrb;
+pub(crate) mod btree;
+pub(crate) mod hamt;
+pub(crate) mod rrb;
 
-pub mod chunk {
+pub(crate) mod chunk {
     use crate::config::VectorChunkSize;
@@ -15,5 +15,4 @@ use sized_chunks as sc;
 
-    pub type Chunk<A> = sc::sized_chunk::Chunk<A, VectorChunkSize>;
-    pub type Iter<A> = sc::sized_chunk::Iter<A, VectorChunkSize>;
-    pub const CHUNK_SIZE: usize = VectorChunkSize::USIZE;
+    pub(crate) type Chunk<A> = sc::sized_chunk::Chunk<A, VectorChunkSize>;
+    pub(crate) const CHUNK_SIZE: usize = VectorChunkSize::USIZE;
 }

src/nodes/rrb.rs

@@ -5,3 +5,2 @@ // This Source Code Form is subject to the terms of the Mozilla Public
 
-use std::iter::FusedIterator;
 use std::mem::replace;
@@ -19,3 +18,3 @@ use std::ops::Range;
 
-pub const NODE_SIZE: usize = CHUNK_SIZE;
+pub(crate) const NODE_SIZE: usize = CHUNK_SIZE;
 
@@ -147,3 +146,3 @@ #[derive(Debug)]
 
-pub enum PushResult<A> {
+pub(crate) enum PushResult<A> {
     Full(A, usize),
@@ -153,3 +152,3 @@ Done,
 
-pub enum PopResult<A> {
+pub(crate) enum PopResult<A> {
     Done(A),
@@ -160,3 +159,3 @@ Drained(A),
 
-pub enum SplitResult {
+pub(crate) enum SplitResult {
     Dropped(usize),
@@ -252,3 +251,3 @@ OutOfBounds,
 
-pub struct Node<A> {
+pub(crate) struct Node<A> {
     children: Entry<A>,
@@ -272,7 +271,7 @@ }
 impl<A: Clone> Node<A> {
-    pub fn new() -> Self {
+    pub(crate) fn new() -> Self {
         Node { children: Empty }
     }
 
-    pub fn parent(pool: &RRBPool<A>, level: usize, children: Chunk<Self>) -> Self {
+    pub(crate) fn parent(pool: &RRBPool<A>, level: usize, children: Chunk<Self>) -> Self {
         let size = {
@@ -302,7 +301,7 @@ let mut size = Size::Size(0);
 
-    pub fn clear_node(&mut self) {
+    pub(crate) fn clear_node(&mut self) {
         self.children = Empty;
     }
 
-    pub fn from_chunk(pool: &RRBPool<A>, level: usize, chunk: PoolRef<Chunk<A>>) -> Self {
+    pub(crate) fn from_chunk(pool: &RRBPool<A>, level: usize, chunk: PoolRef<Chunk<A>>) -> Self {
         let node = Node {
@@ -314,3 +313,3 @@ children: Values(chunk),
 
-    pub fn single_parent(pool: &RRBPool<A>, node: Self) -> Self {
+    pub(crate) fn single_parent(pool: &RRBPool<A>, node: Self) -> Self {
         let size = if node.is_dense() {
@@ -328,3 +327,3 @@ Size::Size(node.len())
 
-    pub fn join_dense(pool: &RRBPool<A>, left: Self, right: Self) -> Self {
+    pub(crate) fn join_dense(pool: &RRBPool<A>, left: Self, right: Self) -> Self {
         let left_len = left.len();
@@ -340,3 +339,3 @@ let right_len = right.len();
 
-    pub fn elevate(self, pool: &RRBPool<A>, level_increment: usize) -> Self {
+    pub(crate) fn elevate(self, pool: &RRBPool<A>, level_increment: usize) -> Self {
         if level_increment > 0 {
@@ -349,3 +348,3 @@ Self::single_parent(pool, self.elevate(pool, level_increment - 1))
 
-    pub fn join_branches(self, pool: &RRBPool<A>, right: Self, level: usize) -> Self {
+    pub(crate) fn join_branches(self, pool: &RRBPool<A>, right: Self, level: usize) -> Self {
         let left_len = self.len();
@@ -367,3 +366,3 @@ let right_len = right.len();
 
-    pub fn len(&self) -> usize {
+    pub(crate) fn len(&self) -> usize {
         match self.children {
@@ -377,19 +376,20 @@ Entry::Nodes(Size::Size(size), _) => size,
 
-    pub fn is_empty(&self) -> bool {
+    pub(crate) fn is_empty(&self) -> bool {
         self.len() == 0
     }
 
-    pub fn is_single(&self) -> bool {
+    pub(crate) fn is_single(&self) -> bool {
         self.children.len() == 1
     }
 
-    pub fn is_full(&self) -> bool {
+    pub(crate) fn is_full(&self) -> bool {
         self.children.is_full()
     }
 
-    pub fn number_of_children(&self) -> usize {
+    #[allow(dead_code)] // this is only used by tests
+    pub(crate) fn number_of_children(&self) -> usize {
         self.children.len()
     }
 
-    pub fn first_child(&self) -> &Self {
+    pub(crate) fn first_child(&self) -> &Self {
         self.children.unwrap_nodes().first().unwrap()
@@ -476,3 +476,3 @@ }
 
-    pub fn index(&self, level: usize, index: usize) -> &A {
+    pub(crate) fn index(&self, level: usize, index: usize) -> &A {
         if level == 0 {
@@ -487,3 +487,3 @@ &self.children.unwrap_values()[index]
 
-    pub fn index_mut(&mut self, pool: &RRBPool<A>, level: usize, index: usize) -> &mut A {
+    pub(crate) fn index_mut(&mut self, pool: &RRBPool<A>, level: usize, index: usize) -> &mut A {
         if level == 0 {
@@ -499,3 +499,3 @@ &mut self.children.unwrap_values_mut(pool)[index]
 
-    pub fn lookup_chunk(
+    pub(crate) fn lookup_chunk(
         &self,
@@ -521,3 +521,3 @@ level: usize,
 
-    pub fn lookup_chunk_mut(
+    pub(crate) fn lookup_chunk_mut(
         &mut self,
@@ -560,3 +560,3 @@ pool: &RRBPool<A>,
 
-    pub fn push_chunk(
+    pub(crate) fn push_chunk(
         &mut self,
@@ -711,3 +711,3 @@ pool: &RRBPool<A>,
 
-    pub fn pop_chunk(
+    pub(crate) fn pop_chunk(
         &mut self,
@@ -774,3 +774,3 @@ pool: &RRBPool<A>,
 
-    pub fn split(
+    pub(crate) fn split(
         &mut self,
@@ -1000,3 +1000,3 @@ pool: &RRBPool<A>,
 
-    pub fn merge(pool: &RRBPool<A>, mut left: Self, mut right: Self, level: usize) -> Self {
+    pub(crate) fn merge(pool: &RRBPool<A>, mut left: Self, mut right: Self, level: usize) -> Self {
         if level == 0 {
@@ -1038,3 +1038,3 @@ Self::merge_leaves(pool, left, right)
 
-    pub fn assert_invariants(&self, level: usize) -> usize {
+    pub(crate) fn assert_invariants(&self, level: usize) -> usize {
         // Verifies that the size table matches reality.
@@ -1123,93 +1123,1 @@ match self.children {
 // }
-
-// Consuming iterator
-
-pub struct ConsumingIter<A> {
-    pool: RRBPool<A>,
-    root: Node<A>,
-    level: usize,
-    front_chunk: Option<Chunk<A>>,
-    back_chunk: Option<Chunk<A>>,
-    remaining: usize,
-}
-
-impl<A: Clone> ConsumingIter<A> {
-    pub fn new(pool: RRBPool<A>, root: Node<A>, level: usize) -> Self {
-        ConsumingIter {
-            pool,
-            remaining: root.len(),
-            root,
-            level,
-            front_chunk: None,
-            back_chunk: None,
-        }
-    }
-}
-
-impl<A: Clone> Iterator for ConsumingIter<A> {
-    type Item = A;
-
-    fn next(&mut self) -> Option<Self::Item> {
-        if self.remaining == 0 {
-            return None;
-        }
-        if let Some(ref mut chunk) = self.front_chunk {
-            if !chunk.is_empty() {
-                self.remaining -= 1;
-                return Some(chunk.pop_front());
-            }
-        }
-        match self.root.pop_chunk(&self.pool, self.level, Side::Left) {
-            PopResult::Done(chunk) => self.front_chunk = Some(PoolRef::unwrap_or_clone(chunk)),
-            PopResult::Drained(chunk) => self.front_chunk = Some(PoolRef::unwrap_or_clone(chunk)),
-            PopResult::Empty => {
-                if let Some(ref mut chunk) = self.back_chunk {
-                    if !chunk.is_empty() {
-                        self.remaining -= 1;
-                        return Some(chunk.pop_front());
-                    } else {
-                        return None;
-                    }
-                }
-            }
-        }
-        self.next()
-    }
-
-    fn size_hint(&self) -> (usize, Option<usize>) {
-        (self.remaining, Some(self.remaining))
-    }
-}
-
-impl<A: Clone> DoubleEndedIterator for ConsumingIter<A> {
-    fn next_back(&mut self) -> Option<Self::Item> {
-        if self.remaining == 0 {
-            return None;
-        }
-        if let Some(ref mut chunk) = self.back_chunk {
-            if !chunk.is_empty() {
-                self.remaining -= 1;
-                return Some(chunk.pop_back());
-            }
-        }
-        match self.root.pop_chunk(&self.pool, self.level, Side::Left) {
-            PopResult::Done(chunk) => self.front_chunk = Some(PoolRef::unwrap_or_clone(chunk)),
-            PopResult::Drained(chunk) => self.front_chunk = Some(PoolRef::unwrap_or_clone(chunk)),
-            PopResult::Empty => {
-                if let Some(ref mut chunk) = self.front_chunk {
-                    if !chunk.is_empty() {
-                        self.remaining -= 1;
-                        return Some(chunk.pop_back());
-                    } else {
-                        return None;
-                    }
-                }
-            }
-        }
-        self.next()
-    }
-}
-
-impl<A: Clone> ExactSizeIterator for ConsumingIter<A> {}
-
-impl<A: Clone> FusedIterator for ConsumingIter<A> {}

src/ord/set.rs

@@ -267,2 +267,15 @@ // This Source Code Form is subject to the terms of the Mozilla Public
 
+    /// Test whether two sets refer to the same content in memory.
+    ///
+    /// This is true if the two sides are references to the same set,
+    /// or if the two sets refer to the same root node.
+    ///
+    /// This would return true if you're comparing a set to itself, or
+    /// if you're comparing a set to a fresh clone of itself.
+    ///
+    /// Time: O(1)
+    pub fn ptr_eq(&self, other: &Self) -> bool {
+        std::ptr::eq(self, other) || PoolRef::ptr_eq(&self.root, &other.root)
+    }
+
     /// Get a reference to the memory pool used by this set.
@@ -327,3 +340,3 @@ ///
     #[must_use]
-    pub fn iter(&self) -> Iter<A> {
+    pub fn iter(&self) -> Iter<'_, A> {
         Iter {
@@ -336,3 +349,3 @@ it: NodeIter::new(&self.root, self.size, ..),
     #[must_use]
-    pub fn range<R, BA>(&self, range: R) -> RangedIter<A>
+    pub fn range<R, BA>(&self, range: R) -> RangedIter<'_, A>
     where
@@ -360,3 +373,3 @@ R: RangeBounds<BA>,
     #[must_use]
-    pub fn diff<'a>(&'a self, other: &'a Self) -> DiffIter<A> {
+    pub fn diff<'a>(&'a self, other: &'a Self) -> DiffIter<'_, A> {
         DiffIter {
@@ -451,3 +464,2 @@ it: NodeDiffIter::new(&self.root, &other.root),
                 }
-                Insert::Update(root) => PoolRef::new(&self.pool.0, root),
                 Insert::Split(left, median, right) => PoolRef::new(
@@ -779,2 +791,6 @@ &self.pool.0,
 impl<A> Clone for OrdSet<A> {
+    /// Clone a set.
+    ///
+    /// Time: O(1)
+    #[inline]
     fn clone(&self) -> Self {
@@ -883,3 +899,3 @@ OrdSet {
 impl<A: Ord + Debug> Debug for OrdSet<A> {
-    fn fmt(&self, f: &mut Formatter) -> Result<(), Error> {
+    fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> {
         f.debug_set().entries(self.iter()).finish()
@@ -892,6 +908,3 @@ }
 // An iterator over the elements of a set.
-pub struct Iter<'a, A>
-where
-    A: 'a,
-{
+pub struct Iter<'a, A> {
     it: NodeIter<'a, Value<A>>,
@@ -934,6 +947,3 @@ }
 // iterating over it to count.
-pub struct RangedIter<'a, A>
-where
-    A: 'a,
-{
+pub struct RangedIter<'a, A> {
     it: NodeIter<'a, Value<A>>,
@@ -989,3 +999,3 @@ }
 // An iterator over the difference between two sets.
-pub struct DiffIter<'a, A: 'a> {
+pub struct DiffIter<'a, A> {
     it: NodeDiffIter<'a, Value<A>>,
@@ -996,3 +1006,3 @@ }
 where
-    A: 'a + Ord + PartialEq,
+    A: Ord + PartialEq,
 {
@@ -1128,10 +1138,11 @@ type Item = DiffItem<'a, A>;
 // QuickCheck
-
 #[cfg(all(threadsafe, feature = "quickcheck"))]
-use quickcheck::{Arbitrary, Gen};
+mod quickcheck {
+    use super::*;
+    use ::quickcheck::{Arbitrary, Gen};
 
-#[cfg(all(threadsafe, feature = "quickcheck"))]
-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: Ord + Clone + Arbitrary + Sync> Arbitrary for OrdSet<A> {
+        fn arbitrary<G: Gen>(g: &mut G) -> Self {
+            OrdSet::from_iter(Vec::<A>::arbitrary(g))
+        }
     }
@@ -1141,3 +1152,2 @@ }
 // Proptest
-
 #[cfg(any(test, feature = "proptest"))]
@@ -1144,0 +1154,0 @@ pub mod proptest {

src/ser.rs

@@ -33,3 +33,3 @@ // This Source Code Form is subject to the terms of the Mozilla Public
 {
-    pub fn new() -> SeqVisitor<'de, S, A> {
+    pub(crate) fn new() -> SeqVisitor<'de, S, A> {
         SeqVisitor {
@@ -50,3 +50,3 @@ phantom_s: PhantomData,
 
-    fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
+    fn expecting(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
         formatter.write_str("a sequence")
@@ -88,3 +88,3 @@ }
 {
-    pub fn new() -> MapVisitor<'de, S, K, V> {
+    pub(crate) fn new() -> MapVisitor<'de, S, K, V> {
         MapVisitor {
@@ -107,3 +107,3 @@ phantom_s: PhantomData,
 
-    fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
+    fn expecting(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
         formatter.write_str("a sequence")
@@ -110,0 +110,0 @@ }

src/sort.rs

@@ -17,4 +17,4 @@ // This Source Code Form is subject to the terms of the Mozilla Public
 // Should be O(n) to O(n log n)
-pub fn do_quicksort<A, F, R>(
-    vector: &mut FocusMut<A>,
+fn do_quicksort<A, F, R>(
+    vector: &mut FocusMut<'_, A>,
     left: usize,
@@ -89,3 +89,3 @@ right: usize,
 
-pub fn quicksort<A, F>(vector: &mut FocusMut<A>, left: usize, right: usize, cmp: &F)
+pub(crate) fn quicksort<A, F>(vector: &mut FocusMut<'_, A>, left: usize, right: usize, cmp: &F)
 where
@@ -92,0 +92,0 @@ A: Clone,

src/sync.rs

@@ -5,3 +5,3 @@ // This Source Code Form is subject to the terms of the Mozilla Public
 
-pub use self::lock::Lock;
+pub(crate) use self::lock::Lock;
 
@@ -13,3 +13,3 @@ #[cfg(threadsafe)]
     /// Thread safe lock: just wraps a `Mutex`.
-    pub struct Lock<A> {
+    pub(crate) struct Lock<A> {
         lock: Arc<Mutex<A>>,
@@ -19,3 +19,3 @@ }
     impl<A> Lock<A> {
-        pub fn new(value: A) -> Self {
+        pub(crate) fn new(value: A) -> Self {
             Lock {
@@ -27,3 +27,3 @@ lock: Arc::new(Mutex::new(value)),
         #[inline]
-        pub fn lock(&mut self) -> Option<MutexGuard<A>> {
+        pub(crate) fn lock(&mut self) -> Option<MutexGuard<'_, A>> {
             self.lock.lock().ok()
@@ -49,3 +49,3 @@ }
     /// trying to access the stored data twice from the same thread.
-    pub struct Lock<A> {
+    pub(crate) struct Lock<A> {
         lock: Rc<RefCell<A>>,
@@ -55,3 +55,3 @@ }
     impl<A> Lock<A> {
-        pub fn new(value: A) -> Self {
+        pub(crate) fn new(value: A) -> Self {
             Lock {
@@ -63,3 +63,3 @@ lock: Rc::new(RefCell::new(value)),
         #[inline]
-        pub fn lock(&mut self) -> Option<RefMut<A>> {
+        pub(crate) fn lock(&mut self) -> Option<RefMut<'_, A>> {
             self.lock.try_borrow_mut().ok()
@@ -66,0 +66,0 @@ }

src/test.rs

@@ -10,3 +10,3 @@ // This Source Code Form is subject to the terms of the Mozilla Public
 
-pub fn is_sorted<A, I>(l: I) -> bool
+pub(crate) fn is_sorted<A, I>(l: I) -> bool
 where
@@ -26,3 +26,3 @@ I: IntoIterator<Item = A>,
 
-pub struct LolHasher<N: Unsigned = U64> {
+pub(crate) struct LolHasher<N: Unsigned = U64> {
     state: u64,
@@ -69,3 +69,3 @@ shift: usize,
 
-pub struct MetroHashBuilder {
+pub(crate) struct MetroHashBuilder {
     seed: u64,
@@ -75,7 +75,7 @@ }
 impl MetroHashBuilder {
-    pub fn new(seed: u64) -> Self {
+    pub(crate) fn new(seed: u64) -> Self {
         MetroHashBuilder { seed }
     }
 
-    pub fn seed(&self) -> u64 {
+    pub(crate) fn seed(&self) -> u64 {
         self.seed
@@ -82,0 +82,0 @@ }

src/tests/hashset.rs

@@ -27,3 +27,3 @@ #![allow(clippy::unit_arg)]
 {
-    fn fmt(&self, f: &mut Formatter) -> Result<(), Error> {
+    fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> {
         let mut out = String::new();
@@ -30,0 +30,0 @@ let mut expected = NatSet::new();

src/tests/ordset.rs

@@ -26,3 +26,3 @@ #![allow(clippy::unit_arg)]
 {
-    fn fmt(&self, f: &mut Formatter) -> Result<(), Error> {
+    fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> {
         let mut out = String::new();
@@ -29,0 +29,0 @@ let mut expected = BTreeSet::new();

src/tests/vector.rs

@@ -34,3 +34,3 @@ #![allow(clippy::unit_arg)]
 {
-    fn fmt(&self, f: &mut Formatter) -> Result<(), Error> {
+    fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> {
         let mut out = String::new();
@@ -37,0 +37,0 @@ let mut expected = vec![];

src/util.rs

@@ -12,3 +12,3 @@ // This Source Code Form is subject to the terms of the Mozilla Public
 #[cfg(feature = "pool")]
-pub use refpool::{PoolClone, PoolDefault};
+pub(crate) use refpool::{PoolClone, PoolDefault};
 
@@ -19,29 +19,29 @@ // The `Ref` type is an alias for either `Rc` or `Arc`, user's choice.
 #[cfg(all(threadsafe, not(feature = "pool")))]
-pub use crate::fakepool::{Arc as PoolRef, Pool, PoolClone, PoolDefault};
+pub(crate) use crate::fakepool::{Arc as PoolRef, Pool, PoolClone, PoolDefault};
 
 // `Arc` with refpool
 #[cfg(all(threadsafe, feature = "pool"))]
-pub type PoolRef<A> = refpool::PoolRef<A, refpool::PoolSync>;
+pub(crate) type PoolRef<A> = refpool::PoolRef<A, refpool::PoolSync>;
 #[cfg(all(threadsafe, feature = "pool"))]
-pub type Pool<A> = refpool::Pool<A, refpool::PoolSync>;
+pub(crate) type Pool<A> = refpool::Pool<A, refpool::PoolSync>;
 
 // `Ref` == `Arc` when threadsafe
 #[cfg(threadsafe)]
-pub type Ref<A> = std::sync::Arc<A>;
+pub(crate) type Ref<A> = std::sync::Arc<A>;
 
 // `Rc` without refpool
 #[cfg(all(not(threadsafe), not(feature = "pool")))]
-pub use crate::fakepool::{Pool, PoolClone, PoolDefault, Rc as PoolRef};
+pub(crate) use crate::fakepool::{Pool, PoolClone, PoolDefault, Rc as PoolRef};
 
 // `Rc` with refpool
 #[cfg(all(not(threadsafe), feature = "pool"))]
-pub type PoolRef<A> = refpool::PoolRef<A, refpool::PoolUnsync>;
+pub(crate) type PoolRef<A> = refpool::PoolRef<A, refpool::PoolUnsync>;
 #[cfg(all(not(threadsafe), feature = "pool"))]
-pub type Pool<A> = refpool::Pool<A, refpool::PoolUnsync>;
+pub(crate) type Pool<A> = refpool::Pool<A, refpool::PoolUnsync>;
 
 // `Ref` == `Rc` when not threadsafe
 #[cfg(not(threadsafe))]
-pub type Ref<A> = std::rc::Rc<A>;
+pub(crate) type Ref<A> = std::rc::Rc<A>;
 
-pub fn clone_ref<A>(r: Ref<A>) -> A
+pub(crate) fn clone_ref<A>(r: Ref<A>) -> A
 where
@@ -54,3 +54,3 @@ A: Clone,
 #[derive(Clone, Copy, PartialEq, Eq, Debug)]
-pub enum Side {
+pub(crate) enum Side {
     Left,
@@ -64,3 +64,3 @@ Right,
 #[allow(unsafe_code)]
-pub fn swap_indices<V>(vector: &mut V, a: usize, b: usize)
+pub(crate) fn swap_indices<V>(vector: &mut V, a: usize, b: usize)
 where
@@ -83,3 +83,3 @@ V: IndexMut<usize>,
 #[allow(dead_code)]
-pub fn linear_search_by<'a, A, I, F>(iterable: I, mut cmp: F) -> Result<usize, usize>
+pub(crate) fn linear_search_by<'a, A, I, F>(iterable: I, mut cmp: F) -> Result<usize, usize>
 where
@@ -102,3 +102,3 @@ A: 'a,
 
-pub fn to_range<R>(range: &R, right_unbounded: usize) -> Range<usize>
+pub(crate) fn to_range<R>(range: &R, right_unbounded: usize) -> Range<usize>
 where
@@ -105,0 +105,0 @@ R: RangeBounds<usize>,

src/vector/focus.rs

@@ -13,3 +13,7 @@ // This Source Code Form is subject to the terms of the Mozilla Public
 use crate::util::{to_range, PoolRef, Ref};
-use crate::vector::{Iter, IterMut, RRBPool, Vector, RRB};
+use crate::vector::{
+    Iter, IterMut, RRBPool, Vector,
+    VectorInner::{Full, Inline, Single},
+    RRB,
+};
 
@@ -83,6 +87,3 @@ /// Focused indexing over a [`Vector`][Vector].
 /// [split_at]: #method.split_at
-pub enum Focus<'a, A>
-where
-    A: 'a,
-{
+pub enum Focus<'a, A> {
     #[doc(hidden)]
@@ -102,6 +103,6 @@ Single(&'a [A]),
     pub fn new(vector: &'a Vector<A>) -> Self {
-        match vector {
-            Vector::Inline(_, chunk) => Focus::Single(chunk),
-            Vector::Single(_, chunk) => Focus::Single(chunk),
-            Vector::Full(_, tree) => Focus::Full(TreeFocus::new(tree)),
+        match &vector.vector {
+            Inline(_, chunk) => Focus::Single(chunk),
+            Single(_, chunk) => Focus::Single(chunk),
+            Full(_, tree) => Focus::Full(TreeFocus::new(tree)),
         }
@@ -465,6 +466,3 @@ }
 /// [Focus]: enum.Focus.html
-pub enum FocusMut<'a, A>
-where
-    A: 'a,
-{
+pub enum FocusMut<'a, A> {
     #[doc(hidden)]
@@ -482,9 +480,9 @@ Single(RRBPool<A>, &'a mut [A]),
     pub fn new(vector: &'a mut Vector<A>) -> Self {
-        match vector {
-            Vector::Inline(pool, chunk) => FocusMut::Single(pool.clone(), chunk),
-            Vector::Single(pool, chunk) => FocusMut::Single(
+        match &mut vector.vector {
+            Inline(pool, chunk) => FocusMut::Single(pool.clone(), chunk),
+            Single(pool, chunk) => FocusMut::Single(
                 pool.clone(),
                 PoolRef::make_mut(&pool.value_pool, chunk).as_mut_slice(),
             ),
-            Vector::Full(pool, tree) => FocusMut::Full(pool.clone(), TreeFocusMut::new(tree)),
+            Full(pool, tree) => FocusMut::Full(pool.clone(), TreeFocusMut::new(tree)),
         }
@@ -768,6 +766,3 @@ }
 
-pub struct TreeFocusMut<'a, A>
-where
-    A: 'a,
-{
+pub struct TreeFocusMut<'a, A> {
     tree: Lock<&'a mut RRB<A>>,
@@ -774,0 +769,0 @@ view: Range<usize>,

No alert changes

No metric changes