]>
Commit | Line | Data |
---|---|---|
1a4d82fc JJ |
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 | //! A simple map based on a vector for small integer keys. Space requirements | |
12 | //! are O(highest integer key). | |
13 | ||
14 | #![allow(missing_docs)] | |
62682a34 SL |
15 | #![unstable(feature = "vecmap", |
16 | reason = "may not be stabilized in the standard library")] | |
1a4d82fc | 17 | |
85aaf69f SL |
18 | use self::Entry::*; |
19 | ||
1a4d82fc JJ |
20 | use core::prelude::*; |
21 | ||
c34b1796 | 22 | use core::cmp::{max, Ordering}; |
1a4d82fc | 23 | use core::fmt; |
85aaf69f | 24 | use core::hash::{Hash, Hasher}; |
9346a6ac | 25 | use core::iter::{Enumerate, FilterMap, Map, FromIterator}; |
1a4d82fc | 26 | use core::iter; |
c34b1796 | 27 | use core::mem::{replace, swap}; |
1a4d82fc JJ |
28 | use core::ops::{Index, IndexMut}; |
29 | ||
30 | use {vec, slice}; | |
31 | use vec::Vec; | |
32 | ||
1a4d82fc JJ |
33 | /// A map optimized for small integer keys. |
34 | /// | |
35 | /// # Examples | |
36 | /// | |
37 | /// ``` | |
62682a34 | 38 | /// # #![feature(vecmap)] |
1a4d82fc JJ |
39 | /// use std::collections::VecMap; |
40 | /// | |
41 | /// let mut months = VecMap::new(); | |
42 | /// months.insert(1, "Jan"); | |
43 | /// months.insert(2, "Feb"); | |
44 | /// months.insert(3, "Mar"); | |
45 | /// | |
46 | /// if !months.contains_key(&12) { | |
47 | /// println!("The end is near!"); | |
48 | /// } | |
49 | /// | |
50 | /// assert_eq!(months.get(&1), Some(&"Jan")); | |
51 | /// | |
9346a6ac AL |
52 | /// if let Some(value) = months.get_mut(&3) { |
53 | /// *value = "Venus"; | |
1a4d82fc JJ |
54 | /// } |
55 | /// | |
56 | /// assert_eq!(months.get(&3), Some(&"Venus")); | |
57 | /// | |
58 | /// // Print out all months | |
62682a34 | 59 | /// for (key, value) in &months { |
1a4d82fc JJ |
60 | /// println!("month {} is {}", key, value); |
61 | /// } | |
62 | /// | |
63 | /// months.clear(); | |
64 | /// assert!(months.is_empty()); | |
65 | /// ``` | |
66 | pub struct VecMap<V> { | |
67 | v: Vec<Option<V>>, | |
68 | } | |
69 | ||
85aaf69f | 70 | /// A view into a single entry in a map, which may either be vacant or occupied. |
c34b1796 AL |
71 | |
72 | #[stable(feature = "rust1", since = "1.0.0")] | |
85aaf69f SL |
73 | pub enum Entry<'a, V:'a> { |
74 | /// A vacant Entry | |
c34b1796 | 75 | #[stable(feature = "rust1", since = "1.0.0")] |
85aaf69f | 76 | Vacant(VacantEntry<'a, V>), |
c34b1796 | 77 | |
85aaf69f | 78 | /// An occupied Entry |
c34b1796 | 79 | #[stable(feature = "rust1", since = "1.0.0")] |
85aaf69f SL |
80 | Occupied(OccupiedEntry<'a, V>), |
81 | } | |
82 | ||
83 | /// A vacant Entry. | |
c34b1796 AL |
84 | |
85 | #[stable(feature = "rust1", since = "1.0.0")] | |
85aaf69f SL |
86 | pub struct VacantEntry<'a, V:'a> { |
87 | map: &'a mut VecMap<V>, | |
88 | index: usize, | |
89 | } | |
90 | ||
91 | /// An occupied Entry. | |
c34b1796 | 92 | #[stable(feature = "rust1", since = "1.0.0")] |
85aaf69f SL |
93 | pub struct OccupiedEntry<'a, V:'a> { |
94 | map: &'a mut VecMap<V>, | |
95 | index: usize, | |
96 | } | |
97 | ||
98 | #[stable(feature = "rust1", since = "1.0.0")] | |
1a4d82fc | 99 | impl<V> Default for VecMap<V> { |
85aaf69f | 100 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
101 | #[inline] |
102 | fn default() -> VecMap<V> { VecMap::new() } | |
103 | } | |
104 | ||
85aaf69f | 105 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
106 | impl<V:Clone> Clone for VecMap<V> { |
107 | #[inline] | |
108 | fn clone(&self) -> VecMap<V> { | |
109 | VecMap { v: self.v.clone() } | |
110 | } | |
111 | ||
112 | #[inline] | |
113 | fn clone_from(&mut self, source: &VecMap<V>) { | |
114 | self.v.clone_from(&source.v); | |
115 | } | |
116 | } | |
117 | ||
85aaf69f | 118 | #[stable(feature = "rust1", since = "1.0.0")] |
85aaf69f SL |
119 | impl<V: Hash> Hash for VecMap<V> { |
120 | fn hash<H: Hasher>(&self, state: &mut H) { | |
121 | // In order to not traverse the `VecMap` twice, count the elements | |
122 | // during iteration. | |
123 | let mut count: usize = 0; | |
124 | for elt in self { | |
1a4d82fc JJ |
125 | elt.hash(state); |
126 | count += 1; | |
127 | } | |
128 | count.hash(state); | |
129 | } | |
130 | } | |
131 | ||
132 | impl<V> VecMap<V> { | |
133 | /// Creates an empty `VecMap`. | |
134 | /// | |
135 | /// # Examples | |
136 | /// | |
137 | /// ``` | |
62682a34 | 138 | /// # #![feature(vecmap)] |
1a4d82fc JJ |
139 | /// use std::collections::VecMap; |
140 | /// let mut map: VecMap<&str> = VecMap::new(); | |
141 | /// ``` | |
85aaf69f | 142 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
143 | pub fn new() -> VecMap<V> { VecMap { v: vec![] } } |
144 | ||
145 | /// Creates an empty `VecMap` with space for at least `capacity` | |
146 | /// elements before resizing. | |
147 | /// | |
148 | /// # Examples | |
149 | /// | |
150 | /// ``` | |
62682a34 | 151 | /// # #![feature(vecmap)] |
1a4d82fc JJ |
152 | /// use std::collections::VecMap; |
153 | /// let mut map: VecMap<&str> = VecMap::with_capacity(10); | |
154 | /// ``` | |
85aaf69f SL |
155 | #[stable(feature = "rust1", since = "1.0.0")] |
156 | pub fn with_capacity(capacity: usize) -> VecMap<V> { | |
1a4d82fc JJ |
157 | VecMap { v: Vec::with_capacity(capacity) } |
158 | } | |
159 | ||
160 | /// Returns the number of elements the `VecMap` can hold without | |
161 | /// reallocating. | |
162 | /// | |
163 | /// # Examples | |
164 | /// | |
165 | /// ``` | |
62682a34 | 166 | /// # #![feature(vecmap)] |
1a4d82fc JJ |
167 | /// use std::collections::VecMap; |
168 | /// let map: VecMap<String> = VecMap::with_capacity(10); | |
169 | /// assert!(map.capacity() >= 10); | |
170 | /// ``` | |
171 | #[inline] | |
85aaf69f SL |
172 | #[stable(feature = "rust1", since = "1.0.0")] |
173 | pub fn capacity(&self) -> usize { | |
1a4d82fc JJ |
174 | self.v.capacity() |
175 | } | |
176 | ||
177 | /// Reserves capacity for the given `VecMap` to contain `len` distinct keys. | |
178 | /// In the case of `VecMap` this means reallocations will not occur as long | |
179 | /// as all inserted keys are less than `len`. | |
180 | /// | |
181 | /// The collection may reserve more space to avoid frequent reallocations. | |
182 | /// | |
183 | /// # Examples | |
184 | /// | |
185 | /// ``` | |
62682a34 | 186 | /// # #![feature(vecmap)] |
1a4d82fc JJ |
187 | /// use std::collections::VecMap; |
188 | /// let mut map: VecMap<&str> = VecMap::new(); | |
189 | /// map.reserve_len(10); | |
190 | /// assert!(map.capacity() >= 10); | |
191 | /// ``` | |
85aaf69f SL |
192 | #[stable(feature = "rust1", since = "1.0.0")] |
193 | pub fn reserve_len(&mut self, len: usize) { | |
1a4d82fc JJ |
194 | let cur_len = self.v.len(); |
195 | if len >= cur_len { | |
196 | self.v.reserve(len - cur_len); | |
197 | } | |
198 | } | |
199 | ||
200 | /// Reserves the minimum capacity for the given `VecMap` to contain `len` distinct keys. | |
201 | /// In the case of `VecMap` this means reallocations will not occur as long as all inserted | |
202 | /// keys are less than `len`. | |
203 | /// | |
204 | /// Note that the allocator may give the collection more space than it requests. | |
205 | /// Therefore capacity cannot be relied upon to be precisely minimal. Prefer | |
206 | /// `reserve_len` if future insertions are expected. | |
207 | /// | |
208 | /// # Examples | |
209 | /// | |
210 | /// ``` | |
62682a34 | 211 | /// # #![feature(vecmap)] |
1a4d82fc JJ |
212 | /// use std::collections::VecMap; |
213 | /// let mut map: VecMap<&str> = VecMap::new(); | |
214 | /// map.reserve_len_exact(10); | |
215 | /// assert!(map.capacity() >= 10); | |
216 | /// ``` | |
85aaf69f SL |
217 | #[stable(feature = "rust1", since = "1.0.0")] |
218 | pub fn reserve_len_exact(&mut self, len: usize) { | |
1a4d82fc JJ |
219 | let cur_len = self.v.len(); |
220 | if len >= cur_len { | |
221 | self.v.reserve_exact(len - cur_len); | |
222 | } | |
223 | } | |
224 | ||
85aaf69f SL |
225 | /// Returns an iterator visiting all keys in ascending order of the keys. |
226 | /// The iterator's element type is `usize`. | |
227 | #[stable(feature = "rust1", since = "1.0.0")] | |
1a4d82fc JJ |
228 | pub fn keys<'r>(&'r self) -> Keys<'r, V> { |
229 | fn first<A, B>((a, _): (A, B)) -> A { a } | |
85aaf69f | 230 | let first: fn((usize, &'r V)) -> usize = first; // coerce to fn pointer |
1a4d82fc JJ |
231 | |
232 | Keys { iter: self.iter().map(first) } | |
233 | } | |
234 | ||
85aaf69f | 235 | /// Returns an iterator visiting all values in ascending order of the keys. |
1a4d82fc | 236 | /// The iterator's element type is `&'r V`. |
85aaf69f | 237 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
238 | pub fn values<'r>(&'r self) -> Values<'r, V> { |
239 | fn second<A, B>((_, b): (A, B)) -> B { b } | |
85aaf69f | 240 | let second: fn((usize, &'r V)) -> &'r V = second; // coerce to fn pointer |
1a4d82fc JJ |
241 | |
242 | Values { iter: self.iter().map(second) } | |
243 | } | |
244 | ||
85aaf69f SL |
245 | /// Returns an iterator visiting all key-value pairs in ascending order of the keys. |
246 | /// The iterator's element type is `(usize, &'r V)`. | |
1a4d82fc JJ |
247 | /// |
248 | /// # Examples | |
249 | /// | |
250 | /// ``` | |
62682a34 | 251 | /// # #![feature(vecmap)] |
1a4d82fc JJ |
252 | /// use std::collections::VecMap; |
253 | /// | |
254 | /// let mut map = VecMap::new(); | |
255 | /// map.insert(1, "a"); | |
256 | /// map.insert(3, "c"); | |
257 | /// map.insert(2, "b"); | |
258 | /// | |
259 | /// // Print `1: a` then `2: b` then `3: c` | |
260 | /// for (key, value) in map.iter() { | |
261 | /// println!("{}: {}", key, value); | |
262 | /// } | |
263 | /// ``` | |
85aaf69f | 264 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
265 | pub fn iter<'r>(&'r self) -> Iter<'r, V> { |
266 | Iter { | |
267 | front: 0, | |
268 | back: self.v.len(), | |
269 | iter: self.v.iter() | |
270 | } | |
271 | } | |
272 | ||
85aaf69f | 273 | /// Returns an iterator visiting all key-value pairs in ascending order of the keys, |
1a4d82fc | 274 | /// with mutable references to the values. |
85aaf69f | 275 | /// The iterator's element type is `(usize, &'r mut V)`. |
1a4d82fc JJ |
276 | /// |
277 | /// # Examples | |
278 | /// | |
279 | /// ``` | |
62682a34 | 280 | /// # #![feature(vecmap)] |
1a4d82fc JJ |
281 | /// use std::collections::VecMap; |
282 | /// | |
283 | /// let mut map = VecMap::new(); | |
284 | /// map.insert(1, "a"); | |
285 | /// map.insert(2, "b"); | |
286 | /// map.insert(3, "c"); | |
287 | /// | |
288 | /// for (key, value) in map.iter_mut() { | |
289 | /// *value = "x"; | |
290 | /// } | |
291 | /// | |
62682a34 | 292 | /// for (key, value) in &map { |
1a4d82fc JJ |
293 | /// assert_eq!(value, &"x"); |
294 | /// } | |
295 | /// ``` | |
85aaf69f | 296 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
297 | pub fn iter_mut<'r>(&'r mut self) -> IterMut<'r, V> { |
298 | IterMut { | |
299 | front: 0, | |
300 | back: self.v.len(), | |
301 | iter: self.v.iter_mut() | |
302 | } | |
303 | } | |
304 | ||
c34b1796 AL |
305 | /// Moves all elements from `other` into the map while overwriting existing keys. |
306 | /// | |
307 | /// # Examples | |
308 | /// | |
309 | /// ``` | |
62682a34 | 310 | /// # #![feature(vecmap, append)] |
c34b1796 AL |
311 | /// use std::collections::VecMap; |
312 | /// | |
313 | /// let mut a = VecMap::new(); | |
314 | /// a.insert(1, "a"); | |
315 | /// a.insert(2, "b"); | |
316 | /// | |
317 | /// let mut b = VecMap::new(); | |
318 | /// b.insert(3, "c"); | |
319 | /// b.insert(4, "d"); | |
320 | /// | |
321 | /// a.append(&mut b); | |
322 | /// | |
323 | /// assert_eq!(a.len(), 4); | |
324 | /// assert_eq!(b.len(), 0); | |
325 | /// assert_eq!(a[1], "a"); | |
326 | /// assert_eq!(a[2], "b"); | |
327 | /// assert_eq!(a[3], "c"); | |
328 | /// assert_eq!(a[4], "d"); | |
329 | /// ``` | |
62682a34 | 330 | #[unstable(feature = "append", |
c34b1796 AL |
331 | reason = "recently added as part of collections reform 2")] |
332 | pub fn append(&mut self, other: &mut Self) { | |
333 | self.extend(other.drain()); | |
334 | } | |
335 | ||
336 | /// Splits the collection into two at the given key. | |
337 | /// | |
338 | /// Returns a newly allocated `Self`. `self` contains elements `[0, at)`, | |
339 | /// and the returned `Self` contains elements `[at, max_key)`. | |
340 | /// | |
341 | /// Note that the capacity of `self` does not change. | |
342 | /// | |
343 | /// # Examples | |
344 | /// | |
345 | /// ``` | |
62682a34 | 346 | /// # #![feature(vecmap, split_off)] |
c34b1796 AL |
347 | /// use std::collections::VecMap; |
348 | /// | |
349 | /// let mut a = VecMap::new(); | |
350 | /// a.insert(1, "a"); | |
351 | /// a.insert(2, "b"); | |
352 | /// a.insert(3, "c"); | |
353 | /// a.insert(4, "d"); | |
354 | /// | |
355 | /// let b = a.split_off(3); | |
356 | /// | |
357 | /// assert_eq!(a[1], "a"); | |
358 | /// assert_eq!(a[2], "b"); | |
359 | /// | |
360 | /// assert_eq!(b[3], "c"); | |
361 | /// assert_eq!(b[4], "d"); | |
362 | /// ``` | |
62682a34 | 363 | #[unstable(feature = "split_off", |
c34b1796 AL |
364 | reason = "recently added as part of collections reform 2")] |
365 | pub fn split_off(&mut self, at: usize) -> Self { | |
366 | let mut other = VecMap::new(); | |
367 | ||
368 | if at == 0 { | |
369 | // Move all elements to other | |
370 | swap(self, &mut other); | |
371 | return other | |
d9579d0f | 372 | } else if at >= self.v.len() { |
c34b1796 AL |
373 | // No elements to copy |
374 | return other; | |
375 | } | |
376 | ||
377 | // Look up the index of the first non-None item | |
378 | let first_index = self.v.iter().position(|el| el.is_some()); | |
379 | let start_index = match first_index { | |
380 | Some(index) => max(at, index), | |
381 | None => { | |
382 | // self has no elements | |
383 | return other; | |
384 | } | |
385 | }; | |
386 | ||
387 | // Fill the new VecMap with `None`s until `start_index` | |
388 | other.v.extend((0..start_index).map(|_| None)); | |
389 | ||
390 | // Move elements beginning with `start_index` from `self` into `other` | |
391 | other.v.extend(self.v[start_index..].iter_mut().map(|el| el.take())); | |
392 | ||
393 | other | |
394 | } | |
395 | ||
85aaf69f | 396 | /// Returns an iterator visiting all key-value pairs in ascending order of |
1a4d82fc | 397 | /// the keys, emptying (but not consuming) the original `VecMap`. |
85aaf69f | 398 | /// The iterator's element type is `(usize, &'r V)`. Keeps the allocated memory for reuse. |
1a4d82fc JJ |
399 | /// |
400 | /// # Examples | |
401 | /// | |
402 | /// ``` | |
62682a34 | 403 | /// # #![feature(vecmap, drain)] |
1a4d82fc JJ |
404 | /// use std::collections::VecMap; |
405 | /// | |
406 | /// let mut map = VecMap::new(); | |
407 | /// map.insert(1, "a"); | |
408 | /// map.insert(3, "c"); | |
409 | /// map.insert(2, "b"); | |
410 | /// | |
85aaf69f | 411 | /// let vec: Vec<(usize, &str)> = map.drain().collect(); |
1a4d82fc | 412 | /// |
c34b1796 | 413 | /// assert_eq!(vec, [(1, "a"), (2, "b"), (3, "c")]); |
1a4d82fc | 414 | /// ``` |
62682a34 | 415 | #[unstable(feature = "drain", |
85aaf69f SL |
416 | reason = "matches collection reform specification, waiting for dust to settle")] |
417 | pub fn drain<'a>(&'a mut self) -> Drain<'a, V> { | |
418 | fn filter<A>((i, v): (usize, Option<A>)) -> Option<(usize, A)> { | |
1a4d82fc JJ |
419 | v.map(|v| (i, v)) |
420 | } | |
85aaf69f | 421 | let filter: fn((usize, Option<V>)) -> Option<(usize, V)> = filter; // coerce to fn ptr |
1a4d82fc | 422 | |
d9579d0f | 423 | Drain { iter: self.v.drain(..).enumerate().filter_map(filter) } |
1a4d82fc JJ |
424 | } |
425 | ||
9346a6ac | 426 | /// Returns the number of elements in the map. |
1a4d82fc JJ |
427 | /// |
428 | /// # Examples | |
429 | /// | |
430 | /// ``` | |
62682a34 | 431 | /// # #![feature(vecmap)] |
1a4d82fc JJ |
432 | /// use std::collections::VecMap; |
433 | /// | |
434 | /// let mut a = VecMap::new(); | |
435 | /// assert_eq!(a.len(), 0); | |
436 | /// a.insert(1, "a"); | |
437 | /// assert_eq!(a.len(), 1); | |
438 | /// ``` | |
85aaf69f SL |
439 | #[stable(feature = "rust1", since = "1.0.0")] |
440 | pub fn len(&self) -> usize { | |
1a4d82fc JJ |
441 | self.v.iter().filter(|elt| elt.is_some()).count() |
442 | } | |
443 | ||
9346a6ac | 444 | /// Returns true if the map contains no elements. |
1a4d82fc JJ |
445 | /// |
446 | /// # Examples | |
447 | /// | |
448 | /// ``` | |
62682a34 | 449 | /// # #![feature(vecmap)] |
1a4d82fc JJ |
450 | /// use std::collections::VecMap; |
451 | /// | |
452 | /// let mut a = VecMap::new(); | |
453 | /// assert!(a.is_empty()); | |
454 | /// a.insert(1, "a"); | |
455 | /// assert!(!a.is_empty()); | |
456 | /// ``` | |
85aaf69f | 457 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
458 | pub fn is_empty(&self) -> bool { |
459 | self.v.iter().all(|elt| elt.is_none()) | |
460 | } | |
461 | ||
462 | /// Clears the map, removing all key-value pairs. | |
463 | /// | |
464 | /// # Examples | |
465 | /// | |
466 | /// ``` | |
62682a34 | 467 | /// # #![feature(vecmap)] |
1a4d82fc JJ |
468 | /// use std::collections::VecMap; |
469 | /// | |
470 | /// let mut a = VecMap::new(); | |
471 | /// a.insert(1, "a"); | |
472 | /// a.clear(); | |
473 | /// assert!(a.is_empty()); | |
474 | /// ``` | |
85aaf69f | 475 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
476 | pub fn clear(&mut self) { self.v.clear() } |
477 | ||
478 | /// Returns a reference to the value corresponding to the key. | |
479 | /// | |
480 | /// # Examples | |
481 | /// | |
482 | /// ``` | |
62682a34 | 483 | /// # #![feature(vecmap)] |
1a4d82fc JJ |
484 | /// use std::collections::VecMap; |
485 | /// | |
486 | /// let mut map = VecMap::new(); | |
487 | /// map.insert(1, "a"); | |
488 | /// assert_eq!(map.get(&1), Some(&"a")); | |
489 | /// assert_eq!(map.get(&2), None); | |
490 | /// ``` | |
85aaf69f SL |
491 | #[stable(feature = "rust1", since = "1.0.0")] |
492 | pub fn get(&self, key: &usize) -> Option<&V> { | |
1a4d82fc JJ |
493 | if *key < self.v.len() { |
494 | match self.v[*key] { | |
495 | Some(ref value) => Some(value), | |
496 | None => None | |
497 | } | |
498 | } else { | |
499 | None | |
500 | } | |
501 | } | |
502 | ||
503 | /// Returns true if the map contains a value for the specified key. | |
504 | /// | |
505 | /// # Examples | |
506 | /// | |
507 | /// ``` | |
62682a34 | 508 | /// # #![feature(vecmap)] |
1a4d82fc JJ |
509 | /// use std::collections::VecMap; |
510 | /// | |
511 | /// let mut map = VecMap::new(); | |
512 | /// map.insert(1, "a"); | |
513 | /// assert_eq!(map.contains_key(&1), true); | |
514 | /// assert_eq!(map.contains_key(&2), false); | |
515 | /// ``` | |
516 | #[inline] | |
85aaf69f SL |
517 | #[stable(feature = "rust1", since = "1.0.0")] |
518 | pub fn contains_key(&self, key: &usize) -> bool { | |
1a4d82fc JJ |
519 | self.get(key).is_some() |
520 | } | |
521 | ||
522 | /// Returns a mutable reference to the value corresponding to the key. | |
523 | /// | |
524 | /// # Examples | |
525 | /// | |
526 | /// ``` | |
62682a34 | 527 | /// # #![feature(vecmap)] |
1a4d82fc JJ |
528 | /// use std::collections::VecMap; |
529 | /// | |
530 | /// let mut map = VecMap::new(); | |
531 | /// map.insert(1, "a"); | |
9346a6ac AL |
532 | /// if let Some(x) = map.get_mut(&1) { |
533 | /// *x = "b"; | |
1a4d82fc JJ |
534 | /// } |
535 | /// assert_eq!(map[1], "b"); | |
536 | /// ``` | |
85aaf69f SL |
537 | #[stable(feature = "rust1", since = "1.0.0")] |
538 | pub fn get_mut(&mut self, key: &usize) -> Option<&mut V> { | |
1a4d82fc JJ |
539 | if *key < self.v.len() { |
540 | match *(&mut self.v[*key]) { | |
541 | Some(ref mut value) => Some(value), | |
542 | None => None | |
543 | } | |
544 | } else { | |
545 | None | |
546 | } | |
547 | } | |
548 | ||
9346a6ac | 549 | /// Inserts a key-value pair into the map. If the key already had a value |
1a4d82fc JJ |
550 | /// present in the map, that value is returned. Otherwise, `None` is returned. |
551 | /// | |
552 | /// # Examples | |
553 | /// | |
554 | /// ``` | |
62682a34 | 555 | /// # #![feature(vecmap)] |
1a4d82fc JJ |
556 | /// use std::collections::VecMap; |
557 | /// | |
558 | /// let mut map = VecMap::new(); | |
559 | /// assert_eq!(map.insert(37, "a"), None); | |
560 | /// assert_eq!(map.is_empty(), false); | |
561 | /// | |
562 | /// map.insert(37, "b"); | |
563 | /// assert_eq!(map.insert(37, "c"), Some("b")); | |
564 | /// assert_eq!(map[37], "c"); | |
565 | /// ``` | |
85aaf69f SL |
566 | #[stable(feature = "rust1", since = "1.0.0")] |
567 | pub fn insert(&mut self, key: usize, value: V) -> Option<V> { | |
1a4d82fc JJ |
568 | let len = self.v.len(); |
569 | if len <= key { | |
85aaf69f | 570 | self.v.extend((0..key - len + 1).map(|_| None)); |
1a4d82fc JJ |
571 | } |
572 | replace(&mut self.v[key], Some(value)) | |
573 | } | |
574 | ||
575 | /// Removes a key from the map, returning the value at the key if the key | |
576 | /// was previously in the map. | |
577 | /// | |
578 | /// # Examples | |
579 | /// | |
580 | /// ``` | |
62682a34 | 581 | /// # #![feature(vecmap)] |
1a4d82fc JJ |
582 | /// use std::collections::VecMap; |
583 | /// | |
584 | /// let mut map = VecMap::new(); | |
585 | /// map.insert(1, "a"); | |
586 | /// assert_eq!(map.remove(&1), Some("a")); | |
587 | /// assert_eq!(map.remove(&1), None); | |
588 | /// ``` | |
85aaf69f SL |
589 | #[stable(feature = "rust1", since = "1.0.0")] |
590 | pub fn remove(&mut self, key: &usize) -> Option<V> { | |
1a4d82fc JJ |
591 | if *key >= self.v.len() { |
592 | return None; | |
593 | } | |
594 | let result = &mut self.v[*key]; | |
595 | result.take() | |
596 | } | |
85aaf69f SL |
597 | |
598 | /// Gets the given key's corresponding entry in the map for in-place manipulation. | |
599 | /// | |
600 | /// # Examples | |
601 | /// | |
602 | /// ``` | |
62682a34 | 603 | /// # #![feature(vecmap, entry)] |
85aaf69f | 604 | /// use std::collections::VecMap; |
85aaf69f SL |
605 | /// |
606 | /// let mut count: VecMap<u32> = VecMap::new(); | |
607 | /// | |
608 | /// // count the number of occurrences of numbers in the vec | |
c34b1796 AL |
609 | /// for x in vec![1, 2, 1, 2, 3, 4, 1, 2, 4] { |
610 | /// *count.entry(x).or_insert(0) += 1; | |
85aaf69f SL |
611 | /// } |
612 | /// | |
613 | /// assert_eq!(count[1], 3); | |
614 | /// ``` | |
615 | #[stable(feature = "rust1", since = "1.0.0")] | |
616 | pub fn entry(&mut self, key: usize) -> Entry<V> { | |
617 | // FIXME(Gankro): this is basically the dumbest implementation of | |
618 | // entry possible, because weird non-lexical borrows issues make it | |
619 | // completely insane to do any other way. That said, Entry is a border-line | |
620 | // useless construct on VecMap, so it's hardly a big loss. | |
621 | if self.contains_key(&key) { | |
622 | Occupied(OccupiedEntry { | |
623 | map: self, | |
624 | index: key, | |
625 | }) | |
626 | } else { | |
627 | Vacant(VacantEntry { | |
628 | map: self, | |
629 | index: key, | |
630 | }) | |
631 | } | |
632 | } | |
633 | } | |
634 | ||
635 | ||
636 | impl<'a, V> Entry<'a, V> { | |
62682a34 | 637 | #[unstable(feature = "entry", |
c34b1796 AL |
638 | reason = "will soon be replaced by or_insert")] |
639 | #[deprecated(since = "1.0", | |
640 | reason = "replaced with more ergonomic `or_insert` and `or_insert_with`")] | |
85aaf69f SL |
641 | /// Returns a mutable reference to the entry if occupied, or the VacantEntry if vacant |
642 | pub fn get(self) -> Result<&'a mut V, VacantEntry<'a, V>> { | |
643 | match self { | |
644 | Occupied(entry) => Ok(entry.into_mut()), | |
645 | Vacant(entry) => Err(entry), | |
646 | } | |
647 | } | |
c34b1796 | 648 | |
62682a34 SL |
649 | #[stable(feature = "vecmap_entry", since = "1.2.0")] |
650 | /// Ensures a value is in the entry by inserting the default if empty, and | |
651 | /// returns a mutable reference to the value in the entry. | |
c34b1796 AL |
652 | pub fn or_insert(self, default: V) -> &'a mut V { |
653 | match self { | |
654 | Occupied(entry) => entry.into_mut(), | |
655 | Vacant(entry) => entry.insert(default), | |
656 | } | |
657 | } | |
658 | ||
62682a34 SL |
659 | #[stable(feature = "vecmap_entry", since = "1.2.0")] |
660 | /// Ensures a value is in the entry by inserting the result of the default | |
661 | /// function if empty, and returns a mutable reference to the value in the | |
662 | /// entry. | |
c34b1796 AL |
663 | pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V { |
664 | match self { | |
665 | Occupied(entry) => entry.into_mut(), | |
666 | Vacant(entry) => entry.insert(default()), | |
667 | } | |
668 | } | |
1a4d82fc JJ |
669 | } |
670 | ||
85aaf69f SL |
671 | impl<'a, V> VacantEntry<'a, V> { |
672 | /// Sets the value of the entry with the VacantEntry's key, | |
673 | /// and returns a mutable reference to it. | |
674 | #[stable(feature = "rust1", since = "1.0.0")] | |
675 | pub fn insert(self, value: V) -> &'a mut V { | |
676 | let index = self.index; | |
677 | self.map.insert(index, value); | |
678 | &mut self.map[index] | |
679 | } | |
680 | } | |
681 | ||
682 | impl<'a, V> OccupiedEntry<'a, V> { | |
683 | /// Gets a reference to the value in the entry. | |
684 | #[stable(feature = "rust1", since = "1.0.0")] | |
685 | pub fn get(&self) -> &V { | |
686 | let index = self.index; | |
687 | &self.map[index] | |
688 | } | |
689 | ||
690 | /// Gets a mutable reference to the value in the entry. | |
691 | #[stable(feature = "rust1", since = "1.0.0")] | |
692 | pub fn get_mut(&mut self) -> &mut V { | |
693 | let index = self.index; | |
694 | &mut self.map[index] | |
695 | } | |
696 | ||
697 | /// Converts the entry into a mutable reference to its value. | |
698 | #[stable(feature = "rust1", since = "1.0.0")] | |
699 | pub fn into_mut(self) -> &'a mut V { | |
700 | let index = self.index; | |
701 | &mut self.map[index] | |
702 | } | |
703 | ||
704 | /// Sets the value of the entry with the OccupiedEntry's key, | |
705 | /// and returns the entry's old value. | |
706 | #[stable(feature = "rust1", since = "1.0.0")] | |
707 | pub fn insert(&mut self, value: V) -> V { | |
708 | let index = self.index; | |
709 | self.map.insert(index, value).unwrap() | |
710 | } | |
711 | ||
712 | /// Takes the value of the entry out of the map, and returns it. | |
713 | #[stable(feature = "rust1", since = "1.0.0")] | |
714 | pub fn remove(self) -> V { | |
715 | let index = self.index; | |
716 | self.map.remove(&index).unwrap() | |
717 | } | |
718 | } | |
719 | ||
720 | #[stable(feature = "rust1", since = "1.0.0")] | |
1a4d82fc JJ |
721 | impl<V: PartialEq> PartialEq for VecMap<V> { |
722 | fn eq(&self, other: &VecMap<V>) -> bool { | |
723 | iter::order::eq(self.iter(), other.iter()) | |
724 | } | |
725 | } | |
726 | ||
85aaf69f | 727 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
728 | impl<V: Eq> Eq for VecMap<V> {} |
729 | ||
85aaf69f | 730 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
731 | impl<V: PartialOrd> PartialOrd for VecMap<V> { |
732 | #[inline] | |
733 | fn partial_cmp(&self, other: &VecMap<V>) -> Option<Ordering> { | |
734 | iter::order::partial_cmp(self.iter(), other.iter()) | |
735 | } | |
736 | } | |
737 | ||
85aaf69f | 738 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
739 | impl<V: Ord> Ord for VecMap<V> { |
740 | #[inline] | |
741 | fn cmp(&self, other: &VecMap<V>) -> Ordering { | |
742 | iter::order::cmp(self.iter(), other.iter()) | |
743 | } | |
744 | } | |
745 | ||
85aaf69f SL |
746 | #[stable(feature = "rust1", since = "1.0.0")] |
747 | impl<V: fmt::Debug> fmt::Debug for VecMap<V> { | |
1a4d82fc | 748 | fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { |
c34b1796 | 749 | try!(write!(f, "{{")); |
1a4d82fc JJ |
750 | |
751 | for (i, (k, v)) in self.iter().enumerate() { | |
752 | if i != 0 { try!(write!(f, ", ")); } | |
753 | try!(write!(f, "{}: {:?}", k, *v)); | |
754 | } | |
755 | ||
756 | write!(f, "}}") | |
757 | } | |
758 | } | |
759 | ||
85aaf69f SL |
760 | #[stable(feature = "rust1", since = "1.0.0")] |
761 | impl<V> FromIterator<(usize, V)> for VecMap<V> { | |
762 | fn from_iter<I: IntoIterator<Item=(usize, V)>>(iter: I) -> VecMap<V> { | |
1a4d82fc JJ |
763 | let mut map = VecMap::new(); |
764 | map.extend(iter); | |
765 | map | |
766 | } | |
767 | } | |
768 | ||
85aaf69f SL |
769 | #[stable(feature = "rust1", since = "1.0.0")] |
770 | impl<T> IntoIterator for VecMap<T> { | |
771 | type Item = (usize, T); | |
772 | type IntoIter = IntoIter<T>; | |
773 | ||
9346a6ac AL |
774 | /// Returns an iterator visiting all key-value pairs in ascending order of |
775 | /// the keys, consuming the original `VecMap`. | |
776 | /// The iterator's element type is `(usize, &'r V)`. | |
777 | /// | |
778 | /// # Examples | |
779 | /// | |
780 | /// ``` | |
62682a34 | 781 | /// # #![feature(vecmap)] |
9346a6ac AL |
782 | /// use std::collections::VecMap; |
783 | /// | |
784 | /// let mut map = VecMap::new(); | |
785 | /// map.insert(1, "a"); | |
786 | /// map.insert(3, "c"); | |
787 | /// map.insert(2, "b"); | |
788 | /// | |
789 | /// let vec: Vec<(usize, &str)> = map.into_iter().collect(); | |
790 | /// | |
791 | /// assert_eq!(vec, [(1, "a"), (2, "b"), (3, "c")]); | |
792 | /// ``` | |
85aaf69f | 793 | fn into_iter(self) -> IntoIter<T> { |
9346a6ac AL |
794 | fn filter<A>((i, v): (usize, Option<A>)) -> Option<(usize, A)> { |
795 | v.map(|v| (i, v)) | |
796 | } | |
797 | let filter: fn((usize, Option<T>)) -> Option<(usize, T)> = filter; // coerce to fn ptr | |
798 | ||
799 | IntoIter { iter: self.v.into_iter().enumerate().filter_map(filter) } | |
85aaf69f SL |
800 | } |
801 | } | |
802 | ||
803 | #[stable(feature = "rust1", since = "1.0.0")] | |
804 | impl<'a, T> IntoIterator for &'a VecMap<T> { | |
805 | type Item = (usize, &'a T); | |
806 | type IntoIter = Iter<'a, T>; | |
807 | ||
808 | fn into_iter(self) -> Iter<'a, T> { | |
809 | self.iter() | |
810 | } | |
811 | } | |
812 | ||
813 | #[stable(feature = "rust1", since = "1.0.0")] | |
814 | impl<'a, T> IntoIterator for &'a mut VecMap<T> { | |
815 | type Item = (usize, &'a mut T); | |
816 | type IntoIter = IterMut<'a, T>; | |
817 | ||
818 | fn into_iter(mut self) -> IterMut<'a, T> { | |
819 | self.iter_mut() | |
820 | } | |
821 | } | |
822 | ||
823 | #[stable(feature = "rust1", since = "1.0.0")] | |
824 | impl<V> Extend<(usize, V)> for VecMap<V> { | |
825 | fn extend<I: IntoIterator<Item=(usize, V)>>(&mut self, iter: I) { | |
1a4d82fc JJ |
826 | for (k, v) in iter { |
827 | self.insert(k, v); | |
828 | } | |
829 | } | |
830 | } | |
831 | ||
62682a34 SL |
832 | #[stable(feature = "extend_ref", since = "1.2.0")] |
833 | impl<'a, V: Copy> Extend<(usize, &'a V)> for VecMap<V> { | |
834 | fn extend<I: IntoIterator<Item=(usize, &'a V)>>(&mut self, iter: I) { | |
835 | self.extend(iter.into_iter().map(|(key, &value)| (key, value))); | |
836 | } | |
837 | } | |
838 | ||
85aaf69f | 839 | impl<V> Index<usize> for VecMap<V> { |
1a4d82fc JJ |
840 | type Output = V; |
841 | ||
842 | #[inline] | |
c34b1796 AL |
843 | fn index<'a>(&'a self, i: usize) -> &'a V { |
844 | self.get(&i).expect("key not present") | |
845 | } | |
846 | } | |
847 | ||
848 | impl<'a,V> Index<&'a usize> for VecMap<V> { | |
849 | type Output = V; | |
850 | ||
851 | #[inline] | |
852 | fn index(&self, i: &usize) -> &V { | |
1a4d82fc JJ |
853 | self.get(i).expect("key not present") |
854 | } | |
855 | } | |
856 | ||
85aaf69f SL |
857 | #[stable(feature = "rust1", since = "1.0.0")] |
858 | impl<V> IndexMut<usize> for VecMap<V> { | |
1a4d82fc | 859 | #[inline] |
c34b1796 AL |
860 | fn index_mut(&mut self, i: usize) -> &mut V { |
861 | self.get_mut(&i).expect("key not present") | |
862 | } | |
863 | } | |
864 | ||
865 | #[stable(feature = "rust1", since = "1.0.0")] | |
866 | impl<'a, V> IndexMut<&'a usize> for VecMap<V> { | |
867 | #[inline] | |
868 | fn index_mut(&mut self, i: &usize) -> &mut V { | |
1a4d82fc JJ |
869 | self.get_mut(i).expect("key not present") |
870 | } | |
871 | } | |
872 | ||
873 | macro_rules! iterator { | |
874 | (impl $name:ident -> $elem:ty, $($getter:ident),+) => { | |
85aaf69f | 875 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
876 | impl<'a, V> Iterator for $name<'a, V> { |
877 | type Item = $elem; | |
878 | ||
879 | #[inline] | |
880 | fn next(&mut self) -> Option<$elem> { | |
881 | while self.front < self.back { | |
882 | match self.iter.next() { | |
883 | Some(elem) => { | |
884 | match elem$(. $getter ())+ { | |
885 | Some(x) => { | |
886 | let index = self.front; | |
887 | self.front += 1; | |
888 | return Some((index, x)); | |
889 | }, | |
890 | None => {}, | |
891 | } | |
892 | } | |
893 | _ => () | |
894 | } | |
895 | self.front += 1; | |
896 | } | |
897 | None | |
898 | } | |
899 | ||
900 | #[inline] | |
85aaf69f | 901 | fn size_hint(&self) -> (usize, Option<usize>) { |
1a4d82fc JJ |
902 | (0, Some(self.back - self.front)) |
903 | } | |
904 | } | |
905 | } | |
906 | } | |
907 | ||
908 | macro_rules! double_ended_iterator { | |
909 | (impl $name:ident -> $elem:ty, $($getter:ident),+) => { | |
85aaf69f | 910 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
911 | impl<'a, V> DoubleEndedIterator for $name<'a, V> { |
912 | #[inline] | |
913 | fn next_back(&mut self) -> Option<$elem> { | |
914 | while self.front < self.back { | |
915 | match self.iter.next_back() { | |
916 | Some(elem) => { | |
917 | match elem$(. $getter ())+ { | |
918 | Some(x) => { | |
919 | self.back -= 1; | |
920 | return Some((self.back, x)); | |
921 | }, | |
922 | None => {}, | |
923 | } | |
924 | } | |
925 | _ => () | |
926 | } | |
927 | self.back -= 1; | |
928 | } | |
929 | None | |
930 | } | |
931 | } | |
932 | } | |
933 | } | |
934 | ||
935 | /// An iterator over the key-value pairs of a map. | |
85aaf69f | 936 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 937 | pub struct Iter<'a, V:'a> { |
85aaf69f SL |
938 | front: usize, |
939 | back: usize, | |
1a4d82fc JJ |
940 | iter: slice::Iter<'a, Option<V>> |
941 | } | |
942 | ||
943 | // FIXME(#19839) Remove in favor of `#[derive(Clone)]` | |
944 | impl<'a, V> Clone for Iter<'a, V> { | |
945 | fn clone(&self) -> Iter<'a, V> { | |
946 | Iter { | |
947 | front: self.front, | |
948 | back: self.back, | |
949 | iter: self.iter.clone() | |
950 | } | |
951 | } | |
952 | } | |
953 | ||
85aaf69f SL |
954 | iterator! { impl Iter -> (usize, &'a V), as_ref } |
955 | double_ended_iterator! { impl Iter -> (usize, &'a V), as_ref } | |
1a4d82fc JJ |
956 | |
957 | /// An iterator over the key-value pairs of a map, with the | |
958 | /// values being mutable. | |
85aaf69f | 959 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 960 | pub struct IterMut<'a, V:'a> { |
85aaf69f SL |
961 | front: usize, |
962 | back: usize, | |
1a4d82fc JJ |
963 | iter: slice::IterMut<'a, Option<V>> |
964 | } | |
965 | ||
85aaf69f SL |
966 | iterator! { impl IterMut -> (usize, &'a mut V), as_mut } |
967 | double_ended_iterator! { impl IterMut -> (usize, &'a mut V), as_mut } | |
1a4d82fc JJ |
968 | |
969 | /// An iterator over the keys of a map. | |
85aaf69f | 970 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 971 | pub struct Keys<'a, V: 'a> { |
85aaf69f | 972 | iter: Map<Iter<'a, V>, fn((usize, &'a V)) -> usize> |
1a4d82fc JJ |
973 | } |
974 | ||
975 | // FIXME(#19839) Remove in favor of `#[derive(Clone)]` | |
976 | impl<'a, V> Clone for Keys<'a, V> { | |
977 | fn clone(&self) -> Keys<'a, V> { | |
978 | Keys { | |
979 | iter: self.iter.clone() | |
980 | } | |
981 | } | |
982 | } | |
983 | ||
984 | /// An iterator over the values of a map. | |
85aaf69f | 985 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 986 | pub struct Values<'a, V: 'a> { |
85aaf69f | 987 | iter: Map<Iter<'a, V>, fn((usize, &'a V)) -> &'a V> |
1a4d82fc JJ |
988 | } |
989 | ||
990 | // FIXME(#19839) Remove in favor of `#[derive(Clone)]` | |
991 | impl<'a, V> Clone for Values<'a, V> { | |
992 | fn clone(&self) -> Values<'a, V> { | |
993 | Values { | |
994 | iter: self.iter.clone() | |
995 | } | |
996 | } | |
997 | } | |
998 | ||
999 | /// A consuming iterator over the key-value pairs of a map. | |
85aaf69f | 1000 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1001 | pub struct IntoIter<V> { |
1002 | iter: FilterMap< | |
1a4d82fc | 1003 | Enumerate<vec::IntoIter<Option<V>>>, |
85aaf69f | 1004 | fn((usize, Option<V>)) -> Option<(usize, V)>> |
1a4d82fc JJ |
1005 | } |
1006 | ||
62682a34 | 1007 | #[unstable(feature = "drain")] |
85aaf69f SL |
1008 | pub struct Drain<'a, V:'a> { |
1009 | iter: FilterMap< | |
1010 | Enumerate<vec::Drain<'a, Option<V>>>, | |
1011 | fn((usize, Option<V>)) -> Option<(usize, V)>> | |
1012 | } | |
1013 | ||
62682a34 | 1014 | #[unstable(feature = "drain")] |
85aaf69f SL |
1015 | impl<'a, V> Iterator for Drain<'a, V> { |
1016 | type Item = (usize, V); | |
1017 | ||
1018 | fn next(&mut self) -> Option<(usize, V)> { self.iter.next() } | |
1019 | fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() } | |
1020 | } | |
1021 | ||
62682a34 | 1022 | #[unstable(feature = "drain")] |
85aaf69f SL |
1023 | impl<'a, V> DoubleEndedIterator for Drain<'a, V> { |
1024 | fn next_back(&mut self) -> Option<(usize, V)> { self.iter.next_back() } | |
1025 | } | |
1026 | ||
1027 | #[stable(feature = "rust1", since = "1.0.0")] | |
1a4d82fc | 1028 | impl<'a, V> Iterator for Keys<'a, V> { |
85aaf69f | 1029 | type Item = usize; |
1a4d82fc | 1030 | |
85aaf69f SL |
1031 | fn next(&mut self) -> Option<usize> { self.iter.next() } |
1032 | fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() } | |
1a4d82fc | 1033 | } |
85aaf69f | 1034 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 1035 | impl<'a, V> DoubleEndedIterator for Keys<'a, V> { |
85aaf69f | 1036 | fn next_back(&mut self) -> Option<usize> { self.iter.next_back() } |
1a4d82fc JJ |
1037 | } |
1038 | ||
85aaf69f | 1039 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1040 | impl<'a, V> Iterator for Values<'a, V> { |
1041 | type Item = &'a V; | |
1042 | ||
1043 | fn next(&mut self) -> Option<(&'a V)> { self.iter.next() } | |
85aaf69f | 1044 | fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() } |
1a4d82fc | 1045 | } |
85aaf69f | 1046 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc JJ |
1047 | impl<'a, V> DoubleEndedIterator for Values<'a, V> { |
1048 | fn next_back(&mut self) -> Option<(&'a V)> { self.iter.next_back() } | |
1049 | } | |
1050 | ||
85aaf69f | 1051 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 1052 | impl<V> Iterator for IntoIter<V> { |
85aaf69f | 1053 | type Item = (usize, V); |
1a4d82fc | 1054 | |
85aaf69f SL |
1055 | fn next(&mut self) -> Option<(usize, V)> { self.iter.next() } |
1056 | fn size_hint(&self) -> (usize, Option<usize>) { self.iter.size_hint() } | |
1a4d82fc | 1057 | } |
85aaf69f | 1058 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 1059 | impl<V> DoubleEndedIterator for IntoIter<V> { |
85aaf69f | 1060 | fn next_back(&mut self) -> Option<(usize, V)> { self.iter.next_back() } |
1a4d82fc | 1061 | } |