1 // This Source Code Form is subject to the terms of the Mozilla Public 2 // License, v. 2.0. If a copy of the MPL was not distributed with this 3 // file, You can obtain one at http://mozilla.org/MPL/2.0/. 4 5 //! An ordered map. 6 //! 7 //! An immutable ordered map implemented as a [B-tree] [1]. 8 //! 9 //! Most operations on this type of map are O(log n). A 10 //! [`HashMap`][hashmap::HashMap] is usually a better choice for 11 //! performance, but the `OrdMap` has the advantage of only requiring 12 //! an [`Ord`][std::cmp::Ord] constraint on the key, and of being 13 //! ordered, so that keys always come out from lowest to highest, 14 //! where a [`HashMap`][hashmap::HashMap] has no guaranteed ordering. 15 //! 16 //! [1]: https://en.wikipedia.org/wiki/B-tree 17 //! [hashmap::HashMap]: ../hashmap/struct.HashMap.html 18 //! [std::cmp::Ord]: https://doc.rust-lang.org/std/cmp/trait.Ord.html 19 20 use std::borrow::Borrow; 21 use std::cmp::Ordering; 22 use std::collections; 23 use std::fmt::{Debug, Error, Formatter}; 24 use std::hash::{BuildHasher, Hash, Hasher}; 25 use std::iter::{FromIterator, Iterator, Sum}; 26 use std::mem; 27 use std::ops::{Add, Index, IndexMut, RangeBounds}; 28 29 use crate::hashmap::HashMap; 30 use crate::nodes::btree::{BTreeValue, Insert, Node, Remove}; 31 #[cfg(has_specialisation)] 32 use crate::util::linear_search_by; 33 use crate::util::{Pool, PoolRef}; 34 35 pub use crate::nodes::btree::{ 36 ConsumingIter, DiffItem as NodeDiffItem, DiffIter as NodeDiffIter, Iter as RangedIter, 37 }; 38 39 /// Construct a map from a sequence of key/value pairs. 40 /// 41 /// # Examples 42 /// 43 /// ``` 44 /// # #[macro_use] extern crate im; 45 /// # use im::ordmap::OrdMap; 46 /// # fn main() { 47 /// assert_eq!( 48 /// ordmap!{ 49 /// 1 => 11, 50 /// 2 => 22, 51 /// 3 => 33 52 /// }, 53 /// OrdMap::from(vec![(1, 11), (2, 22), (3, 33)]) 54 /// ); 55 /// # } 56 /// ``` 57 #[macro_export] 58 macro_rules! ordmap { 59 () => { $crate::ordmap::OrdMap::new() }; 60 61 ( $( $key:expr => $value:expr ),* ) => {{ 62 let mut map = $crate::ordmap::OrdMap::new(); 63 $({ 64 map.insert($key, $value); 65 })*; 66 map 67 }}; 68 } 69 70 #[cfg(not(has_specialisation))] 71 impl<K: Ord, V> BTreeValue for (K, V) { 72 type Key = K; 73 ptr_eq(&self, _other: &Self) -> bool74 fn ptr_eq(&self, _other: &Self) -> bool { 75 false 76 } 77 search_key<BK>(slice: &[Self], key: &BK) -> Result<usize, usize> where BK: Ord + ?Sized, Self::Key: Borrow<BK>,78 fn search_key<BK>(slice: &[Self], key: &BK) -> Result<usize, usize> 79 where 80 BK: Ord + ?Sized, 81 Self::Key: Borrow<BK>, 82 { 83 slice.binary_search_by(|value| Self::Key::borrow(&value.0).cmp(key)) 84 } 85 search_value(slice: &[Self], key: &Self) -> Result<usize, usize>86 fn search_value(slice: &[Self], key: &Self) -> Result<usize, usize> { 87 slice.binary_search_by(|value| value.0.cmp(&key.0)) 88 } 89 cmp_keys<BK>(&self, other: &BK) -> Ordering where BK: Ord + ?Sized, Self::Key: Borrow<BK>,90 fn cmp_keys<BK>(&self, other: &BK) -> Ordering 91 where 92 BK: Ord + ?Sized, 93 Self::Key: Borrow<BK>, 94 { 95 Self::Key::borrow(&self.0).cmp(other) 96 } 97 cmp_values(&self, other: &Self) -> Ordering98 fn cmp_values(&self, other: &Self) -> Ordering { 99 self.0.cmp(&other.0) 100 } 101 } 102 103 #[cfg(has_specialisation)] 104 impl<K: Ord, V> BTreeValue for (K, V) { 105 type Key = K; 106 ptr_eq(&self, _other: &Self) -> bool107 fn ptr_eq(&self, _other: &Self) -> bool { 108 false 109 } 110 search_key<BK>(slice: &[Self], key: &BK) -> Result<usize, usize> where BK: Ord + ?Sized, Self::Key: Borrow<BK>,111 default fn search_key<BK>(slice: &[Self], key: &BK) -> Result<usize, usize> 112 where 113 BK: Ord + ?Sized, 114 Self::Key: Borrow<BK>, 115 { 116 slice.binary_search_by(|value| Self::Key::borrow(&value.0).cmp(key)) 117 } 118 search_value(slice: &[Self], key: &Self) -> Result<usize, usize>119 default fn search_value(slice: &[Self], key: &Self) -> Result<usize, usize> { 120 slice.binary_search_by(|value| value.0.cmp(&key.0)) 121 } 122 cmp_keys<BK>(&self, other: &BK) -> Ordering where BK: Ord + ?Sized, Self::Key: Borrow<BK>,123 fn cmp_keys<BK>(&self, other: &BK) -> Ordering 124 where 125 BK: Ord + ?Sized, 126 Self::Key: Borrow<BK>, 127 { 128 Self::Key::borrow(&self.0).cmp(other) 129 } 130 cmp_values(&self, other: &Self) -> Ordering131 fn cmp_values(&self, other: &Self) -> Ordering { 132 self.0.cmp(&other.0) 133 } 134 } 135 136 #[cfg(has_specialisation)] 137 impl<K: Ord + Copy, V> BTreeValue for (K, V) { search_key<BK>(slice: &[Self], key: &BK) -> Result<usize, usize> where BK: Ord + ?Sized, Self::Key: Borrow<BK>,138 fn search_key<BK>(slice: &[Self], key: &BK) -> Result<usize, usize> 139 where 140 BK: Ord + ?Sized, 141 Self::Key: Borrow<BK>, 142 { 143 linear_search_by(slice, |value| Self::Key::borrow(&value.0).cmp(key)) 144 } 145 search_value(slice: &[Self], key: &Self) -> Result<usize, usize>146 fn search_value(slice: &[Self], key: &Self) -> Result<usize, usize> { 147 linear_search_by(slice, |value| value.0.cmp(&key.0)) 148 } 149 } 150 151 def_pool!(OrdMapPool<K, V>, Node<(K, V)>); 152 153 /// An ordered map. 154 /// 155 /// An immutable ordered map implemented as a B-tree. 156 /// 157 /// Most operations on this type of map are O(log n). A 158 /// [`HashMap`][hashmap::HashMap] is usually a better choice for 159 /// performance, but the `OrdMap` has the advantage of only requiring 160 /// an [`Ord`][std::cmp::Ord] constraint on the key, and of being 161 /// ordered, so that keys always come out from lowest to highest, 162 /// where a [`HashMap`][hashmap::HashMap] has no guaranteed ordering. 163 /// 164 /// [hashmap::HashMap]: ../hashmap/struct.HashMap.html 165 /// [std::cmp::Ord]: https://doc.rust-lang.org/std/cmp/trait.Ord.html 166 pub struct OrdMap<K, V> { 167 size: usize, 168 pool: OrdMapPool<K, V>, 169 root: PoolRef<Node<(K, V)>>, 170 } 171 172 impl<K, V> OrdMap<K, V> { 173 /// Construct an empty map. 174 #[must_use] new() -> Self175 pub fn new() -> Self { 176 let pool = OrdMapPool::default(); 177 let root = PoolRef::default(&pool.0); 178 OrdMap { 179 size: 0, 180 pool, 181 root, 182 } 183 } 184 185 /// Construct an empty map using a specific memory pool. 186 #[cfg(feature = "pool")] 187 #[must_use] with_pool(pool: &OrdMapPool<K, V>) -> Self188 pub fn with_pool(pool: &OrdMapPool<K, V>) -> Self { 189 let root = PoolRef::default(&pool.0); 190 OrdMap { 191 size: 0, 192 pool: pool.clone(), 193 root, 194 } 195 } 196 197 /// Construct a map with a single mapping. 198 /// 199 /// # Examples 200 /// 201 /// ``` 202 /// # #[macro_use] extern crate im; 203 /// # use im::ordmap::OrdMap; 204 /// let map = OrdMap::unit(123, "onetwothree"); 205 /// assert_eq!( 206 /// map.get(&123), 207 /// Some(&"onetwothree") 208 /// ); 209 /// ``` 210 #[inline] 211 #[must_use] unit(key: K, value: V) -> Self212 pub fn unit(key: K, value: V) -> Self { 213 let pool = OrdMapPool::default(); 214 let root = PoolRef::new(&pool.0, Node::unit((key, value))); 215 OrdMap { 216 size: 1, 217 pool, 218 root, 219 } 220 } 221 222 /// Test whether a map is empty. 223 /// 224 /// Time: O(1) 225 /// 226 /// # Examples 227 /// 228 /// ``` 229 /// # #[macro_use] extern crate im; 230 /// # use im::ordmap::OrdMap; 231 /// assert!( 232 /// !ordmap!{1 => 2}.is_empty() 233 /// ); 234 /// assert!( 235 /// OrdMap::<i32, i32>::new().is_empty() 236 /// ); 237 /// ``` 238 #[inline] 239 #[must_use] is_empty(&self) -> bool240 pub fn is_empty(&self) -> bool { 241 self.len() == 0 242 } 243 244 /// Test whether two maps refer to the same content in memory. 245 /// 246 /// This is true if the two sides are references to the same map, 247 /// or if the two maps refer to the same root node. 248 /// 249 /// This would return true if you're comparing a map to itself, or 250 /// if you're comparing a map to a fresh clone of itself. 251 /// 252 /// Time: O(1) ptr_eq(&self, other: &Self) -> bool253 pub fn ptr_eq(&self, other: &Self) -> bool { 254 std::ptr::eq(self, other) || PoolRef::ptr_eq(&self.root, &other.root) 255 } 256 257 /// Get the size of a map. 258 /// 259 /// Time: O(1) 260 /// 261 /// # Examples 262 /// 263 /// ``` 264 /// # #[macro_use] extern crate im; 265 /// # use im::ordmap::OrdMap; 266 /// assert_eq!(3, ordmap!{ 267 /// 1 => 11, 268 /// 2 => 22, 269 /// 3 => 33 270 /// }.len()); 271 /// ``` 272 #[inline] 273 #[must_use] len(&self) -> usize274 pub fn len(&self) -> usize { 275 self.size 276 } 277 278 /// Get a reference to the memory pool used by this map. 279 /// 280 /// Note that if you didn't specifically construct it with a pool, you'll 281 /// get back a reference to a pool of size 0. 282 #[cfg(feature = "pool")] pool(&self) -> &OrdMapPool<K, V>283 pub fn pool(&self) -> &OrdMapPool<K, V> { 284 &self.pool 285 } 286 287 /// Discard all elements from the map. 288 /// 289 /// This leaves you with an empty map, and all elements that 290 /// were previously inside it are dropped. 291 /// 292 /// Time: O(n) 293 /// 294 /// # Examples 295 /// 296 /// ``` 297 /// # #[macro_use] extern crate im; 298 /// # use im::OrdMap; 299 /// let mut map = ordmap![1=>1, 2=>2, 3=>3]; 300 /// map.clear(); 301 /// assert!(map.is_empty()); 302 /// ``` clear(&mut self)303 pub fn clear(&mut self) { 304 if !self.is_empty() { 305 self.root = PoolRef::default(&self.pool.0); 306 self.size = 0; 307 } 308 } 309 } 310 311 impl<K, V> OrdMap<K, V> 312 where 313 K: Ord, 314 { 315 /// Get the largest key in a map, along with its value. If the map 316 /// is empty, return `None`. 317 /// 318 /// Time: O(log n) 319 /// 320 /// # Examples 321 /// 322 /// ``` 323 /// # #[macro_use] extern crate im; 324 /// # use im::ordmap::OrdMap; 325 /// assert_eq!(Some(&(3, 33)), ordmap!{ 326 /// 1 => 11, 327 /// 2 => 22, 328 /// 3 => 33 329 /// }.get_max()); 330 /// ``` 331 #[must_use] get_max(&self) -> Option<&(K, V)>332 pub fn get_max(&self) -> Option<&(K, V)> { 333 self.root.max() 334 } 335 336 /// Get the smallest key in a map, along with its value. If the 337 /// map is empty, return `None`. 338 /// 339 /// Time: O(log n) 340 /// 341 /// # Examples 342 /// 343 /// ``` 344 /// # #[macro_use] extern crate im; 345 /// # use im::ordmap::OrdMap; 346 /// assert_eq!(Some(&(1, 11)), ordmap!{ 347 /// 1 => 11, 348 /// 2 => 22, 349 /// 3 => 33 350 /// }.get_min()); 351 /// ``` 352 #[must_use] get_min(&self) -> Option<&(K, V)>353 pub fn get_min(&self) -> Option<&(K, V)> { 354 self.root.min() 355 } 356 357 /// Get an iterator over the key/value pairs of a map. 358 #[must_use] iter(&self) -> Iter<'_, K, V>359 pub fn iter(&self) -> Iter<'_, K, V> { 360 Iter { 361 it: RangedIter::new(&self.root, self.size, ..), 362 } 363 } 364 365 /// Create an iterator over a range of key/value pairs. 366 #[must_use] range<R, BK>(&self, range: R) -> Iter<'_, K, V> where R: RangeBounds<BK>, K: Borrow<BK>, BK: Ord + ?Sized,367 pub fn range<R, BK>(&self, range: R) -> Iter<'_, K, V> 368 where 369 R: RangeBounds<BK>, 370 K: Borrow<BK>, 371 BK: Ord + ?Sized, 372 { 373 Iter { 374 it: RangedIter::new(&self.root, self.size, range), 375 } 376 } 377 378 /// Get an iterator over a map's keys. 379 #[must_use] keys(&self) -> Keys<'_, K, V>380 pub fn keys(&self) -> Keys<'_, K, V> { 381 Keys { it: self.iter() } 382 } 383 384 /// Get an iterator over a map's values. 385 #[must_use] values(&self) -> Values<'_, K, V>386 pub fn values(&self) -> Values<'_, K, V> { 387 Values { it: self.iter() } 388 } 389 390 /// Get an iterator over the differences between this map and 391 /// another, i.e. the set of entries to add, update, or remove to 392 /// this map in order to make it equal to the other map. 393 /// 394 /// This function will avoid visiting nodes which are shared 395 /// between the two maps, meaning that even very large maps can be 396 /// compared quickly if most of their structure is shared. 397 /// 398 /// Time: O(n) (where n is the number of unique elements across 399 /// the two maps, minus the number of elements belonging to nodes 400 /// shared between them) 401 #[must_use] diff<'a>(&'a self, other: &'a Self) -> DiffIter<'a, K, V>402 pub fn diff<'a>(&'a self, other: &'a Self) -> DiffIter<'a, K, V> { 403 DiffIter { 404 it: NodeDiffIter::new(&self.root, &other.root), 405 } 406 } 407 408 /// Get the value for a key from a map. 409 /// 410 /// Time: O(log n) 411 /// 412 /// # Examples 413 /// 414 /// ``` 415 /// # #[macro_use] extern crate im; 416 /// # use im::ordmap::OrdMap; 417 /// let map = ordmap!{123 => "lol"}; 418 /// assert_eq!( 419 /// map.get(&123), 420 /// Some(&"lol") 421 /// ); 422 /// ``` 423 #[must_use] get<BK>(&self, key: &BK) -> Option<&V> where BK: Ord + ?Sized, K: Borrow<BK>,424 pub fn get<BK>(&self, key: &BK) -> Option<&V> 425 where 426 BK: Ord + ?Sized, 427 K: Borrow<BK>, 428 { 429 self.root.lookup(key).map(|(_, v)| v) 430 } 431 432 /// Get the key/value pair for a key from a map. 433 /// 434 /// Time: O(log n) 435 /// 436 /// # Examples 437 /// 438 /// ``` 439 /// # #[macro_use] extern crate im; 440 /// # use im::ordmap::OrdMap; 441 /// let map = ordmap!{123 => "lol"}; 442 /// assert_eq!( 443 /// map.get_key_value(&123), 444 /// Some((&123, &"lol")) 445 /// ); 446 /// ``` 447 #[must_use] get_key_value<BK>(&self, key: &BK) -> Option<(&K, &V)> where BK: Ord + ?Sized, K: Borrow<BK>,448 pub fn get_key_value<BK>(&self, key: &BK) -> Option<(&K, &V)> 449 where 450 BK: Ord + ?Sized, 451 K: Borrow<BK>, 452 { 453 self.root.lookup(key).map(|&(ref k, ref v)| (k, v)) 454 } 455 456 /// Get the closest smaller entry in a map to a given key 457 /// as a mutable reference. 458 /// 459 /// If the map contains the given key, this is returned. 460 /// Otherwise, the closest key in the map smaller than the 461 /// given value is returned. If the smallest key in the map 462 /// is larger than the given key, `None` is returned. 463 /// 464 /// # Examples 465 /// 466 /// ```rust 467 /// # #[macro_use] extern crate im; 468 /// # use im::OrdMap; 469 /// let map = ordmap![1 => 1, 3 => 3, 5 => 5]; 470 /// assert_eq!(Some((&3, &3)), map.get_prev(&4)); 471 /// ``` 472 #[must_use] get_prev<BK>(&self, key: &BK) -> Option<(&K, &V)> where BK: Ord + ?Sized, K: Borrow<BK>,473 pub fn get_prev<BK>(&self, key: &BK) -> Option<(&K, &V)> 474 where 475 BK: Ord + ?Sized, 476 K: Borrow<BK>, 477 { 478 self.root.lookup_prev(key).map(|(k, v)| (k, v)) 479 } 480 481 /// Get the closest larger entry in a map to a given key 482 /// as a mutable reference. 483 /// 484 /// If the set contains the given value, this is returned. 485 /// Otherwise, the closest value in the set larger than the 486 /// given value is returned. If the largest value in the set 487 /// is smaller than the given value, `None` is returned. 488 /// 489 /// # Examples 490 /// 491 /// ```rust 492 /// # #[macro_use] extern crate im; 493 /// # use im::OrdMap; 494 /// let map = ordmap![1 => 1, 3 => 3, 5 => 5]; 495 /// assert_eq!(Some((&5, &5)), map.get_next(&4)); 496 /// ``` 497 #[must_use] get_next<BK>(&self, key: &BK) -> Option<(&K, &V)> where BK: Ord + ?Sized, K: Borrow<BK>,498 pub fn get_next<BK>(&self, key: &BK) -> Option<(&K, &V)> 499 where 500 BK: Ord + ?Sized, 501 K: Borrow<BK>, 502 { 503 self.root.lookup_next(key).map(|(k, v)| (k, v)) 504 } 505 506 /// Test for the presence of a key in a map. 507 /// 508 /// Time: O(log n) 509 /// 510 /// # Examples 511 /// 512 /// ``` 513 /// # #[macro_use] extern crate im; 514 /// # use im::ordmap::OrdMap; 515 /// let map = ordmap!{123 => "lol"}; 516 /// assert!( 517 /// map.contains_key(&123) 518 /// ); 519 /// assert!( 520 /// !map.contains_key(&321) 521 /// ); 522 /// ``` 523 #[must_use] contains_key<BK>(&self, k: &BK) -> bool where BK: Ord + ?Sized, K: Borrow<BK>,524 pub fn contains_key<BK>(&self, k: &BK) -> bool 525 where 526 BK: Ord + ?Sized, 527 K: Borrow<BK>, 528 { 529 self.get(k).is_some() 530 } 531 532 /// Test whether a map is a submap of another map, meaning that 533 /// all keys in our map must also be in the other map, with the 534 /// same values. 535 /// 536 /// Use the provided function to decide whether values are equal. 537 /// 538 /// Time: O(n log n) 539 #[must_use] is_submap_by<B, RM, F>(&self, other: RM, mut cmp: F) -> bool where F: FnMut(&V, &B) -> bool, RM: Borrow<OrdMap<K, B>>,540 pub fn is_submap_by<B, RM, F>(&self, other: RM, mut cmp: F) -> bool 541 where 542 F: FnMut(&V, &B) -> bool, 543 RM: Borrow<OrdMap<K, B>>, 544 { 545 self.iter() 546 .all(|(k, v)| other.borrow().get(k).map(|ov| cmp(v, ov)).unwrap_or(false)) 547 } 548 549 /// Test whether a map is a proper submap of another map, meaning 550 /// that all keys in our map must also be in the other map, with 551 /// the same values. To be a proper submap, ours must also contain 552 /// fewer keys than the other map. 553 /// 554 /// Use the provided function to decide whether values are equal. 555 /// 556 /// Time: O(n log n) 557 #[must_use] is_proper_submap_by<B, RM, F>(&self, other: RM, cmp: F) -> bool where F: FnMut(&V, &B) -> bool, RM: Borrow<OrdMap<K, B>>,558 pub fn is_proper_submap_by<B, RM, F>(&self, other: RM, cmp: F) -> bool 559 where 560 F: FnMut(&V, &B) -> bool, 561 RM: Borrow<OrdMap<K, B>>, 562 { 563 self.len() != other.borrow().len() && self.is_submap_by(other, cmp) 564 } 565 566 /// Test whether a map is a submap of another map, meaning that 567 /// all keys in our map must also be in the other map, with the 568 /// same values. 569 /// 570 /// Time: O(n log n) 571 /// 572 /// # Examples 573 /// 574 /// ``` 575 /// # #[macro_use] extern crate im; 576 /// # use im::ordmap::OrdMap; 577 /// let map1 = ordmap!{1 => 1, 2 => 2}; 578 /// let map2 = ordmap!{1 => 1, 2 => 2, 3 => 3}; 579 /// assert!(map1.is_submap(map2)); 580 /// ``` 581 #[must_use] is_submap<RM>(&self, other: RM) -> bool where V: PartialEq, RM: Borrow<Self>,582 pub fn is_submap<RM>(&self, other: RM) -> bool 583 where 584 V: PartialEq, 585 RM: Borrow<Self>, 586 { 587 self.is_submap_by(other.borrow(), PartialEq::eq) 588 } 589 590 /// Test whether a map is a proper submap of another map, meaning 591 /// that all keys in our map must also be in the other map, with 592 /// the same values. To be a proper submap, ours must also contain 593 /// fewer keys than the other map. 594 /// 595 /// Time: O(n log n) 596 /// 597 /// # Examples 598 /// 599 /// ``` 600 /// # #[macro_use] extern crate im; 601 /// # use im::ordmap::OrdMap; 602 /// let map1 = ordmap!{1 => 1, 2 => 2}; 603 /// let map2 = ordmap!{1 => 1, 2 => 2, 3 => 3}; 604 /// assert!(map1.is_proper_submap(map2)); 605 /// 606 /// let map3 = ordmap!{1 => 1, 2 => 2}; 607 /// let map4 = ordmap!{1 => 1, 2 => 2}; 608 /// assert!(!map3.is_proper_submap(map4)); 609 /// ``` 610 #[must_use] is_proper_submap<RM>(&self, other: RM) -> bool where V: PartialEq, RM: Borrow<Self>,611 pub fn is_proper_submap<RM>(&self, other: RM) -> bool 612 where 613 V: PartialEq, 614 RM: Borrow<Self>, 615 { 616 self.is_proper_submap_by(other.borrow(), PartialEq::eq) 617 } 618 } 619 620 impl<K, V> OrdMap<K, V> 621 where 622 K: Ord + Clone, 623 V: Clone, 624 { 625 /// Get a mutable reference to the value for a key from a map. 626 /// 627 /// Time: O(log n) 628 /// 629 /// # Examples 630 /// 631 /// ``` 632 /// # #[macro_use] extern crate im; 633 /// # use im::ordmap::OrdMap; 634 /// let mut map = ordmap!{123 => "lol"}; 635 /// if let Some(value) = map.get_mut(&123) { 636 /// *value = "omg"; 637 /// } 638 /// assert_eq!( 639 /// map.get(&123), 640 /// Some(&"omg") 641 /// ); 642 /// ``` 643 #[must_use] get_mut<BK>(&mut self, key: &BK) -> Option<&mut V> where BK: Ord + ?Sized, K: Borrow<BK>,644 pub fn get_mut<BK>(&mut self, key: &BK) -> Option<&mut V> 645 where 646 BK: Ord + ?Sized, 647 K: Borrow<BK>, 648 { 649 let root = PoolRef::make_mut(&self.pool.0, &mut self.root); 650 root.lookup_mut(&self.pool.0, key).map(|(_, v)| v) 651 } 652 653 /// Get the closest smaller entry in a map to a given key 654 /// as a mutable reference. 655 /// 656 /// If the map contains the given key, this is returned. 657 /// Otherwise, the closest key in the map smaller than the 658 /// given value is returned. If the smallest key in the map 659 /// is larger than the given key, `None` is returned. 660 /// 661 /// # Examples 662 /// 663 /// ```rust 664 /// # #[macro_use] extern crate im; 665 /// # use im::OrdMap; 666 /// let mut map = ordmap![1 => 1, 3 => 3, 5 => 5]; 667 /// if let Some((key, value)) = map.get_prev_mut(&4) { 668 /// *value = 4; 669 /// } 670 /// assert_eq!(ordmap![1 => 1, 3 => 4, 5 => 5], map); 671 /// ``` 672 #[must_use] get_prev_mut<BK>(&mut self, key: &BK) -> Option<(&K, &mut V)> where BK: Ord + ?Sized, K: Borrow<BK>,673 pub fn get_prev_mut<BK>(&mut self, key: &BK) -> Option<(&K, &mut V)> 674 where 675 BK: Ord + ?Sized, 676 K: Borrow<BK>, 677 { 678 let pool = &self.pool.0; 679 PoolRef::make_mut(pool, &mut self.root) 680 .lookup_prev_mut(pool, key) 681 .map(|(ref k, ref mut v)| (k, v)) 682 } 683 684 /// Get the closest larger entry in a map to a given key 685 /// as a mutable reference. 686 /// 687 /// If the set contains the given value, this is returned. 688 /// Otherwise, the closest value in the set larger than the 689 /// given value is returned. If the largest value in the set 690 /// is smaller than the given value, `None` is returned. 691 /// 692 /// # Examples 693 /// 694 /// ```rust 695 /// # #[macro_use] extern crate im; 696 /// # use im::OrdMap; 697 /// let mut map = ordmap![1 => 1, 3 => 3, 5 => 5]; 698 /// if let Some((key, value)) = map.get_next_mut(&4) { 699 /// *value = 4; 700 /// } 701 /// assert_eq!(ordmap![1 => 1, 3 => 3, 5 => 4], map); 702 /// ``` 703 #[must_use] get_next_mut<BK>(&mut self, key: &BK) -> Option<(&K, &mut V)> where BK: Ord + ?Sized, K: Borrow<BK>,704 pub fn get_next_mut<BK>(&mut self, key: &BK) -> Option<(&K, &mut V)> 705 where 706 BK: Ord + ?Sized, 707 K: Borrow<BK>, 708 { 709 let pool = &self.pool.0; 710 PoolRef::make_mut(pool, &mut self.root) 711 .lookup_next_mut(pool, key) 712 .map(|(ref k, ref mut v)| (k, v)) 713 } 714 715 /// Insert a key/value mapping into a map. 716 /// 717 /// This is a copy-on-write operation, so that the parts of the 718 /// map's structure which are shared with other maps will be 719 /// safely copied before mutating. 720 /// 721 /// If the map already has a mapping for the given key, the 722 /// previous value is overwritten. 723 /// 724 /// Time: O(log n) 725 /// 726 /// # Examples 727 /// 728 /// ``` 729 /// # #[macro_use] extern crate im; 730 /// # use im::ordmap::OrdMap; 731 /// let mut map = ordmap!{}; 732 /// map.insert(123, "123"); 733 /// map.insert(456, "456"); 734 /// assert_eq!( 735 /// map, 736 /// ordmap!{123 => "123", 456 => "456"} 737 /// ); 738 /// ``` 739 /// 740 /// [insert]: #method.insert 741 #[inline] insert(&mut self, key: K, value: V) -> Option<V>742 pub fn insert(&mut self, key: K, value: V) -> Option<V> { 743 let new_root = { 744 let root = PoolRef::make_mut(&self.pool.0, &mut self.root); 745 match root.insert(&self.pool.0, (key, value)) { 746 Insert::Replaced((_, old_value)) => return Some(old_value), 747 Insert::Added => { 748 self.size += 1; 749 return None; 750 } 751 Insert::Split(left, median, right) => PoolRef::new( 752 &self.pool.0, 753 Node::new_from_split(&self.pool.0, left, median, right), 754 ), 755 } 756 }; 757 self.size += 1; 758 self.root = new_root; 759 None 760 } 761 762 /// Remove a key/value mapping from a map if it exists. 763 /// 764 /// Time: O(log n) 765 /// 766 /// # Examples 767 /// 768 /// ``` 769 /// # #[macro_use] extern crate im; 770 /// # use im::ordmap::OrdMap; 771 /// let mut map = ordmap!{123 => "123", 456 => "456"}; 772 /// map.remove(&123); 773 /// map.remove(&456); 774 /// assert!(map.is_empty()); 775 /// ``` 776 /// 777 /// [remove]: #method.remove 778 #[inline] remove<BK>(&mut self, k: &BK) -> Option<V> where BK: Ord + ?Sized, K: Borrow<BK>,779 pub fn remove<BK>(&mut self, k: &BK) -> Option<V> 780 where 781 BK: Ord + ?Sized, 782 K: Borrow<BK>, 783 { 784 self.remove_with_key(k).map(|(_, v)| v) 785 } 786 787 /// Remove a key/value pair from a map, if it exists, and return 788 /// the removed key and value. 789 /// 790 /// Time: O(log n) remove_with_key<BK>(&mut self, k: &BK) -> Option<(K, V)> where BK: Ord + ?Sized, K: Borrow<BK>,791 pub fn remove_with_key<BK>(&mut self, k: &BK) -> Option<(K, V)> 792 where 793 BK: Ord + ?Sized, 794 K: Borrow<BK>, 795 { 796 let (new_root, removed_value) = { 797 let root = PoolRef::make_mut(&self.pool.0, &mut self.root); 798 match root.remove(&self.pool.0, k) { 799 Remove::NoChange => return None, 800 Remove::Removed(pair) => { 801 self.size -= 1; 802 return Some(pair); 803 } 804 Remove::Update(pair, root) => (PoolRef::new(&self.pool.0, root), Some(pair)), 805 } 806 }; 807 self.size -= 1; 808 self.root = new_root; 809 removed_value 810 } 811 812 /// Construct a new map by inserting a key/value mapping into a 813 /// map. 814 /// 815 /// If the map already has a mapping for the given key, the 816 /// previous value is overwritten. 817 /// 818 /// Time: O(log n) 819 /// 820 /// # Examples 821 /// 822 /// ``` 823 /// # #[macro_use] extern crate im; 824 /// # use im::ordmap::OrdMap; 825 /// let map = ordmap!{}; 826 /// assert_eq!( 827 /// map.update(123, "123"), 828 /// ordmap!{123 => "123"} 829 /// ); 830 /// ``` 831 #[must_use] update(&self, key: K, value: V) -> Self832 pub fn update(&self, key: K, value: V) -> Self { 833 let mut out = self.clone(); 834 out.insert(key, value); 835 out 836 } 837 838 /// Construct a new map by inserting a key/value mapping into a 839 /// map. 840 /// 841 /// If the map already has a mapping for the given key, we call 842 /// the provided function with the old value and the new value, 843 /// and insert the result as the new value. 844 /// 845 /// Time: O(log n) 846 #[must_use] update_with<F>(self, k: K, v: V, f: F) -> Self where F: FnOnce(V, V) -> V,847 pub fn update_with<F>(self, k: K, v: V, f: F) -> Self 848 where 849 F: FnOnce(V, V) -> V, 850 { 851 self.update_with_key(k, v, |_, v1, v2| f(v1, v2)) 852 } 853 854 /// Construct a new map by inserting a key/value mapping into a 855 /// map. 856 /// 857 /// If the map already has a mapping for the given key, we call 858 /// the provided function with the key, the old value and the new 859 /// value, and insert the result as the new value. 860 /// 861 /// Time: O(log n) 862 #[must_use] update_with_key<F>(self, k: K, v: V, f: F) -> Self where F: FnOnce(&K, V, V) -> V,863 pub fn update_with_key<F>(self, k: K, v: V, f: F) -> Self 864 where 865 F: FnOnce(&K, V, V) -> V, 866 { 867 match self.extract_with_key(&k) { 868 None => self.update(k, v), 869 Some((_, v2, m)) => { 870 let out_v = f(&k, v2, v); 871 m.update(k, out_v) 872 } 873 } 874 } 875 876 /// Construct a new map by inserting a key/value mapping into a 877 /// map, returning the old value for the key as well as the new 878 /// map. 879 /// 880 /// If the map already has a mapping for the given key, we call 881 /// the provided function with the key, the old value and the new 882 /// value, and insert the result as the new value. 883 /// 884 /// Time: O(log n) 885 #[must_use] update_lookup_with_key<F>(self, k: K, v: V, f: F) -> (Option<V>, Self) where F: FnOnce(&K, &V, V) -> V,886 pub fn update_lookup_with_key<F>(self, k: K, v: V, f: F) -> (Option<V>, Self) 887 where 888 F: FnOnce(&K, &V, V) -> V, 889 { 890 match self.extract_with_key(&k) { 891 None => (None, self.update(k, v)), 892 Some((_, v2, m)) => { 893 let out_v = f(&k, &v2, v); 894 (Some(v2), m.update(k, out_v)) 895 } 896 } 897 } 898 899 /// Update the value for a given key by calling a function with 900 /// the current value and overwriting it with the function's 901 /// return value. 902 /// 903 /// The function gets an [`Option<V>`][std::option::Option] and 904 /// returns the same, so that it can decide to delete a mapping 905 /// instead of updating the value, and decide what to do if the 906 /// key isn't in the map. 907 /// 908 /// Time: O(log n) 909 /// 910 /// [std::option::Option]: https://doc.rust-lang.org/std/option/enum.Option.html 911 #[must_use] alter<F>(&self, f: F, k: K) -> Self where F: FnOnce(Option<V>) -> Option<V>,912 pub fn alter<F>(&self, f: F, k: K) -> Self 913 where 914 F: FnOnce(Option<V>) -> Option<V>, 915 { 916 let pop = self.extract_with_key(&k); 917 match (f(pop.as_ref().map(|&(_, ref v, _)| v.clone())), pop) { 918 (None, None) => self.clone(), 919 (Some(v), None) => self.update(k, v), 920 (None, Some((_, _, m))) => m, 921 (Some(v), Some((_, _, m))) => m.update(k, v), 922 } 923 } 924 925 /// Remove a key/value pair from a map, if it exists. 926 /// 927 /// Time: O(log n) 928 #[must_use] without<BK>(&self, k: &BK) -> Self where BK: Ord + ?Sized, K: Borrow<BK>,929 pub fn without<BK>(&self, k: &BK) -> Self 930 where 931 BK: Ord + ?Sized, 932 K: Borrow<BK>, 933 { 934 self.extract(k) 935 .map(|(_, m)| m) 936 .unwrap_or_else(|| self.clone()) 937 } 938 939 /// Remove a key/value pair from a map, if it exists, and return 940 /// the removed value as well as the updated list. 941 /// 942 /// Time: O(log n) 943 #[must_use] extract<BK>(&self, k: &BK) -> Option<(V, Self)> where BK: Ord + ?Sized, K: Borrow<BK>,944 pub fn extract<BK>(&self, k: &BK) -> Option<(V, Self)> 945 where 946 BK: Ord + ?Sized, 947 K: Borrow<BK>, 948 { 949 self.extract_with_key(k).map(|(_, v, m)| (v, m)) 950 } 951 952 /// Remove a key/value pair from a map, if it exists, and return 953 /// the removed key and value as well as the updated list. 954 /// 955 /// Time: O(log n) 956 #[must_use] extract_with_key<BK>(&self, k: &BK) -> Option<(K, V, Self)> where BK: Ord + ?Sized, K: Borrow<BK>,957 pub fn extract_with_key<BK>(&self, k: &BK) -> Option<(K, V, Self)> 958 where 959 BK: Ord + ?Sized, 960 K: Borrow<BK>, 961 { 962 let mut out = self.clone(); 963 let result = out.remove_with_key(k); 964 result.map(|(k, v)| (k, v, out)) 965 } 966 967 /// Construct the union of two maps, keeping the values in the 968 /// current map when keys exist in both maps. 969 /// 970 /// Time: O(n log n) 971 /// 972 /// # Examples 973 /// 974 /// ``` 975 /// # #[macro_use] extern crate im; 976 /// # use im::ordmap::OrdMap; 977 /// let map1 = ordmap!{1 => 1, 3 => 3}; 978 /// let map2 = ordmap!{2 => 2, 3 => 4}; 979 /// let expected = ordmap!{1 => 1, 2 => 2, 3 => 3}; 980 /// assert_eq!(expected, map1.union(map2)); 981 /// ``` 982 #[inline] 983 #[must_use] union(mut self, other: Self) -> Self984 pub fn union(mut self, other: Self) -> Self { 985 for (k, v) in other { 986 self.entry(k).or_insert(v); 987 } 988 self 989 } 990 991 /// Construct the union of two maps, using a function to decide 992 /// what to do with the value when a key is in both maps. 993 /// 994 /// The function is called when a value exists in both maps, and 995 /// receives the value from the current map as its first argument, 996 /// and the value from the other map as the second. It should 997 /// return the value to be inserted in the resulting map. 998 /// 999 /// Time: O(n log n) 1000 #[inline] 1001 #[must_use] union_with<F>(self, other: Self, mut f: F) -> Self where F: FnMut(V, V) -> V,1002 pub fn union_with<F>(self, other: Self, mut f: F) -> Self 1003 where 1004 F: FnMut(V, V) -> V, 1005 { 1006 self.union_with_key(other, |_, v1, v2| f(v1, v2)) 1007 } 1008 1009 /// Construct the union of two maps, using a function to decide 1010 /// what to do with the value when a key is in both maps. 1011 /// 1012 /// The function is called when a value exists in both maps, and 1013 /// receives a reference to the key as its first argument, the 1014 /// value from the current map as the second argument, and the 1015 /// value from the other map as the third argument. It should 1016 /// return the value to be inserted in the resulting map. 1017 /// 1018 /// Time: O(n log n) 1019 /// 1020 /// # Examples 1021 /// 1022 /// ``` 1023 /// # #[macro_use] extern crate im; 1024 /// # use im::ordmap::OrdMap; 1025 /// let map1 = ordmap!{1 => 1, 3 => 4}; 1026 /// let map2 = ordmap!{2 => 2, 3 => 5}; 1027 /// let expected = ordmap!{1 => 1, 2 => 2, 3 => 9}; 1028 /// assert_eq!(expected, map1.union_with_key( 1029 /// map2, 1030 /// |key, left, right| left + right 1031 /// )); 1032 /// ``` 1033 #[must_use] union_with_key<F>(mut self, other: Self, mut f: F) -> Self where F: FnMut(&K, V, V) -> V,1034 pub fn union_with_key<F>(mut self, other: Self, mut f: F) -> Self 1035 where 1036 F: FnMut(&K, V, V) -> V, 1037 { 1038 for (key, right_value) in other { 1039 match self.remove(&key) { 1040 None => { 1041 self.insert(key, right_value); 1042 } 1043 Some(left_value) => { 1044 let final_value = f(&key, left_value, right_value); 1045 self.insert(key, final_value); 1046 } 1047 } 1048 } 1049 self 1050 } 1051 1052 /// Construct the union of a sequence of maps, selecting the value 1053 /// of the leftmost when a key appears in more than one map. 1054 /// 1055 /// Time: O(n log n) 1056 /// 1057 /// # Examples 1058 /// 1059 /// ``` 1060 /// # #[macro_use] extern crate im; 1061 /// # use im::ordmap::OrdMap; 1062 /// let map1 = ordmap!{1 => 1, 3 => 3}; 1063 /// let map2 = ordmap!{2 => 2}; 1064 /// let expected = ordmap!{1 => 1, 2 => 2, 3 => 3}; 1065 /// assert_eq!(expected, OrdMap::unions(vec![map1, map2])); 1066 /// ``` 1067 #[must_use] unions<I>(i: I) -> Self where I: IntoIterator<Item = Self>,1068 pub fn unions<I>(i: I) -> Self 1069 where 1070 I: IntoIterator<Item = Self>, 1071 { 1072 i.into_iter().fold(Self::default(), Self::union) 1073 } 1074 1075 /// Construct the union of a sequence of maps, using a function to 1076 /// decide what to do with the value when a key is in more than 1077 /// one map. 1078 /// 1079 /// The function is called when a value exists in multiple maps, 1080 /// and receives the value from the current map as its first 1081 /// argument, and the value from the next map as the second. It 1082 /// should return the value to be inserted in the resulting map. 1083 /// 1084 /// Time: O(n log n) 1085 #[must_use] unions_with<I, F>(i: I, f: F) -> Self where I: IntoIterator<Item = Self>, F: Fn(V, V) -> V,1086 pub fn unions_with<I, F>(i: I, f: F) -> Self 1087 where 1088 I: IntoIterator<Item = Self>, 1089 F: Fn(V, V) -> V, 1090 { 1091 i.into_iter() 1092 .fold(Self::default(), |a, b| a.union_with(b, &f)) 1093 } 1094 1095 /// Construct the union of a sequence of maps, using a function to 1096 /// decide what to do with the value when a key is in more than 1097 /// one map. 1098 /// 1099 /// The function is called when a value exists in multiple maps, 1100 /// and receives a reference to the key as its first argument, the 1101 /// value from the current map as the second argument, and the 1102 /// value from the next map as the third argument. It should 1103 /// return the value to be inserted in the resulting map. 1104 /// 1105 /// Time: O(n log n) 1106 #[must_use] unions_with_key<I, F>(i: I, f: F) -> Self where I: IntoIterator<Item = Self>, F: Fn(&K, V, V) -> V,1107 pub fn unions_with_key<I, F>(i: I, f: F) -> Self 1108 where 1109 I: IntoIterator<Item = Self>, 1110 F: Fn(&K, V, V) -> V, 1111 { 1112 i.into_iter() 1113 .fold(Self::default(), |a, b| a.union_with_key(b, &f)) 1114 } 1115 1116 /// Construct the symmetric difference between two maps by discarding keys 1117 /// which occur in both maps. 1118 /// 1119 /// This is an alias for the 1120 /// [`symmetric_difference`][symmetric_difference] method. 1121 /// 1122 /// Time: O(n log n) 1123 /// 1124 /// # Examples 1125 /// 1126 /// ``` 1127 /// # #[macro_use] extern crate im; 1128 /// # use im::ordmap::OrdMap; 1129 /// let map1 = ordmap!{1 => 1, 3 => 4}; 1130 /// let map2 = ordmap!{2 => 2, 3 => 5}; 1131 /// let expected = ordmap!{1 => 1, 2 => 2}; 1132 /// assert_eq!(expected, map1.difference(map2)); 1133 /// ``` 1134 /// 1135 /// [symmetric_difference]: #method.symmetric_difference 1136 #[inline] 1137 #[must_use] difference(self, other: Self) -> Self1138 pub fn difference(self, other: Self) -> Self { 1139 self.symmetric_difference(other) 1140 } 1141 1142 /// Construct the symmetric difference between two maps by discarding keys 1143 /// which occur in both maps. 1144 /// 1145 /// Time: O(n log n) 1146 /// 1147 /// # Examples 1148 /// 1149 /// ``` 1150 /// # #[macro_use] extern crate im; 1151 /// # use im::ordmap::OrdMap; 1152 /// let map1 = ordmap!{1 => 1, 3 => 4}; 1153 /// let map2 = ordmap!{2 => 2, 3 => 5}; 1154 /// let expected = ordmap!{1 => 1, 2 => 2}; 1155 /// assert_eq!(expected, map1.symmetric_difference(map2)); 1156 /// ``` 1157 #[inline] 1158 #[must_use] symmetric_difference(self, other: Self) -> Self1159 pub fn symmetric_difference(self, other: Self) -> Self { 1160 self.symmetric_difference_with_key(other, |_, _, _| None) 1161 } 1162 1163 /// Construct the symmetric difference between two maps by using a function 1164 /// to decide what to do if a key occurs in both. 1165 /// 1166 /// This is an alias for the 1167 /// [`symmetric_difference_with`][symmetric_difference_with] method. 1168 /// 1169 /// Time: O(n log n) 1170 /// 1171 /// [symmetric_difference_with]: #method.symmetric_difference_with 1172 #[inline] 1173 #[must_use] difference_with<F>(self, other: Self, f: F) -> Self where F: FnMut(V, V) -> Option<V>,1174 pub fn difference_with<F>(self, other: Self, f: F) -> Self 1175 where 1176 F: FnMut(V, V) -> Option<V>, 1177 { 1178 self.symmetric_difference_with(other, f) 1179 } 1180 1181 /// Construct the symmetric difference between two maps by using a function 1182 /// to decide what to do if a key occurs in both. 1183 /// 1184 /// Time: O(n log n) 1185 #[inline] 1186 #[must_use] symmetric_difference_with<F>(self, other: Self, mut f: F) -> Self where F: FnMut(V, V) -> Option<V>,1187 pub fn symmetric_difference_with<F>(self, other: Self, mut f: F) -> Self 1188 where 1189 F: FnMut(V, V) -> Option<V>, 1190 { 1191 self.symmetric_difference_with_key(other, |_, a, b| f(a, b)) 1192 } 1193 1194 /// Construct the symmetric difference between two maps by using a function 1195 /// to decide what to do if a key occurs in both. The function 1196 /// receives the key as well as both values. 1197 /// 1198 /// This is an alias for the 1199 /// [`symmetric_difference_with_key`][symmetric_difference_with_key] 1200 /// method. 1201 /// 1202 /// Time: O(n log n) 1203 /// 1204 /// # Examples 1205 /// 1206 /// ``` 1207 /// # #[macro_use] extern crate im; 1208 /// # use im::ordmap::OrdMap; 1209 /// let map1 = ordmap!{1 => 1, 3 => 4}; 1210 /// let map2 = ordmap!{2 => 2, 3 => 5}; 1211 /// let expected = ordmap!{1 => 1, 2 => 2, 3 => 9}; 1212 /// assert_eq!(expected, map1.difference_with_key( 1213 /// map2, 1214 /// |key, left, right| Some(left + right) 1215 /// )); 1216 /// ``` 1217 /// [symmetric_difference_with_key]: #method.symmetric_difference_with_key 1218 #[must_use] difference_with_key<F>(self, other: Self, f: F) -> Self where F: FnMut(&K, V, V) -> Option<V>,1219 pub fn difference_with_key<F>(self, other: Self, f: F) -> Self 1220 where 1221 F: FnMut(&K, V, V) -> Option<V>, 1222 { 1223 self.symmetric_difference_with_key(other, f) 1224 } 1225 1226 /// Construct the symmetric difference between two maps by using a function 1227 /// to decide what to do if a key occurs in both. The function 1228 /// receives the key as well as both values. 1229 /// 1230 /// Time: O(n log n) 1231 /// 1232 /// # Examples 1233 /// 1234 /// ``` 1235 /// # #[macro_use] extern crate im; 1236 /// # use im::ordmap::OrdMap; 1237 /// let map1 = ordmap!{1 => 1, 3 => 4}; 1238 /// let map2 = ordmap!{2 => 2, 3 => 5}; 1239 /// let expected = ordmap!{1 => 1, 2 => 2, 3 => 9}; 1240 /// assert_eq!(expected, map1.symmetric_difference_with_key( 1241 /// map2, 1242 /// |key, left, right| Some(left + right) 1243 /// )); 1244 /// ``` 1245 #[must_use] symmetric_difference_with_key<F>(mut self, other: Self, mut f: F) -> Self where F: FnMut(&K, V, V) -> Option<V>,1246 pub fn symmetric_difference_with_key<F>(mut self, other: Self, mut f: F) -> Self 1247 where 1248 F: FnMut(&K, V, V) -> Option<V>, 1249 { 1250 let mut out = Self::default(); 1251 for (key, right_value) in other { 1252 match self.remove(&key) { 1253 None => { 1254 out.insert(key, right_value); 1255 } 1256 Some(left_value) => { 1257 if let Some(final_value) = f(&key, left_value, right_value) { 1258 out.insert(key, final_value); 1259 } 1260 } 1261 } 1262 } 1263 out.union(self) 1264 } 1265 1266 /// Construct the relative complement between two maps by discarding keys 1267 /// which occur in `other`. 1268 /// 1269 /// Time: O(m log n) where m is the size of the other map 1270 /// 1271 /// # Examples 1272 /// 1273 /// ``` 1274 /// # #[macro_use] extern crate im; 1275 /// # use im::ordmap::OrdMap; 1276 /// let map1 = ordmap!{1 => 1, 3 => 4}; 1277 /// let map2 = ordmap!{2 => 2, 3 => 5}; 1278 /// let expected = ordmap!{1 => 1}; 1279 /// assert_eq!(expected, map1.relative_complement(map2)); 1280 /// ``` 1281 #[inline] 1282 #[must_use] relative_complement(mut self, other: Self) -> Self1283 pub fn relative_complement(mut self, other: Self) -> Self { 1284 for (key, _) in other { 1285 let _ = self.remove(&key); 1286 } 1287 self 1288 } 1289 1290 /// Construct the intersection of two maps, keeping the values 1291 /// from the current map. 1292 /// 1293 /// Time: O(n log n) 1294 /// 1295 /// # Examples 1296 /// 1297 /// ``` 1298 /// # #[macro_use] extern crate im; 1299 /// # use im::ordmap::OrdMap; 1300 /// let map1 = ordmap!{1 => 1, 2 => 2}; 1301 /// let map2 = ordmap!{2 => 3, 3 => 4}; 1302 /// let expected = ordmap!{2 => 2}; 1303 /// assert_eq!(expected, map1.intersection(map2)); 1304 /// ``` 1305 #[inline] 1306 #[must_use] intersection(self, other: Self) -> Self1307 pub fn intersection(self, other: Self) -> Self { 1308 self.intersection_with_key(other, |_, v, _| v) 1309 } 1310 1311 /// Construct the intersection of two maps, calling a function 1312 /// with both values for each key and using the result as the 1313 /// value for the key. 1314 /// 1315 /// Time: O(n log n) 1316 #[inline] 1317 #[must_use] intersection_with<B, C, F>(self, other: OrdMap<K, B>, mut f: F) -> OrdMap<K, C> where B: Clone, C: Clone, F: FnMut(V, B) -> C,1318 pub fn intersection_with<B, C, F>(self, other: OrdMap<K, B>, mut f: F) -> OrdMap<K, C> 1319 where 1320 B: Clone, 1321 C: Clone, 1322 F: FnMut(V, B) -> C, 1323 { 1324 self.intersection_with_key(other, |_, v1, v2| f(v1, v2)) 1325 } 1326 1327 /// Construct the intersection of two maps, calling a function 1328 /// with the key and both values for each key and using the result 1329 /// as the value for the key. 1330 /// 1331 /// Time: O(n log n) 1332 /// 1333 /// # Examples 1334 /// 1335 /// ``` 1336 /// # #[macro_use] extern crate im; 1337 /// # use im::ordmap::OrdMap; 1338 /// let map1 = ordmap!{1 => 1, 2 => 2}; 1339 /// let map2 = ordmap!{2 => 3, 3 => 4}; 1340 /// let expected = ordmap!{2 => 5}; 1341 /// assert_eq!(expected, map1.intersection_with_key( 1342 /// map2, 1343 /// |key, left, right| left + right 1344 /// )); 1345 /// ``` 1346 #[must_use] intersection_with_key<B, C, F>(mut self, other: OrdMap<K, B>, mut f: F) -> OrdMap<K, C> where B: Clone, C: Clone, F: FnMut(&K, V, B) -> C,1347 pub fn intersection_with_key<B, C, F>(mut self, other: OrdMap<K, B>, mut f: F) -> OrdMap<K, C> 1348 where 1349 B: Clone, 1350 C: Clone, 1351 F: FnMut(&K, V, B) -> C, 1352 { 1353 let mut out = OrdMap::<K, C>::default(); 1354 for (key, right_value) in other { 1355 match self.remove(&key) { 1356 None => (), 1357 Some(left_value) => { 1358 let result = f(&key, left_value, right_value); 1359 out.insert(key, result); 1360 } 1361 } 1362 } 1363 out 1364 } 1365 1366 /// Split a map into two, with the left hand map containing keys 1367 /// which are smaller than `split`, and the right hand map 1368 /// containing keys which are larger than `split`. 1369 /// 1370 /// The `split` mapping is discarded. 1371 #[must_use] split<BK>(&self, split: &BK) -> (Self, Self) where BK: Ord + ?Sized, K: Borrow<BK>,1372 pub fn split<BK>(&self, split: &BK) -> (Self, Self) 1373 where 1374 BK: Ord + ?Sized, 1375 K: Borrow<BK>, 1376 { 1377 let (l, _, r) = self.split_lookup(split); 1378 (l, r) 1379 } 1380 1381 /// Split a map into two, with the left hand map containing keys 1382 /// which are smaller than `split`, and the right hand map 1383 /// containing keys which are larger than `split`. 1384 /// 1385 /// Returns both the two maps and the value of `split`. 1386 #[must_use] split_lookup<BK>(&self, split: &BK) -> (Self, Option<V>, Self) where BK: Ord + ?Sized, K: Borrow<BK>,1387 pub fn split_lookup<BK>(&self, split: &BK) -> (Self, Option<V>, Self) 1388 where 1389 BK: Ord + ?Sized, 1390 K: Borrow<BK>, 1391 { 1392 // TODO this is atrociously slow, got to be a better way 1393 self.iter() 1394 .fold((ordmap![], None, ordmap![]), |(l, m, r), (k, v)| { 1395 match k.borrow().cmp(split) { 1396 Ordering::Less => (l.update(k.clone(), v.clone()), m, r), 1397 Ordering::Equal => (l, Some(v.clone()), r), 1398 Ordering::Greater => (l, m, r.update(k.clone(), v.clone())), 1399 } 1400 }) 1401 } 1402 1403 /// Construct a map with only the `n` smallest keys from a given 1404 /// map. 1405 #[must_use] take(&self, n: usize) -> Self1406 pub fn take(&self, n: usize) -> Self { 1407 self.iter() 1408 .take(n) 1409 .map(|(k, v)| (k.clone(), v.clone())) 1410 .collect() 1411 } 1412 1413 /// Construct a map with the `n` smallest keys removed from a 1414 /// given map. 1415 #[must_use] skip(&self, n: usize) -> Self1416 pub fn skip(&self, n: usize) -> Self { 1417 self.iter() 1418 .skip(n) 1419 .map(|(k, v)| (k.clone(), v.clone())) 1420 .collect() 1421 } 1422 1423 /// Remove the smallest key from a map, and return its value as 1424 /// well as the updated map. 1425 #[must_use] without_min(&self) -> (Option<V>, Self)1426 pub fn without_min(&self) -> (Option<V>, Self) { 1427 let (pop, next) = self.without_min_with_key(); 1428 (pop.map(|(_, v)| v), next) 1429 } 1430 1431 /// Remove the smallest key from a map, and return that key, its 1432 /// value as well as the updated map. 1433 #[must_use] without_min_with_key(&self) -> (Option<(K, V)>, Self)1434 pub fn without_min_with_key(&self) -> (Option<(K, V)>, Self) { 1435 match self.get_min() { 1436 None => (None, self.clone()), 1437 Some((k, _)) => { 1438 let (key, value, next) = self.extract_with_key(k).unwrap(); 1439 (Some((key, value)), next) 1440 } 1441 } 1442 } 1443 1444 /// Remove the largest key from a map, and return its value as 1445 /// well as the updated map. 1446 #[must_use] without_max(&self) -> (Option<V>, Self)1447 pub fn without_max(&self) -> (Option<V>, Self) { 1448 let (pop, next) = self.without_max_with_key(); 1449 (pop.map(|(_, v)| v), next) 1450 } 1451 1452 /// Remove the largest key from a map, and return that key, its 1453 /// value as well as the updated map. 1454 #[must_use] without_max_with_key(&self) -> (Option<(K, V)>, Self)1455 pub fn without_max_with_key(&self) -> (Option<(K, V)>, Self) { 1456 match self.get_max() { 1457 None => (None, self.clone()), 1458 Some((k, _)) => { 1459 let (key, value, next) = self.extract_with_key(k).unwrap(); 1460 (Some((key, value)), next) 1461 } 1462 } 1463 } 1464 1465 /// Get the [`Entry`][Entry] for a key in the map for in-place manipulation. 1466 /// 1467 /// Time: O(log n) 1468 /// 1469 /// [Entry]: enum.Entry.html 1470 #[must_use] entry(&mut self, key: K) -> Entry<'_, K, V>1471 pub fn entry(&mut self, key: K) -> Entry<'_, K, V> { 1472 if self.contains_key(&key) { 1473 Entry::Occupied(OccupiedEntry { map: self, key }) 1474 } else { 1475 Entry::Vacant(VacantEntry { map: self, key }) 1476 } 1477 } 1478 } 1479 1480 // Entries 1481 1482 /// A handle for a key and its associated value. 1483 pub enum Entry<'a, K, V> 1484 where 1485 K: Ord + Clone, 1486 V: Clone, 1487 { 1488 /// An entry which exists in the map. 1489 Occupied(OccupiedEntry<'a, K, V>), 1490 /// An entry which doesn't exist in the map. 1491 Vacant(VacantEntry<'a, K, V>), 1492 } 1493 1494 impl<'a, K, V> Entry<'a, K, V> 1495 where 1496 K: Ord + Clone, 1497 V: Clone, 1498 { 1499 /// Insert the default value provided if there was no value 1500 /// already, and return a mutable reference to the value. or_insert(self, default: V) -> &'a mut V1501 pub fn or_insert(self, default: V) -> &'a mut V { 1502 self.or_insert_with(|| default) 1503 } 1504 1505 /// Insert the default value from the provided function if there 1506 /// was no value already, and return a mutable reference to the 1507 /// value. or_insert_with<F>(self, default: F) -> &'a mut V where F: FnOnce() -> V,1508 pub fn or_insert_with<F>(self, default: F) -> &'a mut V 1509 where 1510 F: FnOnce() -> V, 1511 { 1512 match self { 1513 Entry::Occupied(entry) => entry.into_mut(), 1514 Entry::Vacant(entry) => entry.insert(default()), 1515 } 1516 } 1517 1518 /// Insert a default value if there was no value already, and 1519 /// return a mutable reference to the value. or_default(self) -> &'a mut V where V: Default,1520 pub fn or_default(self) -> &'a mut V 1521 where 1522 V: Default, 1523 { 1524 self.or_insert_with(Default::default) 1525 } 1526 1527 /// Get the key for this entry. 1528 #[must_use] key(&self) -> &K1529 pub fn key(&self) -> &K { 1530 match self { 1531 Entry::Occupied(entry) => entry.key(), 1532 Entry::Vacant(entry) => entry.key(), 1533 } 1534 } 1535 1536 /// Call the provided function to modify the value if the value 1537 /// exists. and_modify<F>(mut self, f: F) -> Self where F: FnOnce(&mut V),1538 pub fn and_modify<F>(mut self, f: F) -> Self 1539 where 1540 F: FnOnce(&mut V), 1541 { 1542 match &mut self { 1543 Entry::Occupied(ref mut entry) => f(entry.get_mut()), 1544 Entry::Vacant(_) => (), 1545 } 1546 self 1547 } 1548 } 1549 1550 /// An entry for a mapping that already exists in the map. 1551 pub struct OccupiedEntry<'a, K, V> 1552 where 1553 K: Ord + Clone, 1554 V: Clone, 1555 { 1556 map: &'a mut OrdMap<K, V>, 1557 key: K, 1558 } 1559 1560 impl<'a, K, V> OccupiedEntry<'a, K, V> 1561 where 1562 K: 'a + Ord + Clone, 1563 V: 'a + Clone, 1564 { 1565 /// Get the key for this entry. 1566 #[must_use] key(&self) -> &K1567 pub fn key(&self) -> &K { 1568 &self.key 1569 } 1570 1571 /// Remove this entry from the map and return the removed mapping. remove_entry(self) -> (K, V)1572 pub fn remove_entry(self) -> (K, V) { 1573 self.map 1574 .remove_with_key(&self.key) 1575 .expect("ordmap::OccupiedEntry::remove_entry: key has vanished!") 1576 } 1577 1578 /// Get the current value. 1579 #[must_use] get(&self) -> &V1580 pub fn get(&self) -> &V { 1581 self.map.get(&self.key).unwrap() 1582 } 1583 1584 /// Get a mutable reference to the current value. 1585 #[must_use] get_mut(&mut self) -> &mut V1586 pub fn get_mut(&mut self) -> &mut V { 1587 self.map.get_mut(&self.key).unwrap() 1588 } 1589 1590 /// Convert this entry into a mutable reference. 1591 #[must_use] into_mut(self) -> &'a mut V1592 pub fn into_mut(self) -> &'a mut V { 1593 self.map.get_mut(&self.key).unwrap() 1594 } 1595 1596 /// Overwrite the current value. insert(&mut self, value: V) -> V1597 pub fn insert(&mut self, value: V) -> V { 1598 mem::replace(self.get_mut(), value) 1599 } 1600 1601 /// Remove this entry from the map and return the removed value. remove(self) -> V1602 pub fn remove(self) -> V { 1603 self.remove_entry().1 1604 } 1605 } 1606 1607 /// An entry for a mapping that does not already exist in the map. 1608 pub struct VacantEntry<'a, K, V> 1609 where 1610 K: Ord + Clone, 1611 V: Clone, 1612 { 1613 map: &'a mut OrdMap<K, V>, 1614 key: K, 1615 } 1616 1617 impl<'a, K, V> VacantEntry<'a, K, V> 1618 where 1619 K: 'a + Ord + Clone, 1620 V: 'a + Clone, 1621 { 1622 /// Get the key for this entry. 1623 #[must_use] key(&self) -> &K1624 pub fn key(&self) -> &K { 1625 &self.key 1626 } 1627 1628 /// Convert this entry into its key. 1629 #[must_use] into_key(self) -> K1630 pub fn into_key(self) -> K { 1631 self.key 1632 } 1633 1634 /// Insert a value into this entry. insert(self, value: V) -> &'a mut V1635 pub fn insert(self, value: V) -> &'a mut V { 1636 self.map.insert(self.key.clone(), value); 1637 // TODO insert_mut ought to return this reference 1638 self.map.get_mut(&self.key).unwrap() 1639 } 1640 } 1641 1642 // Core traits 1643 1644 impl<K, V> Clone for OrdMap<K, V> { 1645 /// Clone a map. 1646 /// 1647 /// Time: O(1) 1648 #[inline] clone(&self) -> Self1649 fn clone(&self) -> Self { 1650 OrdMap { 1651 size: self.size, 1652 pool: self.pool.clone(), 1653 root: self.root.clone(), 1654 } 1655 } 1656 } 1657 1658 #[cfg(not(has_specialisation))] 1659 impl<K, V> PartialEq for OrdMap<K, V> 1660 where 1661 K: Ord + PartialEq, 1662 V: PartialEq, 1663 { eq(&self, other: &Self) -> bool1664 fn eq(&self, other: &Self) -> bool { 1665 self.len() == other.len() && self.diff(other).next().is_none() 1666 } 1667 } 1668 1669 #[cfg(has_specialisation)] 1670 impl<K, V> PartialEq for OrdMap<K, V> 1671 where 1672 K: Ord + PartialEq, 1673 V: PartialEq, 1674 { eq(&self, other: &Self) -> bool1675 default fn eq(&self, other: &Self) -> bool { 1676 self.len() == other.len() && self.diff(other).next().is_none() 1677 } 1678 } 1679 1680 #[cfg(has_specialisation)] 1681 impl<K, V> PartialEq for OrdMap<K, V> 1682 where 1683 K: Ord + Eq, 1684 V: Eq, 1685 { eq(&self, other: &Self) -> bool1686 fn eq(&self, other: &Self) -> bool { 1687 PoolRef::ptr_eq(&self.root, &other.root) 1688 || (self.len() == other.len() && self.diff(other).next().is_none()) 1689 } 1690 } 1691 1692 impl<K: Ord + Eq, V: Eq> Eq for OrdMap<K, V> {} 1693 1694 impl<K, V> PartialOrd for OrdMap<K, V> 1695 where 1696 K: Ord, 1697 V: PartialOrd, 1698 { partial_cmp(&self, other: &Self) -> Option<Ordering>1699 fn partial_cmp(&self, other: &Self) -> Option<Ordering> { 1700 self.iter().partial_cmp(other.iter()) 1701 } 1702 } 1703 1704 impl<K, V> Ord for OrdMap<K, V> 1705 where 1706 K: Ord, 1707 V: Ord, 1708 { cmp(&self, other: &Self) -> Ordering1709 fn cmp(&self, other: &Self) -> Ordering { 1710 self.iter().cmp(other.iter()) 1711 } 1712 } 1713 1714 impl<K, V> Hash for OrdMap<K, V> 1715 where 1716 K: Ord + Hash, 1717 V: Hash, 1718 { hash<H>(&self, state: &mut H) where H: Hasher,1719 fn hash<H>(&self, state: &mut H) 1720 where 1721 H: Hasher, 1722 { 1723 for i in self.iter() { 1724 i.hash(state); 1725 } 1726 } 1727 } 1728 1729 impl<K, V> Default for OrdMap<K, V> { default() -> Self1730 fn default() -> Self { 1731 Self::new() 1732 } 1733 } 1734 1735 impl<'a, K, V> Add for &'a OrdMap<K, V> 1736 where 1737 K: Ord + Clone, 1738 V: Clone, 1739 { 1740 type Output = OrdMap<K, V>; 1741 add(self, other: Self) -> Self::Output1742 fn add(self, other: Self) -> Self::Output { 1743 self.clone().union(other.clone()) 1744 } 1745 } 1746 1747 impl<K, V> Add for OrdMap<K, V> 1748 where 1749 K: Ord + Clone, 1750 V: Clone, 1751 { 1752 type Output = OrdMap<K, V>; 1753 add(self, other: Self) -> Self::Output1754 fn add(self, other: Self) -> Self::Output { 1755 self.union(other) 1756 } 1757 } 1758 1759 impl<K, V> Sum for OrdMap<K, V> 1760 where 1761 K: Ord + Clone, 1762 V: Clone, 1763 { sum<I>(it: I) -> Self where I: Iterator<Item = Self>,1764 fn sum<I>(it: I) -> Self 1765 where 1766 I: Iterator<Item = Self>, 1767 { 1768 it.fold(Self::default(), |a, b| a + b) 1769 } 1770 } 1771 1772 impl<K, V, RK, RV> Extend<(RK, RV)> for OrdMap<K, V> 1773 where 1774 K: Ord + Clone + From<RK>, 1775 V: Clone + From<RV>, 1776 { extend<I>(&mut self, iter: I) where I: IntoIterator<Item = (RK, RV)>,1777 fn extend<I>(&mut self, iter: I) 1778 where 1779 I: IntoIterator<Item = (RK, RV)>, 1780 { 1781 for (key, value) in iter { 1782 self.insert(From::from(key), From::from(value)); 1783 } 1784 } 1785 } 1786 1787 impl<'a, BK, K, V> Index<&'a BK> for OrdMap<K, V> 1788 where 1789 BK: Ord + ?Sized, 1790 K: Ord + Borrow<BK>, 1791 { 1792 type Output = V; 1793 index(&self, key: &BK) -> &Self::Output1794 fn index(&self, key: &BK) -> &Self::Output { 1795 match self.root.lookup(key) { 1796 None => panic!("OrdMap::index: invalid key"), 1797 Some(&(_, ref value)) => value, 1798 } 1799 } 1800 } 1801 1802 impl<'a, BK, K, V> IndexMut<&'a BK> for OrdMap<K, V> 1803 where 1804 BK: Ord + ?Sized, 1805 K: Ord + Clone + Borrow<BK>, 1806 V: Clone, 1807 { index_mut(&mut self, key: &BK) -> &mut Self::Output1808 fn index_mut(&mut self, key: &BK) -> &mut Self::Output { 1809 let root = PoolRef::make_mut(&self.pool.0, &mut self.root); 1810 match root.lookup_mut(&self.pool.0, key) { 1811 None => panic!("OrdMap::index: invalid key"), 1812 Some(&mut (_, ref mut value)) => value, 1813 } 1814 } 1815 } 1816 1817 impl<K, V> Debug for OrdMap<K, V> 1818 where 1819 K: Ord + Debug, 1820 V: Debug, 1821 { fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error>1822 fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> { 1823 let mut d = f.debug_map(); 1824 for (k, v) in self.iter() { 1825 d.entry(k, v); 1826 } 1827 d.finish() 1828 } 1829 } 1830 1831 // Iterators 1832 1833 /// An iterator over the key/value pairs of a map. 1834 pub struct Iter<'a, K, V> { 1835 it: RangedIter<'a, (K, V)>, 1836 } 1837 1838 impl<'a, K, V> Iterator for Iter<'a, K, V> 1839 where 1840 (K, V): 'a + BTreeValue, 1841 { 1842 type Item = (&'a K, &'a V); 1843 next(&mut self) -> Option<Self::Item>1844 fn next(&mut self) -> Option<Self::Item> { 1845 self.it.next().map(|(k, v)| (k, v)) 1846 } 1847 size_hint(&self) -> (usize, Option<usize>)1848 fn size_hint(&self) -> (usize, Option<usize>) { 1849 (self.it.remaining, Some(self.it.remaining)) 1850 } 1851 } 1852 1853 impl<'a, K, V> DoubleEndedIterator for Iter<'a, K, V> 1854 where 1855 (K, V): 'a + BTreeValue, 1856 { next_back(&mut self) -> Option<Self::Item>1857 fn next_back(&mut self) -> Option<Self::Item> { 1858 self.it.next_back().map(|(k, v)| (k, v)) 1859 } 1860 } 1861 1862 impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> where (K, V): 'a + BTreeValue {} 1863 1864 /// An iterator over the differences between two maps. 1865 pub struct DiffIter<'a, K, V> { 1866 it: NodeDiffIter<'a, (K, V)>, 1867 } 1868 1869 /// A description of a difference between two ordered maps. 1870 #[derive(PartialEq, Eq, Debug)] 1871 pub enum DiffItem<'a, K, V> { 1872 /// This value has been added to the new map. 1873 Add(&'a K, &'a V), 1874 /// This value has been changed between the two maps. 1875 Update { 1876 /// The old value. 1877 old: (&'a K, &'a V), 1878 /// The new value. 1879 new: (&'a K, &'a V), 1880 }, 1881 /// This value has been removed from the new map. 1882 Remove(&'a K, &'a V), 1883 } 1884 1885 impl<'a, K, V> Iterator for DiffIter<'a, K, V> 1886 where 1887 (K, V): 'a + BTreeValue + PartialEq, 1888 { 1889 type Item = DiffItem<'a, K, V>; 1890 next(&mut self) -> Option<Self::Item>1891 fn next(&mut self) -> Option<Self::Item> { 1892 self.it.next().map(|item| match item { 1893 NodeDiffItem::Add((k, v)) => DiffItem::Add(k, v), 1894 NodeDiffItem::Update { 1895 old: (oldk, oldv), 1896 new: (newk, newv), 1897 } => DiffItem::Update { 1898 old: (oldk, oldv), 1899 new: (newk, newv), 1900 }, 1901 NodeDiffItem::Remove((k, v)) => DiffItem::Remove(k, v), 1902 }) 1903 } 1904 } 1905 1906 /// An iterator ove the keys of a map. 1907 pub struct Keys<'a, K, V> { 1908 it: Iter<'a, K, V>, 1909 } 1910 1911 impl<'a, K, V> Iterator for Keys<'a, K, V> 1912 where 1913 K: 'a + Ord, 1914 V: 'a, 1915 { 1916 type Item = &'a K; 1917 next(&mut self) -> Option<Self::Item>1918 fn next(&mut self) -> Option<Self::Item> { 1919 self.it.next().map(|(k, _)| k) 1920 } 1921 size_hint(&self) -> (usize, Option<usize>)1922 fn size_hint(&self) -> (usize, Option<usize>) { 1923 self.it.size_hint() 1924 } 1925 } 1926 1927 impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> 1928 where 1929 K: 'a + Ord, 1930 V: 'a, 1931 { next_back(&mut self) -> Option<Self::Item>1932 fn next_back(&mut self) -> Option<Self::Item> { 1933 match self.it.next_back() { 1934 None => None, 1935 Some((k, _)) => Some(k), 1936 } 1937 } 1938 } 1939 1940 impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> 1941 where 1942 K: 'a + Ord, 1943 V: 'a, 1944 { 1945 } 1946 1947 /// An iterator over the values of a map. 1948 pub struct Values<'a, K, V> { 1949 it: Iter<'a, K, V>, 1950 } 1951 1952 impl<'a, K, V> Iterator for Values<'a, K, V> 1953 where 1954 K: 'a + Ord, 1955 V: 'a, 1956 { 1957 type Item = &'a V; 1958 next(&mut self) -> Option<Self::Item>1959 fn next(&mut self) -> Option<Self::Item> { 1960 self.it.next().map(|(_, v)| v) 1961 } 1962 size_hint(&self) -> (usize, Option<usize>)1963 fn size_hint(&self) -> (usize, Option<usize>) { 1964 self.it.size_hint() 1965 } 1966 } 1967 1968 impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> 1969 where 1970 K: 'a + Ord, 1971 V: 'a, 1972 { next_back(&mut self) -> Option<Self::Item>1973 fn next_back(&mut self) -> Option<Self::Item> { 1974 match self.it.next_back() { 1975 None => None, 1976 Some((_, v)) => Some(v), 1977 } 1978 } 1979 } 1980 1981 impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> 1982 where 1983 K: 'a + Ord, 1984 V: 'a, 1985 { 1986 } 1987 1988 impl<K, V, RK, RV> FromIterator<(RK, RV)> for OrdMap<K, V> 1989 where 1990 K: Ord + Clone + From<RK>, 1991 V: Clone + From<RV>, 1992 { from_iter<T>(i: T) -> Self where T: IntoIterator<Item = (RK, RV)>,1993 fn from_iter<T>(i: T) -> Self 1994 where 1995 T: IntoIterator<Item = (RK, RV)>, 1996 { 1997 let mut m = OrdMap::default(); 1998 for (k, v) in i { 1999 m.insert(From::from(k), From::from(v)); 2000 } 2001 m 2002 } 2003 } 2004 2005 impl<'a, K, V> IntoIterator for &'a OrdMap<K, V> 2006 where 2007 K: Ord, 2008 { 2009 type Item = (&'a K, &'a V); 2010 type IntoIter = Iter<'a, K, V>; 2011 into_iter(self) -> Self::IntoIter2012 fn into_iter(self) -> Self::IntoIter { 2013 self.iter() 2014 } 2015 } 2016 2017 impl<K, V> IntoIterator for OrdMap<K, V> 2018 where 2019 K: Ord + Clone, 2020 V: Clone, 2021 { 2022 type Item = (K, V); 2023 type IntoIter = ConsumingIter<(K, V)>; 2024 into_iter(self) -> Self::IntoIter2025 fn into_iter(self) -> Self::IntoIter { 2026 ConsumingIter::new(&self.root, self.size) 2027 } 2028 } 2029 2030 // Conversions 2031 2032 impl<K, V> AsRef<OrdMap<K, V>> for OrdMap<K, V> { as_ref(&self) -> &Self2033 fn as_ref(&self) -> &Self { 2034 self 2035 } 2036 } 2037 2038 impl<'m, 'k, 'v, K, V, OK, OV> From<&'m OrdMap<&'k K, &'v V>> for OrdMap<OK, OV> 2039 where 2040 K: Ord + ToOwned<Owned = OK> + ?Sized, 2041 V: ToOwned<Owned = OV> + ?Sized, 2042 OK: Ord + Clone + Borrow<K>, 2043 OV: Clone + Borrow<V>, 2044 { from(m: &OrdMap<&K, &V>) -> Self2045 fn from(m: &OrdMap<&K, &V>) -> Self { 2046 m.iter() 2047 .map(|(k, v)| ((*k).to_owned(), (*v).to_owned())) 2048 .collect() 2049 } 2050 } 2051 2052 impl<'a, K, V, RK, RV, OK, OV> From<&'a [(RK, RV)]> for OrdMap<K, V> 2053 where 2054 K: Ord + Clone + From<OK>, 2055 V: Clone + From<OV>, 2056 OK: Borrow<RK>, 2057 OV: Borrow<RV>, 2058 RK: ToOwned<Owned = OK>, 2059 RV: ToOwned<Owned = OV>, 2060 { from(m: &'a [(RK, RV)]) -> OrdMap<K, V>2061 fn from(m: &'a [(RK, RV)]) -> OrdMap<K, V> { 2062 m.iter() 2063 .map(|&(ref k, ref v)| (k.to_owned(), v.to_owned())) 2064 .collect() 2065 } 2066 } 2067 2068 impl<K, V, RK, RV> From<Vec<(RK, RV)>> for OrdMap<K, V> 2069 where 2070 K: Ord + Clone + From<RK>, 2071 V: Clone + From<RV>, 2072 { from(m: Vec<(RK, RV)>) -> OrdMap<K, V>2073 fn from(m: Vec<(RK, RV)>) -> OrdMap<K, V> { 2074 m.into_iter().collect() 2075 } 2076 } 2077 2078 impl<'a, K: Ord, V, RK, RV, OK, OV> From<&'a Vec<(RK, RV)>> for OrdMap<K, V> 2079 where 2080 K: Ord + Clone + From<OK>, 2081 V: Clone + From<OV>, 2082 OK: Borrow<RK>, 2083 OV: Borrow<RV>, 2084 RK: ToOwned<Owned = OK>, 2085 RV: ToOwned<Owned = OV>, 2086 { from(m: &'a Vec<(RK, RV)>) -> OrdMap<K, V>2087 fn from(m: &'a Vec<(RK, RV)>) -> OrdMap<K, V> { 2088 m.iter() 2089 .map(|&(ref k, ref v)| (k.to_owned(), v.to_owned())) 2090 .collect() 2091 } 2092 } 2093 2094 impl<K: Ord, V, RK: Eq + Hash, RV> From<collections::HashMap<RK, RV>> for OrdMap<K, V> 2095 where 2096 K: Ord + Clone + From<RK>, 2097 V: Clone + From<RV>, 2098 { from(m: collections::HashMap<RK, RV>) -> OrdMap<K, V>2099 fn from(m: collections::HashMap<RK, RV>) -> OrdMap<K, V> { 2100 m.into_iter().collect() 2101 } 2102 } 2103 2104 impl<'a, K, V, OK, OV, RK, RV> From<&'a collections::HashMap<RK, RV>> for OrdMap<K, V> 2105 where 2106 K: Ord + Clone + From<OK>, 2107 V: Clone + From<OV>, 2108 OK: Borrow<RK>, 2109 OV: Borrow<RV>, 2110 RK: Hash + Eq + ToOwned<Owned = OK>, 2111 RV: ToOwned<Owned = OV>, 2112 { from(m: &'a collections::HashMap<RK, RV>) -> OrdMap<K, V>2113 fn from(m: &'a collections::HashMap<RK, RV>) -> OrdMap<K, V> { 2114 m.iter() 2115 .map(|(k, v)| (k.to_owned(), v.to_owned())) 2116 .collect() 2117 } 2118 } 2119 2120 impl<K: Ord, V, RK, RV> From<collections::BTreeMap<RK, RV>> for OrdMap<K, V> 2121 where 2122 K: Ord + Clone + From<RK>, 2123 V: Clone + From<RV>, 2124 { from(m: collections::BTreeMap<RK, RV>) -> OrdMap<K, V>2125 fn from(m: collections::BTreeMap<RK, RV>) -> OrdMap<K, V> { 2126 m.into_iter().collect() 2127 } 2128 } 2129 2130 impl<'a, K: Ord, V, RK, RV, OK, OV> From<&'a collections::BTreeMap<RK, RV>> for OrdMap<K, V> 2131 where 2132 K: Ord + Clone + From<OK>, 2133 V: Clone + From<OV>, 2134 OK: Borrow<RK>, 2135 OV: Borrow<RV>, 2136 RK: Ord + ToOwned<Owned = OK>, 2137 RV: ToOwned<Owned = OV>, 2138 { from(m: &'a collections::BTreeMap<RK, RV>) -> OrdMap<K, V>2139 fn from(m: &'a collections::BTreeMap<RK, RV>) -> OrdMap<K, V> { 2140 m.iter() 2141 .map(|(k, v)| (k.to_owned(), v.to_owned())) 2142 .collect() 2143 } 2144 } 2145 2146 impl<K: Ord + Hash + Eq + Clone, V: Clone, S: BuildHasher> From<HashMap<K, V, S>> for OrdMap<K, V> { from(m: HashMap<K, V, S>) -> Self2147 fn from(m: HashMap<K, V, S>) -> Self { 2148 m.into_iter().collect() 2149 } 2150 } 2151 2152 impl<'a, K: Ord + Hash + Eq + Clone, V: Clone, S: BuildHasher> From<&'a HashMap<K, V, S>> 2153 for OrdMap<K, V> 2154 { from(m: &'a HashMap<K, V, S>) -> Self2155 fn from(m: &'a HashMap<K, V, S>) -> Self { 2156 m.iter().map(|(k, v)| (k.clone(), v.clone())).collect() 2157 } 2158 } 2159 2160 // Proptest 2161 #[cfg(any(test, feature = "proptest"))] 2162 #[doc(hidden)] 2163 pub mod proptest { 2164 #[deprecated( 2165 since = "14.3.0", 2166 note = "proptest strategies have moved to im::proptest" 2167 )] 2168 pub use crate::proptest::ord_map; 2169 } 2170 2171 // Tests 2172 2173 #[cfg(test)] 2174 mod test { 2175 use super::*; 2176 use crate::proptest::*; 2177 use crate::test::is_sorted; 2178 use ::proptest::num::{i16, usize}; 2179 use ::proptest::{bool, collection, proptest}; 2180 2181 #[test] iterates_in_order()2182 fn iterates_in_order() { 2183 let map = ordmap! { 2184 2 => 22, 2185 1 => 11, 2186 3 => 33, 2187 8 => 88, 2188 9 => 99, 2189 4 => 44, 2190 5 => 55, 2191 7 => 77, 2192 6 => 66 2193 }; 2194 let mut it = map.iter(); 2195 assert_eq!(it.next(), Some((&1, &11))); 2196 assert_eq!(it.next(), Some((&2, &22))); 2197 assert_eq!(it.next(), Some((&3, &33))); 2198 assert_eq!(it.next(), Some((&4, &44))); 2199 assert_eq!(it.next(), Some((&5, &55))); 2200 assert_eq!(it.next(), Some((&6, &66))); 2201 assert_eq!(it.next(), Some((&7, &77))); 2202 assert_eq!(it.next(), Some((&8, &88))); 2203 assert_eq!(it.next(), Some((&9, &99))); 2204 assert_eq!(it.next(), None); 2205 } 2206 2207 #[test] into_iter()2208 fn into_iter() { 2209 let map = ordmap! { 2210 2 => 22, 2211 1 => 11, 2212 3 => 33, 2213 8 => 88, 2214 9 => 99, 2215 4 => 44, 2216 5 => 55, 2217 7 => 77, 2218 6 => 66 2219 }; 2220 let mut vec = vec![]; 2221 for (k, v) in map { 2222 assert_eq!(k * 11, v); 2223 vec.push(k) 2224 } 2225 assert_eq!(vec, vec![1, 2, 3, 4, 5, 6, 7, 8, 9]); 2226 } 2227 2228 #[test] deletes_correctly()2229 fn deletes_correctly() { 2230 let map = ordmap! { 2231 2 => 22, 2232 1 => 11, 2233 3 => 33, 2234 8 => 88, 2235 9 => 99, 2236 4 => 44, 2237 5 => 55, 2238 7 => 77, 2239 6 => 66 2240 }; 2241 assert_eq!(map.extract(&11), None); 2242 let (popped, less) = map.extract(&5).unwrap(); 2243 assert_eq!(popped, 55); 2244 let mut it = less.iter(); 2245 assert_eq!(it.next(), Some((&1, &11))); 2246 assert_eq!(it.next(), Some((&2, &22))); 2247 assert_eq!(it.next(), Some((&3, &33))); 2248 assert_eq!(it.next(), Some((&4, &44))); 2249 assert_eq!(it.next(), Some((&6, &66))); 2250 assert_eq!(it.next(), Some((&7, &77))); 2251 assert_eq!(it.next(), Some((&8, &88))); 2252 assert_eq!(it.next(), Some((&9, &99))); 2253 assert_eq!(it.next(), None); 2254 } 2255 2256 #[test] debug_output()2257 fn debug_output() { 2258 assert_eq!( 2259 format!("{:?}", ordmap! { 3 => 4, 5 => 6, 1 => 2 }), 2260 "{1: 2, 3: 4, 5: 6}" 2261 ); 2262 } 2263 2264 #[test] equality2()2265 fn equality2() { 2266 let v1 = "1".to_string(); 2267 let v2 = "1".to_string(); 2268 assert_eq!(v1, v2); 2269 let p1 = Vec::<String>::new(); 2270 let p2 = Vec::<String>::new(); 2271 assert_eq!(p1, p2); 2272 let c1 = OrdMap::unit(v1, p1); 2273 let c2 = OrdMap::unit(v2, p2); 2274 assert_eq!(c1, c2); 2275 } 2276 2277 #[test] insert_remove_single_mut()2278 fn insert_remove_single_mut() { 2279 let mut m = OrdMap::new(); 2280 m.insert(0, 0); 2281 assert_eq!(OrdMap::unit(0, 0), m); 2282 m.remove(&0); 2283 assert_eq!(OrdMap::new(), m); 2284 } 2285 2286 #[test] double_ended_iterator_1()2287 fn double_ended_iterator_1() { 2288 let m = ordmap! {1 => 1, 2 => 2, 3 => 3, 4 => 4}; 2289 let mut it = m.iter(); 2290 assert_eq!(Some((&1, &1)), it.next()); 2291 assert_eq!(Some((&4, &4)), it.next_back()); 2292 assert_eq!(Some((&2, &2)), it.next()); 2293 assert_eq!(Some((&3, &3)), it.next_back()); 2294 assert_eq!(None, it.next()); 2295 } 2296 2297 #[test] double_ended_iterator_2()2298 fn double_ended_iterator_2() { 2299 let m = ordmap! {1 => 1, 2 => 2, 3 => 3, 4 => 4}; 2300 let mut it = m.iter(); 2301 assert_eq!(Some((&1, &1)), it.next()); 2302 assert_eq!(Some((&4, &4)), it.next_back()); 2303 assert_eq!(Some((&2, &2)), it.next()); 2304 assert_eq!(Some((&3, &3)), it.next_back()); 2305 assert_eq!(None, it.next_back()); 2306 } 2307 2308 #[test] safe_mutation()2309 fn safe_mutation() { 2310 let v1 = OrdMap::from_iter((0..131_072).map(|i| (i, i))); 2311 let mut v2 = v1.clone(); 2312 v2.insert(131_000, 23); 2313 assert_eq!(Some(&23), v2.get(&131_000)); 2314 assert_eq!(Some(&131_000), v1.get(&131_000)); 2315 } 2316 2317 #[test] index_operator()2318 fn index_operator() { 2319 let mut map = ordmap! {1 => 2, 3 => 4, 5 => 6}; 2320 assert_eq!(4, map[&3]); 2321 map[&3] = 8; 2322 assert_eq!(ordmap! {1 => 2, 3 => 8, 5 => 6}, map); 2323 } 2324 2325 #[test] entry_api()2326 fn entry_api() { 2327 let mut map = ordmap! {"bar" => 5}; 2328 map.entry(&"foo").and_modify(|v| *v += 5).or_insert(1); 2329 assert_eq!(1, map[&"foo"]); 2330 map.entry(&"foo").and_modify(|v| *v += 5).or_insert(1); 2331 assert_eq!(6, map[&"foo"]); 2332 map.entry(&"bar").and_modify(|v| *v += 5).or_insert(1); 2333 assert_eq!(10, map[&"bar"]); 2334 assert_eq!( 2335 10, 2336 match map.entry(&"bar") { 2337 Entry::Occupied(entry) => entry.remove(), 2338 _ => panic!(), 2339 } 2340 ); 2341 assert!(!map.contains_key(&"bar")); 2342 } 2343 2344 #[test] match_string_keys_with_string_slices()2345 fn match_string_keys_with_string_slices() { 2346 let mut map: OrdMap<String, i32> = 2347 From::from(ºap! { "foo" => &1, "bar" => &2, "baz" => &3 }); 2348 assert_eq!(Some(&1), map.get("foo")); 2349 map = map.without("foo"); 2350 assert_eq!(Some(3), map.remove("baz")); 2351 map["bar"] = 8; 2352 assert_eq!(8, map["bar"]); 2353 } 2354 2355 #[test] ranged_iter()2356 fn ranged_iter() { 2357 let map: OrdMap<i32, i32> = ordmap![1=>2, 2=>3, 3=>4, 4=>5, 5=>6]; 2358 let range: Vec<(i32, i32)> = map.range(..).map(|(k, v)| (*k, *v)).collect(); 2359 assert_eq!(vec![(1, 2), (2, 3), (3, 4), (4, 5), (5, 6)], range); 2360 let range: Vec<(i32, i32)> = map.range(..).rev().map(|(k, v)| (*k, *v)).collect(); 2361 assert_eq!(vec![(5, 6), (4, 5), (3, 4), (2, 3), (1, 2)], range); 2362 let range: Vec<(i32, i32)> = map.range(2..5).map(|(k, v)| (*k, *v)).collect(); 2363 assert_eq!(vec![(2, 3), (3, 4), (4, 5)], range); 2364 let range: Vec<(i32, i32)> = map.range(2..5).rev().map(|(k, v)| (*k, *v)).collect(); 2365 assert_eq!(vec![(4, 5), (3, 4), (2, 3)], range); 2366 let range: Vec<(i32, i32)> = map.range(3..).map(|(k, v)| (*k, *v)).collect(); 2367 assert_eq!(vec![(3, 4), (4, 5), (5, 6)], range); 2368 let range: Vec<(i32, i32)> = map.range(3..).rev().map(|(k, v)| (*k, *v)).collect(); 2369 assert_eq!(vec![(5, 6), (4, 5), (3, 4)], range); 2370 let range: Vec<(i32, i32)> = map.range(..4).map(|(k, v)| (*k, *v)).collect(); 2371 assert_eq!(vec![(1, 2), (2, 3), (3, 4)], range); 2372 let range: Vec<(i32, i32)> = map.range(..4).rev().map(|(k, v)| (*k, *v)).collect(); 2373 assert_eq!(vec![(3, 4), (2, 3), (1, 2)], range); 2374 let range: Vec<(i32, i32)> = map.range(..=3).map(|(k, v)| (*k, *v)).collect(); 2375 assert_eq!(vec![(1, 2), (2, 3), (3, 4)], range); 2376 let range: Vec<(i32, i32)> = map.range(..=3).rev().map(|(k, v)| (*k, *v)).collect(); 2377 assert_eq!(vec![(3, 4), (2, 3), (1, 2)], range); 2378 } 2379 2380 proptest! { 2381 #[test] 2382 fn length(ref input in collection::btree_map(i16::ANY, i16::ANY, 0..1000)) { 2383 let map: OrdMap<i32, i32> = OrdMap::from(input.clone()); 2384 input.len() == map.len() 2385 } 2386 2387 #[test] 2388 fn order(ref input in collection::hash_map(i16::ANY, i16::ANY, 0..1000)) { 2389 let map: OrdMap<i32, i32> = OrdMap::from(input.clone()); 2390 is_sorted(map.keys()) 2391 } 2392 2393 #[test] 2394 fn overwrite_values(ref vec in collection::vec((i16::ANY, i16::ANY), 1..1000), index_rand in usize::ANY, new_val in i16::ANY) { 2395 let index = vec[index_rand % vec.len()].0; 2396 let map1 = OrdMap::from_iter(vec.clone()); 2397 let map2 = map1.update(index, new_val); 2398 for (k, v) in map2 { 2399 if k == index { 2400 assert_eq!(v, new_val); 2401 } else { 2402 match map1.get(&k) { 2403 None => panic!("map1 didn't have key {:?}", k), 2404 Some(other_v) => { 2405 assert_eq!(v, *other_v); 2406 } 2407 } 2408 } 2409 } 2410 } 2411 2412 #[test] 2413 fn delete_values(ref vec in collection::vec((usize::ANY, usize::ANY), 1..1000), index_rand in usize::ANY) { 2414 let index = vec[index_rand % vec.len()].0; 2415 let map1: OrdMap<usize, usize> = OrdMap::from_iter(vec.clone()); 2416 let map2 = map1.without(&index); 2417 assert_eq!(map1.len(), map2.len() + 1); 2418 for k in map2.keys() { 2419 assert_ne!(*k, index); 2420 } 2421 } 2422 2423 #[test] 2424 fn insert_and_delete_values( 2425 ref input in ord_map(0usize..64, 0usize..64, 1..1000), 2426 ref ops in collection::vec((bool::ANY, usize::ANY, usize::ANY), 1..1000) 2427 ) { 2428 let mut map = input.clone(); 2429 let mut tree: collections::BTreeMap<usize, usize> = input.iter().map(|(k, v)| (*k, *v)).collect(); 2430 for (ins, key, val) in ops { 2431 if *ins { 2432 tree.insert(*key, *val); 2433 map = map.update(*key, *val) 2434 } else { 2435 tree.remove(key); 2436 map = map.without(key) 2437 } 2438 } 2439 assert!(map.iter().map(|(k, v)| (*k, *v)).eq(tree.iter().map(|(k, v)| (*k, *v)))); 2440 } 2441 2442 #[test] 2443 fn proptest_works(ref m in ord_map(0..9999, ".*", 10..100)) { 2444 assert!(m.len() < 100); 2445 assert!(m.len() >= 10); 2446 } 2447 2448 #[test] 2449 fn insert_and_length(ref m in collection::hash_map(i16::ANY, i16::ANY, 0..1000)) { 2450 let mut map: OrdMap<i16, i16> = OrdMap::new(); 2451 for (k, v) in m.iter() { 2452 map = map.update(*k, *v) 2453 } 2454 assert_eq!(m.len(), map.len()); 2455 } 2456 2457 #[test] 2458 fn from_iterator(ref m in collection::hash_map(i16::ANY, i16::ANY, 0..1000)) { 2459 let map: OrdMap<i16, i16> = 2460 FromIterator::from_iter(m.iter().map(|(k, v)| (*k, *v))); 2461 assert_eq!(m.len(), map.len()); 2462 } 2463 2464 #[test] 2465 fn iterate_over(ref m in collection::hash_map(i16::ANY, i16::ANY, 0..1000)) { 2466 let map: OrdMap<i16, i16> = 2467 FromIterator::from_iter(m.iter().map(|(k, v)| (*k, *v))); 2468 assert_eq!(m.len(), map.iter().count()); 2469 } 2470 2471 #[test] 2472 fn equality(ref m in collection::hash_map(i16::ANY, i16::ANY, 0..1000)) { 2473 let map1: OrdMap<i16, i16> = 2474 FromIterator::from_iter(m.iter().map(|(k, v)| (*k, *v))); 2475 let map2: OrdMap<i16, i16> = 2476 FromIterator::from_iter(m.iter().map(|(k, v)| (*k, *v))); 2477 assert_eq!(map1, map2); 2478 } 2479 2480 #[test] 2481 fn lookup(ref m in ord_map(i16::ANY, i16::ANY, 0..1000)) { 2482 let map: OrdMap<i16, i16> = 2483 FromIterator::from_iter(m.iter().map(|(k, v)| (*k, *v))); 2484 for (k, v) in m.iter() { 2485 assert_eq!(Some(*v), map.get(k).cloned()); 2486 } 2487 } 2488 2489 #[test] 2490 fn remove(ref m in ord_map(i16::ANY, i16::ANY, 0..1000)) { 2491 let mut map: OrdMap<i16, i16> = 2492 FromIterator::from_iter(m.iter().map(|(k, v)| (*k, *v))); 2493 for k in m.keys() { 2494 let l = map.len(); 2495 assert_eq!(m.get(k).cloned(), map.get(k).cloned()); 2496 map = map.without(k); 2497 assert_eq!(None, map.get(k)); 2498 assert_eq!(l - 1, map.len()); 2499 } 2500 } 2501 2502 #[test] 2503 fn insert_mut(ref m in ord_map(i16::ANY, i16::ANY, 0..1000)) { 2504 let mut mut_map = OrdMap::new(); 2505 let mut map = OrdMap::new(); 2506 for (k, v) in m.iter() { 2507 map = map.update(*k, *v); 2508 mut_map.insert(*k, *v); 2509 } 2510 assert_eq!(map, mut_map); 2511 } 2512 2513 #[test] 2514 fn remove_mut(ref orig in ord_map(i16::ANY, i16::ANY, 0..1000)) { 2515 let mut map = orig.clone(); 2516 for key in orig.keys() { 2517 let len = map.len(); 2518 assert_eq!(orig.get(key), map.get(key)); 2519 assert_eq!(orig.get(key).cloned(), map.remove(key)); 2520 assert_eq!(None, map.get(key)); 2521 assert_eq!(len - 1, map.len()); 2522 } 2523 } 2524 2525 #[test] 2526 fn remove_alien(ref orig in collection::hash_map(i16::ANY, i16::ANY, 0..1000)) { 2527 let mut map = OrdMap::<i16, i16>::from(orig.clone()); 2528 for key in orig.keys() { 2529 let len = map.len(); 2530 assert_eq!(orig.get(key), map.get(key)); 2531 assert_eq!(orig.get(key).cloned(), map.remove(key)); 2532 assert_eq!(None, map.get(key)); 2533 assert_eq!(len - 1, map.len()); 2534 } 2535 } 2536 2537 #[test] 2538 fn delete_and_reinsert( 2539 ref input in collection::hash_map(i16::ANY, i16::ANY, 1..1000), 2540 index_rand in usize::ANY 2541 ) { 2542 let index = *input.keys().nth(index_rand % input.len()).unwrap(); 2543 let map1 = OrdMap::from_iter(input.clone()); 2544 let (val, map2): (i16, _) = map1.extract(&index).unwrap(); 2545 let map3 = map2.update(index, val); 2546 for key in map2.keys() { 2547 assert!(*key != index); 2548 } 2549 assert_eq!(map1.len(), map2.len() + 1); 2550 assert_eq!(map1, map3); 2551 } 2552 2553 #[test] 2554 fn exact_size_iterator(ref m in ord_map(i16::ANY, i16::ANY, 1..1000)) { 2555 let mut should_be = m.len(); 2556 let mut it = m.iter(); 2557 loop { 2558 assert_eq!(should_be, it.len()); 2559 match it.next() { 2560 None => break, 2561 Some(_) => should_be -= 1, 2562 } 2563 } 2564 assert_eq!(0, it.len()); 2565 } 2566 2567 #[test] 2568 fn diff_all_values(a in collection::vec((usize::ANY, usize::ANY), 1..1000), b in collection::vec((usize::ANY, usize::ANY), 1..1000)) { 2569 let a: OrdMap<usize, usize> = OrdMap::from(a); 2570 let b: OrdMap<usize, usize> = OrdMap::from(b); 2571 2572 let diff: Vec<_> = a.diff(&b).collect(); 2573 let union = b.clone().union(a.clone()); 2574 let expected: Vec<_> = union.iter().filter_map(|(k, v)| { 2575 if a.contains_key(&k) { 2576 if b.contains_key(&k) { 2577 let old = a.get(&k).unwrap(); 2578 if old != v { 2579 Some(DiffItem::Update { 2580 old: (k, old), 2581 new: (k, v), 2582 }) 2583 } else { 2584 None 2585 } 2586 } else { 2587 Some(DiffItem::Remove(k, v)) 2588 } 2589 } else { 2590 Some(DiffItem::Add(k, v)) 2591 } 2592 }).collect(); 2593 assert_eq!(expected, diff); 2594 } 2595 } 2596 } 2597