]>
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. | |
1a4d82fc | 10 | |
85aaf69f | 11 | use borrow::Borrow; |
1a4d82fc JJ |
12 | use clone::Clone; |
13 | use cmp::{Eq, PartialEq}; | |
14 | use core::marker::Sized; | |
15 | use default::Default; | |
85aaf69f | 16 | use fmt::Debug; |
1a4d82fc | 17 | use fmt; |
85aaf69f | 18 | use hash::Hash; |
c34b1796 | 19 | use iter::{Iterator, IntoIterator, ExactSizeIterator, FromIterator, Map, Chain, Extend}; |
1a4d82fc JJ |
20 | use ops::{BitOr, BitAnd, BitXor, Sub}; |
21 | use option::Option::{Some, None, self}; | |
22 | ||
e9174d1e | 23 | use super::Recover; |
62682a34 | 24 | use super::map::{self, HashMap, Keys, RandomState}; |
1a4d82fc JJ |
25 | use super::state::HashState; |
26 | ||
62682a34 SL |
27 | const INITIAL_CAPACITY: usize = 32; |
28 | ||
1a4d82fc JJ |
29 | // Future Optimization (FIXME!) |
30 | // ============================= | |
31 | // | |
32 | // Iteration over zero sized values is a noop. There is no need | |
33 | // for `bucket.val` in the case of HashSet. I suppose we would need HKT | |
34 | // to get rid of it properly. | |
35 | ||
36 | /// An implementation of a hash set using the underlying representation of a | |
d9579d0f AL |
37 | /// HashMap where the value is (). |
38 | /// | |
39 | /// As with the `HashMap` type, a `HashSet` requires that the elements | |
40 | /// implement the `Eq` and `Hash` traits. This can frequently be achieved by | |
41 | /// using `#[derive(PartialEq, Eq, Hash)]`. If you implement these yourself, | |
42 | /// it is important that the following property holds: | |
c34b1796 AL |
43 | /// |
44 | /// ```text | |
45 | /// k1 == k2 -> hash(k1) == hash(k2) | |
46 | /// ``` | |
47 | /// | |
48 | /// In other words, if two keys are equal, their hashes must be equal. | |
1a4d82fc | 49 | /// |
c34b1796 AL |
50 | /// |
51 | /// It is a logic error for an item to be modified in such a way that the | |
52 | /// item's hash, as determined by the `Hash` trait, or its equality, as | |
53 | /// determined by the `Eq` trait, changes while it is in the set. This is | |
54 | /// normally only possible through `Cell`, `RefCell`, global state, I/O, or | |
55 | /// unsafe code. | |
56 | /// | |
57 | /// # Examples | |
1a4d82fc JJ |
58 | /// |
59 | /// ``` | |
60 | /// use std::collections::HashSet; | |
61 | /// // Type inference lets us omit an explicit type signature (which | |
62 | /// // would be `HashSet<&str>` in this example). | |
63 | /// let mut books = HashSet::new(); | |
64 | /// | |
65 | /// // Add some books. | |
66 | /// books.insert("A Dance With Dragons"); | |
67 | /// books.insert("To Kill a Mockingbird"); | |
68 | /// books.insert("The Odyssey"); | |
69 | /// books.insert("The Great Gatsby"); | |
70 | /// | |
71 | /// // Check for a specific one. | |
d9579d0f | 72 | /// if !books.contains("The Winds of Winter") { |
1a4d82fc JJ |
73 | /// println!("We have {} books, but The Winds of Winter ain't one.", |
74 | /// books.len()); | |
75 | /// } | |
76 | /// | |
77 | /// // Remove a book. | |
d9579d0f | 78 | /// books.remove("The Odyssey"); |
1a4d82fc JJ |
79 | /// |
80 | /// // Iterate over everything. | |
d9579d0f AL |
81 | /// for book in &books { |
82 | /// println!("{}", book); | |
1a4d82fc JJ |
83 | /// } |
84 | /// ``` | |
85 | /// | |
86 | /// The easiest way to use `HashSet` with a custom type is to derive | |
87 | /// `Eq` and `Hash`. We must also derive `PartialEq`, this will in the | |
88 | /// future be implied by `Eq`. | |
89 | /// | |
90 | /// ``` | |
91 | /// use std::collections::HashSet; | |
85aaf69f | 92 | /// #[derive(Hash, Eq, PartialEq, Debug)] |
1a4d82fc JJ |
93 | /// struct Viking<'a> { |
94 | /// name: &'a str, | |
85aaf69f | 95 | /// power: usize, |
1a4d82fc JJ |
96 | /// } |
97 | /// | |
98 | /// let mut vikings = HashSet::new(); | |
99 | /// | |
85aaf69f SL |
100 | /// vikings.insert(Viking { name: "Einar", power: 9 }); |
101 | /// vikings.insert(Viking { name: "Einar", power: 9 }); | |
102 | /// vikings.insert(Viking { name: "Olaf", power: 4 }); | |
103 | /// vikings.insert(Viking { name: "Harald", power: 8 }); | |
1a4d82fc JJ |
104 | /// |
105 | /// // Use derived implementation to print the vikings. | |
d9579d0f | 106 | /// for x in &vikings { |
1a4d82fc JJ |
107 | /// println!("{:?}", x); |
108 | /// } | |
109 | /// ``` | |
110 | #[derive(Clone)] | |
85aaf69f | 111 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
112 | pub struct HashSet<T, S = RandomState> { |
113 | map: HashMap<T, (), S> | |
114 | } | |
115 | ||
85aaf69f | 116 | impl<T: Hash + Eq> HashSet<T, RandomState> { |
9346a6ac | 117 | /// Creates an empty HashSet. |
1a4d82fc | 118 | /// |
c34b1796 | 119 | /// # Examples |
1a4d82fc JJ |
120 | /// |
121 | /// ``` | |
122 | /// use std::collections::HashSet; | |
85aaf69f | 123 | /// let mut set: HashSet<i32> = HashSet::new(); |
1a4d82fc JJ |
124 | /// ``` |
125 | #[inline] | |
85aaf69f | 126 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
127 | pub fn new() -> HashSet<T, RandomState> { |
128 | HashSet::with_capacity(INITIAL_CAPACITY) | |
129 | } | |
130 | ||
9346a6ac | 131 | /// Creates an empty HashSet with space for at least `n` elements in |
1a4d82fc JJ |
132 | /// the hash table. |
133 | /// | |
c34b1796 | 134 | /// # Examples |
1a4d82fc JJ |
135 | /// |
136 | /// ``` | |
137 | /// use std::collections::HashSet; | |
85aaf69f | 138 | /// let mut set: HashSet<i32> = HashSet::with_capacity(10); |
1a4d82fc JJ |
139 | /// ``` |
140 | #[inline] | |
85aaf69f SL |
141 | #[stable(feature = "rust1", since = "1.0.0")] |
142 | pub fn with_capacity(capacity: usize) -> HashSet<T, RandomState> { | |
1a4d82fc JJ |
143 | HashSet { map: HashMap::with_capacity(capacity) } |
144 | } | |
145 | } | |
146 | ||
85aaf69f SL |
147 | impl<T, S> HashSet<T, S> |
148 | where T: Eq + Hash, S: HashState | |
1a4d82fc JJ |
149 | { |
150 | /// Creates a new empty hash set which will use the given hasher to hash | |
151 | /// keys. | |
152 | /// | |
153 | /// The hash set is also created with the default initial capacity. | |
154 | /// | |
c34b1796 | 155 | /// # Examples |
1a4d82fc JJ |
156 | /// |
157 | /// ``` | |
c1a9b12d SL |
158 | /// #![feature(hashmap_hasher)] |
159 | /// | |
1a4d82fc JJ |
160 | /// use std::collections::HashSet; |
161 | /// use std::collections::hash_map::RandomState; | |
162 | /// | |
163 | /// let s = RandomState::new(); | |
164 | /// let mut set = HashSet::with_hash_state(s); | |
85aaf69f | 165 | /// set.insert(2); |
1a4d82fc JJ |
166 | /// ``` |
167 | #[inline] | |
e9174d1e SL |
168 | #[unstable(feature = "hashmap_hasher", reason = "hasher stuff is unclear", |
169 | issue = "27713")] | |
1a4d82fc JJ |
170 | pub fn with_hash_state(hash_state: S) -> HashSet<T, S> { |
171 | HashSet::with_capacity_and_hash_state(INITIAL_CAPACITY, hash_state) | |
172 | } | |
173 | ||
9346a6ac | 174 | /// Creates an empty HashSet with space for at least `capacity` |
1a4d82fc JJ |
175 | /// elements in the hash table, using `hasher` to hash the keys. |
176 | /// | |
177 | /// Warning: `hasher` is normally randomly generated, and | |
178 | /// is designed to allow `HashSet`s to be resistant to attacks that | |
179 | /// cause many collisions and very poor performance. Setting it | |
180 | /// manually using this function can expose a DoS attack vector. | |
181 | /// | |
c34b1796 | 182 | /// # Examples |
1a4d82fc JJ |
183 | /// |
184 | /// ``` | |
c1a9b12d SL |
185 | /// #![feature(hashmap_hasher)] |
186 | /// | |
1a4d82fc JJ |
187 | /// use std::collections::HashSet; |
188 | /// use std::collections::hash_map::RandomState; | |
189 | /// | |
190 | /// let s = RandomState::new(); | |
85aaf69f SL |
191 | /// let mut set = HashSet::with_capacity_and_hash_state(10, s); |
192 | /// set.insert(1); | |
1a4d82fc JJ |
193 | /// ``` |
194 | #[inline] | |
e9174d1e SL |
195 | #[unstable(feature = "hashmap_hasher", reason = "hasher stuff is unclear", |
196 | issue = "27713")] | |
85aaf69f | 197 | pub fn with_capacity_and_hash_state(capacity: usize, hash_state: S) |
1a4d82fc JJ |
198 | -> HashSet<T, S> { |
199 | HashSet { | |
200 | map: HashMap::with_capacity_and_hash_state(capacity, hash_state), | |
201 | } | |
202 | } | |
203 | ||
204 | /// Returns the number of elements the set can hold without reallocating. | |
205 | /// | |
c34b1796 | 206 | /// # Examples |
1a4d82fc JJ |
207 | /// |
208 | /// ``` | |
209 | /// use std::collections::HashSet; | |
85aaf69f | 210 | /// let set: HashSet<i32> = HashSet::with_capacity(100); |
1a4d82fc JJ |
211 | /// assert!(set.capacity() >= 100); |
212 | /// ``` | |
213 | #[inline] | |
85aaf69f SL |
214 | #[stable(feature = "rust1", since = "1.0.0")] |
215 | pub fn capacity(&self) -> usize { | |
1a4d82fc JJ |
216 | self.map.capacity() |
217 | } | |
218 | ||
219 | /// Reserves capacity for at least `additional` more elements to be inserted | |
220 | /// in the `HashSet`. The collection may reserve more space to avoid | |
221 | /// frequent reallocations. | |
222 | /// | |
223 | /// # Panics | |
224 | /// | |
85aaf69f | 225 | /// Panics if the new allocation size overflows `usize`. |
1a4d82fc | 226 | /// |
c34b1796 | 227 | /// # Examples |
1a4d82fc JJ |
228 | /// |
229 | /// ``` | |
230 | /// use std::collections::HashSet; | |
85aaf69f | 231 | /// let mut set: HashSet<i32> = HashSet::new(); |
1a4d82fc JJ |
232 | /// set.reserve(10); |
233 | /// ``` | |
85aaf69f SL |
234 | #[stable(feature = "rust1", since = "1.0.0")] |
235 | pub fn reserve(&mut self, additional: usize) { | |
1a4d82fc JJ |
236 | self.map.reserve(additional) |
237 | } | |
238 | ||
239 | /// Shrinks the capacity of the set as much as possible. It will drop | |
240 | /// down as much as possible while maintaining the internal rules | |
241 | /// and possibly leaving some space in accordance with the resize policy. | |
242 | /// | |
c34b1796 | 243 | /// # Examples |
1a4d82fc JJ |
244 | /// |
245 | /// ``` | |
246 | /// use std::collections::HashSet; | |
247 | /// | |
85aaf69f | 248 | /// let mut set = HashSet::with_capacity(100); |
1a4d82fc JJ |
249 | /// set.insert(1); |
250 | /// set.insert(2); | |
251 | /// assert!(set.capacity() >= 100); | |
252 | /// set.shrink_to_fit(); | |
253 | /// assert!(set.capacity() >= 2); | |
254 | /// ``` | |
85aaf69f | 255 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
256 | pub fn shrink_to_fit(&mut self) { |
257 | self.map.shrink_to_fit() | |
258 | } | |
259 | ||
260 | /// An iterator visiting all elements in arbitrary order. | |
261 | /// Iterator element type is &'a T. | |
262 | /// | |
c34b1796 | 263 | /// # Examples |
1a4d82fc JJ |
264 | /// |
265 | /// ``` | |
266 | /// use std::collections::HashSet; | |
267 | /// let mut set = HashSet::new(); | |
268 | /// set.insert("a"); | |
269 | /// set.insert("b"); | |
270 | /// | |
271 | /// // Will print in an arbitrary order. | |
272 | /// for x in set.iter() { | |
273 | /// println!("{}", x); | |
274 | /// } | |
275 | /// ``` | |
85aaf69f | 276 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
277 | pub fn iter(&self) -> Iter<T> { |
278 | Iter { iter: self.map.keys() } | |
279 | } | |
280 | ||
1a4d82fc JJ |
281 | /// Visit the values representing the difference. |
282 | /// | |
c34b1796 | 283 | /// # Examples |
1a4d82fc JJ |
284 | /// |
285 | /// ``` | |
286 | /// use std::collections::HashSet; | |
85aaf69f SL |
287 | /// let a: HashSet<_> = [1, 2, 3].iter().cloned().collect(); |
288 | /// let b: HashSet<_> = [4, 2, 3, 4].iter().cloned().collect(); | |
1a4d82fc JJ |
289 | /// |
290 | /// // Can be seen as `a - b`. | |
291 | /// for x in a.difference(&b) { | |
292 | /// println!("{}", x); // Print 1 | |
293 | /// } | |
294 | /// | |
85aaf69f SL |
295 | /// let diff: HashSet<_> = a.difference(&b).cloned().collect(); |
296 | /// assert_eq!(diff, [1].iter().cloned().collect()); | |
1a4d82fc JJ |
297 | /// |
298 | /// // Note that difference is not symmetric, | |
299 | /// // and `b - a` means something else: | |
85aaf69f SL |
300 | /// let diff: HashSet<_> = b.difference(&a).cloned().collect(); |
301 | /// assert_eq!(diff, [4].iter().cloned().collect()); | |
1a4d82fc | 302 | /// ``` |
85aaf69f | 303 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
304 | pub fn difference<'a>(&'a self, other: &'a HashSet<T, S>) -> Difference<'a, T, S> { |
305 | Difference { | |
306 | iter: self.iter(), | |
307 | other: other, | |
308 | } | |
309 | } | |
310 | ||
311 | /// Visit the values representing the symmetric difference. | |
312 | /// | |
c34b1796 | 313 | /// # Examples |
1a4d82fc JJ |
314 | /// |
315 | /// ``` | |
316 | /// use std::collections::HashSet; | |
85aaf69f SL |
317 | /// let a: HashSet<_> = [1, 2, 3].iter().cloned().collect(); |
318 | /// let b: HashSet<_> = [4, 2, 3, 4].iter().cloned().collect(); | |
1a4d82fc JJ |
319 | /// |
320 | /// // Print 1, 4 in arbitrary order. | |
321 | /// for x in a.symmetric_difference(&b) { | |
322 | /// println!("{}", x); | |
323 | /// } | |
324 | /// | |
85aaf69f SL |
325 | /// let diff1: HashSet<_> = a.symmetric_difference(&b).cloned().collect(); |
326 | /// let diff2: HashSet<_> = b.symmetric_difference(&a).cloned().collect(); | |
1a4d82fc JJ |
327 | /// |
328 | /// assert_eq!(diff1, diff2); | |
85aaf69f | 329 | /// assert_eq!(diff1, [1, 4].iter().cloned().collect()); |
1a4d82fc | 330 | /// ``` |
85aaf69f | 331 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
332 | pub fn symmetric_difference<'a>(&'a self, other: &'a HashSet<T, S>) |
333 | -> SymmetricDifference<'a, T, S> { | |
334 | SymmetricDifference { iter: self.difference(other).chain(other.difference(self)) } | |
335 | } | |
336 | ||
337 | /// Visit the values representing the intersection. | |
338 | /// | |
c34b1796 | 339 | /// # Examples |
1a4d82fc JJ |
340 | /// |
341 | /// ``` | |
342 | /// use std::collections::HashSet; | |
85aaf69f SL |
343 | /// let a: HashSet<_> = [1, 2, 3].iter().cloned().collect(); |
344 | /// let b: HashSet<_> = [4, 2, 3, 4].iter().cloned().collect(); | |
1a4d82fc JJ |
345 | /// |
346 | /// // Print 2, 3 in arbitrary order. | |
347 | /// for x in a.intersection(&b) { | |
348 | /// println!("{}", x); | |
349 | /// } | |
350 | /// | |
92a42be0 SL |
351 | /// let intersection: HashSet<_> = a.intersection(&b).cloned().collect(); |
352 | /// assert_eq!(intersection, [2, 3].iter().cloned().collect()); | |
1a4d82fc | 353 | /// ``` |
85aaf69f | 354 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
355 | pub fn intersection<'a>(&'a self, other: &'a HashSet<T, S>) -> Intersection<'a, T, S> { |
356 | Intersection { | |
357 | iter: self.iter(), | |
358 | other: other, | |
359 | } | |
360 | } | |
361 | ||
362 | /// Visit the values representing the union. | |
363 | /// | |
c34b1796 | 364 | /// # Examples |
1a4d82fc JJ |
365 | /// |
366 | /// ``` | |
367 | /// use std::collections::HashSet; | |
85aaf69f SL |
368 | /// let a: HashSet<_> = [1, 2, 3].iter().cloned().collect(); |
369 | /// let b: HashSet<_> = [4, 2, 3, 4].iter().cloned().collect(); | |
1a4d82fc JJ |
370 | /// |
371 | /// // Print 1, 2, 3, 4 in arbitrary order. | |
372 | /// for x in a.union(&b) { | |
373 | /// println!("{}", x); | |
374 | /// } | |
375 | /// | |
92a42be0 SL |
376 | /// let union: HashSet<_> = a.union(&b).cloned().collect(); |
377 | /// assert_eq!(union, [1, 2, 3, 4].iter().cloned().collect()); | |
1a4d82fc | 378 | /// ``` |
85aaf69f | 379 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
380 | pub fn union<'a>(&'a self, other: &'a HashSet<T, S>) -> Union<'a, T, S> { |
381 | Union { iter: self.iter().chain(other.difference(self)) } | |
382 | } | |
383 | ||
9346a6ac | 384 | /// Returns the number of elements in the set. |
1a4d82fc | 385 | /// |
c34b1796 | 386 | /// # Examples |
1a4d82fc JJ |
387 | /// |
388 | /// ``` | |
389 | /// use std::collections::HashSet; | |
390 | /// | |
391 | /// let mut v = HashSet::new(); | |
392 | /// assert_eq!(v.len(), 0); | |
85aaf69f | 393 | /// v.insert(1); |
1a4d82fc JJ |
394 | /// assert_eq!(v.len(), 1); |
395 | /// ``` | |
85aaf69f SL |
396 | #[stable(feature = "rust1", since = "1.0.0")] |
397 | pub fn len(&self) -> usize { self.map.len() } | |
1a4d82fc | 398 | |
9346a6ac | 399 | /// Returns true if the set contains no elements. |
1a4d82fc | 400 | /// |
c34b1796 | 401 | /// # Examples |
1a4d82fc JJ |
402 | /// |
403 | /// ``` | |
404 | /// use std::collections::HashSet; | |
405 | /// | |
406 | /// let mut v = HashSet::new(); | |
407 | /// assert!(v.is_empty()); | |
85aaf69f | 408 | /// v.insert(1); |
1a4d82fc JJ |
409 | /// assert!(!v.is_empty()); |
410 | /// ``` | |
85aaf69f | 411 | #[stable(feature = "rust1", since = "1.0.0")] |
9346a6ac | 412 | pub fn is_empty(&self) -> bool { self.map.is_empty() } |
1a4d82fc JJ |
413 | |
414 | /// Clears the set, returning all elements in an iterator. | |
415 | #[inline] | |
92a42be0 | 416 | #[stable(feature = "drain", since = "1.6.0")] |
1a4d82fc JJ |
417 | pub fn drain(&mut self) -> Drain<T> { |
418 | fn first<A, B>((a, _): (A, B)) -> A { a } | |
419 | let first: fn((T, ())) -> T = first; // coerce to fn pointer | |
420 | ||
421 | Drain { iter: self.map.drain().map(first) } | |
422 | } | |
423 | ||
424 | /// Clears the set, removing all values. | |
425 | /// | |
c34b1796 | 426 | /// # Examples |
1a4d82fc JJ |
427 | /// |
428 | /// ``` | |
429 | /// use std::collections::HashSet; | |
430 | /// | |
431 | /// let mut v = HashSet::new(); | |
85aaf69f | 432 | /// v.insert(1); |
1a4d82fc JJ |
433 | /// v.clear(); |
434 | /// assert!(v.is_empty()); | |
435 | /// ``` | |
85aaf69f | 436 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
437 | pub fn clear(&mut self) { self.map.clear() } |
438 | ||
439 | /// Returns `true` if the set contains a value. | |
440 | /// | |
441 | /// The value may be any borrowed form of the set's value type, but | |
442 | /// `Hash` and `Eq` on the borrowed form *must* match those for | |
443 | /// the value type. | |
444 | /// | |
c34b1796 | 445 | /// # Examples |
1a4d82fc JJ |
446 | /// |
447 | /// ``` | |
448 | /// use std::collections::HashSet; | |
449 | /// | |
85aaf69f | 450 | /// let set: HashSet<_> = [1, 2, 3].iter().cloned().collect(); |
1a4d82fc JJ |
451 | /// assert_eq!(set.contains(&1), true); |
452 | /// assert_eq!(set.contains(&4), false); | |
453 | /// ``` | |
85aaf69f | 454 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 455 | pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool |
85aaf69f | 456 | where T: Borrow<Q>, Q: Hash + Eq |
1a4d82fc JJ |
457 | { |
458 | self.map.contains_key(value) | |
459 | } | |
460 | ||
e9174d1e SL |
461 | /// Returns a reference to the value in the set, if any, that is equal to the given value. |
462 | /// | |
463 | /// The value may be any borrowed form of the set's value type, but | |
464 | /// `Hash` and `Eq` on the borrowed form *must* match those for | |
465 | /// the value type. | |
466 | #[unstable(feature = "set_recovery", issue = "28050")] | |
467 | pub fn get<Q: ?Sized>(&self, value: &Q) -> Option<&T> | |
468 | where T: Borrow<Q>, Q: Hash + Eq | |
469 | { | |
470 | Recover::get(&self.map, value) | |
471 | } | |
472 | ||
1a4d82fc JJ |
473 | /// Returns `true` if the set has no elements in common with `other`. |
474 | /// This is equivalent to checking for an empty intersection. | |
475 | /// | |
c34b1796 | 476 | /// # Examples |
1a4d82fc JJ |
477 | /// |
478 | /// ``` | |
479 | /// use std::collections::HashSet; | |
480 | /// | |
85aaf69f SL |
481 | /// let a: HashSet<_> = [1, 2, 3].iter().cloned().collect(); |
482 | /// let mut b = HashSet::new(); | |
1a4d82fc JJ |
483 | /// |
484 | /// assert_eq!(a.is_disjoint(&b), true); | |
485 | /// b.insert(4); | |
486 | /// assert_eq!(a.is_disjoint(&b), true); | |
487 | /// b.insert(1); | |
488 | /// assert_eq!(a.is_disjoint(&b), false); | |
489 | /// ``` | |
85aaf69f | 490 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
491 | pub fn is_disjoint(&self, other: &HashSet<T, S>) -> bool { |
492 | self.iter().all(|v| !other.contains(v)) | |
493 | } | |
494 | ||
495 | /// Returns `true` if the set is a subset of another. | |
496 | /// | |
c34b1796 | 497 | /// # Examples |
1a4d82fc JJ |
498 | /// |
499 | /// ``` | |
500 | /// use std::collections::HashSet; | |
501 | /// | |
85aaf69f SL |
502 | /// let sup: HashSet<_> = [1, 2, 3].iter().cloned().collect(); |
503 | /// let mut set = HashSet::new(); | |
1a4d82fc JJ |
504 | /// |
505 | /// assert_eq!(set.is_subset(&sup), true); | |
506 | /// set.insert(2); | |
507 | /// assert_eq!(set.is_subset(&sup), true); | |
508 | /// set.insert(4); | |
509 | /// assert_eq!(set.is_subset(&sup), false); | |
510 | /// ``` | |
85aaf69f | 511 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
512 | pub fn is_subset(&self, other: &HashSet<T, S>) -> bool { |
513 | self.iter().all(|v| other.contains(v)) | |
514 | } | |
515 | ||
516 | /// Returns `true` if the set is a superset of another. | |
517 | /// | |
c34b1796 | 518 | /// # Examples |
1a4d82fc JJ |
519 | /// |
520 | /// ``` | |
521 | /// use std::collections::HashSet; | |
522 | /// | |
85aaf69f SL |
523 | /// let sub: HashSet<_> = [1, 2].iter().cloned().collect(); |
524 | /// let mut set = HashSet::new(); | |
1a4d82fc JJ |
525 | /// |
526 | /// assert_eq!(set.is_superset(&sub), false); | |
527 | /// | |
528 | /// set.insert(0); | |
529 | /// set.insert(1); | |
530 | /// assert_eq!(set.is_superset(&sub), false); | |
531 | /// | |
532 | /// set.insert(2); | |
533 | /// assert_eq!(set.is_superset(&sub), true); | |
534 | /// ``` | |
535 | #[inline] | |
85aaf69f | 536 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
537 | pub fn is_superset(&self, other: &HashSet<T, S>) -> bool { |
538 | other.is_subset(self) | |
539 | } | |
540 | ||
b039eaaf SL |
541 | /// Adds a value to the set. |
542 | /// | |
543 | /// If the set did not have a value present, `true` is returned. | |
544 | /// | |
92a42be0 | 545 | /// If the set did have this key present, `false` is returned. |
1a4d82fc | 546 | /// |
c34b1796 | 547 | /// # Examples |
1a4d82fc JJ |
548 | /// |
549 | /// ``` | |
550 | /// use std::collections::HashSet; | |
551 | /// | |
552 | /// let mut set = HashSet::new(); | |
553 | /// | |
85aaf69f | 554 | /// assert_eq!(set.insert(2), true); |
1a4d82fc JJ |
555 | /// assert_eq!(set.insert(2), false); |
556 | /// assert_eq!(set.len(), 1); | |
557 | /// ``` | |
85aaf69f | 558 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
559 | pub fn insert(&mut self, value: T) -> bool { self.map.insert(value, ()).is_none() } |
560 | ||
e9174d1e SL |
561 | /// Adds a value to the set, replacing the existing value, if any, that is equal to the given |
562 | /// one. Returns the replaced value. | |
563 | #[unstable(feature = "set_recovery", issue = "28050")] | |
564 | pub fn replace(&mut self, value: T) -> Option<T> { | |
565 | Recover::replace(&mut self.map, value) | |
566 | } | |
567 | ||
1a4d82fc JJ |
568 | /// Removes a value from the set. Returns `true` if the value was |
569 | /// present in the set. | |
570 | /// | |
571 | /// The value may be any borrowed form of the set's value type, but | |
572 | /// `Hash` and `Eq` on the borrowed form *must* match those for | |
573 | /// the value type. | |
574 | /// | |
c34b1796 | 575 | /// # Examples |
1a4d82fc JJ |
576 | /// |
577 | /// ``` | |
578 | /// use std::collections::HashSet; | |
579 | /// | |
580 | /// let mut set = HashSet::new(); | |
581 | /// | |
85aaf69f | 582 | /// set.insert(2); |
1a4d82fc JJ |
583 | /// assert_eq!(set.remove(&2), true); |
584 | /// assert_eq!(set.remove(&2), false); | |
585 | /// ``` | |
85aaf69f | 586 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 587 | pub fn remove<Q: ?Sized>(&mut self, value: &Q) -> bool |
85aaf69f | 588 | where T: Borrow<Q>, Q: Hash + Eq |
1a4d82fc JJ |
589 | { |
590 | self.map.remove(value).is_some() | |
591 | } | |
e9174d1e SL |
592 | |
593 | /// Removes and returns the value in the set, if any, that is equal to the given one. | |
594 | /// | |
595 | /// The value may be any borrowed form of the set's value type, but | |
596 | /// `Hash` and `Eq` on the borrowed form *must* match those for | |
597 | /// the value type. | |
598 | #[unstable(feature = "set_recovery", issue = "28050")] | |
599 | pub fn take<Q: ?Sized>(&mut self, value: &Q) -> Option<T> | |
600 | where T: Borrow<Q>, Q: Hash + Eq | |
601 | { | |
602 | Recover::take(&mut self.map, value) | |
603 | } | |
1a4d82fc JJ |
604 | } |
605 | ||
85aaf69f SL |
606 | #[stable(feature = "rust1", since = "1.0.0")] |
607 | impl<T, S> PartialEq for HashSet<T, S> | |
608 | where T: Eq + Hash, S: HashState | |
1a4d82fc JJ |
609 | { |
610 | fn eq(&self, other: &HashSet<T, S>) -> bool { | |
611 | if self.len() != other.len() { return false; } | |
612 | ||
613 | self.iter().all(|key| other.contains(key)) | |
614 | } | |
615 | } | |
616 | ||
85aaf69f SL |
617 | #[stable(feature = "rust1", since = "1.0.0")] |
618 | impl<T, S> Eq for HashSet<T, S> | |
619 | where T: Eq + Hash, S: HashState | |
1a4d82fc JJ |
620 | {} |
621 | ||
85aaf69f SL |
622 | #[stable(feature = "rust1", since = "1.0.0")] |
623 | impl<T, S> fmt::Debug for HashSet<T, S> | |
624 | where T: Eq + Hash + fmt::Debug, | |
625 | S: HashState | |
1a4d82fc JJ |
626 | { |
627 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { | |
62682a34 | 628 | f.debug_set().entries(self.iter()).finish() |
1a4d82fc JJ |
629 | } |
630 | } | |
631 | ||
85aaf69f SL |
632 | #[stable(feature = "rust1", since = "1.0.0")] |
633 | impl<T, S> FromIterator<T> for HashSet<T, S> | |
634 | where T: Eq + Hash, | |
635 | S: HashState + Default, | |
1a4d82fc | 636 | { |
85aaf69f SL |
637 | fn from_iter<I: IntoIterator<Item=T>>(iterable: I) -> HashSet<T, S> { |
638 | let iter = iterable.into_iter(); | |
1a4d82fc JJ |
639 | let lower = iter.size_hint().0; |
640 | let mut set = HashSet::with_capacity_and_hash_state(lower, Default::default()); | |
641 | set.extend(iter); | |
642 | set | |
643 | } | |
644 | } | |
645 | ||
85aaf69f SL |
646 | #[stable(feature = "rust1", since = "1.0.0")] |
647 | impl<T, S> Extend<T> for HashSet<T, S> | |
648 | where T: Eq + Hash, | |
649 | S: HashState, | |
1a4d82fc | 650 | { |
85aaf69f | 651 | fn extend<I: IntoIterator<Item=T>>(&mut self, iter: I) { |
1a4d82fc JJ |
652 | for k in iter { |
653 | self.insert(k); | |
654 | } | |
655 | } | |
656 | } | |
657 | ||
e9174d1e SL |
658 | #[stable(feature = "hash_extend_copy", since = "1.4.0")] |
659 | impl<'a, T, S> Extend<&'a T> for HashSet<T, S> | |
660 | where T: 'a + Eq + Hash + Copy, | |
661 | S: HashState, | |
662 | { | |
663 | fn extend<I: IntoIterator<Item=&'a T>>(&mut self, iter: I) { | |
664 | self.extend(iter.into_iter().cloned()); | |
665 | } | |
666 | } | |
667 | ||
85aaf69f SL |
668 | #[stable(feature = "rust1", since = "1.0.0")] |
669 | impl<T, S> Default for HashSet<T, S> | |
670 | where T: Eq + Hash, | |
671 | S: HashState + Default, | |
1a4d82fc | 672 | { |
1a4d82fc JJ |
673 | fn default() -> HashSet<T, S> { |
674 | HashSet::with_hash_state(Default::default()) | |
675 | } | |
676 | } | |
677 | ||
85aaf69f SL |
678 | #[stable(feature = "rust1", since = "1.0.0")] |
679 | impl<'a, 'b, T, S> BitOr<&'b HashSet<T, S>> for &'a HashSet<T, S> | |
680 | where T: Eq + Hash + Clone, | |
681 | S: HashState + Default, | |
1a4d82fc JJ |
682 | { |
683 | type Output = HashSet<T, S>; | |
684 | ||
685 | /// Returns the union of `self` and `rhs` as a new `HashSet<T, S>`. | |
686 | /// | |
687 | /// # Examples | |
688 | /// | |
689 | /// ``` | |
690 | /// use std::collections::HashSet; | |
691 | /// | |
85aaf69f SL |
692 | /// let a: HashSet<_> = vec![1, 2, 3].into_iter().collect(); |
693 | /// let b: HashSet<_> = vec![3, 4, 5].into_iter().collect(); | |
1a4d82fc | 694 | /// |
85aaf69f | 695 | /// let set = &a | &b; |
1a4d82fc JJ |
696 | /// |
697 | /// let mut i = 0; | |
698 | /// let expected = [1, 2, 3, 4, 5]; | |
62682a34 | 699 | /// for x in &set { |
1a4d82fc JJ |
700 | /// assert!(expected.contains(x)); |
701 | /// i += 1; | |
702 | /// } | |
703 | /// assert_eq!(i, expected.len()); | |
704 | /// ``` | |
705 | fn bitor(self, rhs: &HashSet<T, S>) -> HashSet<T, S> { | |
706 | self.union(rhs).cloned().collect() | |
707 | } | |
708 | } | |
709 | ||
85aaf69f SL |
710 | #[stable(feature = "rust1", since = "1.0.0")] |
711 | impl<'a, 'b, T, S> BitAnd<&'b HashSet<T, S>> for &'a HashSet<T, S> | |
712 | where T: Eq + Hash + Clone, | |
713 | S: HashState + Default, | |
1a4d82fc JJ |
714 | { |
715 | type Output = HashSet<T, S>; | |
716 | ||
717 | /// Returns the intersection of `self` and `rhs` as a new `HashSet<T, S>`. | |
718 | /// | |
719 | /// # Examples | |
720 | /// | |
721 | /// ``` | |
722 | /// use std::collections::HashSet; | |
723 | /// | |
85aaf69f SL |
724 | /// let a: HashSet<_> = vec![1, 2, 3].into_iter().collect(); |
725 | /// let b: HashSet<_> = vec![2, 3, 4].into_iter().collect(); | |
1a4d82fc | 726 | /// |
85aaf69f | 727 | /// let set = &a & &b; |
1a4d82fc JJ |
728 | /// |
729 | /// let mut i = 0; | |
730 | /// let expected = [2, 3]; | |
62682a34 | 731 | /// for x in &set { |
1a4d82fc JJ |
732 | /// assert!(expected.contains(x)); |
733 | /// i += 1; | |
734 | /// } | |
735 | /// assert_eq!(i, expected.len()); | |
736 | /// ``` | |
737 | fn bitand(self, rhs: &HashSet<T, S>) -> HashSet<T, S> { | |
738 | self.intersection(rhs).cloned().collect() | |
739 | } | |
740 | } | |
741 | ||
85aaf69f SL |
742 | #[stable(feature = "rust1", since = "1.0.0")] |
743 | impl<'a, 'b, T, S> BitXor<&'b HashSet<T, S>> for &'a HashSet<T, S> | |
744 | where T: Eq + Hash + Clone, | |
745 | S: HashState + Default, | |
1a4d82fc JJ |
746 | { |
747 | type Output = HashSet<T, S>; | |
748 | ||
749 | /// Returns the symmetric difference of `self` and `rhs` as a new `HashSet<T, S>`. | |
750 | /// | |
751 | /// # Examples | |
752 | /// | |
753 | /// ``` | |
754 | /// use std::collections::HashSet; | |
755 | /// | |
85aaf69f SL |
756 | /// let a: HashSet<_> = vec![1, 2, 3].into_iter().collect(); |
757 | /// let b: HashSet<_> = vec![3, 4, 5].into_iter().collect(); | |
1a4d82fc | 758 | /// |
85aaf69f | 759 | /// let set = &a ^ &b; |
1a4d82fc JJ |
760 | /// |
761 | /// let mut i = 0; | |
762 | /// let expected = [1, 2, 4, 5]; | |
62682a34 | 763 | /// for x in &set { |
1a4d82fc JJ |
764 | /// assert!(expected.contains(x)); |
765 | /// i += 1; | |
766 | /// } | |
767 | /// assert_eq!(i, expected.len()); | |
768 | /// ``` | |
769 | fn bitxor(self, rhs: &HashSet<T, S>) -> HashSet<T, S> { | |
770 | self.symmetric_difference(rhs).cloned().collect() | |
771 | } | |
772 | } | |
773 | ||
85aaf69f SL |
774 | #[stable(feature = "rust1", since = "1.0.0")] |
775 | impl<'a, 'b, T, S> Sub<&'b HashSet<T, S>> for &'a HashSet<T, S> | |
776 | where T: Eq + Hash + Clone, | |
777 | S: HashState + Default, | |
1a4d82fc JJ |
778 | { |
779 | type Output = HashSet<T, S>; | |
780 | ||
781 | /// Returns the difference of `self` and `rhs` as a new `HashSet<T, S>`. | |
782 | /// | |
783 | /// # Examples | |
784 | /// | |
785 | /// ``` | |
786 | /// use std::collections::HashSet; | |
787 | /// | |
85aaf69f SL |
788 | /// let a: HashSet<_> = vec![1, 2, 3].into_iter().collect(); |
789 | /// let b: HashSet<_> = vec![3, 4, 5].into_iter().collect(); | |
1a4d82fc | 790 | /// |
85aaf69f | 791 | /// let set = &a - &b; |
1a4d82fc JJ |
792 | /// |
793 | /// let mut i = 0; | |
794 | /// let expected = [1, 2]; | |
62682a34 | 795 | /// for x in &set { |
1a4d82fc JJ |
796 | /// assert!(expected.contains(x)); |
797 | /// i += 1; | |
798 | /// } | |
799 | /// assert_eq!(i, expected.len()); | |
800 | /// ``` | |
801 | fn sub(self, rhs: &HashSet<T, S>) -> HashSet<T, S> { | |
802 | self.difference(rhs).cloned().collect() | |
803 | } | |
804 | } | |
805 | ||
806 | /// HashSet iterator | |
85aaf69f | 807 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
808 | pub struct Iter<'a, K: 'a> { |
809 | iter: Keys<'a, K, ()> | |
810 | } | |
811 | ||
812 | /// HashSet move iterator | |
85aaf69f | 813 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 814 | pub struct IntoIter<K> { |
85aaf69f | 815 | iter: Map<map::IntoIter<K, ()>, fn((K, ())) -> K> |
1a4d82fc JJ |
816 | } |
817 | ||
818 | /// HashSet drain iterator | |
85aaf69f | 819 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 820 | pub struct Drain<'a, K: 'a> { |
85aaf69f | 821 | iter: Map<map::Drain<'a, K, ()>, fn((K, ())) -> K>, |
1a4d82fc JJ |
822 | } |
823 | ||
824 | /// Intersection iterator | |
85aaf69f | 825 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
826 | pub struct Intersection<'a, T: 'a, S: 'a> { |
827 | // iterator of the first set | |
828 | iter: Iter<'a, T>, | |
829 | // the second set | |
830 | other: &'a HashSet<T, S>, | |
831 | } | |
832 | ||
833 | /// Difference iterator | |
85aaf69f | 834 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
835 | pub struct Difference<'a, T: 'a, S: 'a> { |
836 | // iterator of the first set | |
837 | iter: Iter<'a, T>, | |
838 | // the second set | |
839 | other: &'a HashSet<T, S>, | |
840 | } | |
841 | ||
842 | /// Symmetric difference iterator. | |
85aaf69f | 843 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
844 | pub struct SymmetricDifference<'a, T: 'a, S: 'a> { |
845 | iter: Chain<Difference<'a, T, S>, Difference<'a, T, S>> | |
846 | } | |
847 | ||
848 | /// Set union iterator. | |
85aaf69f | 849 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
850 | pub struct Union<'a, T: 'a, S: 'a> { |
851 | iter: Chain<Iter<'a, T>, Difference<'a, T, S>> | |
852 | } | |
853 | ||
85aaf69f SL |
854 | #[stable(feature = "rust1", since = "1.0.0")] |
855 | impl<'a, T, S> IntoIterator for &'a HashSet<T, S> | |
856 | where T: Eq + Hash, S: HashState | |
857 | { | |
858 | type Item = &'a T; | |
859 | type IntoIter = Iter<'a, T>; | |
860 | ||
861 | fn into_iter(self) -> Iter<'a, T> { | |
862 | self.iter() | |
863 | } | |
864 | } | |
865 | ||
866 | #[stable(feature = "rust1", since = "1.0.0")] | |
867 | impl<T, S> IntoIterator for HashSet<T, S> | |
868 | where T: Eq + Hash, | |
869 | S: HashState | |
870 | { | |
871 | type Item = T; | |
872 | type IntoIter = IntoIter<T>; | |
873 | ||
9346a6ac AL |
874 | /// Creates a consuming iterator, that is, one that moves each value out |
875 | /// of the set in arbitrary order. The set cannot be used after calling | |
876 | /// this. | |
877 | /// | |
878 | /// # Examples | |
879 | /// | |
880 | /// ``` | |
881 | /// use std::collections::HashSet; | |
882 | /// let mut set = HashSet::new(); | |
883 | /// set.insert("a".to_string()); | |
884 | /// set.insert("b".to_string()); | |
885 | /// | |
886 | /// // Not possible to collect to a Vec<String> with a regular `.iter()`. | |
887 | /// let v: Vec<String> = set.into_iter().collect(); | |
888 | /// | |
889 | /// // Will print in an arbitrary order. | |
62682a34 | 890 | /// for x in &v { |
9346a6ac AL |
891 | /// println!("{}", x); |
892 | /// } | |
893 | /// ``` | |
85aaf69f | 894 | fn into_iter(self) -> IntoIter<T> { |
9346a6ac AL |
895 | fn first<A, B>((a, _): (A, B)) -> A { a } |
896 | let first: fn((T, ())) -> T = first; | |
897 | ||
898 | IntoIter { iter: self.map.into_iter().map(first) } | |
85aaf69f SL |
899 | } |
900 | } | |
901 | ||
92a42be0 | 902 | #[stable(feature = "rust1", since = "1.0.0")] |
c34b1796 AL |
903 | impl<'a, K> Clone for Iter<'a, K> { |
904 | fn clone(&self) -> Iter<'a, K> { Iter { iter: self.iter.clone() } } | |
905 | } | |
85aaf69f | 906 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
907 | impl<'a, K> Iterator for Iter<'a, K> { |
908 | type Item = &'a K; | |
909 | ||
910 | fn next(&mut self) -> Option<&'a K> { self.iter.next() } | |
85aaf69f SL |
911 | fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() } |
912 | } | |
913 | #[stable(feature = "rust1", since = "1.0.0")] | |
914 | impl<'a, K> ExactSizeIterator for Iter<'a, K> { | |
915 | fn len(&self) -> usize { self.iter.len() } | |
1a4d82fc JJ |
916 | } |
917 | ||
85aaf69f | 918 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
919 | impl<K> Iterator for IntoIter<K> { |
920 | type Item = K; | |
921 | ||
922 | fn next(&mut self) -> Option<K> { self.iter.next() } | |
85aaf69f SL |
923 | fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() } |
924 | } | |
925 | #[stable(feature = "rust1", since = "1.0.0")] | |
926 | impl<K> ExactSizeIterator for IntoIter<K> { | |
927 | fn len(&self) -> usize { self.iter.len() } | |
1a4d82fc JJ |
928 | } |
929 | ||
85aaf69f SL |
930 | #[stable(feature = "rust1", since = "1.0.0")] |
931 | impl<'a, K> Iterator for Drain<'a, K> { | |
1a4d82fc JJ |
932 | type Item = K; |
933 | ||
934 | fn next(&mut self) -> Option<K> { self.iter.next() } | |
85aaf69f SL |
935 | fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() } |
936 | } | |
937 | #[stable(feature = "rust1", since = "1.0.0")] | |
938 | impl<'a, K> ExactSizeIterator for Drain<'a, K> { | |
939 | fn len(&self) -> usize { self.iter.len() } | |
1a4d82fc JJ |
940 | } |
941 | ||
92a42be0 | 942 | #[stable(feature = "rust1", since = "1.0.0")] |
c34b1796 AL |
943 | impl<'a, T, S> Clone for Intersection<'a, T, S> { |
944 | fn clone(&self) -> Intersection<'a, T, S> { | |
945 | Intersection { iter: self.iter.clone(), ..*self } | |
946 | } | |
947 | } | |
948 | ||
85aaf69f SL |
949 | #[stable(feature = "rust1", since = "1.0.0")] |
950 | impl<'a, T, S> Iterator for Intersection<'a, T, S> | |
951 | where T: Eq + Hash, S: HashState | |
1a4d82fc JJ |
952 | { |
953 | type Item = &'a T; | |
954 | ||
955 | fn next(&mut self) -> Option<&'a T> { | |
956 | loop { | |
957 | match self.iter.next() { | |
958 | None => return None, | |
959 | Some(elt) => if self.other.contains(elt) { | |
960 | return Some(elt) | |
961 | }, | |
962 | } | |
963 | } | |
964 | } | |
965 | ||
85aaf69f | 966 | fn size_hint(&self) -> (usize, Option<usize>) { |
1a4d82fc JJ |
967 | let (_, upper) = self.iter.size_hint(); |
968 | (0, upper) | |
969 | } | |
970 | } | |
971 | ||
92a42be0 | 972 | #[stable(feature = "rust1", since = "1.0.0")] |
c34b1796 AL |
973 | impl<'a, T, S> Clone for Difference<'a, T, S> { |
974 | fn clone(&self) -> Difference<'a, T, S> { | |
975 | Difference { iter: self.iter.clone(), ..*self } | |
976 | } | |
977 | } | |
978 | ||
85aaf69f SL |
979 | #[stable(feature = "rust1", since = "1.0.0")] |
980 | impl<'a, T, S> Iterator for Difference<'a, T, S> | |
981 | where T: Eq + Hash, S: HashState | |
1a4d82fc JJ |
982 | { |
983 | type Item = &'a T; | |
984 | ||
985 | fn next(&mut self) -> Option<&'a T> { | |
986 | loop { | |
987 | match self.iter.next() { | |
988 | None => return None, | |
989 | Some(elt) => if !self.other.contains(elt) { | |
990 | return Some(elt) | |
991 | }, | |
992 | } | |
993 | } | |
994 | } | |
995 | ||
85aaf69f | 996 | fn size_hint(&self) -> (usize, Option<usize>) { |
1a4d82fc JJ |
997 | let (_, upper) = self.iter.size_hint(); |
998 | (0, upper) | |
999 | } | |
1000 | } | |
1001 | ||
92a42be0 | 1002 | #[stable(feature = "rust1", since = "1.0.0")] |
c34b1796 AL |
1003 | impl<'a, T, S> Clone for SymmetricDifference<'a, T, S> { |
1004 | fn clone(&self) -> SymmetricDifference<'a, T, S> { | |
1005 | SymmetricDifference { iter: self.iter.clone() } | |
1006 | } | |
1007 | } | |
1008 | ||
85aaf69f SL |
1009 | #[stable(feature = "rust1", since = "1.0.0")] |
1010 | impl<'a, T, S> Iterator for SymmetricDifference<'a, T, S> | |
1011 | where T: Eq + Hash, S: HashState | |
1a4d82fc JJ |
1012 | { |
1013 | type Item = &'a T; | |
1014 | ||
1015 | fn next(&mut self) -> Option<&'a T> { self.iter.next() } | |
85aaf69f | 1016 | fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() } |
1a4d82fc JJ |
1017 | } |
1018 | ||
92a42be0 | 1019 | #[stable(feature = "rust1", since = "1.0.0")] |
c34b1796 AL |
1020 | impl<'a, T, S> Clone for Union<'a, T, S> { |
1021 | fn clone(&self) -> Union<'a, T, S> { Union { iter: self.iter.clone() } } | |
1022 | } | |
1023 | ||
85aaf69f SL |
1024 | #[stable(feature = "rust1", since = "1.0.0")] |
1025 | impl<'a, T, S> Iterator for Union<'a, T, S> | |
1026 | where T: Eq + Hash, S: HashState | |
1a4d82fc JJ |
1027 | { |
1028 | type Item = &'a T; | |
1029 | ||
1030 | fn next(&mut self) -> Option<&'a T> { self.iter.next() } | |
85aaf69f | 1031 | fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() } |
1a4d82fc JJ |
1032 | } |
1033 | ||
1034 | #[cfg(test)] | |
1035 | mod test_set { | |
1036 | use prelude::v1::*; | |
1037 | ||
1038 | use super::HashSet; | |
1039 | ||
1040 | #[test] | |
1041 | fn test_disjoint() { | |
1042 | let mut xs = HashSet::new(); | |
1043 | let mut ys = HashSet::new(); | |
1044 | assert!(xs.is_disjoint(&ys)); | |
1045 | assert!(ys.is_disjoint(&xs)); | |
85aaf69f SL |
1046 | assert!(xs.insert(5)); |
1047 | assert!(ys.insert(11)); | |
1a4d82fc JJ |
1048 | assert!(xs.is_disjoint(&ys)); |
1049 | assert!(ys.is_disjoint(&xs)); | |
1050 | assert!(xs.insert(7)); | |
1051 | assert!(xs.insert(19)); | |
1052 | assert!(xs.insert(4)); | |
1053 | assert!(ys.insert(2)); | |
1054 | assert!(ys.insert(-11)); | |
1055 | assert!(xs.is_disjoint(&ys)); | |
1056 | assert!(ys.is_disjoint(&xs)); | |
1057 | assert!(ys.insert(7)); | |
1058 | assert!(!xs.is_disjoint(&ys)); | |
1059 | assert!(!ys.is_disjoint(&xs)); | |
1060 | } | |
1061 | ||
1062 | #[test] | |
1063 | fn test_subset_and_superset() { | |
1064 | let mut a = HashSet::new(); | |
85aaf69f | 1065 | assert!(a.insert(0)); |
1a4d82fc JJ |
1066 | assert!(a.insert(5)); |
1067 | assert!(a.insert(11)); | |
1068 | assert!(a.insert(7)); | |
1069 | ||
1070 | let mut b = HashSet::new(); | |
85aaf69f | 1071 | assert!(b.insert(0)); |
1a4d82fc JJ |
1072 | assert!(b.insert(7)); |
1073 | assert!(b.insert(19)); | |
1074 | assert!(b.insert(250)); | |
1075 | assert!(b.insert(11)); | |
1076 | assert!(b.insert(200)); | |
1077 | ||
1078 | assert!(!a.is_subset(&b)); | |
1079 | assert!(!a.is_superset(&b)); | |
1080 | assert!(!b.is_subset(&a)); | |
1081 | assert!(!b.is_superset(&a)); | |
1082 | ||
1083 | assert!(b.insert(5)); | |
1084 | ||
1085 | assert!(a.is_subset(&b)); | |
1086 | assert!(!a.is_superset(&b)); | |
1087 | assert!(!b.is_subset(&a)); | |
1088 | assert!(b.is_superset(&a)); | |
1089 | } | |
1090 | ||
1091 | #[test] | |
1092 | fn test_iterate() { | |
1093 | let mut a = HashSet::new(); | |
85aaf69f | 1094 | for i in 0..32 { |
1a4d82fc JJ |
1095 | assert!(a.insert(i)); |
1096 | } | |
1097 | let mut observed: u32 = 0; | |
85aaf69f | 1098 | for k in &a { |
1a4d82fc JJ |
1099 | observed |= 1 << *k; |
1100 | } | |
1101 | assert_eq!(observed, 0xFFFF_FFFF); | |
1102 | } | |
1103 | ||
1104 | #[test] | |
1105 | fn test_intersection() { | |
1106 | let mut a = HashSet::new(); | |
1107 | let mut b = HashSet::new(); | |
1108 | ||
85aaf69f | 1109 | assert!(a.insert(11)); |
1a4d82fc JJ |
1110 | assert!(a.insert(1)); |
1111 | assert!(a.insert(3)); | |
1112 | assert!(a.insert(77)); | |
1113 | assert!(a.insert(103)); | |
1114 | assert!(a.insert(5)); | |
1115 | assert!(a.insert(-5)); | |
1116 | ||
85aaf69f | 1117 | assert!(b.insert(2)); |
1a4d82fc JJ |
1118 | assert!(b.insert(11)); |
1119 | assert!(b.insert(77)); | |
1120 | assert!(b.insert(-9)); | |
1121 | assert!(b.insert(-42)); | |
1122 | assert!(b.insert(5)); | |
1123 | assert!(b.insert(3)); | |
1124 | ||
1125 | let mut i = 0; | |
1126 | let expected = [3, 5, 11, 77]; | |
1127 | for x in a.intersection(&b) { | |
1128 | assert!(expected.contains(x)); | |
1129 | i += 1 | |
1130 | } | |
1131 | assert_eq!(i, expected.len()); | |
1132 | } | |
1133 | ||
1134 | #[test] | |
1135 | fn test_difference() { | |
1136 | let mut a = HashSet::new(); | |
1137 | let mut b = HashSet::new(); | |
1138 | ||
85aaf69f | 1139 | assert!(a.insert(1)); |
1a4d82fc JJ |
1140 | assert!(a.insert(3)); |
1141 | assert!(a.insert(5)); | |
1142 | assert!(a.insert(9)); | |
1143 | assert!(a.insert(11)); | |
1144 | ||
85aaf69f | 1145 | assert!(b.insert(3)); |
1a4d82fc JJ |
1146 | assert!(b.insert(9)); |
1147 | ||
1148 | let mut i = 0; | |
1149 | let expected = [1, 5, 11]; | |
1150 | for x in a.difference(&b) { | |
1151 | assert!(expected.contains(x)); | |
1152 | i += 1 | |
1153 | } | |
1154 | assert_eq!(i, expected.len()); | |
1155 | } | |
1156 | ||
1157 | #[test] | |
1158 | fn test_symmetric_difference() { | |
1159 | let mut a = HashSet::new(); | |
1160 | let mut b = HashSet::new(); | |
1161 | ||
85aaf69f | 1162 | assert!(a.insert(1)); |
1a4d82fc JJ |
1163 | assert!(a.insert(3)); |
1164 | assert!(a.insert(5)); | |
1165 | assert!(a.insert(9)); | |
1166 | assert!(a.insert(11)); | |
1167 | ||
85aaf69f | 1168 | assert!(b.insert(-2)); |
1a4d82fc JJ |
1169 | assert!(b.insert(3)); |
1170 | assert!(b.insert(9)); | |
1171 | assert!(b.insert(14)); | |
1172 | assert!(b.insert(22)); | |
1173 | ||
1174 | let mut i = 0; | |
1175 | let expected = [-2, 1, 5, 11, 14, 22]; | |
1176 | for x in a.symmetric_difference(&b) { | |
1177 | assert!(expected.contains(x)); | |
1178 | i += 1 | |
1179 | } | |
1180 | assert_eq!(i, expected.len()); | |
1181 | } | |
1182 | ||
1183 | #[test] | |
1184 | fn test_union() { | |
1185 | let mut a = HashSet::new(); | |
1186 | let mut b = HashSet::new(); | |
1187 | ||
85aaf69f | 1188 | assert!(a.insert(1)); |
1a4d82fc JJ |
1189 | assert!(a.insert(3)); |
1190 | assert!(a.insert(5)); | |
1191 | assert!(a.insert(9)); | |
1192 | assert!(a.insert(11)); | |
1193 | assert!(a.insert(16)); | |
1194 | assert!(a.insert(19)); | |
1195 | assert!(a.insert(24)); | |
1196 | ||
85aaf69f | 1197 | assert!(b.insert(-2)); |
1a4d82fc JJ |
1198 | assert!(b.insert(1)); |
1199 | assert!(b.insert(5)); | |
1200 | assert!(b.insert(9)); | |
1201 | assert!(b.insert(13)); | |
1202 | assert!(b.insert(19)); | |
1203 | ||
1204 | let mut i = 0; | |
1205 | let expected = [-2, 1, 3, 5, 9, 11, 13, 16, 19, 24]; | |
1206 | for x in a.union(&b) { | |
1207 | assert!(expected.contains(x)); | |
1208 | i += 1 | |
1209 | } | |
1210 | assert_eq!(i, expected.len()); | |
1211 | } | |
1212 | ||
1213 | #[test] | |
1214 | fn test_from_iter() { | |
85aaf69f | 1215 | let xs = [1, 2, 3, 4, 5, 6, 7, 8, 9]; |
1a4d82fc | 1216 | |
85aaf69f | 1217 | let set: HashSet<_> = xs.iter().cloned().collect(); |
1a4d82fc | 1218 | |
85aaf69f | 1219 | for x in &xs { |
1a4d82fc JJ |
1220 | assert!(set.contains(x)); |
1221 | } | |
1222 | } | |
1223 | ||
1224 | #[test] | |
1225 | fn test_move_iter() { | |
1226 | let hs = { | |
1227 | let mut hs = HashSet::new(); | |
1228 | ||
1229 | hs.insert('a'); | |
1230 | hs.insert('b'); | |
1231 | ||
1232 | hs | |
1233 | }; | |
1234 | ||
1235 | let v = hs.into_iter().collect::<Vec<char>>(); | |
c34b1796 | 1236 | assert!(v == ['a', 'b'] || v == ['b', 'a']); |
1a4d82fc JJ |
1237 | } |
1238 | ||
1239 | #[test] | |
1240 | fn test_eq() { | |
1241 | // These constants once happened to expose a bug in insert(). | |
1242 | // I'm keeping them around to prevent a regression. | |
1243 | let mut s1 = HashSet::new(); | |
1244 | ||
85aaf69f | 1245 | s1.insert(1); |
1a4d82fc JJ |
1246 | s1.insert(2); |
1247 | s1.insert(3); | |
1248 | ||
1249 | let mut s2 = HashSet::new(); | |
1250 | ||
85aaf69f | 1251 | s2.insert(1); |
1a4d82fc JJ |
1252 | s2.insert(2); |
1253 | ||
1254 | assert!(s1 != s2); | |
1255 | ||
1256 | s2.insert(3); | |
1257 | ||
1258 | assert_eq!(s1, s2); | |
1259 | } | |
1260 | ||
1261 | #[test] | |
1262 | fn test_show() { | |
85aaf69f SL |
1263 | let mut set = HashSet::new(); |
1264 | let empty = HashSet::<i32>::new(); | |
1a4d82fc | 1265 | |
85aaf69f | 1266 | set.insert(1); |
1a4d82fc JJ |
1267 | set.insert(2); |
1268 | ||
1269 | let set_str = format!("{:?}", set); | |
1270 | ||
c34b1796 AL |
1271 | assert!(set_str == "{1, 2}" || set_str == "{2, 1}"); |
1272 | assert_eq!(format!("{:?}", empty), "{}"); | |
1a4d82fc JJ |
1273 | } |
1274 | ||
1275 | #[test] | |
1276 | fn test_trivial_drain() { | |
85aaf69f | 1277 | let mut s = HashSet::<i32>::new(); |
1a4d82fc JJ |
1278 | for _ in s.drain() {} |
1279 | assert!(s.is_empty()); | |
1280 | drop(s); | |
1281 | ||
85aaf69f | 1282 | let mut s = HashSet::<i32>::new(); |
1a4d82fc JJ |
1283 | drop(s.drain()); |
1284 | assert!(s.is_empty()); | |
1285 | } | |
1286 | ||
1287 | #[test] | |
1288 | fn test_drain() { | |
85aaf69f | 1289 | let mut s: HashSet<_> = (1..100).collect(); |
1a4d82fc JJ |
1290 | |
1291 | // try this a bunch of times to make sure we don't screw up internal state. | |
85aaf69f | 1292 | for _ in 0..20 { |
1a4d82fc JJ |
1293 | assert_eq!(s.len(), 99); |
1294 | ||
1295 | { | |
1296 | let mut last_i = 0; | |
1297 | let mut d = s.drain(); | |
1298 | for (i, x) in d.by_ref().take(50).enumerate() { | |
1299 | last_i = i; | |
1300 | assert!(x != 0); | |
1301 | } | |
1302 | assert_eq!(last_i, 49); | |
1303 | } | |
1304 | ||
85aaf69f | 1305 | for _ in &s { panic!("s should be empty!"); } |
1a4d82fc JJ |
1306 | |
1307 | // reset to try again. | |
85aaf69f | 1308 | s.extend(1..100); |
1a4d82fc JJ |
1309 | } |
1310 | } | |
e9174d1e SL |
1311 | |
1312 | #[test] | |
1313 | fn test_replace() { | |
1314 | use hash; | |
1315 | ||
1316 | #[derive(Debug)] | |
1317 | struct Foo(&'static str, i32); | |
1318 | ||
1319 | impl PartialEq for Foo { | |
1320 | fn eq(&self, other: &Self) -> bool { | |
1321 | self.0 == other.0 | |
1322 | } | |
1323 | } | |
1324 | ||
1325 | impl Eq for Foo {} | |
1326 | ||
1327 | impl hash::Hash for Foo { | |
1328 | fn hash<H: hash::Hasher>(&self, h: &mut H) { | |
1329 | self.0.hash(h); | |
1330 | } | |
1331 | } | |
1332 | ||
1333 | let mut s = HashSet::new(); | |
1334 | assert_eq!(s.replace(Foo("a", 1)), None); | |
1335 | assert_eq!(s.len(), 1); | |
1336 | assert_eq!(s.replace(Foo("a", 2)), Some(Foo("a", 1))); | |
1337 | assert_eq!(s.len(), 1); | |
1338 | ||
1339 | let mut it = s.iter(); | |
1340 | assert_eq!(it.next(), Some(&Foo("a", 2))); | |
1341 | assert_eq!(it.next(), None); | |
1342 | } | |
1343 | ||
1344 | #[test] | |
1345 | fn test_extend_ref() { | |
1346 | let mut a = HashSet::new(); | |
1347 | a.insert(1); | |
1348 | ||
1349 | a.extend(&[2, 3, 4]); | |
1350 | ||
1351 | assert_eq!(a.len(), 4); | |
1352 | assert!(a.contains(&1)); | |
1353 | assert!(a.contains(&2)); | |
1354 | assert!(a.contains(&3)); | |
1355 | assert!(a.contains(&4)); | |
1356 | ||
1357 | let mut b = HashSet::new(); | |
1358 | b.insert(5); | |
1359 | b.insert(6); | |
1360 | ||
1361 | a.extend(&b); | |
1362 | ||
1363 | assert_eq!(a.len(), 6); | |
1364 | assert!(a.contains(&1)); | |
1365 | assert!(a.contains(&2)); | |
1366 | assert!(a.contains(&3)); | |
1367 | assert!(a.contains(&4)); | |
1368 | assert!(a.contains(&5)); | |
1369 | assert!(a.contains(&6)); | |
1370 | } | |
1a4d82fc | 1371 | } |