src/libstd/hashmap.rs

   1 // Copyright 2013 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 //! Unordered containers, implemented as hash-tables (`HashSet` and `HashMap` types)
  12 //!
  13 //! The tables use a keyed hash with new random keys generated for each container, so the ordering
  14 //! of a set of keys in a hash table is randomized.
  15 //!
  16 //! # Example
  17 //!
  18 //! ```rust
  19 //! use std::hashmap::HashMap;
  20 //!
  21 //! // type inference lets us omit an explicit type signature (which
  22 //! // would be `HashMap<&str, &str>` in this example).
  23 //! let mut book_reviews = HashMap::new();
  24 //!
  25 //! // review some books.
  26 //! book_reviews.insert("Adventures of Hucklebury Fin",      "My favorite book.");
  27 //! book_reviews.insert("Grimms' Fairy Tales",               "Masterpiece.");
  28 //! book_reviews.insert("Pride and Prejudice",               "Very enjoyable.");
  29 //! book_reviews.insert("The Adventures of Sherlock Holmes", "Eye lyked it alot.");
  30 //!
  31 //! // check for a specific one.
  32 //! if !book_reviews.contains_key(& &"Les Misérables") {
  33 //!     println!("We've got {} reviews, but Les Misérables ain't one.",
  34 //!              book_reviews.len());
  35 //! }
  36 //!
  37 //! // oops, this review has a lot of spelling mistakes, let's delete it.
  38 //! book_reviews.remove(& &"The Adventures of Sherlock Holmes");
  39 //!
  40 //! // look up the values associated with some keys.
  41 //! let to_find = ["Pride and Prejudice", "Alice's Adventure in Wonderland"];
  42 //! for book in to_find.iter() {
  43 //!     match book_reviews.find(book) {
  44 //!         Some(review) => println!("{}: {}", *book, *review),
  45 //!         None => println!("{} is unreviewed.", *book)
  46 //!     }
  47 //! }
  48 //!
  49 //! // iterate over everything.
  50 //! for (book, review) in book_reviews.iter() {
  51 //!     println!("{}: \"{}\"", *book, *review);
  52 //! }
  53 //! ```
  54
  55 use container::{Container, Mutable, Map, MutableMap, Set, MutableSet};
  56 use clone::Clone;
  57 use cmp::{Eq, Equiv};
  58 use default::Default;
  59 use hash::Hash;
  60 use iter;
  61 use iter::{Iterator, FromIterator, Extendable};
  62 use iter::{FilterMap, Chain, Repeat, Zip};
  63 use num;
  64 use option::{None, Option, Some};
  65 use rand::Rng;
  66 use rand;
  67 use uint;
  68 use util::replace;
  69 use vec::{ImmutableVector, MutableVector, OwnedVector};
  70 use vec;
  71
  72 static INITIAL_CAPACITY: uint = 32u; // 2^5
  73
  74 struct Bucket<K,V> {
  75     hash: uint,
  76     key: K,
  77     value: V,
  78 }
  79
  80 /// A hash map implementation which uses linear probing along with the SipHash
  81 /// hash function for internal state. This means that the order of all hash maps
  82 /// is randomized by keying each hash map randomly on creation.
  83 ///
  84 /// It is required that the keys implement the `Eq` and `Hash` traits, although
  85 /// this can frequently be achieved by just implementing the `Eq` and
  86 /// `IterBytes` traits as `Hash` is automatically implemented for types that
  87 /// implement `IterBytes`.
  88 pub struct HashMap<K,V> {
  89     priv k0: u64,
  90     priv k1: u64,
  91     priv resize_at: uint,
  92     priv size: uint,
  93     priv buckets: ~[Option<Bucket<K, V>>],
  94 }
  95
  96 // We could rewrite FoundEntry to have type Option<&Bucket<K, V>>
  97 // which would be nifty
  98 enum SearchResult {
  99     FoundEntry(uint), FoundHole(uint), TableFull
 100 }
 101
 102 #[inline]
 103 fn resize_at(capacity: uint) -> uint {
 104     (capacity * 3) / 4
 105 }
 106
 107 impl<K:Hash + Eq,V> HashMap<K, V> {
 108     #[inline]
 109     fn to_bucket(&self, h: uint) -> uint {
 110         // A good hash function with entropy spread over all of the
 111         // bits is assumed. SipHash is more than good enough.
 112         h % self.buckets.len()
 113     }
 114
 115     #[inline]
 116     fn next_bucket(&self, idx: uint, len_buckets: uint) -> uint {
 117         (idx + 1) % len_buckets
 118     }
 119
 120     #[inline]
 121     fn bucket_sequence(&self, hash: uint, op: |uint| -> bool) -> bool {
 122         let start_idx = self.to_bucket(hash);
 123         let len_buckets = self.buckets.len();
 124         let mut idx = start_idx;
 125         loop {
 126             if !op(idx) { return false; }
 127             idx = self.next_bucket(idx, len_buckets);
 128             if idx == start_idx {
 129                 return true;
 130             }
 131         }
 132     }
 133
 134     #[inline]
 135     fn bucket_for_key(&self, k: &K) -> SearchResult {
 136         let hash = k.hash_keyed(self.k0, self.k1) as uint;
 137         self.bucket_for_key_with_hash(hash, k)
 138     }
 139
 140     #[inline]
 141     fn bucket_for_key_equiv<Q:Hash + Equiv<K>>(&self, k: &Q)
 142                                                -> SearchResult {
 143         let hash = k.hash_keyed(self.k0, self.k1) as uint;
 144         self.bucket_for_key_with_hash_equiv(hash, k)
 145     }
 146
 147     #[inline]
 148     fn bucket_for_key_with_hash(&self,
 149                                 hash: uint,
 150                                 k: &K)
 151                              -> SearchResult {
 152         let mut ret = TableFull;
 153         self.bucket_sequence(hash, |i| {
 154             match self.buckets[i] {
 155                 Some(ref bkt) if bkt.hash == hash && *k == bkt.key => {
 156                     ret = FoundEntry(i); false
 157                 },
 158                 None => { ret = FoundHole(i); false }
 159                 _ => true,
 160             }
 161         });
 162         ret
 163     }
 164
 165     #[inline]
 166     fn bucket_for_key_with_hash_equiv<Q:Equiv<K>>(&self,
 167                                                   hash: uint,
 168                                                   k: &Q)
 169                                                -> SearchResult {
 170         let mut ret = TableFull;
 171         self.bucket_sequence(hash, |i| {
 172             match self.buckets[i] {
 173                 Some(ref bkt) if bkt.hash == hash && k.equiv(&bkt.key) => {
 174                     ret = FoundEntry(i); false
 175                 },
 176                 None => { ret = FoundHole(i); false }
 177                 _ => true,
 178             }
 179         });
 180         ret
 181     }
 182
 183     /// Expand the capacity of the array to the next power of two
 184     /// and re-insert each of the existing buckets.
 185     #[inline]
 186     fn expand(&mut self) {
 187         let new_capacity = self.buckets.len() * 2;
 188         self.resize(new_capacity);
 189     }
 190
 191     /// Expands the capacity of the array and re-insert each of the
 192     /// existing buckets.
 193     fn resize(&mut self, new_capacity: uint) {
 194         self.resize_at = resize_at(new_capacity);
 195
 196         let old_buckets = replace(&mut self.buckets,
 197                                   vec::from_fn(new_capacity, |_| None));
 198
 199         self.size = 0;
 200         for bucket in old_buckets.move_iter() {
 201             self.insert_opt_bucket(bucket);
 202         }
 203     }
 204
 205     fn insert_opt_bucket(&mut self, bucket: Option<Bucket<K, V>>) {
 206         match bucket {
 207             Some(Bucket{hash: hash, key: key, value: value}) => {
 208                 self.insert_internal(hash, key, value);
 209             }
 210             None => {}
 211         }
 212     }
 213
 214     #[inline]
 215     fn value_for_bucket<'a>(&'a self, idx: uint) -> &'a V {
 216         match self.buckets[idx] {
 217             Some(ref bkt) => &bkt.value,
 218             None => fail!("HashMap::find: internal logic error"),
 219         }
 220     }
 221
 222     #[inline]
 223     fn mut_value_for_bucket<'a>(&'a mut self, idx: uint) -> &'a mut V {
 224         match self.buckets[idx] {
 225             Some(ref mut bkt) => &mut bkt.value,
 226             None => unreachable!()
 227         }
 228     }
 229
 230     /// Inserts the key value pair into the buckets.
 231     /// Assumes that there will be a bucket.
 232     /// True if there was no previous entry with that key
 233     fn insert_internal(&mut self, hash: uint, k: K, v: V) -> Option<V> {
 234         match self.bucket_for_key_with_hash(hash, &k) {
 235             TableFull => { fail!("Internal logic error"); }
 236             FoundHole(idx) => {
 237                 self.buckets[idx] = Some(Bucket{hash: hash, key: k,
 238                                                 value: v});
 239                 self.size += 1;
 240                 None
 241             }
 242             FoundEntry(idx) => {
 243                 match self.buckets[idx] {
 244                     None => { fail!("insert_internal: Internal logic error") }
 245                     Some(ref mut b) => {
 246                         b.hash = hash;
 247                         b.key = k;
 248                         Some(replace(&mut b.value, v))
 249                     }
 250                 }
 251             }
 252         }
 253     }
 254
 255     fn pop_internal(&mut self, hash: uint, k: &K) -> Option<V> {
 256         // Removing from an open-addressed hashtable
 257         // is, well, painful.  The problem is that
 258         // the entry may lie on the probe path for other
 259         // entries, so removing it would make you think that
 260         // those probe paths are empty.
 261         //
 262         // To address this we basically have to keep walking,
 263         // re-inserting entries we find until we reach an empty
 264         // bucket.  We know we will eventually reach one because
 265         // we insert one ourselves at the beginning (the removed
 266         // entry).
 267         //
 268         // I found this explanation elucidating:
 269         // http://www.maths.lse.ac.uk/Courses/MA407/del-hash.pdf
 270         let mut idx = match self.bucket_for_key_with_hash(hash, k) {
 271             TableFull | FoundHole(_) => return None,
 272             FoundEntry(idx) => idx
 273         };
 274
 275         let len_buckets = self.buckets.len();
 276         let bucket = self.buckets[idx].take();
 277
 278         let value = bucket.map(|bucket| bucket.value);
 279
 280         /* re-inserting buckets may cause changes in size, so remember
 281         what our new size is ahead of time before we start insertions */
 282         let size = self.size - 1;
 283         idx = self.next_bucket(idx, len_buckets);
 284         while self.buckets[idx].is_some() {
 285             let bucket = self.buckets[idx].take();
 286             self.insert_opt_bucket(bucket);
 287             idx = self.next_bucket(idx, len_buckets);
 288         }
 289         self.size = size;
 290
 291         value
 292     }
 293 }
 294
 295 impl<K:Hash + Eq,V> Container for HashMap<K, V> {
 296     /// Return the number of elements in the map
 297     fn len(&self) -> uint { self.size }
 298 }
 299
 300 impl<K:Hash + Eq,V> Mutable for HashMap<K, V> {
 301     /// Clear the map, removing all key-value pairs.
 302     fn clear(&mut self) {
 303         for bkt in self.buckets.mut_iter() {
 304             *bkt = None;
 305         }
 306         self.size = 0;
 307     }
 308 }
 309
 310 impl<K:Hash + Eq,V> Map<K, V> for HashMap<K, V> {
 311     /// Return a reference to the value corresponding to the key
 312     fn find<'a>(&'a self, k: &K) -> Option<&'a V> {
 313         match self.bucket_for_key(k) {
 314             FoundEntry(idx) => Some(self.value_for_bucket(idx)),
 315             TableFull | FoundHole(_) => None,
 316         }
 317     }
 318 }
 319
 320 impl<K:Hash + Eq,V> MutableMap<K, V> for HashMap<K, V> {
 321     /// Return a mutable reference to the value corresponding to the key
 322     fn find_mut<'a>(&'a mut self, k: &K) -> Option<&'a mut V> {
 323         let idx = match self.bucket_for_key(k) {
 324             FoundEntry(idx) => idx,
 325             TableFull | FoundHole(_) => return None
 326         };
 327         Some(self.mut_value_for_bucket(idx))
 328     }
 329
 330     /// Insert a key-value pair from the map. If the key already had a value
 331     /// present in the map, that value is returned. Otherwise None is returned.
 332     fn swap(&mut self, k: K, v: V) -> Option<V> {
 333         // this could be faster.
 334
 335         if self.size >= self.resize_at {
 336             // n.b.: We could also do this after searching, so
 337             // that we do not resize if this call to insert is
 338             // simply going to update a key in place.  My sense
 339             // though is that it's worse to have to search through
 340             // buckets to find the right spot twice than to just
 341             // resize in this corner case.
 342             self.expand();
 343         }
 344
 345         let hash = k.hash_keyed(self.k0, self.k1) as uint;
 346         self.insert_internal(hash, k, v)
 347     }
 348
 349     /// Removes a key from the map, returning the value at the key if the key
 350     /// was previously in the map.
 351     fn pop(&mut self, k: &K) -> Option<V> {
 352         let hash = k.hash_keyed(self.k0, self.k1) as uint;
 353         self.pop_internal(hash, k)
 354     }
 355 }
 356
 357 impl<K: Hash + Eq, V> HashMap<K, V> {
 358     /// Create an empty HashMap
 359     pub fn new() -> HashMap<K, V> {
 360         HashMap::with_capacity(INITIAL_CAPACITY)
 361     }
 362
 363     /// Create an empty HashMap with space for at least `capacity`
 364     /// elements in the hash table.
 365     pub fn with_capacity(capacity: uint) -> HashMap<K, V> {
 366         let mut r = rand::task_rng();
 367         HashMap::with_capacity_and_keys(r.gen(), r.gen(), capacity)
 368     }
 369
 370     /// Create an empty HashMap with space for at least `capacity`
 371     /// elements, using `k0` and `k1` as the keys.
 372     ///
 373     /// Warning: `k0` and `k1` are normally randomly generated, and
 374     /// are designed to allow HashMaps to be resistant to attacks that
 375     /// cause many collisions and very poor performance. Setting them
 376     /// manually using this function can expose a DoS attack vector.
 377     pub fn with_capacity_and_keys(k0: u64, k1: u64, capacity: uint) -> HashMap<K, V> {
 378         let cap = num::max(INITIAL_CAPACITY, capacity);
 379         HashMap {
 380             k0: k0, k1: k1,
 381             resize_at: resize_at(cap),
 382             size: 0,
 383             buckets: vec::from_fn(cap, |_| None)
 384         }
 385     }
 386
 387     /// Reserve space for at least `n` elements in the hash table.
 388     pub fn reserve_at_least(&mut self, n: uint) {
 389         if n > self.buckets.len() {
 390             let buckets = n * 4 / 3 + 1;
 391             self.resize(uint::next_power_of_two(buckets));
 392         }
 393     }
 394
 395     /// Modify and return the value corresponding to the key in the map, or
 396     /// insert and return a new value if it doesn't exist.
 397     ///
 398     /// This method allows for all insertion behaviours of a hashmap,
 399     /// see methods like `insert`, `find_or_insert` and
 400     /// `insert_or_update_with` for less general and more friendly
 401     /// variations of this.
 402     ///
 403     /// # Example
 404     ///
 405     /// ```rust
 406     /// use std::hashmap::HashMap;
 407     ///
 408     /// // map some strings to vectors of strings
 409     /// let mut map = HashMap::<~str, ~[~str]>::new();
 410     /// map.insert(~"a key", ~[~"value"]);
 411     /// map.insert(~"z key", ~[~"value"]);
 412     ///
 413     /// let new = ~[~"a key", ~"b key", ~"z key"];
 414     /// for k in new.move_iter() {
 415     ///     map.mangle(k, ~"new value",
 416     ///                // if the key doesn't exist in the map yet, add it in
 417     ///                // the obvious way.
 418     ///                |_k, v| ~[v],
 419     ///                // if the key does exist either prepend or append this
 420     ///                // new value based on the first letter of the key.
 421     ///                |key, already, new| {
 422     ///                     if key.starts_with("z") {
 423     ///                         already.unshift(new);
 424     ///                     } else {
 425     ///                         already.push(new);
 426     ///                     }
 427     ///                });
 428     /// }
 429     ///
 430     /// for (k, v) in map.iter() {
 431     ///    println!("{} -> {:?}", *k, *v);
 432     /// }
 433     /// ```
 434     pub fn mangle<'a,
 435                   A>(
 436                   &'a mut self,
 437                   k: K,
 438                   a: A,
 439                   not_found: |&K, A| -> V,
 440                   found: |&K, &mut V, A|)
 441                   -> &'a mut V {
 442         if self.size >= self.resize_at {
 443             // n.b.: We could also do this after searching, so
 444             // that we do not resize if this call to insert is
 445             // simply going to update a key in place.  My sense
 446             // though is that it's worse to have to search through
 447             // buckets to find the right spot twice than to just
 448             // resize in this corner case.
 449             self.expand();
 450         }
 451
 452         let hash = k.hash_keyed(self.k0, self.k1) as uint;
 453         let idx = match self.bucket_for_key_with_hash(hash, &k) {
 454             TableFull => fail!("Internal logic error"),
 455             FoundEntry(idx) => { found(&k, self.mut_value_for_bucket(idx), a); idx }
 456             FoundHole(idx) => {
 457                 let v = not_found(&k, a);
 458                 self.buckets[idx] = Some(Bucket{hash: hash, key: k, value: v});
 459                 self.size += 1;
 460                 idx
 461             }
 462         };
 463
 464         self.mut_value_for_bucket(idx)
 465     }
 466
 467     /// Return the value corresponding to the key in the map, or insert
 468     /// and return the value if it doesn't exist.
 469     pub fn find_or_insert<'a>(&'a mut self, k: K, v: V) -> &'a mut V {
 470         self.mangle(k, v, |_k, a| a, |_k,_v,_a| ())
 471     }
 472
 473     /// Return the value corresponding to the key in the map, or create,
 474     /// insert, and return a new value if it doesn't exist.
 475     pub fn find_or_insert_with<'a>(&'a mut self, k: K, f: |&K| -> V)
 476                                -> &'a mut V {
 477         self.mangle(k, (), |k,_a| f(k), |_k,_v,_a| ())
 478     }
 479
 480     /// Insert a key-value pair into the map if the key is not already present.
 481     /// Otherwise, modify the existing value for the key.
 482     /// Returns the new or modified value for the key.
 483     pub fn insert_or_update_with<'a>(
 484                                  &'a mut self,
 485                                  k: K,
 486                                  v: V,
 487                                  f: |&K, &mut V|)
 488                                  -> &'a mut V {
 489         self.mangle(k, v, |_k,a| a, |k,v,_a| f(k,v))
 490     }
 491
 492     /// Retrieves a value for the given key, failing if the key is not
 493     /// present.
 494     pub fn get<'a>(&'a self, k: &K) -> &'a V {
 495         match self.find(k) {
 496             Some(v) => v,
 497             None => fail!("No entry found for key: {:?}", k),
 498         }
 499     }
 500
 501     /// Retrieves a (mutable) value for the given key, failing if the key
 502     /// is not present.
 503     pub fn get_mut<'a>(&'a mut self, k: &K) -> &'a mut V {
 504         match self.find_mut(k) {
 505             Some(v) => v,
 506             None => fail!("No entry found for key: {:?}", k),
 507         }
 508     }
 509
 510     /// Return true if the map contains a value for the specified key,
 511     /// using equivalence
 512     pub fn contains_key_equiv<Q:Hash + Equiv<K>>(&self, key: &Q) -> bool {
 513         match self.bucket_for_key_equiv(key) {
 514             FoundEntry(_) => {true}
 515             TableFull | FoundHole(_) => {false}
 516         }
 517     }
 518
 519     /// Return the value corresponding to the key in the map, using
 520     /// equivalence
 521     pub fn find_equiv<'a, Q:Hash + Equiv<K>>(&'a self, k: &Q)
 522                                              -> Option<&'a V> {
 523         match self.bucket_for_key_equiv(k) {
 524             FoundEntry(idx) => Some(self.value_for_bucket(idx)),
 525             TableFull | FoundHole(_) => None,
 526         }
 527     }
 528
 529     /// An iterator visiting all keys in arbitrary order.
 530     /// Iterator element type is &'a K.
 531     pub fn keys<'a>(&'a self) -> HashMapKeyIterator<'a, K, V> {
 532         self.iter().map(|(k, _v)| k)
 533     }
 534
 535     /// An iterator visiting all values in arbitrary order.
 536     /// Iterator element type is &'a V.
 537     pub fn values<'a>(&'a self) -> HashMapValueIterator<'a, K, V> {
 538         self.iter().map(|(_k, v)| v)
 539     }
 540
 541     /// An iterator visiting all key-value pairs in arbitrary order.
 542     /// Iterator element type is (&'a K, &'a V).
 543     pub fn iter<'a>(&'a self) -> HashMapIterator<'a, K, V> {
 544         HashMapIterator { iter: self.buckets.iter() }
 545     }
 546
 547     /// An iterator visiting all key-value pairs in arbitrary order,
 548     /// with mutable references to the values.
 549     /// Iterator element type is (&'a K, &'a mut V).
 550     pub fn mut_iter<'a>(&'a mut self) -> HashMapMutIterator<'a, K, V> {
 551         HashMapMutIterator { iter: self.buckets.mut_iter() }
 552     }
 553
 554     /// Creates a consuming iterator, that is, one that moves each key-value
 555     /// pair out of the map in arbitrary order. The map cannot be used after
 556     /// calling this.
 557     pub fn move_iter(self) -> HashMapMoveIterator<K, V> {
 558         HashMapMoveIterator {iter: self.buckets.move_iter()}
 559     }
 560 }
 561
 562 impl<K: Hash + Eq, V: Clone> HashMap<K, V> {
 563     /// Like `find`, but returns a copy of the value.
 564     pub fn find_copy(&self, k: &K) -> Option<V> {
 565         self.find(k).map(|v| (*v).clone())
 566     }
 567
 568     /// Like `get`, but returns a copy of the value.
 569     pub fn get_copy(&self, k: &K) -> V {
 570         (*self.get(k)).clone()
 571     }
 572 }
 573
 574 impl<K:Hash + Eq,V:Eq> Eq for HashMap<K, V> {
 575     fn eq(&self, other: &HashMap<K, V>) -> bool {
 576         if self.len() != other.len() { return false; }
 577
 578         self.iter().all(|(key, value)| {
 579             match other.find(key) {
 580                 None => false,
 581                 Some(v) => value == v
 582             }
 583         })
 584     }
 585
 586     fn ne(&self, other: &HashMap<K, V>) -> bool { !self.eq(other) }
 587 }
 588
 589 impl<K:Hash + Eq + Clone,V:Clone> Clone for HashMap<K,V> {
 590     fn clone(&self) -> HashMap<K,V> {
 591         let mut new_map = HashMap::with_capacity(self.len());
 592         for (key, value) in self.iter() {
 593             new_map.insert((*key).clone(), (*value).clone());
 594         }
 595         new_map
 596     }
 597 }
 598
 599 /// HashMap iterator
 600 #[deriving(Clone)]
 601 pub struct HashMapIterator<'a, K, V> {
 602     priv iter: vec::VecIterator<'a, Option<Bucket<K, V>>>,
 603 }
 604
 605 /// HashMap mutable values iterator
 606 pub struct HashMapMutIterator<'a, K, V> {
 607     priv iter: vec::VecMutIterator<'a, Option<Bucket<K, V>>>,
 608 }
 609
 610 /// HashMap move iterator
 611 pub struct HashMapMoveIterator<K, V> {
 612     priv iter: vec::MoveIterator<Option<Bucket<K, V>>>,
 613 }
 614
 615 /// HashMap keys iterator
 616 pub type HashMapKeyIterator<'a, K, V> =
 617     iter::Map<'static, (&'a K, &'a V), &'a K, HashMapIterator<'a, K, V>>;
 618
 619 /// HashMap values iterator
 620 pub type HashMapValueIterator<'a, K, V> =
 621     iter::Map<'static, (&'a K, &'a V), &'a V, HashMapIterator<'a, K, V>>;
 622
 623 /// HashSet iterator
 624 #[deriving(Clone)]
 625 pub struct HashSetIterator<'a, K> {
 626     priv iter: vec::VecIterator<'a, Option<Bucket<K, ()>>>,
 627 }
 628
 629 /// HashSet move iterator
 630 pub struct HashSetMoveIterator<K> {
 631     priv iter: vec::MoveIterator<Option<Bucket<K, ()>>>,
 632 }
 633
 634 impl<'a, K, V> Iterator<(&'a K, &'a V)> for HashMapIterator<'a, K, V> {
 635     #[inline]
 636     fn next(&mut self) -> Option<(&'a K, &'a V)> {
 637         for elt in self.iter {
 638             match elt {
 639                 &Some(ref bucket) => return Some((&bucket.key, &bucket.value)),
 640                 &None => {},
 641             }
 642         }
 643         None
 644     }
 645 }
 646
 647 impl<'a, K, V> Iterator<(&'a K, &'a mut V)> for HashMapMutIterator<'a, K, V> {
 648     #[inline]
 649     fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
 650         for elt in self.iter {
 651             match elt {
 652                 &Some(ref mut bucket) => return Some((&bucket.key, &mut bucket.value)),
 653                 &None => {},
 654             }
 655         }
 656         None
 657     }
 658 }
 659
 660 impl<K, V> Iterator<(K, V)> for HashMapMoveIterator<K, V> {
 661     #[inline]
 662     fn next(&mut self) -> Option<(K, V)> {
 663         for elt in self.iter {
 664             match elt {
 665                 Some(Bucket {key, value, ..}) => return Some((key, value)),
 666                 None => {},
 667             }
 668         }
 669         None
 670     }
 671 }
 672
 673 impl<'a, K> Iterator<&'a K> for HashSetIterator<'a, K> {
 674     #[inline]
 675     fn next(&mut self) -> Option<&'a K> {
 676         for elt in self.iter {
 677             match elt {
 678                 &Some(ref bucket) => return Some(&bucket.key),
 679                 &None => {},
 680             }
 681         }
 682         None
 683     }
 684 }
 685
 686 impl<K> Iterator<K> for HashSetMoveIterator<K> {
 687     #[inline]
 688     fn next(&mut self) -> Option<K> {
 689         for elt in self.iter {
 690             match elt {
 691                 Some(bucket) => return Some(bucket.key),
 692                 None => {},
 693             }
 694         }
 695         None
 696     }
 697 }
 698
 699 impl<K: Eq + Hash, V> FromIterator<(K, V)> for HashMap<K, V> {
 700     fn from_iterator<T: Iterator<(K, V)>>(iter: &mut T) -> HashMap<K, V> {
 701         let (lower, _) = iter.size_hint();
 702         let mut map = HashMap::with_capacity(lower);
 703         map.extend(iter);
 704         map
 705     }
 706 }
 707
 708 impl<K: Eq + Hash, V> Extendable<(K, V)> for HashMap<K, V> {
 709     fn extend<T: Iterator<(K, V)>>(&mut self, iter: &mut T) {
 710         for (k, v) in *iter {
 711             self.insert(k, v);
 712         }
 713     }
 714 }
 715
 716 impl<K: Eq + Hash, V> Default for HashMap<K, V> {
 717     fn default() -> HashMap<K, V> { HashMap::new() }
 718 }
 719
 720 /// An implementation of a hash set using the underlying representation of a
 721 /// HashMap where the value is (). As with the `HashMap` type, a `HashSet`
 722 /// requires that the elements implement the `Eq` and `Hash` traits.
 723 pub struct HashSet<T> {
 724     priv map: HashMap<T, ()>
 725 }
 726
 727 impl<T:Hash + Eq> Eq for HashSet<T> {
 728     fn eq(&self, other: &HashSet<T>) -> bool { self.map == other.map }
 729     fn ne(&self, other: &HashSet<T>) -> bool { self.map != other.map }
 730 }
 731
 732 impl<T:Hash + Eq> Container for HashSet<T> {
 733     /// Return the number of elements in the set
 734     fn len(&self) -> uint { self.map.len() }
 735 }
 736
 737 impl<T:Hash + Eq> Mutable for HashSet<T> {
 738     /// Clear the set, removing all values.
 739     fn clear(&mut self) { self.map.clear() }
 740 }
 741
 742 impl<T:Hash + Eq> Set<T> for HashSet<T> {
 743     /// Return true if the set contains a value
 744     fn contains(&self, value: &T) -> bool { self.map.contains_key(value) }
 745
 746     /// Return true if the set has no elements in common with `other`.
 747     /// This is equivalent to checking for an empty intersection.
 748     fn is_disjoint(&self, other: &HashSet<T>) -> bool {
 749         self.iter().all(|v| !other.contains(v))
 750     }
 751
 752     /// Return true if the set is a subset of another
 753     fn is_subset(&self, other: &HashSet<T>) -> bool {
 754         self.iter().all(|v| other.contains(v))
 755     }
 756
 757     /// Return true if the set is a superset of another
 758     fn is_superset(&self, other: &HashSet<T>) -> bool {
 759         other.is_subset(self)
 760     }
 761 }
 762
 763 impl<T:Hash + Eq> MutableSet<T> for HashSet<T> {
 764     /// Add a value to the set. Return true if the value was not already
 765     /// present in the set.
 766     fn insert(&mut self, value: T) -> bool { self.map.insert(value, ()) }
 767
 768     /// Remove a value from the set. Return true if the value was
 769     /// present in the set.
 770     fn remove(&mut self, value: &T) -> bool { self.map.remove(value) }
 771 }
 772
 773 impl<T:Hash + Eq> HashSet<T> {
 774     /// Create an empty HashSet
 775     pub fn new() -> HashSet<T> {
 776         HashSet::with_capacity(INITIAL_CAPACITY)
 777     }
 778
 779     /// Create an empty HashSet with space for at least `n` elements in
 780     /// the hash table.
 781     pub fn with_capacity(capacity: uint) -> HashSet<T> {
 782         HashSet { map: HashMap::with_capacity(capacity) }
 783     }
 784
 785     /// Create an empty HashSet with space for at least `capacity`
 786     /// elements in the hash table, using `k0` and `k1` as the keys.
 787     ///
 788     /// Warning: `k0` and `k1` are normally randomly generated, and
 789     /// are designed to allow HashSets to be resistant to attacks that
 790     /// cause many collisions and very poor performance. Setting them
 791     /// manually using this function can expose a DoS attack vector.
 792     pub fn with_capacity_and_keys(k0: u64, k1: u64, capacity: uint) -> HashSet<T> {
 793         HashSet { map: HashMap::with_capacity_and_keys(k0, k1, capacity) }
 794     }
 795
 796     /// Reserve space for at least `n` elements in the hash table.
 797     pub fn reserve_at_least(&mut self, n: uint) {
 798         self.map.reserve_at_least(n)
 799     }
 800
 801     /// Returns true if the hash set contains a value equivalent to the
 802     /// given query value.
 803     pub fn contains_equiv<Q:Hash + Equiv<T>>(&self, value: &Q) -> bool {
 804       self.map.contains_key_equiv(value)
 805     }
 806
 807     /// An iterator visiting all elements in arbitrary order.
 808     /// Iterator element type is &'a T.
 809     pub fn iter<'a>(&'a self) -> HashSetIterator<'a, T> {
 810         HashSetIterator { iter: self.map.buckets.iter() }
 811     }
 812
 813     /// Creates a consuming iterator, that is, one that moves each value out
 814     /// of the set in arbitrary order. The set cannot be used after calling
 815     /// this.
 816     pub fn move_iter(self) -> HashSetMoveIterator<T> {
 817         HashSetMoveIterator {iter: self.map.buckets.move_iter()}
 818     }
 819
 820     /// Visit the values representing the difference
 821     pub fn difference<'a>(&'a self, other: &'a HashSet<T>) -> SetAlgebraIter<'a, T> {
 822         Repeat::new(other)
 823             .zip(self.iter())
 824             .filter_map(|(other, elt)| {
 825                 if !other.contains(elt) { Some(elt) } else { None }
 826             })
 827     }
 828
 829     /// Visit the values representing the symmetric difference
 830     pub fn symmetric_difference<'a>(&'a self, other: &'a HashSet<T>)
 831         -> Chain<SetAlgebraIter<'a, T>, SetAlgebraIter<'a, T>> {
 832         self.difference(other).chain(other.difference(self))
 833     }
 834
 835     /// Visit the values representing the intersection
 836     pub fn intersection<'a>(&'a self, other: &'a HashSet<T>)
 837         -> SetAlgebraIter<'a, T> {
 838         Repeat::new(other)
 839             .zip(self.iter())
 840             .filter_map(|(other, elt)| {
 841                 if other.contains(elt) { Some(elt) } else { None }
 842             })
 843     }
 844
 845     /// Visit the values representing the union
 846     pub fn union<'a>(&'a self, other: &'a HashSet<T>)
 847         -> Chain<HashSetIterator<'a, T>, SetAlgebraIter<'a, T>> {
 848         self.iter().chain(other.difference(self))
 849     }
 850
 851 }
 852
 853 impl<T:Hash + Eq + Clone> Clone for HashSet<T> {
 854     fn clone(&self) -> HashSet<T> {
 855         HashSet {
 856             map: self.map.clone()
 857         }
 858     }
 859 }
 860
 861 impl<K: Eq + Hash> FromIterator<K> for HashSet<K> {
 862     fn from_iterator<T: Iterator<K>>(iter: &mut T) -> HashSet<K> {
 863         let (lower, _) = iter.size_hint();
 864         let mut set = HashSet::with_capacity(lower);
 865         set.extend(iter);
 866         set
 867     }
 868 }
 869
 870 impl<K: Eq + Hash> Extendable<K> for HashSet<K> {
 871     fn extend<T: Iterator<K>>(&mut self, iter: &mut T) {
 872         for k in *iter {
 873             self.insert(k);
 874         }
 875     }
 876 }
 877
 878 impl<K: Eq + Hash> Default for HashSet<K> {
 879     fn default() -> HashSet<K> { HashSet::new() }
 880 }
 881
 882 // `Repeat` is used to feed the filter closure an explicit capture
 883 // of a reference to the other set
 884 /// Set operations iterator
 885 pub type SetAlgebraIter<'a, T> =
 886     FilterMap<'static,(&'a HashSet<T>, &'a T), &'a T,
 887               Zip<Repeat<&'a HashSet<T>>,HashSetIterator<'a,T>>>;
 888
 889
 890 #[cfg(test)]
 891 mod test_map {
 892     use prelude::*;
 893     use super::*;
 894
 895     #[test]
 896     fn test_create_capacity_zero() {
 897         let mut m = HashMap::with_capacity(0);
 898         assert!(m.insert(1, 1));
 899     }
 900
 901     #[test]
 902     fn test_insert() {
 903         let mut m = HashMap::new();
 904         assert!(m.insert(1, 2));
 905         assert!(m.insert(2, 4));
 906         assert_eq!(*m.get(&1), 2);
 907         assert_eq!(*m.get(&2), 4);
 908     }
 909
 910     #[test]
 911     fn test_find_mut() {
 912         let mut m = HashMap::new();
 913         assert!(m.insert(1, 12));
 914         assert!(m.insert(2, 8));
 915         assert!(m.insert(5, 14));
 916         let new = 100;
 917         match m.find_mut(&5) {
 918             None => fail!(), Some(x) => *x = new
 919         }
 920         assert_eq!(m.find(&5), Some(&new));
 921     }
 922
 923     #[test]
 924     fn test_insert_overwrite() {
 925         let mut m = HashMap::new();
 926         assert!(m.insert(1, 2));
 927         assert_eq!(*m.get(&1), 2);
 928         assert!(!m.insert(1, 3));
 929         assert_eq!(*m.get(&1), 3);
 930     }
 931
 932     #[test]
 933     fn test_insert_conflicts() {
 934         let mut m = HashMap::with_capacity(4);
 935         assert!(m.insert(1, 2));
 936         assert!(m.insert(5, 3));
 937         assert!(m.insert(9, 4));
 938         assert_eq!(*m.get(&9), 4);
 939         assert_eq!(*m.get(&5), 3);
 940         assert_eq!(*m.get(&1), 2);
 941     }
 942
 943     #[test]
 944     fn test_conflict_remove() {
 945         let mut m = HashMap::with_capacity(4);
 946         assert!(m.insert(1, 2));
 947         assert!(m.insert(5, 3));
 948         assert!(m.insert(9, 4));
 949         assert!(m.remove(&1));
 950         assert_eq!(*m.get(&9), 4);
 951         assert_eq!(*m.get(&5), 3);
 952     }
 953
 954     #[test]
 955     fn test_is_empty() {
 956         let mut m = HashMap::with_capacity(4);
 957         assert!(m.insert(1, 2));
 958         assert!(!m.is_empty());
 959         assert!(m.remove(&1));
 960         assert!(m.is_empty());
 961     }
 962
 963     #[test]
 964     fn test_pop() {
 965         let mut m = HashMap::new();
 966         m.insert(1, 2);
 967         assert_eq!(m.pop(&1), Some(2));
 968         assert_eq!(m.pop(&1), None);
 969     }
 970
 971     #[test]
 972     fn test_swap() {
 973         let mut m = HashMap::new();
 974         assert_eq!(m.swap(1, 2), None);
 975         assert_eq!(m.swap(1, 3), Some(2));
 976         assert_eq!(m.swap(1, 4), Some(3));
 977     }
 978
 979     #[test]
 980     fn test_find_or_insert() {
 981         let mut m: HashMap<int,int> = HashMap::new();
 982         assert_eq!(*m.find_or_insert(1, 2), 2);
 983         assert_eq!(*m.find_or_insert(1, 3), 2);
 984     }
 985
 986     #[test]
 987     fn test_find_or_insert_with() {
 988         let mut m: HashMap<int,int> = HashMap::new();
 989         assert_eq!(*m.find_or_insert_with(1, |_| 2), 2);
 990         assert_eq!(*m.find_or_insert_with(1, |_| 3), 2);
 991     }
 992
 993     #[test]
 994     fn test_insert_or_update_with() {
 995         let mut m: HashMap<int,int> = HashMap::new();
 996         assert_eq!(*m.insert_or_update_with(1, 2, |_,x| *x+=1), 2);
 997         assert_eq!(*m.insert_or_update_with(1, 2, |_,x| *x+=1), 3);
 998     }
 999
1000     #[test]
1001     fn test_move_iter() {
1002         let hm = {
1003             let mut hm = HashMap::new();
1004
1005             hm.insert('a', 1);
1006             hm.insert('b', 2);
1007
1008             hm
1009         };
1010
1011         let v = hm.move_iter().collect::<~[(char, int)]>();
1012         assert!([('a', 1), ('b', 2)] == v || [('b', 2), ('a', 1)] == v);
1013     }
1014
1015     #[test]
1016     fn test_iterate() {
1017         let mut m = HashMap::with_capacity(4);
1018         for i in range(0u, 32) {
1019             assert!(m.insert(i, i*2));
1020         }
1021         let mut observed = 0;
1022         for (k, v) in m.iter() {
1023             assert_eq!(*v, *k * 2);
1024             observed |= (1 << *k);
1025         }
1026         assert_eq!(observed, 0xFFFF_FFFF);
1027     }
1028
1029     #[test]
1030     fn test_keys() {
1031         let vec = ~[(1, 'a'), (2, 'b'), (3, 'c')];
1032         let map = vec.move_iter().collect::<HashMap<int, char>>();
1033         let keys = map.keys().map(|&k| k).collect::<~[int]>();
1034         assert_eq!(keys.len(), 3);
1035         assert!(keys.contains(&1));
1036         assert!(keys.contains(&2));
1037         assert!(keys.contains(&3));
1038     }
1039
1040     #[test]
1041     fn test_values() {
1042         let vec = ~[(1, 'a'), (2, 'b'), (3, 'c')];
1043         let map = vec.move_iter().collect::<HashMap<int, char>>();
1044         let values = map.values().map(|&v| v).collect::<~[char]>();
1045         assert_eq!(values.len(), 3);
1046         assert!(values.contains(&'a'));
1047         assert!(values.contains(&'b'));
1048         assert!(values.contains(&'c'));
1049     }
1050
1051     #[test]
1052     fn test_find() {
1053         let mut m = HashMap::new();
1054         assert!(m.find(&1).is_none());
1055         m.insert(1, 2);
1056         match m.find(&1) {
1057             None => fail!(),
1058             Some(v) => assert!(*v == 2)
1059         }
1060     }
1061
1062     #[test]
1063     fn test_eq() {
1064         let mut m1 = HashMap::new();
1065         m1.insert(1, 2);
1066         m1.insert(2, 3);
1067         m1.insert(3, 4);
1068
1069         let mut m2 = HashMap::new();
1070         m2.insert(1, 2);
1071         m2.insert(2, 3);
1072
1073         assert!(m1 != m2);
1074
1075         m2.insert(3, 4);
1076
1077         assert_eq!(m1, m2);
1078     }
1079
1080     #[test]
1081     fn test_expand() {
1082         let mut m = HashMap::new();
1083
1084         assert_eq!(m.len(), 0);
1085         assert!(m.is_empty());
1086
1087         let mut i = 0u;
1088         let old_resize_at = m.resize_at;
1089         while old_resize_at == m.resize_at {
1090             m.insert(i, i);
1091             i += 1;
1092         }
1093
1094         assert_eq!(m.len(), i);
1095         assert!(!m.is_empty());
1096     }
1097
1098     #[test]
1099     fn test_find_equiv() {
1100         let mut m = HashMap::new();
1101
1102         let (foo, bar, baz) = (1,2,3);
1103         m.insert(~"foo", foo);
1104         m.insert(~"bar", bar);
1105         m.insert(~"baz", baz);
1106
1107
1108         assert_eq!(m.find_equiv(&("foo")), Some(&foo));
1109         assert_eq!(m.find_equiv(&("bar")), Some(&bar));
1110         assert_eq!(m.find_equiv(&("baz")), Some(&baz));
1111
1112         assert_eq!(m.find_equiv(&("qux")), None);
1113     }
1114
1115     #[test]
1116     fn test_from_iter() {
1117         let xs = ~[(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
1118
1119         let map: HashMap<int, int> = xs.iter().map(|&x| x).collect();
1120
1121         for &(k, v) in xs.iter() {
1122             assert_eq!(map.find(&k), Some(&v));
1123         }
1124     }
1125 }
1126
1127 #[cfg(test)]
1128 mod test_set {
1129     use super::*;
1130     use prelude::*;
1131     use container::Container;
1132     use vec::ImmutableEqVector;
1133
1134     #[test]
1135     fn test_disjoint() {
1136         let mut xs = HashSet::new();
1137         let mut ys = HashSet::new();
1138         assert!(xs.is_disjoint(&ys));
1139         assert!(ys.is_disjoint(&xs));
1140         assert!(xs.insert(5));
1141         assert!(ys.insert(11));
1142         assert!(xs.is_disjoint(&ys));
1143         assert!(ys.is_disjoint(&xs));
1144         assert!(xs.insert(7));
1145         assert!(xs.insert(19));
1146         assert!(xs.insert(4));
1147         assert!(ys.insert(2));
1148         assert!(ys.insert(-11));
1149         assert!(xs.is_disjoint(&ys));
1150         assert!(ys.is_disjoint(&xs));
1151         assert!(ys.insert(7));
1152         assert!(!xs.is_disjoint(&ys));
1153         assert!(!ys.is_disjoint(&xs));
1154     }
1155
1156     #[test]
1157     fn test_subset_and_superset() {
1158         let mut a = HashSet::new();
1159         assert!(a.insert(0));
1160         assert!(a.insert(5));
1161         assert!(a.insert(11));
1162         assert!(a.insert(7));
1163
1164         let mut b = HashSet::new();
1165         assert!(b.insert(0));
1166         assert!(b.insert(7));
1167         assert!(b.insert(19));
1168         assert!(b.insert(250));
1169         assert!(b.insert(11));
1170         assert!(b.insert(200));
1171
1172         assert!(!a.is_subset(&b));
1173         assert!(!a.is_superset(&b));
1174         assert!(!b.is_subset(&a));
1175         assert!(!b.is_superset(&a));
1176
1177         assert!(b.insert(5));
1178
1179         assert!(a.is_subset(&b));
1180         assert!(!a.is_superset(&b));
1181         assert!(!b.is_subset(&a));
1182         assert!(b.is_superset(&a));
1183     }
1184
1185     #[test]
1186     fn test_iterate() {
1187         let mut a = HashSet::new();
1188         for i in range(0u, 32) {
1189             assert!(a.insert(i));
1190         }
1191         let mut observed = 0;
1192         for k in a.iter() {
1193             observed |= (1 << *k);
1194         }
1195         assert_eq!(observed, 0xFFFF_FFFF);
1196     }
1197
1198     #[test]
1199     fn test_intersection() {
1200         let mut a = HashSet::new();
1201         let mut b = HashSet::new();
1202
1203         assert!(a.insert(11));
1204         assert!(a.insert(1));
1205         assert!(a.insert(3));
1206         assert!(a.insert(77));
1207         assert!(a.insert(103));
1208         assert!(a.insert(5));
1209         assert!(a.insert(-5));
1210
1211         assert!(b.insert(2));
1212         assert!(b.insert(11));
1213         assert!(b.insert(77));
1214         assert!(b.insert(-9));
1215         assert!(b.insert(-42));
1216         assert!(b.insert(5));
1217         assert!(b.insert(3));
1218
1219         let mut i = 0;
1220         let expected = [3, 5, 11, 77];
1221         for x in a.intersection(&b) {
1222             assert!(expected.contains(x));
1223             i += 1
1224         }
1225         assert_eq!(i, expected.len());
1226     }
1227
1228     #[test]
1229     fn test_difference() {
1230         let mut a = HashSet::new();
1231         let mut b = HashSet::new();
1232
1233         assert!(a.insert(1));
1234         assert!(a.insert(3));
1235         assert!(a.insert(5));
1236         assert!(a.insert(9));
1237         assert!(a.insert(11));
1238
1239         assert!(b.insert(3));
1240         assert!(b.insert(9));
1241
1242         let mut i = 0;
1243         let expected = [1, 5, 11];
1244         for x in a.difference(&b) {
1245             assert!(expected.contains(x));
1246             i += 1
1247         }
1248         assert_eq!(i, expected.len());
1249     }
1250
1251     #[test]
1252     fn test_symmetric_difference() {
1253         let mut a = HashSet::new();
1254         let mut b = HashSet::new();
1255
1256         assert!(a.insert(1));
1257         assert!(a.insert(3));
1258         assert!(a.insert(5));
1259         assert!(a.insert(9));
1260         assert!(a.insert(11));
1261
1262         assert!(b.insert(-2));
1263         assert!(b.insert(3));
1264         assert!(b.insert(9));
1265         assert!(b.insert(14));
1266         assert!(b.insert(22));
1267
1268         let mut i = 0;
1269         let expected = [-2, 1, 5, 11, 14, 22];
1270         for x in a.symmetric_difference(&b) {
1271             assert!(expected.contains(x));
1272             i += 1
1273         }
1274         assert_eq!(i, expected.len());
1275     }
1276
1277     #[test]
1278     fn test_union() {
1279         let mut a = HashSet::new();
1280         let mut b = HashSet::new();
1281
1282         assert!(a.insert(1));
1283         assert!(a.insert(3));
1284         assert!(a.insert(5));
1285         assert!(a.insert(9));
1286         assert!(a.insert(11));
1287         assert!(a.insert(16));
1288         assert!(a.insert(19));
1289         assert!(a.insert(24));
1290
1291         assert!(b.insert(-2));
1292         assert!(b.insert(1));
1293         assert!(b.insert(5));
1294         assert!(b.insert(9));
1295         assert!(b.insert(13));
1296         assert!(b.insert(19));
1297
1298         let mut i = 0;
1299         let expected = [-2, 1, 3, 5, 9, 11, 13, 16, 19, 24];
1300         for x in a.union(&b) {
1301             assert!(expected.contains(x));
1302             i += 1
1303         }
1304         assert_eq!(i, expected.len());
1305     }
1306
1307     #[test]
1308     fn test_from_iter() {
1309         let xs = ~[1, 2, 3, 4, 5, 6, 7, 8, 9];
1310
1311         let set: HashSet<int> = xs.iter().map(|&x| x).collect();
1312
1313         for x in xs.iter() {
1314             assert!(set.contains(x));
1315         }
1316     }
1317
1318     #[test]
1319     fn test_move_iter() {
1320         let hs = {
1321             let mut hs = HashSet::new();
1322
1323             hs.insert('a');
1324             hs.insert('b');
1325
1326             hs
1327         };
1328
1329         let v = hs.move_iter().collect::<~[char]>();
1330         assert!(['a', 'b'] == v || ['b', 'a'] == v);
1331     }
1332
1333     #[test]
1334     fn test_eq() {
1335         let mut s1 = HashSet::new();
1336         s1.insert(1);
1337         s1.insert(2);
1338         s1.insert(3);
1339
1340         let mut s2 = HashSet::new();
1341         s2.insert(1);
1342         s2.insert(2);
1343
1344         assert!(s1 != s2);
1345
1346         s2.insert(3);
1347
1348         assert_eq!(s1, s2);
1349     }
1350 }