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, Rev};
  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     #[deprecated = "replaced by .iter().rev()"]
 146     pub fn rev_iter<'r>(&'r self) -> Rev<Entries<'r, V>> {
 147         self.iter().rev()
 148     }
 149
 150     #[deprecated = "replaced by .mut_iter().rev()"]
 151     pub fn mut_rev_iter<'r>(&'r mut self) -> Rev<MutEntries<'r, V>> {
 152         self.mut_iter().rev()
 153     }
 154
 155     /// Empties the hash map, moving all values into the specified closure
 156     pub fn move_iter(&mut self)
 157         -> FilterMap<(uint, Option<V>), (uint, V),
 158                 Enumerate<vec::MoveItems<Option<V>>>>
 159     {
 160         let values = replace(&mut self.v, vec!());
 161         values.move_iter().enumerate().filter_map(|(i, v)| {
 162             v.map(|v| (i, v))
 163         })
 164     }
 165 }
 166
 167 impl<V:Clone> SmallIntMap<V> {
 168     pub fn update_with_key(&mut self,
 169                            key: uint,
 170                            val: V,
 171                            ff: |uint, V, V| -> V)
 172                            -> bool {
 173         let new_val = match self.find(&key) {
 174             None => val,
 175             Some(orig) => ff(key, (*orig).clone(), val)
 176         };
 177         self.insert(key, new_val)
 178     }
 179
 180     pub fn update(&mut self, key: uint, newval: V, ff: |V, V| -> V) -> bool {
 181         self.update_with_key(key, newval, |_k, v, v1| ff(v,v1))
 182     }
 183 }
 184
 185
 186 macro_rules! iterator {
 187     (impl $name:ident -> $elem:ty, $getter:ident) => {
 188         impl<'a, T> Iterator<$elem> for $name<'a, T> {
 189             #[inline]
 190             fn next(&mut self) -> Option<$elem> {
 191                 while self.front < self.back {
 192                     match self.iter.next() {
 193                         Some(elem) => {
 194                             if elem.is_some() {
 195                                 let index = self.front;
 196                                 self.front += 1;
 197                                 return Some((index, elem. $getter ()));
 198                             }
 199                         }
 200                         _ => ()
 201                     }
 202                     self.front += 1;
 203                 }
 204                 None
 205             }
 206
 207             #[inline]
 208             fn size_hint(&self) -> (uint, Option<uint>) {
 209                 (0, Some(self.back - self.front))
 210             }
 211         }
 212     }
 213 }
 214
 215 macro_rules! double_ended_iterator {
 216     (impl $name:ident -> $elem:ty, $getter:ident) => {
 217         impl<'a, T> DoubleEndedIterator<$elem> for $name<'a, T> {
 218             #[inline]
 219             fn next_back(&mut self) -> Option<$elem> {
 220                 while self.front < self.back {
 221                     match self.iter.next_back() {
 222                         Some(elem) => {
 223                             if elem.is_some() {
 224                                 self.back -= 1;
 225                                 return Some((self.back, elem. $getter ()));
 226                             }
 227                         }
 228                         _ => ()
 229                     }
 230                     self.back -= 1;
 231                 }
 232                 None
 233             }
 234         }
 235     }
 236 }
 237
 238 pub struct Entries<'a, T> {
 239     front: uint,
 240     back: uint,
 241     iter: slice::Items<'a, Option<T>>
 242 }
 243
 244 iterator!(impl Entries -> (uint, &'a T), get_ref)
 245 double_ended_iterator!(impl Entries -> (uint, &'a T), get_ref)
 246 #[deprecated = "replaced by Rev<Entries<'a, T>>"]
 247 pub type RevEntries<'a, T> = Rev<Entries<'a, T>>;
 248
 249 pub struct MutEntries<'a, T> {
 250     front: uint,
 251     back: uint,
 252     iter: slice::MutItems<'a, Option<T>>
 253 }
 254
 255 iterator!(impl MutEntries -> (uint, &'a mut T), get_mut_ref)
 256 double_ended_iterator!(impl MutEntries -> (uint, &'a mut T), get_mut_ref)
 257 #[deprecated = "replaced by Rev<MutEntries<'a, T>"]
 258 pub type RevMutEntries<'a, T> = Rev<MutEntries<'a, T>>;
 259
 260 #[cfg(test)]
 261 mod test_map {
 262
 263     use super::SmallIntMap;
 264
 265     #[test]
 266     fn test_find_mut() {
 267         let mut m = SmallIntMap::new();
 268         assert!(m.insert(1, 12));
 269         assert!(m.insert(2, 8));
 270         assert!(m.insert(5, 14));
 271         let new = 100;
 272         match m.find_mut(&5) {
 273             None => fail!(), Some(x) => *x = new
 274         }
 275         assert_eq!(m.find(&5), Some(&new));
 276     }
 277
 278     #[test]
 279     fn test_len() {
 280         let mut map = SmallIntMap::new();
 281         assert_eq!(map.len(), 0);
 282         assert!(map.is_empty());
 283         assert!(map.insert(5, 20));
 284         assert_eq!(map.len(), 1);
 285         assert!(!map.is_empty());
 286         assert!(map.insert(11, 12));
 287         assert_eq!(map.len(), 2);
 288         assert!(!map.is_empty());
 289         assert!(map.insert(14, 22));
 290         assert_eq!(map.len(), 3);
 291         assert!(!map.is_empty());
 292     }
 293
 294     #[test]
 295     fn test_clear() {
 296         let mut map = SmallIntMap::new();
 297         assert!(map.insert(5, 20));
 298         assert!(map.insert(11, 12));
 299         assert!(map.insert(14, 22));
 300         map.clear();
 301         assert!(map.is_empty());
 302         assert!(map.find(&5).is_none());
 303         assert!(map.find(&11).is_none());
 304         assert!(map.find(&14).is_none());
 305     }
 306
 307     #[test]
 308     fn test_insert_with_key() {
 309         let mut map = SmallIntMap::new();
 310
 311         // given a new key, initialize it with this new count,
 312         // given an existing key, add more to its count
 313         fn addMoreToCount(_k: uint, v0: uint, v1: uint) -> uint {
 314             v0 + v1
 315         }
 316
 317         fn addMoreToCount_simple(v0: uint, v1: uint) -> uint {
 318             v0 + v1
 319         }
 320
 321         // count integers
 322         map.update(3, 1, addMoreToCount_simple);
 323         map.update_with_key(9, 1, addMoreToCount);
 324         map.update(3, 7, addMoreToCount_simple);
 325         map.update_with_key(5, 3, addMoreToCount);
 326         map.update_with_key(3, 2, addMoreToCount);
 327
 328         // check the total counts
 329         assert_eq!(map.find(&3).unwrap(), &10);
 330         assert_eq!(map.find(&5).unwrap(), &3);
 331         assert_eq!(map.find(&9).unwrap(), &1);
 332
 333         // sadly, no sevens were counted
 334         assert!(map.find(&7).is_none());
 335     }
 336
 337     #[test]
 338     fn test_swap() {
 339         let mut m = SmallIntMap::new();
 340         assert_eq!(m.swap(1, 2), None);
 341         assert_eq!(m.swap(1, 3), Some(2));
 342         assert_eq!(m.swap(1, 4), Some(3));
 343     }
 344
 345     #[test]
 346     fn test_pop() {
 347         let mut m = SmallIntMap::new();
 348         m.insert(1, 2);
 349         assert_eq!(m.pop(&1), Some(2));
 350         assert_eq!(m.pop(&1), None);
 351     }
 352
 353     #[test]
 354     fn test_iterator() {
 355         let mut m = SmallIntMap::new();
 356
 357         assert!(m.insert(0, 1));
 358         assert!(m.insert(1, 2));
 359         assert!(m.insert(3, 5));
 360         assert!(m.insert(6, 10));
 361         assert!(m.insert(10, 11));
 362
 363         let mut it = m.iter();
 364         assert_eq!(it.size_hint(), (0, Some(11)));
 365         assert_eq!(it.next().unwrap(), (0, &1));
 366         assert_eq!(it.size_hint(), (0, Some(10)));
 367         assert_eq!(it.next().unwrap(), (1, &2));
 368         assert_eq!(it.size_hint(), (0, Some(9)));
 369         assert_eq!(it.next().unwrap(), (3, &5));
 370         assert_eq!(it.size_hint(), (0, Some(7)));
 371         assert_eq!(it.next().unwrap(), (6, &10));
 372         assert_eq!(it.size_hint(), (0, Some(4)));
 373         assert_eq!(it.next().unwrap(), (10, &11));
 374         assert_eq!(it.size_hint(), (0, Some(0)));
 375         assert!(it.next().is_none());
 376     }
 377
 378     #[test]
 379     fn test_iterator_size_hints() {
 380         let mut m = SmallIntMap::new();
 381
 382         assert!(m.insert(0, 1));
 383         assert!(m.insert(1, 2));
 384         assert!(m.insert(3, 5));
 385         assert!(m.insert(6, 10));
 386         assert!(m.insert(10, 11));
 387
 388         assert_eq!(m.iter().size_hint(), (0, Some(11)));
 389         assert_eq!(m.iter().rev().size_hint(), (0, Some(11)));
 390         assert_eq!(m.mut_iter().size_hint(), (0, Some(11)));
 391         assert_eq!(m.mut_iter().rev().size_hint(), (0, Some(11)));
 392     }
 393
 394     #[test]
 395     fn test_mut_iterator() {
 396         let mut m = SmallIntMap::new();
 397
 398         assert!(m.insert(0, 1));
 399         assert!(m.insert(1, 2));
 400         assert!(m.insert(3, 5));
 401         assert!(m.insert(6, 10));
 402         assert!(m.insert(10, 11));
 403
 404         for (k, v) in m.mut_iter() {
 405             *v += k as int;
 406         }
 407
 408         let mut it = m.iter();
 409         assert_eq!(it.next().unwrap(), (0, &1));
 410         assert_eq!(it.next().unwrap(), (1, &3));
 411         assert_eq!(it.next().unwrap(), (3, &8));
 412         assert_eq!(it.next().unwrap(), (6, &16));
 413         assert_eq!(it.next().unwrap(), (10, &21));
 414         assert!(it.next().is_none());
 415     }
 416
 417     #[test]
 418     fn test_rev_iterator() {
 419         let mut m = SmallIntMap::new();
 420
 421         assert!(m.insert(0, 1));
 422         assert!(m.insert(1, 2));
 423         assert!(m.insert(3, 5));
 424         assert!(m.insert(6, 10));
 425         assert!(m.insert(10, 11));
 426
 427         let mut it = m.iter().rev();
 428         assert_eq!(it.next().unwrap(), (10, &11));
 429         assert_eq!(it.next().unwrap(), (6, &10));
 430         assert_eq!(it.next().unwrap(), (3, &5));
 431         assert_eq!(it.next().unwrap(), (1, &2));
 432         assert_eq!(it.next().unwrap(), (0, &1));
 433         assert!(it.next().is_none());
 434     }
 435
 436     #[test]
 437     fn test_mut_rev_iterator() {
 438         let mut m = SmallIntMap::new();
 439
 440         assert!(m.insert(0, 1));
 441         assert!(m.insert(1, 2));
 442         assert!(m.insert(3, 5));
 443         assert!(m.insert(6, 10));
 444         assert!(m.insert(10, 11));
 445
 446         for (k, v) in m.mut_iter().rev() {
 447             *v += k as int;
 448         }
 449
 450         let mut it = m.iter();
 451         assert_eq!(it.next().unwrap(), (0, &1));
 452         assert_eq!(it.next().unwrap(), (1, &3));
 453         assert_eq!(it.next().unwrap(), (3, &8));
 454         assert_eq!(it.next().unwrap(), (6, &16));
 455         assert_eq!(it.next().unwrap(), (10, &21));
 456         assert!(it.next().is_none());
 457     }
 458
 459     #[test]
 460     fn test_move_iter() {
 461         let mut m = SmallIntMap::new();
 462         m.insert(1, box 2);
 463         let mut called = false;
 464         for (k, v) in m.move_iter() {
 465             assert!(!called);
 466             called = true;
 467             assert_eq!(k, 1);
 468             assert_eq!(v, box 2);
 469         }
 470         assert!(called);
 471         m.insert(2, box 1);
 472     }
 473 }
 474
 475 #[cfg(test)]
 476 mod bench {
 477     extern crate test;
 478     use self::test::Bencher;
 479     use super::SmallIntMap;
 480     use deque::bench::{insert_rand_n, insert_seq_n, find_rand_n, find_seq_n};
 481
 482     // Find seq
 483     #[bench]
 484     pub fn insert_rand_100(b: &mut Bencher) {
 485         let mut m : SmallIntMap<uint> = SmallIntMap::new();
 486         insert_rand_n(100, &mut m, b);
 487     }
 488
 489     #[bench]
 490     pub fn insert_rand_10_000(b: &mut Bencher) {
 491         let mut m : SmallIntMap<uint> = SmallIntMap::new();
 492         insert_rand_n(10_000, &mut m, b);
 493     }
 494
 495     // Insert seq
 496     #[bench]
 497     pub fn insert_seq_100(b: &mut Bencher) {
 498         let mut m : SmallIntMap<uint> = SmallIntMap::new();
 499         insert_seq_n(100, &mut m, b);
 500     }
 501
 502     #[bench]
 503     pub fn insert_seq_10_000(b: &mut Bencher) {
 504         let mut m : SmallIntMap<uint> = SmallIntMap::new();
 505         insert_seq_n(10_000, &mut m, b);
 506     }
 507
 508     // Find rand
 509     #[bench]
 510     pub fn find_rand_100(b: &mut Bencher) {
 511         let mut m : SmallIntMap<uint> = SmallIntMap::new();
 512         find_rand_n(100, &mut m, b);
 513     }
 514
 515     #[bench]
 516     pub fn find_rand_10_000(b: &mut Bencher) {
 517         let mut m : SmallIntMap<uint> = SmallIntMap::new();
 518         find_rand_n(10_000, &mut m, b);
 519     }
 520
 521     // Find seq
 522     #[bench]
 523     pub fn find_seq_100(b: &mut Bencher) {
 524         let mut m : SmallIntMap<uint> = SmallIntMap::new();
 525         find_seq_n(100, &mut m, b);
 526     }
 527
 528     #[bench]
 529     pub fn find_seq_10_000(b: &mut Bencher) {
 530         let mut m : SmallIntMap<uint> = SmallIntMap::new();
 531         find_seq_n(10_000, &mut m, b);
 532     }
 533 }