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