Update itertools to 0.14.0
Test: m
Change-Id: I780e9a4636bf7d00b7ebce6adb19dffbcdc1050e
diff --git a/crates/itertools/.android-checksum.json b/crates/itertools/.android-checksum.json
index bad3edd..1d505e1 100644
--- a/crates/itertools/.android-checksum.json
+++ b/crates/itertools/.android-checksum.json
@@ -1 +1 @@
-{"package":null,"files":{".cargo-checksum.json":"257dc46557410c03abd76c73a69f9adf3e564bbbea257a4b98eeb26162b7f207","Android.bp":"5ee265653e6582d25b05825dc8a2e7e41729cde2b8e667337d995624e817789d","CHANGELOG.md":"f1847e87f3097ef6f806ea99742d417c54cef0c02c96c8a52df8f43f9c92f0db","CONTRIBUTING.md":"0d7ab7d906e3ffb5f7c83efeefe84579106cc9f12a87886f03fdb0ddc5b8f81e","Cargo.lock":"32bc950e9dd34296698a2d5c3ce1e60aa1d7a0526578ae3fa6aeab144dbc41a7","Cargo.toml":"e762efee6c058e7b9ee88bd45fd9fd7aa55bfd288a9af6baafe5dfcae6d192a5","LICENSE":"3c7cd2396b5b772507febd2615d3d5a55b80103845037df77c87ba6e64872f2c","LICENSE-APACHE":"3c7cd2396b5b772507febd2615d3d5a55b80103845037df77c87ba6e64872f2c","LICENSE-MIT":"25045647f8514b43237cf0efdc4ba7dc153f8793e19c9e4b4a65af7e1b78cb5b","METADATA":"f3168c1900d70cac03a3469f5f523109e334aa59e35b95e8724c91a260506fbb","MODULE_LICENSE_APACHE2":"0d6f8afa3940b7f06bebee651376d43bc8b0d5b437337be2696d30377451e93a","README.md":"9cde44f0b329cdf3c255738ca84b60032f6280349ed2bc63270a4556fb39a065","TEST_MAPPING":"07d90e0d0888f048c20648fd613f2d89945853092265fa9346a3d4254bf0de17","benches/bench1.rs":"3d593f853938bf0d3eaeed26cd39a3afb90c48a8e799a4d4ff0dc26c5eee85f1","benches/combinations.rs":"9b36ec7cf395c2d8892a027914d57b114302f9a0a499959a1ad1c8942742daf8","benches/combinations_with_replacement.rs":"9fa18af6ddfc6f812fcaca4bc77fba4d4a04577251e2bcc25ff2bf5b9478bcdd","benches/fold_specialization.rs":"048b22ee15ca3c8f2da52ea3394527106cd1d8296d59898a7f84ff85c79e68a9","benches/powerset.rs":"47fe0d3cb3ba056283b88d7250c4f250b58b98020aed775a3ee03d26cf63fed4","benches/specializations.rs":"58cf97f0c51b48a491b897f5e5c6ff90854b871f53a27f19db52d2cd44998442","benches/tree_reduce.rs":"88c65e4da528f6df83a37eb720a8441eb284e872a5daf184a1004109937417f3","benches/tuple_combinations.rs":"4bc2c02549fd3aac467fd2c40e4f3134901ef2cecc67d3ace338d42f5d7bddd8","benches/tuples.rs":"07a663fced16df1e519110ba5c2dd9483955f2f21e8fc5171eea60d52bc715d0","cargo_embargo.json":"1c412d446965f40b1f2eb1d39291bb0e0732cc3b9c5fb36737f432d930e23c6e","examples/iris.data":"f952e90ad557c796d4834705174aaf71bb0a235dd09ca9407eff9b5b72a9f76f","examples/iris.rs":"6c3b8e2763ee4fdec1ecd7a4942b2d1bbf71d9658feb866b7420cb7512945c99","src/adaptors/coalesce.rs":"0a14e65588912e47c86c4cc43be4173992ac69958e73e4ca75406bf1a72787c1","src/adaptors/map.rs":"d0d5adb862ba83a9ff8d7bc2c2aa3e794a00639cb93a8355b4388c3d726d5c22","src/adaptors/mod.rs":"87833680388fc63edb2f4c9775a20e2e7e9055da0b527aeeecac9c9c1ffa8ef4","src/adaptors/multi_product.rs":"833ccc206e0d6d0a6e5ec95835c6ef87b9c6ff0db510c3aaf9a5627cd5061feb","src/combinations.rs":"1cea853cdba4b0254520e19129266651dec5a874cd386d7df80f74c05a0f16f3","src/combinations_with_replacement.rs":"7ebf227e9a1999a302e3f4642f27b39a96bad81760a8e0a19c4ec5eb1a20559c","src/concat_impl.rs":"4c0774db0f60c30214dafa73441676e7e81a4d6d64e579a80cc1a3092852266b","src/cons_tuples_impl.rs":"8fe663096421ee4cb48433298d2d3dd574261219004cf862d763256ef0f5073e","src/diff.rs":"a75dbab47313046304d8accbb1a4511800a90a5da861fa800a1bf4a5a04eca3f","src/duplicates_impl.rs":"dd3d4e04af8a85479658115105646159640c1a2b9d2216f251922c97da8b2f49","src/either_or_both.rs":"7c990e808fd7ae8b855a8383be7cc77e7aa3b5fe52044c4a662f2e47e94a9c68","src/exactly_one_err.rs":"558badd3aad0c38c4344a8e1469af442043304af51cde3fb9b41ad4c1581f349","src/extrema_set.rs":"15e5e133bb8efa2a99e8d68b8cbf5466cad6d3d7a5baec1b11a467cb7511da5e","src/flatten_ok.rs":"0bd61298617834e035c68ac9e485bae7f9d89d0fa07b5a2a84818bbddc92abd4","src/format.rs":"266506a1caa9b14caed9a4c4ff0564025d5726fb5119c79db8489635a3f453de","src/free.rs":"75ca79438588826fa2aec14097197a0af139786417dc0902d04f7a8337fd40b1","src/group_map.rs":"f2e97e58f03f36a01e31da3f912bfe1dcd4b456d5c6e05f540c4ec8344891b4b","src/groupbylazy.rs":"6b27e9c5c801e54946dec9e29c5d4bca290d7200a84d4c93a8e4af3ad8c9e3cf","src/grouping_map.rs":"0b62f8987d14956ee7bfdb1d5bbdfe9f01e17b1585647f9ad310332e74ce2e7f","src/impl_macros.rs":"29d480f310b17a1e8c68504d1be6024a3ccf9b4350a93b2cd6ea9b7be279ac6a","src/intersperse.rs":"481b6729e3f98cd62405f0c181aa2bb528508bd084bf3a3054d57c810f6e5c43","src/iter_index.rs":"1d68bf19eed6f975d06131638534e5a7b382f5b03aeb29e1107412bb08ce36a1","src/k_smallest.rs":"ffda60dd32d662c75d3ed9cfa849458e5322fc20ecab0d2dd8cc75c9cbe9c753","src/kmerge_impl.rs":"eaff0331e8a85b5b6a2a3a2041e5546b6d765a2ea0fc948f570d577d8fc646a0","src/lazy_buffer.rs":"8fd6ff0e0700ad6f22543a9cfe209cd10e2284a2c63b769e2cfb9349e154c7d7","src/lib.rs":"590fe6fe598de46afb7eadc289438730913a7236b9a71fbb70db76855ac584dc","src/merge_join.rs":"91f824fb58859d0a0b7925f530a64e91218baf46feece8b5b76974ae5f05f8aa","src/minmax.rs":"6c1eb4f9048153adb841adcbc33c78f237fbadd3b8705289a9fef104b4920693","src/multipeek_impl.rs":"502c545ab39b8db9ea5482b37226c02290aa5ba169b58a9c2427bb38a6f18628","src/pad_tail.rs":"91babaf864d230a402d63c959f1d87a0ff6b6881bb582b213896f7fe5fa61d14","src/peek_nth.rs":"b293ccc75f50919d44653f4453cd27a28bd33f21448df57b1f87a72e38941417","src/peeking_take_while.rs":"9e0bd09c19ed1df98772b43ed16a646d6887ecb6af73e5ebf22889065fd0d770","src/permutations.rs":"1cc667ff17fa7b3a9227f7a96cb861770228c3a1cabb6e0a515cd46ab8ef46c3","src/powerset.rs":"2a55d1100eda58c94a0843a639120df6d26b15318c659404654fcfea0275880e","src/process_results_impl.rs":"1196dae4ae1118e090b46def6b4f4519392000f811c7a9ced031628553f63233","src/put_back_n_impl.rs":"da1b66a391cb0b1d5467fd6257e1dcc86b90a2c12ed03c0bd6cad73a71c3414d","src/rciter_impl.rs":"7774181fcf4b70155123faacd512ba059d18ef05a5a3dd7fb5fab61d7540d99f","src/repeatn.rs":"4d5be3a1d97e91ee94fdc8d508ebe7fb815279db1b06d0e38ddf69e58475ed4a","src/size_hint.rs":"3ef07e7c3fa75bd1469de67452f8eb992a4d6c3e7839e79ff883bfb02ed65839","src/sources.rs":"b9d87801a0c1d39efb657a6f4fa33e95e71fab2230a8e2ae3d02bb686f42cb99","src/take_while_inclusive.rs":"ec3a8501a874422d8a7e6f556c949cc411180e43116ed7fa5f92954829eb56da","src/tee.rs":"9f97c5b4bb44ce437b51e92619274a488bd32eab8a9897c192e64dea9d5fbd9b","src/tuple_impl.rs":"0ece5c00544ffe88c61d89ad7bb997127c86764f17fe1a53e6a0c019ba185984","src/unique_impl.rs":"a99c3ae80697791d7b663b1d8a981fdcfe6e1ca67155c4ac87b4ad1d8fb6e18e","src/unziptuple.rs":"e26d5ab3e522604e84b5286ab0d7f608394677db3b9a69beeb4d557f5871f8d4","src/with_position.rs":"9cdd85aa92ccdadf88dfcd9643a69af6d3e053c5597ef3b00ee62fdc5bbc611d","src/zip_eq_impl.rs":"38fa6317618064c666be842ac1452c04b4f90d2e90e4e2a54266312a13963031","src/zip_longest.rs":"3f9003b0b7c050d53f48d2d36997ea45bb428fa74e5ba13d1df98205f7a51084","src/ziptuple.rs":"552ab217529b637f12b5e39702008f0ac91d2dc0b5d5819b839766d740c64c9e","tests/adaptors_no_collect.rs":"1aa9c1a1f6144f7b7a126c1802c2a791e1bc7d0a6330971ab5d51c1f6ab9e2d9","tests/flatten_ok.rs":"05d7773126bc41913bd6a5db6617c4cf90bb051f6ad5e7c1718694b6a0b4e0c1","tests/laziness.rs":"660e0df9a95e5021d954b57fec5ca18aeb71a6fd8c13637faf0eef023642c084","tests/macros_hygiene.rs":"809cebecb915752fe8e2b5883f8725b0494181775ddbe231bb0945c686dc53b6","tests/merge_join.rs":"cf07e22a97cb496ae2a18ffbecaf797c9cc99f2a0de7958ebf0da86b21590cad","tests/peeking_take_while.rs":"8b0220981b437aa6756f2510ea4e25cf49a19a399a14a465dccff9ad08c48d55","tests/quick.rs":"700de3a8923974ee349a395febd047befb668b4aeb523cfa3c7d0442724ef8b4","tests/specializations.rs":"3d5e5305d4c23d780cd7003c78c87c9f8eccbf32d86680a6ad5da6c2081d7980","tests/test_core.rs":"c3986dcb99a72f8d36203a341acdd71771b96f354a2832f1b25ff0bc740bb6ae","tests/test_std.rs":"818af66b216bafdd527ff456ad4943187f28b59b9eb215c4c38981038192a988","tests/tuples.rs":"92df348f8816e17a3c02eeac420ae33e0a2c6ff994f8171aaecd3875863d2f0f","tests/zip.rs":"f1d057149f847eccaebc110b474df6bc6c65e002be09af64516c46675a10ba99"}}
\ No newline at end of file
+{"package":null,"files":{".cargo-checksum.json":"e4ab3828cab0255c2394a3c0b04bd22eeb1698b2fa7591a4e75b164c8f255260","Android.bp":"6db0a7d0d137b70817938262b39b68e4620d28ef2d1fb85d3cde789a9cff5874","CHANGELOG.md":"943156ca6b8384eb6ab7fd6b52ffb38f0874915fac724845fb1fde34ec56202a","CONTRIBUTING.md":"0d7ab7d906e3ffb5f7c83efeefe84579106cc9f12a87886f03fdb0ddc5b8f81e","Cargo.lock":"bc157173dcde8d4fcb537b05849527e45ba85d079866ae3027feb6d11bcfdaa7","Cargo.toml":"7ab158a0e9c5cac50f97adc234907c1569e51b2f9e47ba74addfd8540c8c337e","LICENSE":"3c7cd2396b5b772507febd2615d3d5a55b80103845037df77c87ba6e64872f2c","LICENSE-APACHE":"3c7cd2396b5b772507febd2615d3d5a55b80103845037df77c87ba6e64872f2c","LICENSE-MIT":"25045647f8514b43237cf0efdc4ba7dc153f8793e19c9e4b4a65af7e1b78cb5b","METADATA":"c48db4794e069d47a59163878e98a4854a6c7e40ff7bd9a512dddaa443b999bb","MODULE_LICENSE_APACHE2":"0d6f8afa3940b7f06bebee651376d43bc8b0d5b437337be2696d30377451e93a","README.md":"1b66d859b3ffc9629f9389d22b3ef05598e4675af432ba7ba7ba2fa474962174","TEST_MAPPING":"07d90e0d0888f048c20648fd613f2d89945853092265fa9346a3d4254bf0de17","benches/bench1.rs":"3d593f853938bf0d3eaeed26cd39a3afb90c48a8e799a4d4ff0dc26c5eee85f1","benches/combinations.rs":"9b36ec7cf395c2d8892a027914d57b114302f9a0a499959a1ad1c8942742daf8","benches/combinations_with_replacement.rs":"9fa18af6ddfc6f812fcaca4bc77fba4d4a04577251e2bcc25ff2bf5b9478bcdd","benches/fold_specialization.rs":"048b22ee15ca3c8f2da52ea3394527106cd1d8296d59898a7f84ff85c79e68a9","benches/k_smallest.rs":"bb2b1f1e05814a42da916884727ac550ee995c3b90070497c41d9906cbefbb1b","benches/powerset.rs":"47fe0d3cb3ba056283b88d7250c4f250b58b98020aed775a3ee03d26cf63fed4","benches/specializations.rs":"1662f3f02d989458de47c219ef6dd507f75ee9e0046fabd198ac4b2ddf83c299","benches/tree_reduce.rs":"88c65e4da528f6df83a37eb720a8441eb284e872a5daf184a1004109937417f3","benches/tuple_combinations.rs":"4bc2c02549fd3aac467fd2c40e4f3134901ef2cecc67d3ace338d42f5d7bddd8","benches/tuples.rs":"07a663fced16df1e519110ba5c2dd9483955f2f21e8fc5171eea60d52bc715d0","cargo_embargo.json":"1c412d446965f40b1f2eb1d39291bb0e0732cc3b9c5fb36737f432d930e23c6e","examples/iris.data":"f952e90ad557c796d4834705174aaf71bb0a235dd09ca9407eff9b5b72a9f76f","examples/iris.rs":"6c3b8e2763ee4fdec1ecd7a4942b2d1bbf71d9658feb866b7420cb7512945c99","src/adaptors/coalesce.rs":"0a14e65588912e47c86c4cc43be4173992ac69958e73e4ca75406bf1a72787c1","src/adaptors/map.rs":"d0d5adb862ba83a9ff8d7bc2c2aa3e794a00639cb93a8355b4388c3d726d5c22","src/adaptors/mod.rs":"42b75e89940d8ebb8cf8c16032d56100a12c73bc567316666d4710feec3e71b9","src/adaptors/multi_product.rs":"833ccc206e0d6d0a6e5ec95835c6ef87b9c6ff0db510c3aaf9a5627cd5061feb","src/combinations.rs":"011a33f4b1e2ae57380800d5878c27a736fab0ed7f3b676d0be655cdad8d22b7","src/combinations_with_replacement.rs":"1dd4c50b9add8cba32f47571449cd03bb93db52013c9e8ffe9ca3acb851c01c8","src/concat_impl.rs":"4ab66a9a9800bc20d061a23d6a7bca235f038865850860da77311a0ddf852fc1","src/cons_tuples_impl.rs":"cbfaec74702bb6397b1005b8460b1ba2cfb7c52771b9009dd730a8bff45c09b9","src/diff.rs":"a66f924d8f57718a36e13b5aee2fe142fbb4e2d8ab974a2a83c9f6405278d7d0","src/duplicates_impl.rs":"dd3d4e04af8a85479658115105646159640c1a2b9d2216f251922c97da8b2f49","src/either_or_both.rs":"7c990e808fd7ae8b855a8383be7cc77e7aa3b5fe52044c4a662f2e47e94a9c68","src/exactly_one_err.rs":"558badd3aad0c38c4344a8e1469af442043304af51cde3fb9b41ad4c1581f349","src/extrema_set.rs":"dbbb20f4f293a74dad55b0c0286a38b6849ce918c9085274aafbc7fbde9de013","src/flatten_ok.rs":"0bd61298617834e035c68ac9e485bae7f9d89d0fa07b5a2a84818bbddc92abd4","src/format.rs":"4c5f963ea4a9d4da941c2209496596d895d73db968b1e41b09be39589eb36ac6","src/free.rs":"b6f64938e164559b0a7eb2696d2f460efae6373f4edde12ce2d247b9a67bc526","src/group_map.rs":"f2e97e58f03f36a01e31da3f912bfe1dcd4b456d5c6e05f540c4ec8344891b4b","src/groupbylazy.rs":"6b27e9c5c801e54946dec9e29c5d4bca290d7200a84d4c93a8e4af3ad8c9e3cf","src/grouping_map.rs":"116a100889201637b519cc33dcf20fbf0ce403a1008fddc5f7dc82e6fb34fcf5","src/impl_macros.rs":"29d480f310b17a1e8c68504d1be6024a3ccf9b4350a93b2cd6ea9b7be279ac6a","src/intersperse.rs":"481b6729e3f98cd62405f0c181aa2bb528508bd084bf3a3054d57c810f6e5c43","src/iter_index.rs":"1d68bf19eed6f975d06131638534e5a7b382f5b03aeb29e1107412bb08ce36a1","src/k_smallest.rs":"381043da6b7af62574c5c5034dd55bb1eb7074cc32b1df1340c921e67463b150","src/kmerge_impl.rs":"9670e60ba6ef3c6c51713ccd3eee46f1744393daaa4833ebbe52df7c6965f3b6","src/lazy_buffer.rs":"0bf7a4fe8a7d3d23783bf61e674bfd0ba03cca55cc1d0549145758611f1bdbed","src/lib.rs":"a2156c5f51ce3559c21f6f5eb63e7d0c7fae75cc9e93ec54d09f106198507b07","src/merge_join.rs":"b7ef9d7a3654279e808f32b7751c752f2db5fa35521affd0ed560fa5303e06e1","src/minmax.rs":"6c1eb4f9048153adb841adcbc33c78f237fbadd3b8705289a9fef104b4920693","src/multipeek_impl.rs":"502c545ab39b8db9ea5482b37226c02290aa5ba169b58a9c2427bb38a6f18628","src/next_array.rs":"fd5904fc07fb4b9e4c48a2771a3d300ffabe9db0680ebe96ea754d21e6d2876f","src/pad_tail.rs":"91babaf864d230a402d63c959f1d87a0ff6b6881bb582b213896f7fe5fa61d14","src/peek_nth.rs":"b293ccc75f50919d44653f4453cd27a28bd33f21448df57b1f87a72e38941417","src/peeking_take_while.rs":"ff66fc7a97a9101a04ec5f4a0e56b5754c69ce7b27f3132c5d376b30a1f0b19d","src/permutations.rs":"1cc667ff17fa7b3a9227f7a96cb861770228c3a1cabb6e0a515cd46ab8ef46c3","src/powerset.rs":"2a55d1100eda58c94a0843a639120df6d26b15318c659404654fcfea0275880e","src/process_results_impl.rs":"67c7cd60171053c21939252b71aad6879d6ad251a6ea3d50af1ffb0d0b4241bd","src/put_back_n_impl.rs":"da1b66a391cb0b1d5467fd6257e1dcc86b90a2c12ed03c0bd6cad73a71c3414d","src/rciter_impl.rs":"3aa04cdf4cbd96ddff4b210e90652e346177663b1993836b0f88215043ab228b","src/repeatn.rs":"4d5be3a1d97e91ee94fdc8d508ebe7fb815279db1b06d0e38ddf69e58475ed4a","src/size_hint.rs":"3ef07e7c3fa75bd1469de67452f8eb992a4d6c3e7839e79ff883bfb02ed65839","src/sources.rs":"b9d87801a0c1d39efb657a6f4fa33e95e71fab2230a8e2ae3d02bb686f42cb99","src/take_while_inclusive.rs":"ec3a8501a874422d8a7e6f556c949cc411180e43116ed7fa5f92954829eb56da","src/tee.rs":"9f97c5b4bb44ce437b51e92619274a488bd32eab8a9897c192e64dea9d5fbd9b","src/tuple_impl.rs":"0ece5c00544ffe88c61d89ad7bb997127c86764f17fe1a53e6a0c019ba185984","src/unique_impl.rs":"a99c3ae80697791d7b663b1d8a981fdcfe6e1ca67155c4ac87b4ad1d8fb6e18e","src/unziptuple.rs":"e26d5ab3e522604e84b5286ab0d7f608394677db3b9a69beeb4d557f5871f8d4","src/with_position.rs":"9cdd85aa92ccdadf88dfcd9643a69af6d3e053c5597ef3b00ee62fdc5bbc611d","src/zip_eq_impl.rs":"10ea8763cf64c9f20172c5b041de10108f5c366f6f91bd153d00a8755d01ed94","src/zip_longest.rs":"3f9003b0b7c050d53f48d2d36997ea45bb428fa74e5ba13d1df98205f7a51084","src/ziptuple.rs":"552ab217529b637f12b5e39702008f0ac91d2dc0b5d5819b839766d740c64c9e","tests/adaptors_no_collect.rs":"1aa9c1a1f6144f7b7a126c1802c2a791e1bc7d0a6330971ab5d51c1f6ab9e2d9","tests/flatten_ok.rs":"05d7773126bc41913bd6a5db6617c4cf90bb051f6ad5e7c1718694b6a0b4e0c1","tests/laziness.rs":"660e0df9a95e5021d954b57fec5ca18aeb71a6fd8c13637faf0eef023642c084","tests/macros_hygiene.rs":"b5a9053e2a9fdc6a3f958092846b9201ae4c94a84cf853aafbd4079c8cc9aa50","tests/merge_join.rs":"cf07e22a97cb496ae2a18ffbecaf797c9cc99f2a0de7958ebf0da86b21590cad","tests/peeking_take_while.rs":"8b0220981b437aa6756f2510ea4e25cf49a19a399a14a465dccff9ad08c48d55","tests/quick.rs":"8673d4fa3aac895fddfbe0d772a162cb193cbd2f05e84ed89a281f66b4cbae99","tests/specializations.rs":"a7af5260416febe23c4175b6c744bfcaccc0ccff5034a9758b2f89ba837b7a24","tests/test_core.rs":"ff3e834c8a3cf0d12b2e4e90b696fd5406a9ca588517f5c5630c8fe5fae5556c","tests/test_std.rs":"4c761b1379cb4a48a8f995d7525f59263fd1942c33a486b72555f80115199d68","tests/tuples.rs":"92df348f8816e17a3c02eeac420ae33e0a2c6ff994f8171aaecd3875863d2f0f","tests/zip.rs":"3767be9b0e8bdbcf1a41a6230a968d14263cb5fb6941af4ecf4bbe7782a7a0b2"}}
\ No newline at end of file
diff --git a/crates/itertools/.cargo-checksum.json b/crates/itertools/.cargo-checksum.json
index 38bbe13..13a4681 100644
--- a/crates/itertools/.cargo-checksum.json
+++ b/crates/itertools/.cargo-checksum.json
@@ -1 +1 @@
-{"files":{"CHANGELOG.md":"ceee4376468a3f7647f3bf4649e195a86873dd3091f23e3f992d248bd143fba2","CONTRIBUTING.md":"d5787d0fd4df15481e2e09a37234ac5dec22c007c890826991f633d890efa29e","Cargo.lock":"fd2c9ca8e299f51d7ed2a0f3760c393f03c544c817743ab7341c1f22b8c1d869","Cargo.toml":"49abb2101a0dd9cb137df206454b6620d04929a4975921fab6682ba834435620","LICENSE-APACHE":"a60eea817514531668d7e00765731449fe14d059d3249e0bc93b36de45f759f2","LICENSE-MIT":"7576269ea71f767b99297934c0b2367532690f8c4badc695edf8e04ab6a1e545","README.md":"fc812ab0d5756b62c2ae34f38365899204b53332d5e6a87a695b0fe15a466957","benches/bench1.rs":"d632c8b839d7b318d1cb7b81b9c62570c77dcdf0696b8ce3d52067c79c930f78","benches/combinations.rs":"5b3bd243336d6b6bdc111d66218f3f0a4ecdb10fb72e90db79959e3d8bb2cf6f","benches/combinations_with_replacement.rs":"11f29160652a2d90ce7ca4b1c339c4457888ab6867e2456ce1c62e3adf9be737","benches/fold_specialization.rs":"66ab13fd8576a662afb59ef72c5565f5c3d27f7f30a976450ee5a14958654fa2","benches/powerset.rs":"dc1fd729584147e5d8e4d19c6ca6f8706087d41c3c5beb7293d9ea43b4beab14","benches/specializations.rs":"d8320071a692147c1239881725079003be2f924f6124c3aa3bdf6a4596d66a66","benches/tree_reduce.rs":"fa4f22f042b76df89094ddf6e925ba42c4c3992f8195e719ed035f2e7cfa05bd","benches/tuple_combinations.rs":"16366158743307a0289fc1df423a3cec45009807d410a9fe9922d5b6f8b7d002","benches/tuples.rs":"5ab542aca40df4390de0ebf3819665df402d924a7dd6f4280e6ffc942bbd25c4","examples/iris.data":"596ffd580471ca4d4880f8e439c7281f3b50d8249a5960353cb200b1490f63a0","examples/iris.rs":"42c1b2fc148df52a050b013a57b577ad19911f1fe85b9525863df501979b5cd1","src/adaptors/coalesce.rs":"b57157c205ae077dd398740b61c7f49023aa80868abd8a071a6fe89ae6ecc9ad","src/adaptors/map.rs":"4952ee770cb54e98b2f649efd9c98f18951689358eb9b6bee10f139d056353ae","src/adaptors/mod.rs":"7064a1043baec815c02803d5043bd950e6a515f3a0247e44028ee080004dc225","src/adaptors/multi_product.rs":"ad501e8ae4e5089b9d2f2be1f9a4713da6a2103b14daa759e09918409f88e321","src/combinations.rs":"6c1cd55051eb59c595780b055ccabb07db72add134120dd8b2f5aa60c0f5fa6e","src/combinations_with_replacement.rs":"cad1885ca51e52a1dc324a0b06bd0d1d911f1dd58cf5d76bd9a9c78a09853b86","src/concat_impl.rs":"6094463eb57f77e115f6a3fe7f469992eef81c0c4caa9585b99a426d87f794fb","src/cons_tuples_impl.rs":"3ceee1ff0dbd4c3b43195a490b8f38b05de3a46e0fb691ba11fbbe1e7e3ad746","src/diff.rs":"046b3ac4a22036b9ec8741aba4e8f6729ae44bf14346b61c23192b88d9fc7c88","src/duplicates_impl.rs":"1be37249b4566edc8da611ed9766ec851a526e7513bd13d80fe97482dcfcf7f3","src/either_or_both.rs":"cac278666b5d3c1fd103d97d15ce4c40960ea459441aeae83c6502087fd2ad8d","src/exactly_one_err.rs":"90b6204551161d27394af72107765dbfe3b51a77f4770c2e506fa4938985a184","src/extrema_set.rs":"7e0d92ca1aafc1221e08d0297087b35373463d03228a0e65628cfd1734273e90","src/flatten_ok.rs":"62c18e5221a27949a00de49414306d6dfd601515817c1c8ae6189e3275756dd3","src/format.rs":"94675a6ac4500ec52bbf8463b2241b870fea8b5dd6b113accb8a00b2c1174871","src/free.rs":"6f3597a5ccf8a9b0606da7df6803f7368152ebcf7b7bcfd31b17fcff3a286139","src/group_map.rs":"c9da201137c6bb479b9308bfc38398b76950e39905f4ce8bc435c5318371522c","src/groupbylazy.rs":"5862629719258703aad47977ba1060f20fff15e962e18e6142758ebf6cd4a61c","src/grouping_map.rs":"8dac807a6cbf1893fdc147b4160000c452bfb5e533e1c774ed6bd3af91cf46da","src/impl_macros.rs":"97fc5f39574805e0c220aa462cf1ae7dcac5c1082d6ee5500e7d71c120db5f88","src/intersperse.rs":"55031819e985c3184275e254c9600ecbe01e9fb49f198039c5da82a87ea5b90e","src/iter_index.rs":"1b0ff8376a4ad855d44db8c662450c777db84e0f4997b53ca575c65b107bb83b","src/k_smallest.rs":"6a665742f6665e350a54ae3ff821252e7c599b57aee3239a03fa56a9d1930467","src/kmerge_impl.rs":"2e425d4189898566c5146e8f5bd258045c246f6babbe3ac5fef10ca08ae2efd2","src/lazy_buffer.rs":"a065f73c228f156bdf901824977ea9375f912823af4f9b05378e3f633d3b20e4","src/lib.rs":"75903dcd21573a8a77a205cfb8d335c60c2939771481c6431c29a0918d8dbfb0","src/merge_join.rs":"bb1fccddcc647fe21da1895a8808c06596d49900f5cf60a69a9c9141fc12af11","src/minmax.rs":"0ec34b172ca8efc4aacb96f3e5771bdc5e8ac882876ee0f59d698c3924717c48","src/multipeek_impl.rs":"79eef0be49ad66f15d41808e72c03976c4f7cff5838b69d17975d3ece266f3f8","src/pad_tail.rs":"e6bb5b086478600b0dbb8726cae8364bf83ab36d989ef467e1264eea43933b50","src/peek_nth.rs":"093f1a157b1c917f041af5244a5a46311affa2922126e36dc0ee2c501c79b58c","src/peeking_take_while.rs":"6967ba212f045145da7683a192471b2dcfcedf90d23922d70a5b7e2a1b36622e","src/permutations.rs":"b316084ee14e9e138d22f177367b3bfa24cb3e5e90ab20b9b00a9a23d653496f","src/powerset.rs":"7ab24fefc914b339dd92a6c8e639d0cad34479e09293b3346078856d6bc02d34","src/process_results_impl.rs":"a6f91aec53c56b042e15ecb8f8ca489c81e3ee92347dc9fa8352a5baac44a247","src/put_back_n_impl.rs":"5a58d7a31c03029f0726e4d42de3be869580cf76b73c6d1ef70dd40c240b03a0","src/rciter_impl.rs":"9a50cdc0106587be8ee49c2af5fcf84436b74d353c2846b401eb638c23b4733c","src/repeatn.rs":"dd9a5bf5a63ef9cc6ec5c8a6137c7ffba80f13568b6d001e189daaa29ffbaf39","src/size_hint.rs":"6022c2327ddc6df7e7b939eb60a93ee66ea9aa4d3aab49b9952e663ff4bff10b","src/sources.rs":"ef942af209ca1effcd28a95abedad8c45b659ae2a15b66c2158cb604f6e325f8","src/take_while_inclusive.rs":"1973a9f5322b3dae3b5ccded5912a08a8e2e975b9a5eac666192b118b230d305","src/tee.rs":"dad50ca162627cf0a67786f0993ef27d06cdefc14d412463e58c07824ef409d8","src/tuple_impl.rs":"0213261109e7c65746ccc22425d19141907bf7ea1e3dd4c40e9f278e6148e272","src/unique_impl.rs":"1efc280226f13ddd7dd5f7eedeec0093b704596652c942f3a0b2f8c90fa2e2f7","src/unziptuple.rs":"f3f6a2ee2658fa07db7592f2c344c2e3b1263a21fc75e1325f2be32c9dc1e750","src/with_position.rs":"9ca1eb195d04690b0c3a62a6c0eea349b8042e11c4ca4b80744f54103e1c7355","src/zip_eq_impl.rs":"4e0d38266c26982ea8b8d055994cb1298e93b7749caadbd7f25d2b6e0c8ce0d7","src/zip_longest.rs":"5572699564dd5717cc074b7733333ed238c2e9f3e6819d45e33e3a2dbda74478","src/ziptuple.rs":"d3a12221d39c8a5514574adb3ad2ccd1803d514b1cb09fbcd9253e3ddd628310","tests/adaptors_no_collect.rs":"7e6240878b1fc13b6384fdde0317d5d7ccca3e417b10a201ba61eb5255400fda","tests/flatten_ok.rs":"b7894874132918b8229c7150b2637511d8e3e14197d8eeb9382d46b2a514efa2","tests/laziness.rs":"89e6caec10da3d7aeadf9e30d5caf03cda36d07cee8415ff134b5b8e2a2cf144","tests/macros_hygiene.rs":"c9e9f0546a8c12ea52311c0eadd77d75c782d4e10ae9e74d410ea2861d526c66","tests/merge_join.rs":"5fb506b989f4a331d46cdec5775ea594656985134196099eaf8d3905bdddcdd5","tests/peeking_take_while.rs":"f834361c5520dda15eb9e9ebe87507c905462201412b21859d9f83dab91d0e0b","tests/quick.rs":"60b1ca6d820aa505545f20d6082fd08c1e0470b5326b711567ec1c93d07f9ced","tests/specializations.rs":"7c6a461850a2b4f783801ef23b2303ad985c58f2295c569001369b3c9d4c6e33","tests/test_core.rs":"482e077e0c5fe78ba0a8a126d8c0821162d820a21936855fadede713b1d4e70a","tests/test_std.rs":"f788573adc9ae19eb4bd2886c3967b273dd881982af407f6f5b6276434df0f00","tests/tuples.rs":"014e4da776174bfe923270e2a359cd9c95b372fce4b952b8138909d6e2c52762","tests/zip.rs":"2f68d531170fa2f106efafaf38ae854281d93305bf1b2b8d4bea833072518ecd"},"package":"413ee7dfc52ee1a4949ceeb7dbc8a33f2d6c088194d9f922fb8318faf1f01186"}
\ No newline at end of file
+{"files":{"CHANGELOG.md":"60ec9a1801e015e49f7fbb299b608ac730d5b1a3fb298e6cf7935c0695ddf7fe","CONTRIBUTING.md":"d5787d0fd4df15481e2e09a37234ac5dec22c007c890826991f633d890efa29e","Cargo.lock":"4422e732d4ce6f650afb53a1dcffb1e53c86dd066c3dcd66bc9620acd898b99e","Cargo.toml":"77735549383196a4156a2246dd1cd6742029b223679b3004531456d33562b0ce","LICENSE-APACHE":"a60eea817514531668d7e00765731449fe14d059d3249e0bc93b36de45f759f2","LICENSE-MIT":"7576269ea71f767b99297934c0b2367532690f8c4badc695edf8e04ab6a1e545","README.md":"7dba3f55ea54eff2606f8b9f005e369cf9885dd972cb481432fce00234ee7750","benches/bench1.rs":"d632c8b839d7b318d1cb7b81b9c62570c77dcdf0696b8ce3d52067c79c930f78","benches/combinations.rs":"5b3bd243336d6b6bdc111d66218f3f0a4ecdb10fb72e90db79959e3d8bb2cf6f","benches/combinations_with_replacement.rs":"11f29160652a2d90ce7ca4b1c339c4457888ab6867e2456ce1c62e3adf9be737","benches/fold_specialization.rs":"66ab13fd8576a662afb59ef72c5565f5c3d27f7f30a976450ee5a14958654fa2","benches/k_smallest.rs":"c1bb2aa597def7f7c282d1196f9d70be6d10e1acbae03279c05bc8065544bb8e","benches/powerset.rs":"dc1fd729584147e5d8e4d19c6ca6f8706087d41c3c5beb7293d9ea43b4beab14","benches/specializations.rs":"daa989877d83ccd58e8de529184d50905b3d6fa60a9eeae917f38bd570d72fa4","benches/tree_reduce.rs":"fa4f22f042b76df89094ddf6e925ba42c4c3992f8195e719ed035f2e7cfa05bd","benches/tuple_combinations.rs":"16366158743307a0289fc1df423a3cec45009807d410a9fe9922d5b6f8b7d002","benches/tuples.rs":"5ab542aca40df4390de0ebf3819665df402d924a7dd6f4280e6ffc942bbd25c4","examples/iris.data":"596ffd580471ca4d4880f8e439c7281f3b50d8249a5960353cb200b1490f63a0","examples/iris.rs":"42c1b2fc148df52a050b013a57b577ad19911f1fe85b9525863df501979b5cd1","src/adaptors/coalesce.rs":"b57157c205ae077dd398740b61c7f49023aa80868abd8a071a6fe89ae6ecc9ad","src/adaptors/map.rs":"4952ee770cb54e98b2f649efd9c98f18951689358eb9b6bee10f139d056353ae","src/adaptors/mod.rs":"1e0cf7409c7291a923cf87f1c6d27cc57bd9f71ca52f7dd08a429aa994daa6ce","src/adaptors/multi_product.rs":"ad501e8ae4e5089b9d2f2be1f9a4713da6a2103b14daa759e09918409f88e321","src/combinations.rs":"9c4490bc4c7488fe9a8dba656a30493d90abb33006f7abbe3e266c237ffc986b","src/combinations_with_replacement.rs":"c7d6b7a122057e9aab075b2de41440ccd2973a6985fba75c2e93af13de55ef90","src/concat_impl.rs":"d61c00d43eca1193f135e25d3b6afd840c02ef1c573c29b264c47ee3429a45e8","src/cons_tuples_impl.rs":"7f46da33168107860b2b15d05d8edfe618e41bbc66ff0e16baf82d7373c4356d","src/diff.rs":"6e5ba3705a3a076d4fc360594014c90f1dfc597e61e8a629f96efa050e2433f5","src/duplicates_impl.rs":"1be37249b4566edc8da611ed9766ec851a526e7513bd13d80fe97482dcfcf7f3","src/either_or_both.rs":"cac278666b5d3c1fd103d97d15ce4c40960ea459441aeae83c6502087fd2ad8d","src/exactly_one_err.rs":"90b6204551161d27394af72107765dbfe3b51a77f4770c2e506fa4938985a184","src/extrema_set.rs":"11de200d853941716e9aa9a9b520b006704827c3c43a0c5f067906b0941e51d1","src/flatten_ok.rs":"62c18e5221a27949a00de49414306d6dfd601515817c1c8ae6189e3275756dd3","src/format.rs":"3ae6414043e0040f7358028c560437ea49afdbb2416df138a2410169e2619589","src/free.rs":"00ec21acee2ae2b30bf99e62472f9684c0a1719fbafc8dd2e4195ea8377c5b5d","src/group_map.rs":"c9da201137c6bb479b9308bfc38398b76950e39905f4ce8bc435c5318371522c","src/groupbylazy.rs":"5862629719258703aad47977ba1060f20fff15e962e18e6142758ebf6cd4a61c","src/grouping_map.rs":"3896c46ba4bd8ea886e5344a245658235626a104758d5ccecf223544a9ba471b","src/impl_macros.rs":"97fc5f39574805e0c220aa462cf1ae7dcac5c1082d6ee5500e7d71c120db5f88","src/intersperse.rs":"55031819e985c3184275e254c9600ecbe01e9fb49f198039c5da82a87ea5b90e","src/iter_index.rs":"1b0ff8376a4ad855d44db8c662450c777db84e0f4997b53ca575c65b107bb83b","src/k_smallest.rs":"a6840980e4c1aedd6987f93c904d362aa09a101537e447121fff58bb2473638d","src/kmerge_impl.rs":"3f999d55d7def904f71f2ca88b36707461f7f23b32966e0ccaf31d808886d843","src/lazy_buffer.rs":"baa01490fceb5a8dd7bd9c2634e19ce8a785bd1df352a9dd77d1344e3e0f8892","src/lib.rs":"e7f144351cca5018dc12270b4c33f0562afddb92452acfa85153cb276aebd6e9","src/merge_join.rs":"f2f257e63c84ed772b235229cc787ebe9ae009d7c80ed2087002a6b62c5e2133","src/minmax.rs":"0ec34b172ca8efc4aacb96f3e5771bdc5e8ac882876ee0f59d698c3924717c48","src/multipeek_impl.rs":"79eef0be49ad66f15d41808e72c03976c4f7cff5838b69d17975d3ece266f3f8","src/next_array.rs":"295924058891c08f9fe6313a1d9dd0042dcf60f0a514c6a6e009a1396d804fc9","src/pad_tail.rs":"e6bb5b086478600b0dbb8726cae8364bf83ab36d989ef467e1264eea43933b50","src/peek_nth.rs":"093f1a157b1c917f041af5244a5a46311affa2922126e36dc0ee2c501c79b58c","src/peeking_take_while.rs":"075ce13475c84e2cfdfaf1a7a0d0695332102c82a61914ed4c00a7d2634b1d34","src/permutations.rs":"b316084ee14e9e138d22f177367b3bfa24cb3e5e90ab20b9b00a9a23d653496f","src/powerset.rs":"7ab24fefc914b339dd92a6c8e639d0cad34479e09293b3346078856d6bc02d34","src/process_results_impl.rs":"6b5d82447eef4e87fef7b2a8e56b906ac7b000886a468ce421252f34ec86e371","src/put_back_n_impl.rs":"5a58d7a31c03029f0726e4d42de3be869580cf76b73c6d1ef70dd40c240b03a0","src/rciter_impl.rs":"081fd206ba4a601bd65e2f3b8d7c95e3e4a3564beb7c98944bd2e7986959c230","src/repeatn.rs":"dd9a5bf5a63ef9cc6ec5c8a6137c7ffba80f13568b6d001e189daaa29ffbaf39","src/size_hint.rs":"6022c2327ddc6df7e7b939eb60a93ee66ea9aa4d3aab49b9952e663ff4bff10b","src/sources.rs":"ef942af209ca1effcd28a95abedad8c45b659ae2a15b66c2158cb604f6e325f8","src/take_while_inclusive.rs":"1973a9f5322b3dae3b5ccded5912a08a8e2e975b9a5eac666192b118b230d305","src/tee.rs":"dad50ca162627cf0a67786f0993ef27d06cdefc14d412463e58c07824ef409d8","src/tuple_impl.rs":"0213261109e7c65746ccc22425d19141907bf7ea1e3dd4c40e9f278e6148e272","src/unique_impl.rs":"1efc280226f13ddd7dd5f7eedeec0093b704596652c942f3a0b2f8c90fa2e2f7","src/unziptuple.rs":"f3f6a2ee2658fa07db7592f2c344c2e3b1263a21fc75e1325f2be32c9dc1e750","src/with_position.rs":"9ca1eb195d04690b0c3a62a6c0eea349b8042e11c4ca4b80744f54103e1c7355","src/zip_eq_impl.rs":"3282b177e7dece5d3fbdc9b03563f209589a399ea45e70abf23ccca3b5512ac7","src/zip_longest.rs":"5572699564dd5717cc074b7733333ed238c2e9f3e6819d45e33e3a2dbda74478","src/ziptuple.rs":"d3a12221d39c8a5514574adb3ad2ccd1803d514b1cb09fbcd9253e3ddd628310","tests/adaptors_no_collect.rs":"7e6240878b1fc13b6384fdde0317d5d7ccca3e417b10a201ba61eb5255400fda","tests/flatten_ok.rs":"b7894874132918b8229c7150b2637511d8e3e14197d8eeb9382d46b2a514efa2","tests/laziness.rs":"89e6caec10da3d7aeadf9e30d5caf03cda36d07cee8415ff134b5b8e2a2cf144","tests/macros_hygiene.rs":"c2d517badf593c0ba9b70e987a6f8482ed8997547b2e88bbec70babd9b677aa2","tests/merge_join.rs":"5fb506b989f4a331d46cdec5775ea594656985134196099eaf8d3905bdddcdd5","tests/peeking_take_while.rs":"f834361c5520dda15eb9e9ebe87507c905462201412b21859d9f83dab91d0e0b","tests/quick.rs":"d463bf8712b32742c93bc2cf3993031aeaba1f5b0505ca0ecd347313c3da0582","tests/specializations.rs":"fefbdac83bb774186882e3d31be619c9ce1dbfc4191a99ed2ac90aa764737a8f","tests/test_core.rs":"9bbc6772e97a60d93d4021c184b9e4de1c0440a1c48b991a92edc189699fd20d","tests/test_std.rs":"b0e56deefe309b9c11804bd069c744b5caea7960cd4b68244531f6edf38b9741","tests/tuples.rs":"014e4da776174bfe923270e2a359cd9c95b372fce4b952b8138909d6e2c52762","tests/zip.rs":"457e34761d9bf2943a43abd9020d2b1a4492ebff9e4d94efe4c730652fbf62af"},"package":"2b192c782037fadd9cfa75548310488aabdbf3d2da73885b31bd0abd03351285"}
\ No newline at end of file
diff --git a/crates/itertools/Android.bp b/crates/itertools/Android.bp
index 18776c3..9e1cffa 100644
--- a/crates/itertools/Android.bp
+++ b/crates/itertools/Android.bp
@@ -18,7 +18,7 @@
host_supported: true,
crate_name: "itertools",
cargo_env_compat: true,
- cargo_pkg_version: "0.13.0",
+ cargo_pkg_version: "0.14.0",
crate_root: "src/lib.rs",
edition: "2018",
features: [
diff --git a/crates/itertools/CHANGELOG.md b/crates/itertools/CHANGELOG.md
index de9564c..6b08f68 100644
--- a/crates/itertools/CHANGELOG.md
+++ b/crates/itertools/CHANGELOG.md
@@ -1,5 +1,36 @@
# Changelog
+## 0.14.0
+
+### Breaking
+- Increased MSRV to 1.63.0 (#960)
+- Removed generic parameter from `cons_tuples` (#988)
+
+### Added
+- Added `array_combinations` (#991)
+- Added `k_smallest_relaxed` and variants (#925)
+- Added `next_array` and `collect_array` (#560)
+- Implemented `DoubleEndedIterator` for `FilterOk` (#948)
+- Implemented `DoubleEndedIterator` for `FilterMapOk` (#950)
+
+### Changed
+- Allow `Q: ?Sized` in `Itertools::contains` (#971)
+- Improved hygiene of `chain!` (#943)
+- Improved `into_group_map_by` documentation (#1000)
+- Improved `tree_reduce` documentation (#955)
+- Improved discoverability of `merge_join_by` (#966)
+- Improved discoverability of `take_while_inclusive` (#972)
+- Improved documentation of `find_or_last` and `find_or_first` (#984)
+- Prevented exponentially large type sizes in `tuple_combinations` (#945)
+- Added `track_caller` attr for `asser_equal` (#976)
+
+### Notable Internal Changes
+- Fixed clippy lints (#956, #987, #1008)
+- Addressed warnings within doctests (#964)
+- CI: Run most tests with miri (#961)
+- CI: Speed up "cargo-semver-checks" action (#938)
+- Changed an instance of `default_features` in `Cargo.toml` to `default-features` (#985)
+
## 0.13.0
### Breaking
diff --git a/crates/itertools/Cargo.lock b/crates/itertools/Cargo.lock
index d2183c2..fbf369b 100644
--- a/crates/itertools/Cargo.lock
+++ b/crates/itertools/Cargo.lock
@@ -236,7 +236,7 @@
[[package]]
name = "itertools"
-version = "0.13.0"
+version = "0.14.0"
dependencies = [
"criterion",
"either",
diff --git a/crates/itertools/Cargo.toml b/crates/itertools/Cargo.toml
index 21896fe..96f9597 100644
--- a/crates/itertools/Cargo.toml
+++ b/crates/itertools/Cargo.toml
@@ -11,10 +11,16 @@
[package]
edition = "2018"
-rust-version = "1.43.1"
+rust-version = "1.63.0"
name = "itertools"
-version = "0.13.0"
+version = "0.14.0"
authors = ["bluss"]
+build = false
+autolib = false
+autobins = false
+autoexamples = false
+autotests = false
+autobenches = false
description = "Extra iterator adaptors, iterator methods, free functions, and macros."
documentation = "https://docs.rs/itertools/"
readme = "README.md"
@@ -33,47 +39,120 @@
license = "MIT OR Apache-2.0"
repository = "https://github.com/rust-itertools/itertools"
-[profile.bench]
-debug = 2
+[features]
+default = ["use_std"]
+use_alloc = []
+use_std = [
+ "use_alloc",
+ "either/use_std",
+]
[lib]
+name = "itertools"
+path = "src/lib.rs"
test = false
bench = false
-[[bench]]
-name = "tuple_combinations"
-harness = false
+[[example]]
+name = "iris"
+path = "examples/iris.rs"
-[[bench]]
+[[test]]
+name = "adaptors_no_collect"
+path = "tests/adaptors_no_collect.rs"
+
+[[test]]
+name = "flatten_ok"
+path = "tests/flatten_ok.rs"
+
+[[test]]
+name = "laziness"
+path = "tests/laziness.rs"
+
+[[test]]
+name = "macros_hygiene"
+path = "tests/macros_hygiene.rs"
+
+[[test]]
+name = "merge_join"
+path = "tests/merge_join.rs"
+
+[[test]]
+name = "peeking_take_while"
+path = "tests/peeking_take_while.rs"
+
+[[test]]
+name = "quick"
+path = "tests/quick.rs"
+
+[[test]]
+name = "specializations"
+path = "tests/specializations.rs"
+
+[[test]]
+name = "test_core"
+path = "tests/test_core.rs"
+
+[[test]]
+name = "test_std"
+path = "tests/test_std.rs"
+
+[[test]]
name = "tuples"
-harness = false
+path = "tests/tuples.rs"
-[[bench]]
-name = "fold_specialization"
-harness = false
-
-[[bench]]
-name = "combinations_with_replacement"
-harness = false
-
-[[bench]]
-name = "tree_reduce"
-harness = false
+[[test]]
+name = "zip"
+path = "tests/zip.rs"
[[bench]]
name = "bench1"
+path = "benches/bench1.rs"
harness = false
[[bench]]
name = "combinations"
+path = "benches/combinations.rs"
+harness = false
+
+[[bench]]
+name = "combinations_with_replacement"
+path = "benches/combinations_with_replacement.rs"
+harness = false
+
+[[bench]]
+name = "fold_specialization"
+path = "benches/fold_specialization.rs"
+harness = false
+
+[[bench]]
+name = "k_smallest"
+path = "benches/k_smallest.rs"
harness = false
[[bench]]
name = "powerset"
+path = "benches/powerset.rs"
harness = false
[[bench]]
name = "specializations"
+path = "benches/specializations.rs"
+harness = false
+
+[[bench]]
+name = "tree_reduce"
+path = "benches/tree_reduce.rs"
+harness = false
+
+[[bench]]
+name = "tuple_combinations"
+path = "benches/tuple_combinations.rs"
+harness = false
+
+[[bench]]
+name = "tuples"
+path = "benches/tuples.rs"
harness = false
[dependencies.either]
@@ -82,6 +161,7 @@
[dev-dependencies.criterion]
version = "0.4.0"
+features = ["html_reports"]
[dev-dependencies.paste]
version = "1.0.0"
@@ -91,15 +171,10 @@
[dev-dependencies.quickcheck]
version = "0.9"
-default_features = false
+default-features = false
[dev-dependencies.rand]
version = "0.7"
-[features]
-default = ["use_std"]
-use_alloc = []
-use_std = [
- "use_alloc",
- "either/use_std",
-]
+[profile.bench]
+debug = 2
diff --git a/crates/itertools/METADATA b/crates/itertools/METADATA
index 6bb1771..775971a 100644
--- a/crates/itertools/METADATA
+++ b/crates/itertools/METADATA
@@ -1,17 +1,17 @@
name: "itertools"
description: "Extra iterator adaptors, iterator methods, free functions, and macros."
third_party {
- version: "0.13.0"
+ version: "0.14.0"
license_type: NOTICE
last_upgrade_date {
- year: 2024
- month: 9
- day: 4
+ year: 2025
+ month: 1
+ day: 14
}
homepage: "https://crates.io/crates/itertools"
identifier {
type: "Archive"
- value: "https://static.crates.io/crates/itertools/itertools-0.13.0.crate"
- version: "0.13.0"
+ value: "https://static.crates.io/crates/itertools/itertools-0.14.0.crate"
+ version: "0.14.0"
}
}
diff --git a/crates/itertools/README.md b/crates/itertools/README.md
index 982ef5d..46acc3f 100644
--- a/crates/itertools/README.md
+++ b/crates/itertools/README.md
@@ -8,7 +8,7 @@
```toml
[dependencies]
-itertools = "0.13.0"
+itertools = "0.14.0"
```
How to use in your crate:
diff --git a/crates/itertools/benches/k_smallest.rs b/crates/itertools/benches/k_smallest.rs
new file mode 100644
index 0000000..509ed7f
--- /dev/null
+++ b/crates/itertools/benches/k_smallest.rs
@@ -0,0 +1,61 @@
+use criterion::{black_box, criterion_group, criterion_main, Bencher, BenchmarkId, Criterion};
+use itertools::Itertools;
+use rand::{rngs::StdRng, seq::SliceRandom, SeedableRng};
+
+fn strict(b: &mut Bencher, (k, vals): &(usize, &Vec<usize>)) {
+ b.iter(|| black_box(vals.iter()).k_smallest(*k))
+}
+
+fn relaxed(b: &mut Bencher, (k, vals): &(usize, &Vec<usize>)) {
+ b.iter(|| black_box(vals.iter()).k_smallest_relaxed(*k))
+}
+
+fn ascending(n: usize) -> Vec<usize> {
+ (0..n).collect()
+}
+
+fn random(n: usize) -> Vec<usize> {
+ let mut vals = (0..n).collect_vec();
+ vals.shuffle(&mut StdRng::seed_from_u64(42));
+ vals
+}
+
+fn descending(n: usize) -> Vec<usize> {
+ (0..n).rev().collect()
+}
+
+fn k_smallest(c: &mut Criterion, order: &str, vals: fn(usize) -> Vec<usize>) {
+ let mut g = c.benchmark_group(format!("k-smallest/{order}"));
+
+ for log_n in 20..23 {
+ let n = 1 << log_n;
+
+ let vals = vals(n);
+
+ for log_k in 7..10 {
+ let k = 1 << log_k;
+
+ let params = format!("{log_n}/{log_k}");
+ let input = (k, &vals);
+ g.bench_with_input(BenchmarkId::new("strict", ¶ms), &input, strict);
+ g.bench_with_input(BenchmarkId::new("relaxed", ¶ms), &input, relaxed);
+ }
+ }
+
+ g.finish()
+}
+
+fn k_smallest_asc(c: &mut Criterion) {
+ k_smallest(c, "asc", ascending);
+}
+
+fn k_smallest_rand(c: &mut Criterion) {
+ k_smallest(c, "rand", random);
+}
+
+fn k_smallest_desc(c: &mut Criterion) {
+ k_smallest(c, "desc", descending);
+}
+
+criterion_group!(benches, k_smallest_asc, k_smallest_rand, k_smallest_desc);
+criterion_main!(benches);
diff --git a/crates/itertools/benches/specializations.rs b/crates/itertools/benches/specializations.rs
index 18039fc..e70323f 100644
--- a/crates/itertools/benches/specializations.rs
+++ b/crates/itertools/benches/specializations.rs
@@ -1,4 +1,4 @@
-#![allow(unstable_name_collisions, clippy::incompatible_msrv)]
+#![allow(unstable_name_collisions)]
use criterion::black_box;
use criterion::BenchmarkId;
@@ -639,6 +639,7 @@
v.iter().copied().map_ok(|x| x + 1)
}
filter_ok {
+ DoubleEndedIterator
{
let v = black_box((0_u32..1024)
.map(|x| if x % 2 == 1 { Err(x) } else { Ok(x) })
@@ -647,6 +648,7 @@
v.iter().copied().filter_ok(|x| x % 3 == 0)
}
filter_map_ok {
+ DoubleEndedIterator
{
let v = black_box((0_u32..1024)
.map(|x| if x % 2 == 1 { Err(x) } else { Ok(x) })
diff --git a/crates/itertools/src/adaptors/mod.rs b/crates/itertools/src/adaptors/mod.rs
index 52e36c4..77192f2 100644
--- a/crates/itertools/src/adaptors/mod.rs
+++ b/crates/itertools/src/adaptors/mod.rs
@@ -515,7 +515,7 @@
f: F,
}
-impl<'a, I, F> fmt::Debug for TakeWhileRef<'a, I, F>
+impl<I, F> fmt::Debug for TakeWhileRef<'_, I, F>
where
I: Iterator + fmt::Debug,
{
@@ -530,7 +530,7 @@
TakeWhileRef { iter, f }
}
-impl<'a, I, F> Iterator for TakeWhileRef<'a, I, F>
+impl<I, F> Iterator for TakeWhileRef<'_, I, F>
where
I: Iterator + Clone,
F: FnMut(&I::Item) -> bool,
@@ -773,16 +773,28 @@
where
F: FnMut(B, Self::Item) -> B,
{
+ // We outline this closure to prevent it from unnecessarily
+ // capturing the type parameters `I`, `B`, and `F`. Not doing
+ // so ended up causing exponentially big types during MIR
+ // inlining when building itertools with optimizations enabled.
+ //
+ // This change causes a small improvement to compile times in
+ // release mode.
+ type CurrTuple<A> = (A, $(ignore_ident!($X, A)),*);
+ type PrevTuple<A> = ($(ignore_ident!($X, A),)*);
+ fn map_fn<A: Clone>(z: &A) -> impl FnMut(PrevTuple<A>) -> CurrTuple<A> + '_ {
+ move |($($X,)*)| (z.clone(), $($X),*)
+ }
let Self { c, item, mut iter } = self;
if let Some(z) = item.as_ref() {
init = c
- .map(|($($X,)*)| (z.clone(), $($X),*))
+ .map(map_fn::<A>(z))
.fold(init, &mut f);
}
while let Some(z) = iter.next() {
let c: $P<I> = iter.clone().into();
init = c
- .map(|($($X,)*)| (z.clone(), $($X),*))
+ .map(map_fn::<A>(&z))
.fold(init, &mut f);
}
init
@@ -924,6 +936,30 @@
}
}
+impl<I, F, T, E> DoubleEndedIterator for FilterOk<I, F>
+where
+ I: DoubleEndedIterator<Item = Result<T, E>>,
+ F: FnMut(&T) -> bool,
+{
+ fn next_back(&mut self) -> Option<Self::Item> {
+ let f = &mut self.f;
+ self.iter.rfind(|res| match res {
+ Ok(t) => f(t),
+ _ => true,
+ })
+ }
+
+ fn rfold<Acc, Fold>(self, init: Acc, fold_f: Fold) -> Acc
+ where
+ Fold: FnMut(Acc, Self::Item) -> Acc,
+ {
+ let mut f = self.f;
+ self.iter
+ .filter(|v| v.as_ref().map(&mut f).unwrap_or(true))
+ .rfold(init, fold_f)
+ }
+}
+
impl<I, F, T, E> FusedIterator for FilterOk<I, F>
where
I: FusedIterator<Item = Result<T, E>>,
@@ -1005,6 +1041,30 @@
}
}
+impl<I, F, T, U, E> DoubleEndedIterator for FilterMapOk<I, F>
+where
+ I: DoubleEndedIterator<Item = Result<T, E>>,
+ F: FnMut(T) -> Option<U>,
+{
+ fn next_back(&mut self) -> Option<Self::Item> {
+ let f = &mut self.f;
+ self.iter.by_ref().rev().find_map(|res| match res {
+ Ok(t) => f(t).map(Ok),
+ Err(e) => Some(Err(e)),
+ })
+ }
+
+ fn rfold<Acc, Fold>(self, init: Acc, fold_f: Fold) -> Acc
+ where
+ Fold: FnMut(Acc, Self::Item) -> Acc,
+ {
+ let mut f = self.f;
+ self.iter
+ .filter_map(|v| transpose_result(v.map(&mut f)))
+ .rfold(init, fold_f)
+ }
+}
+
impl<I, F, T, U, E> FusedIterator for FilterMapOk<I, F>
where
I: FusedIterator<Item = Result<T, E>>,
@@ -1048,9 +1108,7 @@
fn next(&mut self) -> Option<Self::Item> {
let f = &mut self.f;
- // TODO: once MSRV >= 1.62, use `then_some`.
- self.iter
- .find_map(|(count, val)| if f(val) { Some(count) } else { None })
+ self.iter.find_map(|(count, val)| f(val).then_some(count))
}
fn size_hint(&self) -> (usize, Option<usize>) {
@@ -1078,11 +1136,10 @@
{
fn next_back(&mut self) -> Option<Self::Item> {
let f = &mut self.f;
- // TODO: once MSRV >= 1.62, use `then_some`.
self.iter
.by_ref()
.rev()
- .find_map(|(count, val)| if f(val) { Some(count) } else { None })
+ .find_map(|(count, val)| f(val).then_some(count))
}
fn rfold<B, G>(self, init: B, mut func: G) -> B
diff --git a/crates/itertools/src/combinations.rs b/crates/itertools/src/combinations.rs
index 6bb2f3e..54a0275 100644
--- a/crates/itertools/src/combinations.rs
+++ b/crates/itertools/src/combinations.rs
@@ -1,3 +1,5 @@
+use core::array;
+use core::borrow::BorrowMut;
use std::fmt;
use std::iter::FusedIterator;
@@ -6,45 +8,101 @@
use crate::adaptors::checked_binomial;
+/// Iterator for `Vec` valued combinations returned by [`.combinations()`](crate::Itertools::combinations)
+pub type Combinations<I> = CombinationsGeneric<I, Vec<usize>>;
+/// Iterator for const generic combinations returned by [`.array_combinations()`](crate::Itertools::array_combinations)
+pub type ArrayCombinations<I, const K: usize> = CombinationsGeneric<I, [usize; K]>;
+
+/// Create a new `Combinations` from a clonable iterator.
+pub fn combinations<I: Iterator>(iter: I, k: usize) -> Combinations<I>
+where
+ I::Item: Clone,
+{
+ Combinations::new(iter, (0..k).collect())
+}
+
+/// Create a new `ArrayCombinations` from a clonable iterator.
+pub fn array_combinations<I: Iterator, const K: usize>(iter: I) -> ArrayCombinations<I, K>
+where
+ I::Item: Clone,
+{
+ ArrayCombinations::new(iter, array::from_fn(|i| i))
+}
+
/// An iterator to iterate through all the `k`-length combinations in an iterator.
///
-/// See [`.combinations()`](crate::Itertools::combinations) for more information.
+/// See [`.combinations()`](crate::Itertools::combinations) and [`.array_combinations()`](crate::Itertools::array_combinations) for more information.
#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
-pub struct Combinations<I: Iterator> {
- indices: Vec<usize>,
+pub struct CombinationsGeneric<I: Iterator, Idx> {
+ indices: Idx,
pool: LazyBuffer<I>,
first: bool,
}
-impl<I> Clone for Combinations<I>
+/// A type holding indices of elements in a pool or buffer of items from an inner iterator
+/// and used to pick out different combinations in a generic way.
+pub trait PoolIndex<T>: BorrowMut<[usize]> {
+ type Item;
+
+ fn extract_item<I: Iterator<Item = T>>(&self, pool: &LazyBuffer<I>) -> Self::Item
+ where
+ T: Clone;
+
+ fn len(&self) -> usize {
+ self.borrow().len()
+ }
+}
+
+impl<T> PoolIndex<T> for Vec<usize> {
+ type Item = Vec<T>;
+
+ fn extract_item<I: Iterator<Item = T>>(&self, pool: &LazyBuffer<I>) -> Vec<T>
+ where
+ T: Clone,
+ {
+ pool.get_at(self)
+ }
+}
+
+impl<T, const K: usize> PoolIndex<T> for [usize; K] {
+ type Item = [T; K];
+
+ fn extract_item<I: Iterator<Item = T>>(&self, pool: &LazyBuffer<I>) -> [T; K]
+ where
+ T: Clone,
+ {
+ pool.get_array(*self)
+ }
+}
+
+impl<I, Idx> Clone for CombinationsGeneric<I, Idx>
where
- I: Clone + Iterator,
+ I: Iterator + Clone,
I::Item: Clone,
+ Idx: Clone,
{
clone_fields!(indices, pool, first);
}
-impl<I> fmt::Debug for Combinations<I>
+impl<I, Idx> fmt::Debug for CombinationsGeneric<I, Idx>
where
I: Iterator + fmt::Debug,
I::Item: fmt::Debug,
+ Idx: fmt::Debug,
{
debug_fmt_fields!(Combinations, indices, pool, first);
}
-/// Create a new `Combinations` from a clonable iterator.
-pub fn combinations<I>(iter: I, k: usize) -> Combinations<I>
-where
- I: Iterator,
-{
- Combinations {
- indices: (0..k).collect(),
- pool: LazyBuffer::new(iter),
- first: true,
+impl<I: Iterator, Idx: PoolIndex<I::Item>> CombinationsGeneric<I, Idx> {
+ /// Constructor with arguments the inner iterator and the initial state for the indices.
+ fn new(iter: I, indices: Idx) -> Self {
+ Self {
+ indices,
+ pool: LazyBuffer::new(iter),
+ first: true,
+ }
}
-}
-impl<I: Iterator> Combinations<I> {
/// Returns the length of a combination produced by this iterator.
#[inline]
pub fn k(&self) -> usize {
@@ -64,27 +122,7 @@
&self.pool
}
- /// Resets this `Combinations` back to an initial state for combinations of length
- /// `k` over the same pool data source. If `k` is larger than the current length
- /// of the data pool an attempt is made to prefill the pool so that it holds `k`
- /// elements.
- pub(crate) fn reset(&mut self, k: usize) {
- self.first = true;
-
- if k < self.indices.len() {
- self.indices.truncate(k);
- for i in 0..k {
- self.indices[i] = i;
- }
- } else {
- for i in 0..self.indices.len() {
- self.indices[i] = i;
- }
- self.indices.extend(self.indices.len()..k);
- self.pool.prefill(k);
- }
- }
-
+ /// Return the length of the inner iterator and the count of remaining combinations.
pub(crate) fn n_and_count(self) -> (usize, usize) {
let Self {
indices,
@@ -92,7 +130,7 @@
first,
} = self;
let n = pool.count();
- (n, remaining_for(n, first, &indices).unwrap())
+ (n, remaining_for(n, first, indices.borrow()).unwrap())
}
/// Initialises the iterator by filling a buffer with elements from the
@@ -113,19 +151,21 @@
///
/// Returns true if we've run out of combinations, false otherwise.
fn increment_indices(&mut self) -> bool {
- if self.indices.is_empty() {
+ // Borrow once instead of noise each time it's indexed
+ let indices = self.indices.borrow_mut();
+
+ if indices.is_empty() {
return true; // Done
}
-
// Scan from the end, looking for an index to increment
- let mut i: usize = self.indices.len() - 1;
+ let mut i: usize = indices.len() - 1;
// Check if we need to consume more from the iterator
- if self.indices[i] == self.pool.len() - 1 {
+ if indices[i] == self.pool.len() - 1 {
self.pool.get_next(); // may change pool size
}
- while self.indices[i] == i + self.pool.len() - self.indices.len() {
+ while indices[i] == i + self.pool.len() - indices.len() {
if i > 0 {
i -= 1;
} else {
@@ -135,11 +175,10 @@
}
// Increment index, and reset the ones to its right
- self.indices[i] += 1;
- for j in i + 1..self.indices.len() {
- self.indices[j] = self.indices[j - 1] + 1;
+ indices[i] += 1;
+ for j in i + 1..indices.len() {
+ indices[j] = indices[j - 1] + 1;
}
-
// If we've made it this far, we haven't run out of combos
false
}
@@ -147,6 +186,7 @@
/// Returns the n-th item or the number of successful steps.
pub(crate) fn try_nth(&mut self, n: usize) -> Result<<Self as Iterator>::Item, usize>
where
+ I: Iterator,
I::Item: Clone,
{
let done = if self.first {
@@ -162,16 +202,17 @@
return Err(i + 1);
}
}
- Ok(self.pool.get_at(&self.indices))
+ Ok(self.indices.extract_item(&self.pool))
}
}
-impl<I> Iterator for Combinations<I>
+impl<I, Idx> Iterator for CombinationsGeneric<I, Idx>
where
I: Iterator,
I::Item: Clone,
+ Idx: PoolIndex<I::Item>,
{
- type Item = Vec<I::Item>;
+ type Item = Idx::Item;
fn next(&mut self) -> Option<Self::Item> {
let done = if self.first {
self.init()
@@ -183,7 +224,7 @@
return None;
}
- Some(self.pool.get_at(&self.indices))
+ Some(self.indices.extract_item(&self.pool))
}
fn nth(&mut self, n: usize) -> Option<Self::Item> {
@@ -192,8 +233,8 @@
fn size_hint(&self) -> (usize, Option<usize>) {
let (mut low, mut upp) = self.pool.size_hint();
- low = remaining_for(low, self.first, &self.indices).unwrap_or(usize::MAX);
- upp = upp.and_then(|upp| remaining_for(upp, self.first, &self.indices));
+ low = remaining_for(low, self.first, self.indices.borrow()).unwrap_or(usize::MAX);
+ upp = upp.and_then(|upp| remaining_for(upp, self.first, self.indices.borrow()));
(low, upp)
}
@@ -203,13 +244,37 @@
}
}
-impl<I> FusedIterator for Combinations<I>
+impl<I, Idx> FusedIterator for CombinationsGeneric<I, Idx>
where
I: Iterator,
I::Item: Clone,
+ Idx: PoolIndex<I::Item>,
{
}
+impl<I: Iterator> Combinations<I> {
+ /// Resets this `Combinations` back to an initial state for combinations of length
+ /// `k` over the same pool data source. If `k` is larger than the current length
+ /// of the data pool an attempt is made to prefill the pool so that it holds `k`
+ /// elements.
+ pub(crate) fn reset(&mut self, k: usize) {
+ self.first = true;
+
+ if k < self.indices.len() {
+ self.indices.truncate(k);
+ for i in 0..k {
+ self.indices[i] = i;
+ }
+ } else {
+ for i in 0..self.indices.len() {
+ self.indices[i] = i;
+ }
+ self.indices.extend(self.indices.len()..k);
+ self.pool.prefill(k);
+ }
+ }
+}
+
/// For a given size `n`, return the count of remaining combinations or None if it would overflow.
fn remaining_for(n: usize, first: bool, indices: &[usize]) -> Option<usize> {
let k = indices.len();
diff --git a/crates/itertools/src/combinations_with_replacement.rs b/crates/itertools/src/combinations_with_replacement.rs
index f363f9b..c17e752 100644
--- a/crates/itertools/src/combinations_with_replacement.rs
+++ b/crates/itertools/src/combinations_with_replacement.rs
@@ -73,11 +73,7 @@
Some((increment_from, increment_value)) => {
// We need to update the rightmost non-max value
// and all those to the right
- for i in &mut self.indices[increment_from..] {
- *i = increment_value;
- }
- // TODO: once MSRV >= 1.50, use `fill` instead:
- // self.indices[increment_from..].fill(increment_value);
+ self.indices[increment_from..].fill(increment_value);
false
}
// Otherwise, we're done
diff --git a/crates/itertools/src/concat_impl.rs b/crates/itertools/src/concat_impl.rs
index ec7b91c..dc80839 100644
--- a/crates/itertools/src/concat_impl.rs
+++ b/crates/itertools/src/concat_impl.rs
@@ -1,8 +1,6 @@
-use crate::Itertools;
-
/// Combine all an iterator's elements into one element by using [`Extend`].
///
-/// [`IntoIterator`]-enabled version of [`Itertools::concat`].
+/// [`IntoIterator`]-enabled version of [`Itertools::concat`](crate::Itertools::concat).
///
/// This combinator will extend the first item with each of the rest of the
/// items of the iterator. If the iterator is empty, the default value of
@@ -19,10 +17,9 @@
I: IntoIterator,
I::Item: Extend<<<I as IntoIterator>::Item as IntoIterator>::Item> + IntoIterator + Default,
{
- #[allow(deprecated)] //TODO: once msrv hits 1.51. replace `fold1` with `reduce`
iterable
.into_iter()
- .fold1(|mut a, b| {
+ .reduce(|mut a, b| {
a.extend(b);
a
})
diff --git a/crates/itertools/src/cons_tuples_impl.rs b/crates/itertools/src/cons_tuples_impl.rs
index 9ab3094..7e86260 100644
--- a/crates/itertools/src/cons_tuples_impl.rs
+++ b/crates/itertools/src/cons_tuples_impl.rs
@@ -1,24 +1,15 @@
+use crate::adaptors::map::{MapSpecialCase, MapSpecialCaseFn};
+
macro_rules! impl_cons_iter(
($_A:ident, $_B:ident, ) => (); // stop
($A:ident, $($B:ident,)*) => (
impl_cons_iter!($($B,)*);
#[allow(non_snake_case)]
- impl<X, Iter, $($B),*> Iterator for ConsTuples<Iter, (($($B,)*), X)>
- where Iter: Iterator<Item = (($($B,)*), X)>,
- {
- type Item = ($($B,)* X, );
- fn next(&mut self) -> Option<Self::Item> {
- self.iter.next().map(|(($($B,)*), x)| ($($B,)* x, ))
- }
-
- fn size_hint(&self) -> (usize, Option<usize>) {
- self.iter.size_hint()
- }
- fn fold<Acc, Fold>(self, accum: Acc, mut f: Fold) -> Acc
- where Fold: FnMut(Acc, Self::Item) -> Acc,
- {
- self.iter.fold(accum, move |acc, (($($B,)*), x)| f(acc, ($($B,)* x, )))
+ impl<$($B),*, X> MapSpecialCaseFn<(($($B,)*), X)> for ConsTuplesFn {
+ type Out = ($($B,)* X, );
+ fn call(&mut self, (($($B,)*), X): (($($B,)*), X)) -> Self::Out {
+ ($($B,)* X, )
}
}
);
@@ -26,33 +17,23 @@
impl_cons_iter!(A, B, C, D, E, F, G, H, I, J, K, L,);
+#[derive(Debug, Clone)]
+pub struct ConsTuplesFn;
+
/// An iterator that maps an iterator of tuples like
/// `((A, B), C)` to an iterator of `(A, B, C)`.
///
/// Used by the `iproduct!()` macro.
-#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
-#[derive(Debug)]
-pub struct ConsTuples<I, J>
-where
- I: Iterator<Item = J>,
-{
- iter: I,
-}
-
-impl<I, J> Clone for ConsTuples<I, J>
-where
- I: Clone + Iterator<Item = J>,
-{
- clone_fields!(iter);
-}
+pub type ConsTuples<I> = MapSpecialCase<I, ConsTuplesFn>;
/// Create an iterator that maps for example iterators of
/// `((A, B), C)` to `(A, B, C)`.
-pub fn cons_tuples<I, J>(iterable: I) -> ConsTuples<I::IntoIter, J>
+pub fn cons_tuples<I>(iterable: I) -> ConsTuples<I::IntoIter>
where
- I: IntoIterator<Item = J>,
+ I: IntoIterator,
{
ConsTuples {
iter: iterable.into_iter(),
+ f: ConsTuplesFn,
}
}
diff --git a/crates/itertools/src/diff.rs b/crates/itertools/src/diff.rs
index c6d9965..df88d80 100644
--- a/crates/itertools/src/diff.rs
+++ b/crates/itertools/src/diff.rs
@@ -1,7 +1,7 @@
//! "Diff"ing iterators for caching elements to sequential collections without requiring the new
//! elements' iterator to be `Clone`.
//!
-//! - [`Diff`] (produced by the [`diff_with`] function)
+//! [`Diff`] (produced by the [`diff_with`] function)
//! describes the difference between two non-`Clone` iterators `I` and `J` after breaking ASAP from
//! a lock-step comparison.
diff --git a/crates/itertools/src/extrema_set.rs b/crates/itertools/src/extrema_set.rs
index d24114c..7d35382 100644
--- a/crates/itertools/src/extrema_set.rs
+++ b/crates/itertools/src/extrema_set.rs
@@ -1,4 +1,3 @@
-#![cfg(feature = "use_alloc")]
use alloc::{vec, vec::Vec};
use std::cmp::Ordering;
diff --git a/crates/itertools/src/format.rs b/crates/itertools/src/format.rs
index 15cee34..3abdda3 100644
--- a/crates/itertools/src/format.rs
+++ b/crates/itertools/src/format.rs
@@ -47,7 +47,7 @@
}
}
-impl<'a, I, F> fmt::Display for FormatWith<'a, I, F>
+impl<I, F> fmt::Display for FormatWith<'_, I, F>
where
I: Iterator,
F: FnMut(I::Item, &mut dyn FnMut(&dyn fmt::Display) -> fmt::Result) -> fmt::Result,
@@ -71,7 +71,7 @@
}
}
-impl<'a, I, F> fmt::Debug for FormatWith<'a, I, F>
+impl<I, F> fmt::Debug for FormatWith<'_, I, F>
where
I: Iterator,
F: FnMut(I::Item, &mut dyn FnMut(&dyn fmt::Display) -> fmt::Result) -> fmt::Result,
@@ -81,7 +81,7 @@
}
}
-impl<'a, I> Format<'a, I>
+impl<I> Format<'_, I>
where
I: Iterator,
{
@@ -125,7 +125,7 @@
impl_format! {Display Debug UpperExp LowerExp UpperHex LowerHex Octal Binary Pointer}
-impl<'a, I, F> Clone for FormatWith<'a, I, F>
+impl<I, F> Clone for FormatWith<'_, I, F>
where
(I, F): Clone,
{
@@ -135,7 +135,7 @@
inner: Option<(I, F)>,
}
// This ensures we preserve the state of the original `FormatWith` if `Clone` panics
- impl<'r, 'a, I, F> Drop for PutBackOnDrop<'r, 'a, I, F> {
+ impl<I, F> Drop for PutBackOnDrop<'_, '_, I, F> {
fn drop(&mut self) {
self.into.inner.set(self.inner.take())
}
@@ -151,7 +151,7 @@
}
}
-impl<'a, I> Clone for Format<'a, I>
+impl<I> Clone for Format<'_, I>
where
I: Clone,
{
@@ -161,7 +161,7 @@
inner: Option<I>,
}
// This ensures we preserve the state of the original `FormatWith` if `Clone` panics
- impl<'r, 'a, I> Drop for PutBackOnDrop<'r, 'a, I> {
+ impl<I> Drop for PutBackOnDrop<'_, '_, I> {
fn drop(&mut self) {
self.into.inner.set(self.inner.take())
}
diff --git a/crates/itertools/src/free.rs b/crates/itertools/src/free.rs
index 8d0bcf3..4c68205 100644
--- a/crates/itertools/src/free.rs
+++ b/crates/itertools/src/free.rs
@@ -36,7 +36,7 @@
/// ```
/// use itertools::intersperse;
///
-/// itertools::assert_equal(intersperse((0..3), 8), vec![0, 8, 1, 8, 2]);
+/// itertools::assert_equal(intersperse(0..3, 8), vec![0, 8, 1, 8, 2]);
/// ```
pub fn intersperse<I>(iterable: I, element: I::Item) -> Intersperse<I::IntoIter>
where
@@ -55,7 +55,7 @@
/// use itertools::intersperse_with;
///
/// let mut i = 10;
-/// itertools::assert_equal(intersperse_with((0..3), || { i -= 1; i }), vec![0, 9, 1, 8, 2]);
+/// itertools::assert_equal(intersperse_with(0..3, || { i -= 1; i }), vec![0, 9, 1, 8, 2]);
/// assert_eq!(i, 8);
/// ```
pub fn intersperse_with<I, F>(iterable: I, element: F) -> IntersperseWith<I::IntoIter, F>
@@ -75,6 +75,7 @@
///
/// for (i, elt) in enumerate(&[1, 2, 3]) {
/// /* loop body */
+/// # let _ = (i, elt);
/// }
/// ```
pub fn enumerate<I>(iterable: I) -> iter::Enumerate<I::IntoIter>
@@ -93,6 +94,7 @@
///
/// for elt in rev(&[1, 2, 3]) {
/// /* loop body */
+/// # let _ = elt;
/// }
/// ```
pub fn rev<I>(iterable: I) -> iter::Rev<I::IntoIter>
diff --git a/crates/itertools/src/grouping_map.rs b/crates/itertools/src/grouping_map.rs
index b4aae9e..86cb55d 100644
--- a/crates/itertools/src/grouping_map.rs
+++ b/crates/itertools/src/grouping_map.rs
@@ -1,5 +1,3 @@
-#![cfg(feature = "use_std")]
-
use crate::{
adaptors::map::{MapSpecialCase, MapSpecialCaseFn},
MinMaxResult,
diff --git a/crates/itertools/src/k_smallest.rs b/crates/itertools/src/k_smallest.rs
index 7b2f62e..7e4ace2 100644
--- a/crates/itertools/src/k_smallest.rs
+++ b/crates/itertools/src/k_smallest.rs
@@ -88,6 +88,46 @@
storage
}
+pub(crate) fn k_smallest_relaxed_general<I, F>(iter: I, k: usize, mut comparator: F) -> Vec<I::Item>
+where
+ I: Iterator,
+ F: FnMut(&I::Item, &I::Item) -> Ordering,
+{
+ if k == 0 {
+ iter.last();
+ return Vec::new();
+ }
+
+ let mut iter = iter.fuse();
+ let mut buf = iter.by_ref().take(2 * k).collect::<Vec<_>>();
+
+ if buf.len() < k {
+ buf.sort_unstable_by(&mut comparator);
+ return buf;
+ }
+
+ buf.select_nth_unstable_by(k - 1, &mut comparator);
+ buf.truncate(k);
+
+ iter.for_each(|val| {
+ if comparator(&val, &buf[k - 1]) != Ordering::Less {
+ return;
+ }
+
+ assert_ne!(buf.len(), buf.capacity());
+ buf.push(val);
+
+ if buf.len() == 2 * k {
+ buf.select_nth_unstable_by(k - 1, &mut comparator);
+ buf.truncate(k);
+ }
+ });
+
+ buf.sort_unstable_by(&mut comparator);
+ buf.truncate(k);
+ buf
+}
+
#[inline]
pub(crate) fn key_to_cmp<T, K, F>(mut key: F) -> impl FnMut(&T, &T) -> Ordering
where
diff --git a/crates/itertools/src/kmerge_impl.rs b/crates/itertools/src/kmerge_impl.rs
index 0be3840..9ea73f9 100644
--- a/crates/itertools/src/kmerge_impl.rs
+++ b/crates/itertools/src/kmerge_impl.rs
@@ -1,5 +1,4 @@
use crate::size_hint;
-use crate::Itertools;
use alloc::vec::Vec;
use std::fmt;
@@ -128,13 +127,14 @@
/// Create an iterator that merges elements of the contained iterators using
/// the ordering function.
///
-/// [`IntoIterator`] enabled version of [`Itertools::kmerge`].
+/// [`IntoIterator`] enabled version of [`Itertools::kmerge`](crate::Itertools::kmerge).
///
/// ```
/// use itertools::kmerge;
///
/// for elt in kmerge(vec![vec![0, 2, 4], vec![1, 3, 5], vec![6, 7]]) {
/// /* loop body */
+/// # let _ = elt;
/// }
/// ```
pub fn kmerge<I>(iterable: I) -> KMerge<<I::Item as IntoIterator>::IntoIter>
@@ -172,7 +172,7 @@
/// Create an iterator that merges elements of the contained iterators.
///
-/// [`IntoIterator`] enabled version of [`Itertools::kmerge_by`].
+/// [`IntoIterator`] enabled version of [`Itertools::kmerge_by`](crate::Itertools::kmerge_by).
pub fn kmerge_by<I, F>(
iterable: I,
mut less_than: F,
@@ -223,11 +223,10 @@
}
fn size_hint(&self) -> (usize, Option<usize>) {
- #[allow(deprecated)] //TODO: once msrv hits 1.51. replace `fold1` with `reduce`
self.heap
.iter()
.map(|i| i.size_hint())
- .fold1(size_hint::add)
+ .reduce(size_hint::add)
.unwrap_or((0, Some(0)))
}
}
diff --git a/crates/itertools/src/lazy_buffer.rs b/crates/itertools/src/lazy_buffer.rs
index fefcff8..fafa5f7 100644
--- a/crates/itertools/src/lazy_buffer.rs
+++ b/crates/itertools/src/lazy_buffer.rs
@@ -59,6 +59,10 @@
pub fn get_at(&self, indices: &[usize]) -> Vec<I::Item> {
indices.iter().map(|i| self.buffer[*i].clone()).collect()
}
+
+ pub fn get_array<const K: usize>(&self, indices: [usize; K]) -> [I::Item; K] {
+ indices.map(|i| self.buffer[i].clone())
+ }
}
impl<I, J> Index<J> for LazyBuffer<I>
diff --git a/crates/itertools/src/lib.rs b/crates/itertools/src/lib.rs
index f4de79c..20226d8 100644
--- a/crates/itertools/src/lib.rs
+++ b/crates/itertools/src/lib.rs
@@ -1,6 +1,7 @@
#![warn(missing_docs, clippy::default_numeric_fallback)]
#![crate_name = "itertools"]
#![cfg_attr(not(feature = "use_std"), no_std)]
+#![doc(test(attr(deny(warnings), allow(deprecated, unstable_name_collisions))))]
//! Extra iterator adaptors, functions and macros.
//!
@@ -8,6 +9,7 @@
//! the [`Itertools`] trait:
//!
//! ```
+//! # #[allow(unused_imports)]
//! use itertools::Itertools;
//! ```
//!
@@ -29,6 +31,7 @@
//!
//! for elt in interleave(&[1, 2, 3], &[2, 3, 4]) {
//! /* loop body */
+//! # let _ = elt;
//! }
//! ```
//!
@@ -46,7 +49,7 @@
//!
//! ## Rust Version
//!
-//! This version of itertools requires Rust 1.43.1 or later.
+//! This version of itertools requires Rust 1.63.0 or later.
#[cfg(not(feature = "use_std"))]
extern crate core as std;
@@ -94,7 +97,7 @@
TakeWhileRef, TupleCombinations, Update, WhileSome,
};
#[cfg(feature = "use_alloc")]
- pub use crate::combinations::Combinations;
+ pub use crate::combinations::{ArrayCombinations, Combinations};
#[cfg(feature = "use_alloc")]
pub use crate::combinations_with_replacement::CombinationsWithReplacement;
pub use crate::cons_tuples_impl::ConsTuples;
@@ -206,6 +209,7 @@
mod minmax;
#[cfg(feature = "use_alloc")]
mod multipeek_impl;
+mod next_array;
mod pad_tail;
#[cfg(feature = "use_alloc")]
mod peek_nth;
@@ -248,6 +252,7 @@
/// // from (0, 0, 0), (0, 0, 1), .., (0, 1, 0), (0, 1, 1), .. etc until (3, 3, 3)
/// for (i, j, k) in iproduct!(0..4, 0..4, 0..4) {
/// // ..
+/// # let _ = (i, j, k);
/// }
/// # }
/// ```
@@ -262,7 +267,10 @@
$crate::__std_iter::once(())
);
($I:expr $(,)?) => (
- $crate::__std_iter::IntoIterator::into_iter($I).map(|elt| (elt,))
+ $crate::__std_iter::Iterator::map(
+ $crate::__std_iter::IntoIterator::into_iter($I),
+ |elt| (elt,)
+ )
);
($I:expr, $J:expr $(,)?) => (
$crate::Itertools::cartesian_product(
@@ -330,19 +338,24 @@
// binary
($first:expr, $second:expr $(,)*) => {
- $crate::izip!($first)
- .zip($second)
+ $crate::__std_iter::Iterator::zip(
+ $crate::__std_iter::IntoIterator::into_iter($first),
+ $second,
+ )
};
// n-ary where n > 2
( $first:expr $( , $rest:expr )* $(,)* ) => {
- $crate::izip!($first)
+ {
+ let iter = $crate::__std_iter::IntoIterator::into_iter($first);
$(
- .zip($rest)
+ let iter = $crate::__std_iter::Iterator::zip(iter, $rest);
)*
- .map(
+ $crate::__std_iter::Iterator::map(
+ iter,
$crate::izip!(@closure a => (a) $( , $rest )*)
)
+ }
};
}
@@ -367,16 +380,16 @@
///
/// Invocations of `chain!` with one argument expand to [`arg.into_iter()`](IntoIterator):
/// ```
-/// use std::{ops::Range, slice};
+/// use std::ops::Range;
/// use itertools::chain;
-/// let _: <Range<_> as IntoIterator>::IntoIter = chain!((2..6),); // trailing comma optional!
+/// let _: <Range<_> as IntoIterator>::IntoIter = chain!(2..6,); // trailing comma optional!
/// let _: <&[_] as IntoIterator>::IntoIter = chain!(&[2, 3, 4]);
/// ```
///
/// Invocations of `chain!` with multiple arguments [`.into_iter()`](IntoIterator) each
/// argument, and then [`chain`] them together:
/// ```
-/// use std::{iter::*, ops::Range, slice};
+/// use std::{iter::*, slice};
/// use itertools::{assert_equal, chain};
///
/// // e.g., this:
@@ -393,16 +406,16 @@
/// ```
macro_rules! chain {
() => {
- core::iter::empty()
+ $crate::__std_iter::empty()
};
($first:expr $(, $rest:expr )* $(,)?) => {
{
- let iter = core::iter::IntoIterator::into_iter($first);
+ let iter = $crate::__std_iter::IntoIterator::into_iter($first);
$(
let iter =
- core::iter::Iterator::chain(
+ $crate::__std_iter::Iterator::chain(
iter,
- core::iter::IntoIterator::into_iter($rest));
+ $crate::__std_iter::IntoIterator::into_iter($rest));
)*
iter
}
@@ -415,13 +428,13 @@
/// This trait defines a number of methods. They are divided into two groups:
///
/// * *Adaptors* take an iterator and parameter as input, and return
-/// a new iterator value. These are listed first in the trait. An example
-/// of an adaptor is [`.interleave()`](Itertools::interleave)
+/// a new iterator value. These are listed first in the trait. An example
+/// of an adaptor is [`.interleave()`](Itertools::interleave)
///
/// * *Regular methods* are those that don't return iterators and instead
-/// return a regular value of some other kind.
-/// [`.next_tuple()`](Itertools::next_tuple) is an example and the first regular
-/// method in the list.
+/// return a regular value of some other kind.
+/// [`.next_tuple()`](Itertools::next_tuple) is an example and the first regular
+/// method in the list.
pub trait Itertools: Iterator {
// adaptors
@@ -1043,7 +1056,6 @@
/// let it = a.merge_by(b, |x, y| x.1 <= y.1);
/// itertools::assert_equal(it, vec![(0, 'a'), (0, 'b'), (1, 'c'), (1, 'd')]);
/// ```
-
fn merge_by<J, F>(self, other: J, is_first: F) -> MergeBy<Self, J::IntoIter, F>
where
Self: Sized,
@@ -1079,7 +1091,9 @@
/// let b = (0..10).step_by(3);
///
/// itertools::assert_equal(
- /// a.merge_join_by(b, |i, j| i.cmp(j)),
+ /// // This performs a diff in the style of the Unix command comm(1),
+ /// // generalized to arbitrary types rather than text.
+ /// a.merge_join_by(b, Ord::cmp),
/// vec![Both(0, 0), Left(2), Right(3), Left(4), Both(6, 6), Left(1), Right(9)]
/// );
/// ```
@@ -1111,6 +1125,7 @@
/// );
/// ```
#[inline]
+ #[doc(alias = "comm")]
fn merge_join_by<J, F, T>(self, other: J, cmp_fn: F) -> MergeJoinBy<Self, J::IntoIter, F>
where
J: IntoIterator,
@@ -1582,6 +1597,7 @@
/// .collect();
/// let expected: Vec<_> = vec![1, 2, 3].into_iter().map(NoCloneImpl).collect();
/// assert_eq!(filtered, expected);
+ #[doc(alias = "take_until")]
fn take_while_inclusive<F>(self, accept: F) -> TakeWhileInclusive<Self, F>
where
Self: Sized,
@@ -1658,6 +1674,53 @@
adaptors::tuple_combinations(self)
}
+ /// Return an iterator adaptor that iterates over the combinations of the
+ /// elements from an iterator.
+ ///
+ /// Iterator element type is [Self::Item; K]. The iterator produces a new
+ /// array per iteration, and clones the iterator elements.
+ ///
+ /// # Guarantees
+ ///
+ /// If the adapted iterator is deterministic,
+ /// this iterator adapter yields items in a reliable order.
+ ///
+ /// ```
+ /// use itertools::Itertools;
+ ///
+ /// let mut v = Vec::new();
+ /// for [a, b] in (1..5).array_combinations() {
+ /// v.push([a, b]);
+ /// }
+ /// assert_eq!(v, vec![[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]);
+ ///
+ /// let mut it = (1..5).array_combinations();
+ /// assert_eq!(Some([1, 2, 3]), it.next());
+ /// assert_eq!(Some([1, 2, 4]), it.next());
+ /// assert_eq!(Some([1, 3, 4]), it.next());
+ /// assert_eq!(Some([2, 3, 4]), it.next());
+ /// assert_eq!(None, it.next());
+ ///
+ /// // this requires a type hint
+ /// let it = (1..5).array_combinations::<3>();
+ /// itertools::assert_equal(it, vec![[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]);
+ ///
+ /// // you can also specify the complete type
+ /// use itertools::ArrayCombinations;
+ /// use std::ops::Range;
+ ///
+ /// let it: ArrayCombinations<Range<u32>, 3> = (1..5).array_combinations();
+ /// itertools::assert_equal(it, vec![[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]);
+ /// ```
+ #[cfg(feature = "use_alloc")]
+ fn array_combinations<const K: usize>(self) -> ArrayCombinations<Self, K>
+ where
+ Self: Sized + Clone,
+ Self::Item: Clone,
+ {
+ combinations::array_combinations(self)
+ }
+
/// Return an iterator adaptor that iterates over the `k`-length combinations of
/// the elements from an iterator.
///
@@ -1894,7 +1957,7 @@
/// use itertools::Itertools;
///
/// let input = vec![vec![1], vec![3, 2, 1]];
- /// let it = input.into_iter().update(|mut v| v.push(0));
+ /// let it = input.into_iter().update(|v| v.push(0));
/// itertools::assert_equal(it, vec![vec![1, 0], vec![3, 2, 1, 0]]);
/// ```
fn update<F>(self, updater: F) -> Update<Self, F>
@@ -1906,6 +1969,50 @@
}
// non-adaptor methods
+ /// Advances the iterator and returns the next items grouped in an array of
+ /// a specific size.
+ ///
+ /// If there are enough elements to be grouped in an array, then the array
+ /// is returned inside `Some`, otherwise `None` is returned.
+ ///
+ /// ```
+ /// use itertools::Itertools;
+ ///
+ /// let mut iter = 1..5;
+ ///
+ /// assert_eq!(Some([1, 2]), iter.next_array());
+ /// ```
+ fn next_array<const N: usize>(&mut self) -> Option<[Self::Item; N]>
+ where
+ Self: Sized,
+ {
+ next_array::next_array(self)
+ }
+
+ /// Collects all items from the iterator into an array of a specific size.
+ ///
+ /// If the number of elements inside the iterator is **exactly** equal to
+ /// the array size, then the array is returned inside `Some`, otherwise
+ /// `None` is returned.
+ ///
+ /// ```
+ /// use itertools::Itertools;
+ ///
+ /// let iter = 1..3;
+ ///
+ /// if let Some([x, y]) = iter.collect_array() {
+ /// assert_eq!([x, y], [1, 2])
+ /// } else {
+ /// panic!("Expected two elements")
+ /// }
+ /// ```
+ fn collect_array<const N: usize>(mut self) -> Option<[Self::Item; N]>
+ where
+ Self: Sized,
+ {
+ self.next_array().filter(|_| self.next().is_none())
+ }
+
/// Advances the iterator and returns the next items grouped in a tuple of
/// a specific size (up to 12).
///
@@ -1986,6 +2093,15 @@
/// assert_eq!(numbers.iter().find_or_last(|&&x| x > 5), Some(&4));
/// assert_eq!(numbers.iter().find_or_last(|&&x| x > 2), Some(&3));
/// assert_eq!(std::iter::empty::<i32>().find_or_last(|&x| x > 5), None);
+ ///
+ /// // An iterator of Results can return the first Ok or the last Err:
+ /// let input = vec![Err(()), Ok(11), Err(()), Ok(22)];
+ /// assert_eq!(input.into_iter().find_or_last(Result::is_ok), Some(Ok(11)));
+ ///
+ /// let input: Vec<Result<(), i32>> = vec![Err(11), Err(22)];
+ /// assert_eq!(input.into_iter().find_or_last(Result::is_ok), Some(Err(22)));
+ ///
+ /// assert_eq!(std::iter::empty::<Result<(), i32>>().find_or_last(Result::is_ok), None);
/// ```
fn find_or_last<P>(mut self, mut predicate: P) -> Option<Self::Item>
where
@@ -2014,6 +2130,15 @@
/// assert_eq!(numbers.iter().find_or_first(|&&x| x > 5), Some(&1));
/// assert_eq!(numbers.iter().find_or_first(|&&x| x > 2), Some(&3));
/// assert_eq!(std::iter::empty::<i32>().find_or_first(|&x| x > 5), None);
+ ///
+ /// // An iterator of Results can return the first Ok or the first Err:
+ /// let input = vec![Err(()), Ok(11), Err(()), Ok(22)];
+ /// assert_eq!(input.into_iter().find_or_first(Result::is_ok), Some(Ok(11)));
+ ///
+ /// let input: Vec<Result<(), i32>> = vec![Err(11), Err(22)];
+ /// assert_eq!(input.into_iter().find_or_first(Result::is_ok), Some(Err(11)));
+ ///
+ /// assert_eq!(std::iter::empty::<Result<(), i32>>().find_or_first(Result::is_ok), None);
/// ```
fn find_or_first<P>(mut self, mut predicate: P) -> Option<Self::Item>
where
@@ -2056,7 +2181,7 @@
where
Self: Sized,
Self::Item: Borrow<Q>,
- Q: PartialEq,
+ Q: PartialEq + ?Sized,
{
self.any(|x| x.borrow() == query)
}
@@ -2154,7 +2279,7 @@
/// ```
/// use itertools::Itertools;
///
- /// let mut iter = "αβγ".chars().dropping(2);
+ /// let iter = "αβγ".chars().dropping(2);
/// itertools::assert_equal(iter, "γ".chars());
/// ```
///
@@ -2238,14 +2363,17 @@
///
/// fn process_dir_entries(entries: &[fs::DirEntry]) {
/// // ...
+ /// # let _ = entries;
/// }
///
- /// fn do_stuff() -> std::io::Result<()> {
+ /// fn do_stuff() -> io::Result<()> {
/// let entries: Vec<_> = fs::read_dir(".")?.try_collect()?;
/// process_dir_entries(&entries);
///
/// Ok(())
/// }
+ ///
+ /// # let _ = do_stuff;
/// ```
fn try_collect<T, U, E>(self) -> Result<U, E>
where
@@ -2396,6 +2524,7 @@
/// accum = f(accum, 1);
/// accum = f(accum, 2);
/// accum = f(accum, 3);
+ /// # let _ = accum;
/// ```
///
/// With a `start` value of 0 and an addition as folding function,
@@ -2520,34 +2649,64 @@
///
/// If `f` is associative you should also decide carefully:
///
- /// - if `f` is a trivial operation like `u32::wrapping_add`, prefer the normal
- /// [`Iterator::reduce`] instead since it will most likely result in the generation of simpler
- /// code because the compiler is able to optimize it
- /// - otherwise if `f` is non-trivial like `format!`, you should use `tree_reduce` since it
- /// reduces the number of operations from `O(n)` to `O(ln(n))`
+ /// For an iterator producing `n` elements, both [`Iterator::reduce`] and `tree_reduce` will
+ /// call `f` `n - 1` times. However, `tree_reduce` will call `f` on earlier intermediate
+ /// results, which is beneficial for `f` that allocate and produce longer results for longer
+ /// arguments. For example if `f` combines arguments using `format!`, then `tree_reduce` will
+ /// operate on average on shorter arguments resulting in less bytes being allocated overall.
///
- /// Here "non-trivial" means:
+ /// Moreover, the output of `tree_reduce` is preferable to that of [`Iterator::reduce`] in
+ /// certain cases. For example, building a binary search tree using `tree_reduce` will result in
+ /// a balanced tree with height `O(ln(n))`, while [`Iterator::reduce`] will output a tree with
+ /// height `O(n)`, essentially a linked list.
///
- /// - any allocating operation
- /// - any function that is a composition of many operations
+ /// If `f` does not benefit from such a reordering, like `u32::wrapping_add`, prefer the
+ /// normal [`Iterator::reduce`] instead since it will most likely result in the generation of
+ /// simpler code because the compiler is able to optimize it.
///
/// ```
/// use itertools::Itertools;
///
- /// // The same tree as above
- /// let num_strings = (1..8).map(|x| x.to_string());
- /// assert_eq!(num_strings.tree_reduce(|x, y| format!("f({}, {})", x, y)),
- /// Some(String::from("f(f(f(1, 2), f(3, 4)), f(f(5, 6), 7))")));
+ /// let f = |a: String, b: String| {
+ /// format!("f({a}, {b})")
+ /// };
///
- /// // Like fold1, an empty iterator produces None
+ /// // The same tree as above
+ /// assert_eq!((1..8).map(|x| x.to_string()).tree_reduce(f),
+ /// Some(String::from("f(f(f(1, 2), f(3, 4)), f(f(5, 6), 7))")));
+ ///
+ /// // Like reduce, an empty iterator produces None
/// assert_eq!((0..0).tree_reduce(|x, y| x * y), None);
///
- /// // tree_reduce matches fold1 for associative operations...
+ /// // tree_reduce matches reduce for associative operations...
/// assert_eq!((0..10).tree_reduce(|x, y| x + y),
- /// (0..10).fold1(|x, y| x + y));
+ /// (0..10).reduce(|x, y| x + y));
+ ///
/// // ...but not for non-associative ones
/// assert_ne!((0..10).tree_reduce(|x, y| x - y),
- /// (0..10).fold1(|x, y| x - y));
+ /// (0..10).reduce(|x, y| x - y));
+ ///
+ /// let mut total_len_reduce = 0;
+ /// let reduce_res = (1..100).map(|x| x.to_string())
+ /// .reduce(|a, b| {
+ /// let r = f(a, b);
+ /// total_len_reduce += r.len();
+ /// r
+ /// })
+ /// .unwrap();
+ ///
+ /// let mut total_len_tree_reduce = 0;
+ /// let tree_reduce_res = (1..100).map(|x| x.to_string())
+ /// .tree_reduce(|a, b| {
+ /// let r = f(a, b);
+ /// total_len_tree_reduce += r.len();
+ /// r
+ /// })
+ /// .unwrap();
+ ///
+ /// assert_eq!(total_len_reduce, 33299);
+ /// assert_eq!(total_len_tree_reduce, 4228);
+ /// assert_eq!(reduce_res.len(), tree_reduce_res.len());
/// ```
fn tree_reduce<F>(mut self, mut f: F) -> Option<Self::Item>
where
@@ -3115,6 +3274,105 @@
self.k_smallest_by(k, k_smallest::key_to_cmp(key))
}
+ /// Sort the k smallest elements into a new iterator, in ascending order, relaxing the amount of memory required.
+ ///
+ /// **Note:** This consumes the entire iterator, and returns the result
+ /// as a new iterator that owns its elements. If the input contains
+ /// less than k elements, the result is equivalent to `self.sorted()`.
+ ///
+ /// This is guaranteed to use `2 * k * sizeof(Self::Item) + O(1)` memory
+ /// and `O(n + k log k)` time, with `n` the number of elements in the input,
+ /// meaning it uses more memory than the minimum obtained by [`k_smallest`](Itertools::k_smallest)
+ /// but achieves linear time in the number of elements.
+ ///
+ /// The sorted iterator, if directly collected to a `Vec`, is converted
+ /// without any extra copying or allocation cost.
+ ///
+ /// **Note:** This is functionally-equivalent to `self.sorted().take(k)`
+ /// but much more efficient.
+ ///
+ /// ```
+ /// use itertools::Itertools;
+ ///
+ /// // A random permutation of 0..15
+ /// let numbers = vec![6, 9, 1, 14, 0, 4, 8, 7, 11, 2, 10, 3, 13, 12, 5];
+ ///
+ /// let five_smallest = numbers
+ /// .into_iter()
+ /// .k_smallest_relaxed(5);
+ ///
+ /// itertools::assert_equal(five_smallest, 0..5);
+ /// ```
+ #[cfg(feature = "use_alloc")]
+ fn k_smallest_relaxed(self, k: usize) -> VecIntoIter<Self::Item>
+ where
+ Self: Sized,
+ Self::Item: Ord,
+ {
+ self.k_smallest_relaxed_by(k, Ord::cmp)
+ }
+
+ /// Sort the k smallest elements into a new iterator using the provided comparison, relaxing the amount of memory required.
+ ///
+ /// The sorted iterator, if directly collected to a `Vec`, is converted
+ /// without any extra copying or allocation cost.
+ ///
+ /// This corresponds to `self.sorted_by(cmp).take(k)` in the same way that
+ /// [`k_smallest_relaxed`](Itertools::k_smallest_relaxed) corresponds to `self.sorted().take(k)`,
+ /// in both semantics and complexity.
+ ///
+ /// ```
+ /// use itertools::Itertools;
+ ///
+ /// // A random permutation of 0..15
+ /// let numbers = vec![6, 9, 1, 14, 0, 4, 8, 7, 11, 2, 10, 3, 13, 12, 5];
+ ///
+ /// let five_smallest = numbers
+ /// .into_iter()
+ /// .k_smallest_relaxed_by(5, |a, b| (a % 7).cmp(&(b % 7)).then(a.cmp(b)));
+ ///
+ /// itertools::assert_equal(five_smallest, vec![0, 7, 14, 1, 8]);
+ /// ```
+ #[cfg(feature = "use_alloc")]
+ fn k_smallest_relaxed_by<F>(self, k: usize, cmp: F) -> VecIntoIter<Self::Item>
+ where
+ Self: Sized,
+ F: FnMut(&Self::Item, &Self::Item) -> Ordering,
+ {
+ k_smallest::k_smallest_relaxed_general(self, k, cmp).into_iter()
+ }
+
+ /// Return the elements producing the k smallest outputs of the provided function, relaxing the amount of memory required.
+ ///
+ /// The sorted iterator, if directly collected to a `Vec`, is converted
+ /// without any extra copying or allocation cost.
+ ///
+ /// This corresponds to `self.sorted_by_key(key).take(k)` in the same way that
+ /// [`k_smallest_relaxed`](Itertools::k_smallest_relaxed) corresponds to `self.sorted().take(k)`,
+ /// in both semantics and complexity.
+ ///
+ /// ```
+ /// use itertools::Itertools;
+ ///
+ /// // A random permutation of 0..15
+ /// let numbers = vec![6, 9, 1, 14, 0, 4, 8, 7, 11, 2, 10, 3, 13, 12, 5];
+ ///
+ /// let five_smallest = numbers
+ /// .into_iter()
+ /// .k_smallest_relaxed_by_key(5, |n| (n % 7, *n));
+ ///
+ /// itertools::assert_equal(five_smallest, vec![0, 7, 14, 1, 8]);
+ /// ```
+ #[cfg(feature = "use_alloc")]
+ fn k_smallest_relaxed_by_key<F, K>(self, k: usize, key: F) -> VecIntoIter<Self::Item>
+ where
+ Self: Sized,
+ F: FnMut(&Self::Item) -> K,
+ K: Ord,
+ {
+ self.k_smallest_relaxed_by(k, k_smallest::key_to_cmp(key))
+ }
+
/// Sort the k largest elements into a new iterator, in descending order.
///
/// The sorted iterator, if directly collected to a `Vec`, is converted
@@ -3205,6 +3463,94 @@
self.k_largest_by(k, k_smallest::key_to_cmp(key))
}
+ /// Sort the k largest elements into a new iterator, in descending order, relaxing the amount of memory required.
+ ///
+ /// The sorted iterator, if directly collected to a `Vec`, is converted
+ /// without any extra copying or allocation cost.
+ ///
+ /// It is semantically equivalent to [`k_smallest_relaxed`](Itertools::k_smallest_relaxed)
+ /// with a reversed `Ord`.
+ ///
+ /// ```
+ /// use itertools::Itertools;
+ ///
+ /// // A random permutation of 0..15
+ /// let numbers = vec![6, 9, 1, 14, 0, 4, 8, 7, 11, 2, 10, 3, 13, 12, 5];
+ ///
+ /// let five_largest = numbers
+ /// .into_iter()
+ /// .k_largest_relaxed(5);
+ ///
+ /// itertools::assert_equal(five_largest, vec![14, 13, 12, 11, 10]);
+ /// ```
+ #[cfg(feature = "use_alloc")]
+ fn k_largest_relaxed(self, k: usize) -> VecIntoIter<Self::Item>
+ where
+ Self: Sized,
+ Self::Item: Ord,
+ {
+ self.k_largest_relaxed_by(k, Self::Item::cmp)
+ }
+
+ /// Sort the k largest elements into a new iterator using the provided comparison, relaxing the amount of memory required.
+ ///
+ /// The sorted iterator, if directly collected to a `Vec`, is converted
+ /// without any extra copying or allocation cost.
+ ///
+ /// Functionally equivalent to [`k_smallest_relaxed_by`](Itertools::k_smallest_relaxed_by)
+ /// with a reversed `Ord`.
+ ///
+ /// ```
+ /// use itertools::Itertools;
+ ///
+ /// // A random permutation of 0..15
+ /// let numbers = vec![6, 9, 1, 14, 0, 4, 8, 7, 11, 2, 10, 3, 13, 12, 5];
+ ///
+ /// let five_largest = numbers
+ /// .into_iter()
+ /// .k_largest_relaxed_by(5, |a, b| (a % 7).cmp(&(b % 7)).then(a.cmp(b)));
+ ///
+ /// itertools::assert_equal(five_largest, vec![13, 6, 12, 5, 11]);
+ /// ```
+ #[cfg(feature = "use_alloc")]
+ fn k_largest_relaxed_by<F>(self, k: usize, mut cmp: F) -> VecIntoIter<Self::Item>
+ where
+ Self: Sized,
+ F: FnMut(&Self::Item, &Self::Item) -> Ordering,
+ {
+ self.k_smallest_relaxed_by(k, move |a, b| cmp(b, a))
+ }
+
+ /// Return the elements producing the k largest outputs of the provided function, relaxing the amount of memory required.
+ ///
+ /// The sorted iterator, if directly collected to a `Vec`, is converted
+ /// without any extra copying or allocation cost.
+ ///
+ /// Functionally equivalent to [`k_smallest_relaxed_by_key`](Itertools::k_smallest_relaxed_by_key)
+ /// with a reversed `Ord`.
+ ///
+ /// ```
+ /// use itertools::Itertools;
+ ///
+ /// // A random permutation of 0..15
+ /// let numbers = vec![6, 9, 1, 14, 0, 4, 8, 7, 11, 2, 10, 3, 13, 12, 5];
+ ///
+ /// let five_largest = numbers
+ /// .into_iter()
+ /// .k_largest_relaxed_by_key(5, |n| (n % 7, *n));
+ ///
+ /// itertools::assert_equal(five_largest, vec![13, 6, 12, 5, 11]);
+ /// ```
+ #[cfg(feature = "use_alloc")]
+ fn k_largest_relaxed_by_key<F, K>(self, k: usize, key: F) -> VecIntoIter<Self::Item>
+ where
+ Self: Sized,
+ F: FnMut(&Self::Item) -> K,
+ K: Ord,
+ {
+ self.k_largest_relaxed_by(k, k_smallest::key_to_cmp(key))
+ }
+
/// Consumes the iterator and return an iterator of the last `n` elements.
///
/// The iterator, if directly collected to a `VecDeque`, is converted
@@ -3357,8 +3703,8 @@
group_map::into_group_map(self)
}
- /// Return an `Iterator` on a `HashMap`. Keys mapped to `Vec`s of values. The key is specified
- /// in the closure.
+ /// Return a `HashMap` of keys mapped to `Vec`s of values. The key is specified
+ /// in the closure. The values are taken from the input iterator.
///
/// Essentially a shorthand for `.into_grouping_map_by(f).collect::<Vec<_>>()`.
///
@@ -3370,7 +3716,7 @@
/// let lookup: HashMap<u32,Vec<(u32, u32)>> =
/// data.clone().into_iter().into_group_map_by(|a| a.0);
///
- /// assert_eq!(lookup[&0], vec![(0,10),(0,20)]);
+ /// assert_eq!(lookup[&0], vec![(0,10), (0,20)]);
/// assert_eq!(lookup.get(&1), None);
/// assert_eq!(lookup[&2], vec![(2,12), (2,42)]);
/// assert_eq!(lookup[&3], vec![(3,13), (3,33)]);
@@ -4125,7 +4471,7 @@
/// # Examples
/// ```
/// # use itertools::Itertools;
- /// let counts = [1, 1, 1, 3, 3, 5].into_iter().counts();
+ /// let counts = [1, 1, 1, 3, 3, 5].iter().counts();
/// assert_eq!(counts[&1], 3);
/// assert_eq!(counts[&3], 2);
/// assert_eq!(counts[&5], 1);
@@ -4151,6 +4497,7 @@
/// # use itertools::Itertools;
/// struct Character {
/// first_name: &'static str,
+ /// # #[allow(dead_code)]
/// last_name: &'static str,
/// }
///
@@ -4268,6 +4615,7 @@
/// assert_equal("exceed".split('c'), "excess".split('c'));
/// // ^PANIC: panicked at 'Failed assertion Some("eed") == Some("ess") for iteration 1'.
/// ```
+#[track_caller]
pub fn assert_equal<I, J>(a: I, b: J)
where
I: IntoIterator,
diff --git a/crates/itertools/src/merge_join.rs b/crates/itertools/src/merge_join.rs
index c0de35f..5f4a605 100644
--- a/crates/itertools/src/merge_join.rs
+++ b/crates/itertools/src/merge_join.rs
@@ -31,6 +31,7 @@
///
/// for elt in merge(&[1, 2, 3], &[2, 3, 4]) {
/// /* loop body */
+/// # let _ = elt;
/// }
/// ```
pub fn merge<I, J>(
diff --git a/crates/itertools/src/next_array.rs b/crates/itertools/src/next_array.rs
new file mode 100644
index 0000000..86480b1
--- /dev/null
+++ b/crates/itertools/src/next_array.rs
@@ -0,0 +1,269 @@
+use core::mem::{self, MaybeUninit};
+
+/// An array of at most `N` elements.
+struct ArrayBuilder<T, const N: usize> {
+ /// The (possibly uninitialized) elements of the `ArrayBuilder`.
+ ///
+ /// # Safety
+ ///
+ /// The elements of `arr[..len]` are valid `T`s.
+ arr: [MaybeUninit<T>; N],
+
+ /// The number of leading elements of `arr` that are valid `T`s, len <= N.
+ len: usize,
+}
+
+impl<T, const N: usize> ArrayBuilder<T, N> {
+ /// Initializes a new, empty `ArrayBuilder`.
+ pub fn new() -> Self {
+ // SAFETY: The safety invariant of `arr` trivially holds for `len = 0`.
+ Self {
+ arr: [(); N].map(|_| MaybeUninit::uninit()),
+ len: 0,
+ }
+ }
+
+ /// Pushes `value` onto the end of the array.
+ ///
+ /// # Panics
+ ///
+ /// This panics if `self.len >= N`.
+ #[inline(always)]
+ pub fn push(&mut self, value: T) {
+ // PANICS: This will panic if `self.len >= N`.
+ let place = &mut self.arr[self.len];
+ // SAFETY: The safety invariant of `self.arr` applies to elements at
+ // indices `0..self.len` — not to the element at `self.len`. Writing to
+ // the element at index `self.len` therefore does not violate the safety
+ // invariant of `self.arr`. Even if this line panics, we have not
+ // created any intermediate invalid state.
+ *place = MaybeUninit::new(value);
+ // Lemma: `self.len < N`. By invariant, `self.len <= N`. Above, we index
+ // into `self.arr`, which has size `N`, at index `self.len`. If `self.len == N`
+ // at that point, that index would be out-of-bounds, and the index
+ // operation would panic. Thus, `self.len != N`, and since `self.len <= N`,
+ // that means that `self.len < N`.
+ //
+ // PANICS: Since `self.len < N`, and since `N <= usize::MAX`,
+ // `self.len + 1 <= usize::MAX`, and so `self.len += 1` will not
+ // overflow. Overflow is the only panic condition of `+=`.
+ //
+ // SAFETY:
+ // - We are required to uphold the invariant that `self.len <= N`.
+ // Since, by the preceding lemma, `self.len < N` at this point in the
+ // code, `self.len += 1` results in `self.len <= N`.
+ // - We are required to uphold the invariant that `self.arr[..self.len]`
+ // are valid instances of `T`. Since this invariant already held when
+ // this method was called, and since we only increment `self.len`
+ // by 1 here, we only need to prove that the element at
+ // `self.arr[self.len]` (using the value of `self.len` before incrementing)
+ // is valid. Above, we construct `place` to point to `self.arr[self.len]`,
+ // and then initialize `*place` to `MaybeUninit::new(value)`, which is
+ // a valid `T` by construction.
+ self.len += 1;
+ }
+
+ /// Consumes the elements in the `ArrayBuilder` and returns them as an array
+ /// `[T; N]`.
+ ///
+ /// If `self.len() < N`, this returns `None`.
+ pub fn take(&mut self) -> Option<[T; N]> {
+ if self.len == N {
+ // SAFETY: Decreasing the value of `self.len` cannot violate the
+ // safety invariant on `self.arr`.
+ self.len = 0;
+
+ // SAFETY: Since `self.len` is 0, `self.arr` may safely contain
+ // uninitialized elements.
+ let arr = mem::replace(&mut self.arr, [(); N].map(|_| MaybeUninit::uninit()));
+
+ Some(arr.map(|v| {
+ // SAFETY: We know that all elements of `arr` are valid because
+ // we checked that `len == N`.
+ unsafe { v.assume_init() }
+ }))
+ } else {
+ None
+ }
+ }
+}
+
+impl<T, const N: usize> AsMut<[T]> for ArrayBuilder<T, N> {
+ fn as_mut(&mut self) -> &mut [T] {
+ let valid = &mut self.arr[..self.len];
+ // SAFETY: By invariant on `self.arr`, the elements of `self.arr` at
+ // indices `0..self.len` are in a valid state. Since `valid` references
+ // only these elements, the safety precondition of
+ // `slice_assume_init_mut` is satisfied.
+ unsafe { slice_assume_init_mut(valid) }
+ }
+}
+
+impl<T, const N: usize> Drop for ArrayBuilder<T, N> {
+ // We provide a non-trivial `Drop` impl, because the trivial impl would be a
+ // no-op; `MaybeUninit<T>` has no innate awareness of its own validity, and
+ // so it can only forget its contents. By leveraging the safety invariant of
+ // `self.arr`, we do know which elements of `self.arr` are valid, and can
+ // selectively run their destructors.
+ fn drop(&mut self) {
+ // SAFETY:
+ // - by invariant on `&mut [T]`, `self.as_mut()` is:
+ // - valid for reads and writes
+ // - properly aligned
+ // - non-null
+ // - the dropped `T` are valid for dropping; they do not have any
+ // additional library invariants that we've violated
+ // - no other pointers to `valid` exist (since we're in the context of
+ // `drop`)
+ unsafe { core::ptr::drop_in_place(self.as_mut()) }
+ }
+}
+
+/// Assuming all the elements are initialized, get a mutable slice to them.
+///
+/// # Safety
+///
+/// The caller guarantees that the elements `T` referenced by `slice` are in a
+/// valid state.
+unsafe fn slice_assume_init_mut<T>(slice: &mut [MaybeUninit<T>]) -> &mut [T] {
+ // SAFETY: Casting `&mut [MaybeUninit<T>]` to `&mut [T]` is sound, because
+ // `MaybeUninit<T>` is guaranteed to have the same size, alignment and ABI
+ // as `T`, and because the caller has guaranteed that `slice` is in the
+ // valid state.
+ unsafe { &mut *(slice as *mut [MaybeUninit<T>] as *mut [T]) }
+}
+
+/// Equivalent to `it.next_array()`.
+pub(crate) fn next_array<I, const N: usize>(it: &mut I) -> Option<[I::Item; N]>
+where
+ I: Iterator,
+{
+ let mut builder = ArrayBuilder::new();
+ for _ in 0..N {
+ builder.push(it.next()?);
+ }
+ builder.take()
+}
+
+#[cfg(test)]
+mod test {
+ use super::ArrayBuilder;
+
+ #[test]
+ fn zero_len_take() {
+ let mut builder = ArrayBuilder::<(), 0>::new();
+ let taken = builder.take();
+ assert_eq!(taken, Some([(); 0]));
+ }
+
+ #[test]
+ #[should_panic]
+ fn zero_len_push() {
+ let mut builder = ArrayBuilder::<(), 0>::new();
+ builder.push(());
+ }
+
+ #[test]
+ fn push_4() {
+ let mut builder = ArrayBuilder::<(), 4>::new();
+ assert_eq!(builder.take(), None);
+
+ builder.push(());
+ assert_eq!(builder.take(), None);
+
+ builder.push(());
+ assert_eq!(builder.take(), None);
+
+ builder.push(());
+ assert_eq!(builder.take(), None);
+
+ builder.push(());
+ assert_eq!(builder.take(), Some([(); 4]));
+ }
+
+ #[test]
+ fn tracked_drop() {
+ use std::panic::{catch_unwind, AssertUnwindSafe};
+ use std::sync::atomic::{AtomicU16, Ordering};
+
+ static DROPPED: AtomicU16 = AtomicU16::new(0);
+
+ #[derive(Debug, PartialEq)]
+ struct TrackedDrop;
+
+ impl Drop for TrackedDrop {
+ fn drop(&mut self) {
+ DROPPED.fetch_add(1, Ordering::Relaxed);
+ }
+ }
+
+ {
+ let builder = ArrayBuilder::<TrackedDrop, 0>::new();
+ assert_eq!(DROPPED.load(Ordering::Relaxed), 0);
+ drop(builder);
+ assert_eq!(DROPPED.load(Ordering::Relaxed), 0);
+ }
+
+ {
+ let mut builder = ArrayBuilder::<TrackedDrop, 2>::new();
+ builder.push(TrackedDrop);
+ assert_eq!(builder.take(), None);
+ assert_eq!(DROPPED.load(Ordering::Relaxed), 0);
+ drop(builder);
+ assert_eq!(DROPPED.swap(0, Ordering::Relaxed), 1);
+ }
+
+ {
+ let mut builder = ArrayBuilder::<TrackedDrop, 2>::new();
+ builder.push(TrackedDrop);
+ builder.push(TrackedDrop);
+ assert!(matches!(builder.take(), Some(_)));
+ assert_eq!(DROPPED.swap(0, Ordering::Relaxed), 2);
+ drop(builder);
+ assert_eq!(DROPPED.load(Ordering::Relaxed), 0);
+ }
+
+ {
+ let mut builder = ArrayBuilder::<TrackedDrop, 2>::new();
+
+ builder.push(TrackedDrop);
+ builder.push(TrackedDrop);
+
+ assert!(catch_unwind(AssertUnwindSafe(|| {
+ builder.push(TrackedDrop);
+ }))
+ .is_err());
+
+ assert_eq!(DROPPED.load(Ordering::Relaxed), 1);
+
+ drop(builder);
+
+ assert_eq!(DROPPED.swap(0, Ordering::Relaxed), 3);
+ }
+
+ {
+ let mut builder = ArrayBuilder::<TrackedDrop, 2>::new();
+
+ builder.push(TrackedDrop);
+ builder.push(TrackedDrop);
+
+ assert!(catch_unwind(AssertUnwindSafe(|| {
+ builder.push(TrackedDrop);
+ }))
+ .is_err());
+
+ assert_eq!(DROPPED.load(Ordering::Relaxed), 1);
+
+ assert!(matches!(builder.take(), Some(_)));
+
+ assert_eq!(DROPPED.load(Ordering::Relaxed), 3);
+
+ builder.push(TrackedDrop);
+ builder.push(TrackedDrop);
+
+ assert!(matches!(builder.take(), Some(_)));
+
+ assert_eq!(DROPPED.swap(0, Ordering::Relaxed), 5);
+ }
+ }
+}
diff --git a/crates/itertools/src/peeking_take_while.rs b/crates/itertools/src/peeking_take_while.rs
index 19872a9..f3259a9 100644
--- a/crates/itertools/src/peeking_take_while.rs
+++ b/crates/itertools/src/peeking_take_while.rs
@@ -22,7 +22,7 @@
F: FnOnce(&Self::Item) -> bool;
}
-impl<'a, I> PeekingNext for &'a mut I
+impl<I> PeekingNext for &mut I
where
I: PeekingNext,
{
@@ -133,7 +133,7 @@
PeekingTakeWhile { iter, f }
}
-impl<'a, I, F> Iterator for PeekingTakeWhile<'a, I, F>
+impl<I, F> Iterator for PeekingTakeWhile<'_, I, F>
where
I: PeekingNext,
F: FnMut(&I::Item) -> bool,
@@ -148,7 +148,7 @@
}
}
-impl<'a, I, F> PeekingNext for PeekingTakeWhile<'a, I, F>
+impl<I, F> PeekingNext for PeekingTakeWhile<'_, I, F>
where
I: PeekingNext,
F: FnMut(&I::Item) -> bool,
diff --git a/crates/itertools/src/process_results_impl.rs b/crates/itertools/src/process_results_impl.rs
index ad6c60d..31389c5 100644
--- a/crates/itertools/src/process_results_impl.rs
+++ b/crates/itertools/src/process_results_impl.rs
@@ -13,7 +13,7 @@
iter: I,
}
-impl<'a, I, E> ProcessResults<'a, I, E> {
+impl<I, E> ProcessResults<'_, I, E> {
#[inline(always)]
fn next_body<T>(&mut self, item: Option<Result<T, E>>) -> Option<T> {
match item {
@@ -27,7 +27,7 @@
}
}
-impl<'a, I, T, E> Iterator for ProcessResults<'a, I, E>
+impl<I, T, E> Iterator for ProcessResults<'_, I, E>
where
I: Iterator<Item = Result<T, E>>,
{
@@ -60,7 +60,7 @@
}
}
-impl<'a, I, T, E> DoubleEndedIterator for ProcessResults<'a, I, E>
+impl<I, T, E> DoubleEndedIterator for ProcessResults<'_, I, E>
where
I: Iterator<Item = Result<T, E>>,
I: DoubleEndedIterator,
diff --git a/crates/itertools/src/rciter_impl.rs b/crates/itertools/src/rciter_impl.rs
index e3b7532..96a0fd6 100644
--- a/crates/itertools/src/rciter_impl.rs
+++ b/crates/itertools/src/rciter_impl.rs
@@ -87,7 +87,7 @@
}
/// Return an iterator from `&RcIter<I>` (by simply cloning it).
-impl<'a, I> IntoIterator for &'a RcIter<I>
+impl<I> IntoIterator for &RcIter<I>
where
I: Iterator,
{
diff --git a/crates/itertools/src/zip_eq_impl.rs b/crates/itertools/src/zip_eq_impl.rs
index 6d3b682..3240a40 100644
--- a/crates/itertools/src/zip_eq_impl.rs
+++ b/crates/itertools/src/zip_eq_impl.rs
@@ -21,6 +21,7 @@
/// let data = [1, 2, 3, 4, 5];
/// for (a, b) in zip_eq(&data[..data.len() - 1], &data[1..]) {
/// /* loop body */
+/// # let _ = (a, b);
/// }
/// ```
pub fn zip_eq<I, J>(i: I, j: J) -> ZipEq<I::IntoIter, J::IntoIter>
diff --git a/crates/itertools/tests/macros_hygiene.rs b/crates/itertools/tests/macros_hygiene.rs
index 20b59fb..e6e8955 100644
--- a/crates/itertools/tests/macros_hygiene.rs
+++ b/crates/itertools/tests/macros_hygiene.rs
@@ -1,3 +1,8 @@
+mod alloc {}
+mod core {}
+mod either {}
+mod std {}
+
#[test]
fn iproduct_hygiene() {
let _ = itertools::iproduct!();
@@ -12,3 +17,11 @@
let _ = itertools::izip!(0..6, 0..9);
let _ = itertools::izip!(0..6, 0..9, 0..12);
}
+
+#[test]
+fn chain_hygiene() {
+ let _: ::std::iter::Empty<i32> = itertools::chain!();
+ let _ = itertools::chain!(0..6);
+ let _ = itertools::chain!(0..6, 0..9);
+ let _ = itertools::chain!(0..6, 0..9, 0..12);
+}
diff --git a/crates/itertools/tests/quick.rs b/crates/itertools/tests/quick.rs
index 5b8fd6a..672901e 100644
--- a/crates/itertools/tests/quick.rs
+++ b/crates/itertools/tests/quick.rs
@@ -2,7 +2,11 @@
//! and adaptors.
//!
//! In particular we test the tedious size_hint and exact size correctness.
+//!
+//! **NOTE:** Due to performance limitations, these tests are not run with miri!
+//! They cannot be relied upon to discover soundness issues.
+#![cfg(not(miri))]
#![allow(deprecated, unstable_name_collisions)]
use itertools::free::{
@@ -253,7 +257,6 @@
let mut it = get_it();
for _ in 0..(counts.len() - 1) {
- #[allow(clippy::manual_assert)]
if it.next().is_none() {
panic!("Iterator shouldn't be finished, may not be deterministic");
}
@@ -1512,13 +1515,12 @@
acc + val
});
- // TODO: Swap `fold1` with stdlib's `reduce` when it's stabilized
let group_map_lookup = a.iter()
.map(|&b| b as u64)
.map(|i| (i % modulo, i))
.into_group_map()
.into_iter()
- .map(|(key, vals)| (key, vals.into_iter().fold1(|acc, val| acc + val).unwrap()))
+ .map(|(key, vals)| (key, vals.into_iter().reduce(|acc, val| acc + val).unwrap()))
.collect::<HashMap<_,_>>();
assert_eq!(lookup, group_map_lookup);
diff --git a/crates/itertools/tests/specializations.rs b/crates/itertools/tests/specializations.rs
index 7123114..e6694c8 100644
--- a/crates/itertools/tests/specializations.rs
+++ b/crates/itertools/tests/specializations.rs
@@ -1,3 +1,10 @@
+//! Test specializations of methods with default impls match the behavior of the
+//! default impls.
+//!
+//! **NOTE:** Due to performance limitations, these tests are not run with miri!
+//! They cannot be relied upon to discover soundness issues.
+
+#![cfg(not(miri))]
#![allow(unstable_name_collisions)]
use itertools::Itertools;
@@ -266,6 +273,16 @@
test_specializations(&v.into_iter().intersperse_with(|| 0));
}
+ fn array_combinations(v: Vec<u8>) -> TestResult {
+ if v.len() > 10 {
+ return TestResult::discard();
+ }
+ test_specializations(&v.iter().array_combinations::<1>());
+ test_specializations(&v.iter().array_combinations::<2>());
+ test_specializations(&v.iter().array_combinations::<3>());
+ TestResult::passed()
+ }
+
fn combinations(a: Vec<u8>, n: u8) -> TestResult {
if n > 3 || a.len() > 8 {
return TestResult::discard();
@@ -447,11 +464,15 @@
}
fn filter_ok(v: Vec<Result<u8, char>>) -> () {
- test_specializations(&v.into_iter().filter_ok(|&i| i < 20));
+ let it = v.into_iter().filter_ok(|&i| i < 20);
+ test_specializations(&it);
+ test_double_ended_specializations(&it);
}
fn filter_map_ok(v: Vec<Result<u8, char>>) -> () {
- test_specializations(&v.into_iter().filter_map_ok(|i| if i < 20 { Some(i * 2) } else { None }));
+ let it = v.into_iter().filter_map_ok(|i| if i < 20 { Some(i * 2) } else { None });
+ test_specializations(&it);
+ test_double_ended_specializations(&it);
}
// `SmallIter2<u8>` because `Vec<u8>` is too slow and we get bad coverage from a singleton like Option<u8>
diff --git a/crates/itertools/tests/test_core.rs b/crates/itertools/tests/test_core.rs
index 32af246..4936160 100644
--- a/crates/itertools/tests/test_core.rs
+++ b/crates/itertools/tests/test_core.rs
@@ -372,3 +372,28 @@
assert_eq!(v[1..3].iter().cloned().product1::<i32>(), Some(2));
assert_eq!(v[1..5].iter().cloned().product1::<i32>(), Some(24));
}
+
+#[test]
+fn next_array() {
+ let v = [1, 2, 3, 4, 5];
+ let mut iter = v.iter();
+ assert_eq!(iter.next_array(), Some([]));
+ assert_eq!(iter.next_array().map(|[&x, &y]| [x, y]), Some([1, 2]));
+ assert_eq!(iter.next_array().map(|[&x, &y]| [x, y]), Some([3, 4]));
+ assert_eq!(iter.next_array::<2>(), None);
+}
+
+#[test]
+fn collect_array() {
+ let v = [1, 2];
+ let iter = v.iter().cloned();
+ assert_eq!(iter.collect_array(), Some([1, 2]));
+
+ let v = [1];
+ let iter = v.iter().cloned();
+ assert_eq!(iter.collect_array::<2>(), None);
+
+ let v = [1, 2, 3];
+ let iter = v.iter().cloned();
+ assert_eq!(iter.collect_array::<2>(), None);
+}
diff --git a/crates/itertools/tests/test_std.rs b/crates/itertools/tests/test_std.rs
index 00246d5..ad391fa 100644
--- a/crates/itertools/tests/test_std.rs
+++ b/crates/itertools/tests/test_std.rs
@@ -491,6 +491,7 @@
it::assert_equal(v, vec![4, 3, 2, 1, 0]);
}
+#[cfg(not(miri))]
qc::quickcheck! {
fn k_smallest_range(n: i64, m: u16, k: u16) -> () {
// u16 is used to constrain k and m to 0..2¹⁶,
@@ -527,6 +528,42 @@
it::assert_equal(largest_by, sorted_largest.clone());
it::assert_equal(largest_by_key, sorted_largest);
}
+
+ fn k_smallest_relaxed_range(n: i64, m: u16, k: u16) -> () {
+ // u16 is used to constrain k and m to 0..2¹⁶,
+ // otherwise the test could use too much memory.
+ let (k, m) = (k as usize, m as u64);
+
+ let mut v: Vec<_> = (n..n.saturating_add(m as _)).collect();
+ // Generate a random permutation of n..n+m
+ v.shuffle(&mut thread_rng());
+
+ // Construct the right answers for the top and bottom elements
+ let mut sorted = v.clone();
+ sorted.sort();
+ // how many elements are we checking
+ let num_elements = min(k, m as _);
+
+ // Compute the top and bottom k in various combinations
+ let sorted_smallest = sorted[..num_elements].iter().cloned();
+ let smallest = v.iter().cloned().k_smallest_relaxed(k);
+ let smallest_by = v.iter().cloned().k_smallest_relaxed_by(k, Ord::cmp);
+ let smallest_by_key = v.iter().cloned().k_smallest_relaxed_by_key(k, |&x| x);
+
+ let sorted_largest = sorted[sorted.len() - num_elements..].iter().rev().cloned();
+ let largest = v.iter().cloned().k_largest_relaxed(k);
+ let largest_by = v.iter().cloned().k_largest_relaxed_by(k, Ord::cmp);
+ let largest_by_key = v.iter().cloned().k_largest_relaxed_by_key(k, |&x| x);
+
+ // Check the variations produce the same answers and that they're right
+ it::assert_equal(smallest, sorted_smallest.clone());
+ it::assert_equal(smallest_by, sorted_smallest.clone());
+ it::assert_equal(smallest_by_key, sorted_smallest);
+
+ it::assert_equal(largest, sorted_largest.clone());
+ it::assert_equal(largest_by, sorted_largest.clone());
+ it::assert_equal(largest_by_key, sorted_largest);
+ }
}
#[derive(Clone, Debug)]
@@ -571,8 +608,11 @@
I::Item: Ord + Debug,
{
let j = i.clone();
+ let i1 = i.clone();
+ let j1 = i.clone();
let k = k as usize;
- it::assert_equal(i.k_smallest(k), j.sorted().take(k))
+ it::assert_equal(i.k_smallest(k), j.sorted().take(k));
+ it::assert_equal(i1.k_smallest_relaxed(k), j1.sorted().take(k));
}
// Similar to `k_smallest_sort` but for our custom heap implementation.
@@ -582,8 +622,11 @@
I::Item: Ord + Debug,
{
let j = i.clone();
+ let i1 = i.clone();
+ let j1 = i.clone();
let k = k as usize;
- it::assert_equal(i.k_smallest_by(k, Ord::cmp), j.sorted().take(k))
+ it::assert_equal(i.k_smallest_by(k, Ord::cmp), j.sorted().take(k));
+ it::assert_equal(i1.k_smallest_relaxed_by(k, Ord::cmp), j1.sorted().take(k));
}
macro_rules! generic_test {
@@ -598,7 +641,9 @@
};
}
+#[cfg(not(miri))]
generic_test!(k_smallest_sort, u8, u16, u32, u64, i8, i16, i32, i64);
+#[cfg(not(miri))]
generic_test!(k_smallest_by_sort, u8, u16, u32, u64, i8, i16, i32, i64);
#[test]
@@ -1055,8 +1100,8 @@
#[test]
fn combinations_range_count() {
- for n in 0..=10 {
- for k in 0..=10 {
+ for n in 0..=7 {
+ for k in 0..=7 {
let len = binomial(n, k);
let mut it = (0..n).combinations(k);
assert_eq!(len, it.clone().count());
@@ -1077,7 +1122,7 @@
#[test]
fn combinations_inexact_size_hints() {
- for k in 0..=10 {
+ for k in 0..=7 {
let mut numbers = (0..18).filter(|i| i % 2 == 0); // 9 elements
let mut it = numbers.clone().combinations(k);
let real_n = numbers.clone().count();
@@ -1129,8 +1174,8 @@
#[test]
fn permutations_range_count() {
- for n in 0..=7 {
- for k in 0..=7 {
+ for n in 0..=4 {
+ for k in 0..=4 {
let len = if k <= n { (n - k + 1..=n).product() } else { 0 };
let mut it = (0..n).permutations(k);
assert_eq!(len, it.clone().count());
@@ -1162,6 +1207,7 @@
}
#[test]
+#[cfg(not(miri))]
fn combinations_with_replacement() {
// Pool smaller than n
it::assert_equal((0..1).combinations_with_replacement(2), vec![vec![0, 0]]);
@@ -1190,8 +1236,8 @@
#[test]
fn combinations_with_replacement_range_count() {
- for n in 0..=7 {
- for k in 0..=7 {
+ for n in 0..=4 {
+ for k in 0..=4 {
let len = binomial(usize::saturating_sub(n + k, 1), k);
let mut it = (0..n).combinations_with_replacement(k);
assert_eq!(len, it.clone().count());
@@ -1236,7 +1282,7 @@
assert_eq!((0..8).powerset().count(), 1 << 8);
assert_eq!((0..16).powerset().count(), 1 << 16);
- for n in 0..=10 {
+ for n in 0..=4 {
let mut it = (0..n).powerset();
let len = 2_usize.pow(n);
assert_eq!(len, it.clone().count());
diff --git a/crates/itertools/tests/zip.rs b/crates/itertools/tests/zip.rs
index 716ac20..daed31e 100644
--- a/crates/itertools/tests/zip.rs
+++ b/crates/itertools/tests/zip.rs
@@ -20,7 +20,7 @@
let v: &[_] = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
let v2 = &[10, 11, 12];
- assert_eq!(c.zip_longest(v.iter()).size_hint(), (std::usize::MAX, None));
+ assert_eq!(c.zip_longest(v.iter()).size_hint(), (usize::MAX, None));
assert_eq!(v.iter().zip_longest(v2.iter()).size_hint(), (10, Some(10)));
}
diff --git a/pseudo_crate/Cargo.lock b/pseudo_crate/Cargo.lock
index 39eaecd..4dd188c 100644
--- a/pseudo_crate/Cargo.lock
+++ b/pseudo_crate/Cargo.lock
@@ -241,7 +241,7 @@
"inotify-sys",
"instant",
"intrusive-collections",
- "itertools 0.13.0",
+ "itertools 0.14.0",
"itoa",
"jni",
"jni-sys",
@@ -2771,9 +2771,9 @@
[[package]]
name = "itertools"
-version = "0.13.0"
+version = "0.14.0"
source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "413ee7dfc52ee1a4949ceeb7dbc8a33f2d6c088194d9f922fb8318faf1f01186"
+checksum = "2b192c782037fadd9cfa75548310488aabdbf3d2da73885b31bd0abd03351285"
dependencies = [
"either",
]
diff --git a/pseudo_crate/Cargo.toml b/pseudo_crate/Cargo.toml
index 419e9da..44fdb9d 100644
--- a/pseudo_crate/Cargo.toml
+++ b/pseudo_crate/Cargo.toml
@@ -156,7 +156,7 @@
inotify-sys = "=0.1.5"
instant = "=0.1.12"
intrusive-collections = "=0.9.7"
-itertools = "=0.13.0"
+itertools = "=0.14.0"
itoa = "=1.0.14"
jni = "=0.21.1"
jni-sys = "=0.3.0"
