From 9918693037dce8aa4bb6f08741b6812923486c18 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 19 Jun 2024 11:26:03 +0200 Subject: Merging upstream version 1.76.0+dfsg1. Signed-off-by: Daniel Baumann --- vendor/indexmap/.cargo-checksum.json | 2 +- vendor/indexmap/Cargo.toml | 10 +- vendor/indexmap/README.md | 2 +- vendor/indexmap/RELEASES.md | 22 ++++ vendor/indexmap/src/lib.rs | 2 +- vendor/indexmap/src/map.rs | 57 +++++++++ vendor/indexmap/src/map/core.rs | 20 ++++ vendor/indexmap/src/map/core/raw.rs | 23 ---- vendor/indexmap/src/map/slice.rs | 75 +++++++++++- vendor/indexmap/src/map/tests.rs | 221 +++++++++++++++++++++++++++++++++++ vendor/indexmap/src/set.rs | 64 ++++++++++ vendor/indexmap/src/set/slice.rs | 69 ++++++++++- vendor/indexmap/src/set/tests.rs | 139 ++++++++++++++++++++++ 13 files changed, 669 insertions(+), 37 deletions(-) (limited to 'vendor/indexmap') diff --git a/vendor/indexmap/.cargo-checksum.json b/vendor/indexmap/.cargo-checksum.json index 8b983cd05..e58b146fe 100644 --- a/vendor/indexmap/.cargo-checksum.json +++ b/vendor/indexmap/.cargo-checksum.json @@ -1 +1 @@ -{"files":{"Cargo.toml":"22de53b350fe2ece033469dc50c449aed2d48b2e51bd95cd289e5a64281ad941","LICENSE-APACHE":"a60eea817514531668d7e00765731449fe14d059d3249e0bc93b36de45f759f2","LICENSE-MIT":"ecc269ef87fd38a1d98e30bfac9ba964a9dbd9315c3770fed98d4d7cb5882055","README.md":"8a6d3b3ddc2b028e309885d80152bea5434dd61c2dc9a64a68daf161fe00233b","RELEASES.md":"6caa90a493de65e6764415168586c647749ad49341f2de807ba70f212f8989b5","benches/bench.rs":"3b2900abbc9e8a60af78b0395222ee75e86bc68519a0f38477387d1572eed397","benches/faststring.rs":"5fdd6cdb19d0557ed58f241e809a240cf8939d9e5b87a72d5f127f81ab98380b","src/arbitrary.rs":"068713b1e8e762dbe9e4d19d555e77c17e59408335a40f4777d6100340605655","src/lib.rs":"f9d5ee25446660e93cbc6de314a8699c1f44da2a56ec3e1b432f61389f77af74","src/macros.rs":"32ab59dfb19713598769252e5fbcef31744dd0399bc839375c4edb5f00701b0d","src/map.rs":"ae2696a0c9746c6694db72d46e34b24d5f91e28d16d024be4d507b56e778ea56","src/map/core.rs":"55ecc1f83ac0b78d687008a057f912be2cfad270af29d1c880dde7b8ad269350","src/map/core/raw.rs":"b0aaa4cf58d789acd056c1d4cca914cd945e3f1f097479298e4432b909ccf9e4","src/map/iter.rs":"23278a1787d08dcbc30885c0653369d82a695a7b8f1084d7709fbf903e53a776","src/map/serde_seq.rs":"eff1ccbefe20c8f4338afa92732473e28fd0b752cb2bc153600ee5387d484627","src/map/slice.rs":"e264c31592ce382830281605846663ecc1694074d5b57b862de9fd090e022fc9","src/map/tests.rs":"7a192e8330a1df604d6a151e854d1d0638c068a8418f8922e92a65868ae5d569","src/mutable_keys.rs":"2bdd739bde1dd7f81c82e90595b877fbdb1cd9f963b180fcc819128bb1c750a7","src/rayon/map.rs":"22a30fa68437f69c24752c8ed17be6e084d02b0c12730e48e238a4e92f208b55","src/rayon/mod.rs":"019e9379ccab57a299ab5b5a2c0efc7561b77a715a5afe8f797c7e8330c6206c","src/rayon/set.rs":"cea2517db405ee64306e24b571ed773e129eae43ecfc866e93e365c118edc0ed","src/rustc.rs":"fe7a348c5a10a66880cb6c737593fe79d3b6de40f44ba0d7b89204aa95e14a3a","src/serde.rs":"91bbf14e3afbcf518aeb7f8a9b65011d0ede2f88d12857dfddda451f35574281","src/set.rs":"e78aa42ea1719f0398c83edd04512b1d7a699eab0578e1f6327a9eec094520ca","src/set/iter.rs":"9b90c736185889fca8b0a461293da4a1a1e50d9db539bd5b9f72254bee461a3e","src/set/slice.rs":"404cf6c749e220d2b29790180edb66b67056a5370f39955175b8f22d01fd21c1","src/set/tests.rs":"81bbb18834603479f26af1a1a6b676fe5ec949e23b2a358fcc868acedc886fa4","src/util.rs":"dbd57cfdac2a72db8c5ce83bf288bcaf33b5ae59adddcd088792a624c4c0e909","tests/equivalent_trait.rs":"efe9393069e3cfc893d2c9c0343679979578e437fdb98a10baefeced027ba310","tests/macros_full_path.rs":"c33c86d7341581fdd08e2e6375a4afca507fa603540c54a3b9e51c4cd011cd71","tests/quick.rs":"f34ae9ce8aa51d9338595c299a2088ab56dbb5c04786050009a2fa22a6bbfa32","tests/tests.rs":"f6dbeeb0e2950402b0e66ac52bf74c9e4197d3c5d9c0dde64a7998a2ef74d327"},"package":"d5477fe2230a79769d8dc68e0eabf5437907c0457a5614a9e8dddb67f65eb65d"} \ No newline at end of file +{"files":{"Cargo.toml":"7049b39c9bc740c313a738053b3d058aa66a5fdc1bd9f2e195c961d6d0dd5e92","LICENSE-APACHE":"a60eea817514531668d7e00765731449fe14d059d3249e0bc93b36de45f759f2","LICENSE-MIT":"ecc269ef87fd38a1d98e30bfac9ba964a9dbd9315c3770fed98d4d7cb5882055","README.md":"37c2da326dcc144e67b9371ec98c78becfbbb8fab93d0537999b6083bdb80243","RELEASES.md":"c22f67c4bc30852920125c80eb52ad00152b2b61b5254acb8d39081d7d8b5f32","benches/bench.rs":"3b2900abbc9e8a60af78b0395222ee75e86bc68519a0f38477387d1572eed397","benches/faststring.rs":"5fdd6cdb19d0557ed58f241e809a240cf8939d9e5b87a72d5f127f81ab98380b","src/arbitrary.rs":"068713b1e8e762dbe9e4d19d555e77c17e59408335a40f4777d6100340605655","src/lib.rs":"66bfcbc906d703f19715a03d42caa84435f71174316bd31d44beca698c22c8d4","src/macros.rs":"32ab59dfb19713598769252e5fbcef31744dd0399bc839375c4edb5f00701b0d","src/map.rs":"197b39ea7eca1497129a9d4059a1731d5306c9a08dd7cfd5eac13c89f759c8cb","src/map/core.rs":"d59dfa0a1838b6a034c32cc41426b42d9180127d5d36324a106c732f94db7e1e","src/map/core/raw.rs":"f8b19c728978278754ae49e98deb8de1034f007805d1f254d43208b0c453ed6f","src/map/iter.rs":"23278a1787d08dcbc30885c0653369d82a695a7b8f1084d7709fbf903e53a776","src/map/serde_seq.rs":"eff1ccbefe20c8f4338afa92732473e28fd0b752cb2bc153600ee5387d484627","src/map/slice.rs":"1aa189fe7b0cef6362a7c06cce31ee43c2c842ee288e5dab86196743789b76fd","src/map/tests.rs":"1866c233e34a06cc51a2e66824d68a11ac4fd3d1621a88a24af5a3882ef0de6a","src/mutable_keys.rs":"2bdd739bde1dd7f81c82e90595b877fbdb1cd9f963b180fcc819128bb1c750a7","src/rayon/map.rs":"22a30fa68437f69c24752c8ed17be6e084d02b0c12730e48e238a4e92f208b55","src/rayon/mod.rs":"019e9379ccab57a299ab5b5a2c0efc7561b77a715a5afe8f797c7e8330c6206c","src/rayon/set.rs":"cea2517db405ee64306e24b571ed773e129eae43ecfc866e93e365c118edc0ed","src/rustc.rs":"fe7a348c5a10a66880cb6c737593fe79d3b6de40f44ba0d7b89204aa95e14a3a","src/serde.rs":"91bbf14e3afbcf518aeb7f8a9b65011d0ede2f88d12857dfddda451f35574281","src/set.rs":"3d46a0d43878d965df81a2de16155c7ca8400cea245a81e28b8f9dd3f94727b2","src/set/iter.rs":"9b90c736185889fca8b0a461293da4a1a1e50d9db539bd5b9f72254bee461a3e","src/set/slice.rs":"18556170598113341e6381ad1a6234441969e7ac0e3674b7e6da29d7ffb82979","src/set/tests.rs":"155c6eec14c2979c3acebfa9c2675f249937b427780f61670a83fafd85cf1f3b","src/util.rs":"dbd57cfdac2a72db8c5ce83bf288bcaf33b5ae59adddcd088792a624c4c0e909","tests/equivalent_trait.rs":"efe9393069e3cfc893d2c9c0343679979578e437fdb98a10baefeced027ba310","tests/macros_full_path.rs":"c33c86d7341581fdd08e2e6375a4afca507fa603540c54a3b9e51c4cd011cd71","tests/quick.rs":"f34ae9ce8aa51d9338595c299a2088ab56dbb5c04786050009a2fa22a6bbfa32","tests/tests.rs":"f6dbeeb0e2950402b0e66ac52bf74c9e4197d3c5d9c0dde64a7998a2ef74d327"},"package":"d530e1a18b1cb4c484e6e34556a0d948706958449fca0cab753d649f2bce3d1f"} \ No newline at end of file diff --git a/vendor/indexmap/Cargo.toml b/vendor/indexmap/Cargo.toml index d46c15d68..65be975ee 100644 --- a/vendor/indexmap/Cargo.toml +++ b/vendor/indexmap/Cargo.toml @@ -11,9 +11,9 @@ [package] edition = "2021" -rust-version = "1.64" +rust-version = "1.63" name = "indexmap" -version = "2.0.0" +version = "2.1.0" description = "A hash table with consistent order and fast iteration." documentation = "https://docs.rs/indexmap/" readme = "README.md" @@ -45,7 +45,7 @@ no-dev-version = true tag-name = "{{version}}" [profile.bench] -debug = true +debug = 2 [lib] bench = false @@ -60,7 +60,7 @@ version = "1.0" default-features = false [dependencies.hashbrown] -version = "0.14" +version = "0.14.1" features = ["raw"] default-features = false @@ -90,7 +90,7 @@ version = "1.0" version = "0.2.1" [dev-dependencies.itertools] -version = "0.10" +version = "0.11" [dev-dependencies.lazy_static] version = "1.3" diff --git a/vendor/indexmap/README.md b/vendor/indexmap/README.md index c87360191..bf8693231 100644 --- a/vendor/indexmap/README.md +++ b/vendor/indexmap/README.md @@ -3,7 +3,7 @@ [![build status](https://github.com/bluss/indexmap/workflows/Continuous%20integration/badge.svg?branch=master)](https://github.com/bluss/indexmap/actions) [![crates.io](https://img.shields.io/crates/v/indexmap.svg)](https://crates.io/crates/indexmap) [![docs](https://docs.rs/indexmap/badge.svg)](https://docs.rs/indexmap) -[![rustc](https://img.shields.io/badge/rust-1.64%2B-orange.svg)](https://img.shields.io/badge/rust-1.64%2B-orange.svg) +[![rustc](https://img.shields.io/badge/rust-1.63%2B-orange.svg)](https://img.shields.io/badge/rust-1.63%2B-orange.svg) A pure-Rust hash table which preserves (in a limited sense) insertion order. diff --git a/vendor/indexmap/RELEASES.md b/vendor/indexmap/RELEASES.md index 1fe5ad89e..817a2dc2f 100644 --- a/vendor/indexmap/RELEASES.md +++ b/vendor/indexmap/RELEASES.md @@ -1,3 +1,25 @@ +- 2.1.0 + + - Empty slices can now be created with `map::Slice::{new, new_mut}` and + `set::Slice::new`. In addition, `Slice::new`, `len`, and `is_empty` are + now `const` functions on both types. + + - `IndexMap`, `IndexSet`, and their respective `Slice`s all have binary + search methods for sorted data: map `binary_search_keys` and set + `binary_search` for plain comparision, `binary_search_by` for custom + comparators, `binary_search_by_key` for key extraction, and + `partition_point` for boolean conditions. + +- 2.0.2 + + - The `hashbrown` dependency has been updated to version 0.14.1 to + complete the support for Rust 1.63. + +- 2.0.1 + + - **MSRV**: Rust 1.63.0 is now supported as well, pending publication of + `hashbrown`'s relaxed MSRV (or use cargo `--ignore-rust-version`). + - 2.0.0 - **MSRV**: Rust 1.64.0 or later is now required. diff --git a/vendor/indexmap/src/lib.rs b/vendor/indexmap/src/lib.rs index 8939d261a..5e427843f 100644 --- a/vendor/indexmap/src/lib.rs +++ b/vendor/indexmap/src/lib.rs @@ -81,7 +81,7 @@ //! //! ### Rust Version //! -//! This version of indexmap requires Rust 1.64 or later. +//! This version of indexmap requires Rust 1.63 or later. //! //! The indexmap 2.x release series will use a carefully considered version //! upgrade policy, where in a later 2.x version, we will raise the minimum diff --git a/vendor/indexmap/src/map.rs b/vendor/indexmap/src/map.rs index cb405caf4..4ee24d5f7 100644 --- a/vendor/indexmap/src/map.rs +++ b/vendor/indexmap/src/map.rs @@ -794,6 +794,63 @@ where }); } + /// Search over a sorted map for a key. + /// + /// Returns the position where that key is present, or the position where it can be inserted to + /// maintain the sort. See [`slice::binary_search`] for more details. + /// + /// Computes in **O(log(n))** time, which is notably less scalable than looking the key up + /// using [`get_index_of`][IndexMap::get_index_of], but this can also position missing keys. + pub fn binary_search_keys(&self, x: &K) -> Result + where + K: Ord, + { + self.as_slice().binary_search_keys(x) + } + + /// Search over a sorted map with a comparator function. + /// + /// Returns the position where that value is present, or the position where it can be inserted + /// to maintain the sort. See [`slice::binary_search_by`] for more details. + /// + /// Computes in **O(log(n))** time. + #[inline] + pub fn binary_search_by<'a, F>(&'a self, f: F) -> Result + where + F: FnMut(&'a K, &'a V) -> Ordering, + { + self.as_slice().binary_search_by(f) + } + + /// Search over a sorted map with an extraction function. + /// + /// Returns the position where that value is present, or the position where it can be inserted + /// to maintain the sort. See [`slice::binary_search_by_key`] for more details. + /// + /// Computes in **O(log(n))** time. + #[inline] + pub fn binary_search_by_key<'a, B, F>(&'a self, b: &B, f: F) -> Result + where + F: FnMut(&'a K, &'a V) -> B, + B: Ord, + { + self.as_slice().binary_search_by_key(b, f) + } + + /// Returns the index of the partition point of a sorted map according to the given predicate + /// (the index of the first element of the second partition). + /// + /// See [`slice::partition_point`] for more details. + /// + /// Computes in **O(log(n))** time. + #[must_use] + pub fn partition_point

(&self, pred: P) -> usize + where + P: FnMut(&K, &V) -> bool, + { + self.as_slice().partition_point(pred) + } + /// Reverses the order of the map’s key-value pairs in place. /// /// Computes in **O(n)** time and **O(1)** space. diff --git a/vendor/indexmap/src/map/core.rs b/vendor/indexmap/src/map/core.rs index 3e392ace6..4a78035c9 100644 --- a/vendor/indexmap/src/map/core.rs +++ b/vendor/indexmap/src/map/core.rs @@ -410,6 +410,26 @@ impl IndexMapCore { } } + pub(crate) fn swap_indices(&mut self, a: usize, b: usize) { + // If they're equal and in-bounds, there's nothing to do. + if a == b && a < self.entries.len() { + return; + } + + // We'll get a "nice" bounds-check from indexing `self.entries`, + // and then we expect to find it in the table as well. + let [ref_a, ref_b] = self + .indices + .get_many_mut( + [self.entries[a].hash.get(), self.entries[b].hash.get()], + move |i, &x| if i == 0 { x == a } else { x == b }, + ) + .expect("indices not found"); + + mem::swap(ref_a, ref_b); + self.entries.swap(a, b); + } + /// Remove an entry by swapping it with the last pub(crate) fn swap_remove_full(&mut self, hash: HashValue, key: &Q) -> Option<(usize, K, V)> where diff --git a/vendor/indexmap/src/map/core/raw.rs b/vendor/indexmap/src/map/core/raw.rs index 332770cc2..be71c9cff 100644 --- a/vendor/indexmap/src/map/core/raw.rs +++ b/vendor/indexmap/src/map/core/raw.rs @@ -100,29 +100,6 @@ impl IndexMapCore { // only the item references that are appropriately bound to `&mut self`. unsafe { self.indices.iter().map(|bucket| bucket.as_mut()) } } - - /// Return the raw bucket for the given index - fn find_index(&self, index: usize) -> RawBucket { - // We'll get a "nice" bounds-check from indexing `self.entries`, - // and then we expect to find it in the table as well. - let hash = self.entries[index].hash.get(); - self.indices - .find(hash, move |&i| i == index) - .expect("index not found") - } - - pub(crate) fn swap_indices(&mut self, a: usize, b: usize) { - // SAFETY: Can't take two `get_mut` references from one table, so we - // must use raw buckets to do the swap. This is still safe because we - // are locally sure they won't dangle, and we write them individually. - unsafe { - let raw_bucket_a = self.find_index(a); - let raw_bucket_b = self.find_index(b); - *raw_bucket_a.as_mut() = b; - *raw_bucket_b.as_mut() = a; - } - self.entries.swap(a, b); - } } /// A view into an occupied entry in a `IndexMap`. diff --git a/vendor/indexmap/src/map/slice.rs b/vendor/indexmap/src/map/slice.rs index 9fb876fd2..ebab208c9 100644 --- a/vendor/indexmap/src/map/slice.rs +++ b/vendor/indexmap/src/map/slice.rs @@ -27,7 +27,7 @@ pub struct Slice { // and reference lifetimes are bound together in function signatures. #[allow(unsafe_code)] impl Slice { - pub(super) fn from_slice(entries: &[Bucket]) -> &Self { + pub(super) const fn from_slice(entries: &[Bucket]) -> &Self { unsafe { &*(entries as *const [Bucket] as *const Self) } } @@ -49,15 +49,25 @@ impl Slice { self.into_boxed().into_vec() } + /// Returns an empty slice. + pub const fn new<'a>() -> &'a Self { + Self::from_slice(&[]) + } + + /// Returns an empty mutable slice. + pub fn new_mut<'a>() -> &'a mut Self { + Self::from_mut_slice(&mut []) + } + /// Return the number of key-value pairs in the map slice. #[inline] - pub fn len(&self) -> usize { + pub const fn len(&self) -> usize { self.entries.len() } /// Returns true if the map slice contains no elements. #[inline] - pub fn is_empty(&self) -> bool { + pub const fn is_empty(&self) -> bool { self.entries.is_empty() } @@ -201,6 +211,65 @@ impl Slice { pub fn into_values(self: Box) -> IntoValues { IntoValues::new(self.into_entries()) } + + /// Search over a sorted map for a key. + /// + /// Returns the position where that key is present, or the position where it can be inserted to + /// maintain the sort. See [`slice::binary_search`] for more details. + /// + /// Computes in **O(log(n))** time, which is notably less scalable than looking the key up in + /// the map this is a slice from using [`IndexMap::get_index_of`], but this can also position + /// missing keys. + pub fn binary_search_keys(&self, x: &K) -> Result + where + K: Ord, + { + self.binary_search_by(|p, _| p.cmp(x)) + } + + /// Search over a sorted map with a comparator function. + /// + /// Returns the position where that value is present, or the position where it can be inserted + /// to maintain the sort. See [`slice::binary_search_by`] for more details. + /// + /// Computes in **O(log(n))** time. + #[inline] + pub fn binary_search_by<'a, F>(&'a self, mut f: F) -> Result + where + F: FnMut(&'a K, &'a V) -> Ordering, + { + self.entries.binary_search_by(move |a| f(&a.key, &a.value)) + } + + /// Search over a sorted map with an extraction function. + /// + /// Returns the position where that value is present, or the position where it can be inserted + /// to maintain the sort. See [`slice::binary_search_by_key`] for more details. + /// + /// Computes in **O(log(n))** time. + #[inline] + pub fn binary_search_by_key<'a, B, F>(&'a self, b: &B, mut f: F) -> Result + where + F: FnMut(&'a K, &'a V) -> B, + B: Ord, + { + self.binary_search_by(|k, v| f(k, v).cmp(b)) + } + + /// Returns the index of the partition point of a sorted map according to the given predicate + /// (the index of the first element of the second partition). + /// + /// See [`slice::partition_point`] for more details. + /// + /// Computes in **O(log(n))** time. + #[must_use] + pub fn partition_point

(&self, mut pred: P) -> usize + where + P: FnMut(&K, &V) -> bool, + { + self.entries + .partition_point(move |a| pred(&a.key, &a.value)) + } } impl<'a, K, V> IntoIterator for &'a Slice { diff --git a/vendor/indexmap/src/map/tests.rs b/vendor/indexmap/src/map/tests.rs index f273d7162..3d2315d3e 100644 --- a/vendor/indexmap/src/map/tests.rs +++ b/vendor/indexmap/src/map/tests.rs @@ -447,3 +447,224 @@ fn iter_default() { assert_default::>(); assert_default::>(); } + +#[test] +fn test_binary_search_by() { + // adapted from std's test for binary_search + let b: IndexMap<_, i32> = [] + .into_iter() + .enumerate() + .map(|(i, x)| (i + 100, x)) + .collect(); + assert_eq!(b.binary_search_by(|_, x| x.cmp(&5)), Err(0)); + + let b: IndexMap<_, i32> = [4] + .into_iter() + .enumerate() + .map(|(i, x)| (i + 100, x)) + .collect(); + assert_eq!(b.binary_search_by(|_, x| x.cmp(&3)), Err(0)); + assert_eq!(b.binary_search_by(|_, x| x.cmp(&4)), Ok(0)); + assert_eq!(b.binary_search_by(|_, x| x.cmp(&5)), Err(1)); + + let b: IndexMap<_, i32> = [1, 2, 4, 6, 8, 9] + .into_iter() + .enumerate() + .map(|(i, x)| (i + 100, x)) + .collect(); + assert_eq!(b.binary_search_by(|_, x| x.cmp(&5)), Err(3)); + assert_eq!(b.binary_search_by(|_, x| x.cmp(&6)), Ok(3)); + assert_eq!(b.binary_search_by(|_, x| x.cmp(&7)), Err(4)); + assert_eq!(b.binary_search_by(|_, x| x.cmp(&8)), Ok(4)); + + let b: IndexMap<_, i32> = [1, 2, 4, 5, 6, 8] + .into_iter() + .enumerate() + .map(|(i, x)| (i + 100, x)) + .collect(); + assert_eq!(b.binary_search_by(|_, x| x.cmp(&9)), Err(6)); + + let b: IndexMap<_, i32> = [1, 2, 4, 6, 7, 8, 9] + .into_iter() + .enumerate() + .map(|(i, x)| (i + 100, x)) + .collect(); + assert_eq!(b.binary_search_by(|_, x| x.cmp(&6)), Ok(3)); + assert_eq!(b.binary_search_by(|_, x| x.cmp(&5)), Err(3)); + assert_eq!(b.binary_search_by(|_, x| x.cmp(&8)), Ok(5)); + + let b: IndexMap<_, i32> = [1, 2, 4, 5, 6, 8, 9] + .into_iter() + .enumerate() + .map(|(i, x)| (i + 100, x)) + .collect(); + assert_eq!(b.binary_search_by(|_, x| x.cmp(&7)), Err(5)); + assert_eq!(b.binary_search_by(|_, x| x.cmp(&0)), Err(0)); + + let b: IndexMap<_, i32> = [1, 3, 3, 3, 7] + .into_iter() + .enumerate() + .map(|(i, x)| (i + 100, x)) + .collect(); + assert_eq!(b.binary_search_by(|_, x| x.cmp(&0)), Err(0)); + assert_eq!(b.binary_search_by(|_, x| x.cmp(&1)), Ok(0)); + assert_eq!(b.binary_search_by(|_, x| x.cmp(&2)), Err(1)); + assert!(match b.binary_search_by(|_, x| x.cmp(&3)) { + Ok(1..=3) => true, + _ => false, + }); + assert!(match b.binary_search_by(|_, x| x.cmp(&3)) { + Ok(1..=3) => true, + _ => false, + }); + assert_eq!(b.binary_search_by(|_, x| x.cmp(&4)), Err(4)); + assert_eq!(b.binary_search_by(|_, x| x.cmp(&5)), Err(4)); + assert_eq!(b.binary_search_by(|_, x| x.cmp(&6)), Err(4)); + assert_eq!(b.binary_search_by(|_, x| x.cmp(&7)), Ok(4)); + assert_eq!(b.binary_search_by(|_, x| x.cmp(&8)), Err(5)); +} + +#[test] +fn test_binary_search_by_key() { + // adapted from std's test for binary_search + let b: IndexMap<_, i32> = [] + .into_iter() + .enumerate() + .map(|(i, x)| (i + 100, x)) + .collect(); + assert_eq!(b.binary_search_by_key(&5, |_, &x| x), Err(0)); + + let b: IndexMap<_, i32> = [4] + .into_iter() + .enumerate() + .map(|(i, x)| (i + 100, x)) + .collect(); + assert_eq!(b.binary_search_by_key(&3, |_, &x| x), Err(0)); + assert_eq!(b.binary_search_by_key(&4, |_, &x| x), Ok(0)); + assert_eq!(b.binary_search_by_key(&5, |_, &x| x), Err(1)); + + let b: IndexMap<_, i32> = [1, 2, 4, 6, 8, 9] + .into_iter() + .enumerate() + .map(|(i, x)| (i + 100, x)) + .collect(); + assert_eq!(b.binary_search_by_key(&5, |_, &x| x), Err(3)); + assert_eq!(b.binary_search_by_key(&6, |_, &x| x), Ok(3)); + assert_eq!(b.binary_search_by_key(&7, |_, &x| x), Err(4)); + assert_eq!(b.binary_search_by_key(&8, |_, &x| x), Ok(4)); + + let b: IndexMap<_, i32> = [1, 2, 4, 5, 6, 8] + .into_iter() + .enumerate() + .map(|(i, x)| (i + 100, x)) + .collect(); + assert_eq!(b.binary_search_by_key(&9, |_, &x| x), Err(6)); + + let b: IndexMap<_, i32> = [1, 2, 4, 6, 7, 8, 9] + .into_iter() + .enumerate() + .map(|(i, x)| (i + 100, x)) + .collect(); + assert_eq!(b.binary_search_by_key(&6, |_, &x| x), Ok(3)); + assert_eq!(b.binary_search_by_key(&5, |_, &x| x), Err(3)); + assert_eq!(b.binary_search_by_key(&8, |_, &x| x), Ok(5)); + + let b: IndexMap<_, i32> = [1, 2, 4, 5, 6, 8, 9] + .into_iter() + .enumerate() + .map(|(i, x)| (i + 100, x)) + .collect(); + assert_eq!(b.binary_search_by_key(&7, |_, &x| x), Err(5)); + assert_eq!(b.binary_search_by_key(&0, |_, &x| x), Err(0)); + + let b: IndexMap<_, i32> = [1, 3, 3, 3, 7] + .into_iter() + .enumerate() + .map(|(i, x)| (i + 100, x)) + .collect(); + assert_eq!(b.binary_search_by_key(&0, |_, &x| x), Err(0)); + assert_eq!(b.binary_search_by_key(&1, |_, &x| x), Ok(0)); + assert_eq!(b.binary_search_by_key(&2, |_, &x| x), Err(1)); + assert!(match b.binary_search_by_key(&3, |_, &x| x) { + Ok(1..=3) => true, + _ => false, + }); + assert!(match b.binary_search_by_key(&3, |_, &x| x) { + Ok(1..=3) => true, + _ => false, + }); + assert_eq!(b.binary_search_by_key(&4, |_, &x| x), Err(4)); + assert_eq!(b.binary_search_by_key(&5, |_, &x| x), Err(4)); + assert_eq!(b.binary_search_by_key(&6, |_, &x| x), Err(4)); + assert_eq!(b.binary_search_by_key(&7, |_, &x| x), Ok(4)); + assert_eq!(b.binary_search_by_key(&8, |_, &x| x), Err(5)); +} + +#[test] +fn test_partition_point() { + // adapted from std's test for partition_point + let b: IndexMap<_, i32> = [] + .into_iter() + .enumerate() + .map(|(i, x)| (i + 100, x)) + .collect(); + assert_eq!(b.partition_point(|_, &x| x < 5), 0); + + let b: IndexMap<_, i32> = [4] + .into_iter() + .enumerate() + .map(|(i, x)| (i + 100, x)) + .collect(); + assert_eq!(b.partition_point(|_, &x| x < 3), 0); + assert_eq!(b.partition_point(|_, &x| x < 4), 0); + assert_eq!(b.partition_point(|_, &x| x < 5), 1); + + let b: IndexMap<_, i32> = [1, 2, 4, 6, 8, 9] + .into_iter() + .enumerate() + .map(|(i, x)| (i + 100, x)) + .collect(); + assert_eq!(b.partition_point(|_, &x| x < 5), 3); + assert_eq!(b.partition_point(|_, &x| x < 6), 3); + assert_eq!(b.partition_point(|_, &x| x < 7), 4); + assert_eq!(b.partition_point(|_, &x| x < 8), 4); + + let b: IndexMap<_, i32> = [1, 2, 4, 5, 6, 8] + .into_iter() + .enumerate() + .map(|(i, x)| (i + 100, x)) + .collect(); + assert_eq!(b.partition_point(|_, &x| x < 9), 6); + + let b: IndexMap<_, i32> = [1, 2, 4, 6, 7, 8, 9] + .into_iter() + .enumerate() + .map(|(i, x)| (i + 100, x)) + .collect(); + assert_eq!(b.partition_point(|_, &x| x < 6), 3); + assert_eq!(b.partition_point(|_, &x| x < 5), 3); + assert_eq!(b.partition_point(|_, &x| x < 8), 5); + + let b: IndexMap<_, i32> = [1, 2, 4, 5, 6, 8, 9] + .into_iter() + .enumerate() + .map(|(i, x)| (i + 100, x)) + .collect(); + assert_eq!(b.partition_point(|_, &x| x < 7), 5); + assert_eq!(b.partition_point(|_, &x| x < 0), 0); + + let b: IndexMap<_, i32> = [1, 3, 3, 3, 7] + .into_iter() + .enumerate() + .map(|(i, x)| (i + 100, x)) + .collect(); + assert_eq!(b.partition_point(|_, &x| x < 0), 0); + assert_eq!(b.partition_point(|_, &x| x < 1), 0); + assert_eq!(b.partition_point(|_, &x| x < 2), 1); + assert_eq!(b.partition_point(|_, &x| x < 3), 1); + assert_eq!(b.partition_point(|_, &x| x < 4), 4); + assert_eq!(b.partition_point(|_, &x| x < 5), 4); + assert_eq!(b.partition_point(|_, &x| x < 6), 4); + assert_eq!(b.partition_point(|_, &x| x < 7), 4); + assert_eq!(b.partition_point(|_, &x| x < 8), 5); +} diff --git a/vendor/indexmap/src/set.rs b/vendor/indexmap/src/set.rs index dbee481f1..c047b0bea 100644 --- a/vendor/indexmap/src/set.rs +++ b/vendor/indexmap/src/set.rs @@ -56,6 +56,11 @@ type Bucket = super::Bucket; /// `0..self.len()`. For example, the method `.get_full` looks up the index for /// a value, and the method `.get_index` looks up the value by index. /// +/// # Complexity +/// +/// Internally, `IndexSet` just holds an [`IndexMap`](IndexMap). Thus the complexity +/// of the two are the same for most methods. +/// /// # Examples /// /// ``` @@ -420,6 +425,8 @@ where } /// Return item index, if it exists in the set + /// + /// Computes in **O(1)** time (average). pub fn get_index_of(&self, value: &Q) -> Option where Q: Hash + Equivalent, @@ -681,6 +688,63 @@ where }); } + /// Search over a sorted set for a value. + /// + /// Returns the position where that value is present, or the position where it can be inserted + /// to maintain the sort. See [`slice::binary_search`] for more details. + /// + /// Computes in **O(log(n))** time, which is notably less scalable than looking the value up + /// using [`get_index_of`][IndexSet::get_index_of], but this can also position missing values. + pub fn binary_search(&self, x: &T) -> Result + where + T: Ord, + { + self.as_slice().binary_search(x) + } + + /// Search over a sorted set with a comparator function. + /// + /// Returns the position where that value is present, or the position where it can be inserted + /// to maintain the sort. See [`slice::binary_search_by`] for more details. + /// + /// Computes in **O(log(n))** time. + #[inline] + pub fn binary_search_by<'a, F>(&'a self, f: F) -> Result + where + F: FnMut(&'a T) -> Ordering, + { + self.as_slice().binary_search_by(f) + } + + /// Search over a sorted set with an extraction function. + /// + /// Returns the position where that value is present, or the position where it can be inserted + /// to maintain the sort. See [`slice::binary_search_by_key`] for more details. + /// + /// Computes in **O(log(n))** time. + #[inline] + pub fn binary_search_by_key<'a, B, F>(&'a self, b: &B, f: F) -> Result + where + F: FnMut(&'a T) -> B, + B: Ord, + { + self.as_slice().binary_search_by_key(b, f) + } + + /// Returns the index of the partition point of a sorted set according to the given predicate + /// (the index of the first element of the second partition). + /// + /// See [`slice::partition_point`] for more details. + /// + /// Computes in **O(log(n))** time. + #[must_use] + pub fn partition_point

(&self, pred: P) -> usize + where + P: FnMut(&T) -> bool, + { + self.as_slice().partition_point(pred) + } + /// Reverses the order of the set’s values in place. /// /// Computes in **O(n)** time and **O(1)** space. diff --git a/vendor/indexmap/src/set/slice.rs b/vendor/indexmap/src/set/slice.rs index 608311d2d..251d0677d 100644 --- a/vendor/indexmap/src/set/slice.rs +++ b/vendor/indexmap/src/set/slice.rs @@ -24,7 +24,7 @@ pub struct Slice { // and reference lifetimes are bound together in function signatures. #[allow(unsafe_code)] impl Slice { - pub(super) fn from_slice(entries: &[Bucket]) -> &Self { + pub(super) const fn from_slice(entries: &[Bucket]) -> &Self { unsafe { &*(entries as *const [Bucket] as *const Self) } } @@ -42,13 +42,18 @@ impl Slice { self.into_boxed().into_vec() } + /// Returns an empty slice. + pub const fn new<'a>() -> &'a Self { + Self::from_slice(&[]) + } + /// Return the number of elements in the set slice. - pub fn len(&self) -> usize { + pub const fn len(&self) -> usize { self.entries.len() } /// Returns true if the set slice contains no elements. - pub fn is_empty(&self) -> bool { + pub const fn is_empty(&self) -> bool { self.entries.is_empty() } @@ -109,6 +114,64 @@ impl Slice { pub fn iter(&self) -> Iter<'_, T> { Iter::new(&self.entries) } + + /// Search over a sorted set for a value. + /// + /// Returns the position where that value is present, or the position where it can be inserted + /// to maintain the sort. See [`slice::binary_search`] for more details. + /// + /// Computes in **O(log(n))** time, which is notably less scalable than looking the value up in + /// the set this is a slice from using [`IndexSet::get_index_of`], but this can also position + /// missing values. + pub fn binary_search(&self, x: &T) -> Result + where + T: Ord, + { + self.binary_search_by(|p| p.cmp(x)) + } + + /// Search over a sorted set with a comparator function. + /// + /// Returns the position where that value is present, or the position where it can be inserted + /// to maintain the sort. See [`slice::binary_search_by`] for more details. + /// + /// Computes in **O(log(n))** time. + #[inline] + pub fn binary_search_by<'a, F>(&'a self, mut f: F) -> Result + where + F: FnMut(&'a T) -> Ordering, + { + self.entries.binary_search_by(move |a| f(&a.key)) + } + + /// Search over a sorted set with an extraction function. + /// + /// Returns the position where that value is present, or the position where it can be inserted + /// to maintain the sort. See [`slice::binary_search_by_key`] for more details. + /// + /// Computes in **O(log(n))** time. + #[inline] + pub fn binary_search_by_key<'a, B, F>(&'a self, b: &B, mut f: F) -> Result + where + F: FnMut(&'a T) -> B, + B: Ord, + { + self.binary_search_by(|k| f(k).cmp(b)) + } + + /// Returns the index of the partition point of a sorted set according to the given predicate + /// (the index of the first element of the second partition). + /// + /// See [`slice::partition_point`] for more details. + /// + /// Computes in **O(log(n))** time. + #[must_use] + pub fn partition_point

(&self, mut pred: P) -> usize + where + P: FnMut(&T) -> bool, + { + self.entries.partition_point(move |a| pred(&a.key)) + } } impl<'a, T> IntoIterator for &'a Slice { diff --git a/vendor/indexmap/src/set/tests.rs b/vendor/indexmap/src/set/tests.rs index 44f8ed841..d7bb9de64 100644 --- a/vendor/indexmap/src/set/tests.rs +++ b/vendor/indexmap/src/set/tests.rs @@ -543,3 +543,142 @@ fn iter_default() { assert_default::>(); assert_default::>(); } + +#[test] +fn test_binary_search_by() { + // adapted from std's test for binary_search + let b: IndexSet = [].into(); + assert_eq!(b.binary_search_by(|x| x.cmp(&5)), Err(0)); + + let b: IndexSet = [4].into(); + assert_eq!(b.binary_search_by(|x| x.cmp(&3)), Err(0)); + assert_eq!(b.binary_search_by(|x| x.cmp(&4)), Ok(0)); + assert_eq!(b.binary_search_by(|x| x.cmp(&5)), Err(1)); + + let b: IndexSet = [1, 2, 4, 6, 8, 9].into(); + assert_eq!(b.binary_search_by(|x| x.cmp(&5)), Err(3)); + assert_eq!(b.binary_search_by(|x| x.cmp(&6)), Ok(3)); + assert_eq!(b.binary_search_by(|x| x.cmp(&7)), Err(4)); + assert_eq!(b.binary_search_by(|x| x.cmp(&8)), Ok(4)); + + let b: IndexSet = [1, 2, 4, 5, 6, 8].into(); + assert_eq!(b.binary_search_by(|x| x.cmp(&9)), Err(6)); + + let b: IndexSet = [1, 2, 4, 6, 7, 8, 9].into(); + assert_eq!(b.binary_search_by(|x| x.cmp(&6)), Ok(3)); + assert_eq!(b.binary_search_by(|x| x.cmp(&5)), Err(3)); + assert_eq!(b.binary_search_by(|x| x.cmp(&8)), Ok(5)); + + let b: IndexSet = [1, 2, 4, 5, 6, 8, 9].into(); + assert_eq!(b.binary_search_by(|x| x.cmp(&7)), Err(5)); + assert_eq!(b.binary_search_by(|x| x.cmp(&0)), Err(0)); + + let b: IndexSet = [1, 3, 3, 3, 7].into(); + assert_eq!(b.binary_search_by(|x| x.cmp(&0)), Err(0)); + assert_eq!(b.binary_search_by(|x| x.cmp(&1)), Ok(0)); + assert_eq!(b.binary_search_by(|x| x.cmp(&2)), Err(1)); + // diff from std as set merges the duplicate keys + assert!(match b.binary_search_by(|x| x.cmp(&3)) { + Ok(1..=2) => true, + _ => false, + }); + assert!(match b.binary_search_by(|x| x.cmp(&3)) { + Ok(1..=2) => true, + _ => false, + }); + assert_eq!(b.binary_search_by(|x| x.cmp(&4)), Err(2)); + assert_eq!(b.binary_search_by(|x| x.cmp(&5)), Err(2)); + assert_eq!(b.binary_search_by(|x| x.cmp(&6)), Err(2)); + assert_eq!(b.binary_search_by(|x| x.cmp(&7)), Ok(2)); + assert_eq!(b.binary_search_by(|x| x.cmp(&8)), Err(3)); +} + +#[test] +fn test_binary_search_by_key() { + // adapted from std's test for binary_search + let b: IndexSet = [].into(); + assert_eq!(b.binary_search_by_key(&5, |&x| x), Err(0)); + + let b: IndexSet = [4].into(); + assert_eq!(b.binary_search_by_key(&3, |&x| x), Err(0)); + assert_eq!(b.binary_search_by_key(&4, |&x| x), Ok(0)); + assert_eq!(b.binary_search_by_key(&5, |&x| x), Err(1)); + + let b: IndexSet = [1, 2, 4, 6, 8, 9].into(); + assert_eq!(b.binary_search_by_key(&5, |&x| x), Err(3)); + assert_eq!(b.binary_search_by_key(&6, |&x| x), Ok(3)); + assert_eq!(b.binary_search_by_key(&7, |&x| x), Err(4)); + assert_eq!(b.binary_search_by_key(&8, |&x| x), Ok(4)); + + let b: IndexSet = [1, 2, 4, 5, 6, 8].into(); + assert_eq!(b.binary_search_by_key(&9, |&x| x), Err(6)); + + let b: IndexSet = [1, 2, 4, 6, 7, 8, 9].into(); + assert_eq!(b.binary_search_by_key(&6, |&x| x), Ok(3)); + assert_eq!(b.binary_search_by_key(&5, |&x| x), Err(3)); + assert_eq!(b.binary_search_by_key(&8, |&x| x), Ok(5)); + + let b: IndexSet = [1, 2, 4, 5, 6, 8, 9].into(); + assert_eq!(b.binary_search_by_key(&7, |&x| x), Err(5)); + assert_eq!(b.binary_search_by_key(&0, |&x| x), Err(0)); + + let b: IndexSet = [1, 3, 3, 3, 7].into(); + assert_eq!(b.binary_search_by_key(&0, |&x| x), Err(0)); + assert_eq!(b.binary_search_by_key(&1, |&x| x), Ok(0)); + assert_eq!(b.binary_search_by_key(&2, |&x| x), Err(1)); + // diff from std as set merges the duplicate keys + assert!(match b.binary_search_by_key(&3, |&x| x) { + Ok(1..=2) => true, + _ => false, + }); + assert!(match b.binary_search_by_key(&3, |&x| x) { + Ok(1..=2) => true, + _ => false, + }); + assert_eq!(b.binary_search_by_key(&4, |&x| x), Err(2)); + assert_eq!(b.binary_search_by_key(&5, |&x| x), Err(2)); + assert_eq!(b.binary_search_by_key(&6, |&x| x), Err(2)); + assert_eq!(b.binary_search_by_key(&7, |&x| x), Ok(2)); + assert_eq!(b.binary_search_by_key(&8, |&x| x), Err(3)); +} + +#[test] +fn test_partition_point() { + // adapted from std's test for partition_point + let b: IndexSet = [].into(); + assert_eq!(b.partition_point(|&x| x < 5), 0); + + let b: IndexSet<_> = [4].into(); + assert_eq!(b.partition_point(|&x| x < 3), 0); + assert_eq!(b.partition_point(|&x| x < 4), 0); + assert_eq!(b.partition_point(|&x| x < 5), 1); + + let b: IndexSet<_> = [1, 2, 4, 6, 8, 9].into(); + assert_eq!(b.partition_point(|&x| x < 5), 3); + assert_eq!(b.partition_point(|&x| x < 6), 3); + assert_eq!(b.partition_point(|&x| x < 7), 4); + assert_eq!(b.partition_point(|&x| x < 8), 4); + + let b: IndexSet<_> = [1, 2, 4, 5, 6, 8].into(); + assert_eq!(b.partition_point(|&x| x < 9), 6); + + let b: IndexSet<_> = [1, 2, 4, 6, 7, 8, 9].into(); + assert_eq!(b.partition_point(|&x| x < 6), 3); + assert_eq!(b.partition_point(|&x| x < 5), 3); + assert_eq!(b.partition_point(|&x| x < 8), 5); + + let b: IndexSet<_> = [1, 2, 4, 5, 6, 8, 9].into(); + assert_eq!(b.partition_point(|&x| x < 7), 5); + assert_eq!(b.partition_point(|&x| x < 0), 0); + + let b: IndexSet<_> = [1, 3, 3, 3, 7].into(); + assert_eq!(b.partition_point(|&x| x < 0), 0); + assert_eq!(b.partition_point(|&x| x < 1), 0); + assert_eq!(b.partition_point(|&x| x < 2), 1); + assert_eq!(b.partition_point(|&x| x < 3), 1); + assert_eq!(b.partition_point(|&x| x < 4), 2); // diff from std as set merges the duplicate keys + assert_eq!(b.partition_point(|&x| x < 5), 2); + assert_eq!(b.partition_point(|&x| x < 6), 2); + assert_eq!(b.partition_point(|&x| x < 7), 2); + assert_eq!(b.partition_point(|&x| x < 8), 3); +} -- cgit v1.2.3