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