summaryrefslogtreecommitdiffstats
path: root/third_party/rust/indexmap/src/map/iter.rs
diff options
context:
space:
mode:
Diffstat (limited to 'third_party/rust/indexmap/src/map/iter.rs')
-rw-r--r--third_party/rust/indexmap/src/map/iter.rs713
1 files changed, 713 insertions, 0 deletions
diff --git a/third_party/rust/indexmap/src/map/iter.rs b/third_party/rust/indexmap/src/map/iter.rs
new file mode 100644
index 0000000000..1ec3703cfb
--- /dev/null
+++ b/third_party/rust/indexmap/src/map/iter.rs
@@ -0,0 +1,713 @@
+use super::core::IndexMapCore;
+use super::{Bucket, Entries, IndexMap, Slice};
+
+use alloc::vec::{self, Vec};
+use core::fmt;
+use core::hash::{BuildHasher, Hash};
+use core::iter::FusedIterator;
+use core::ops::{Index, RangeBounds};
+use core::slice;
+
+impl<'a, K, V, S> IntoIterator for &'a IndexMap<K, V, S> {
+ type Item = (&'a K, &'a V);
+ type IntoIter = Iter<'a, K, V>;
+
+ fn into_iter(self) -> Self::IntoIter {
+ self.iter()
+ }
+}
+
+impl<'a, K, V, S> IntoIterator for &'a mut IndexMap<K, V, S> {
+ type Item = (&'a K, &'a mut V);
+ type IntoIter = IterMut<'a, K, V>;
+
+ fn into_iter(self) -> Self::IntoIter {
+ self.iter_mut()
+ }
+}
+
+impl<K, V, S> IntoIterator for IndexMap<K, V, S> {
+ type Item = (K, V);
+ type IntoIter = IntoIter<K, V>;
+
+ fn into_iter(self) -> Self::IntoIter {
+ IntoIter::new(self.into_entries())
+ }
+}
+
+/// An iterator over the entries of an [`IndexMap`].
+///
+/// This `struct` is created by the [`IndexMap::iter`] method.
+/// See its documentation for more.
+pub struct Iter<'a, K, V> {
+ iter: slice::Iter<'a, Bucket<K, V>>,
+}
+
+impl<'a, K, V> Iter<'a, K, V> {
+ pub(super) fn new(entries: &'a [Bucket<K, V>]) -> Self {
+ Self {
+ iter: entries.iter(),
+ }
+ }
+
+ /// Returns a slice of the remaining entries in the iterator.
+ pub fn as_slice(&self) -> &'a Slice<K, V> {
+ Slice::from_slice(self.iter.as_slice())
+ }
+}
+
+impl<'a, K, V> Iterator for Iter<'a, K, V> {
+ type Item = (&'a K, &'a V);
+
+ iterator_methods!(Bucket::refs);
+}
+
+impl<K, V> DoubleEndedIterator for Iter<'_, K, V> {
+ double_ended_iterator_methods!(Bucket::refs);
+}
+
+impl<K, V> ExactSizeIterator for Iter<'_, K, V> {
+ fn len(&self) -> usize {
+ self.iter.len()
+ }
+}
+
+impl<K, V> FusedIterator for Iter<'_, K, V> {}
+
+// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
+impl<K, V> Clone for Iter<'_, K, V> {
+ fn clone(&self) -> Self {
+ Iter {
+ iter: self.iter.clone(),
+ }
+ }
+}
+
+impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Iter<'_, K, V> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_list().entries(self.clone()).finish()
+ }
+}
+
+impl<K, V> Default for Iter<'_, K, V> {
+ fn default() -> Self {
+ Self { iter: [].iter() }
+ }
+}
+
+/// A mutable iterator over the entries of an [`IndexMap`].
+///
+/// This `struct` is created by the [`IndexMap::iter_mut`] method.
+/// See its documentation for more.
+pub struct IterMut<'a, K, V> {
+ iter: slice::IterMut<'a, Bucket<K, V>>,
+}
+
+impl<'a, K, V> IterMut<'a, K, V> {
+ pub(super) fn new(entries: &'a mut [Bucket<K, V>]) -> Self {
+ Self {
+ iter: entries.iter_mut(),
+ }
+ }
+
+ /// Returns a slice of the remaining entries in the iterator.
+ pub fn as_slice(&self) -> &Slice<K, V> {
+ Slice::from_slice(self.iter.as_slice())
+ }
+
+ /// Returns a mutable slice of the remaining entries in the iterator.
+ ///
+ /// To avoid creating `&mut` references that alias, this is forced to consume the iterator.
+ pub fn into_slice(self) -> &'a mut Slice<K, V> {
+ Slice::from_mut_slice(self.iter.into_slice())
+ }
+}
+
+impl<'a, K, V> Iterator for IterMut<'a, K, V> {
+ type Item = (&'a K, &'a mut V);
+
+ iterator_methods!(Bucket::ref_mut);
+}
+
+impl<K, V> DoubleEndedIterator for IterMut<'_, K, V> {
+ double_ended_iterator_methods!(Bucket::ref_mut);
+}
+
+impl<K, V> ExactSizeIterator for IterMut<'_, K, V> {
+ fn len(&self) -> usize {
+ self.iter.len()
+ }
+}
+
+impl<K, V> FusedIterator for IterMut<'_, K, V> {}
+
+impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IterMut<'_, K, V> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ let iter = self.iter.as_slice().iter().map(Bucket::refs);
+ f.debug_list().entries(iter).finish()
+ }
+}
+
+impl<K, V> Default for IterMut<'_, K, V> {
+ fn default() -> Self {
+ Self {
+ iter: [].iter_mut(),
+ }
+ }
+}
+
+/// An owning iterator over the entries of an [`IndexMap`].
+///
+/// This `struct` is created by the [`IndexMap::into_iter`] method
+/// (provided by the [`IntoIterator`] trait). See its documentation for more.
+pub struct IntoIter<K, V> {
+ iter: vec::IntoIter<Bucket<K, V>>,
+}
+
+impl<K, V> IntoIter<K, V> {
+ pub(super) fn new(entries: Vec<Bucket<K, V>>) -> Self {
+ Self {
+ iter: entries.into_iter(),
+ }
+ }
+
+ /// Returns a slice of the remaining entries in the iterator.
+ pub fn as_slice(&self) -> &Slice<K, V> {
+ Slice::from_slice(self.iter.as_slice())
+ }
+
+ /// Returns a mutable slice of the remaining entries in the iterator.
+ pub fn as_mut_slice(&mut self) -> &mut Slice<K, V> {
+ Slice::from_mut_slice(self.iter.as_mut_slice())
+ }
+}
+
+impl<K, V> Iterator for IntoIter<K, V> {
+ type Item = (K, V);
+
+ iterator_methods!(Bucket::key_value);
+}
+
+impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
+ double_ended_iterator_methods!(Bucket::key_value);
+}
+
+impl<K, V> ExactSizeIterator for IntoIter<K, V> {
+ fn len(&self) -> usize {
+ self.iter.len()
+ }
+}
+
+impl<K, V> FusedIterator for IntoIter<K, V> {}
+
+impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IntoIter<K, V> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ let iter = self.iter.as_slice().iter().map(Bucket::refs);
+ f.debug_list().entries(iter).finish()
+ }
+}
+
+impl<K, V> Default for IntoIter<K, V> {
+ fn default() -> Self {
+ Self {
+ iter: Vec::new().into_iter(),
+ }
+ }
+}
+
+/// A draining iterator over the entries of an [`IndexMap`].
+///
+/// This `struct` is created by the [`IndexMap::drain`] method.
+/// See its documentation for more.
+pub struct Drain<'a, K, V> {
+ iter: vec::Drain<'a, Bucket<K, V>>,
+}
+
+impl<'a, K, V> Drain<'a, K, V> {
+ pub(super) fn new(iter: vec::Drain<'a, Bucket<K, V>>) -> Self {
+ Self { iter }
+ }
+
+ /// Returns a slice of the remaining entries in the iterator.
+ pub fn as_slice(&self) -> &Slice<K, V> {
+ Slice::from_slice(self.iter.as_slice())
+ }
+}
+
+impl<K, V> Iterator for Drain<'_, K, V> {
+ type Item = (K, V);
+
+ iterator_methods!(Bucket::key_value);
+}
+
+impl<K, V> DoubleEndedIterator for Drain<'_, K, V> {
+ double_ended_iterator_methods!(Bucket::key_value);
+}
+
+impl<K, V> ExactSizeIterator for Drain<'_, K, V> {
+ fn len(&self) -> usize {
+ self.iter.len()
+ }
+}
+
+impl<K, V> FusedIterator for Drain<'_, K, V> {}
+
+impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Drain<'_, K, V> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ let iter = self.iter.as_slice().iter().map(Bucket::refs);
+ f.debug_list().entries(iter).finish()
+ }
+}
+
+/// An iterator over the keys of an [`IndexMap`].
+///
+/// This `struct` is created by the [`IndexMap::keys`] method.
+/// See its documentation for more.
+pub struct Keys<'a, K, V> {
+ iter: slice::Iter<'a, Bucket<K, V>>,
+}
+
+impl<'a, K, V> Keys<'a, K, V> {
+ pub(super) fn new(entries: &'a [Bucket<K, V>]) -> Self {
+ Self {
+ iter: entries.iter(),
+ }
+ }
+}
+
+impl<'a, K, V> Iterator for Keys<'a, K, V> {
+ type Item = &'a K;
+
+ iterator_methods!(Bucket::key_ref);
+}
+
+impl<K, V> DoubleEndedIterator for Keys<'_, K, V> {
+ double_ended_iterator_methods!(Bucket::key_ref);
+}
+
+impl<K, V> ExactSizeIterator for Keys<'_, K, V> {
+ fn len(&self) -> usize {
+ self.iter.len()
+ }
+}
+
+impl<K, V> FusedIterator for Keys<'_, K, V> {}
+
+// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
+impl<K, V> Clone for Keys<'_, K, V> {
+ fn clone(&self) -> Self {
+ Keys {
+ iter: self.iter.clone(),
+ }
+ }
+}
+
+impl<K: fmt::Debug, V> fmt::Debug for Keys<'_, K, V> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_list().entries(self.clone()).finish()
+ }
+}
+
+impl<K, V> Default for Keys<'_, K, V> {
+ fn default() -> Self {
+ Self { iter: [].iter() }
+ }
+}
+
+/// Access [`IndexMap`] keys at indexed positions.
+///
+/// While [`Index<usize> for IndexMap`][values] accesses a map's values,
+/// indexing through [`IndexMap::keys`] offers an alternative to access a map's
+/// keys instead.
+///
+/// [values]: IndexMap#impl-Index<usize>-for-IndexMap<K,+V,+S>
+///
+/// Since `Keys` is also an iterator, consuming items from the iterator will
+/// offset the effective indexes. Similarly, if `Keys` is obtained from
+/// [`Slice::keys`], indexes will be interpreted relative to the position of
+/// that slice.
+///
+/// # Examples
+///
+/// ```
+/// use indexmap::IndexMap;
+///
+/// let mut map = IndexMap::new();
+/// for word in "Lorem ipsum dolor sit amet".split_whitespace() {
+/// map.insert(word.to_lowercase(), word.to_uppercase());
+/// }
+///
+/// assert_eq!(map[0], "LOREM");
+/// assert_eq!(map.keys()[0], "lorem");
+/// assert_eq!(map[1], "IPSUM");
+/// assert_eq!(map.keys()[1], "ipsum");
+///
+/// map.reverse();
+/// assert_eq!(map.keys()[0], "amet");
+/// assert_eq!(map.keys()[1], "sit");
+///
+/// map.sort_keys();
+/// assert_eq!(map.keys()[0], "amet");
+/// assert_eq!(map.keys()[1], "dolor");
+///
+/// // Advancing the iterator will offset the indexing
+/// let mut keys = map.keys();
+/// assert_eq!(keys[0], "amet");
+/// assert_eq!(keys.next().map(|s| &**s), Some("amet"));
+/// assert_eq!(keys[0], "dolor");
+/// assert_eq!(keys[1], "ipsum");
+///
+/// // Slices may have an offset as well
+/// let slice = &map[2..];
+/// assert_eq!(slice[0], "IPSUM");
+/// assert_eq!(slice.keys()[0], "ipsum");
+/// ```
+///
+/// ```should_panic
+/// use indexmap::IndexMap;
+///
+/// let mut map = IndexMap::new();
+/// map.insert("foo", 1);
+/// println!("{:?}", map.keys()[10]); // panics!
+/// ```
+impl<'a, K, V> Index<usize> for Keys<'a, K, V> {
+ type Output = K;
+
+ /// Returns a reference to the key at the supplied `index`.
+ ///
+ /// ***Panics*** if `index` is out of bounds.
+ fn index(&self, index: usize) -> &K {
+ &self.iter.as_slice()[index].key
+ }
+}
+
+/// An owning iterator over the keys of an [`IndexMap`].
+///
+/// This `struct` is created by the [`IndexMap::into_keys`] method.
+/// See its documentation for more.
+pub struct IntoKeys<K, V> {
+ iter: vec::IntoIter<Bucket<K, V>>,
+}
+
+impl<K, V> IntoKeys<K, V> {
+ pub(super) fn new(entries: Vec<Bucket<K, V>>) -> Self {
+ Self {
+ iter: entries.into_iter(),
+ }
+ }
+}
+
+impl<K, V> Iterator for IntoKeys<K, V> {
+ type Item = K;
+
+ iterator_methods!(Bucket::key);
+}
+
+impl<K, V> DoubleEndedIterator for IntoKeys<K, V> {
+ double_ended_iterator_methods!(Bucket::key);
+}
+
+impl<K, V> ExactSizeIterator for IntoKeys<K, V> {
+ fn len(&self) -> usize {
+ self.iter.len()
+ }
+}
+
+impl<K, V> FusedIterator for IntoKeys<K, V> {}
+
+impl<K: fmt::Debug, V> fmt::Debug for IntoKeys<K, V> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ let iter = self.iter.as_slice().iter().map(Bucket::key_ref);
+ f.debug_list().entries(iter).finish()
+ }
+}
+
+impl<K, V> Default for IntoKeys<K, V> {
+ fn default() -> Self {
+ Self {
+ iter: Vec::new().into_iter(),
+ }
+ }
+}
+
+/// An iterator over the values of an [`IndexMap`].
+///
+/// This `struct` is created by the [`IndexMap::values`] method.
+/// See its documentation for more.
+pub struct Values<'a, K, V> {
+ iter: slice::Iter<'a, Bucket<K, V>>,
+}
+
+impl<'a, K, V> Values<'a, K, V> {
+ pub(super) fn new(entries: &'a [Bucket<K, V>]) -> Self {
+ Self {
+ iter: entries.iter(),
+ }
+ }
+}
+
+impl<'a, K, V> Iterator for Values<'a, K, V> {
+ type Item = &'a V;
+
+ iterator_methods!(Bucket::value_ref);
+}
+
+impl<K, V> DoubleEndedIterator for Values<'_, K, V> {
+ double_ended_iterator_methods!(Bucket::value_ref);
+}
+
+impl<K, V> ExactSizeIterator for Values<'_, K, V> {
+ fn len(&self) -> usize {
+ self.iter.len()
+ }
+}
+
+impl<K, V> FusedIterator for Values<'_, K, V> {}
+
+// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
+impl<K, V> Clone for Values<'_, K, V> {
+ fn clone(&self) -> Self {
+ Values {
+ iter: self.iter.clone(),
+ }
+ }
+}
+
+impl<K, V: fmt::Debug> fmt::Debug for Values<'_, K, V> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ f.debug_list().entries(self.clone()).finish()
+ }
+}
+
+impl<K, V> Default for Values<'_, K, V> {
+ fn default() -> Self {
+ Self { iter: [].iter() }
+ }
+}
+
+/// A mutable iterator over the values of an [`IndexMap`].
+///
+/// This `struct` is created by the [`IndexMap::values_mut`] method.
+/// See its documentation for more.
+pub struct ValuesMut<'a, K, V> {
+ iter: slice::IterMut<'a, Bucket<K, V>>,
+}
+
+impl<'a, K, V> ValuesMut<'a, K, V> {
+ pub(super) fn new(entries: &'a mut [Bucket<K, V>]) -> Self {
+ Self {
+ iter: entries.iter_mut(),
+ }
+ }
+}
+
+impl<'a, K, V> Iterator for ValuesMut<'a, K, V> {
+ type Item = &'a mut V;
+
+ iterator_methods!(Bucket::value_mut);
+}
+
+impl<K, V> DoubleEndedIterator for ValuesMut<'_, K, V> {
+ double_ended_iterator_methods!(Bucket::value_mut);
+}
+
+impl<K, V> ExactSizeIterator for ValuesMut<'_, K, V> {
+ fn len(&self) -> usize {
+ self.iter.len()
+ }
+}
+
+impl<K, V> FusedIterator for ValuesMut<'_, K, V> {}
+
+impl<K, V: fmt::Debug> fmt::Debug for ValuesMut<'_, K, V> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ let iter = self.iter.as_slice().iter().map(Bucket::value_ref);
+ f.debug_list().entries(iter).finish()
+ }
+}
+
+impl<K, V> Default for ValuesMut<'_, K, V> {
+ fn default() -> Self {
+ Self {
+ iter: [].iter_mut(),
+ }
+ }
+}
+
+/// An owning iterator over the values of an [`IndexMap`].
+///
+/// This `struct` is created by the [`IndexMap::into_values`] method.
+/// See its documentation for more.
+pub struct IntoValues<K, V> {
+ iter: vec::IntoIter<Bucket<K, V>>,
+}
+
+impl<K, V> IntoValues<K, V> {
+ pub(super) fn new(entries: Vec<Bucket<K, V>>) -> Self {
+ Self {
+ iter: entries.into_iter(),
+ }
+ }
+}
+
+impl<K, V> Iterator for IntoValues<K, V> {
+ type Item = V;
+
+ iterator_methods!(Bucket::value);
+}
+
+impl<K, V> DoubleEndedIterator for IntoValues<K, V> {
+ double_ended_iterator_methods!(Bucket::value);
+}
+
+impl<K, V> ExactSizeIterator for IntoValues<K, V> {
+ fn len(&self) -> usize {
+ self.iter.len()
+ }
+}
+
+impl<K, V> FusedIterator for IntoValues<K, V> {}
+
+impl<K, V: fmt::Debug> fmt::Debug for IntoValues<K, V> {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ let iter = self.iter.as_slice().iter().map(Bucket::value_ref);
+ f.debug_list().entries(iter).finish()
+ }
+}
+
+impl<K, V> Default for IntoValues<K, V> {
+ fn default() -> Self {
+ Self {
+ iter: Vec::new().into_iter(),
+ }
+ }
+}
+
+/// A splicing iterator for `IndexMap`.
+///
+/// This `struct` is created by [`IndexMap::splice()`].
+/// See its documentation for more.
+pub struct Splice<'a, I, K, V, S>
+where
+ I: Iterator<Item = (K, V)>,
+ K: Hash + Eq,
+ S: BuildHasher,
+{
+ map: &'a mut IndexMap<K, V, S>,
+ tail: IndexMapCore<K, V>,
+ drain: vec::IntoIter<Bucket<K, V>>,
+ replace_with: I,
+}
+
+impl<'a, I, K, V, S> Splice<'a, I, K, V, S>
+where
+ I: Iterator<Item = (K, V)>,
+ K: Hash + Eq,
+ S: BuildHasher,
+{
+ pub(super) fn new<R>(map: &'a mut IndexMap<K, V, S>, range: R, replace_with: I) -> Self
+ where
+ R: RangeBounds<usize>,
+ {
+ let (tail, drain) = map.core.split_splice(range);
+ Self {
+ map,
+ tail,
+ drain,
+ replace_with,
+ }
+ }
+}
+
+impl<I, K, V, S> Drop for Splice<'_, I, K, V, S>
+where
+ I: Iterator<Item = (K, V)>,
+ K: Hash + Eq,
+ S: BuildHasher,
+{
+ fn drop(&mut self) {
+ // Finish draining unconsumed items. We don't strictly *have* to do this
+ // manually, since we already split it into separate memory, but it will
+ // match the drop order of `vec::Splice` items this way.
+ let _ = self.drain.nth(usize::MAX);
+
+ // Now insert all the new items. If a key matches an existing entry, it
+ // keeps the original position and only replaces the value, like `insert`.
+ while let Some((key, value)) = self.replace_with.next() {
+ // Since the tail is disjoint, we can try to update it first,
+ // or else insert (update or append) the primary map.
+ let hash = self.map.hash(&key);
+ if let Some(i) = self.tail.get_index_of(hash, &key) {
+ self.tail.as_entries_mut()[i].value = value;
+ } else {
+ self.map.core.insert_full(hash, key, value);
+ }
+ }
+
+ // Finally, re-append the tail
+ self.map.core.append_unchecked(&mut self.tail);
+ }
+}
+
+impl<I, K, V, S> Iterator for Splice<'_, I, K, V, S>
+where
+ I: Iterator<Item = (K, V)>,
+ K: Hash + Eq,
+ S: BuildHasher,
+{
+ type Item = (K, V);
+
+ fn next(&mut self) -> Option<Self::Item> {
+ self.drain.next().map(Bucket::key_value)
+ }
+
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ self.drain.size_hint()
+ }
+}
+
+impl<I, K, V, S> DoubleEndedIterator for Splice<'_, I, K, V, S>
+where
+ I: Iterator<Item = (K, V)>,
+ K: Hash + Eq,
+ S: BuildHasher,
+{
+ fn next_back(&mut self) -> Option<Self::Item> {
+ self.drain.next_back().map(Bucket::key_value)
+ }
+}
+
+impl<I, K, V, S> ExactSizeIterator for Splice<'_, I, K, V, S>
+where
+ I: Iterator<Item = (K, V)>,
+ K: Hash + Eq,
+ S: BuildHasher,
+{
+ fn len(&self) -> usize {
+ self.drain.len()
+ }
+}
+
+impl<I, K, V, S> FusedIterator for Splice<'_, I, K, V, S>
+where
+ I: Iterator<Item = (K, V)>,
+ K: Hash + Eq,
+ S: BuildHasher,
+{
+}
+
+impl<'a, I, K, V, S> fmt::Debug for Splice<'a, I, K, V, S>
+where
+ I: fmt::Debug + Iterator<Item = (K, V)>,
+ K: fmt::Debug + Hash + Eq,
+ V: fmt::Debug,
+ S: BuildHasher,
+{
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ // Follow `vec::Splice` in only printing the drain and replacement
+ f.debug_struct("Splice")
+ .field("drain", &self.drain)
+ .field("replace_with", &self.replace_with)
+ .finish()
+ }
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-16 03:15:01 +0000