1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158

use std::borrow::Borrow;
use std::collections::HashMap;
use std::hash::Hash;

/// An interface to the hash map operations used by
/// [`KeyNodeList`](crate::KeyNodeList).
///
/// Any data structure that implements this trait can be used as the
/// underlying hash map for [`KeyNodeList`](crate::KeyNodeList).
pub trait Map<K, V> {
  /// Returns the number of elements in the map.
  ///
  /// This operation should compute in *O*(1) time.
  fn len(&self) -> usize;

  /// Returns `true` if the map contains no elements.
  ///
  /// This operation should compute in *O*(1) time.
  #[inline]
  fn is_empty(&self) -> bool {
    self.len() == 0
  }

  /// Clears the map, removing all key-value pairs.
  /// Keeps the allocated memory for reuse.
  fn clear(&mut self);

  /// Returns `true` if the map contains a value for the specified key.
  ///
  /// The key may be any borrowed form of the map’s key type, but [`Hash`]
  /// and [`Eq`] on the borrowed form must match those for the key type.
  ///
  /// This operation should compute in *O*(1) time on average.
  #[inline]
  fn contains_key<Q: ?Sized>(&self, k: &Q) -> bool
  where
    K: Hash + Eq + Borrow<Q>,
    Q: Hash + Eq,
  {
    self.get(k).is_some()
  }

  /// Returns a reference to the value corresponding to the key.
  ///
  /// The key may be any borrowed form of the map’s key type, but [`Hash`]
  /// and [`Eq`] on the borrowed form must match those for the key type.
  ///
  /// This operation should compute in *O*(1) time on average.
  fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>
  where
    K: Hash + Eq + Borrow<Q>,
    Q: Hash + Eq;

  /// Returns a mutable reference to the value corresponding to the key.
  ///
  /// The key may be any borrowed form of the map’s key type, but [`Hash`]
  /// and [`Eq`] on the borrowed form must match those for the key type.
  ///
  /// This operation should compute in *O*(1) time on average.
  fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V>
  where
    K: Hash + Eq + Borrow<Q>,
    Q: Hash + Eq;

  /// Inserts a key-value pair into the map.
  ///
  /// If the map did have this key present, returns an error containing the
  /// key and the value.
  ///
  /// If the map did not have this key present, the key-value pair is
  /// inserted, and [`Ok(())`](Ok) is returned.
  ///
  /// This operation should compute in *O*(1) time on average.
  fn insert<T: Into<V>>(&mut self, k: K, v: T) -> Result<(), (K, T)>
  where
    K: Hash + Eq;

  /// Removes a key from the map, returning the value at the key if the key
  /// was previously in the map.
  ///
  /// The key may be any borrowed form of the map’s key type, but [`Hash`]
  /// and [`Eq`] on the borrowed form must match those for the key type.
  ///
  /// This operation should compute in *O*(1) time on average.
  #[inline]
  fn remove<Q: ?Sized>(&mut self, k: &Q) -> Option<V>
  where
    K: Hash + Eq + Borrow<Q>,
    Q: Hash + Eq,
  {
    self.remove_entry(k).map(|(_, v)| v)
  }

  /// Removes a key from the map, returning the stored key and value if the
  /// key was previously in the map.
  ///
  /// The key may be any borrowed form of the map’s key type, but [`Hash`]
  /// and [`Eq`] on the borrowed form must match those for the key type.
  ///
  /// This operation should compute in *O*(1) time on average.
  fn remove_entry<Q: ?Sized>(&mut self, k: &Q) -> Option<(K, V)>
  where
    K: Hash + Eq + Borrow<Q>,
    Q: Hash + Eq;
}

impl<K, V> Map<K, V> for HashMap<K, V> {
  #[inline]
  fn len(&self) -> usize {
    self.len()
  }

  #[inline]
  fn clear(&mut self) {
    self.clear()
  }

  #[inline]
  fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>
  where
    K: Hash + Eq + Borrow<Q>,
    Q: Hash + Eq,
  {
    self.get(k)
  }

  #[inline]
  fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V>
  where
    K: Hash + Eq + Borrow<Q>,
    Q: Hash + Eq,
  {
    self.get_mut(k)
  }

  #[inline]
  #[allow(clippy::map_entry)]
  fn insert<T: Into<V>>(&mut self, k: K, v: T) -> Result<(), (K, T)>
  where
    K: Hash + Eq,
  {
    if self.contains_key(&k) {
      Err((k, v))
    } else {
      self.insert(k, v.into());
      Ok(())
    }
  }

  #[inline]
  fn remove_entry<Q: ?Sized>(&mut self, k: &Q) -> Option<(K, V)>
  where
    K: Hash + Eq + Borrow<Q>,
    Q: Hash + Eq,
  {
    self.remove_entry(k)
  }
}