1 | use crate::vec::Vec; |
2 | use core::borrow::Borrow; |
3 | use core::cmp::Ordering::{self, Equal, Greater, Less}; |
4 | use core::cmp::{max, min}; |
5 | use core::fmt::{self, Debug}; |
6 | use core::hash::{Hash, Hasher}; |
7 | use core::iter::{FusedIterator, Peekable}; |
8 | use core::mem::ManuallyDrop; |
9 | use core::ops::{BitAnd, BitOr, BitXor, RangeBounds, Sub}; |
10 | |
11 | use super::map::{BTreeMap, Keys}; |
12 | use super::merge_iter::MergeIterInner; |
13 | use super::set_val::SetValZST; |
14 | use super::Recover; |
15 | |
16 | use crate::alloc::{Allocator, Global}; |
17 | |
18 | /// An ordered set based on a B-Tree. |
19 | /// |
20 | /// See [`BTreeMap`]'s documentation for a detailed discussion of this collection's performance |
21 | /// benefits and drawbacks. |
22 | /// |
23 | /// It is a logic error for an item to be modified in such a way that the item's ordering relative |
24 | /// to any other item, as determined by the [`Ord`] trait, changes while it is in the set. This is |
25 | /// normally only possible through [`Cell`], [`RefCell`], global state, I/O, or unsafe code. |
26 | /// The behavior resulting from such a logic error is not specified, but will be encapsulated to the |
27 | /// `BTreeSet` that observed the logic error and not result in undefined behavior. This could |
28 | /// include panics, incorrect results, aborts, memory leaks, and non-termination. |
29 | /// |
30 | /// Iterators returned by [`BTreeSet::iter`] and [`BTreeSet::into_iter`] produce their items in order, and take worst-case |
31 | /// logarithmic and amortized constant time per item returned. |
32 | /// |
33 | /// [`Cell`]: core::cell::Cell |
34 | /// [`RefCell`]: core::cell::RefCell |
35 | /// |
36 | /// # Examples |
37 | /// |
38 | /// ``` |
39 | /// use std::collections::BTreeSet; |
40 | /// |
41 | /// // Type inference lets us omit an explicit type signature (which |
42 | /// // would be `BTreeSet<&str>` in this example). |
43 | /// let mut books = BTreeSet::new(); |
44 | /// |
45 | /// // Add some books. |
46 | /// books.insert("A Dance With Dragons" ); |
47 | /// books.insert("To Kill a Mockingbird" ); |
48 | /// books.insert("The Odyssey" ); |
49 | /// books.insert("The Great Gatsby" ); |
50 | /// |
51 | /// // Check for a specific one. |
52 | /// if !books.contains("The Winds of Winter" ) { |
53 | /// println!("We have {} books, but The Winds of Winter ain't one." , |
54 | /// books.len()); |
55 | /// } |
56 | /// |
57 | /// // Remove a book. |
58 | /// books.remove("The Odyssey" ); |
59 | /// |
60 | /// // Iterate over everything. |
61 | /// for book in &books { |
62 | /// println!("{book}" ); |
63 | /// } |
64 | /// ``` |
65 | /// |
66 | /// A `BTreeSet` with a known list of items can be initialized from an array: |
67 | /// |
68 | /// ``` |
69 | /// use std::collections::BTreeSet; |
70 | /// |
71 | /// let set = BTreeSet::from([1, 2, 3]); |
72 | /// ``` |
73 | #[stable (feature = "rust1" , since = "1.0.0" )] |
74 | #[cfg_attr (not(test), rustc_diagnostic_item = "BTreeSet" )] |
75 | pub struct BTreeSet< |
76 | T, |
77 | #[unstable (feature = "allocator_api" , issue = "32838" )] A: Allocator + Clone = Global, |
78 | > { |
79 | map: BTreeMap<T, SetValZST, A>, |
80 | } |
81 | |
82 | #[stable (feature = "rust1" , since = "1.0.0" )] |
83 | impl<T: Hash, A: Allocator + Clone> Hash for BTreeSet<T, A> { |
84 | fn hash<H: Hasher>(&self, state: &mut H) { |
85 | self.map.hash(state) |
86 | } |
87 | } |
88 | |
89 | #[stable (feature = "rust1" , since = "1.0.0" )] |
90 | impl<T: PartialEq, A: Allocator + Clone> PartialEq for BTreeSet<T, A> { |
91 | fn eq(&self, other: &BTreeSet<T, A>) -> bool { |
92 | self.map.eq(&other.map) |
93 | } |
94 | } |
95 | |
96 | #[stable (feature = "rust1" , since = "1.0.0" )] |
97 | impl<T: Eq, A: Allocator + Clone> Eq for BTreeSet<T, A> {} |
98 | |
99 | #[stable (feature = "rust1" , since = "1.0.0" )] |
100 | impl<T: PartialOrd, A: Allocator + Clone> PartialOrd for BTreeSet<T, A> { |
101 | fn partial_cmp(&self, other: &BTreeSet<T, A>) -> Option<Ordering> { |
102 | self.map.partial_cmp(&other.map) |
103 | } |
104 | } |
105 | |
106 | #[stable (feature = "rust1" , since = "1.0.0" )] |
107 | impl<T: Ord, A: Allocator + Clone> Ord for BTreeSet<T, A> { |
108 | fn cmp(&self, other: &BTreeSet<T, A>) -> Ordering { |
109 | self.map.cmp(&other.map) |
110 | } |
111 | } |
112 | |
113 | #[stable (feature = "rust1" , since = "1.0.0" )] |
114 | impl<T: Clone, A: Allocator + Clone> Clone for BTreeSet<T, A> { |
115 | fn clone(&self) -> Self { |
116 | BTreeSet { map: self.map.clone() } |
117 | } |
118 | |
119 | fn clone_from(&mut self, source: &Self) { |
120 | self.map.clone_from(&source.map); |
121 | } |
122 | } |
123 | |
124 | /// An iterator over the items of a `BTreeSet`. |
125 | /// |
126 | /// This `struct` is created by the [`iter`] method on [`BTreeSet`]. |
127 | /// See its documentation for more. |
128 | /// |
129 | /// [`iter`]: BTreeSet::iter |
130 | #[must_use = "iterators are lazy and do nothing unless consumed" ] |
131 | #[stable (feature = "rust1" , since = "1.0.0" )] |
132 | pub struct Iter<'a, T: 'a> { |
133 | iter: Keys<'a, T, SetValZST>, |
134 | } |
135 | |
136 | #[stable (feature = "collection_debug" , since = "1.17.0" )] |
137 | impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> { |
138 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
139 | f.debug_tuple(name:"Iter" ).field(&self.iter.clone()).finish() |
140 | } |
141 | } |
142 | |
143 | /// An owning iterator over the items of a `BTreeSet` in ascending order. |
144 | /// |
145 | /// This `struct` is created by the [`into_iter`] method on [`BTreeSet`] |
146 | /// (provided by the [`IntoIterator`] trait). See its documentation for more. |
147 | /// |
148 | /// [`into_iter`]: BTreeSet#method.into_iter |
149 | #[stable (feature = "rust1" , since = "1.0.0" )] |
150 | #[derive (Debug)] |
151 | pub struct IntoIter< |
152 | T, |
153 | #[unstable (feature = "allocator_api" , issue = "32838" )] A: Allocator + Clone = Global, |
154 | > { |
155 | iter: super::map::IntoIter<T, SetValZST, A>, |
156 | } |
157 | |
158 | /// An iterator over a sub-range of items in a `BTreeSet`. |
159 | /// |
160 | /// This `struct` is created by the [`range`] method on [`BTreeSet`]. |
161 | /// See its documentation for more. |
162 | /// |
163 | /// [`range`]: BTreeSet::range |
164 | #[must_use = "iterators are lazy and do nothing unless consumed" ] |
165 | #[derive (Debug)] |
166 | #[stable (feature = "btree_range" , since = "1.17.0" )] |
167 | pub struct Range<'a, T: 'a> { |
168 | iter: super::map::Range<'a, T, SetValZST>, |
169 | } |
170 | |
171 | /// A lazy iterator producing elements in the difference of `BTreeSet`s. |
172 | /// |
173 | /// This `struct` is created by the [`difference`] method on [`BTreeSet`]. |
174 | /// See its documentation for more. |
175 | /// |
176 | /// [`difference`]: BTreeSet::difference |
177 | #[must_use = "this returns the difference as an iterator, \ |
178 | without modifying either input set" ] |
179 | #[stable (feature = "rust1" , since = "1.0.0" )] |
180 | pub struct Difference< |
181 | 'a, |
182 | T: 'a, |
183 | #[unstable (feature = "allocator_api" , issue = "32838" )] A: Allocator + Clone = Global, |
184 | > { |
185 | inner: DifferenceInner<'a, T, A>, |
186 | } |
187 | enum DifferenceInner<'a, T: 'a, A: Allocator + Clone> { |
188 | Stitch { |
189 | // iterate all of `self` and some of `other`, spotting matches along the way |
190 | self_iter: Iter<'a, T>, |
191 | other_iter: Peekable<Iter<'a, T>>, |
192 | }, |
193 | Search { |
194 | // iterate `self`, look up in `other` |
195 | self_iter: Iter<'a, T>, |
196 | other_set: &'a BTreeSet<T, A>, |
197 | }, |
198 | Iterate(Iter<'a, T>), // simply produce all elements in `self` |
199 | } |
200 | |
201 | // Explicit Debug impl necessary because of issue #26925 |
202 | impl<T: Debug, A: Allocator + Clone> Debug for DifferenceInner<'_, T, A> { |
203 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
204 | match self { |
205 | DifferenceInner::Stitch { self_iter: &Iter<'_, T>, other_iter: &Peekable> } => f&mut DebugStruct<'_, '_> |
206 | .debug_struct("Stitch" ) |
207 | .field("self_iter" , self_iter) |
208 | .field(name:"other_iter" , value:other_iter) |
209 | .finish(), |
210 | DifferenceInner::Search { self_iter: &Iter<'_, T>, other_set: &&BTreeSet } => f&mut DebugStruct<'_, '_> |
211 | .debug_struct("Search" ) |
212 | .field("self_iter" , self_iter) |
213 | .field(name:"other_iter" , value:other_set) |
214 | .finish(), |
215 | DifferenceInner::Iterate(x: &Iter<'_, T>) => f.debug_tuple(name:"Iterate" ).field(x).finish(), |
216 | } |
217 | } |
218 | } |
219 | |
220 | #[stable (feature = "collection_debug" , since = "1.17.0" )] |
221 | impl<T: fmt::Debug, A: Allocator + Clone> fmt::Debug for Difference<'_, T, A> { |
222 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
223 | f.debug_tuple(name:"Difference" ).field(&self.inner).finish() |
224 | } |
225 | } |
226 | |
227 | /// A lazy iterator producing elements in the symmetric difference of `BTreeSet`s. |
228 | /// |
229 | /// This `struct` is created by the [`symmetric_difference`] method on |
230 | /// [`BTreeSet`]. See its documentation for more. |
231 | /// |
232 | /// [`symmetric_difference`]: BTreeSet::symmetric_difference |
233 | #[must_use = "this returns the difference as an iterator, \ |
234 | without modifying either input set" ] |
235 | #[stable (feature = "rust1" , since = "1.0.0" )] |
236 | pub struct SymmetricDifference<'a, T: 'a>(MergeIterInner<Iter<'a, T>>); |
237 | |
238 | #[stable (feature = "collection_debug" , since = "1.17.0" )] |
239 | impl<T: fmt::Debug> fmt::Debug for SymmetricDifference<'_, T> { |
240 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
241 | f.debug_tuple(name:"SymmetricDifference" ).field(&self.0).finish() |
242 | } |
243 | } |
244 | |
245 | /// A lazy iterator producing elements in the intersection of `BTreeSet`s. |
246 | /// |
247 | /// This `struct` is created by the [`intersection`] method on [`BTreeSet`]. |
248 | /// See its documentation for more. |
249 | /// |
250 | /// [`intersection`]: BTreeSet::intersection |
251 | #[must_use = "this returns the intersection as an iterator, \ |
252 | without modifying either input set" ] |
253 | #[stable (feature = "rust1" , since = "1.0.0" )] |
254 | pub struct Intersection< |
255 | 'a, |
256 | T: 'a, |
257 | #[unstable (feature = "allocator_api" , issue = "32838" )] A: Allocator + Clone = Global, |
258 | > { |
259 | inner: IntersectionInner<'a, T, A>, |
260 | } |
261 | enum IntersectionInner<'a, T: 'a, A: Allocator + Clone> { |
262 | Stitch { |
263 | // iterate similarly sized sets jointly, spotting matches along the way |
264 | a: Iter<'a, T>, |
265 | b: Iter<'a, T>, |
266 | }, |
267 | Search { |
268 | // iterate a small set, look up in the large set |
269 | small_iter: Iter<'a, T>, |
270 | large_set: &'a BTreeSet<T, A>, |
271 | }, |
272 | Answer(Option<&'a T>), // return a specific element or emptiness |
273 | } |
274 | |
275 | // Explicit Debug impl necessary because of issue #26925 |
276 | impl<T: Debug, A: Allocator + Clone> Debug for IntersectionInner<'_, T, A> { |
277 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
278 | match self { |
279 | IntersectionInner::Stitch { a: &Iter<'_, T>, b: &Iter<'_, T> } => { |
280 | f.debug_struct("Stitch" ).field("a" , a).field(name:"b" , value:b).finish() |
281 | } |
282 | IntersectionInner::Search { small_iter: &Iter<'_, T>, large_set: &&BTreeSet } => f&mut DebugStruct<'_, '_> |
283 | .debug_struct("Search" ) |
284 | .field("small_iter" , small_iter) |
285 | .field(name:"large_set" , value:large_set) |
286 | .finish(), |
287 | IntersectionInner::Answer(x: &Option<&T>) => f.debug_tuple(name:"Answer" ).field(x).finish(), |
288 | } |
289 | } |
290 | } |
291 | |
292 | #[stable (feature = "collection_debug" , since = "1.17.0" )] |
293 | impl<T: Debug, A: Allocator + Clone> Debug for Intersection<'_, T, A> { |
294 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
295 | f.debug_tuple(name:"Intersection" ).field(&self.inner).finish() |
296 | } |
297 | } |
298 | |
299 | /// A lazy iterator producing elements in the union of `BTreeSet`s. |
300 | /// |
301 | /// This `struct` is created by the [`union`] method on [`BTreeSet`]. |
302 | /// See its documentation for more. |
303 | /// |
304 | /// [`union`]: BTreeSet::union |
305 | #[must_use = "this returns the union as an iterator, \ |
306 | without modifying either input set" ] |
307 | #[stable (feature = "rust1" , since = "1.0.0" )] |
308 | pub struct Union<'a, T: 'a>(MergeIterInner<Iter<'a, T>>); |
309 | |
310 | #[stable (feature = "collection_debug" , since = "1.17.0" )] |
311 | impl<T: fmt::Debug> fmt::Debug for Union<'_, T> { |
312 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
313 | f.debug_tuple(name:"Union" ).field(&self.0).finish() |
314 | } |
315 | } |
316 | |
317 | // This constant is used by functions that compare two sets. |
318 | // It estimates the relative size at which searching performs better |
319 | // than iterating, based on the benchmarks in |
320 | // https://github.com/ssomers/rust_bench_btreeset_intersection. |
321 | // It's used to divide rather than multiply sizes, to rule out overflow, |
322 | // and it's a power of two to make that division cheap. |
323 | const ITER_PERFORMANCE_TIPPING_SIZE_DIFF: usize = 16; |
324 | |
325 | impl<T> BTreeSet<T> { |
326 | /// Makes a new, empty `BTreeSet`. |
327 | /// |
328 | /// Does not allocate anything on its own. |
329 | /// |
330 | /// # Examples |
331 | /// |
332 | /// ``` |
333 | /// # #![allow (unused_mut)] |
334 | /// use std::collections::BTreeSet; |
335 | /// |
336 | /// let mut set: BTreeSet<i32> = BTreeSet::new(); |
337 | /// ``` |
338 | #[stable (feature = "rust1" , since = "1.0.0" )] |
339 | #[rustc_const_stable (feature = "const_btree_new" , since = "1.66.0" )] |
340 | #[must_use ] |
341 | pub const fn new() -> BTreeSet<T> { |
342 | BTreeSet { map: BTreeMap::new() } |
343 | } |
344 | } |
345 | |
346 | impl<T, A: Allocator + Clone> BTreeSet<T, A> { |
347 | /// Makes a new `BTreeSet` with a reasonable choice of B. |
348 | /// |
349 | /// # Examples |
350 | /// |
351 | /// ``` |
352 | /// # #![allow (unused_mut)] |
353 | /// # #![feature (allocator_api)] |
354 | /// # #![feature (btreemap_alloc)] |
355 | /// use std::collections::BTreeSet; |
356 | /// use std::alloc::Global; |
357 | /// |
358 | /// let mut set: BTreeSet<i32> = BTreeSet::new_in(Global); |
359 | /// ``` |
360 | #[unstable (feature = "btreemap_alloc" , issue = "32838" )] |
361 | pub const fn new_in(alloc: A) -> BTreeSet<T, A> { |
362 | BTreeSet { map: BTreeMap::new_in(alloc) } |
363 | } |
364 | |
365 | /// Constructs a double-ended iterator over a sub-range of elements in the set. |
366 | /// The simplest way is to use the range syntax `min..max`, thus `range(min..max)` will |
367 | /// yield elements from min (inclusive) to max (exclusive). |
368 | /// The range may also be entered as `(Bound<T>, Bound<T>)`, so for example |
369 | /// `range((Excluded(4), Included(10)))` will yield a left-exclusive, right-inclusive |
370 | /// range from 4 to 10. |
371 | /// |
372 | /// # Panics |
373 | /// |
374 | /// Panics if range `start > end`. |
375 | /// Panics if range `start == end` and both bounds are `Excluded`. |
376 | /// |
377 | /// # Examples |
378 | /// |
379 | /// ``` |
380 | /// use std::collections::BTreeSet; |
381 | /// use std::ops::Bound::Included; |
382 | /// |
383 | /// let mut set = BTreeSet::new(); |
384 | /// set.insert(3); |
385 | /// set.insert(5); |
386 | /// set.insert(8); |
387 | /// for &elem in set.range((Included(&4), Included(&8))) { |
388 | /// println!("{elem}" ); |
389 | /// } |
390 | /// assert_eq!(Some(&5), set.range(4..).next()); |
391 | /// ``` |
392 | #[stable (feature = "btree_range" , since = "1.17.0" )] |
393 | pub fn range<K: ?Sized, R>(&self, range: R) -> Range<'_, T> |
394 | where |
395 | K: Ord, |
396 | T: Borrow<K> + Ord, |
397 | R: RangeBounds<K>, |
398 | { |
399 | Range { iter: self.map.range(range) } |
400 | } |
401 | |
402 | /// Visits the elements representing the difference, |
403 | /// i.e., the elements that are in `self` but not in `other`, |
404 | /// in ascending order. |
405 | /// |
406 | /// # Examples |
407 | /// |
408 | /// ``` |
409 | /// use std::collections::BTreeSet; |
410 | /// |
411 | /// let mut a = BTreeSet::new(); |
412 | /// a.insert(1); |
413 | /// a.insert(2); |
414 | /// |
415 | /// let mut b = BTreeSet::new(); |
416 | /// b.insert(2); |
417 | /// b.insert(3); |
418 | /// |
419 | /// let diff: Vec<_> = a.difference(&b).cloned().collect(); |
420 | /// assert_eq!(diff, [1]); |
421 | /// ``` |
422 | #[stable (feature = "rust1" , since = "1.0.0" )] |
423 | pub fn difference<'a>(&'a self, other: &'a BTreeSet<T, A>) -> Difference<'a, T, A> |
424 | where |
425 | T: Ord, |
426 | { |
427 | let (self_min, self_max) = |
428 | if let (Some(self_min), Some(self_max)) = (self.first(), self.last()) { |
429 | (self_min, self_max) |
430 | } else { |
431 | return Difference { inner: DifferenceInner::Iterate(self.iter()) }; |
432 | }; |
433 | let (other_min, other_max) = |
434 | if let (Some(other_min), Some(other_max)) = (other.first(), other.last()) { |
435 | (other_min, other_max) |
436 | } else { |
437 | return Difference { inner: DifferenceInner::Iterate(self.iter()) }; |
438 | }; |
439 | Difference { |
440 | inner: match (self_min.cmp(other_max), self_max.cmp(other_min)) { |
441 | (Greater, _) | (_, Less) => DifferenceInner::Iterate(self.iter()), |
442 | (Equal, _) => { |
443 | let mut self_iter = self.iter(); |
444 | self_iter.next(); |
445 | DifferenceInner::Iterate(self_iter) |
446 | } |
447 | (_, Equal) => { |
448 | let mut self_iter = self.iter(); |
449 | self_iter.next_back(); |
450 | DifferenceInner::Iterate(self_iter) |
451 | } |
452 | _ if self.len() <= other.len() / ITER_PERFORMANCE_TIPPING_SIZE_DIFF => { |
453 | DifferenceInner::Search { self_iter: self.iter(), other_set: other } |
454 | } |
455 | _ => DifferenceInner::Stitch { |
456 | self_iter: self.iter(), |
457 | other_iter: other.iter().peekable(), |
458 | }, |
459 | }, |
460 | } |
461 | } |
462 | |
463 | /// Visits the elements representing the symmetric difference, |
464 | /// i.e., the elements that are in `self` or in `other` but not in both, |
465 | /// in ascending order. |
466 | /// |
467 | /// # Examples |
468 | /// |
469 | /// ``` |
470 | /// use std::collections::BTreeSet; |
471 | /// |
472 | /// let mut a = BTreeSet::new(); |
473 | /// a.insert(1); |
474 | /// a.insert(2); |
475 | /// |
476 | /// let mut b = BTreeSet::new(); |
477 | /// b.insert(2); |
478 | /// b.insert(3); |
479 | /// |
480 | /// let sym_diff: Vec<_> = a.symmetric_difference(&b).cloned().collect(); |
481 | /// assert_eq!(sym_diff, [1, 3]); |
482 | /// ``` |
483 | #[stable (feature = "rust1" , since = "1.0.0" )] |
484 | pub fn symmetric_difference<'a>( |
485 | &'a self, |
486 | other: &'a BTreeSet<T, A>, |
487 | ) -> SymmetricDifference<'a, T> |
488 | where |
489 | T: Ord, |
490 | { |
491 | SymmetricDifference(MergeIterInner::new(self.iter(), other.iter())) |
492 | } |
493 | |
494 | /// Visits the elements representing the intersection, |
495 | /// i.e., the elements that are both in `self` and `other`, |
496 | /// in ascending order. |
497 | /// |
498 | /// # Examples |
499 | /// |
500 | /// ``` |
501 | /// use std::collections::BTreeSet; |
502 | /// |
503 | /// let mut a = BTreeSet::new(); |
504 | /// a.insert(1); |
505 | /// a.insert(2); |
506 | /// |
507 | /// let mut b = BTreeSet::new(); |
508 | /// b.insert(2); |
509 | /// b.insert(3); |
510 | /// |
511 | /// let intersection: Vec<_> = a.intersection(&b).cloned().collect(); |
512 | /// assert_eq!(intersection, [2]); |
513 | /// ``` |
514 | #[stable (feature = "rust1" , since = "1.0.0" )] |
515 | pub fn intersection<'a>(&'a self, other: &'a BTreeSet<T, A>) -> Intersection<'a, T, A> |
516 | where |
517 | T: Ord, |
518 | { |
519 | let (self_min, self_max) = |
520 | if let (Some(self_min), Some(self_max)) = (self.first(), self.last()) { |
521 | (self_min, self_max) |
522 | } else { |
523 | return Intersection { inner: IntersectionInner::Answer(None) }; |
524 | }; |
525 | let (other_min, other_max) = |
526 | if let (Some(other_min), Some(other_max)) = (other.first(), other.last()) { |
527 | (other_min, other_max) |
528 | } else { |
529 | return Intersection { inner: IntersectionInner::Answer(None) }; |
530 | }; |
531 | Intersection { |
532 | inner: match (self_min.cmp(other_max), self_max.cmp(other_min)) { |
533 | (Greater, _) | (_, Less) => IntersectionInner::Answer(None), |
534 | (Equal, _) => IntersectionInner::Answer(Some(self_min)), |
535 | (_, Equal) => IntersectionInner::Answer(Some(self_max)), |
536 | _ if self.len() <= other.len() / ITER_PERFORMANCE_TIPPING_SIZE_DIFF => { |
537 | IntersectionInner::Search { small_iter: self.iter(), large_set: other } |
538 | } |
539 | _ if other.len() <= self.len() / ITER_PERFORMANCE_TIPPING_SIZE_DIFF => { |
540 | IntersectionInner::Search { small_iter: other.iter(), large_set: self } |
541 | } |
542 | _ => IntersectionInner::Stitch { a: self.iter(), b: other.iter() }, |
543 | }, |
544 | } |
545 | } |
546 | |
547 | /// Visits the elements representing the union, |
548 | /// i.e., all the elements in `self` or `other`, without duplicates, |
549 | /// in ascending order. |
550 | /// |
551 | /// # Examples |
552 | /// |
553 | /// ``` |
554 | /// use std::collections::BTreeSet; |
555 | /// |
556 | /// let mut a = BTreeSet::new(); |
557 | /// a.insert(1); |
558 | /// |
559 | /// let mut b = BTreeSet::new(); |
560 | /// b.insert(2); |
561 | /// |
562 | /// let union: Vec<_> = a.union(&b).cloned().collect(); |
563 | /// assert_eq!(union, [1, 2]); |
564 | /// ``` |
565 | #[stable (feature = "rust1" , since = "1.0.0" )] |
566 | pub fn union<'a>(&'a self, other: &'a BTreeSet<T, A>) -> Union<'a, T> |
567 | where |
568 | T: Ord, |
569 | { |
570 | Union(MergeIterInner::new(self.iter(), other.iter())) |
571 | } |
572 | |
573 | /// Clears the set, removing all elements. |
574 | /// |
575 | /// # Examples |
576 | /// |
577 | /// ``` |
578 | /// use std::collections::BTreeSet; |
579 | /// |
580 | /// let mut v = BTreeSet::new(); |
581 | /// v.insert(1); |
582 | /// v.clear(); |
583 | /// assert!(v.is_empty()); |
584 | /// ``` |
585 | #[stable (feature = "rust1" , since = "1.0.0" )] |
586 | pub fn clear(&mut self) |
587 | where |
588 | A: Clone, |
589 | { |
590 | self.map.clear() |
591 | } |
592 | |
593 | /// Returns `true` if the set contains an element equal to the value. |
594 | /// |
595 | /// The value may be any borrowed form of the set's element type, |
596 | /// but the ordering on the borrowed form *must* match the |
597 | /// ordering on the element type. |
598 | /// |
599 | /// # Examples |
600 | /// |
601 | /// ``` |
602 | /// use std::collections::BTreeSet; |
603 | /// |
604 | /// let set = BTreeSet::from([1, 2, 3]); |
605 | /// assert_eq!(set.contains(&1), true); |
606 | /// assert_eq!(set.contains(&4), false); |
607 | /// ``` |
608 | #[stable (feature = "rust1" , since = "1.0.0" )] |
609 | pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool |
610 | where |
611 | T: Borrow<Q> + Ord, |
612 | Q: Ord, |
613 | { |
614 | self.map.contains_key(value) |
615 | } |
616 | |
617 | /// Returns a reference to the element in the set, if any, that is equal to |
618 | /// the value. |
619 | /// |
620 | /// The value may be any borrowed form of the set's element type, |
621 | /// but the ordering on the borrowed form *must* match the |
622 | /// ordering on the element type. |
623 | /// |
624 | /// # Examples |
625 | /// |
626 | /// ``` |
627 | /// use std::collections::BTreeSet; |
628 | /// |
629 | /// let set = BTreeSet::from([1, 2, 3]); |
630 | /// assert_eq!(set.get(&2), Some(&2)); |
631 | /// assert_eq!(set.get(&4), None); |
632 | /// ``` |
633 | #[stable (feature = "set_recovery" , since = "1.9.0" )] |
634 | pub fn get<Q: ?Sized>(&self, value: &Q) -> Option<&T> |
635 | where |
636 | T: Borrow<Q> + Ord, |
637 | Q: Ord, |
638 | { |
639 | Recover::get(&self.map, value) |
640 | } |
641 | |
642 | /// Returns `true` if `self` has no elements in common with `other`. |
643 | /// This is equivalent to checking for an empty intersection. |
644 | /// |
645 | /// # Examples |
646 | /// |
647 | /// ``` |
648 | /// use std::collections::BTreeSet; |
649 | /// |
650 | /// let a = BTreeSet::from([1, 2, 3]); |
651 | /// let mut b = BTreeSet::new(); |
652 | /// |
653 | /// assert_eq!(a.is_disjoint(&b), true); |
654 | /// b.insert(4); |
655 | /// assert_eq!(a.is_disjoint(&b), true); |
656 | /// b.insert(1); |
657 | /// assert_eq!(a.is_disjoint(&b), false); |
658 | /// ``` |
659 | #[must_use ] |
660 | #[stable (feature = "rust1" , since = "1.0.0" )] |
661 | pub fn is_disjoint(&self, other: &BTreeSet<T, A>) -> bool |
662 | where |
663 | T: Ord, |
664 | { |
665 | self.intersection(other).next().is_none() |
666 | } |
667 | |
668 | /// Returns `true` if the set is a subset of another, |
669 | /// i.e., `other` contains at least all the elements in `self`. |
670 | /// |
671 | /// # Examples |
672 | /// |
673 | /// ``` |
674 | /// use std::collections::BTreeSet; |
675 | /// |
676 | /// let sup = BTreeSet::from([1, 2, 3]); |
677 | /// let mut set = BTreeSet::new(); |
678 | /// |
679 | /// assert_eq!(set.is_subset(&sup), true); |
680 | /// set.insert(2); |
681 | /// assert_eq!(set.is_subset(&sup), true); |
682 | /// set.insert(4); |
683 | /// assert_eq!(set.is_subset(&sup), false); |
684 | /// ``` |
685 | #[must_use ] |
686 | #[stable (feature = "rust1" , since = "1.0.0" )] |
687 | pub fn is_subset(&self, other: &BTreeSet<T, A>) -> bool |
688 | where |
689 | T: Ord, |
690 | { |
691 | // Same result as self.difference(other).next().is_none() |
692 | // but the code below is faster (hugely in some cases). |
693 | if self.len() > other.len() { |
694 | return false; |
695 | } |
696 | let (self_min, self_max) = |
697 | if let (Some(self_min), Some(self_max)) = (self.first(), self.last()) { |
698 | (self_min, self_max) |
699 | } else { |
700 | return true; // self is empty |
701 | }; |
702 | let (other_min, other_max) = |
703 | if let (Some(other_min), Some(other_max)) = (other.first(), other.last()) { |
704 | (other_min, other_max) |
705 | } else { |
706 | return false; // other is empty |
707 | }; |
708 | let mut self_iter = self.iter(); |
709 | match self_min.cmp(other_min) { |
710 | Less => return false, |
711 | Equal => { |
712 | self_iter.next(); |
713 | } |
714 | Greater => (), |
715 | } |
716 | match self_max.cmp(other_max) { |
717 | Greater => return false, |
718 | Equal => { |
719 | self_iter.next_back(); |
720 | } |
721 | Less => (), |
722 | } |
723 | if self_iter.len() <= other.len() / ITER_PERFORMANCE_TIPPING_SIZE_DIFF { |
724 | for next in self_iter { |
725 | if !other.contains(next) { |
726 | return false; |
727 | } |
728 | } |
729 | } else { |
730 | let mut other_iter = other.iter(); |
731 | other_iter.next(); |
732 | other_iter.next_back(); |
733 | let mut self_next = self_iter.next(); |
734 | while let Some(self1) = self_next { |
735 | match other_iter.next().map_or(Less, |other1| self1.cmp(other1)) { |
736 | Less => return false, |
737 | Equal => self_next = self_iter.next(), |
738 | Greater => (), |
739 | } |
740 | } |
741 | } |
742 | true |
743 | } |
744 | |
745 | /// Returns `true` if the set is a superset of another, |
746 | /// i.e., `self` contains at least all the elements in `other`. |
747 | /// |
748 | /// # Examples |
749 | /// |
750 | /// ``` |
751 | /// use std::collections::BTreeSet; |
752 | /// |
753 | /// let sub = BTreeSet::from([1, 2]); |
754 | /// let mut set = BTreeSet::new(); |
755 | /// |
756 | /// assert_eq!(set.is_superset(&sub), false); |
757 | /// |
758 | /// set.insert(0); |
759 | /// set.insert(1); |
760 | /// assert_eq!(set.is_superset(&sub), false); |
761 | /// |
762 | /// set.insert(2); |
763 | /// assert_eq!(set.is_superset(&sub), true); |
764 | /// ``` |
765 | #[must_use ] |
766 | #[stable (feature = "rust1" , since = "1.0.0" )] |
767 | pub fn is_superset(&self, other: &BTreeSet<T, A>) -> bool |
768 | where |
769 | T: Ord, |
770 | { |
771 | other.is_subset(self) |
772 | } |
773 | |
774 | /// Returns a reference to the first element in the set, if any. |
775 | /// This element is always the minimum of all elements in the set. |
776 | /// |
777 | /// # Examples |
778 | /// |
779 | /// Basic usage: |
780 | /// |
781 | /// ``` |
782 | /// use std::collections::BTreeSet; |
783 | /// |
784 | /// let mut set = BTreeSet::new(); |
785 | /// assert_eq!(set.first(), None); |
786 | /// set.insert(1); |
787 | /// assert_eq!(set.first(), Some(&1)); |
788 | /// set.insert(2); |
789 | /// assert_eq!(set.first(), Some(&1)); |
790 | /// ``` |
791 | #[must_use ] |
792 | #[stable (feature = "map_first_last" , since = "1.66.0" )] |
793 | #[rustc_confusables ("front" )] |
794 | pub fn first(&self) -> Option<&T> |
795 | where |
796 | T: Ord, |
797 | { |
798 | self.map.first_key_value().map(|(k, _)| k) |
799 | } |
800 | |
801 | /// Returns a reference to the last element in the set, if any. |
802 | /// This element is always the maximum of all elements in the set. |
803 | /// |
804 | /// # Examples |
805 | /// |
806 | /// Basic usage: |
807 | /// |
808 | /// ``` |
809 | /// use std::collections::BTreeSet; |
810 | /// |
811 | /// let mut set = BTreeSet::new(); |
812 | /// assert_eq!(set.last(), None); |
813 | /// set.insert(1); |
814 | /// assert_eq!(set.last(), Some(&1)); |
815 | /// set.insert(2); |
816 | /// assert_eq!(set.last(), Some(&2)); |
817 | /// ``` |
818 | #[must_use ] |
819 | #[stable (feature = "map_first_last" , since = "1.66.0" )] |
820 | #[rustc_confusables ("back" )] |
821 | pub fn last(&self) -> Option<&T> |
822 | where |
823 | T: Ord, |
824 | { |
825 | self.map.last_key_value().map(|(k, _)| k) |
826 | } |
827 | |
828 | /// Removes the first element from the set and returns it, if any. |
829 | /// The first element is always the minimum element in the set. |
830 | /// |
831 | /// # Examples |
832 | /// |
833 | /// ``` |
834 | /// use std::collections::BTreeSet; |
835 | /// |
836 | /// let mut set = BTreeSet::new(); |
837 | /// |
838 | /// set.insert(1); |
839 | /// while let Some(n) = set.pop_first() { |
840 | /// assert_eq!(n, 1); |
841 | /// } |
842 | /// assert!(set.is_empty()); |
843 | /// ``` |
844 | #[stable (feature = "map_first_last" , since = "1.66.0" )] |
845 | pub fn pop_first(&mut self) -> Option<T> |
846 | where |
847 | T: Ord, |
848 | { |
849 | self.map.pop_first().map(|kv| kv.0) |
850 | } |
851 | |
852 | /// Removes the last element from the set and returns it, if any. |
853 | /// The last element is always the maximum element in the set. |
854 | /// |
855 | /// # Examples |
856 | /// |
857 | /// ``` |
858 | /// use std::collections::BTreeSet; |
859 | /// |
860 | /// let mut set = BTreeSet::new(); |
861 | /// |
862 | /// set.insert(1); |
863 | /// while let Some(n) = set.pop_last() { |
864 | /// assert_eq!(n, 1); |
865 | /// } |
866 | /// assert!(set.is_empty()); |
867 | /// ``` |
868 | #[stable (feature = "map_first_last" , since = "1.66.0" )] |
869 | pub fn pop_last(&mut self) -> Option<T> |
870 | where |
871 | T: Ord, |
872 | { |
873 | self.map.pop_last().map(|kv| kv.0) |
874 | } |
875 | |
876 | /// Adds a value to the set. |
877 | /// |
878 | /// Returns whether the value was newly inserted. That is: |
879 | /// |
880 | /// - If the set did not previously contain an equal value, `true` is |
881 | /// returned. |
882 | /// - If the set already contained an equal value, `false` is returned, and |
883 | /// the entry is not updated. |
884 | /// |
885 | /// See the [module-level documentation] for more. |
886 | /// |
887 | /// [module-level documentation]: index.html#insert-and-complex-keys |
888 | /// |
889 | /// # Examples |
890 | /// |
891 | /// ``` |
892 | /// use std::collections::BTreeSet; |
893 | /// |
894 | /// let mut set = BTreeSet::new(); |
895 | /// |
896 | /// assert_eq!(set.insert(2), true); |
897 | /// assert_eq!(set.insert(2), false); |
898 | /// assert_eq!(set.len(), 1); |
899 | /// ``` |
900 | #[stable (feature = "rust1" , since = "1.0.0" )] |
901 | #[rustc_confusables ("push" , "put" )] |
902 | pub fn insert(&mut self, value: T) -> bool |
903 | where |
904 | T: Ord, |
905 | { |
906 | self.map.insert(value, SetValZST::default()).is_none() |
907 | } |
908 | |
909 | /// Adds a value to the set, replacing the existing element, if any, that is |
910 | /// equal to the value. Returns the replaced element. |
911 | /// |
912 | /// # Examples |
913 | /// |
914 | /// ``` |
915 | /// use std::collections::BTreeSet; |
916 | /// |
917 | /// let mut set = BTreeSet::new(); |
918 | /// set.insert(Vec::<i32>::new()); |
919 | /// |
920 | /// assert_eq!(set.get(&[][..]).unwrap().capacity(), 0); |
921 | /// set.replace(Vec::with_capacity(10)); |
922 | /// assert_eq!(set.get(&[][..]).unwrap().capacity(), 10); |
923 | /// ``` |
924 | #[stable (feature = "set_recovery" , since = "1.9.0" )] |
925 | #[rustc_confusables ("swap" )] |
926 | pub fn replace(&mut self, value: T) -> Option<T> |
927 | where |
928 | T: Ord, |
929 | { |
930 | Recover::replace(&mut self.map, value) |
931 | } |
932 | |
933 | /// If the set contains an element equal to the value, removes it from the |
934 | /// set and drops it. Returns whether such an element was present. |
935 | /// |
936 | /// The value may be any borrowed form of the set's element type, |
937 | /// but the ordering on the borrowed form *must* match the |
938 | /// ordering on the element type. |
939 | /// |
940 | /// # Examples |
941 | /// |
942 | /// ``` |
943 | /// use std::collections::BTreeSet; |
944 | /// |
945 | /// let mut set = BTreeSet::new(); |
946 | /// |
947 | /// set.insert(2); |
948 | /// assert_eq!(set.remove(&2), true); |
949 | /// assert_eq!(set.remove(&2), false); |
950 | /// ``` |
951 | #[stable (feature = "rust1" , since = "1.0.0" )] |
952 | pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool |
953 | where |
954 | T: Borrow<Q> + Ord, |
955 | Q: Ord, |
956 | { |
957 | self.map.remove(value).is_some() |
958 | } |
959 | |
960 | /// Removes and returns the element in the set, if any, that is equal to |
961 | /// the value. |
962 | /// |
963 | /// The value may be any borrowed form of the set's element type, |
964 | /// but the ordering on the borrowed form *must* match the |
965 | /// ordering on the element type. |
966 | /// |
967 | /// # Examples |
968 | /// |
969 | /// ``` |
970 | /// use std::collections::BTreeSet; |
971 | /// |
972 | /// let mut set = BTreeSet::from([1, 2, 3]); |
973 | /// assert_eq!(set.take(&2), Some(2)); |
974 | /// assert_eq!(set.take(&2), None); |
975 | /// ``` |
976 | #[stable (feature = "set_recovery" , since = "1.9.0" )] |
977 | pub fn take<Q: ?Sized>(&mut self, value: &Q) -> Option<T> |
978 | where |
979 | T: Borrow<Q> + Ord, |
980 | Q: Ord, |
981 | { |
982 | Recover::take(&mut self.map, value) |
983 | } |
984 | |
985 | /// Retains only the elements specified by the predicate. |
986 | /// |
987 | /// In other words, remove all elements `e` for which `f(&e)` returns `false`. |
988 | /// The elements are visited in ascending order. |
989 | /// |
990 | /// # Examples |
991 | /// |
992 | /// ``` |
993 | /// use std::collections::BTreeSet; |
994 | /// |
995 | /// let mut set = BTreeSet::from([1, 2, 3, 4, 5, 6]); |
996 | /// // Keep only the even numbers. |
997 | /// set.retain(|&k| k % 2 == 0); |
998 | /// assert!(set.iter().eq([2, 4, 6].iter())); |
999 | /// ``` |
1000 | #[stable (feature = "btree_retain" , since = "1.53.0" )] |
1001 | pub fn retain<F>(&mut self, mut f: F) |
1002 | where |
1003 | T: Ord, |
1004 | F: FnMut(&T) -> bool, |
1005 | { |
1006 | self.extract_if(|v| !f(v)).for_each(drop); |
1007 | } |
1008 | |
1009 | /// Moves all elements from `other` into `self`, leaving `other` empty. |
1010 | /// |
1011 | /// # Examples |
1012 | /// |
1013 | /// ``` |
1014 | /// use std::collections::BTreeSet; |
1015 | /// |
1016 | /// let mut a = BTreeSet::new(); |
1017 | /// a.insert(1); |
1018 | /// a.insert(2); |
1019 | /// a.insert(3); |
1020 | /// |
1021 | /// let mut b = BTreeSet::new(); |
1022 | /// b.insert(3); |
1023 | /// b.insert(4); |
1024 | /// b.insert(5); |
1025 | /// |
1026 | /// a.append(&mut b); |
1027 | /// |
1028 | /// assert_eq!(a.len(), 5); |
1029 | /// assert_eq!(b.len(), 0); |
1030 | /// |
1031 | /// assert!(a.contains(&1)); |
1032 | /// assert!(a.contains(&2)); |
1033 | /// assert!(a.contains(&3)); |
1034 | /// assert!(a.contains(&4)); |
1035 | /// assert!(a.contains(&5)); |
1036 | /// ``` |
1037 | #[stable (feature = "btree_append" , since = "1.11.0" )] |
1038 | pub fn append(&mut self, other: &mut Self) |
1039 | where |
1040 | T: Ord, |
1041 | A: Clone, |
1042 | { |
1043 | self.map.append(&mut other.map); |
1044 | } |
1045 | |
1046 | /// Splits the collection into two at the value. Returns a new collection |
1047 | /// with all elements greater than or equal to the value. |
1048 | /// |
1049 | /// # Examples |
1050 | /// |
1051 | /// Basic usage: |
1052 | /// |
1053 | /// ``` |
1054 | /// use std::collections::BTreeSet; |
1055 | /// |
1056 | /// let mut a = BTreeSet::new(); |
1057 | /// a.insert(1); |
1058 | /// a.insert(2); |
1059 | /// a.insert(3); |
1060 | /// a.insert(17); |
1061 | /// a.insert(41); |
1062 | /// |
1063 | /// let b = a.split_off(&3); |
1064 | /// |
1065 | /// assert_eq!(a.len(), 2); |
1066 | /// assert_eq!(b.len(), 3); |
1067 | /// |
1068 | /// assert!(a.contains(&1)); |
1069 | /// assert!(a.contains(&2)); |
1070 | /// |
1071 | /// assert!(b.contains(&3)); |
1072 | /// assert!(b.contains(&17)); |
1073 | /// assert!(b.contains(&41)); |
1074 | /// ``` |
1075 | #[stable (feature = "btree_split_off" , since = "1.11.0" )] |
1076 | pub fn split_off<Q: ?Sized + Ord>(&mut self, value: &Q) -> Self |
1077 | where |
1078 | T: Borrow<Q> + Ord, |
1079 | A: Clone, |
1080 | { |
1081 | BTreeSet { map: self.map.split_off(value) } |
1082 | } |
1083 | |
1084 | /// Creates an iterator that visits all elements in ascending order and |
1085 | /// uses a closure to determine if an element should be removed. |
1086 | /// |
1087 | /// If the closure returns `true`, the element is removed from the set and |
1088 | /// yielded. If the closure returns `false`, or panics, the element remains |
1089 | /// in the set and will not be yielded. |
1090 | /// |
1091 | /// If the returned `ExtractIf` is not exhausted, e.g. because it is dropped without iterating |
1092 | /// or the iteration short-circuits, then the remaining elements will be retained. |
1093 | /// Use [`retain`] with a negated predicate if you do not need the returned iterator. |
1094 | /// |
1095 | /// [`retain`]: BTreeSet::retain |
1096 | /// # Examples |
1097 | /// |
1098 | /// Splitting a set into even and odd values, reusing the original set: |
1099 | /// |
1100 | /// ``` |
1101 | /// #![feature(btree_extract_if)] |
1102 | /// use std::collections::BTreeSet; |
1103 | /// |
1104 | /// let mut set: BTreeSet<i32> = (0..8).collect(); |
1105 | /// let evens: BTreeSet<_> = set.extract_if(|v| v % 2 == 0).collect(); |
1106 | /// let odds = set; |
1107 | /// assert_eq!(evens.into_iter().collect::<Vec<_>>(), vec![0, 2, 4, 6]); |
1108 | /// assert_eq!(odds.into_iter().collect::<Vec<_>>(), vec![1, 3, 5, 7]); |
1109 | /// ``` |
1110 | #[unstable (feature = "btree_extract_if" , issue = "70530" )] |
1111 | pub fn extract_if<'a, F>(&'a mut self, pred: F) -> ExtractIf<'a, T, F, A> |
1112 | where |
1113 | T: Ord, |
1114 | F: 'a + FnMut(&T) -> bool, |
1115 | { |
1116 | let (inner, alloc) = self.map.extract_if_inner(); |
1117 | ExtractIf { pred, inner, alloc } |
1118 | } |
1119 | |
1120 | /// Gets an iterator that visits the elements in the `BTreeSet` in ascending |
1121 | /// order. |
1122 | /// |
1123 | /// # Examples |
1124 | /// |
1125 | /// ``` |
1126 | /// use std::collections::BTreeSet; |
1127 | /// |
1128 | /// let set = BTreeSet::from([3, 1, 2]); |
1129 | /// let mut set_iter = set.iter(); |
1130 | /// assert_eq!(set_iter.next(), Some(&1)); |
1131 | /// assert_eq!(set_iter.next(), Some(&2)); |
1132 | /// assert_eq!(set_iter.next(), Some(&3)); |
1133 | /// assert_eq!(set_iter.next(), None); |
1134 | /// ``` |
1135 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1136 | pub fn iter(&self) -> Iter<'_, T> { |
1137 | Iter { iter: self.map.keys() } |
1138 | } |
1139 | |
1140 | /// Returns the number of elements in the set. |
1141 | /// |
1142 | /// # Examples |
1143 | /// |
1144 | /// ``` |
1145 | /// use std::collections::BTreeSet; |
1146 | /// |
1147 | /// let mut v = BTreeSet::new(); |
1148 | /// assert_eq!(v.len(), 0); |
1149 | /// v.insert(1); |
1150 | /// assert_eq!(v.len(), 1); |
1151 | /// ``` |
1152 | #[must_use ] |
1153 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1154 | #[rustc_const_unstable ( |
1155 | feature = "const_btree_len" , |
1156 | issue = "71835" , |
1157 | implied_by = "const_btree_new" |
1158 | )] |
1159 | #[rustc_confusables ("length" , "size" )] |
1160 | pub const fn len(&self) -> usize { |
1161 | self.map.len() |
1162 | } |
1163 | |
1164 | /// Returns `true` if the set contains no elements. |
1165 | /// |
1166 | /// # Examples |
1167 | /// |
1168 | /// ``` |
1169 | /// use std::collections::BTreeSet; |
1170 | /// |
1171 | /// let mut v = BTreeSet::new(); |
1172 | /// assert!(v.is_empty()); |
1173 | /// v.insert(1); |
1174 | /// assert!(!v.is_empty()); |
1175 | /// ``` |
1176 | #[must_use ] |
1177 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1178 | #[rustc_const_unstable ( |
1179 | feature = "const_btree_len" , |
1180 | issue = "71835" , |
1181 | implied_by = "const_btree_new" |
1182 | )] |
1183 | pub const fn is_empty(&self) -> bool { |
1184 | self.len() == 0 |
1185 | } |
1186 | } |
1187 | |
1188 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1189 | impl<T: Ord> FromIterator<T> for BTreeSet<T> { |
1190 | fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> BTreeSet<T> { |
1191 | let mut inputs: Vec<_> = iter.into_iter().collect(); |
1192 | |
1193 | if inputs.is_empty() { |
1194 | return BTreeSet::new(); |
1195 | } |
1196 | |
1197 | // use stable sort to preserve the insertion order. |
1198 | inputs.sort(); |
1199 | BTreeSet::from_sorted_iter(inputs.into_iter(), alloc:Global) |
1200 | } |
1201 | } |
1202 | |
1203 | impl<T: Ord, A: Allocator + Clone> BTreeSet<T, A> { |
1204 | fn from_sorted_iter<I: Iterator<Item = T>>(iter: I, alloc: A) -> BTreeSet<T, A> { |
1205 | let iter: impl Iterator = iter.map(|k: T| (k, SetValZST::default())); |
1206 | let map: BTreeMap = BTreeMap::bulk_build_from_sorted_iter(iter, alloc); |
1207 | BTreeSet { map } |
1208 | } |
1209 | } |
1210 | |
1211 | #[stable (feature = "std_collections_from_array" , since = "1.56.0" )] |
1212 | impl<T: Ord, const N: usize> From<[T; N]> for BTreeSet<T> { |
1213 | /// Converts a `[T; N]` into a `BTreeSet<T>`. |
1214 | /// |
1215 | /// ``` |
1216 | /// use std::collections::BTreeSet; |
1217 | /// |
1218 | /// let set1 = BTreeSet::from([1, 2, 3, 4]); |
1219 | /// let set2: BTreeSet<_> = [1, 2, 3, 4].into(); |
1220 | /// assert_eq!(set1, set2); |
1221 | /// ``` |
1222 | fn from(mut arr: [T; N]) -> Self { |
1223 | if N == 0 { |
1224 | return BTreeSet::new(); |
1225 | } |
1226 | |
1227 | // use stable sort to preserve the insertion order. |
1228 | arr.sort(); |
1229 | let iter: impl Iterator = IntoIterator::into_iter(self:arr).map(|k: T| (k, SetValZST::default())); |
1230 | let map: BTreeMap = BTreeMap::bulk_build_from_sorted_iter(iter, alloc:Global); |
1231 | BTreeSet { map } |
1232 | } |
1233 | } |
1234 | |
1235 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1236 | impl<T, A: Allocator + Clone> IntoIterator for BTreeSet<T, A> { |
1237 | type Item = T; |
1238 | type IntoIter = IntoIter<T, A>; |
1239 | |
1240 | /// Gets an iterator for moving out the `BTreeSet`'s contents in ascending order. |
1241 | /// |
1242 | /// # Examples |
1243 | /// |
1244 | /// ``` |
1245 | /// use std::collections::BTreeSet; |
1246 | /// |
1247 | /// let set = BTreeSet::from([1, 2, 3, 4]); |
1248 | /// |
1249 | /// let v: Vec<_> = set.into_iter().collect(); |
1250 | /// assert_eq!(v, [1, 2, 3, 4]); |
1251 | /// ``` |
1252 | fn into_iter(self) -> IntoIter<T, A> { |
1253 | IntoIter { iter: self.map.into_iter() } |
1254 | } |
1255 | } |
1256 | |
1257 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1258 | impl<'a, T, A: Allocator + Clone> IntoIterator for &'a BTreeSet<T, A> { |
1259 | type Item = &'a T; |
1260 | type IntoIter = Iter<'a, T>; |
1261 | |
1262 | fn into_iter(self) -> Iter<'a, T> { |
1263 | self.iter() |
1264 | } |
1265 | } |
1266 | |
1267 | /// An iterator produced by calling `extract_if` on BTreeSet. |
1268 | #[unstable (feature = "btree_extract_if" , issue = "70530" )] |
1269 | #[must_use = "iterators are lazy and do nothing unless consumed" ] |
1270 | pub struct ExtractIf< |
1271 | 'a, |
1272 | T, |
1273 | F, |
1274 | #[unstable (feature = "allocator_api" , issue = "32838" )] A: Allocator + Clone = Global, |
1275 | > where |
1276 | T: 'a, |
1277 | F: 'a + FnMut(&T) -> bool, |
1278 | { |
1279 | pred: F, |
1280 | inner: super::map::ExtractIfInner<'a, T, SetValZST>, |
1281 | /// The BTreeMap will outlive this IntoIter so we don't care about drop order for `alloc`. |
1282 | alloc: A, |
1283 | } |
1284 | |
1285 | #[unstable (feature = "btree_extract_if" , issue = "70530" )] |
1286 | impl<T, F, A: Allocator + Clone> fmt::Debug for ExtractIf<'_, T, F, A> |
1287 | where |
1288 | T: fmt::Debug, |
1289 | F: FnMut(&T) -> bool, |
1290 | { |
1291 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
1292 | f.debug_tuple(name:"ExtractIf" ).field(&self.inner.peek().map(|(k: &T, _)| k)).finish() |
1293 | } |
1294 | } |
1295 | |
1296 | #[unstable (feature = "btree_extract_if" , issue = "70530" )] |
1297 | impl<'a, T, F, A: Allocator + Clone> Iterator for ExtractIf<'_, T, F, A> |
1298 | where |
1299 | F: 'a + FnMut(&T) -> bool, |
1300 | { |
1301 | type Item = T; |
1302 | |
1303 | fn next(&mut self) -> Option<T> { |
1304 | let pred: &mut F = &mut self.pred; |
1305 | let mut mapped_pred: impl FnMut(&T, &mut SetValZST) -> … = |k: &T, _v: &mut SetValZST| pred(k); |
1306 | self.inner.next(&mut mapped_pred, self.alloc.clone()).map(|(k: T, _)| k) |
1307 | } |
1308 | |
1309 | fn size_hint(&self) -> (usize, Option<usize>) { |
1310 | self.inner.size_hint() |
1311 | } |
1312 | } |
1313 | |
1314 | #[unstable (feature = "btree_extract_if" , issue = "70530" )] |
1315 | impl<T, F, A: Allocator + Clone> FusedIterator for ExtractIf<'_, T, F, A> where F: FnMut(&T) -> bool {} |
1316 | |
1317 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1318 | impl<T: Ord, A: Allocator + Clone> Extend<T> for BTreeSet<T, A> { |
1319 | #[inline ] |
1320 | fn extend<Iter: IntoIterator<Item = T>>(&mut self, iter: Iter) { |
1321 | iter.into_iter().for_each(move |elem: T| { |
1322 | self.insert(elem); |
1323 | }); |
1324 | } |
1325 | |
1326 | #[inline ] |
1327 | fn extend_one(&mut self, elem: T) { |
1328 | self.insert(elem); |
1329 | } |
1330 | } |
1331 | |
1332 | #[stable (feature = "extend_ref" , since = "1.2.0" )] |
1333 | impl<'a, T: 'a + Ord + Copy, A: Allocator + Clone> Extend<&'a T> for BTreeSet<T, A> { |
1334 | fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) { |
1335 | self.extend(iter:iter.into_iter().cloned()); |
1336 | } |
1337 | |
1338 | #[inline ] |
1339 | fn extend_one(&mut self, &elem: T: &'a T) { |
1340 | self.insert(elem); |
1341 | } |
1342 | } |
1343 | |
1344 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1345 | impl<T> Default for BTreeSet<T> { |
1346 | /// Creates an empty `BTreeSet`. |
1347 | fn default() -> BTreeSet<T> { |
1348 | BTreeSet::new() |
1349 | } |
1350 | } |
1351 | |
1352 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1353 | impl<T: Ord + Clone, A: Allocator + Clone> Sub<&BTreeSet<T, A>> for &BTreeSet<T, A> { |
1354 | type Output = BTreeSet<T, A>; |
1355 | |
1356 | /// Returns the difference of `self` and `rhs` as a new `BTreeSet<T>`. |
1357 | /// |
1358 | /// # Examples |
1359 | /// |
1360 | /// ``` |
1361 | /// use std::collections::BTreeSet; |
1362 | /// |
1363 | /// let a = BTreeSet::from([1, 2, 3]); |
1364 | /// let b = BTreeSet::from([3, 4, 5]); |
1365 | /// |
1366 | /// let result = &a - &b; |
1367 | /// assert_eq!(result, BTreeSet::from([1, 2])); |
1368 | /// ``` |
1369 | fn sub(self, rhs: &BTreeSet<T, A>) -> BTreeSet<T, A> { |
1370 | BTreeSet::from_sorted_iter( |
1371 | self.difference(rhs).cloned(), |
1372 | alloc:ManuallyDrop::into_inner(self.map.alloc.clone()), |
1373 | ) |
1374 | } |
1375 | } |
1376 | |
1377 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1378 | impl<T: Ord + Clone, A: Allocator + Clone> BitXor<&BTreeSet<T, A>> for &BTreeSet<T, A> { |
1379 | type Output = BTreeSet<T, A>; |
1380 | |
1381 | /// Returns the symmetric difference of `self` and `rhs` as a new `BTreeSet<T>`. |
1382 | /// |
1383 | /// # Examples |
1384 | /// |
1385 | /// ``` |
1386 | /// use std::collections::BTreeSet; |
1387 | /// |
1388 | /// let a = BTreeSet::from([1, 2, 3]); |
1389 | /// let b = BTreeSet::from([2, 3, 4]); |
1390 | /// |
1391 | /// let result = &a ^ &b; |
1392 | /// assert_eq!(result, BTreeSet::from([1, 4])); |
1393 | /// ``` |
1394 | fn bitxor(self, rhs: &BTreeSet<T, A>) -> BTreeSet<T, A> { |
1395 | BTreeSet::from_sorted_iter( |
1396 | self.symmetric_difference(rhs).cloned(), |
1397 | alloc:ManuallyDrop::into_inner(self.map.alloc.clone()), |
1398 | ) |
1399 | } |
1400 | } |
1401 | |
1402 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1403 | impl<T: Ord + Clone, A: Allocator + Clone> BitAnd<&BTreeSet<T, A>> for &BTreeSet<T, A> { |
1404 | type Output = BTreeSet<T, A>; |
1405 | |
1406 | /// Returns the intersection of `self` and `rhs` as a new `BTreeSet<T>`. |
1407 | /// |
1408 | /// # Examples |
1409 | /// |
1410 | /// ``` |
1411 | /// use std::collections::BTreeSet; |
1412 | /// |
1413 | /// let a = BTreeSet::from([1, 2, 3]); |
1414 | /// let b = BTreeSet::from([2, 3, 4]); |
1415 | /// |
1416 | /// let result = &a & &b; |
1417 | /// assert_eq!(result, BTreeSet::from([2, 3])); |
1418 | /// ``` |
1419 | fn bitand(self, rhs: &BTreeSet<T, A>) -> BTreeSet<T, A> { |
1420 | BTreeSet::from_sorted_iter( |
1421 | self.intersection(rhs).cloned(), |
1422 | alloc:ManuallyDrop::into_inner(self.map.alloc.clone()), |
1423 | ) |
1424 | } |
1425 | } |
1426 | |
1427 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1428 | impl<T: Ord + Clone, A: Allocator + Clone> BitOr<&BTreeSet<T, A>> for &BTreeSet<T, A> { |
1429 | type Output = BTreeSet<T, A>; |
1430 | |
1431 | /// Returns the union of `self` and `rhs` as a new `BTreeSet<T>`. |
1432 | /// |
1433 | /// # Examples |
1434 | /// |
1435 | /// ``` |
1436 | /// use std::collections::BTreeSet; |
1437 | /// |
1438 | /// let a = BTreeSet::from([1, 2, 3]); |
1439 | /// let b = BTreeSet::from([3, 4, 5]); |
1440 | /// |
1441 | /// let result = &a | &b; |
1442 | /// assert_eq!(result, BTreeSet::from([1, 2, 3, 4, 5])); |
1443 | /// ``` |
1444 | fn bitor(self, rhs: &BTreeSet<T, A>) -> BTreeSet<T, A> { |
1445 | BTreeSet::from_sorted_iter( |
1446 | self.union(rhs).cloned(), |
1447 | alloc:ManuallyDrop::into_inner(self.map.alloc.clone()), |
1448 | ) |
1449 | } |
1450 | } |
1451 | |
1452 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1453 | impl<T: Debug, A: Allocator + Clone> Debug for BTreeSet<T, A> { |
1454 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
1455 | f.debug_set().entries(self.iter()).finish() |
1456 | } |
1457 | } |
1458 | |
1459 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1460 | impl<T> Clone for Iter<'_, T> { |
1461 | fn clone(&self) -> Self { |
1462 | Iter { iter: self.iter.clone() } |
1463 | } |
1464 | } |
1465 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1466 | impl<'a, T> Iterator for Iter<'a, T> { |
1467 | type Item = &'a T; |
1468 | |
1469 | fn next(&mut self) -> Option<&'a T> { |
1470 | self.iter.next() |
1471 | } |
1472 | |
1473 | fn size_hint(&self) -> (usize, Option<usize>) { |
1474 | self.iter.size_hint() |
1475 | } |
1476 | |
1477 | fn last(mut self) -> Option<&'a T> { |
1478 | self.next_back() |
1479 | } |
1480 | |
1481 | fn min(mut self) -> Option<&'a T> |
1482 | where |
1483 | &'a T: Ord, |
1484 | { |
1485 | self.next() |
1486 | } |
1487 | |
1488 | fn max(mut self) -> Option<&'a T> |
1489 | where |
1490 | &'a T: Ord, |
1491 | { |
1492 | self.next_back() |
1493 | } |
1494 | } |
1495 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1496 | impl<'a, T> DoubleEndedIterator for Iter<'a, T> { |
1497 | fn next_back(&mut self) -> Option<&'a T> { |
1498 | self.iter.next_back() |
1499 | } |
1500 | } |
1501 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1502 | impl<T> ExactSizeIterator for Iter<'_, T> { |
1503 | fn len(&self) -> usize { |
1504 | self.iter.len() |
1505 | } |
1506 | } |
1507 | |
1508 | #[stable (feature = "fused" , since = "1.26.0" )] |
1509 | impl<T> FusedIterator for Iter<'_, T> {} |
1510 | |
1511 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1512 | impl<T, A: Allocator + Clone> Iterator for IntoIter<T, A> { |
1513 | type Item = T; |
1514 | |
1515 | fn next(&mut self) -> Option<T> { |
1516 | self.iter.next().map(|(k: T, _)| k) |
1517 | } |
1518 | |
1519 | fn size_hint(&self) -> (usize, Option<usize>) { |
1520 | self.iter.size_hint() |
1521 | } |
1522 | } |
1523 | |
1524 | #[stable (feature = "default_iters" , since = "1.70.0" )] |
1525 | impl<T> Default for Iter<'_, T> { |
1526 | /// Creates an empty `btree_set::Iter`. |
1527 | /// |
1528 | /// ``` |
1529 | /// # use std::collections::btree_set; |
1530 | /// let iter: btree_set::Iter<'_, u8> = Default::default(); |
1531 | /// assert_eq!(iter.len(), 0); |
1532 | /// ``` |
1533 | fn default() -> Self { |
1534 | Iter { iter: Default::default() } |
1535 | } |
1536 | } |
1537 | |
1538 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1539 | impl<T, A: Allocator + Clone> DoubleEndedIterator for IntoIter<T, A> { |
1540 | fn next_back(&mut self) -> Option<T> { |
1541 | self.iter.next_back().map(|(k: T, _)| k) |
1542 | } |
1543 | } |
1544 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1545 | impl<T, A: Allocator + Clone> ExactSizeIterator for IntoIter<T, A> { |
1546 | fn len(&self) -> usize { |
1547 | self.iter.len() |
1548 | } |
1549 | } |
1550 | |
1551 | #[stable (feature = "fused" , since = "1.26.0" )] |
1552 | impl<T, A: Allocator + Clone> FusedIterator for IntoIter<T, A> {} |
1553 | |
1554 | #[stable (feature = "default_iters" , since = "1.70.0" )] |
1555 | impl<T, A> Default for IntoIter<T, A> |
1556 | where |
1557 | A: Allocator + Default + Clone, |
1558 | { |
1559 | /// Creates an empty `btree_set::IntoIter`. |
1560 | /// |
1561 | /// ``` |
1562 | /// # use std::collections::btree_set; |
1563 | /// let iter: btree_set::IntoIter<u8> = Default::default(); |
1564 | /// assert_eq!(iter.len(), 0); |
1565 | /// ``` |
1566 | fn default() -> Self { |
1567 | IntoIter { iter: Default::default() } |
1568 | } |
1569 | } |
1570 | |
1571 | #[stable (feature = "btree_range" , since = "1.17.0" )] |
1572 | impl<T> Clone for Range<'_, T> { |
1573 | fn clone(&self) -> Self { |
1574 | Range { iter: self.iter.clone() } |
1575 | } |
1576 | } |
1577 | |
1578 | #[stable (feature = "btree_range" , since = "1.17.0" )] |
1579 | impl<'a, T> Iterator for Range<'a, T> { |
1580 | type Item = &'a T; |
1581 | |
1582 | fn next(&mut self) -> Option<&'a T> { |
1583 | self.iter.next().map(|(k, _)| k) |
1584 | } |
1585 | |
1586 | fn last(mut self) -> Option<&'a T> { |
1587 | self.next_back() |
1588 | } |
1589 | |
1590 | fn min(mut self) -> Option<&'a T> |
1591 | where |
1592 | &'a T: Ord, |
1593 | { |
1594 | self.next() |
1595 | } |
1596 | |
1597 | fn max(mut self) -> Option<&'a T> |
1598 | where |
1599 | &'a T: Ord, |
1600 | { |
1601 | self.next_back() |
1602 | } |
1603 | } |
1604 | |
1605 | #[stable (feature = "btree_range" , since = "1.17.0" )] |
1606 | impl<'a, T> DoubleEndedIterator for Range<'a, T> { |
1607 | fn next_back(&mut self) -> Option<&'a T> { |
1608 | self.iter.next_back().map(|(k: &T, _)| k) |
1609 | } |
1610 | } |
1611 | |
1612 | #[stable (feature = "fused" , since = "1.26.0" )] |
1613 | impl<T> FusedIterator for Range<'_, T> {} |
1614 | |
1615 | #[stable (feature = "default_iters" , since = "1.70.0" )] |
1616 | impl<T> Default for Range<'_, T> { |
1617 | /// Creates an empty `btree_set::Range`. |
1618 | /// |
1619 | /// ``` |
1620 | /// # use std::collections::btree_set; |
1621 | /// let iter: btree_set::Range<'_, u8> = Default::default(); |
1622 | /// assert_eq!(iter.count(), 0); |
1623 | /// ``` |
1624 | fn default() -> Self { |
1625 | Range { iter: Default::default() } |
1626 | } |
1627 | } |
1628 | |
1629 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1630 | impl<T, A: Allocator + Clone> Clone for Difference<'_, T, A> { |
1631 | fn clone(&self) -> Self { |
1632 | Difference { |
1633 | inner: match &self.inner { |
1634 | DifferenceInner::Stitch { self_iter: &Iter<'_, T>, other_iter: &Peekable> } => DifferenceInner::Stitch { |
1635 | self_iter: self_iter.clone(), |
1636 | other_iter: other_iter.clone(), |
1637 | }, |
1638 | DifferenceInner::Search { self_iter: &Iter<'_, T>, other_set: &&BTreeSet } => { |
1639 | DifferenceInner::Search { self_iter: self_iter.clone(), other_set } |
1640 | } |
1641 | DifferenceInner::Iterate(iter: &Iter<'_, T>) => DifferenceInner::Iterate(iter.clone()), |
1642 | }, |
1643 | } |
1644 | } |
1645 | } |
1646 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1647 | impl<'a, T: Ord, A: Allocator + Clone> Iterator for Difference<'a, T, A> { |
1648 | type Item = &'a T; |
1649 | |
1650 | fn next(&mut self) -> Option<&'a T> { |
1651 | match &mut self.inner { |
1652 | DifferenceInner::Stitch { self_iter, other_iter } => { |
1653 | let mut self_next = self_iter.next()?; |
1654 | loop { |
1655 | match other_iter.peek().map_or(Less, |other_next| self_next.cmp(other_next)) { |
1656 | Less => return Some(self_next), |
1657 | Equal => { |
1658 | self_next = self_iter.next()?; |
1659 | other_iter.next(); |
1660 | } |
1661 | Greater => { |
1662 | other_iter.next(); |
1663 | } |
1664 | } |
1665 | } |
1666 | } |
1667 | DifferenceInner::Search { self_iter, other_set } => loop { |
1668 | let self_next = self_iter.next()?; |
1669 | if !other_set.contains(&self_next) { |
1670 | return Some(self_next); |
1671 | } |
1672 | }, |
1673 | DifferenceInner::Iterate(iter) => iter.next(), |
1674 | } |
1675 | } |
1676 | |
1677 | fn size_hint(&self) -> (usize, Option<usize>) { |
1678 | let (self_len, other_len) = match &self.inner { |
1679 | DifferenceInner::Stitch { self_iter, other_iter } => { |
1680 | (self_iter.len(), other_iter.len()) |
1681 | } |
1682 | DifferenceInner::Search { self_iter, other_set } => (self_iter.len(), other_set.len()), |
1683 | DifferenceInner::Iterate(iter) => (iter.len(), 0), |
1684 | }; |
1685 | (self_len.saturating_sub(other_len), Some(self_len)) |
1686 | } |
1687 | |
1688 | fn min(mut self) -> Option<&'a T> { |
1689 | self.next() |
1690 | } |
1691 | } |
1692 | |
1693 | #[stable (feature = "fused" , since = "1.26.0" )] |
1694 | impl<T: Ord, A: Allocator + Clone> FusedIterator for Difference<'_, T, A> {} |
1695 | |
1696 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1697 | impl<T> Clone for SymmetricDifference<'_, T> { |
1698 | fn clone(&self) -> Self { |
1699 | SymmetricDifference(self.0.clone()) |
1700 | } |
1701 | } |
1702 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1703 | impl<'a, T: Ord> Iterator for SymmetricDifference<'a, T> { |
1704 | type Item = &'a T; |
1705 | |
1706 | fn next(&mut self) -> Option<&'a T> { |
1707 | loop { |
1708 | let (a_next: Option<&T>, b_next: Option<&T>) = self.0.nexts(Self::Item::cmp); |
1709 | if a_next.and(optb:b_next).is_none() { |
1710 | return a_next.or(optb:b_next); |
1711 | } |
1712 | } |
1713 | } |
1714 | |
1715 | fn size_hint(&self) -> (usize, Option<usize>) { |
1716 | let (a_len: usize, b_len: usize) = self.0.lens(); |
1717 | // No checked_add, because even if a and b refer to the same set, |
1718 | // and T is a zero-sized type, the storage overhead of sets limits |
1719 | // the number of elements to less than half the range of usize. |
1720 | (0, Some(a_len + b_len)) |
1721 | } |
1722 | |
1723 | fn min(mut self) -> Option<&'a T> { |
1724 | self.next() |
1725 | } |
1726 | } |
1727 | |
1728 | #[stable (feature = "fused" , since = "1.26.0" )] |
1729 | impl<T: Ord> FusedIterator for SymmetricDifference<'_, T> {} |
1730 | |
1731 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1732 | impl<T, A: Allocator + Clone> Clone for Intersection<'_, T, A> { |
1733 | fn clone(&self) -> Self { |
1734 | Intersection { |
1735 | inner: match &self.inner { |
1736 | IntersectionInner::Stitch { a: &Iter<'_, T>, b: &Iter<'_, T> } => { |
1737 | IntersectionInner::Stitch { a: a.clone(), b: b.clone() } |
1738 | } |
1739 | IntersectionInner::Search { small_iter: &Iter<'_, T>, large_set: &&BTreeSet } => { |
1740 | IntersectionInner::Search { small_iter: small_iter.clone(), large_set } |
1741 | } |
1742 | IntersectionInner::Answer(answer: &Option<&T>) => IntersectionInner::Answer(*answer), |
1743 | }, |
1744 | } |
1745 | } |
1746 | } |
1747 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1748 | impl<'a, T: Ord, A: Allocator + Clone> Iterator for Intersection<'a, T, A> { |
1749 | type Item = &'a T; |
1750 | |
1751 | fn next(&mut self) -> Option<&'a T> { |
1752 | match &mut self.inner { |
1753 | IntersectionInner::Stitch { a, b } => { |
1754 | let mut a_next = a.next()?; |
1755 | let mut b_next = b.next()?; |
1756 | loop { |
1757 | match a_next.cmp(b_next) { |
1758 | Less => a_next = a.next()?, |
1759 | Greater => b_next = b.next()?, |
1760 | Equal => return Some(a_next), |
1761 | } |
1762 | } |
1763 | } |
1764 | IntersectionInner::Search { small_iter, large_set } => loop { |
1765 | let small_next = small_iter.next()?; |
1766 | if large_set.contains(&small_next) { |
1767 | return Some(small_next); |
1768 | } |
1769 | }, |
1770 | IntersectionInner::Answer(answer) => answer.take(), |
1771 | } |
1772 | } |
1773 | |
1774 | fn size_hint(&self) -> (usize, Option<usize>) { |
1775 | match &self.inner { |
1776 | IntersectionInner::Stitch { a, b } => (0, Some(min(a.len(), b.len()))), |
1777 | IntersectionInner::Search { small_iter, .. } => (0, Some(small_iter.len())), |
1778 | IntersectionInner::Answer(None) => (0, Some(0)), |
1779 | IntersectionInner::Answer(Some(_)) => (1, Some(1)), |
1780 | } |
1781 | } |
1782 | |
1783 | fn min(mut self) -> Option<&'a T> { |
1784 | self.next() |
1785 | } |
1786 | } |
1787 | |
1788 | #[stable (feature = "fused" , since = "1.26.0" )] |
1789 | impl<T: Ord, A: Allocator + Clone> FusedIterator for Intersection<'_, T, A> {} |
1790 | |
1791 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1792 | impl<T> Clone for Union<'_, T> { |
1793 | fn clone(&self) -> Self { |
1794 | Union(self.0.clone()) |
1795 | } |
1796 | } |
1797 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1798 | impl<'a, T: Ord> Iterator for Union<'a, T> { |
1799 | type Item = &'a T; |
1800 | |
1801 | fn next(&mut self) -> Option<&'a T> { |
1802 | let (a_next: Option<&T>, b_next: Option<&T>) = self.0.nexts(Self::Item::cmp); |
1803 | a_next.or(optb:b_next) |
1804 | } |
1805 | |
1806 | fn size_hint(&self) -> (usize, Option<usize>) { |
1807 | let (a_len: usize, b_len: usize) = self.0.lens(); |
1808 | // No checked_add - see SymmetricDifference::size_hint. |
1809 | (max(v1:a_len, v2:b_len), Some(a_len + b_len)) |
1810 | } |
1811 | |
1812 | fn min(mut self) -> Option<&'a T> { |
1813 | self.next() |
1814 | } |
1815 | } |
1816 | |
1817 | #[stable (feature = "fused" , since = "1.26.0" )] |
1818 | impl<T: Ord> FusedIterator for Union<'_, T> {} |
1819 | |
1820 | #[cfg (test)] |
1821 | mod tests; |
1822 | |