src/libcollections/smallintmap.rs

   1 // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 /*!
  12  * A simple map based on a vector for small integer keys. Space requirements
  13  * are O(highest integer key).
  14  */
  15
  16 #![allow(missing_doc)]
  17
  18 use std::iter::{Enumerate, FilterMap};
  19 use std::mem::replace;
  20 use std::{vec, slice};
  21
  22 #[allow(missing_doc)]
  23 pub struct SmallIntMap<T> {
  24     v: Vec<Option<T>>,
  25 }
  26
  27 impl<V> Container for SmallIntMap<V> {
  28     /// Return the number of elements in the map
  29     fn len(&self) -> uint {
  30         self.v.iter().count(|elt| elt.is_some())
  31     }
  32
  33     /// Return true if there are no elements in the map
  34     fn is_empty(&self) -> bool {
  35         self.v.iter().all(|elt| elt.is_none())
  36     }
  37 }
  38
  39 impl<V> Mutable for SmallIntMap<V> {
  40     /// Clear the map, removing all key-value pairs.
  41     fn clear(&mut self) { self.v.clear() }
  42 }
  43
  44 impl<V> Map<uint, V> for SmallIntMap<V> {
  45     /// Return a reference to the value corresponding to the key
  46     fn find<'a>(&'a self, key: &uint) -> Option<&'a V> {
  47         if *key < self.v.len() {
  48             match *self.v.get(*key) {
  49               Some(ref value) => Some(value),
  50               None => None
  51             }
  52         } else {
  53             None
  54         }
  55     }
  56 }
  57
  58 impl<V> MutableMap<uint, V> for SmallIntMap<V> {
  59     /// Return a mutable reference to the value corresponding to the key
  60     fn find_mut<'a>(&'a mut self, key: &uint) -> Option<&'a mut V> {
  61         if *key < self.v.len() {
  62             match *self.v.get_mut(*key) {
  63               Some(ref mut value) => Some(value),
  64               None => None
  65             }
  66         } else {
  67             None
  68         }
  69     }
  70
  71     /// Insert a key-value pair into the map. An existing value for a
  72     /// key is replaced by the new value. Return true if the key did
  73     /// not already exist in the map.
  74     fn insert(&mut self, key: uint, value: V) -> bool {
  75         let exists = self.contains_key(&key);
  76         let len = self.v.len();
  77         if len <= key {
  78             self.v.grow_fn(key - len + 1, |_| None);
  79         }
  80         *self.v.get_mut(key) = Some(value);
  81         !exists
  82     }
  83
  84     /// Remove a key-value pair from the map. Return true if the key
  85     /// was present in the map, otherwise false.
  86     fn remove(&mut self, key: &uint) -> bool {
  87         self.pop(key).is_some()
  88     }
  89
  90     /// Insert a key-value pair from the map. If the key already had a value
  91     /// present in the map, that value is returned. Otherwise None is returned.
  92     fn swap(&mut self, key: uint, value: V) -> Option<V> {
  93         match self.find_mut(&key) {
  94             Some(loc) => { return Some(replace(loc, value)); }
  95             None => ()
  96         }
  97         self.insert(key, value);
  98         return None;
  99     }
 100
 101     /// Removes a key from the map, returning the value at the key if the key
 102     /// was previously in the map.
 103     fn pop(&mut self, key: &uint) -> Option<V> {
 104         if *key >= self.v.len() {
 105             return None;
 106         }
 107         self.v.get_mut(*key).take()
 108     }
 109 }
 110
 111 impl<V> SmallIntMap<V> {
 112     /// Create an empty SmallIntMap
 113     pub fn new() -> SmallIntMap<V> { SmallIntMap{v: vec!()} }
 114
 115     /// Create an empty SmallIntMap with capacity `capacity`
 116     pub fn with_capacity(capacity: uint) -> SmallIntMap<V> {
 117         SmallIntMap { v: Vec::with_capacity(capacity) }
 118     }
 119
 120     pub fn get<'a>(&'a self, key: &uint) -> &'a V {
 121         self.find(key).expect("key not present")
 122     }
 123
 124     /// An iterator visiting all key-value pairs in ascending order by the keys.
 125     /// Iterator element type is (uint, &'r V)
 126     pub fn iter<'r>(&'r self) -> Entries<'r, V> {
 127         Entries {
 128             front: 0,
 129             back: self.v.len(),
 130             iter: self.v.iter()
 131         }
 132     }
 133
 134     /// An iterator visiting all key-value pairs in ascending order by the keys,
 135     /// with mutable references to the values
 136     /// Iterator element type is (uint, &'r mut V)
 137     pub fn mut_iter<'r>(&'r mut self) -> MutEntries<'r, V> {
 138         MutEntries {
 139             front: 0,
 140             back: self.v.len(),
 141             iter: self.v.mut_iter()
 142         }
 143     }
 144
 145     /// Empties the hash map, moving all values into the specified closure
 146     pub fn move_iter(&mut self)
 147         -> FilterMap<(uint, Option<V>), (uint, V),
 148                 Enumerate<vec::MoveItems<Option<V>>>>
 149     {
 150         let values = replace(&mut self.v, vec!());
 151         values.move_iter().enumerate().filter_map(|(i, v)| {
 152             v.map(|v| (i, v))
 153         })
 154     }
 155 }
 156
 157 impl<V:Clone> SmallIntMap<V> {
 158     pub fn update_with_key(&mut self,
 159                            key: uint,
 160                            val: V,
 161                            ff: |uint, V, V| -> V)
 162                            -> bool {
 163         let new_val = match self.find(&key) {
 164             None => val,
 165             Some(orig) => ff(key, (*orig).clone(), val)
 166         };
 167         self.insert(key, new_val)
 168     }
 169
 170     pub fn update(&mut self, key: uint, newval: V, ff: |V, V| -> V) -> bool {
 171         self.update_with_key(key, newval, |_k, v, v1| ff(v,v1))
 172     }
 173 }
 174
 175
 176 macro_rules! iterator {
 177     (impl $name:ident -> $elem:ty, $getter:ident) => {
 178         impl<'a, T> Iterator<$elem> for $name<'a, T> {
 179             #[inline]
 180             fn next(&mut self) -> Option<$elem> {
 181                 while self.front < self.back {
 182                     match self.iter.next() {
 183                         Some(elem) => {
 184                             if elem.is_some() {
 185                                 let index = self.front;
 186                                 self.front += 1;
 187                                 return Some((index, elem. $getter ()));
 188                             }
 189                         }
 190                         _ => ()
 191                     }
 192                     self.front += 1;
 193                 }
 194                 None
 195             }
 196
 197             #[inline]
 198             fn size_hint(&self) -> (uint, Option<uint>) {
 199                 (0, Some(self.back - self.front))
 200             }
 201         }
 202     }
 203 }
 204
 205 macro_rules! double_ended_iterator {
 206     (impl $name:ident -> $elem:ty, $getter:ident) => {
 207         impl<'a, T> DoubleEndedIterator<$elem> for $name<'a, T> {
 208             #[inline]
 209             fn next_back(&mut self) -> Option<$elem> {
 210                 while self.front < self.back {
 211                     match self.iter.next_back() {
 212                         Some(elem) => {
 213                             if elem.is_some() {
 214                                 self.back -= 1;
 215                                 return Some((self.back, elem. $getter ()));
 216                             }
 217                         }
 218                         _ => ()
 219                     }
 220                     self.back -= 1;
 221                 }
 222                 None
 223             }
 224         }
 225     }
 226 }
 227
 228 pub struct Entries<'a, T> {
 229     front: uint,
 230     back: uint,
 231     iter: slice::Items<'a, Option<T>>
 232 }
 233
 234 iterator!(impl Entries -> (uint, &'a T), get_ref)
 235 double_ended_iterator!(impl Entries -> (uint, &'a T), get_ref)
 236
 237 pub struct MutEntries<'a, T> {
 238     front: uint,
 239     back: uint,
 240     iter: slice::MutItems<'a, Option<T>>
 241 }
 242
 243 iterator!(impl MutEntries -> (uint, &'a mut T), get_mut_ref)
 244 double_ended_iterator!(impl MutEntries -> (uint, &'a mut T), get_mut_ref)
 245
 246 #[cfg(test)]
 247 mod test_map {
 248
 249     use super::SmallIntMap;
 250
 251     #[test]
 252     fn test_find_mut() {
 253         let mut m = SmallIntMap::new();
 254         assert!(m.insert(1, 12));
 255         assert!(m.insert(2, 8));
 256         assert!(m.insert(5, 14));
 257         let new = 100;
 258         match m.find_mut(&5) {
 259             None => fail!(), Some(x) => *x = new
 260         }
 261         assert_eq!(m.find(&5), Some(&new));
 262     }
 263
 264     #[test]
 265     fn test_len() {
 266         let mut map = SmallIntMap::new();
 267         assert_eq!(map.len(), 0);
 268         assert!(map.is_empty());
 269         assert!(map.insert(5, 20));
 270         assert_eq!(map.len(), 1);
 271         assert!(!map.is_empty());
 272         assert!(map.insert(11, 12));
 273         assert_eq!(map.len(), 2);
 274         assert!(!map.is_empty());
 275         assert!(map.insert(14, 22));
 276         assert_eq!(map.len(), 3);
 277         assert!(!map.is_empty());
 278     }
 279
 280     #[test]
 281     fn test_clear() {
 282         let mut map = SmallIntMap::new();
 283         assert!(map.insert(5, 20));
 284         assert!(map.insert(11, 12));
 285         assert!(map.insert(14, 22));
 286         map.clear();
 287         assert!(map.is_empty());
 288         assert!(map.find(&5).is_none());
 289         assert!(map.find(&11).is_none());
 290         assert!(map.find(&14).is_none());
 291     }
 292
 293     #[test]
 294     fn test_insert_with_key() {
 295         let mut map = SmallIntMap::new();
 296
 297         // given a new key, initialize it with this new count,
 298         // given an existing key, add more to its count
 299         fn addMoreToCount(_k: uint, v0: uint, v1: uint) -> uint {
 300             v0 + v1
 301         }
 302
 303         fn addMoreToCount_simple(v0: uint, v1: uint) -> uint {
 304             v0 + v1
 305         }
 306
 307         // count integers
 308         map.update(3, 1, addMoreToCount_simple);
 309         map.update_with_key(9, 1, addMoreToCount);
 310         map.update(3, 7, addMoreToCount_simple);
 311         map.update_with_key(5, 3, addMoreToCount);
 312         map.update_with_key(3, 2, addMoreToCount);
 313
 314         // check the total counts
 315         assert_eq!(map.find(&3).unwrap(), &10);
 316         assert_eq!(map.find(&5).unwrap(), &3);
 317         assert_eq!(map.find(&9).unwrap(), &1);
 318
 319         // sadly, no sevens were counted
 320         assert!(map.find(&7).is_none());
 321     }
 322
 323     #[test]
 324     fn test_swap() {
 325         let mut m = SmallIntMap::new();
 326         assert_eq!(m.swap(1, 2), None);
 327         assert_eq!(m.swap(1, 3), Some(2));
 328         assert_eq!(m.swap(1, 4), Some(3));
 329     }
 330
 331     #[test]
 332     fn test_pop() {
 333         let mut m = SmallIntMap::new();
 334         m.insert(1, 2);
 335         assert_eq!(m.pop(&1), Some(2));
 336         assert_eq!(m.pop(&1), None);
 337     }
 338
 339     #[test]
 340     fn test_iterator() {
 341         let mut m = SmallIntMap::new();
 342
 343         assert!(m.insert(0, 1));
 344         assert!(m.insert(1, 2));
 345         assert!(m.insert(3, 5));
 346         assert!(m.insert(6, 10));
 347         assert!(m.insert(10, 11));
 348
 349         let mut it = m.iter();
 350         assert_eq!(it.size_hint(), (0, Some(11)));
 351         assert_eq!(it.next().unwrap(), (0, &1));
 352         assert_eq!(it.size_hint(), (0, Some(10)));
 353         assert_eq!(it.next().unwrap(), (1, &2));
 354         assert_eq!(it.size_hint(), (0, Some(9)));
 355         assert_eq!(it.next().unwrap(), (3, &5));
 356         assert_eq!(it.size_hint(), (0, Some(7)));
 357         assert_eq!(it.next().unwrap(), (6, &10));
 358         assert_eq!(it.size_hint(), (0, Some(4)));
 359         assert_eq!(it.next().unwrap(), (10, &11));
 360         assert_eq!(it.size_hint(), (0, Some(0)));
 361         assert!(it.next().is_none());
 362     }
 363
 364     #[test]
 365     fn test_iterator_size_hints() {
 366         let mut m = SmallIntMap::new();
 367
 368         assert!(m.insert(0, 1));
 369         assert!(m.insert(1, 2));
 370         assert!(m.insert(3, 5));
 371         assert!(m.insert(6, 10));
 372         assert!(m.insert(10, 11));
 373
 374         assert_eq!(m.iter().size_hint(), (0, Some(11)));
 375         assert_eq!(m.iter().rev().size_hint(), (0, Some(11)));
 376         assert_eq!(m.mut_iter().size_hint(), (0, Some(11)));
 377         assert_eq!(m.mut_iter().rev().size_hint(), (0, Some(11)));
 378     }
 379
 380     #[test]
 381     fn test_mut_iterator() {
 382         let mut m = SmallIntMap::new();
 383
 384         assert!(m.insert(0, 1));
 385         assert!(m.insert(1, 2));
 386         assert!(m.insert(3, 5));
 387         assert!(m.insert(6, 10));
 388         assert!(m.insert(10, 11));
 389
 390         for (k, v) in m.mut_iter() {
 391             *v += k as int;
 392         }
 393
 394         let mut it = m.iter();
 395         assert_eq!(it.next().unwrap(), (0, &1));
 396         assert_eq!(it.next().unwrap(), (1, &3));
 397         assert_eq!(it.next().unwrap(), (3, &8));
 398         assert_eq!(it.next().unwrap(), (6, &16));
 399         assert_eq!(it.next().unwrap(), (10, &21));
 400         assert!(it.next().is_none());
 401     }
 402
 403     #[test]
 404     fn test_rev_iterator() {
 405         let mut m = SmallIntMap::new();
 406
 407         assert!(m.insert(0, 1));
 408         assert!(m.insert(1, 2));
 409         assert!(m.insert(3, 5));
 410         assert!(m.insert(6, 10));
 411         assert!(m.insert(10, 11));
 412
 413         let mut it = m.iter().rev();
 414         assert_eq!(it.next().unwrap(), (10, &11));
 415         assert_eq!(it.next().unwrap(), (6, &10));
 416         assert_eq!(it.next().unwrap(), (3, &5));
 417         assert_eq!(it.next().unwrap(), (1, &2));
 418         assert_eq!(it.next().unwrap(), (0, &1));
 419         assert!(it.next().is_none());
 420     }
 421
 422     #[test]
 423     fn test_mut_rev_iterator() {
 424         let mut m = SmallIntMap::new();
 425
 426         assert!(m.insert(0, 1));
 427         assert!(m.insert(1, 2));
 428         assert!(m.insert(3, 5));
 429         assert!(m.insert(6, 10));
 430         assert!(m.insert(10, 11));
 431
 432         for (k, v) in m.mut_iter().rev() {
 433             *v += k as int;
 434         }
 435
 436         let mut it = m.iter();
 437         assert_eq!(it.next().unwrap(), (0, &1));
 438         assert_eq!(it.next().unwrap(), (1, &3));
 439         assert_eq!(it.next().unwrap(), (3, &8));
 440         assert_eq!(it.next().unwrap(), (6, &16));
 441         assert_eq!(it.next().unwrap(), (10, &21));
 442         assert!(it.next().is_none());
 443     }
 444
 445     #[test]
 446     fn test_move_iter() {
 447         let mut m = SmallIntMap::new();
 448         m.insert(1, box 2);
 449         let mut called = false;
 450         for (k, v) in m.move_iter() {
 451             assert!(!called);
 452             called = true;
 453             assert_eq!(k, 1);
 454             assert_eq!(v, box 2);
 455         }
 456         assert!(called);
 457         m.insert(2, box 1);
 458     }
 459 }
 460
 461 #[cfg(test)]
 462 mod bench {
 463     extern crate test;
 464     use self::test::Bencher;
 465     use super::SmallIntMap;
 466     use deque::bench::{insert_rand_n, insert_seq_n, find_rand_n, find_seq_n};
 467
 468     // Find seq
 469     #[bench]
 470     pub fn insert_rand_100(b: &mut Bencher) {
 471         let mut m : SmallIntMap<uint> = SmallIntMap::new();
 472         insert_rand_n(100, &mut m, b);
 473     }
 474
 475     #[bench]
 476     pub fn insert_rand_10_000(b: &mut Bencher) {
 477         let mut m : SmallIntMap<uint> = SmallIntMap::new();
 478         insert_rand_n(10_000, &mut m, b);
 479     }
 480
 481     // Insert seq
 482     #[bench]
 483     pub fn insert_seq_100(b: &mut Bencher) {
 484         let mut m : SmallIntMap<uint> = SmallIntMap::new();
 485         insert_seq_n(100, &mut m, b);
 486     }
 487
 488     #[bench]
 489     pub fn insert_seq_10_000(b: &mut Bencher) {
 490         let mut m : SmallIntMap<uint> = SmallIntMap::new();
 491         insert_seq_n(10_000, &mut m, b);
 492     }
 493
 494     // Find rand
 495     #[bench]
 496     pub fn find_rand_100(b: &mut Bencher) {
 497         let mut m : SmallIntMap<uint> = SmallIntMap::new();
 498         find_rand_n(100, &mut m, b);
 499     }
 500
 501     #[bench]
 502     pub fn find_rand_10_000(b: &mut Bencher) {
 503         let mut m : SmallIntMap<uint> = SmallIntMap::new();
 504         find_rand_n(10_000, &mut m, b);
 505     }
 506
 507     // Find seq
 508     #[bench]
 509     pub fn find_seq_100(b: &mut Bencher) {
 510         let mut m : SmallIntMap<uint> = SmallIntMap::new();
 511         find_seq_n(100, &mut m, b);
 512     }
 513
 514     #[bench]
 515     pub fn find_seq_10_000(b: &mut Bencher) {
 516         let mut m : SmallIntMap<uint> = SmallIntMap::new();
 517         find_seq_n(10_000, &mut m, b);
 518     }
 519 }