1//! An ordered map based on a B-Tree that keeps insertion order of elements.
2
3#[cfg(all(
4 feature = "hash-collections",
5 not(feature = "prefer-btree-collections")
6))]
7mod impls {
8 use crate::collections::hash;
9 use indexmap::IndexMap;
10
11 pub type IndexMapImpl<K, V> = IndexMap<K, V, hash::RandomState>;
12 pub type EntryImpl<'a, K, V> = indexmap::map::Entry<'a, K, V>;
13 pub type OccupiedEntryImpl<'a, K, V> = indexmap::map::OccupiedEntry<'a, K, V>;
14 pub type VacantEntryImpl<'a, K, V> = indexmap::map::VacantEntry<'a, K, V>;
15 pub type IterImpl<'a, K, V> = indexmap::map::Iter<'a, K, V>;
16 pub type IterMutImpl<'a, K, V> = indexmap::map::IterMut<'a, K, V>;
17 pub type IntoIterImpl<K, V> = indexmap::map::IntoIter<K, V>;
18 pub type KeysImpl<'a, K, V> = indexmap::map::Keys<'a, K, V>;
19 pub type ValuesImpl<'a, K, V> = indexmap::map::Values<'a, K, V>;
20 pub type ValuesMutImpl<'a, K, V> = indexmap::map::ValuesMut<'a, K, V>;
21}
22
23#[cfg(any(
24 not(feature = "hash-collections"),
25 feature = "prefer-btree-collections"
26))]
27mod impls {
28 pub type IndexMapImpl<K, V> = super::IndexMap<K, V>;
29 pub type EntryImpl<'a, K, V> = super::Entry<'a, K, V>;
30 pub type OccupiedEntryImpl<'a, K, V> = super::OccupiedEntry<'a, K, V>;
31 pub type VacantEntryImpl<'a, K, V> = super::VacantEntry<'a, K, V>;
32 pub type IterImpl<'a, K, V> = super::Iter<'a, K, V>;
33 pub type IterMutImpl<'a, K, V> = super::IterMut<'a, K, V>;
34 pub type IntoIterImpl<K, V> = super::IntoIter<K, V>;
35 pub type KeysImpl<'a, K, V> = super::Keys<'a, K, V>;
36 pub type ValuesImpl<'a, K, V> = super::Values<'a, K, V>;
37 pub type ValuesMutImpl<'a, K, V> = super::ValuesMut<'a, K, V>;
38}
39
40pub use self::impls::*;
41
42use alloc::collections::{btree_map, BTreeMap};
43use alloc::vec::IntoIter as VecIntoIter;
44use alloc::vec::Vec;
45use core::borrow::Borrow;
46use core::fmt;
47use core::iter::FusedIterator;
48use core::mem::replace;
49use core::ops::{Index, IndexMut};
50use core::slice::Iter as SliceIter;
51use core::slice::IterMut as SliceIterMut;
52
53/// A slot index referencing a slot in an [`IndexMap`].
54#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
55struct SlotIndex(usize);
56
57impl SlotIndex {
58 /// Returns the raw `usize` index of the [`SlotIndex`].
59 pub fn index(self) -> usize {
60 self.0
61 }
62}
63
64#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
65struct Slot<K, V> {
66 /// The key of the [`Slot`].
67 key: K,
68 /// The value of the [`Slot`].
69 value: V,
70}
71
72impl<K, V> Slot<K, V> {
73 /// Creates a new [`Slot`] from the given `key` and `value`.
74 pub fn new(key: K, value: V) -> Self {
75 Self { key, value }
76 }
77
78 /// Returns the [`Slot`] as a pair of references to its `key` and `value`.
79 pub fn as_pair(&self) -> (&K, &V) {
80 (&self.key, &self.value)
81 }
82
83 /// Returns the [`Slot`] as a pair of references to its `key` and `value`.
84 pub fn as_pair_mut(&mut self) -> (&K, &mut V) {
85 (&self.key, &mut self.value)
86 }
87
88 /// Converts the [`Slot`] into a pair of its `key` and `value`.
89 pub fn into_pair(self) -> (K, V) {
90 (self.key, self.value)
91 }
92
93 /// Returns a shared reference to the key of the [`Slot`].
94 pub fn key(&self) -> &K {
95 &self.key
96 }
97
98 /// Returns a shared reference to the value of the [`Slot`].
99 pub fn value(&self) -> &V {
100 &self.value
101 }
102
103 /// Returns an exclusive reference to the value of the [`Slot`].
104 pub fn value_mut(&mut self) -> &mut V {
105 &mut self.value
106 }
107}
108
109/// A b-tree map where the iteration order of the key-value
110/// pairs is independent of the ordering of the keys.
111///
112/// The interface is closely compatible with the [`indexmap` crate]
113/// and a subset of the features that is relevant for the
114/// [`wasmparser-nostd` crate].
115///
116/// # Differences to original `IndexMap`
117///
118/// Since the goal of this crate was to maintain a simple
119/// `no_std` compatible fork of the [`indexmap` crate] there are some
120/// downsides and differences.
121///
122/// - Some operations such as `IndexMap::insert` now require `K: Clone`.
123/// - It is to be expected that this fork performs worse than the original
124/// [`indexmap` crate] implementation.
125/// - The implementation is based on `BTreeMap` internally instead of
126/// `HashMap` which has the effect that methods no longer require `K: Hash`
127/// but `K: Ord` instead.
128///
129/// [`indexmap` crate]: https://crates.io/crates/indexmap
130/// [`wasmparser-nostd` crate]: https://crates.io/crates/wasmparser-nostd
131#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
132pub struct IndexMap<K, V> {
133 /// A mapping from keys to slot indices.
134 key2slot: BTreeMap<K, SlotIndex>,
135 /// A vector holding all slots of key value pairs.
136 slots: Vec<Slot<K, V>>,
137}
138
139impl<K, V> Default for IndexMap<K, V> {
140 fn default() -> Self {
141 Self::new()
142 }
143}
144
145impl<K, V> IndexMap<K, V> {
146 /// Makes a new, empty [`IndexMap`].
147 ///
148 /// Does not allocate anything on its own.
149 pub fn new() -> Self {
150 Self {
151 key2slot: BTreeMap::new(),
152 slots: Vec::new(),
153 }
154 }
155
156 /// Constructs a new, empty [`IndexMap`] with at least the specified capacity.
157 ///
158 /// Does not allocate if `capacity` is zero.
159 pub fn with_capacity(capacity: usize) -> Self {
160 Self {
161 key2slot: BTreeMap::new(),
162 slots: Vec::with_capacity(capacity),
163 }
164 }
165
166 /// Reserve capacity for at least `additional` more key-value pairs.
167 pub fn reserve(&mut self, additional: usize) {
168 self.slots.reserve(additional);
169 }
170
171 /// Returns the number of elements in the map.
172 pub fn len(&self) -> usize {
173 self.slots.len()
174 }
175
176 /// Returns `true` if the map contains no elements.
177 pub fn is_empty(&self) -> bool {
178 self.len() == 0
179 }
180
181 /// Returns true if the map contains a value for the specified key.
182 ///
183 /// The key may be any borrowed form of the map’s key type,
184 /// but the ordering on the borrowed form must match the ordering on the key type.
185 pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool
186 where
187 K: Borrow<Q> + Ord,
188 Q: Ord,
189 {
190 self.key2slot.contains_key(key)
191 }
192
193 /// Inserts a key-value pair into the map.
194 ///
195 /// If the map did not have this key present, `None` is returned.
196 ///
197 /// If the map did have this key present, the value is updated, and the old
198 /// value is returned. The key is not updated, though; this matters for
199 /// types that can be `==` without being identical.
200 pub fn insert(&mut self, key: K, value: V) -> Option<V>
201 where
202 K: Ord + Clone,
203 {
204 self.insert_full(key, value).1
205 }
206
207 /// Inserts a key-value pair into the map.
208 ///
209 /// Returns the unique index to the key-value pair alongside the previous value.
210 ///
211 /// If the map did not have this key present, `None` is returned.
212 ///
213 /// If the map did have this key present, the value is updated, and the old
214 /// value is returned. The key is not updated, though; this matters for
215 /// types that can be `==` without being identical.
216 pub fn insert_full(&mut self, key: K, value: V) -> (usize, Option<V>)
217 where
218 K: Ord + Clone,
219 {
220 match self.key2slot.entry(key.clone()) {
221 btree_map::Entry::Vacant(entry) => {
222 let index = self.slots.len();
223 entry.insert(SlotIndex(index));
224 self.slots.push(Slot::new(key, value));
225 (index, None)
226 }
227 btree_map::Entry::Occupied(entry) => {
228 let index = entry.get().index();
229 let new_slot = Slot::new(key, value);
230 let old_slot = replace(&mut self.slots[index], new_slot);
231 (index, Some(old_slot.value))
232 }
233 }
234 }
235
236 /// Remove the key-value pair equivalent to `key` and return it and
237 /// the index it had.
238 ///
239 /// Like [`Vec::swap_remove`], the pair is removed by swapping it with the
240 /// last element of the map and popping it off. **This perturbs
241 /// the position of what used to be the last element!**
242 ///
243 /// Return `None` if `key` is not in map.
244 pub fn swap_remove<Q>(&mut self, key: &Q) -> Option<V>
245 where
246 K: Borrow<Q> + Ord,
247 Q: ?Sized + Ord,
248 {
249 self.swap_remove_full(key)
250 .map(|(_index, _key, value)| value)
251 }
252
253 /// Remove and return the key-value pair equivalent to `key`.
254 ///
255 /// Like [`Vec::swap_remove`], the pair is removed by swapping it with the
256 /// last element of the map and popping it off. **This perturbs
257 /// the position of what used to be the last element!**
258 ///
259 /// Return `None` if `key` is not in map.
260 ///
261 /// [`Vec::swap_remove`]: alloc::vec::Vec::swap_remove
262 pub fn swap_remove_entry<Q>(&mut self, key: &Q) -> Option<(K, V)>
263 where
264 K: Borrow<Q> + Ord,
265 Q: ?Sized + Ord,
266 {
267 self.swap_remove_full(key)
268 .map(|(_index, key, value)| (key, value))
269 }
270
271 /// Remove the key-value pair equivalent to `key` and return it and
272 /// the index it had.
273 ///
274 /// Like [`Vec::swap_remove`], the pair is removed by swapping it with the
275 /// last element of the map and popping it off. **This perturbs
276 /// the position of what used to be the last element!**
277 ///
278 /// Return `None` if `key` is not in map.
279 pub fn swap_remove_full<Q>(&mut self, key: &Q) -> Option<(usize, K, V)>
280 where
281 K: Borrow<Q> + Ord,
282 Q: ?Sized + Ord,
283 {
284 let index = self.key2slot.remove(key)?.0;
285 let removed = self.slots.swap_remove(index);
286 if index != self.len() {
287 // If the index was referring the last element
288 // `swap_remove` would not swap any other element
289 // thus adjustments are only needed if this was not the case.
290 let swapped = self.slots[index].key.borrow();
291 let swapped_index = self
292 .key2slot
293 .get_mut(swapped)
294 .expect("the swapped entry's key must be present");
295 *swapped_index = SlotIndex(index);
296 }
297 Some((index, removed.key, removed.value))
298 }
299
300 /// Gets the given key’s corresponding entry in the map for in-place manipulation.
301 pub fn entry(&mut self, key: K) -> Entry<K, V>
302 where
303 K: Ord + Clone,
304 {
305 match self.key2slot.entry(key) {
306 btree_map::Entry::Vacant(entry) => Entry::Vacant(VacantEntry {
307 vacant: entry,
308 slots: &mut self.slots,
309 }),
310 btree_map::Entry::Occupied(entry) => Entry::Occupied(OccupiedEntry {
311 occupied: entry,
312 slots: &mut self.slots,
313 }),
314 }
315 }
316
317 /// Returns a reference to the value corresponding to the key.
318 ///
319 /// The key may be any borrowed form of the map’s key type,
320 /// but the ordering on the borrowed form must match the ordering on the key type.
321 pub fn get<Q>(&self, key: &Q) -> Option<&V>
322 where
323 K: Borrow<Q> + Ord,
324 Q: ?Sized + Ord,
325 {
326 self.key2slot
327 .get(key)
328 .map(|slot| &self.slots[slot.index()].value)
329 }
330
331 /// Returns a mutable reference to the value corresponding to the key.
332 ///
333 /// The key may be any borrowed form of the map’s key type,
334 /// but the ordering on the borrowed form must match the ordering on the key type.
335 pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>
336 where
337 K: Borrow<Q> + Ord,
338 Q: Ord,
339 {
340 self.key2slot
341 .get(key)
342 .map(|slot| &mut self.slots[slot.index()].value)
343 }
344
345 /// Returns the key-value pair corresponding to the supplied key.
346 ///
347 /// The supplied key may be any borrowed form of the map's key type,
348 /// but the ordering on the borrowed form *must* match the ordering
349 /// on the key type.
350 pub fn get_key_value<Q: ?Sized>(&self, key: &Q) -> Option<(&K, &V)>
351 where
352 K: Borrow<Q> + Ord,
353 Q: Ord,
354 {
355 self.key2slot
356 .get_key_value(key)
357 .map(|(key, slot)| (key, &self.slots[slot.index()].value))
358 }
359
360 /// Returns the key-value pair corresponding to the supplied key
361 /// as well as the unique index of the returned key-value pair.
362 ///
363 /// The supplied key may be any borrowed form of the map's key type,
364 /// but the ordering on the borrowed form *must* match the ordering
365 /// on the key type.
366 pub fn get_full<Q: ?Sized>(&self, key: &Q) -> Option<(usize, &K, &V)>
367 where
368 K: Borrow<Q> + Ord,
369 Q: Ord,
370 {
371 self.key2slot.get_key_value(key).map(|(key, slot)| {
372 let index = slot.index();
373 let value = &self.slots[index].value;
374 (index, key, value)
375 })
376 }
377
378 /// Returns the unique index corresponding to the supplied key.
379 ///
380 /// The supplied key may be any borrowed form of the map's key type,
381 /// but the ordering on the borrowed form *must* match the ordering
382 /// on the key type.
383 pub fn get_index_of<Q: ?Sized>(&self, key: &Q) -> Option<usize>
384 where
385 K: Borrow<Q> + Ord,
386 Q: Ord,
387 {
388 self.key2slot.get(key).copied().map(SlotIndex::index)
389 }
390
391 /// Returns a shared reference to the key-value pair at the given index.
392 pub fn get_index(&self, index: usize) -> Option<(&K, &V)> {
393 self.slots.get(index).map(Slot::as_pair)
394 }
395
396 /// Returns an exclusive reference to the key-value pair at the given index.
397 pub fn get_index_mut(&mut self, index: usize) -> Option<(&K, &mut V)> {
398 self.slots.get_mut(index).map(Slot::as_pair_mut)
399 }
400
401 /// Gets an iterator over the entries of the map, sorted by key.
402 pub fn iter(&self) -> Iter<K, V> {
403 Iter {
404 iter: self.slots.iter(),
405 }
406 }
407
408 /// Gets a mutable iterator over the entries of the map, sorted by key.
409 pub fn iter_mut(&mut self) -> IterMut<K, V> {
410 IterMut {
411 iter: self.slots.iter_mut(),
412 }
413 }
414
415 /// Gets an iterator over the values of the map, in order by key.
416 pub fn keys(&self) -> Keys<K, V> {
417 Keys {
418 iter: self.slots.iter(),
419 }
420 }
421
422 /// Gets an iterator over the values of the map, in order by key.
423 pub fn values(&self) -> Values<K, V> {
424 Values {
425 iter: self.slots.iter(),
426 }
427 }
428
429 /// Gets a mutable iterator over the values of the map, in order by key.
430 pub fn values_mut(&mut self) -> ValuesMut<K, V> {
431 ValuesMut {
432 iter: self.slots.iter_mut(),
433 }
434 }
435
436 /// Clears the map, removing all elements.
437 pub fn clear(&mut self) {
438 self.key2slot.clear();
439 self.slots.clear();
440 }
441}
442
443impl<'a, K, Q, V> Index<&'a Q> for IndexMap<K, V>
444where
445 K: Borrow<Q> + Ord,
446 Q: ?Sized + Ord,
447{
448 type Output = V;
449
450 fn index(&self, key: &'a Q) -> &Self::Output {
451 self.get(key).expect(msg:"no entry found for key")
452 }
453}
454
455impl<K, V> Index<usize> for IndexMap<K, V> {
456 type Output = V;
457
458 fn index(&self, index: usize) -> &Self::Output {
459 let (_key: &K, value: &V) = self
460 .get_index(index)
461 .expect(msg:"IndexMap: index out of bounds");
462 value
463 }
464}
465
466impl<K, V> IndexMut<usize> for IndexMap<K, V> {
467 fn index_mut(&mut self, index: usize) -> &mut Self::Output {
468 let (_key: &K, value: &mut V) = self
469 .get_index_mut(index)
470 .expect(msg:"IndexMap: index out of bounds");
471 value
472 }
473}
474
475impl<'a, K, V> Extend<(&'a K, &'a V)> for IndexMap<K, V>
476where
477 K: Ord + Copy,
478 V: Copy,
479{
480 fn extend<T>(&mut self, iter: T)
481 where
482 T: IntoIterator<Item = (&'a K, &'a V)>,
483 {
484 self.extend(iter.into_iter().map(|(key: &'a K, value: &'a V)| (*key, *value)))
485 }
486}
487
488impl<K, V> Extend<(K, V)> for IndexMap<K, V>
489where
490 K: Ord + Clone,
491{
492 fn extend<T>(&mut self, iter: T)
493 where
494 T: IntoIterator<Item = (K, V)>,
495 {
496 iter.into_iter().for_each(move |(k: K, v: V)| {
497 self.insert(key:k, value:v);
498 });
499 }
500}
501
502impl<K, V> FromIterator<(K, V)> for IndexMap<K, V>
503where
504 K: Ord + Clone,
505{
506 fn from_iter<T>(iter: T) -> Self
507 where
508 T: IntoIterator<Item = (K, V)>,
509 {
510 let mut map: IndexMap = IndexMap::new();
511 map.extend(iter);
512 map
513 }
514}
515
516impl<K, V, const N: usize> From<[(K, V); N]> for IndexMap<K, V>
517where
518 K: Ord + Clone,
519{
520 fn from(items: [(K, V); N]) -> Self {
521 items.into_iter().collect()
522 }
523}
524
525impl<'a, K, V> IntoIterator for &'a IndexMap<K, V> {
526 type Item = (&'a K, &'a V);
527 type IntoIter = Iter<'a, K, V>;
528
529 fn into_iter(self) -> Self::IntoIter {
530 self.iter()
531 }
532}
533
534impl<'a, K, V> IntoIterator for &'a mut IndexMap<K, V> {
535 type Item = (&'a K, &'a mut V);
536 type IntoIter = IterMut<'a, K, V>;
537
538 fn into_iter(self) -> Self::IntoIter {
539 self.iter_mut()
540 }
541}
542
543impl<K, V> IntoIterator for IndexMap<K, V> {
544 type Item = (K, V);
545 type IntoIter = IntoIter<K, V>;
546
547 fn into_iter(self) -> Self::IntoIter {
548 IntoIter {
549 iter: self.slots.into_iter(),
550 }
551 }
552}
553
554/// An iterator over the entries of an [`IndexMap`].
555///
556/// This `struct` is created by the [`iter`] method on [`IndexMap`]. See its
557/// documentation for more.
558///
559/// [`iter`]: IndexMap::iter
560#[derive(Debug, Clone)]
561pub struct Iter<'a, K, V> {
562 iter: SliceIter<'a, Slot<K, V>>,
563}
564
565impl<'a, K, V> Iterator for Iter<'a, K, V> {
566 type Item = (&'a K, &'a V);
567
568 fn size_hint(&self) -> (usize, Option<usize>) {
569 self.iter.size_hint()
570 }
571
572 fn count(self) -> usize {
573 self.iter.count()
574 }
575
576 fn next(&mut self) -> Option<Self::Item> {
577 self.iter.next().map(Slot::as_pair)
578 }
579}
580
581impl<'a, K, V> DoubleEndedIterator for Iter<'a, K, V> {
582 fn next_back(&mut self) -> Option<Self::Item> {
583 self.iter.next_back().map(Slot::as_pair)
584 }
585}
586
587impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> {
588 fn len(&self) -> usize {
589 self.iter.len()
590 }
591}
592
593impl<'a, K, V> FusedIterator for Iter<'a, K, V> {}
594
595/// A mutable iterator over the entries of an [`IndexMap`].
596///
597/// This `struct` is created by the [`iter_mut`] method on [`IndexMap`]. See its
598/// documentation for more.
599///
600/// [`iter_mut`]: IndexMap::iter_mut
601#[derive(Debug)]
602pub struct IterMut<'a, K, V> {
603 iter: SliceIterMut<'a, Slot<K, V>>,
604}
605
606impl<'a, K, V> Iterator for IterMut<'a, K, V> {
607 type Item = (&'a K, &'a mut V);
608
609 fn size_hint(&self) -> (usize, Option<usize>) {
610 self.iter.size_hint()
611 }
612
613 fn count(self) -> usize {
614 self.iter.count()
615 }
616
617 fn next(&mut self) -> Option<Self::Item> {
618 self.iter.next().map(Slot::as_pair_mut)
619 }
620}
621
622impl<'a, K, V> DoubleEndedIterator for IterMut<'a, K, V> {
623 fn next_back(&mut self) -> Option<Self::Item> {
624 self.iter.next_back().map(Slot::as_pair_mut)
625 }
626}
627
628impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> {
629 fn len(&self) -> usize {
630 self.iter.len()
631 }
632}
633
634impl<'a, K, V> FusedIterator for IterMut<'a, K, V> {}
635
636/// An owning iterator over the entries of a [`IndexMap`].
637///
638/// This `struct` is created by the [`into_iter`] method on [`IndexMap`]
639/// (provided by the [`IntoIterator`] trait). See its documentation for more.
640///
641/// [`into_iter`]: IntoIterator::into_iter
642/// [`IntoIterator`]: core::iter::IntoIterator
643#[derive(Debug)]
644pub struct IntoIter<K, V> {
645 iter: VecIntoIter<Slot<K, V>>,
646}
647
648impl<K, V> Iterator for IntoIter<K, V> {
649 type Item = (K, V);
650
651 fn size_hint(&self) -> (usize, Option<usize>) {
652 self.iter.size_hint()
653 }
654
655 fn count(self) -> usize {
656 self.iter.count()
657 }
658
659 fn next(&mut self) -> Option<Self::Item> {
660 self.iter.next().map(Slot::into_pair)
661 }
662}
663
664impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
665 fn next_back(&mut self) -> Option<Self::Item> {
666 self.iter.next_back().map(Slot::into_pair)
667 }
668}
669
670impl<K, V> ExactSizeIterator for IntoIter<K, V> {
671 fn len(&self) -> usize {
672 self.iter.len()
673 }
674}
675
676impl<K, V> FusedIterator for IntoIter<K, V> {}
677
678/// An iterator over the keys of an [`IndexMap`].
679///
680/// This `struct` is created by the [`keys`] method on [`IndexMap`]. See its
681/// documentation for more.
682///
683/// [`keys`]: IndexMap::keys
684#[derive(Debug, Clone)]
685pub struct Keys<'a, K, V> {
686 iter: SliceIter<'a, Slot<K, V>>,
687}
688
689impl<'a, K, V> Iterator for Keys<'a, K, V> {
690 type Item = &'a K;
691
692 fn size_hint(&self) -> (usize, Option<usize>) {
693 self.iter.size_hint()
694 }
695
696 fn count(self) -> usize {
697 self.iter.count()
698 }
699
700 fn next(&mut self) -> Option<Self::Item> {
701 self.iter.next().map(Slot::key)
702 }
703}
704
705impl<'a, K, V> DoubleEndedIterator for Keys<'a, K, V> {
706 fn next_back(&mut self) -> Option<Self::Item> {
707 self.iter.next_back().map(Slot::key)
708 }
709}
710
711impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> {
712 fn len(&self) -> usize {
713 self.iter.len()
714 }
715}
716
717impl<'a, K, V> FusedIterator for Keys<'a, K, V> {}
718
719/// An iterator over the values of an [`IndexMap`].
720///
721/// This `struct` is created by the [`values`] method on [`IndexMap`]. See its
722/// documentation for more.
723///
724/// [`values`]: IndexMap::values
725#[derive(Debug, Clone)]
726pub struct Values<'a, K, V> {
727 iter: SliceIter<'a, Slot<K, V>>,
728}
729
730impl<'a, K, V> Iterator for Values<'a, K, V> {
731 type Item = &'a V;
732
733 fn size_hint(&self) -> (usize, Option<usize>) {
734 self.iter.size_hint()
735 }
736
737 fn count(self) -> usize {
738 self.iter.count()
739 }
740
741 fn next(&mut self) -> Option<Self::Item> {
742 self.iter.next().map(Slot::value)
743 }
744}
745
746impl<'a, K, V> DoubleEndedIterator for Values<'a, K, V> {
747 fn next_back(&mut self) -> Option<Self::Item> {
748 self.iter.next_back().map(Slot::value)
749 }
750}
751
752impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> {
753 fn len(&self) -> usize {
754 self.iter.len()
755 }
756}
757
758impl<'a, K, V> FusedIterator for Values<'a, K, V> {}
759
760/// An iterator over the values of an [`IndexMap`].
761///
762/// This `struct` is created by the [`values`] method on [`IndexMap`]. See its
763/// documentation for more.
764///
765/// [`values`]: IndexMap::values
766#[derive(Debug)]
767pub struct ValuesMut<'a, K, V> {
768 iter: SliceIterMut<'a, Slot<K, V>>,
769}
770
771impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
772 type Item = &'a mut V;
773
774 fn size_hint(&self) -> (usize, Option<usize>) {
775 self.iter.size_hint()
776 }
777
778 fn count(self) -> usize {
779 self.iter.count()
780 }
781
782 fn next(&mut self) -> Option<Self::Item> {
783 self.iter.next().map(Slot::value_mut)
784 }
785}
786
787impl<'a, K, V> DoubleEndedIterator for ValuesMut<'a, K, V> {
788 fn next_back(&mut self) -> Option<Self::Item> {
789 self.iter.next_back().map(Slot::value_mut)
790 }
791}
792
793impl<'a, K, V> ExactSizeIterator for ValuesMut<'a, K, V> {
794 fn len(&self) -> usize {
795 self.iter.len()
796 }
797}
798
799impl<'a, K, V> FusedIterator for ValuesMut<'a, K, V> {}
800
801/// A view into a single entry in a map, which may either be vacant or occupied.
802///
803/// This `enum` is constructed from the [`entry`] method on [`IndexMap`].
804///
805/// [`entry`]: IndexMap::entry
806pub enum Entry<'a, K, V> {
807 /// A vacant entry.
808 Vacant(VacantEntry<'a, K, V>),
809 /// An occupied entry.
810 Occupied(OccupiedEntry<'a, K, V>),
811}
812
813impl<'a, K: Ord, V> Entry<'a, K, V> {
814 /// Ensures a value is in the entry by inserting the default if empty,
815 /// and returns a mutable reference to the value in the entry.
816 pub fn or_insert(self, default: V) -> &'a mut V
817 where
818 K: Clone,
819 {
820 match self {
821 Self::Occupied(entry) => entry.into_mut(),
822 Self::Vacant(entry) => entry.insert(default),
823 }
824 }
825
826 /// Ensures a value is in the entry by inserting the result
827 /// of the default function if empty,
828 /// and returns a mutable reference to the value in the entry.
829 pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V
830 where
831 K: Clone,
832 {
833 match self {
834 Self::Occupied(entry) => entry.into_mut(),
835 Self::Vacant(entry) => entry.insert(default()),
836 }
837 }
838
839 /// Ensures a value is in the entry by inserting,
840 /// if empty, the result of the default function.
841 ///
842 /// This method allows for generating key-derived values for
843 /// insertion by providing the default function a reference
844 /// to the key that was moved during the `.entry(key)` method call.
845 ///
846 /// The reference to the moved key is provided
847 /// so that cloning or copying the key is
848 /// unnecessary, unlike with `.or_insert_with(|| ... )`.
849 pub fn or_insert_with_key<F: FnOnce(&K) -> V>(self, default: F) -> &'a mut V
850 where
851 K: Clone,
852 {
853 match self {
854 Self::Occupied(entry) => entry.into_mut(),
855 Self::Vacant(entry) => {
856 let value = default(entry.key());
857 entry.insert(value)
858 }
859 }
860 }
861
862 /// Returns a reference to this entry’s key.
863 pub fn key(&self) -> &K {
864 match *self {
865 Self::Occupied(ref entry) => entry.key(),
866 Self::Vacant(ref entry) => entry.key(),
867 }
868 }
869
870 /// Provides in-place mutable access to an occupied entry
871 /// before any potential inserts into the map.
872 pub fn and_modify<F>(self, f: F) -> Self
873 where
874 F: FnOnce(&mut V),
875 {
876 match self {
877 Self::Occupied(mut entry) => {
878 f(entry.get_mut());
879 Self::Occupied(entry)
880 }
881 Self::Vacant(entry) => Self::Vacant(entry),
882 }
883 }
884}
885
886impl<'a, K, V> Entry<'a, K, V>
887where
888 K: Ord + Clone,
889 V: Default,
890{
891 /// Ensures a value is in the entry by inserting the default value if empty,
892 /// and returns a mutable reference to the value in the entry.
893 pub fn or_default(self) -> &'a mut V {
894 match self {
895 Self::Occupied(entry: OccupiedEntry<'a, K, V>) => entry.into_mut(),
896 Self::Vacant(entry: VacantEntry<'a, K, V>) => entry.insert(Default::default()),
897 }
898 }
899}
900
901impl<'a, K, V> fmt::Debug for Entry<'a, K, V>
902where
903 K: fmt::Debug + Ord,
904 V: fmt::Debug,
905{
906 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
907 match self {
908 Entry::Vacant(entry: &VacantEntry<'_, K, V>) => entry.fmt(f),
909 Entry::Occupied(entry: &OccupiedEntry<'_, K, V>) => entry.fmt(f),
910 }
911 }
912}
913
914/// A view into a vacant entry in an [`IndexMap`]. It is part of the [`Entry`] `enum`.
915pub struct VacantEntry<'a, K, V> {
916 /// The underlying vacant entry.
917 vacant: btree_map::VacantEntry<'a, K, SlotIndex>,
918 /// The vector that stores all slots.
919 slots: &'a mut Vec<Slot<K, V>>,
920}
921
922impl<'a, K, V> VacantEntry<'a, K, V>
923where
924 K: Ord,
925{
926 /// Gets a reference to the key that would be used when inserting a value through the VacantEntry.
927 pub fn key(&self) -> &K {
928 self.vacant.key()
929 }
930
931 /// Take ownership of the key.
932 pub fn into_key(self) -> K {
933 self.vacant.into_key()
934 }
935
936 /// Sets the value of the entry with the `VacantEntry`’s key,
937 /// and returns a mutable reference to it.
938 pub fn insert(self, value: V) -> &'a mut V
939 where
940 K: Clone,
941 {
942 let index: usize = self.slots.len();
943 let key: K = self.vacant.key().clone();
944 self.vacant.insert(SlotIndex(index));
945 self.slots.push(Slot::new(key, value));
946 &mut self.slots[index].value
947 }
948}
949
950impl<'a, K, V> fmt::Debug for VacantEntry<'a, K, V>
951where
952 K: fmt::Debug + Ord,
953{
954 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
955 f&mut DebugStruct<'_, '_>.debug_struct("VacantEntry")
956 .field(name:"key", self.key())
957 .finish()
958 }
959}
960
961/// A view into an occupied entry in a [`IndexMap`]. It is part of the [`Entry`] `enum`.
962pub struct OccupiedEntry<'a, K, V> {
963 /// The underlying occupied entry.
964 occupied: btree_map::OccupiedEntry<'a, K, SlotIndex>,
965 /// The vector that stores all slots.
966 slots: &'a mut Vec<Slot<K, V>>,
967}
968
969impl<'a, K, V> OccupiedEntry<'a, K, V>
970where
971 K: Ord,
972{
973 /// Gets a reference to the key in the entry.
974 pub fn key(&self) -> &K {
975 self.occupied.key()
976 }
977
978 /// Gets a reference to the value in the entry.
979 pub fn get(&self) -> &V {
980 let index = self.occupied.get().index();
981 &self.slots[index].value
982 }
983
984 /// Gets a mutable reference to the value in the entry.
985 ///
986 /// If you need a reference to the `OccupiedEntry` that may outlive the
987 /// destruction of the `Entry` value, see [`into_mut`].
988 ///
989 /// [`into_mut`]: OccupiedEntry::into_mut
990 pub fn get_mut(&mut self) -> &mut V {
991 let index = self.occupied.get().index();
992 &mut self.slots[index].value
993 }
994
995 /// Converts the entry into a mutable reference to its value.
996 ///
997 /// If you need multiple references to the `OccupiedEntry`, see [`get_mut`].
998 ///
999 /// [`get_mut`]: OccupiedEntry::get_mut
1000 pub fn into_mut(self) -> &'a mut V {
1001 let index = self.occupied.get().index();
1002 &mut self.slots[index].value
1003 }
1004
1005 /// Sets the value of the entry with the `OccupiedEntry`’s key,
1006 /// and returns the entry’s old value.
1007 pub fn insert(&mut self, value: V) -> V
1008 where
1009 K: Clone,
1010 {
1011 let index = self.occupied.get().index();
1012 let key = self.key().clone();
1013 let new_slot = Slot::new(key, value);
1014 let old_slot = replace(&mut self.slots[index], new_slot);
1015 old_slot.value
1016 }
1017}
1018
1019impl<'a, K, V> fmt::Debug for OccupiedEntry<'a, K, V>
1020where
1021 K: fmt::Debug + Ord,
1022 V: fmt::Debug,
1023{
1024 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1025 f&mut DebugStruct<'_, '_>.debug_struct("OccupiedEntry")
1026 .field("key", self.key())
1027 .field(name:"value", self.get())
1028 .finish()
1029 }
1030}
1031
1032#[cfg(feature = "serde")]
1033mod serde_impls {
1034 use super::IndexMap;
1035 use core::fmt;
1036 use core::marker::PhantomData;
1037 use serde::de::{Deserialize, MapAccess, Visitor};
1038 use serde::ser::{Serialize, SerializeMap, Serializer};
1039
1040 impl<K, V> Serialize for IndexMap<K, V>
1041 where
1042 K: Serialize + Ord,
1043 V: Serialize,
1044 {
1045 fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
1046 where
1047 S: Serializer,
1048 {
1049 let mut map = serializer.serialize_map(Some(self.len()))?;
1050 for (k, v) in self.iter() {
1051 map.serialize_entry(k, v)?;
1052 }
1053 map.end()
1054 }
1055 }
1056
1057 impl<'a, K, V> Deserialize<'a> for IndexMap<K, V>
1058 where
1059 K: Deserialize<'a> + Clone + Ord,
1060 V: Deserialize<'a>,
1061 {
1062 fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
1063 where
1064 D: serde::de::Deserializer<'a>,
1065 {
1066 deserializer.deserialize_map(IndexMapVisitor {
1067 _marker: PhantomData,
1068 })
1069 }
1070 }
1071
1072 struct IndexMapVisitor<K, V> {
1073 _marker: PhantomData<fn() -> IndexMap<K, V>>,
1074 }
1075
1076 impl<'de, K, V> Visitor<'de> for IndexMapVisitor<K, V>
1077 where
1078 K: Deserialize<'de> + Clone + Ord,
1079 V: Deserialize<'de>,
1080 {
1081 type Value = IndexMap<K, V>;
1082
1083 fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
1084 formatter.write_str("a map")
1085 }
1086
1087 fn visit_map<M>(self, mut access: M) -> Result<Self::Value, M::Error>
1088 where
1089 M: MapAccess<'de>,
1090 {
1091 let mut map = IndexMap::with_capacity(access.size_hint().unwrap_or(0));
1092
1093 while let Some((key, value)) = access.next_entry()? {
1094 map.insert(key, value);
1095 }
1096
1097 Ok(map)
1098 }
1099 }
1100}
1101