1//! Type definitions for an ordered map.
2
3use core::borrow::Borrow;
4use core::hash::Hash;
5use core::iter::FusedIterator;
6use core::ops::Index;
7
8mod detail;
9
10#[cfg(test)]
11mod tests;
12
13/// A hash table where the iteration order of the key-value pairs is independent of the hash values of the keys.
14///
15/// Provides an API compatible with both [`IndexMap`] and a custom implementation based on [`BTreeMap`].
16///
17/// [`IndexMap`]: indexmap::IndexMap
18/// [`BTreeMap`]: alloc::collections::BTreeMap
19#[derive(Debug, Clone)]
20pub struct IndexMap<K, V> {
21 inner: detail::IndexMapImpl<K, V>,
22}
23
24impl<K, V> Default for IndexMap<K, V> {
25 #[inline]
26 fn default() -> Self {
27 Self {
28 inner: detail::IndexMapImpl::default(),
29 }
30 }
31}
32
33impl<K, V> IndexMap<K, V> {
34 /// Clears the [`IndexMap`], removing all elements.
35 #[inline]
36 pub fn clear(&mut self) {
37 self.inner.clear()
38 }
39
40 /// Returns the number of elements in the [`IndexMap`].
41 #[inline]
42 pub fn len(&self) -> usize {
43 self.inner.len()
44 }
45
46 /// Returns `true` if the [`IndexMap`] contains no elements.
47 #[inline]
48 pub fn is_empty(&self) -> bool {
49 self.inner.is_empty()
50 }
51
52 /// Returns an iterator that yields the items in the [`IndexMap`].
53 #[inline]
54 pub fn iter(&self) -> Iter<'_, K, V> {
55 Iter {
56 inner: self.inner.iter(),
57 }
58 }
59
60 /// Returns an iterator that yields the mutable items in the [`IndexMap`].
61 #[inline]
62 pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
63 IterMut {
64 inner: self.inner.iter_mut(),
65 }
66 }
67
68 /// Returns an iterator that yields the keys in the [`IndexMap`].
69 #[inline]
70 pub fn keys(&self) -> Keys<'_, K, V> {
71 Keys {
72 inner: self.inner.keys(),
73 }
74 }
75
76 /// Returns an iterator that yields the values in the [`IndexMap`].
77 #[inline]
78 pub fn values(&self) -> Values<'_, K, V> {
79 Values {
80 inner: self.inner.values(),
81 }
82 }
83
84 /// Returns a mutable iterator that yields the values in the [`IndexMap`].
85 #[inline]
86 pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {
87 ValuesMut {
88 inner: self.inner.values_mut(),
89 }
90 }
91
92 /// Returns the key-value entry at the given `index` if any.
93 #[inline]
94 pub fn get_index(&self, index: usize) -> Option<(&K, &V)> {
95 self.inner.get_index(index)
96 }
97
98 /// Returns the mutable key-value entry at the given `index` if any.
99 #[inline]
100 pub fn get_index_mut(&mut self, index: usize) -> Option<(&K, &mut V)> {
101 self.inner.get_index_mut(index)
102 }
103}
104
105impl<K, V> IndexMap<K, V>
106where
107 K: Hash + Eq + Ord + Clone,
108{
109 /// Reserves capacity for at least `additional` more elements to be inserted in the [`IndexMap`].
110 #[inline]
111 pub fn reserve(&mut self, additional: usize) {
112 self.inner.reserve(additional);
113 }
114
115 /// Returns true if `key` is contains in the [`IndexMap`].
116 #[inline]
117 pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool
118 where
119 K: Borrow<Q>,
120 Q: Hash + Eq + Ord,
121 {
122 self.inner.contains_key(key)
123 }
124
125 /// Returns a reference to the value corresponding to the `key`.
126 #[inline]
127 pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V>
128 where
129 K: Borrow<Q>,
130 Q: Hash + Eq + Ord,
131 {
132 self.inner.get(key)
133 }
134
135 /// Return references to the key-value pair stored for `key`,
136 /// if it is present, else `None`.
137 #[inline]
138 pub fn get_key_value<Q: ?Sized>(&self, key: &Q) -> Option<(&K, &V)>
139 where
140 K: Borrow<Q>,
141 Q: Hash + Eq + Ord,
142 {
143 self.inner.get_key_value(key)
144 }
145
146 /// Returns the key-value pair corresponding to the supplied key
147 /// as well as the unique index of the returned key-value pair.
148 ///
149 /// The supplied key may be any borrowed form of the map's key type,
150 /// but the ordering on the borrowed form *must* match the ordering
151 /// on the key type.
152 #[inline]
153 pub fn get_full<Q: ?Sized>(&self, key: &Q) -> Option<(usize, &K, &V)>
154 where
155 K: Borrow<Q> + Ord,
156 Q: Hash + Eq + Ord,
157 {
158 self.inner.get_full(key)
159 }
160
161 /// Returns a mutable reference to the value corresponding to the key.
162 #[inline]
163 pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V>
164 where
165 K: Borrow<Q>,
166 Q: Hash + Eq + Ord,
167 {
168 self.inner.get_mut(key)
169 }
170
171 /// Inserts a key-value pair into the [`IndexMap`].
172 ///
173 /// If the map did not have this key present, `None` is returned.
174 ///
175 /// If the map did have this key present, the value is updated, and the old
176 /// value is returned. The key is not updated, though; this matters for
177 /// types that can be `==` without being identical.
178 #[inline]
179 pub fn insert(&mut self, key: K, value: V) -> Option<V> {
180 self.inner.insert(key, value)
181 }
182
183 /// Remove the key-value pair equivalent to `key` and return its value.
184 ///
185 /// Like [`Vec::swap_remove`], the pair is removed by swapping it with the
186 /// last element of the map and popping it off. **This perturbs
187 /// the position of what used to be the last element!**
188 ///
189 /// Return `None` if `key` is not in map.
190 ///
191 /// [`Vec::swap_remove`]: alloc::vec::Vec::swap_remove
192 #[inline]
193 pub fn swap_remove<Q>(&mut self, key: &Q) -> Option<V>
194 where
195 K: Borrow<Q>,
196 Q: ?Sized + Hash + Eq + Ord,
197 {
198 self.inner.swap_remove(key)
199 }
200
201 /// Remove and return the key-value pair equivalent to `key`.
202 ///
203 /// Like [`Vec::swap_remove`], the pair is removed by swapping it with the
204 /// last element of the map and popping it off. **This perturbs
205 /// the position of what used to be the last element!**
206 ///
207 /// Return `None` if `key` is not in map.
208 ///
209 /// [`Vec::swap_remove`]: alloc::vec::Vec::swap_remove
210 #[inline]
211 pub fn swap_remove_entry<Q>(&mut self, key: &Q) -> Option<(K, V)>
212 where
213 K: Borrow<Q>,
214 Q: ?Sized + Hash + Eq + Ord,
215 {
216 self.inner.swap_remove_entry(key)
217 }
218
219 /// Gets the given key's corresponding entry in the [`IndexMap`] for in-place manipulation.
220 #[inline]
221 pub fn entry(&mut self, key: K) -> Entry<'_, K, V> {
222 match self.inner.entry(key) {
223 detail::EntryImpl::Occupied(entry) => Entry::Occupied(OccupiedEntry { inner: entry }),
224 detail::EntryImpl::Vacant(entry) => Entry::Vacant(VacantEntry { inner: entry }),
225 }
226 }
227}
228
229impl<K, Q, V> Index<&Q> for IndexMap<K, V>
230where
231 K: Borrow<Q> + Hash + Eq + Ord,
232 Q: ?Sized + Hash + Eq + Ord,
233{
234 type Output = V;
235
236 #[inline]
237 fn index(&self, key: &Q) -> &V {
238 &self.inner[key]
239 }
240}
241
242impl<K, V> Index<usize> for IndexMap<K, V>
243where
244 K: Hash + Eq + Ord,
245{
246 type Output = V;
247
248 #[inline]
249 fn index(&self, key: usize) -> &V {
250 &self.inner[key]
251 }
252}
253
254impl<K, V> Extend<(K, V)> for IndexMap<K, V>
255where
256 K: Eq + Hash + Ord + Clone,
257{
258 #[inline]
259 fn extend<Iter: IntoIterator<Item = (K, V)>>(&mut self, iter: Iter) {
260 self.inner.extend(iter)
261 }
262}
263
264/// A view into a single entry in a [`IndexMap`], which may either be vacant or occupied.
265///
266/// This enum is constructed from the entry method on [`IndexMap`].
267#[derive(Debug)]
268pub enum Entry<'a, K: Ord, V> {
269 /// An occupied entry.
270 Occupied(OccupiedEntry<'a, K, V>),
271 /// A vacant entry.
272 Vacant(VacantEntry<'a, K, V>),
273}
274
275impl<'a, K, V> Entry<'a, K, V>
276where
277 K: Hash + Eq + Ord + Clone,
278{
279 /// Returns a reference to this entry's key.
280 #[inline]
281 pub fn key(&self) -> &K {
282 match *self {
283 Self::Occupied(ref entry: &OccupiedEntry<'a, K, V>) => entry.key(),
284 Self::Vacant(ref entry: &VacantEntry<'a, K, V>) => entry.key(),
285 }
286 }
287}
288
289impl<'a, K, V> Entry<'a, K, V>
290where
291 K: Hash + Eq + Ord + Clone,
292 V: Default,
293{
294 /// Ensures a value is in the entry by inserting the default value if empty,
295 /// and returns a mutable reference to the value in the entry.
296 #[inline]
297 pub fn or_default(self) -> &'a mut V {
298 match self {
299 Self::Occupied(entry: OccupiedEntry<'a, K, V>) => entry.into_mut(),
300 Self::Vacant(entry: VacantEntry<'a, K, V>) => entry.insert(Default::default()),
301 }
302 }
303}
304
305/// A view into an occupied entry in a [`IndexMap`].
306///
307/// It is part of the [`Entry`] enum.
308#[derive(Debug)]
309pub struct OccupiedEntry<'a, K: Ord, V> {
310 inner: detail::OccupiedEntryImpl<'a, K, V>,
311}
312
313impl<'a, K: 'a, V: 'a> OccupiedEntry<'a, K, V>
314where
315 K: Ord + Clone,
316{
317 /// Gets a reference to the key in the entry.
318 #[inline]
319 pub fn key(&self) -> &K {
320 self.inner.key()
321 }
322
323 /// Gets a reference to the value in the entry.
324 #[inline]
325 pub fn get(&self) -> &V {
326 self.inner.get()
327 }
328
329 /// Gets a mutable reference to the value in the entry.
330 #[inline]
331 pub fn get_mut(&mut self) -> &mut V {
332 self.inner.get_mut()
333 }
334
335 /// Sets the value of the entry with the [`OccupiedEntry`]'s key, and returns the entry's old value.
336 #[inline]
337 pub fn insert(&mut self, value: V) -> V {
338 self.inner.insert(value)
339 }
340
341 /// Converts the [`OccupiedEntry`] into a mutable reference to the value in the entry
342 /// with a lifetime bound to the map itself.
343 #[inline]
344 pub fn into_mut(self) -> &'a mut V {
345 self.inner.into_mut()
346 }
347}
348
349/// A view into a vacant entry in a [`IndexMap`].
350///
351/// It is part of the [`Entry`] enum.
352#[derive(Debug)]
353pub struct VacantEntry<'a, K: Ord, V> {
354 inner: detail::VacantEntryImpl<'a, K, V>,
355}
356
357impl<'a, K: 'a, V: 'a> VacantEntry<'a, K, V>
358where
359 K: Ord + Clone,
360{
361 /// Gets a reference to the key in the entry.
362 #[inline]
363 pub fn key(&self) -> &K {
364 self.inner.key()
365 }
366
367 /// Take ownership of the key.
368 #[inline]
369 pub fn into_key(self) -> K {
370 self.inner.into_key()
371 }
372
373 /// Sets the value of the entry with the [`VacantEntry`]'s key, and returns a mutable reference to it.
374 #[inline]
375 pub fn insert(self, value: V) -> &'a mut V
376 where
377 K: Hash,
378 {
379 self.inner.insert(value)
380 }
381}
382
383impl<K, V> FromIterator<(K, V)> for IndexMap<K, V>
384where
385 K: Hash + Ord + Eq + Clone,
386{
387 #[inline]
388 fn from_iter<I>(iter: I) -> Self
389 where
390 I: IntoIterator<Item = (K, V)>,
391 {
392 Self {
393 inner: <detail::IndexMapImpl<K, V>>::from_iter(iter),
394 }
395 }
396}
397
398impl<'a, K, V> IntoIterator for &'a IndexMap<K, V> {
399 type Item = (&'a K, &'a V);
400 type IntoIter = Iter<'a, K, V>;
401
402 #[inline]
403 fn into_iter(self) -> Self::IntoIter {
404 self.iter()
405 }
406}
407
408/// An iterator over the items of a [`IndexMap`].
409#[derive(Debug, Clone)]
410pub struct Iter<'a, K, V> {
411 inner: detail::IterImpl<'a, K, V>,
412}
413
414impl<'a, K, V> Iterator for Iter<'a, K, V> {
415 type Item = (&'a K, &'a V);
416
417 #[inline]
418 fn size_hint(&self) -> (usize, Option<usize>) {
419 self.inner.size_hint()
420 }
421
422 #[inline]
423 fn next(&mut self) -> Option<Self::Item> {
424 self.inner.next()
425 }
426}
427
428impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> {
429 #[inline]
430 fn len(&self) -> usize {
431 self.inner.len()
432 }
433}
434
435impl<'a, K, V> FusedIterator for Iter<'a, K, V> {}
436
437impl<'a, K, V> IntoIterator for &'a mut IndexMap<K, V> {
438 type Item = (&'a K, &'a mut V);
439 type IntoIter = IterMut<'a, K, V>;
440
441 #[inline]
442 fn into_iter(self) -> Self::IntoIter {
443 self.iter_mut()
444 }
445}
446
447/// An iterator over the mutable items of a [`IndexMap`].
448#[derive(Debug)]
449pub struct IterMut<'a, K, V> {
450 inner: detail::IterMutImpl<'a, K, V>,
451}
452
453impl<'a, K, V> Iterator for IterMut<'a, K, V> {
454 type Item = (&'a K, &'a mut V);
455
456 #[inline]
457 fn size_hint(&self) -> (usize, Option<usize>) {
458 self.inner.size_hint()
459 }
460
461 #[inline]
462 fn next(&mut self) -> Option<Self::Item> {
463 self.inner.next()
464 }
465}
466
467impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> {
468 #[inline]
469 fn len(&self) -> usize {
470 self.inner.len()
471 }
472}
473
474impl<'a, K, V> FusedIterator for IterMut<'a, K, V> {}
475
476impl<K, V> IntoIterator for IndexMap<K, V> {
477 type Item = (K, V);
478 type IntoIter = IntoIter<K, V>;
479
480 #[inline]
481 fn into_iter(self) -> Self::IntoIter {
482 IntoIter {
483 inner: self.inner.into_iter(),
484 }
485 }
486}
487
488/// An iterator over the owned items of an [`IndexMap`].
489#[derive(Debug)]
490pub struct IntoIter<K, V> {
491 inner: detail::IntoIterImpl<K, V>,
492}
493
494impl<'a, K, V> Iterator for IntoIter<K, V> {
495 type Item = (K, V);
496
497 #[inline]
498 fn size_hint(&self) -> (usize, Option<usize>) {
499 self.inner.size_hint()
500 }
501
502 #[inline]
503 fn next(&mut self) -> Option<Self::Item> {
504 self.inner.next()
505 }
506}
507
508impl<'a, K, V> ExactSizeIterator for IntoIter<K, V> {
509 #[inline]
510 fn len(&self) -> usize {
511 self.inner.len()
512 }
513}
514
515impl<'a, K, V> FusedIterator for IntoIter<K, V> {}
516
517/// An iterator over the keys of a [`IndexMap`].
518#[derive(Debug, Clone)]
519pub struct Keys<'a, K, V> {
520 inner: detail::KeysImpl<'a, K, V>,
521}
522
523impl<'a, K, V> Iterator for Keys<'a, K, V> {
524 type Item = &'a K;
525
526 #[inline]
527 fn size_hint(&self) -> (usize, Option<usize>) {
528 self.inner.size_hint()
529 }
530
531 #[inline]
532 fn next(&mut self) -> Option<Self::Item> {
533 self.inner.next()
534 }
535}
536
537impl<'a, K, V> ExactSizeIterator for Keys<'a, K, V> {
538 #[inline]
539 fn len(&self) -> usize {
540 self.inner.len()
541 }
542}
543
544impl<'a, K, V> FusedIterator for Keys<'a, K, V> {}
545
546/// An iterator over the values of a [`IndexMap`].
547#[derive(Debug, Clone)]
548pub struct Values<'a, K, V> {
549 inner: detail::ValuesImpl<'a, K, V>,
550}
551
552impl<'a, K, V> Iterator for Values<'a, K, V> {
553 type Item = &'a V;
554
555 #[inline]
556 fn size_hint(&self) -> (usize, Option<usize>) {
557 self.inner.size_hint()
558 }
559
560 #[inline]
561 fn next(&mut self) -> Option<Self::Item> {
562 self.inner.next()
563 }
564}
565
566impl<'a, K, V> ExactSizeIterator for Values<'a, K, V> {
567 #[inline]
568 fn len(&self) -> usize {
569 self.inner.len()
570 }
571}
572
573impl<'a, K, V> FusedIterator for Values<'a, K, V> {}
574
575/// An mutable iterator over the values of a [`IndexMap`].
576#[derive(Debug)]
577pub struct ValuesMut<'a, K, V> {
578 inner: detail::ValuesMutImpl<'a, K, V>,
579}
580
581impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
582 type Item = &'a mut V;
583
584 #[inline]
585 fn size_hint(&self) -> (usize, Option<usize>) {
586 self.inner.size_hint()
587 }
588
589 #[inline]
590 fn next(&mut self) -> Option<Self::Item> {
591 self.inner.next()
592 }
593}
594
595impl<'a, K, V> ExactSizeIterator for ValuesMut<'a, K, V> {
596 #[inline]
597 fn len(&self) -> usize {
598 self.inner.len()
599 }
600}
601
602impl<'a, K, V> FusedIterator for ValuesMut<'a, K, V> {}
603
604#[cfg(feature = "serde")]
605impl<K, V> serde::Serialize for IndexMap<K, V>
606where
607 K: serde::Serialize + Eq + Hash + Ord,
608 V: serde::Serialize,
609{
610 fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
611 where
612 S: serde::ser::Serializer,
613 {
614 serde::Serialize::serialize(&self.inner, serializer)
615 }
616}
617
618#[cfg(feature = "serde")]
619impl<'a, K, V> serde::Deserialize<'a> for IndexMap<K, V>
620where
621 K: serde::Deserialize<'a> + Eq + Hash + Ord + Clone,
622 V: serde::Deserialize<'a>,
623{
624 fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
625 where
626 D: serde::de::Deserializer<'a>,
627 {
628 Ok(IndexMap {
629 inner: serde::Deserialize::deserialize(deserializer)?,
630 })
631 }
632}
633
634impl<K, V> PartialEq for IndexMap<K, V>
635where
636 K: PartialEq + Hash + Ord,
637 V: PartialEq,
638{
639 fn eq(&self, other: &Self) -> bool {
640 self.inner == other.inner
641 }
642
643 fn ne(&self, other: &Self) -> bool {
644 self.inner != other.inner
645 }
646}
647
648impl<K, V> Eq for IndexMap<K, V>
649where
650 K: Eq + Hash + Ord,
651 V: Eq,
652{
653}
654