]>
Commit | Line | Data |
---|---|---|
1a4d82fc JJ |
1 | // Copyright 2014 The Rust Project Developers. See the COPYRIGHT |
2 | // file at the top-level directory of this distribution and at | |
3 | // http://rust-lang.org/COPYRIGHT. | |
4 | // | |
5 | // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or | |
6 | // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license | |
7 | // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your | |
8 | // option. This file may not be copied, modified, or distributed | |
9 | // except according to those terms. | |
10 | ||
11 | // This is pretty much entirely stolen from TreeSet, since BTreeMap has an identical interface | |
12 | // to TreeMap | |
13 | ||
1a4d82fc | 14 | use core::cmp::Ordering::{self, Less, Greater, Equal}; |
7453a54e | 15 | use core::cmp::{min, max}; |
85aaf69f | 16 | use core::fmt::Debug; |
1a4d82fc | 17 | use core::fmt; |
9e0c209e | 18 | use core::iter::{Peekable, FromIterator, FusedIterator}; |
1a4d82fc JJ |
19 | use core::ops::{BitOr, BitAnd, BitXor, Sub}; |
20 | ||
85aaf69f | 21 | use borrow::Borrow; |
1a4d82fc | 22 | use btree_map::{BTreeMap, Keys}; |
e9174d1e | 23 | use super::Recover; |
32a655c1 | 24 | use range::RangeArgument; |
1a4d82fc JJ |
25 | |
26 | // FIXME(conventions): implement bounded iterators | |
27 | ||
28 | /// A set based on a B-Tree. | |
29 | /// | |
9cc50fc6 | 30 | /// See [`BTreeMap`]'s documentation for a detailed discussion of this collection's performance |
1a4d82fc | 31 | /// benefits and drawbacks. |
c34b1796 AL |
32 | /// |
33 | /// It is a logic error for an item to be modified in such a way that the item's ordering relative | |
9cc50fc6 SL |
34 | /// to any other item, as determined by the [`Ord`] trait, changes while it is in the set. This is |
35 | /// normally only possible through [`Cell`], [`RefCell`], global state, I/O, or unsafe code. | |
36 | /// | |
54a0048b SL |
37 | /// [`BTreeMap`]: struct.BTreeMap.html |
38 | /// [`Ord`]: ../../std/cmp/trait.Ord.html | |
9cc50fc6 SL |
39 | /// [`Cell`]: ../../std/cell/struct.Cell.html |
40 | /// [`RefCell`]: ../../std/cell/struct.RefCell.html | |
54a0048b SL |
41 | /// |
42 | /// # Examples | |
43 | /// | |
44 | /// ``` | |
45 | /// use std::collections::BTreeSet; | |
46 | /// | |
47 | /// // Type inference lets us omit an explicit type signature (which | |
48 | /// // would be `BTreeSet<&str>` in this example). | |
49 | /// let mut books = BTreeSet::new(); | |
50 | /// | |
51 | /// // Add some books. | |
52 | /// books.insert("A Dance With Dragons"); | |
53 | /// books.insert("To Kill a Mockingbird"); | |
54 | /// books.insert("The Odyssey"); | |
55 | /// books.insert("The Great Gatsby"); | |
56 | /// | |
57 | /// // Check for a specific one. | |
58 | /// if !books.contains("The Winds of Winter") { | |
59 | /// println!("We have {} books, but The Winds of Winter ain't one.", | |
60 | /// books.len()); | |
61 | /// } | |
62 | /// | |
63 | /// // Remove a book. | |
64 | /// books.remove("The Odyssey"); | |
65 | /// | |
66 | /// // Iterate over everything. | |
67 | /// for book in &books { | |
68 | /// println!("{}", book); | |
69 | /// } | |
70 | /// ``` | |
1a4d82fc | 71 | #[derive(Clone, Hash, PartialEq, Eq, Ord, PartialOrd)] |
85aaf69f | 72 | #[stable(feature = "rust1", since = "1.0.0")] |
92a42be0 | 73 | pub struct BTreeSet<T> { |
1a4d82fc JJ |
74 | map: BTreeMap<T, ()>, |
75 | } | |
76 | ||
cc61c64b | 77 | /// An iterator over the items of a `BTreeSet`. |
32a655c1 | 78 | /// |
cc61c64b XL |
79 | /// This `struct` is created by the [`iter`] method on [`BTreeSet`]. |
80 | /// See its documentation for more. | |
32a655c1 SL |
81 | /// |
82 | /// [`BTreeSet`]: struct.BTreeSet.html | |
83 | /// [`iter`]: struct.BTreeSet.html#method.iter | |
85aaf69f | 84 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 85 | pub struct Iter<'a, T: 'a> { |
92a42be0 | 86 | iter: Keys<'a, T, ()>, |
1a4d82fc JJ |
87 | } |
88 | ||
8bb4bdeb XL |
89 | #[stable(feature = "collection_debug", since = "1.17.0")] |
90 | impl<'a, T: 'a + fmt::Debug> fmt::Debug for Iter<'a, T> { | |
91 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | |
92 | f.debug_tuple("Iter") | |
93 | .field(&self.iter.clone()) | |
94 | .finish() | |
95 | } | |
96 | } | |
97 | ||
cc61c64b | 98 | /// An owning iterator over the items of a `BTreeSet`. |
32a655c1 | 99 | /// |
cc61c64b XL |
100 | /// This `struct` is created by the [`into_iter`] method on [`BTreeSet`][`BTreeSet`] |
101 | /// (provided by the `IntoIterator` trait). See its documentation for more. | |
32a655c1 SL |
102 | /// |
103 | /// [`BTreeSet`]: struct.BTreeSet.html | |
cc61c64b | 104 | /// [`into_iter`]: struct.BTreeSet.html#method.into_iter |
85aaf69f | 105 | #[stable(feature = "rust1", since = "1.0.0")] |
8bb4bdeb | 106 | #[derive(Debug)] |
1a4d82fc | 107 | pub struct IntoIter<T> { |
9cc50fc6 | 108 | iter: ::btree_map::IntoIter<T, ()>, |
85aaf69f SL |
109 | } |
110 | ||
cc61c64b | 111 | /// An iterator over a sub-range of items in a `BTreeSet`. |
32a655c1 | 112 | /// |
cc61c64b XL |
113 | /// This `struct` is created by the [`range`] method on [`BTreeSet`]. |
114 | /// See its documentation for more. | |
32a655c1 SL |
115 | /// |
116 | /// [`BTreeSet`]: struct.BTreeSet.html | |
117 | /// [`range`]: struct.BTreeSet.html#method.range | |
8bb4bdeb XL |
118 | #[derive(Debug)] |
119 | #[stable(feature = "btree_range", since = "1.17.0")] | |
85aaf69f | 120 | pub struct Range<'a, T: 'a> { |
9cc50fc6 | 121 | iter: ::btree_map::Range<'a, T, ()>, |
1a4d82fc JJ |
122 | } |
123 | ||
cc61c64b | 124 | /// A lazy iterator producing elements in the difference of `BTreeSet`s. |
32a655c1 | 125 | /// |
cc61c64b XL |
126 | /// This `struct` is created by the [`difference`] method on [`BTreeSet`]. |
127 | /// See its documentation for more. | |
32a655c1 SL |
128 | /// |
129 | /// [`BTreeSet`]: struct.BTreeSet.html | |
130 | /// [`difference`]: struct.BTreeSet.html#method.difference | |
85aaf69f | 131 | #[stable(feature = "rust1", since = "1.0.0")] |
92a42be0 | 132 | pub struct Difference<'a, T: 'a> { |
85aaf69f SL |
133 | a: Peekable<Iter<'a, T>>, |
134 | b: Peekable<Iter<'a, T>>, | |
1a4d82fc JJ |
135 | } |
136 | ||
8bb4bdeb XL |
137 | #[stable(feature = "collection_debug", since = "1.17.0")] |
138 | impl<'a, T: 'a + fmt::Debug> fmt::Debug for Difference<'a, T> { | |
139 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | |
140 | f.debug_tuple("Difference") | |
cc61c64b XL |
141 | .field(&self.a) |
142 | .field(&self.b) | |
8bb4bdeb XL |
143 | .finish() |
144 | } | |
145 | } | |
146 | ||
cc61c64b | 147 | /// A lazy iterator producing elements in the symmetric difference of `BTreeSet`s. |
32a655c1 | 148 | /// |
cc61c64b XL |
149 | /// This `struct` is created by the [`symmetric_difference`] method on |
150 | /// [`BTreeSet`]. See its documentation for more. | |
32a655c1 SL |
151 | /// |
152 | /// [`BTreeSet`]: struct.BTreeSet.html | |
153 | /// [`symmetric_difference`]: struct.BTreeSet.html#method.symmetric_difference | |
85aaf69f | 154 | #[stable(feature = "rust1", since = "1.0.0")] |
92a42be0 | 155 | pub struct SymmetricDifference<'a, T: 'a> { |
85aaf69f SL |
156 | a: Peekable<Iter<'a, T>>, |
157 | b: Peekable<Iter<'a, T>>, | |
1a4d82fc JJ |
158 | } |
159 | ||
8bb4bdeb XL |
160 | #[stable(feature = "collection_debug", since = "1.17.0")] |
161 | impl<'a, T: 'a + fmt::Debug> fmt::Debug for SymmetricDifference<'a, T> { | |
162 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | |
163 | f.debug_tuple("SymmetricDifference") | |
cc61c64b XL |
164 | .field(&self.a) |
165 | .field(&self.b) | |
8bb4bdeb XL |
166 | .finish() |
167 | } | |
168 | } | |
169 | ||
cc61c64b | 170 | /// A lazy iterator producing elements in the intersection of `BTreeSet`s. |
32a655c1 | 171 | /// |
cc61c64b XL |
172 | /// This `struct` is created by the [`intersection`] method on [`BTreeSet`]. |
173 | /// See its documentation for more. | |
32a655c1 SL |
174 | /// |
175 | /// [`BTreeSet`]: struct.BTreeSet.html | |
176 | /// [`intersection`]: struct.BTreeSet.html#method.intersection | |
85aaf69f | 177 | #[stable(feature = "rust1", since = "1.0.0")] |
92a42be0 | 178 | pub struct Intersection<'a, T: 'a> { |
85aaf69f SL |
179 | a: Peekable<Iter<'a, T>>, |
180 | b: Peekable<Iter<'a, T>>, | |
1a4d82fc JJ |
181 | } |
182 | ||
8bb4bdeb XL |
183 | #[stable(feature = "collection_debug", since = "1.17.0")] |
184 | impl<'a, T: 'a + fmt::Debug> fmt::Debug for Intersection<'a, T> { | |
185 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | |
186 | f.debug_tuple("Intersection") | |
cc61c64b XL |
187 | .field(&self.a) |
188 | .field(&self.b) | |
8bb4bdeb XL |
189 | .finish() |
190 | } | |
191 | } | |
192 | ||
cc61c64b | 193 | /// A lazy iterator producing elements in the union of `BTreeSet`s. |
32a655c1 | 194 | /// |
cc61c64b XL |
195 | /// This `struct` is created by the [`union`] method on [`BTreeSet`]. |
196 | /// See its documentation for more. | |
32a655c1 SL |
197 | /// |
198 | /// [`BTreeSet`]: struct.BTreeSet.html | |
199 | /// [`union`]: struct.BTreeSet.html#method.union | |
85aaf69f | 200 | #[stable(feature = "rust1", since = "1.0.0")] |
92a42be0 | 201 | pub struct Union<'a, T: 'a> { |
85aaf69f SL |
202 | a: Peekable<Iter<'a, T>>, |
203 | b: Peekable<Iter<'a, T>>, | |
1a4d82fc JJ |
204 | } |
205 | ||
8bb4bdeb XL |
206 | #[stable(feature = "collection_debug", since = "1.17.0")] |
207 | impl<'a, T: 'a + fmt::Debug> fmt::Debug for Union<'a, T> { | |
208 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | |
209 | f.debug_tuple("Union") | |
cc61c64b XL |
210 | .field(&self.a) |
211 | .field(&self.b) | |
8bb4bdeb XL |
212 | .finish() |
213 | } | |
214 | } | |
215 | ||
1a4d82fc | 216 | impl<T: Ord> BTreeSet<T> { |
32a655c1 | 217 | /// Makes a new `BTreeSet` with a reasonable choice of B. |
1a4d82fc JJ |
218 | /// |
219 | /// # Examples | |
220 | /// | |
221 | /// ``` | |
92a42be0 | 222 | /// # #![allow(unused_mut)] |
1a4d82fc JJ |
223 | /// use std::collections::BTreeSet; |
224 | /// | |
85aaf69f | 225 | /// let mut set: BTreeSet<i32> = BTreeSet::new(); |
1a4d82fc | 226 | /// ``` |
85aaf69f | 227 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
228 | pub fn new() -> BTreeSet<T> { |
229 | BTreeSet { map: BTreeMap::new() } | |
230 | } | |
1a4d82fc JJ |
231 | } |
232 | ||
233 | impl<T> BTreeSet<T> { | |
32a655c1 | 234 | /// Gets an iterator that visits the values in the `BTreeSet` in ascending order. |
1a4d82fc JJ |
235 | /// |
236 | /// # Examples | |
237 | /// | |
238 | /// ``` | |
239 | /// use std::collections::BTreeSet; | |
240 | /// | |
32a655c1 SL |
241 | /// let set: BTreeSet<usize> = [1, 2, 3].iter().cloned().collect(); |
242 | /// let mut set_iter = set.iter(); | |
243 | /// assert_eq!(set_iter.next(), Some(&1)); | |
244 | /// assert_eq!(set_iter.next(), Some(&2)); | |
245 | /// assert_eq!(set_iter.next(), Some(&3)); | |
246 | /// assert_eq!(set_iter.next(), None); | |
247 | /// ``` | |
1a4d82fc | 248 | /// |
32a655c1 SL |
249 | /// Values returned by the iterator are returned in ascending order: |
250 | /// | |
251 | /// ``` | |
252 | /// use std::collections::BTreeSet; | |
1a4d82fc | 253 | /// |
32a655c1 SL |
254 | /// let set: BTreeSet<usize> = [3, 1, 2].iter().cloned().collect(); |
255 | /// let mut set_iter = set.iter(); | |
256 | /// assert_eq!(set_iter.next(), Some(&1)); | |
257 | /// assert_eq!(set_iter.next(), Some(&2)); | |
258 | /// assert_eq!(set_iter.next(), Some(&3)); | |
259 | /// assert_eq!(set_iter.next(), None); | |
1a4d82fc | 260 | /// ``` |
85aaf69f | 261 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
262 | pub fn iter(&self) -> Iter<T> { |
263 | Iter { iter: self.map.keys() } | |
264 | } | |
1a4d82fc JJ |
265 | } |
266 | ||
85aaf69f | 267 | impl<T: Ord> BTreeSet<T> { |
32a655c1 SL |
268 | /// Constructs a double-ended iterator over a sub-range of elements in the set. |
269 | /// The simplest way is to use the range syntax `min..max`, thus `range(min..max)` will | |
270 | /// yield elements from min (inclusive) to max (exclusive). | |
271 | /// The range may also be entered as `(Bound<T>, Bound<T>)`, so for example | |
272 | /// `range((Excluded(4), Included(10)))` will yield a left-exclusive, right-inclusive | |
273 | /// range from 4 to 10. | |
85aaf69f SL |
274 | /// |
275 | /// # Examples | |
276 | /// | |
277 | /// ``` | |
278 | /// use std::collections::BTreeSet; | |
32a655c1 | 279 | /// use std::collections::Bound::Included; |
85aaf69f SL |
280 | /// |
281 | /// let mut set = BTreeSet::new(); | |
282 | /// set.insert(3); | |
283 | /// set.insert(5); | |
284 | /// set.insert(8); | |
32a655c1 | 285 | /// for &elem in set.range((Included(&4), Included(&8))) { |
85aaf69f SL |
286 | /// println!("{}", elem); |
287 | /// } | |
32a655c1 | 288 | /// assert_eq!(Some(&5), set.range(4..).next()); |
85aaf69f | 289 | /// ``` |
8bb4bdeb | 290 | #[stable(feature = "btree_range", since = "1.17.0")] |
32a655c1 SL |
291 | pub fn range<K: ?Sized, R>(&self, range: R) -> Range<T> |
292 | where K: Ord, T: Borrow<K>, R: RangeArgument<K> | |
e9174d1e | 293 | { |
32a655c1 | 294 | Range { iter: self.map.range(range) } |
85aaf69f SL |
295 | } |
296 | } | |
297 | ||
1a4d82fc | 298 | impl<T: Ord> BTreeSet<T> { |
8bb4bdeb XL |
299 | /// Visits the values representing the difference, |
300 | /// i.e. the values that are in `self` but not in `other`, | |
301 | /// in ascending order. | |
1a4d82fc JJ |
302 | /// |
303 | /// # Examples | |
304 | /// | |
305 | /// ``` | |
306 | /// use std::collections::BTreeSet; | |
307 | /// | |
308 | /// let mut a = BTreeSet::new(); | |
85aaf69f SL |
309 | /// a.insert(1); |
310 | /// a.insert(2); | |
1a4d82fc JJ |
311 | /// |
312 | /// let mut b = BTreeSet::new(); | |
85aaf69f SL |
313 | /// b.insert(2); |
314 | /// b.insert(3); | |
1a4d82fc | 315 | /// |
62682a34 | 316 | /// let diff: Vec<_> = a.difference(&b).cloned().collect(); |
c34b1796 | 317 | /// assert_eq!(diff, [1]); |
1a4d82fc | 318 | /// ``` |
85aaf69f | 319 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 320 | pub fn difference<'a>(&'a self, other: &'a BTreeSet<T>) -> Difference<'a, T> { |
92a42be0 SL |
321 | Difference { |
322 | a: self.iter().peekable(), | |
323 | b: other.iter().peekable(), | |
324 | } | |
1a4d82fc JJ |
325 | } |
326 | ||
8bb4bdeb XL |
327 | /// Visits the values representing the symmetric difference, |
328 | /// i.e. the values that are in `self` or in `other` but not in both, | |
329 | /// in ascending order. | |
1a4d82fc JJ |
330 | /// |
331 | /// # Examples | |
332 | /// | |
333 | /// ``` | |
334 | /// use std::collections::BTreeSet; | |
335 | /// | |
336 | /// let mut a = BTreeSet::new(); | |
85aaf69f SL |
337 | /// a.insert(1); |
338 | /// a.insert(2); | |
1a4d82fc JJ |
339 | /// |
340 | /// let mut b = BTreeSet::new(); | |
85aaf69f SL |
341 | /// b.insert(2); |
342 | /// b.insert(3); | |
1a4d82fc | 343 | /// |
62682a34 | 344 | /// let sym_diff: Vec<_> = a.symmetric_difference(&b).cloned().collect(); |
c34b1796 | 345 | /// assert_eq!(sym_diff, [1, 3]); |
1a4d82fc | 346 | /// ``` |
85aaf69f | 347 | #[stable(feature = "rust1", since = "1.0.0")] |
92a42be0 SL |
348 | pub fn symmetric_difference<'a>(&'a self, |
349 | other: &'a BTreeSet<T>) | |
350 | -> SymmetricDifference<'a, T> { | |
351 | SymmetricDifference { | |
352 | a: self.iter().peekable(), | |
353 | b: other.iter().peekable(), | |
354 | } | |
1a4d82fc JJ |
355 | } |
356 | ||
8bb4bdeb XL |
357 | /// Visits the values representing the intersection, |
358 | /// i.e. the values that are both in `self` and `other`, | |
359 | /// in ascending order. | |
1a4d82fc JJ |
360 | /// |
361 | /// # Examples | |
362 | /// | |
363 | /// ``` | |
364 | /// use std::collections::BTreeSet; | |
365 | /// | |
366 | /// let mut a = BTreeSet::new(); | |
85aaf69f SL |
367 | /// a.insert(1); |
368 | /// a.insert(2); | |
1a4d82fc JJ |
369 | /// |
370 | /// let mut b = BTreeSet::new(); | |
85aaf69f SL |
371 | /// b.insert(2); |
372 | /// b.insert(3); | |
1a4d82fc | 373 | /// |
62682a34 | 374 | /// let intersection: Vec<_> = a.intersection(&b).cloned().collect(); |
c34b1796 | 375 | /// assert_eq!(intersection, [2]); |
1a4d82fc | 376 | /// ``` |
85aaf69f | 377 | #[stable(feature = "rust1", since = "1.0.0")] |
92a42be0 SL |
378 | pub fn intersection<'a>(&'a self, other: &'a BTreeSet<T>) -> Intersection<'a, T> { |
379 | Intersection { | |
380 | a: self.iter().peekable(), | |
381 | b: other.iter().peekable(), | |
382 | } | |
1a4d82fc JJ |
383 | } |
384 | ||
8bb4bdeb XL |
385 | /// Visits the values representing the union, |
386 | /// i.e. all the values in `self` or `other`, without duplicates, | |
387 | /// in ascending order. | |
1a4d82fc JJ |
388 | /// |
389 | /// # Examples | |
390 | /// | |
391 | /// ``` | |
392 | /// use std::collections::BTreeSet; | |
393 | /// | |
394 | /// let mut a = BTreeSet::new(); | |
85aaf69f | 395 | /// a.insert(1); |
1a4d82fc JJ |
396 | /// |
397 | /// let mut b = BTreeSet::new(); | |
85aaf69f | 398 | /// b.insert(2); |
1a4d82fc | 399 | /// |
62682a34 | 400 | /// let union: Vec<_> = a.union(&b).cloned().collect(); |
c34b1796 | 401 | /// assert_eq!(union, [1, 2]); |
1a4d82fc | 402 | /// ``` |
85aaf69f | 403 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 404 | pub fn union<'a>(&'a self, other: &'a BTreeSet<T>) -> Union<'a, T> { |
92a42be0 SL |
405 | Union { |
406 | a: self.iter().peekable(), | |
407 | b: other.iter().peekable(), | |
408 | } | |
1a4d82fc JJ |
409 | } |
410 | ||
9346a6ac | 411 | /// Returns the number of elements in the set. |
1a4d82fc JJ |
412 | /// |
413 | /// # Examples | |
414 | /// | |
415 | /// ``` | |
416 | /// use std::collections::BTreeSet; | |
417 | /// | |
418 | /// let mut v = BTreeSet::new(); | |
419 | /// assert_eq!(v.len(), 0); | |
85aaf69f | 420 | /// v.insert(1); |
1a4d82fc JJ |
421 | /// assert_eq!(v.len(), 1); |
422 | /// ``` | |
85aaf69f | 423 | #[stable(feature = "rust1", since = "1.0.0")] |
92a42be0 SL |
424 | pub fn len(&self) -> usize { |
425 | self.map.len() | |
426 | } | |
1a4d82fc | 427 | |
cc61c64b | 428 | /// Returns `true` if the set contains no elements. |
1a4d82fc JJ |
429 | /// |
430 | /// # Examples | |
431 | /// | |
432 | /// ``` | |
433 | /// use std::collections::BTreeSet; | |
434 | /// | |
435 | /// let mut v = BTreeSet::new(); | |
436 | /// assert!(v.is_empty()); | |
85aaf69f | 437 | /// v.insert(1); |
1a4d82fc JJ |
438 | /// assert!(!v.is_empty()); |
439 | /// ``` | |
85aaf69f | 440 | #[stable(feature = "rust1", since = "1.0.0")] |
92a42be0 SL |
441 | pub fn is_empty(&self) -> bool { |
442 | self.len() == 0 | |
443 | } | |
1a4d82fc JJ |
444 | |
445 | /// Clears the set, removing all values. | |
446 | /// | |
447 | /// # Examples | |
448 | /// | |
449 | /// ``` | |
450 | /// use std::collections::BTreeSet; | |
451 | /// | |
452 | /// let mut v = BTreeSet::new(); | |
85aaf69f | 453 | /// v.insert(1); |
1a4d82fc JJ |
454 | /// v.clear(); |
455 | /// assert!(v.is_empty()); | |
456 | /// ``` | |
85aaf69f | 457 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
458 | pub fn clear(&mut self) { |
459 | self.map.clear() | |
460 | } | |
461 | ||
462 | /// Returns `true` if the set contains a value. | |
463 | /// | |
464 | /// The value may be any borrowed form of the set's value type, | |
465 | /// but the ordering on the borrowed form *must* match the | |
466 | /// ordering on the value type. | |
467 | /// | |
468 | /// # Examples | |
469 | /// | |
470 | /// ``` | |
471 | /// use std::collections::BTreeSet; | |
472 | /// | |
85aaf69f | 473 | /// let set: BTreeSet<_> = [1, 2, 3].iter().cloned().collect(); |
1a4d82fc JJ |
474 | /// assert_eq!(set.contains(&1), true); |
475 | /// assert_eq!(set.contains(&4), false); | |
476 | /// ``` | |
85aaf69f | 477 | #[stable(feature = "rust1", since = "1.0.0")] |
92a42be0 SL |
478 | pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool |
479 | where T: Borrow<Q>, | |
480 | Q: Ord | |
481 | { | |
1a4d82fc JJ |
482 | self.map.contains_key(value) |
483 | } | |
484 | ||
e9174d1e SL |
485 | /// Returns a reference to the value in the set, if any, that is equal to the given value. |
486 | /// | |
487 | /// The value may be any borrowed form of the set's value type, | |
488 | /// but the ordering on the borrowed form *must* match the | |
489 | /// ordering on the value type. | |
54a0048b | 490 | #[stable(feature = "set_recovery", since = "1.9.0")] |
92a42be0 SL |
491 | pub fn get<Q: ?Sized>(&self, value: &Q) -> Option<&T> |
492 | where T: Borrow<Q>, | |
493 | Q: Ord | |
494 | { | |
e9174d1e SL |
495 | Recover::get(&self.map, value) |
496 | } | |
497 | ||
8bb4bdeb | 498 | /// Returns `true` if `self` has no elements in common with `other`. |
1a4d82fc JJ |
499 | /// This is equivalent to checking for an empty intersection. |
500 | /// | |
501 | /// # Examples | |
502 | /// | |
503 | /// ``` | |
504 | /// use std::collections::BTreeSet; | |
505 | /// | |
85aaf69f SL |
506 | /// let a: BTreeSet<_> = [1, 2, 3].iter().cloned().collect(); |
507 | /// let mut b = BTreeSet::new(); | |
1a4d82fc JJ |
508 | /// |
509 | /// assert_eq!(a.is_disjoint(&b), true); | |
510 | /// b.insert(4); | |
511 | /// assert_eq!(a.is_disjoint(&b), true); | |
512 | /// b.insert(1); | |
513 | /// assert_eq!(a.is_disjoint(&b), false); | |
514 | /// ``` | |
85aaf69f | 515 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
516 | pub fn is_disjoint(&self, other: &BTreeSet<T>) -> bool { |
517 | self.intersection(other).next().is_none() | |
518 | } | |
519 | ||
8bb4bdeb XL |
520 | /// Returns `true` if the set is a subset of another, |
521 | /// i.e. `other` contains at least all the values in `self`. | |
1a4d82fc JJ |
522 | /// |
523 | /// # Examples | |
524 | /// | |
525 | /// ``` | |
526 | /// use std::collections::BTreeSet; | |
527 | /// | |
85aaf69f SL |
528 | /// let sup: BTreeSet<_> = [1, 2, 3].iter().cloned().collect(); |
529 | /// let mut set = BTreeSet::new(); | |
1a4d82fc JJ |
530 | /// |
531 | /// assert_eq!(set.is_subset(&sup), true); | |
532 | /// set.insert(2); | |
533 | /// assert_eq!(set.is_subset(&sup), true); | |
534 | /// set.insert(4); | |
535 | /// assert_eq!(set.is_subset(&sup), false); | |
536 | /// ``` | |
85aaf69f | 537 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
538 | pub fn is_subset(&self, other: &BTreeSet<T>) -> bool { |
539 | // Stolen from TreeMap | |
540 | let mut x = self.iter(); | |
541 | let mut y = other.iter(); | |
542 | let mut a = x.next(); | |
543 | let mut b = y.next(); | |
544 | while a.is_some() { | |
545 | if b.is_none() { | |
546 | return false; | |
547 | } | |
548 | ||
549 | let a1 = a.unwrap(); | |
550 | let b1 = b.unwrap(); | |
551 | ||
552 | match b1.cmp(a1) { | |
553 | Less => (), | |
554 | Greater => return false, | |
555 | Equal => a = x.next(), | |
556 | } | |
557 | ||
558 | b = y.next(); | |
559 | } | |
560 | true | |
561 | } | |
562 | ||
8bb4bdeb XL |
563 | /// Returns `true` if the set is a superset of another, |
564 | /// i.e. `self` contains at least all the values in `other`. | |
1a4d82fc JJ |
565 | /// |
566 | /// # Examples | |
567 | /// | |
568 | /// ``` | |
569 | /// use std::collections::BTreeSet; | |
570 | /// | |
85aaf69f SL |
571 | /// let sub: BTreeSet<_> = [1, 2].iter().cloned().collect(); |
572 | /// let mut set = BTreeSet::new(); | |
1a4d82fc JJ |
573 | /// |
574 | /// assert_eq!(set.is_superset(&sub), false); | |
575 | /// | |
576 | /// set.insert(0); | |
577 | /// set.insert(1); | |
578 | /// assert_eq!(set.is_superset(&sub), false); | |
579 | /// | |
580 | /// set.insert(2); | |
581 | /// assert_eq!(set.is_superset(&sub), true); | |
582 | /// ``` | |
85aaf69f | 583 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
584 | pub fn is_superset(&self, other: &BTreeSet<T>) -> bool { |
585 | other.is_subset(self) | |
586 | } | |
587 | ||
b039eaaf SL |
588 | /// Adds a value to the set. |
589 | /// | |
a7813a04 | 590 | /// If the set did not have this value present, `true` is returned. |
b039eaaf | 591 | /// |
a7813a04 | 592 | /// If the set did have this value present, `false` is returned, and the |
b039eaaf SL |
593 | /// entry is not updated. See the [module-level documentation] for more. |
594 | /// | |
595 | /// [module-level documentation]: index.html#insert-and-complex-keys | |
1a4d82fc JJ |
596 | /// |
597 | /// # Examples | |
598 | /// | |
599 | /// ``` | |
600 | /// use std::collections::BTreeSet; | |
601 | /// | |
602 | /// let mut set = BTreeSet::new(); | |
603 | /// | |
85aaf69f SL |
604 | /// assert_eq!(set.insert(2), true); |
605 | /// assert_eq!(set.insert(2), false); | |
1a4d82fc JJ |
606 | /// assert_eq!(set.len(), 1); |
607 | /// ``` | |
85aaf69f | 608 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
609 | pub fn insert(&mut self, value: T) -> bool { |
610 | self.map.insert(value, ()).is_none() | |
611 | } | |
612 | ||
e9174d1e SL |
613 | /// Adds a value to the set, replacing the existing value, if any, that is equal to the given |
614 | /// one. Returns the replaced value. | |
54a0048b | 615 | #[stable(feature = "set_recovery", since = "1.9.0")] |
e9174d1e SL |
616 | pub fn replace(&mut self, value: T) -> Option<T> { |
617 | Recover::replace(&mut self.map, value) | |
618 | } | |
619 | ||
1a4d82fc JJ |
620 | /// Removes a value from the set. Returns `true` if the value was |
621 | /// present in the set. | |
622 | /// | |
623 | /// The value may be any borrowed form of the set's value type, | |
624 | /// but the ordering on the borrowed form *must* match the | |
625 | /// ordering on the value type. | |
626 | /// | |
627 | /// # Examples | |
628 | /// | |
629 | /// ``` | |
630 | /// use std::collections::BTreeSet; | |
631 | /// | |
632 | /// let mut set = BTreeSet::new(); | |
633 | /// | |
85aaf69f | 634 | /// set.insert(2); |
1a4d82fc JJ |
635 | /// assert_eq!(set.remove(&2), true); |
636 | /// assert_eq!(set.remove(&2), false); | |
637 | /// ``` | |
85aaf69f | 638 | #[stable(feature = "rust1", since = "1.0.0")] |
92a42be0 SL |
639 | pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool |
640 | where T: Borrow<Q>, | |
641 | Q: Ord | |
642 | { | |
1a4d82fc JJ |
643 | self.map.remove(value).is_some() |
644 | } | |
e9174d1e SL |
645 | |
646 | /// Removes and returns the value in the set, if any, that is equal to the given one. | |
647 | /// | |
648 | /// The value may be any borrowed form of the set's value type, | |
649 | /// but the ordering on the borrowed form *must* match the | |
650 | /// ordering on the value type. | |
54a0048b | 651 | #[stable(feature = "set_recovery", since = "1.9.0")] |
92a42be0 SL |
652 | pub fn take<Q: ?Sized>(&mut self, value: &Q) -> Option<T> |
653 | where T: Borrow<Q>, | |
654 | Q: Ord | |
655 | { | |
e9174d1e SL |
656 | Recover::take(&mut self.map, value) |
657 | } | |
a7813a04 XL |
658 | |
659 | /// Moves all elements from `other` into `Self`, leaving `other` empty. | |
660 | /// | |
661 | /// # Examples | |
662 | /// | |
663 | /// ``` | |
a7813a04 XL |
664 | /// use std::collections::BTreeSet; |
665 | /// | |
666 | /// let mut a = BTreeSet::new(); | |
667 | /// a.insert(1); | |
668 | /// a.insert(2); | |
669 | /// a.insert(3); | |
670 | /// | |
671 | /// let mut b = BTreeSet::new(); | |
672 | /// b.insert(3); | |
673 | /// b.insert(4); | |
674 | /// b.insert(5); | |
675 | /// | |
676 | /// a.append(&mut b); | |
677 | /// | |
678 | /// assert_eq!(a.len(), 5); | |
679 | /// assert_eq!(b.len(), 0); | |
680 | /// | |
681 | /// assert!(a.contains(&1)); | |
682 | /// assert!(a.contains(&2)); | |
683 | /// assert!(a.contains(&3)); | |
684 | /// assert!(a.contains(&4)); | |
685 | /// assert!(a.contains(&5)); | |
686 | /// ``` | |
3157f602 | 687 | #[stable(feature = "btree_append", since = "1.11.0")] |
a7813a04 XL |
688 | pub fn append(&mut self, other: &mut Self) { |
689 | self.map.append(&mut other.map); | |
690 | } | |
3157f602 XL |
691 | |
692 | /// Splits the collection into two at the given key. Returns everything after the given key, | |
693 | /// including the key. | |
694 | /// | |
695 | /// # Examples | |
696 | /// | |
697 | /// Basic usage: | |
698 | /// | |
699 | /// ``` | |
700 | /// use std::collections::BTreeMap; | |
701 | /// | |
702 | /// let mut a = BTreeMap::new(); | |
703 | /// a.insert(1, "a"); | |
704 | /// a.insert(2, "b"); | |
705 | /// a.insert(3, "c"); | |
706 | /// a.insert(17, "d"); | |
707 | /// a.insert(41, "e"); | |
708 | /// | |
709 | /// let b = a.split_off(&3); | |
710 | /// | |
711 | /// assert_eq!(a.len(), 2); | |
712 | /// assert_eq!(b.len(), 3); | |
713 | /// | |
714 | /// assert_eq!(a[&1], "a"); | |
715 | /// assert_eq!(a[&2], "b"); | |
716 | /// | |
717 | /// assert_eq!(b[&3], "c"); | |
718 | /// assert_eq!(b[&17], "d"); | |
719 | /// assert_eq!(b[&41], "e"); | |
720 | /// ``` | |
721 | #[stable(feature = "btree_split_off", since = "1.11.0")] | |
722 | pub fn split_off<Q: ?Sized + Ord>(&mut self, key: &Q) -> Self where T: Borrow<Q> { | |
723 | BTreeSet { map: self.map.split_off(key) } | |
724 | } | |
1a4d82fc JJ |
725 | } |
726 | ||
85aaf69f | 727 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 728 | impl<T: Ord> FromIterator<T> for BTreeSet<T> { |
92a42be0 | 729 | fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> BTreeSet<T> { |
1a4d82fc JJ |
730 | let mut set = BTreeSet::new(); |
731 | set.extend(iter); | |
732 | set | |
733 | } | |
734 | } | |
735 | ||
85aaf69f SL |
736 | #[stable(feature = "rust1", since = "1.0.0")] |
737 | impl<T> IntoIterator for BTreeSet<T> { | |
738 | type Item = T; | |
739 | type IntoIter = IntoIter<T>; | |
740 | ||
cc61c64b | 741 | /// Gets an iterator for moving out the `BTreeSet`'s contents. |
9346a6ac AL |
742 | /// |
743 | /// # Examples | |
744 | /// | |
745 | /// ``` | |
9346a6ac AL |
746 | /// use std::collections::BTreeSet; |
747 | /// | |
748 | /// let set: BTreeSet<usize> = [1, 2, 3, 4].iter().cloned().collect(); | |
749 | /// | |
62682a34 | 750 | /// let v: Vec<_> = set.into_iter().collect(); |
9346a6ac AL |
751 | /// assert_eq!(v, [1, 2, 3, 4]); |
752 | /// ``` | |
85aaf69f | 753 | fn into_iter(self) -> IntoIter<T> { |
9cc50fc6 | 754 | IntoIter { iter: self.map.into_iter() } |
85aaf69f SL |
755 | } |
756 | } | |
757 | ||
758 | #[stable(feature = "rust1", since = "1.0.0")] | |
759 | impl<'a, T> IntoIterator for &'a BTreeSet<T> { | |
760 | type Item = &'a T; | |
761 | type IntoIter = Iter<'a, T>; | |
762 | ||
763 | fn into_iter(self) -> Iter<'a, T> { | |
764 | self.iter() | |
765 | } | |
766 | } | |
767 | ||
768 | #[stable(feature = "rust1", since = "1.0.0")] | |
1a4d82fc JJ |
769 | impl<T: Ord> Extend<T> for BTreeSet<T> { |
770 | #[inline] | |
92a42be0 | 771 | fn extend<Iter: IntoIterator<Item = T>>(&mut self, iter: Iter) { |
1a4d82fc JJ |
772 | for elem in iter { |
773 | self.insert(elem); | |
774 | } | |
775 | } | |
776 | } | |
777 | ||
62682a34 SL |
778 | #[stable(feature = "extend_ref", since = "1.2.0")] |
779 | impl<'a, T: 'a + Ord + Copy> Extend<&'a T> for BTreeSet<T> { | |
92a42be0 | 780 | fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) { |
62682a34 SL |
781 | self.extend(iter.into_iter().cloned()); |
782 | } | |
783 | } | |
784 | ||
85aaf69f | 785 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 786 | impl<T: Ord> Default for BTreeSet<T> { |
9e0c209e | 787 | /// Makes an empty `BTreeSet<T>` with a reasonable choice of B. |
1a4d82fc JJ |
788 | fn default() -> BTreeSet<T> { |
789 | BTreeSet::new() | |
790 | } | |
791 | } | |
792 | ||
85aaf69f | 793 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
794 | impl<'a, 'b, T: Ord + Clone> Sub<&'b BTreeSet<T>> for &'a BTreeSet<T> { |
795 | type Output = BTreeSet<T>; | |
796 | ||
797 | /// Returns the difference of `self` and `rhs` as a new `BTreeSet<T>`. | |
798 | /// | |
799 | /// # Examples | |
800 | /// | |
801 | /// ``` | |
802 | /// use std::collections::BTreeSet; | |
803 | /// | |
85aaf69f SL |
804 | /// let a: BTreeSet<_> = vec![1, 2, 3].into_iter().collect(); |
805 | /// let b: BTreeSet<_> = vec![3, 4, 5].into_iter().collect(); | |
1a4d82fc | 806 | /// |
85aaf69f SL |
807 | /// let result = &a - &b; |
808 | /// let result_vec: Vec<_> = result.into_iter().collect(); | |
c34b1796 | 809 | /// assert_eq!(result_vec, [1, 2]); |
1a4d82fc JJ |
810 | /// ``` |
811 | fn sub(self, rhs: &BTreeSet<T>) -> BTreeSet<T> { | |
812 | self.difference(rhs).cloned().collect() | |
813 | } | |
814 | } | |
815 | ||
85aaf69f | 816 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
817 | impl<'a, 'b, T: Ord + Clone> BitXor<&'b BTreeSet<T>> for &'a BTreeSet<T> { |
818 | type Output = BTreeSet<T>; | |
819 | ||
820 | /// Returns the symmetric difference of `self` and `rhs` as a new `BTreeSet<T>`. | |
821 | /// | |
822 | /// # Examples | |
823 | /// | |
824 | /// ``` | |
825 | /// use std::collections::BTreeSet; | |
826 | /// | |
85aaf69f SL |
827 | /// let a: BTreeSet<_> = vec![1, 2, 3].into_iter().collect(); |
828 | /// let b: BTreeSet<_> = vec![2, 3, 4].into_iter().collect(); | |
1a4d82fc | 829 | /// |
85aaf69f SL |
830 | /// let result = &a ^ &b; |
831 | /// let result_vec: Vec<_> = result.into_iter().collect(); | |
c34b1796 | 832 | /// assert_eq!(result_vec, [1, 4]); |
1a4d82fc JJ |
833 | /// ``` |
834 | fn bitxor(self, rhs: &BTreeSet<T>) -> BTreeSet<T> { | |
835 | self.symmetric_difference(rhs).cloned().collect() | |
836 | } | |
837 | } | |
838 | ||
85aaf69f | 839 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
840 | impl<'a, 'b, T: Ord + Clone> BitAnd<&'b BTreeSet<T>> for &'a BTreeSet<T> { |
841 | type Output = BTreeSet<T>; | |
842 | ||
843 | /// Returns the intersection of `self` and `rhs` as a new `BTreeSet<T>`. | |
844 | /// | |
845 | /// # Examples | |
846 | /// | |
847 | /// ``` | |
848 | /// use std::collections::BTreeSet; | |
849 | /// | |
85aaf69f SL |
850 | /// let a: BTreeSet<_> = vec![1, 2, 3].into_iter().collect(); |
851 | /// let b: BTreeSet<_> = vec![2, 3, 4].into_iter().collect(); | |
1a4d82fc | 852 | /// |
85aaf69f SL |
853 | /// let result = &a & &b; |
854 | /// let result_vec: Vec<_> = result.into_iter().collect(); | |
c34b1796 | 855 | /// assert_eq!(result_vec, [2, 3]); |
1a4d82fc JJ |
856 | /// ``` |
857 | fn bitand(self, rhs: &BTreeSet<T>) -> BTreeSet<T> { | |
858 | self.intersection(rhs).cloned().collect() | |
859 | } | |
860 | } | |
861 | ||
85aaf69f | 862 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
863 | impl<'a, 'b, T: Ord + Clone> BitOr<&'b BTreeSet<T>> for &'a BTreeSet<T> { |
864 | type Output = BTreeSet<T>; | |
865 | ||
866 | /// Returns the union of `self` and `rhs` as a new `BTreeSet<T>`. | |
867 | /// | |
868 | /// # Examples | |
869 | /// | |
870 | /// ``` | |
871 | /// use std::collections::BTreeSet; | |
872 | /// | |
85aaf69f SL |
873 | /// let a: BTreeSet<_> = vec![1, 2, 3].into_iter().collect(); |
874 | /// let b: BTreeSet<_> = vec![3, 4, 5].into_iter().collect(); | |
1a4d82fc | 875 | /// |
85aaf69f SL |
876 | /// let result = &a | &b; |
877 | /// let result_vec: Vec<_> = result.into_iter().collect(); | |
c34b1796 | 878 | /// assert_eq!(result_vec, [1, 2, 3, 4, 5]); |
1a4d82fc JJ |
879 | /// ``` |
880 | fn bitor(self, rhs: &BTreeSet<T>) -> BTreeSet<T> { | |
881 | self.union(rhs).cloned().collect() | |
882 | } | |
883 | } | |
884 | ||
85aaf69f SL |
885 | #[stable(feature = "rust1", since = "1.0.0")] |
886 | impl<T: Debug> Debug for BTreeSet<T> { | |
1a4d82fc | 887 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { |
62682a34 | 888 | f.debug_set().entries(self.iter()).finish() |
1a4d82fc JJ |
889 | } |
890 | } | |
891 | ||
c30ab7b3 | 892 | #[stable(feature = "rust1", since = "1.0.0")] |
c34b1796 | 893 | impl<'a, T> Clone for Iter<'a, T> { |
92a42be0 SL |
894 | fn clone(&self) -> Iter<'a, T> { |
895 | Iter { iter: self.iter.clone() } | |
896 | } | |
c34b1796 | 897 | } |
85aaf69f | 898 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
899 | impl<'a, T> Iterator for Iter<'a, T> { |
900 | type Item = &'a T; | |
901 | ||
92a42be0 SL |
902 | fn next(&mut self) -> Option<&'a T> { |
903 | self.iter.next() | |
904 | } | |
905 | fn size_hint(&self) -> (usize, Option<usize>) { | |
906 | self.iter.size_hint() | |
907 | } | |
1a4d82fc | 908 | } |
85aaf69f | 909 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 910 | impl<'a, T> DoubleEndedIterator for Iter<'a, T> { |
92a42be0 SL |
911 | fn next_back(&mut self) -> Option<&'a T> { |
912 | self.iter.next_back() | |
913 | } | |
1a4d82fc | 914 | } |
85aaf69f | 915 | #[stable(feature = "rust1", since = "1.0.0")] |
7453a54e SL |
916 | impl<'a, T> ExactSizeIterator for Iter<'a, T> { |
917 | fn len(&self) -> usize { self.iter.len() } | |
918 | } | |
1a4d82fc | 919 | |
9e0c209e SL |
920 | #[unstable(feature = "fused", issue = "35602")] |
921 | impl<'a, T> FusedIterator for Iter<'a, T> {} | |
1a4d82fc | 922 | |
85aaf69f | 923 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
924 | impl<T> Iterator for IntoIter<T> { |
925 | type Item = T; | |
926 | ||
92a42be0 | 927 | fn next(&mut self) -> Option<T> { |
9cc50fc6 | 928 | self.iter.next().map(|(k, _)| k) |
92a42be0 SL |
929 | } |
930 | fn size_hint(&self) -> (usize, Option<usize>) { | |
931 | self.iter.size_hint() | |
932 | } | |
1a4d82fc | 933 | } |
85aaf69f | 934 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 935 | impl<T> DoubleEndedIterator for IntoIter<T> { |
92a42be0 | 936 | fn next_back(&mut self) -> Option<T> { |
9cc50fc6 | 937 | self.iter.next_back().map(|(k, _)| k) |
92a42be0 | 938 | } |
1a4d82fc | 939 | } |
85aaf69f | 940 | #[stable(feature = "rust1", since = "1.0.0")] |
7453a54e SL |
941 | impl<T> ExactSizeIterator for IntoIter<T> { |
942 | fn len(&self) -> usize { self.iter.len() } | |
943 | } | |
1a4d82fc | 944 | |
9e0c209e SL |
945 | #[unstable(feature = "fused", issue = "35602")] |
946 | impl<T> FusedIterator for IntoIter<T> {} | |
85aaf69f | 947 | |
cc61c64b | 948 | #[stable(feature = "btree_range", since = "1.17.0")] |
c34b1796 | 949 | impl<'a, T> Clone for Range<'a, T> { |
92a42be0 SL |
950 | fn clone(&self) -> Range<'a, T> { |
951 | Range { iter: self.iter.clone() } | |
952 | } | |
c34b1796 | 953 | } |
cc61c64b XL |
954 | |
955 | #[stable(feature = "btree_range", since = "1.17.0")] | |
85aaf69f SL |
956 | impl<'a, T> Iterator for Range<'a, T> { |
957 | type Item = &'a T; | |
958 | ||
92a42be0 | 959 | fn next(&mut self) -> Option<&'a T> { |
9cc50fc6 | 960 | self.iter.next().map(|(k, _)| k) |
92a42be0 | 961 | } |
85aaf69f | 962 | } |
cc61c64b XL |
963 | |
964 | #[stable(feature = "btree_range", since = "1.17.0")] | |
85aaf69f | 965 | impl<'a, T> DoubleEndedIterator for Range<'a, T> { |
92a42be0 | 966 | fn next_back(&mut self) -> Option<&'a T> { |
9cc50fc6 | 967 | self.iter.next_back().map(|(k, _)| k) |
92a42be0 | 968 | } |
85aaf69f SL |
969 | } |
970 | ||
9e0c209e SL |
971 | #[unstable(feature = "fused", issue = "35602")] |
972 | impl<'a, T> FusedIterator for Range<'a, T> {} | |
973 | ||
1a4d82fc | 974 | /// Compare `x` and `y`, but return `short` if x is None and `long` if y is None |
92a42be0 | 975 | fn cmp_opt<T: Ord>(x: Option<&T>, y: Option<&T>, short: Ordering, long: Ordering) -> Ordering { |
1a4d82fc | 976 | match (x, y) { |
92a42be0 SL |
977 | (None, _) => short, |
978 | (_, None) => long, | |
1a4d82fc JJ |
979 | (Some(x1), Some(y1)) => x1.cmp(y1), |
980 | } | |
981 | } | |
982 | ||
c30ab7b3 | 983 | #[stable(feature = "rust1", since = "1.0.0")] |
c34b1796 AL |
984 | impl<'a, T> Clone for Difference<'a, T> { |
985 | fn clone(&self) -> Difference<'a, T> { | |
92a42be0 SL |
986 | Difference { |
987 | a: self.a.clone(), | |
988 | b: self.b.clone(), | |
989 | } | |
c34b1796 AL |
990 | } |
991 | } | |
85aaf69f | 992 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
993 | impl<'a, T: Ord> Iterator for Difference<'a, T> { |
994 | type Item = &'a T; | |
995 | ||
996 | fn next(&mut self) -> Option<&'a T> { | |
997 | loop { | |
998 | match cmp_opt(self.a.peek(), self.b.peek(), Less, Less) { | |
92a42be0 SL |
999 | Less => return self.a.next(), |
1000 | Equal => { | |
1001 | self.a.next(); | |
1002 | self.b.next(); | |
1003 | } | |
1004 | Greater => { | |
1005 | self.b.next(); | |
1006 | } | |
1a4d82fc JJ |
1007 | } |
1008 | } | |
1009 | } | |
7453a54e SL |
1010 | |
1011 | fn size_hint(&self) -> (usize, Option<usize>) { | |
1012 | let a_len = self.a.len(); | |
1013 | let b_len = self.b.len(); | |
1014 | (a_len.saturating_sub(b_len), Some(a_len)) | |
1015 | } | |
1a4d82fc JJ |
1016 | } |
1017 | ||
9e0c209e SL |
1018 | #[unstable(feature = "fused", issue = "35602")] |
1019 | impl<'a, T: Ord> FusedIterator for Difference<'a, T> {} | |
1020 | ||
c30ab7b3 | 1021 | #[stable(feature = "rust1", since = "1.0.0")] |
c34b1796 AL |
1022 | impl<'a, T> Clone for SymmetricDifference<'a, T> { |
1023 | fn clone(&self) -> SymmetricDifference<'a, T> { | |
92a42be0 SL |
1024 | SymmetricDifference { |
1025 | a: self.a.clone(), | |
1026 | b: self.b.clone(), | |
1027 | } | |
c34b1796 AL |
1028 | } |
1029 | } | |
85aaf69f | 1030 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1031 | impl<'a, T: Ord> Iterator for SymmetricDifference<'a, T> { |
1032 | type Item = &'a T; | |
1033 | ||
1034 | fn next(&mut self) -> Option<&'a T> { | |
1035 | loop { | |
1036 | match cmp_opt(self.a.peek(), self.b.peek(), Greater, Less) { | |
92a42be0 SL |
1037 | Less => return self.a.next(), |
1038 | Equal => { | |
1039 | self.a.next(); | |
1040 | self.b.next(); | |
1041 | } | |
1a4d82fc JJ |
1042 | Greater => return self.b.next(), |
1043 | } | |
1044 | } | |
1045 | } | |
7453a54e SL |
1046 | |
1047 | fn size_hint(&self) -> (usize, Option<usize>) { | |
1048 | (0, Some(self.a.len() + self.b.len())) | |
1049 | } | |
1a4d82fc JJ |
1050 | } |
1051 | ||
9e0c209e SL |
1052 | #[unstable(feature = "fused", issue = "35602")] |
1053 | impl<'a, T: Ord> FusedIterator for SymmetricDifference<'a, T> {} | |
1054 | ||
c30ab7b3 | 1055 | #[stable(feature = "rust1", since = "1.0.0")] |
c34b1796 AL |
1056 | impl<'a, T> Clone for Intersection<'a, T> { |
1057 | fn clone(&self) -> Intersection<'a, T> { | |
92a42be0 SL |
1058 | Intersection { |
1059 | a: self.a.clone(), | |
1060 | b: self.b.clone(), | |
1061 | } | |
c34b1796 AL |
1062 | } |
1063 | } | |
85aaf69f | 1064 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1065 | impl<'a, T: Ord> Iterator for Intersection<'a, T> { |
1066 | type Item = &'a T; | |
1067 | ||
1068 | fn next(&mut self) -> Option<&'a T> { | |
1069 | loop { | |
ff7c6d11 XL |
1070 | match Ord::cmp(self.a.peek()?, self.b.peek()?) { |
1071 | Less => { | |
92a42be0 SL |
1072 | self.a.next(); |
1073 | } | |
ff7c6d11 | 1074 | Equal => { |
92a42be0 SL |
1075 | self.b.next(); |
1076 | return self.a.next(); | |
1077 | } | |
ff7c6d11 | 1078 | Greater => { |
92a42be0 SL |
1079 | self.b.next(); |
1080 | } | |
1a4d82fc JJ |
1081 | } |
1082 | } | |
1083 | } | |
7453a54e SL |
1084 | |
1085 | fn size_hint(&self) -> (usize, Option<usize>) { | |
1086 | (0, Some(min(self.a.len(), self.b.len()))) | |
1087 | } | |
1a4d82fc JJ |
1088 | } |
1089 | ||
9e0c209e SL |
1090 | #[unstable(feature = "fused", issue = "35602")] |
1091 | impl<'a, T: Ord> FusedIterator for Intersection<'a, T> {} | |
1092 | ||
c30ab7b3 | 1093 | #[stable(feature = "rust1", since = "1.0.0")] |
c34b1796 AL |
1094 | impl<'a, T> Clone for Union<'a, T> { |
1095 | fn clone(&self) -> Union<'a, T> { | |
92a42be0 SL |
1096 | Union { |
1097 | a: self.a.clone(), | |
1098 | b: self.b.clone(), | |
1099 | } | |
c34b1796 AL |
1100 | } |
1101 | } | |
85aaf69f | 1102 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1103 | impl<'a, T: Ord> Iterator for Union<'a, T> { |
1104 | type Item = &'a T; | |
1105 | ||
1106 | fn next(&mut self) -> Option<&'a T> { | |
ea8adc8c XL |
1107 | match cmp_opt(self.a.peek(), self.b.peek(), Greater, Less) { |
1108 | Less => self.a.next(), | |
1109 | Equal => { | |
1110 | self.b.next(); | |
1111 | self.a.next() | |
1a4d82fc | 1112 | } |
ea8adc8c | 1113 | Greater => self.b.next(), |
1a4d82fc JJ |
1114 | } |
1115 | } | |
7453a54e SL |
1116 | |
1117 | fn size_hint(&self) -> (usize, Option<usize>) { | |
1118 | let a_len = self.a.len(); | |
1119 | let b_len = self.b.len(); | |
1120 | (max(a_len, b_len), Some(a_len + b_len)) | |
1121 | } | |
1a4d82fc | 1122 | } |
9e0c209e SL |
1123 | |
1124 | #[unstable(feature = "fused", issue = "35602")] | |
1125 | impl<'a, T: Ord> FusedIterator for Union<'a, T> {} |