🎩 You're Invited:Meet the Socket team at Black Hat in Las Vegas, August 3-6.RSVP →
im-rc - cargo Package Compare versions
+2
-6
@@ -5,5 +5,2 @@ // This Source Code Form is subject to the terms of the Mozilla Public | ||
| extern crate rustc_version; | ||
| use rustc_version::{version_meta, Channel}; | ||
| use std::env; | ||
@@ -13,7 +10,6 @@ | ||
| println!("cargo:rerun-if-changed=build.rs"); | ||
| match version_meta().unwrap().channel { | ||
| Channel::Nightly => { | ||
| if let Some(channel) = version_check::Channel::read() { | ||
| if channel.supports_features() { | ||
| println!("cargo:rustc-cfg=has_specialisation"); | ||
| } | ||
| _ => (), | ||
| } | ||
@@ -20,0 +16,0 @@ let pkgname = env::var("CARGO_PKG_NAME").expect("Cargo didn't set the CARGO_PKG_NAME env var!"); |
+16
-9
@@ -16,3 +16,3 @@ # THIS FILE IS AUTOMATICALLY GENERATED BY CARGO | ||
| name = "im-rc" | ||
| version = "13.0.0" | ||
| version = "14.0.0" | ||
| authors = ["Bodil Stokke <bodil@bodil.org>"] | ||
@@ -31,2 +31,5 @@ build = "./build.rs" | ||
| path = "./src/lib.rs" | ||
| [dependencies.bitmaps] | ||
| version = "2.0.0" | ||
| [dependencies.proptest] | ||
@@ -37,5 +40,11 @@ version = "0.9" | ||
| [dependencies.quickcheck] | ||
| version = "0.8" | ||
| version = "0.9" | ||
| optional = true | ||
| [dependencies.rand_core] | ||
| version = "0.5.1" | ||
| [dependencies.rand_xoshiro] | ||
| version = "0.4.0" | ||
| [dependencies.rayon] | ||
@@ -50,3 +59,3 @@ version = "1.0" | ||
| [dependencies.sized-chunks] | ||
| version = "0.3.0" | ||
| version = "0.5.0" | ||
@@ -68,3 +77,4 @@ [dependencies.typenum] | ||
| [dev-dependencies.rand] | ||
| version = "0.6" | ||
| version = "0.7" | ||
| features = ["small_rng"] | ||
@@ -79,8 +89,5 @@ [dev-dependencies.rayon] | ||
| version = "1.0" | ||
| [dev-dependencies.syntect] | ||
| version = "3.1.0" | ||
| [build-dependencies.rustc_version] | ||
| version = "0.2" | ||
| [build-dependencies.version_check] | ||
| version = "0.9" | ||
| [badges.travis-ci] | ||
| repository = "bodil/im-rs" |
+14
-0
@@ -9,2 +9,16 @@ # Changelog | ||
| ## [14.0.0] - 2019-11-19 | ||
| ### Changed | ||
| - As `sized-chunks` now requires a slightly more recent version of `rustc` to | ||
| compile, specifically version 1.36.0, so does `im`. This is a breaking change, | ||
| but will of course only affect your code if you're using an older `rustc`. | ||
| ### Fixed | ||
| - Fixed a quadratic time worst case scenario in the quicksort implementation for | ||
| `Vector`. (#101) | ||
| - Fixed an edge case bug when splitting and joining large `Vector`s. (#105, #107) | ||
| ## [13.0.0] - 2019-05-18 | ||
@@ -11,0 +25,0 @@ |
@@ -9,1 +9,2 @@ # Seeds for failure cases proptest has generated in the past. It is | ||
| cc bae4a6aa243531a345cb36883fda4aebc84848fffe12d051df4e24ff22af3689 # shrinks to actions = let mut vec = Vector::new(); let mut vec_new = Vector::from([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]); vec_new.append(vec); vec = vec_new; vec = vec.split_off(6); vec.pop_front(); vec.pop_front(); vec.push_front(0); vec.pop_front(); vec.push_front(0); vec.append(Vector::from([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])); vec.split_off(141); let mut vec_new = Vector::from([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]); vec_new.append(vec); vec = vec_new; vec.insert(41, 0); vec.pop_front(); vec.pop_front(); vec = vec.split_off(5); vec.pop_front(); vec.append(Vector::from([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])); vec.append(Vector::from([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1])); vec.push_front(0); vec.push_front(0); let mut vec_new = Vector::from([0]); vec_new.append(vec); vec = vec_new; | ||
| cc 2c8368d1e6fe86c9b944a688cc167d961767ffb028ca724bb3c12e2716cbfbf9 # shrinks to actions = let mut vec = Vector::new(); let mut vec_new = Vector::from(vec![0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]); // size 70 vec_new.append(vec); vec = vec_new; // len = 70 vec.append(Vector::from(vec![0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 53, 59, 108, 189, 95, 24, 92, 116, 211, 64, 195, 2, 58, 198, 130, 44, 163, 180, 50, 176, 78, 24, 2, 180, 91, 132, 176, 205, 155, 65, 228, 182, 175, 100, 204, 222])); // size 61 // len = 131 vec.insert(8, 88); // len = 132 vec.push_back(252); // len = 133 vec.insert(1, 65); // len = 134 let mut vec_new = Vector::from(vec![57, 103, 160, 147, 241, 248, 112, 54, 152, 245, 195, 156, 245, 143, 175, 51, 27, 183, 236, 77, 126, 27, 160, 172, 73, 179]); // size 26 vec_new.append(vec); vec = vec_new; // len = 160 vec.insert(0, 112); // len = 161 let mut vec_new = Vector::from(vec![191, 78, 196, 239, 181, 187, 82, 160]); // size 8 vec_new.append(vec); vec = vec_new; // len = 169 vec.pop_front(); // len = 168 vec.pop_back(); // len = 167 vec.insert(153, 32); // len = 168 vec.split_off(10); // len = 10 vec.insert(6, 131); // len = 11 vec.pop_front(); // len = 10 vec.insert(4, 235); // len = 11 vec.remove(8) // len = 10 vec.insert(6, 48); // len = 11 vec.insert(3, 194); // len = 12 vec.push_back(31); // len = 13 vec.pop_front(); // len = 12 vec.push_front(96); // len = 13 vec.push_back(77); // len = 14 vec.append(Vector::from(vec![70, 240, 146, 141, 164, 160, 150, 102, 163, 137, 14, 197, 249, 2, 249, 52, 9, 203, 50, 161, 148, 209, 86, 161, 34, 32, 189, 39, 208, 106, 47, 100, 194, 160, 147, 69, 4, 249, 250, 77, 73, 181, 49, 228, 141, 195, 210, 102, 73, 75, 167, 106, 233, 141, 182, 243, 42, 102, 166, 184, 248, 127, 120, 88, 246, 204, 127, 214, 30, 201, 205, 115, 28, 204, 26, 17, 67, 228, 44, 158, 15, 79, 141, 86, 101, 148, 76, 44, 216, 65])); // size 90 // len = 104 let mut vec_new = Vector::from(vec![123, 94, 60, 147, 41, 173, 214, 101, 145, 201, 69, 78, 61, 38, 60, 170, 56, 33, 65, 151, 28, 93, 16, 187, 49, 103, 52, 133, 253, 244, 125, 66, 56, 190, 17, 235, 117, 101, 212, 129, 170, 112, 203, 78, 217, 49, 176, 252, 8, 153, 178, 205, 211, 165, 197, 32, 171, 224, 17, 127, 56, 45, 36, 248, 66, 126, 110, 109, 94, 116, 189, 185, 24, 215, 87, 239, 248, 98, 134, 0, 249, 147, 197, 237, 6, 150, 30, 51, 149, 12, 31, 93, 95, 158, 229]); // size 95 vec_new.append(vec); vec = vec_new; // len = 199 vec.append(Vector::from(vec![127, 142, 241, 16, 254, 11, 153, 252, 3, 104, 61, 225, 73, 56, 149, 247, 142, 67, 4, 24, 96, 169, 234, 215, 227, 30, 84, 45, 209])); // size 29 // len = 228 vec.append(Vector::from(vec![194, 101, 202, 247, 108, 248, 86, 224, 255, 187, 50, 123, 93, 110, 63, 83, 122, 101, 48, 38])); // size 20 // len = 248 vec.push_front(80); // len = 249 vec.append(Vector::from(vec![228, 25, 146, 89, 230, 224, 101])); // size 7 // len = 256 let mut vec_new = Vector::from(vec![89, 252, 187, 201, 31, 229, 16, 211, 172, 223, 209, 123, 120, 100, 91, 241, 223, 42, 71, 212, 42, 113, 211, 128, 54, 142]); // size 26 vec_new.append(vec); vec = vec_new; // len = 282 vec = vec.split_off(188); // len = 94 let expected = vec![233, 141, 182, 243, 42, 102, 166, 184, 248, 127, 120, 88, 246, 204, 127, 214, 30, 201, 205, 115, 28, 204, 26, 17, 67, 228, 44, 158, 15, 79, 141, 86, 101, 148, 76, 44, 216, 65, 127, 142, 241, 16, 254, 11, 153, 252, 3, 104, 61, 225, 73, 56, 149, 247, 142, 67, 4, 24, 96, 169, 234, 215, 227, 30, 84, 45, 209, 194, 101, 202, 247, 108, 248, 86, 224, 255, 187, 50, 123, 93, 110, 63, 83, 122, 101, 48, 38, 228, 25, 146, 89, 230, 224, 101]; assert_eq!(Vector::from(expected), vec); |
+6
-0
@@ -1001,2 +1001,4 @@ // This Source Code Form is subject to the terms of the Mozilla Public | ||
| /// ``` | ||
| /// | ||
| /// [symmetric_difference]: #method.symmetric_difference | ||
| #[inline] | ||
@@ -1038,2 +1040,4 @@ #[must_use] | ||
| /// Time: O(n log n) | ||
| /// | ||
| /// [symmetric_difference_with]: #method.symmetric_difference_with | ||
| #[inline] | ||
@@ -1086,2 +1090,4 @@ #[must_use] | ||
| /// ``` | ||
| /// | ||
| /// [symmetric_difference_with_key]: #method.symmetric_difference_with_key | ||
| #[must_use] | ||
@@ -1088,0 +1094,0 @@ pub fn difference_with_key<F>(self, other: Self, f: F) -> Self |
+2
-0
@@ -509,2 +509,4 @@ // This Source Code Form is subject to the terms of the Mozilla Public | ||
| /// ``` | ||
| /// | ||
| /// [symmetric_difference]: #method.symmetric_difference | ||
| #[must_use] | ||
@@ -511,0 +513,0 @@ pub fn difference(self, other: Self) -> Self { |
+4
-4
@@ -223,4 +223,4 @@ // This Source Code Form is subject to the terms of the Mozilla Public | ||
| //! | Type | Algorithm | Constraints | Order | Push | Pop | Split | Append | Lookup | | ||
| //! | --- | --- | --- | --- | --- | --- | --- | | ||
| //! | [`Vector<A>`][vector::Vector] | [RRB tree][rrb-tree] | [`Clone`][std::clone::Clone] | insertion | O(1)* | O(1)* | O(log n) | O(log n) | O(log n) | | ||
| //! | --- | --- | --- | --- | --- | --- | --- | --- | --- | | ||
| //! | [`Vector<A>`][vector::Vector] | [RRB tree][rrb-tree] | [`Clone`][std::clone::Clone] | insertion | O(1)\* | O(1)\* | O(log n) | O(log n) | O(log n) | | ||
| //! | ||
@@ -236,3 +236,3 @@ //! ### Maps | ||
| //! | Type | Algorithm | Key Constraints | Order | Insert | Remove | Lookup | | ||
| //! | --- | --- | --- | --- | --- | --- | | ||
| //! | --- | --- | --- | --- | --- | --- | --- | | ||
| //! | [`HashMap<K, V>`][hashmap::HashMap] | [HAMT][hamt] | [`Clone`][std::clone::Clone] + [`Hash`][std::hash::Hash] + [`Eq`][std::cmp::Eq] | undefined | O(log n) | O(log n) | O(log n) | | ||
@@ -248,3 +248,3 @@ //! | [`OrdMap<K, V>`][ordmap::OrdMap] | [B-tree][b-tree] | [`Clone`][std::clone::Clone] + [`Ord`][std::cmp::Ord] | sorted | O(log n) | O(log n) | O(log n) | | ||
| //! | Type | Algorithm | Constraints | Order | Insert | Remove | Lookup | | ||
| //! | --- | --- | --- | --- | --- | --- | | ||
| //! | --- | --- | --- | --- | --- | --- | --- | | ||
| //! | [`HashSet<A>`][hashset::HashSet] | [HAMT][hamt] | [`Clone`][std::clone::Clone] + [`Hash`][std::hash::Hash] + [`Eq`][std::cmp::Eq] | undefined | O(log n) | O(log n) | O(log n) | | ||
@@ -251,0 +251,0 @@ //! | [`OrdSet<A>`][ordset::OrdSet] | [B-tree][b-tree] | [`Clone`][std::clone::Clone] + [`Ord`][std::cmp::Ord] | sorted | O(log n) | O(log n) | O(log n) | |
@@ -10,6 +10,6 @@ // This Source Code Form is subject to the terms of the Mozilla Public | ||
| use sized_chunks::Chunk; | ||
| use typenum::{Add1, Unsigned}; | ||
| use crate::config::OrdChunkSize as NodeSize; | ||
| use crate::nodes::sized_chunk::Chunk; | ||
| use crate::util::{clone_ref, Ref}; | ||
@@ -127,3 +127,3 @@ | ||
| #[inline] | ||
| pub fn from_split(left: Node<A>, median: A, right: Node<A>) -> Self { | ||
| pub fn new_from_split(left: Node<A>, median: A, right: Node<A>) -> Self { | ||
| Node { | ||
@@ -577,3 +577,3 @@ keys: Chunk::unit(median), | ||
| let mut update = None; | ||
| let mut value; | ||
| let value; | ||
| if let Some(&mut Some(ref mut child_ref)) = children.get_mut(child_index) { | ||
@@ -619,3 +619,3 @@ let child = Ref::make_mut(child_ref); | ||
| let mut update = None; | ||
| let mut out_value; | ||
| let out_value; | ||
| { | ||
@@ -666,3 +666,3 @@ let mut children = self.children.as_mut_slice()[index - 1..=index] | ||
| let mut update = None; | ||
| let mut out_value; | ||
| let out_value; | ||
| { | ||
@@ -719,4 +719,4 @@ let mut children = self.children.as_mut_slice()[index..index + 2] | ||
| let mut merged = Node::merge(middle, clone_ref(left), clone_ref(right)); | ||
| let mut update; | ||
| let mut out_value; | ||
| let update; | ||
| let out_value; | ||
| match merged.remove(key) { | ||
@@ -746,3 +746,3 @@ Remove::NoChange => { | ||
| let mut update = None; | ||
| let mut out_value; | ||
| let out_value; | ||
| if let Some(&mut Some(ref mut child_ref)) = self.children.get_mut(index) { | ||
@@ -749,0 +749,0 @@ let child = Ref::make_mut(child_ref); |
@@ -12,7 +12,7 @@ // This Source Code Form is subject to the terms of the Mozilla Public | ||
| use bitmaps::Bits; | ||
| use sized_chunks::sparse_chunk::{Iter as ChunkIter, IterMut as ChunkIterMut, SparseChunk}; | ||
| use typenum::{Pow, Unsigned, U2}; | ||
| use crate::config::HashLevelSize; | ||
| use crate::nodes::sparse_chunk::{Iter as ChunkIter, IterMut as ChunkIterMut, SparseChunk}; | ||
| use crate::nodes::types::Bits; | ||
| use crate::util::{clone_ref, Ref}; | ||
@@ -19,0 +19,0 @@ |
+0
-2
@@ -9,4 +9,2 @@ // This Source Code Form is subject to the terms of the Mozilla Public | ||
| pub use sized_chunks::*; | ||
| pub mod chunk { | ||
@@ -13,0 +11,0 @@ use crate::config::VectorChunkSize; |
+95
-38
@@ -65,5 +65,11 @@ // This Source Code Form is subject to the terms of the Mozilla Public | ||
| fn push(&mut self, side: Side, value: usize) { | ||
| match self { | ||
| Size::Size(ref mut size) => *size += value, | ||
| fn push(&mut self, side: Side, level: usize, value: usize) { | ||
| let size = match self { | ||
| Size::Size(ref mut size) => match side { | ||
| Left => *size, | ||
| Right => { | ||
| *size += value; | ||
| return; | ||
| } | ||
| }, | ||
| Size::Table(ref mut size_ref) => { | ||
@@ -84,9 +90,18 @@ let size_table = Ref::make_mut(size_ref); | ||
| } | ||
| return; | ||
| } | ||
| } | ||
| }; | ||
| *self = Size::table_from_size(level, size); | ||
| self.push(side, level, value); | ||
| } | ||
| fn pop(&mut self, side: Side, value: usize) { | ||
| match self { | ||
| Size::Size(ref mut size) => *size -= value, | ||
| fn pop(&mut self, side: Side, level: usize, value: usize) { | ||
| let size = match self { | ||
| Size::Size(ref mut size) => match side { | ||
| Left => *size, | ||
| Right => { | ||
| *size -= value; | ||
| return; | ||
| } | ||
| }, | ||
| Size::Table(ref mut size_ref) => { | ||
@@ -108,9 +123,12 @@ let size_table = Ref::make_mut(size_ref); | ||
| } | ||
| return; | ||
| } | ||
| } | ||
| }; | ||
| *self = Size::table_from_size(level, size); | ||
| self.pop(side, level, value); | ||
| } | ||
| fn update(&mut self, index: usize, value: isize) { | ||
| match self { | ||
| Size::Size(ref mut size) => *size = (*size as isize + value) as usize, | ||
| fn update(&mut self, index: usize, level: usize, value: isize) { | ||
| let size = match self { | ||
| Size::Size(ref size) => *size, | ||
| Size::Table(ref mut size_ref) => { | ||
@@ -121,4 +139,7 @@ let size_table = Ref::make_mut(size_ref); | ||
| } | ||
| return; | ||
| } | ||
| } | ||
| }; | ||
| *self = Size::table_from_size(level, size); | ||
| self.update(index, level, value); | ||
| } | ||
@@ -274,3 +295,3 @@ } | ||
| } | ||
| size.push(Right, child.len()) | ||
| size.push(Right, level, child.len()) | ||
| } | ||
@@ -402,5 +423,5 @@ } | ||
| #[inline] | ||
| fn push_size(&mut self, side: Side, value: usize) { | ||
| fn push_size(&mut self, side: Side, level: usize, value: usize) { | ||
| if let Entry::Nodes(ref mut size, _) = self.children { | ||
| size.push(side, value) | ||
| size.push(side, level, value) | ||
| } | ||
@@ -410,5 +431,5 @@ } | ||
| #[inline] | ||
| fn pop_size(&mut self, side: Side, value: usize) { | ||
| fn pop_size(&mut self, side: Side, level: usize, value: usize) { | ||
| if let Entry::Nodes(ref mut size, _) = self.children { | ||
| size.pop(side, value) | ||
| size.pop(side, level, value) | ||
| } | ||
@@ -418,5 +439,5 @@ } | ||
| #[inline] | ||
| fn update_size(&mut self, index: usize, value: isize) { | ||
| fn update_size(&mut self, index: usize, level: usize, value: isize) { | ||
| if let Entry::Nodes(ref mut size, _) = self.children { | ||
| size.update(index, value) | ||
| size.update(index, level, value) | ||
| } | ||
@@ -547,3 +568,3 @@ } | ||
| if self.children.is_empty_node() { | ||
| self.push_size(side, chunk.len()); | ||
| self.push_size(side, level, chunk.len()); | ||
| self.children = Values(chunk); | ||
@@ -579,4 +600,4 @@ PushResult::Done | ||
| values.drain_from_front(chunk, to_drain); | ||
| size.pop(Side::Right, old_size); | ||
| size.push(Side::Right, values.len()); | ||
| size.pop(Side::Right, level, old_size); | ||
| size.push(Side::Right, level, values.len()); | ||
| to_drain | ||
@@ -595,4 +616,4 @@ } else { | ||
| values.drain_from_back(chunk, to_drain); | ||
| size.pop(Side::Left, old_size); | ||
| size.push(Side::Left, values.len()); | ||
| size.pop(Side::Left, level, old_size); | ||
| size.push(Side::Left, level, values.len()); | ||
| to_drain | ||
@@ -618,3 +639,3 @@ } else { | ||
| } | ||
| self.push_size(side, chunk.len()); | ||
| self.push_size(side, level, chunk.len()); | ||
| self.push_child_node(side, Ref::new(Node::from_chunk(0, chunk))); | ||
@@ -652,3 +673,3 @@ } | ||
| Left => { | ||
| self.update_size(0, num_drained as isize); | ||
| self.update_size(0, level, num_drained as isize); | ||
| } | ||
@@ -666,3 +687,3 @@ } | ||
| None => { | ||
| self.update_size(index, chunk_size as isize); | ||
| self.update_size(index, level, chunk_size as isize); | ||
| PushResult::Done | ||
@@ -678,3 +699,3 @@ } | ||
| } | ||
| self.push_size(side, child.len()); | ||
| self.push_size(side, level, child.len()); | ||
| self.push_child_node(side, Ref::from(child)); | ||
@@ -700,3 +721,3 @@ PushResult::Done | ||
| let child_node = self.pop_child_node(side); | ||
| self.pop_size(side, child_node.len()); | ||
| self.pop_size(side, level, child_node.len()); | ||
| let chunk = match child_node.children { | ||
@@ -731,3 +752,3 @@ Values(ref chunk) => chunk.clone(), | ||
| if drained { | ||
| self.pop_size(side, chunk.len()); | ||
| self.pop_size(side, level, chunk.len()); | ||
| self.pop_child_node(side); | ||
@@ -740,3 +761,3 @@ if self.is_empty() { | ||
| } else { | ||
| self.update_size(index, -(chunk.len() as isize)); | ||
| self.update_size(index, level, -(chunk.len() as isize)); | ||
| PopResult::Done(chunk) | ||
@@ -749,4 +770,15 @@ } | ||
| if index == 0 && drop_side == Side::Left { | ||
| // Dropped nothing | ||
| return SplitResult::Dropped(0); | ||
| } | ||
| if level > 0 && index == 0 && drop_side == Side::Right { | ||
| // Dropped everything | ||
| let dropped = if let Entry::Nodes(ref size, _) = self.children { | ||
| size.size() | ||
| } else { | ||
| panic!("leaf node at non-leaf level!"); | ||
| }; | ||
| self.children = Entry::Empty; | ||
| return SplitResult::Dropped(dropped); | ||
| } | ||
| let mut dropped; | ||
@@ -826,4 +858,10 @@ if level == 0 { | ||
| let new_size = remainder - dropped; | ||
| dropped = *size - new_size; | ||
| *size = new_size; | ||
| if new_size < *size { | ||
| dropped = *size - new_size; | ||
| *size = new_size; | ||
| } else { | ||
| unreachable!( | ||
| "this means node is empty, should be caught at start of method" | ||
| ); | ||
| } | ||
| } | ||
@@ -962,3 +1000,5 @@ Size::Table(ref mut size_ref) => { | ||
| let node = Ref::make_mut(children).pop_back(); | ||
| size.pop(Side::Right, node.len()); | ||
| if node.len() > 0 { | ||
| size.pop(Side::Right, level, node.len()); | ||
| } | ||
| node | ||
@@ -971,3 +1011,5 @@ } else { | ||
| let node = Ref::make_mut(children).pop_front(); | ||
| size.pop(Side::Left, node.len()); | ||
| if node.len() > 0 { | ||
| size.pop(Side::Left, level, node.len()); | ||
| } | ||
| node | ||
@@ -984,3 +1026,3 @@ } else { | ||
| pub fn assert_invariants(&self) -> usize { | ||
| pub fn assert_invariants(&self, level: usize) -> usize { | ||
| // Verifies that the size table matches reality. | ||
@@ -992,2 +1034,4 @@ match self.children { | ||
| assert_ne!(0, values.len()); | ||
| // Value nodes should only occur at level 0. | ||
| assert_eq!(0, level); | ||
| values.len() | ||
@@ -998,5 +1042,17 @@ } | ||
| assert_ne!(0, children.len()); | ||
| // Parent nodes should never occur at level 0. | ||
| assert_ne!(0, level); | ||
| let mut lengths = Vec::new(); | ||
| for child in &**children { | ||
| lengths.push(child.assert_invariants()); | ||
| let should_be_dense = if let Size::Size(_) = size { | ||
| true | ||
| } else { | ||
| false | ||
| }; | ||
| for (index, child) in children.iter().enumerate() { | ||
| let len = child.assert_invariants(level - 1); | ||
| if should_be_dense && index < children.len() - 1 { | ||
| // Assert that non-end nodes without size tables are full. | ||
| assert_eq!(len, NODE_SIZE.pow(level as u32)); | ||
| } | ||
| lengths.push(len); | ||
| } | ||
@@ -1009,2 +1065,3 @@ match size { | ||
| Size::Table(ref table) => { | ||
| assert_eq!(table.iter().len(), children.len()); | ||
| for (index, current) in table.iter().enumerate() { | ||
@@ -1011,0 +1068,0 @@ let expected: usize = lengths.iter().take(index + 1).sum(); |
+3
-1
@@ -431,3 +431,3 @@ // This Source Code Form is subject to the terms of the Mozilla Public | ||
| Insert::Split(left, median, right) => { | ||
| Ref::from(Node::from_split(left, median, right)) | ||
| Ref::from(Node::new_from_split(left, median, right)) | ||
| } | ||
@@ -610,2 +610,4 @@ } | ||
| /// ``` | ||
| /// | ||
| /// [symmetric_difference]: #method.symmetric_difference | ||
| #[must_use] | ||
@@ -612,0 +614,0 @@ pub fn difference(self, other: Self) -> Self { |
+28
-4
@@ -6,11 +6,23 @@ // This Source Code Form is subject to the terms of the Mozilla Public | ||
| use crate::vector::FocusMut; | ||
| use rand_core::{RngCore, SeedableRng}; | ||
| use std::cmp::Ordering; | ||
| fn gen_range<R: RngCore>(rng: &mut R, min: usize, max: usize) -> usize { | ||
| let range = max - min; | ||
| min + (rng.next_u64() as usize % range) | ||
| } | ||
| // Ported from the Java version at: | ||
| // http://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf | ||
| // Should be O(n) to O(n log n) | ||
| pub fn quicksort<A, F>(vector: &mut FocusMut<A>, left: usize, right: usize, cmp: &F) | ||
| where | ||
| pub fn do_quicksort<A, F, R>( | ||
| vector: &mut FocusMut<A>, | ||
| left: usize, | ||
| right: usize, | ||
| cmp: &F, | ||
| rng: &mut R, | ||
| ) where | ||
| A: Clone, | ||
| F: Fn(&A, &A) -> Ordering, | ||
| R: RngCore, | ||
| { | ||
@@ -23,2 +35,3 @@ if right <= left { | ||
| let r = right as isize; | ||
| let p = gen_range(rng, left, right + 1) as isize; | ||
| let mut l1 = l; | ||
@@ -28,2 +41,4 @@ let mut r1 = r; | ||
| let mut r2 = r; | ||
| vector.swap(r as usize, p as usize); | ||
| loop { | ||
@@ -71,7 +86,16 @@ while l1 != r && vector.pair(l1 as usize, r as usize, |a, b| cmp(a, b)) == Ordering::Less { | ||
| if r1 >= 0 { | ||
| quicksort(vector, left, r1 as usize, cmp); | ||
| do_quicksort(vector, left, r1 as usize, cmp, rng); | ||
| } | ||
| quicksort(vector, l1 as usize, right, cmp); | ||
| do_quicksort(vector, l1 as usize, right, cmp, rng); | ||
| } | ||
| pub fn quicksort<A, F>(vector: &mut FocusMut<A>, left: usize, right: usize, cmp: &F) | ||
| where | ||
| A: Clone, | ||
| F: Fn(&A, &A) -> Ordering, | ||
| { | ||
| let mut rng = rand_xoshiro::Xoshiro256Plus::seed_from_u64(0); | ||
| do_quicksort(vector, left, right, cmp, &mut rng); | ||
| } | ||
| #[cfg(test)] | ||
@@ -78,0 +102,0 @@ mod test { |
+18
-17
@@ -6,19 +6,20 @@ mod hashset; | ||
| fn code_fmt(code: &str) -> String { | ||
| use syntect::easy::HighlightLines; | ||
| use syntect::highlighting::{Style, ThemeSet}; | ||
| use syntect::parsing::SyntaxSet; | ||
| use syntect::util::{as_24_bit_terminal_escaped, LinesWithEndings}; | ||
| let ps = SyntaxSet::load_defaults_newlines(); | ||
| let ts = ThemeSet::load_defaults(); | ||
| let syntax = ps.find_syntax_by_extension("rs").unwrap(); | ||
| let mut h = HighlightLines::new(syntax, &ts.themes["base16-ocean.dark"]); | ||
| let mut out = String::from("\n\n"); | ||
| for line in LinesWithEndings::from(&code) { | ||
| let ranges: Vec<(Style, &str)> = h.highlight(line, &ps); | ||
| let escaped = as_24_bit_terminal_escaped(&ranges[..], false); | ||
| out += &escaped; | ||
| } | ||
| out += "\n\x1b[0m"; | ||
| out | ||
| // use syntect::easy::HighlightLines; | ||
| // use syntect::highlighting::{Style, ThemeSet}; | ||
| // use syntect::parsing::SyntaxSet; | ||
| // use syntect::util::{as_24_bit_terminal_escaped, LinesWithEndings}; | ||
| // | ||
| // let ps = SyntaxSet::load_defaults_newlines(); | ||
| // let ts = ThemeSet::load_defaults(); | ||
| // let syntax = ps.find_syntax_by_extension("rs").unwrap(); | ||
| // let mut h = HighlightLines::new(syntax, &ts.themes["base16-ocean.dark"]); | ||
| // let mut out = String::from("\n\n"); | ||
| // for line in LinesWithEndings::from(&code) { | ||
| // let ranges: Vec<(Style, &str)> = h.highlight(line, &ps); | ||
| // let escaped = as_24_bit_terminal_escaped(&ranges[..], false); | ||
| // out += &escaped; | ||
| // } | ||
| // out += "\n\x1b[0m"; | ||
| // out | ||
| code.to_string() | ||
| } |
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is too big to display
Sorry, the diff of this file is too big to display
No alert changes
No metric changes