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 }
libcollections/smallintmap.rs:22:22-22:22 -struct- definition:
pub struct SmallIntMap<T> {
v: Vec<Option<T>>,
}
references:- 10112: /// Create an empty SmallIntMap
113: pub fn new() -> SmallIntMap<V> { SmallIntMap{v: vec!()} }
--
116: pub fn with_capacity(capacity: uint) -> SmallIntMap<V> {
117: SmallIntMap { v: Vec::with_capacity(capacity) }
118: }
--
167: impl<V:Clone> SmallIntMap<V> {
168: pub fn update_with_key(&mut self,
libcollections/smallintmap.rs:248:1-248:1 -struct- definition:
pub struct MutEntries<'a, T> {
front: uint,
back: uint,
references:- 6137: pub fn mut_iter<'r>(&'r mut self) -> MutEntries<'r, V> {
138: MutEntries {
139: front: 0,
--
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()
--
258: pub type RevMutEntries<'a, T> = Rev<MutEntries<'a, T>>;
libcollections/smallintmap.rs:237:1-237:1 -struct- definition:
pub struct Entries<'a, T> {
front: uint,
back: uint,
references:- 6126: pub fn iter<'r>(&'r self) -> Entries<'r, V> {
127: Entries {
128: front: 0,
--
145: #[deprecated = "replaced by .iter().rev()"]
146: pub fn rev_iter<'r>(&'r self) -> Rev<Entries<'r, V>> {
147: self.iter().rev()
--
247: pub type RevEntries<'a, T> = Rev<Entries<'a, T>>;