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 set. 6 //! 7 //! An immutable ordered set implemented as a [B-tree] [1]. 8 //! 9 //! Most operations on this type of set are O(log n). A 10 //! [`HashSet`][hashset::HashSet] is usually a better choice for 11 //! performance, but the `OrdSet` has the advantage of only requiring 12 //! an [`Ord`][std::cmp::Ord] constraint on its values, and of being 13 //! ordered, so values always come out from lowest to highest, where a 14 //! [`HashSet`][hashset::HashSet] has no guaranteed ordering. 15 //! 16 //! [1]: https://en.wikipedia.org/wiki/B-tree 17 //! [hashset::HashSet]: ../hashset/struct.HashSet.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, IntoIterator, Sum}; 26 use std::ops::{Add, Deref, Mul, RangeBounds}; 27 28 use crate::hashset::HashSet; 29 use crate::nodes::btree::{ 30 BTreeValue, ConsumingIter as ConsumingNodeIter, DiffIter as NodeDiffIter, Insert, 31 Iter as NodeIter, Node, Remove, 32 }; 33 #[cfg(has_specialisation)] 34 use crate::util::linear_search_by; 35 use crate::util::{Pool, PoolRef}; 36 37 pub use crate::nodes::btree::DiffItem; 38 39 /// Construct a set from a sequence of values. 40 /// 41 /// # Examples 42 /// 43 /// ``` 44 /// # #[macro_use] extern crate im; 45 /// # use im::ordset::OrdSet; 46 /// # fn main() { 47 /// assert_eq!( 48 /// ordset![1, 2, 3], 49 /// OrdSet::from(vec![1, 2, 3]) 50 /// ); 51 /// # } 52 /// ``` 53 #[macro_export] 54 macro_rules! ordset { 55 () => { $crate::ordset::OrdSet::new() }; 56 57 ( $($x:expr),* ) => {{ 58 let mut l = $crate::ordset::OrdSet::new(); 59 $( 60 l.insert($x); 61 )* 62 l 63 }}; 64 } 65 66 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Debug)] 67 struct Value<A>(A); 68 69 impl<A> Deref for Value<A> { 70 type Target = A; deref(&self) -> &Self::Target71 fn deref(&self) -> &Self::Target { 72 &self.0 73 } 74 } 75 76 // FIXME lacking specialisation, we can't simply implement `BTreeValue` 77 // for `A`, we have to use the `Value<A>` indirection. 78 #[cfg(not(has_specialisation))] 79 impl<A: Ord> BTreeValue for Value<A> { 80 type Key = A; 81 ptr_eq(&self, _other: &Self) -> bool82 fn ptr_eq(&self, _other: &Self) -> bool { 83 false 84 } 85 search_key<BK>(slice: &[Self], key: &BK) -> Result<usize, usize> where BK: Ord + ?Sized, Self::Key: Borrow<BK>,86 fn search_key<BK>(slice: &[Self], key: &BK) -> Result<usize, usize> 87 where 88 BK: Ord + ?Sized, 89 Self::Key: Borrow<BK>, 90 { 91 slice.binary_search_by(|value| Self::Key::borrow(value).cmp(key)) 92 } 93 search_value(slice: &[Self], key: &Self) -> Result<usize, usize>94 fn search_value(slice: &[Self], key: &Self) -> Result<usize, usize> { 95 slice.binary_search_by(|value| value.cmp(key)) 96 } 97 cmp_keys<BK>(&self, other: &BK) -> Ordering where BK: Ord + ?Sized, Self::Key: Borrow<BK>,98 fn cmp_keys<BK>(&self, other: &BK) -> Ordering 99 where 100 BK: Ord + ?Sized, 101 Self::Key: Borrow<BK>, 102 { 103 Self::Key::borrow(self).cmp(other) 104 } 105 cmp_values(&self, other: &Self) -> Ordering106 fn cmp_values(&self, other: &Self) -> Ordering { 107 self.cmp(other) 108 } 109 } 110 111 #[cfg(has_specialisation)] 112 impl<A: Ord> BTreeValue for Value<A> { 113 type Key = A; 114 ptr_eq(&self, _other: &Self) -> bool115 fn ptr_eq(&self, _other: &Self) -> bool { 116 false 117 } 118 search_key<BK>(slice: &[Self], key: &BK) -> Result<usize, usize> where BK: Ord + ?Sized, Self::Key: Borrow<BK>,119 default fn search_key<BK>(slice: &[Self], key: &BK) -> Result<usize, usize> 120 where 121 BK: Ord + ?Sized, 122 Self::Key: Borrow<BK>, 123 { 124 slice.binary_search_by(|value| Self::Key::borrow(value).cmp(key)) 125 } 126 search_value(slice: &[Self], key: &Self) -> Result<usize, usize>127 default fn search_value(slice: &[Self], key: &Self) -> Result<usize, usize> { 128 slice.binary_search_by(|value| value.cmp(key)) 129 } 130 cmp_keys<BK>(&self, other: &BK) -> Ordering where BK: Ord + ?Sized, Self::Key: Borrow<BK>,131 fn cmp_keys<BK>(&self, other: &BK) -> Ordering 132 where 133 BK: Ord + ?Sized, 134 Self::Key: Borrow<BK>, 135 { 136 Self::Key::borrow(self).cmp(other) 137 } 138 cmp_values(&self, other: &Self) -> Ordering139 fn cmp_values(&self, other: &Self) -> Ordering { 140 self.cmp(other) 141 } 142 } 143 144 #[cfg(has_specialisation)] 145 impl<A: Ord + Copy> BTreeValue for Value<A> { search_key<BK>(slice: &[Self], key: &BK) -> Result<usize, usize> where BK: Ord + ?Sized, Self::Key: Borrow<BK>,146 fn search_key<BK>(slice: &[Self], key: &BK) -> Result<usize, usize> 147 where 148 BK: Ord + ?Sized, 149 Self::Key: Borrow<BK>, 150 { 151 linear_search_by(slice, |value| Self::Key::borrow(value).cmp(key)) 152 } 153 search_value(slice: &[Self], key: &Self) -> Result<usize, usize>154 fn search_value(slice: &[Self], key: &Self) -> Result<usize, usize> { 155 linear_search_by(slice, |value| value.cmp(key)) 156 } 157 } 158 159 def_pool!(OrdSetPool<A>, Node<Value<A>>); 160 161 /// An ordered set. 162 /// 163 /// An immutable ordered set implemented as a [B-tree] [1]. 164 /// 165 /// Most operations on this type of set are O(log n). A 166 /// [`HashSet`][hashset::HashSet] is usually a better choice for 167 /// performance, but the `OrdSet` has the advantage of only requiring 168 /// an [`Ord`][std::cmp::Ord] constraint on its values, and of being 169 /// ordered, so values always come out from lowest to highest, where a 170 /// [`HashSet`][hashset::HashSet] has no guaranteed ordering. 171 /// 172 /// [1]: https://en.wikipedia.org/wiki/B-tree 173 /// [hashset::HashSet]: ../hashset/struct.HashSet.html 174 /// [std::cmp::Ord]: https://doc.rust-lang.org/std/cmp/trait.Ord.html 175 pub struct OrdSet<A> { 176 size: usize, 177 pool: OrdSetPool<A>, 178 root: PoolRef<Node<Value<A>>>, 179 } 180 181 impl<A> OrdSet<A> { 182 /// Construct an empty set. 183 #[must_use] new() -> Self184 pub fn new() -> Self { 185 let pool = OrdSetPool::default(); 186 let root = PoolRef::default(&pool.0); 187 OrdSet { 188 size: 0, 189 pool, 190 root, 191 } 192 } 193 194 /// Construct an empty set using a specific memory pool. 195 #[cfg(feature = "pool")] 196 #[must_use] with_pool(pool: &OrdSetPool<A>) -> Self197 pub fn with_pool(pool: &OrdSetPool<A>) -> Self { 198 let root = PoolRef::default(&pool.0); 199 OrdSet { 200 size: 0, 201 pool: pool.clone(), 202 root, 203 } 204 } 205 206 /// Construct a set with a single value. 207 /// 208 /// # Examples 209 /// 210 /// ``` 211 /// # #[macro_use] extern crate im; 212 /// # use im::ordset::OrdSet; 213 /// let set = OrdSet::unit(123); 214 /// assert!(set.contains(&123)); 215 /// ``` 216 #[inline] 217 #[must_use] unit(a: A) -> Self218 pub fn unit(a: A) -> Self { 219 let pool = OrdSetPool::default(); 220 let root = PoolRef::new(&pool.0, Node::unit(Value(a))); 221 OrdSet { 222 size: 1, 223 pool, 224 root, 225 } 226 } 227 228 /// Test whether a set is empty. 229 /// 230 /// Time: O(1) 231 /// 232 /// # Examples 233 /// 234 /// ``` 235 /// # #[macro_use] extern crate im; 236 /// # use im::ordset::OrdSet; 237 /// assert!( 238 /// !ordset![1, 2, 3].is_empty() 239 /// ); 240 /// assert!( 241 /// OrdSet::<i32>::new().is_empty() 242 /// ); 243 /// ``` 244 #[inline] 245 #[must_use] is_empty(&self) -> bool246 pub fn is_empty(&self) -> bool { 247 self.len() == 0 248 } 249 250 /// Get the size of a set. 251 /// 252 /// Time: O(1) 253 /// 254 /// # Examples 255 /// 256 /// ``` 257 /// # #[macro_use] extern crate im; 258 /// # use im::ordset::OrdSet; 259 /// assert_eq!(3, ordset![1, 2, 3].len()); 260 /// ``` 261 #[inline] 262 #[must_use] len(&self) -> usize263 pub fn len(&self) -> usize { 264 self.size 265 } 266 267 /// Test whether two sets refer to the same content in memory. 268 /// 269 /// This is true if the two sides are references to the same set, 270 /// or if the two sets refer to the same root node. 271 /// 272 /// This would return true if you're comparing a set to itself, or 273 /// if you're comparing a set to a fresh clone of itself. 274 /// 275 /// Time: O(1) ptr_eq(&self, other: &Self) -> bool276 pub fn ptr_eq(&self, other: &Self) -> bool { 277 std::ptr::eq(self, other) || PoolRef::ptr_eq(&self.root, &other.root) 278 } 279 280 /// Get a reference to the memory pool used by this set. 281 /// 282 /// Note that if you didn't specifically construct it with a pool, you'll 283 /// get back a reference to a pool of size 0. 284 #[cfg(feature = "pool")] pool(&self) -> &OrdSetPool<A>285 pub fn pool(&self) -> &OrdSetPool<A> { 286 &self.pool 287 } 288 289 /// Discard all elements from the set. 290 /// 291 /// This leaves you with an empty set, and all elements that 292 /// were previously inside it are dropped. 293 /// 294 /// Time: O(n) 295 /// 296 /// # Examples 297 /// 298 /// ``` 299 /// # #[macro_use] extern crate im; 300 /// # use im::OrdSet; 301 /// let mut set = ordset![1, 2, 3]; 302 /// set.clear(); 303 /// assert!(set.is_empty()); 304 /// ``` clear(&mut self)305 pub fn clear(&mut self) { 306 if !self.is_empty() { 307 self.root = PoolRef::default(&self.pool.0); 308 self.size = 0; 309 } 310 } 311 } 312 313 impl<A> OrdSet<A> 314 where 315 A: Ord, 316 { 317 /// Get the smallest value in a set. 318 /// 319 /// If the set is empty, returns `None`. 320 /// 321 /// Time: O(log n) 322 #[must_use] get_min(&self) -> Option<&A>323 pub fn get_min(&self) -> Option<&A> { 324 self.root.min().map(Deref::deref) 325 } 326 327 /// Get the largest value in a set. 328 /// 329 /// If the set is empty, returns `None`. 330 /// 331 /// Time: O(log n) 332 #[must_use] get_max(&self) -> Option<&A>333 pub fn get_max(&self) -> Option<&A> { 334 self.root.max().map(Deref::deref) 335 } 336 337 /// Create an iterator over the contents of the set. 338 #[must_use] iter(&self) -> Iter<'_, A>339 pub fn iter(&self) -> Iter<'_, A> { 340 Iter { 341 it: NodeIter::new(&self.root, self.size, ..), 342 } 343 } 344 345 /// Create an iterator over a range inside the set. 346 #[must_use] range<R, BA>(&self, range: R) -> RangedIter<'_, A> where R: RangeBounds<BA>, A: Borrow<BA>, BA: Ord + ?Sized,347 pub fn range<R, BA>(&self, range: R) -> RangedIter<'_, A> 348 where 349 R: RangeBounds<BA>, 350 A: Borrow<BA>, 351 BA: Ord + ?Sized, 352 { 353 RangedIter { 354 it: NodeIter::new(&self.root, self.size, range), 355 } 356 } 357 358 /// Get an iterator over the differences between this set and 359 /// another, i.e. the set of entries to add or remove to this set 360 /// in order to make it equal to the other set. 361 /// 362 /// This function will avoid visiting nodes which are shared 363 /// between the two sets, meaning that even very large sets can be 364 /// compared quickly if most of their structure is shared. 365 /// 366 /// Time: O(n) (where n is the number of unique elements across 367 /// the two sets, minus the number of elements belonging to nodes 368 /// shared between them) 369 #[must_use] diff<'a>(&'a self, other: &'a Self) -> DiffIter<'_, A>370 pub fn diff<'a>(&'a self, other: &'a Self) -> DiffIter<'_, A> { 371 DiffIter { 372 it: NodeDiffIter::new(&self.root, &other.root), 373 } 374 } 375 376 /// Test if a value is part of a set. 377 /// 378 /// Time: O(log n) 379 /// 380 /// # Examples 381 /// 382 /// ``` 383 /// # #[macro_use] extern crate im; 384 /// # use im::ordset::OrdSet; 385 /// let mut set = ordset!{1, 2, 3}; 386 /// assert!(set.contains(&1)); 387 /// assert!(!set.contains(&4)); 388 /// ``` 389 #[inline] 390 #[must_use] contains<BA>(&self, a: &BA) -> bool where BA: Ord + ?Sized, A: Borrow<BA>,391 pub fn contains<BA>(&self, a: &BA) -> bool 392 where 393 BA: Ord + ?Sized, 394 A: Borrow<BA>, 395 { 396 self.root.lookup(a).is_some() 397 } 398 399 /// Get the closest smaller value in a set to a given value. 400 /// 401 /// If the set contains the given value, this is returned. 402 /// Otherwise, the closest value in the set smaller than the 403 /// given value is returned. If the smallest value in the set 404 /// is larger than the given value, `None` is returned. 405 /// 406 /// # Examples 407 /// 408 /// ```rust 409 /// # #[macro_use] extern crate im; 410 /// # use im::OrdSet; 411 /// let set = ordset![1, 3, 5, 7, 9]; 412 /// assert_eq!(Some(&5), set.get_prev(&6)); 413 /// ``` 414 #[must_use] get_prev(&self, key: &A) -> Option<&A>415 pub fn get_prev(&self, key: &A) -> Option<&A> { 416 self.root.lookup_prev(key).map(|v| &v.0) 417 } 418 419 /// Get the closest larger value in a set to a given value. 420 /// 421 /// If the set contains the given value, this is returned. 422 /// Otherwise, the closest value in the set larger than the 423 /// given value is returned. If the largest value in the set 424 /// is smaller than the given value, `None` is returned. 425 /// 426 /// # Examples 427 /// 428 /// ```rust 429 /// # #[macro_use] extern crate im; 430 /// # use im::OrdSet; 431 /// let set = ordset![1, 3, 5, 7, 9]; 432 /// assert_eq!(Some(&5), set.get_next(&4)); 433 /// ``` 434 #[must_use] get_next(&self, key: &A) -> Option<&A>435 pub fn get_next(&self, key: &A) -> Option<&A> { 436 self.root.lookup_next(key).map(|v| &v.0) 437 } 438 439 /// Test whether a set is a subset of another set, meaning that 440 /// all values in our set must also be in the other set. 441 /// 442 /// Time: O(n log m) where m is the size of the other set 443 #[must_use] is_subset<RS>(&self, other: RS) -> bool where RS: Borrow<Self>,444 pub fn is_subset<RS>(&self, other: RS) -> bool 445 where 446 RS: Borrow<Self>, 447 { 448 let other = other.borrow(); 449 if other.len() < self.len() { 450 return false; 451 } 452 self.iter().all(|a| other.contains(&a)) 453 } 454 455 /// Test whether a set is a proper subset of another set, meaning 456 /// that all values in our set must also be in the other set. A 457 /// proper subset must also be smaller than the other set. 458 /// 459 /// Time: O(n log m) where m is the size of the other set 460 #[must_use] is_proper_subset<RS>(&self, other: RS) -> bool where RS: Borrow<Self>,461 pub fn is_proper_subset<RS>(&self, other: RS) -> bool 462 where 463 RS: Borrow<Self>, 464 { 465 self.len() != other.borrow().len() && self.is_subset(other) 466 } 467 } 468 469 impl<A> OrdSet<A> 470 where 471 A: Ord + Clone, 472 { 473 /// Insert a value into a set. 474 /// 475 /// Time: O(log n) 476 /// 477 /// # Examples 478 /// 479 /// ``` 480 /// # #[macro_use] extern crate im; 481 /// # use im::ordset::OrdSet; 482 /// let mut set = ordset!{}; 483 /// set.insert(123); 484 /// set.insert(456); 485 /// assert_eq!( 486 /// set, 487 /// ordset![123, 456] 488 /// ); 489 /// ``` 490 #[inline] insert(&mut self, a: A) -> Option<A>491 pub fn insert(&mut self, a: A) -> Option<A> { 492 let new_root = { 493 let root = PoolRef::make_mut(&self.pool.0, &mut self.root); 494 match root.insert(&self.pool.0, Value(a)) { 495 Insert::Replaced(Value(old_value)) => return Some(old_value), 496 Insert::Added => { 497 self.size += 1; 498 return None; 499 } 500 Insert::Split(left, median, right) => PoolRef::new( 501 &self.pool.0, 502 Node::new_from_split(&self.pool.0, left, median, right), 503 ), 504 } 505 }; 506 self.size += 1; 507 self.root = new_root; 508 None 509 } 510 511 /// Remove a value from a set. 512 /// 513 /// Time: O(log n) 514 #[inline] remove<BA>(&mut self, a: &BA) -> Option<A> where BA: Ord + ?Sized, A: Borrow<BA>,515 pub fn remove<BA>(&mut self, a: &BA) -> Option<A> 516 where 517 BA: Ord + ?Sized, 518 A: Borrow<BA>, 519 { 520 let (new_root, removed_value) = { 521 let root = PoolRef::make_mut(&self.pool.0, &mut self.root); 522 match root.remove(&self.pool.0, a) { 523 Remove::Update(value, root) => (PoolRef::new(&self.pool.0, root), Some(value.0)), 524 Remove::Removed(value) => { 525 self.size -= 1; 526 return Some(value.0); 527 } 528 Remove::NoChange => return None, 529 } 530 }; 531 self.size -= 1; 532 self.root = new_root; 533 removed_value 534 } 535 536 /// Remove the smallest value from a set. 537 /// 538 /// Time: O(log n) remove_min(&mut self) -> Option<A>539 pub fn remove_min(&mut self) -> Option<A> { 540 // FIXME implement this at the node level for better efficiency 541 let key = match self.get_min() { 542 None => return None, 543 Some(v) => v, 544 } 545 .clone(); 546 self.remove(&key) 547 } 548 549 /// Remove the largest value from a set. 550 /// 551 /// Time: O(log n) remove_max(&mut self) -> Option<A>552 pub fn remove_max(&mut self) -> Option<A> { 553 // FIXME implement this at the node level for better efficiency 554 let key = match self.get_max() { 555 None => return None, 556 Some(v) => v, 557 } 558 .clone(); 559 self.remove(&key) 560 } 561 562 /// Construct a new set from the current set with the given value 563 /// added. 564 /// 565 /// Time: O(log n) 566 /// 567 /// # Examples 568 /// 569 /// ``` 570 /// # #[macro_use] extern crate im; 571 /// # use im::ordset::OrdSet; 572 /// let set = ordset![456]; 573 /// assert_eq!( 574 /// set.update(123), 575 /// ordset![123, 456] 576 /// ); 577 /// ``` 578 #[must_use] update(&self, a: A) -> Self579 pub fn update(&self, a: A) -> Self { 580 let mut out = self.clone(); 581 out.insert(a); 582 out 583 } 584 585 /// Construct a new set with the given value removed if it's in 586 /// the set. 587 /// 588 /// Time: O(log n) 589 #[must_use] without<BA>(&self, a: &BA) -> Self where BA: Ord + ?Sized, A: Borrow<BA>,590 pub fn without<BA>(&self, a: &BA) -> Self 591 where 592 BA: Ord + ?Sized, 593 A: Borrow<BA>, 594 { 595 let mut out = self.clone(); 596 out.remove(a); 597 out 598 } 599 600 /// Remove the smallest value from a set, and return that value as 601 /// well as the updated set. 602 /// 603 /// Time: O(log n) 604 #[must_use] without_min(&self) -> (Option<A>, Self)605 pub fn without_min(&self) -> (Option<A>, Self) { 606 match self.get_min() { 607 Some(v) => (Some(v.clone()), self.without(&v)), 608 None => (None, self.clone()), 609 } 610 } 611 612 /// Remove the largest value from a set, and return that value as 613 /// well as the updated set. 614 /// 615 /// Time: O(log n) 616 #[must_use] without_max(&self) -> (Option<A>, Self)617 pub fn without_max(&self) -> (Option<A>, Self) { 618 match self.get_max() { 619 Some(v) => (Some(v.clone()), self.without(&v)), 620 None => (None, self.clone()), 621 } 622 } 623 624 /// Construct the union of two sets. 625 /// 626 /// Time: O(n log n) 627 /// 628 /// # Examples 629 /// 630 /// ``` 631 /// # #[macro_use] extern crate im; 632 /// # use im::ordset::OrdSet; 633 /// let set1 = ordset!{1, 2}; 634 /// let set2 = ordset!{2, 3}; 635 /// let expected = ordset!{1, 2, 3}; 636 /// assert_eq!(expected, set1.union(set2)); 637 /// ``` 638 #[must_use] union(mut self, other: Self) -> Self639 pub fn union(mut self, other: Self) -> Self { 640 for value in other { 641 self.insert(value); 642 } 643 self 644 } 645 646 /// Construct the union of multiple sets. 647 /// 648 /// Time: O(n log n) 649 #[must_use] unions<I>(i: I) -> Self where I: IntoIterator<Item = Self>,650 pub fn unions<I>(i: I) -> Self 651 where 652 I: IntoIterator<Item = Self>, 653 { 654 i.into_iter().fold(Self::default(), Self::union) 655 } 656 657 /// Construct the symmetric difference between two sets. 658 /// 659 /// This is an alias for the 660 /// [`symmetric_difference`][symmetric_difference] method. 661 /// 662 /// Time: O(n log n) 663 /// 664 /// # Examples 665 /// 666 /// ``` 667 /// # #[macro_use] extern crate im; 668 /// # use im::ordset::OrdSet; 669 /// let set1 = ordset!{1, 2}; 670 /// let set2 = ordset!{2, 3}; 671 /// let expected = ordset!{1, 3}; 672 /// assert_eq!(expected, set1.difference(set2)); 673 /// ``` 674 /// 675 /// [symmetric_difference]: #method.symmetric_difference 676 #[must_use] difference(self, other: Self) -> Self677 pub fn difference(self, other: Self) -> Self { 678 self.symmetric_difference(other) 679 } 680 681 /// Construct the symmetric difference between two sets. 682 /// 683 /// Time: O(n log n) 684 /// 685 /// # Examples 686 /// 687 /// ``` 688 /// # #[macro_use] extern crate im; 689 /// # use im::ordset::OrdSet; 690 /// let set1 = ordset!{1, 2}; 691 /// let set2 = ordset!{2, 3}; 692 /// let expected = ordset!{1, 3}; 693 /// assert_eq!(expected, set1.symmetric_difference(set2)); 694 /// ``` 695 #[must_use] symmetric_difference(mut self, other: Self) -> Self696 pub fn symmetric_difference(mut self, other: Self) -> Self { 697 for value in other { 698 if self.remove(&value).is_none() { 699 self.insert(value); 700 } 701 } 702 self 703 } 704 705 /// Construct the relative complement between two sets, that is the set 706 /// of values in `self` that do not occur in `other`. 707 /// 708 /// Time: O(m log n) where m is the size of the other set 709 /// 710 /// # Examples 711 /// 712 /// ``` 713 /// # #[macro_use] extern crate im; 714 /// # use im::ordset::OrdSet; 715 /// let set1 = ordset!{1, 2}; 716 /// let set2 = ordset!{2, 3}; 717 /// let expected = ordset!{1}; 718 /// assert_eq!(expected, set1.relative_complement(set2)); 719 /// ``` 720 #[must_use] relative_complement(mut self, other: Self) -> Self721 pub fn relative_complement(mut self, other: Self) -> Self { 722 for value in other { 723 let _ = self.remove(&value); 724 } 725 self 726 } 727 728 /// Construct the intersection of two sets. 729 /// 730 /// Time: O(n log n) 731 /// 732 /// # Examples 733 /// 734 /// ``` 735 /// # #[macro_use] extern crate im; 736 /// # use im::ordset::OrdSet; 737 /// let set1 = ordset!{1, 2}; 738 /// let set2 = ordset!{2, 3}; 739 /// let expected = ordset!{2}; 740 /// assert_eq!(expected, set1.intersection(set2)); 741 /// ``` 742 #[must_use] intersection(self, other: Self) -> Self743 pub fn intersection(self, other: Self) -> Self { 744 let mut out = Self::default(); 745 for value in other { 746 if self.contains(&value) { 747 out.insert(value); 748 } 749 } 750 out 751 } 752 753 /// Split a set into two, with the left hand set containing values 754 /// which are smaller than `split`, and the right hand set 755 /// containing values which are larger than `split`. 756 /// 757 /// The `split` value itself is discarded. 758 /// 759 /// Time: O(n) 760 #[must_use] split<BA>(self, split: &BA) -> (Self, Self) where BA: Ord + ?Sized, A: Borrow<BA>,761 pub fn split<BA>(self, split: &BA) -> (Self, Self) 762 where 763 BA: Ord + ?Sized, 764 A: Borrow<BA>, 765 { 766 let (left, _, right) = self.split_member(split); 767 (left, right) 768 } 769 770 /// Split a set into two, with the left hand set containing values 771 /// which are smaller than `split`, and the right hand set 772 /// containing values which are larger than `split`. 773 /// 774 /// Returns a tuple of the two sets and a boolean which is true if 775 /// the `split` value existed in the original set, and false 776 /// otherwise. 777 /// 778 /// Time: O(n) 779 #[must_use] split_member<BA>(self, split: &BA) -> (Self, bool, Self) where BA: Ord + ?Sized, A: Borrow<BA>,780 pub fn split_member<BA>(self, split: &BA) -> (Self, bool, Self) 781 where 782 BA: Ord + ?Sized, 783 A: Borrow<BA>, 784 { 785 let mut left = Self::default(); 786 let mut right = Self::default(); 787 let mut present = false; 788 for value in self { 789 match value.borrow().cmp(split) { 790 Ordering::Less => { 791 left.insert(value); 792 } 793 Ordering::Equal => { 794 present = true; 795 } 796 Ordering::Greater => { 797 right.insert(value); 798 } 799 } 800 } 801 (left, present, right) 802 } 803 804 /// Construct a set with only the `n` smallest values from a given 805 /// set. 806 /// 807 /// Time: O(n) 808 #[must_use] take(&self, n: usize) -> Self809 pub fn take(&self, n: usize) -> Self { 810 self.iter().take(n).cloned().collect() 811 } 812 813 /// Construct a set with the `n` smallest values removed from a 814 /// given set. 815 /// 816 /// Time: O(n) 817 #[must_use] skip(&self, n: usize) -> Self818 pub fn skip(&self, n: usize) -> Self { 819 self.iter().skip(n).cloned().collect() 820 } 821 } 822 823 // Core traits 824 825 impl<A> Clone for OrdSet<A> { 826 /// Clone a set. 827 /// 828 /// Time: O(1) 829 #[inline] clone(&self) -> Self830 fn clone(&self) -> Self { 831 OrdSet { 832 size: self.size, 833 pool: self.pool.clone(), 834 root: self.root.clone(), 835 } 836 } 837 } 838 839 impl<A: Ord> PartialEq for OrdSet<A> { eq(&self, other: &Self) -> bool840 fn eq(&self, other: &Self) -> bool { 841 PoolRef::ptr_eq(&self.root, &other.root) 842 || (self.len() == other.len() && self.diff(other).next().is_none()) 843 } 844 } 845 846 impl<A: Ord + Eq> Eq for OrdSet<A> {} 847 848 impl<A: Ord> PartialOrd for OrdSet<A> { partial_cmp(&self, other: &Self) -> Option<Ordering>849 fn partial_cmp(&self, other: &Self) -> Option<Ordering> { 850 self.iter().partial_cmp(other.iter()) 851 } 852 } 853 854 impl<A: Ord> Ord for OrdSet<A> { cmp(&self, other: &Self) -> Ordering855 fn cmp(&self, other: &Self) -> Ordering { 856 self.iter().cmp(other.iter()) 857 } 858 } 859 860 impl<A: Ord + Hash> Hash for OrdSet<A> { hash<H>(&self, state: &mut H) where H: Hasher,861 fn hash<H>(&self, state: &mut H) 862 where 863 H: Hasher, 864 { 865 for i in self.iter() { 866 i.hash(state); 867 } 868 } 869 } 870 871 impl<A> Default for OrdSet<A> { default() -> Self872 fn default() -> Self { 873 OrdSet::new() 874 } 875 } 876 877 impl<A: Ord + Clone> Add for OrdSet<A> { 878 type Output = OrdSet<A>; 879 add(self, other: Self) -> Self::Output880 fn add(self, other: Self) -> Self::Output { 881 self.union(other) 882 } 883 } 884 885 impl<'a, A: Ord + Clone> Add for &'a OrdSet<A> { 886 type Output = OrdSet<A>; 887 add(self, other: Self) -> Self::Output888 fn add(self, other: Self) -> Self::Output { 889 self.clone().union(other.clone()) 890 } 891 } 892 893 impl<A: Ord + Clone> Mul for OrdSet<A> { 894 type Output = OrdSet<A>; 895 mul(self, other: Self) -> Self::Output896 fn mul(self, other: Self) -> Self::Output { 897 self.intersection(other) 898 } 899 } 900 901 impl<'a, A: Ord + Clone> Mul for &'a OrdSet<A> { 902 type Output = OrdSet<A>; 903 mul(self, other: Self) -> Self::Output904 fn mul(self, other: Self) -> Self::Output { 905 self.clone().intersection(other.clone()) 906 } 907 } 908 909 impl<A: Ord + Clone> Sum for OrdSet<A> { sum<I>(it: I) -> Self where I: Iterator<Item = Self>,910 fn sum<I>(it: I) -> Self 911 where 912 I: Iterator<Item = Self>, 913 { 914 it.fold(Self::new(), |a, b| a + b) 915 } 916 } 917 918 impl<A, R> Extend<R> for OrdSet<A> 919 where 920 A: Ord + Clone + From<R>, 921 { extend<I>(&mut self, iter: I) where I: IntoIterator<Item = R>,922 fn extend<I>(&mut self, iter: I) 923 where 924 I: IntoIterator<Item = R>, 925 { 926 for value in iter { 927 self.insert(From::from(value)); 928 } 929 } 930 } 931 932 impl<A: Ord + Debug> Debug for OrdSet<A> { fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error>933 fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> { 934 f.debug_set().entries(self.iter()).finish() 935 } 936 } 937 938 // Iterators 939 940 /// An iterator over the elements of a set. 941 pub struct Iter<'a, A> { 942 it: NodeIter<'a, Value<A>>, 943 } 944 945 impl<'a, A> Iterator for Iter<'a, A> 946 where 947 A: 'a + Ord, 948 { 949 type Item = &'a A; 950 951 /// Advance the iterator and return the next value. 952 /// 953 /// Time: O(1)* next(&mut self) -> Option<Self::Item>954 fn next(&mut self) -> Option<Self::Item> { 955 self.it.next().map(Deref::deref) 956 } 957 size_hint(&self) -> (usize, Option<usize>)958 fn size_hint(&self) -> (usize, Option<usize>) { 959 (self.it.remaining, Some(self.it.remaining)) 960 } 961 } 962 963 impl<'a, A> DoubleEndedIterator for Iter<'a, A> 964 where 965 A: 'a + Ord, 966 { next_back(&mut self) -> Option<Self::Item>967 fn next_back(&mut self) -> Option<Self::Item> { 968 self.it.next_back().map(Deref::deref) 969 } 970 } 971 972 impl<'a, A> ExactSizeIterator for Iter<'a, A> where A: 'a + Ord {} 973 974 /// A ranged iterator over the elements of a set. 975 /// 976 /// The only difference from `Iter` is that this one doesn't implement 977 /// `ExactSizeIterator` because we can't know the size of the range without first 978 /// iterating over it to count. 979 pub struct RangedIter<'a, A> { 980 it: NodeIter<'a, Value<A>>, 981 } 982 983 impl<'a, A> Iterator for RangedIter<'a, A> 984 where 985 A: 'a + Ord, 986 { 987 type Item = &'a A; 988 989 /// Advance the iterator and return the next value. 990 /// 991 /// Time: O(1)* next(&mut self) -> Option<Self::Item>992 fn next(&mut self) -> Option<Self::Item> { 993 self.it.next().map(Deref::deref) 994 } 995 size_hint(&self) -> (usize, Option<usize>)996 fn size_hint(&self) -> (usize, Option<usize>) { 997 self.it.size_hint() 998 } 999 } 1000 1001 impl<'a, A> DoubleEndedIterator for RangedIter<'a, A> 1002 where 1003 A: 'a + Ord, 1004 { next_back(&mut self) -> Option<Self::Item>1005 fn next_back(&mut self) -> Option<Self::Item> { 1006 self.it.next_back().map(Deref::deref) 1007 } 1008 } 1009 1010 /// A consuming iterator over the elements of a set. 1011 pub struct ConsumingIter<A> { 1012 it: ConsumingNodeIter<Value<A>>, 1013 } 1014 1015 impl<A> Iterator for ConsumingIter<A> 1016 where 1017 A: Ord + Clone, 1018 { 1019 type Item = A; 1020 1021 /// Advance the iterator and return the next value. 1022 /// 1023 /// Time: O(1)* next(&mut self) -> Option<Self::Item>1024 fn next(&mut self) -> Option<Self::Item> { 1025 self.it.next().map(|v| v.0) 1026 } 1027 } 1028 1029 /// An iterator over the difference between two sets. 1030 pub struct DiffIter<'a, A> { 1031 it: NodeDiffIter<'a, Value<A>>, 1032 } 1033 1034 impl<'a, A> Iterator for DiffIter<'a, A> 1035 where 1036 A: Ord + PartialEq, 1037 { 1038 type Item = DiffItem<'a, A>; 1039 1040 /// Advance the iterator and return the next value. 1041 /// 1042 /// Time: O(1)* next(&mut self) -> Option<Self::Item>1043 fn next(&mut self) -> Option<Self::Item> { 1044 self.it.next().map(|item| match item { 1045 DiffItem::Add(v) => DiffItem::Add(v.deref()), 1046 DiffItem::Update { old, new } => DiffItem::Update { 1047 old: old.deref(), 1048 new: new.deref(), 1049 }, 1050 DiffItem::Remove(v) => DiffItem::Remove(v.deref()), 1051 }) 1052 } 1053 } 1054 1055 impl<A, R> FromIterator<R> for OrdSet<A> 1056 where 1057 A: Ord + Clone + From<R>, 1058 { from_iter<T>(i: T) -> Self where T: IntoIterator<Item = R>,1059 fn from_iter<T>(i: T) -> Self 1060 where 1061 T: IntoIterator<Item = R>, 1062 { 1063 let mut out = Self::new(); 1064 for item in i { 1065 out.insert(From::from(item)); 1066 } 1067 out 1068 } 1069 } 1070 1071 impl<'a, A> IntoIterator for &'a OrdSet<A> 1072 where 1073 A: 'a + Ord, 1074 { 1075 type Item = &'a A; 1076 type IntoIter = Iter<'a, A>; 1077 into_iter(self) -> Self::IntoIter1078 fn into_iter(self) -> Self::IntoIter { 1079 self.iter() 1080 } 1081 } 1082 1083 impl<A> IntoIterator for OrdSet<A> 1084 where 1085 A: Ord + Clone, 1086 { 1087 type Item = A; 1088 type IntoIter = ConsumingIter<A>; 1089 into_iter(self) -> Self::IntoIter1090 fn into_iter(self) -> Self::IntoIter { 1091 ConsumingIter { 1092 it: ConsumingNodeIter::new(&self.root, self.size), 1093 } 1094 } 1095 } 1096 1097 // Conversions 1098 1099 impl<'s, 'a, A, OA> From<&'s OrdSet<&'a A>> for OrdSet<OA> 1100 where 1101 A: ToOwned<Owned = OA> + Ord + ?Sized, 1102 OA: Borrow<A> + Ord + Clone, 1103 { from(set: &OrdSet<&A>) -> Self1104 fn from(set: &OrdSet<&A>) -> Self { 1105 set.iter().map(|a| (*a).to_owned()).collect() 1106 } 1107 } 1108 1109 impl<'a, A> From<&'a [A]> for OrdSet<A> 1110 where 1111 A: Ord + Clone, 1112 { from(slice: &'a [A]) -> Self1113 fn from(slice: &'a [A]) -> Self { 1114 slice.iter().cloned().collect() 1115 } 1116 } 1117 1118 impl<A: Ord + Clone> From<Vec<A>> for OrdSet<A> { from(vec: Vec<A>) -> Self1119 fn from(vec: Vec<A>) -> Self { 1120 vec.into_iter().collect() 1121 } 1122 } 1123 1124 impl<'a, A: Ord + Clone> From<&'a Vec<A>> for OrdSet<A> { from(vec: &Vec<A>) -> Self1125 fn from(vec: &Vec<A>) -> Self { 1126 vec.iter().cloned().collect() 1127 } 1128 } 1129 1130 impl<A: Eq + Hash + Ord + Clone> From<collections::HashSet<A>> for OrdSet<A> { from(hash_set: collections::HashSet<A>) -> Self1131 fn from(hash_set: collections::HashSet<A>) -> Self { 1132 hash_set.into_iter().collect() 1133 } 1134 } 1135 1136 impl<'a, A: Eq + Hash + Ord + Clone> From<&'a collections::HashSet<A>> for OrdSet<A> { from(hash_set: &collections::HashSet<A>) -> Self1137 fn from(hash_set: &collections::HashSet<A>) -> Self { 1138 hash_set.iter().cloned().collect() 1139 } 1140 } 1141 1142 impl<A: Ord + Clone> From<collections::BTreeSet<A>> for OrdSet<A> { from(btree_set: collections::BTreeSet<A>) -> Self1143 fn from(btree_set: collections::BTreeSet<A>) -> Self { 1144 btree_set.into_iter().collect() 1145 } 1146 } 1147 1148 impl<'a, A: Ord + Clone> From<&'a collections::BTreeSet<A>> for OrdSet<A> { from(btree_set: &collections::BTreeSet<A>) -> Self1149 fn from(btree_set: &collections::BTreeSet<A>) -> Self { 1150 btree_set.iter().cloned().collect() 1151 } 1152 } 1153 1154 impl<A: Hash + Eq + Ord + Clone, S: BuildHasher> From<HashSet<A, S>> for OrdSet<A> { from(hashset: HashSet<A, S>) -> Self1155 fn from(hashset: HashSet<A, S>) -> Self { 1156 hashset.into_iter().collect() 1157 } 1158 } 1159 1160 impl<'a, A: Hash + Eq + Ord + Clone, S: BuildHasher> From<&'a HashSet<A, S>> for OrdSet<A> { from(hashset: &HashSet<A, S>) -> Self1161 fn from(hashset: &HashSet<A, S>) -> Self { 1162 hashset.into_iter().cloned().collect() 1163 } 1164 } 1165 1166 // Proptest 1167 #[cfg(any(test, feature = "proptest"))] 1168 #[doc(hidden)] 1169 pub mod proptest { 1170 #[deprecated( 1171 since = "14.3.0", 1172 note = "proptest strategies have moved to im::proptest" 1173 )] 1174 pub use crate::proptest::ord_set; 1175 } 1176 1177 #[cfg(test)] 1178 mod test { 1179 use super::*; 1180 use crate::proptest::*; 1181 use ::proptest::proptest; 1182 1183 #[test] match_strings_with_string_slices()1184 fn match_strings_with_string_slices() { 1185 let mut set: OrdSet<String> = From::from(&ordset!["foo", "bar"]); 1186 set = set.without("bar"); 1187 assert!(!set.contains("bar")); 1188 set.remove("foo"); 1189 assert!(!set.contains("foo")); 1190 } 1191 1192 #[test] ranged_iter()1193 fn ranged_iter() { 1194 let set: OrdSet<i32> = ordset![1, 2, 3, 4, 5]; 1195 let range: Vec<i32> = set.range(..).cloned().collect(); 1196 assert_eq!(vec![1, 2, 3, 4, 5], range); 1197 let range: Vec<i32> = set.range(..).rev().cloned().collect(); 1198 assert_eq!(vec![5, 4, 3, 2, 1], range); 1199 let range: Vec<i32> = set.range(2..5).cloned().collect(); 1200 assert_eq!(vec![2, 3, 4], range); 1201 let range: Vec<i32> = set.range(2..5).rev().cloned().collect(); 1202 assert_eq!(vec![4, 3, 2], range); 1203 let range: Vec<i32> = set.range(3..).cloned().collect(); 1204 assert_eq!(vec![3, 4, 5], range); 1205 let range: Vec<i32> = set.range(3..).rev().cloned().collect(); 1206 assert_eq!(vec![5, 4, 3], range); 1207 let range: Vec<i32> = set.range(..4).cloned().collect(); 1208 assert_eq!(vec![1, 2, 3], range); 1209 let range: Vec<i32> = set.range(..4).rev().cloned().collect(); 1210 assert_eq!(vec![3, 2, 1], range); 1211 let range: Vec<i32> = set.range(..=3).cloned().collect(); 1212 assert_eq!(vec![1, 2, 3], range); 1213 let range: Vec<i32> = set.range(..=3).rev().cloned().collect(); 1214 assert_eq!(vec![3, 2, 1], range); 1215 } 1216 1217 proptest! { 1218 #[test] 1219 fn proptest_a_set(ref s in ord_set(".*", 10..100)) { 1220 assert!(s.len() < 100); 1221 assert!(s.len() >= 10); 1222 } 1223 1224 #[test] 1225 fn long_ranged_iter(max in 1..1000) { 1226 let range = 0..max; 1227 let expected: Vec<i32> = range.clone().collect(); 1228 let set: OrdSet<i32> = OrdSet::from_iter(range.clone()); 1229 let result: Vec<i32> = set.range(..).cloned().collect(); 1230 assert_eq!(expected, result); 1231 1232 let expected: Vec<i32> = range.clone().rev().collect(); 1233 let set: OrdSet<i32> = OrdSet::from_iter(range); 1234 let result: Vec<i32> = set.range(..).rev().cloned().collect(); 1235 assert_eq!(expected, result); 1236 } 1237 } 1238 } 1239