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