3 use std
::borrow
::Borrow
;
5 /// Flat (Vec) backed map
7 /// This preserves insertion order
8 #[derive(Clone, Debug, PartialEq, Eq)]
9 pub(crate) struct FlatMap
<K
, V
> {
14 impl<K
: PartialEq
+ Eq
, V
> FlatMap
<K
, V
> {
15 pub(crate) fn new() -> Self {
19 pub(crate) fn insert(&mut self, key
: K
, mut value
: V
) -> Option
<V
> {
20 for (index
, existing
) in self.keys
.iter().enumerate() {
22 std
::mem
::swap(&mut self.values
[index
], &mut value
);
27 self.insert_unchecked(key
, value
);
31 pub(crate) fn insert_unchecked(&mut self, key
: K
, value
: V
) {
33 self.values
.push(value
);
36 pub(crate) fn extend_unchecked(&mut self, iter
: impl IntoIterator
<Item
= (K
, V
)>) {
37 for (key
, value
) in iter
{
38 self.insert_unchecked(key
, value
);
42 pub fn contains_key
<Q
: ?Sized
>(&self, key
: &Q
) -> bool
47 for existing
in &self.keys
{
48 if existing
.borrow() == key
{
55 pub fn remove
<Q
: ?Sized
>(&mut self, key
: &Q
) -> Option
<V
>
58 Q
: std
::hash
::Hash
+ Eq
,
60 self.remove_entry(key
).map(|(_
, v
)| v
)
63 pub fn remove_entry
<Q
: ?Sized
>(&mut self, key
: &Q
) -> Option
<(K
, V
)>
66 Q
: std
::hash
::Hash
+ Eq
,
68 let index
= some
!(self
72 .find_map(|(i
, k
)| (k
.borrow() == key
).then_some(i
)));
73 let key
= self.keys
.remove(index
);
74 let value
= self.values
.remove(index
);
78 pub(crate) fn is_empty(&self) -> bool
{
82 pub fn entry(&mut self, key
: K
) -> Entry
<K
, V
> {
83 for (index
, existing
) in self.keys
.iter().enumerate() {
85 return Entry
::Occupied(OccupiedEntry { v: self, index }
);
88 Entry
::Vacant(VacantEntry { v: self, key }
)
91 pub fn get
<Q
: ?Sized
>(&self, k
: &Q
) -> Option
<&V
>
96 for (index
, existing
) in self.keys
.iter().enumerate() {
97 if existing
.borrow() == k
{
98 return Some(&self.values
[index
]);
104 pub fn get_mut
<Q
: ?Sized
>(&mut self, k
: &Q
) -> Option
<&mut V
>
109 for (index
, existing
) in self.keys
.iter().enumerate() {
110 if existing
.borrow() == k
{
111 return Some(&mut self.values
[index
]);
117 pub fn keys(&self) -> std
::slice
::Iter
<'_
, K
> {
121 pub fn iter(&self) -> Iter
<K
, V
> {
123 keys
: self.keys
.iter(),
124 values
: self.values
.iter(),
128 pub fn iter_mut(&mut self) -> IterMut
<K
, V
> {
130 keys
: self.keys
.iter_mut(),
131 values
: self.values
.iter_mut(),
136 impl<K
: PartialEq
+ Eq
, V
> Default
for FlatMap
<K
, V
> {
137 fn default() -> Self {
139 keys
: Default
::default(),
140 values
: Default
::default(),
145 pub enum Entry
<'a
, K
: 'a
, V
: 'a
> {
146 Vacant(VacantEntry
<'a
, K
, V
>),
147 Occupied(OccupiedEntry
<'a
, K
, V
>),
150 impl<'a
, K
: 'a
, V
: 'a
> Entry
<'a
, K
, V
> {
151 pub fn or_insert(self, default: V
) -> &'a
mut V
{
153 Entry
::Occupied(entry
) => &mut entry
.v
.values
[entry
.index
],
154 Entry
::Vacant(entry
) => {
155 entry
.v
.keys
.push(entry
.key
);
156 entry
.v
.values
.push(default);
157 entry
.v
.values
.last_mut().unwrap()
162 pub fn or_insert_with
<F
: FnOnce() -> V
>(self, default: F
) -> &'a
mut V
{
164 Entry
::Occupied(entry
) => &mut entry
.v
.values
[entry
.index
],
165 Entry
::Vacant(entry
) => {
166 entry
.v
.keys
.push(entry
.key
);
167 entry
.v
.values
.push(default());
168 entry
.v
.values
.last_mut().unwrap()
174 pub struct VacantEntry
<'a
, K
: 'a
, V
: 'a
> {
175 v
: &'a
mut FlatMap
<K
, V
>,
179 pub struct OccupiedEntry
<'a
, K
: 'a
, V
: 'a
> {
180 v
: &'a
mut FlatMap
<K
, V
>,
184 pub struct Iter
<'a
, K
: 'a
, V
: 'a
> {
185 keys
: std
::slice
::Iter
<'a
, K
>,
186 values
: std
::slice
::Iter
<'a
, V
>,
189 impl<'a
, K
, V
> Iterator
for Iter
<'a
, K
, V
> {
190 type Item
= (&'a K
, &'a V
);
192 fn next(&mut self) -> Option
<(&'a K
, &'a V
)> {
193 match self.keys
.next() {
195 let v
= self.values
.next().unwrap();
201 fn size_hint(&self) -> (usize, Option
<usize>) {
202 self.keys
.size_hint()
206 impl<'a
, K
, V
> DoubleEndedIterator
for Iter
<'a
, K
, V
> {
207 fn next_back(&mut self) -> Option
<(&'a K
, &'a V
)> {
208 match self.keys
.next_back() {
210 let v
= self.values
.next_back().unwrap();
218 impl<'a
, K
, V
> ExactSizeIterator
for Iter
<'a
, K
, V
> {}
220 pub struct IterMut
<'a
, K
: 'a
, V
: 'a
> {
221 keys
: std
::slice
::IterMut
<'a
, K
>,
222 values
: std
::slice
::IterMut
<'a
, V
>,
225 impl<'a
, K
, V
> Iterator
for IterMut
<'a
, K
, V
> {
226 type Item
= (&'a K
, &'a
mut V
);
228 fn next(&mut self) -> Option
<(&'a K
, &'a
mut V
)> {
229 match self.keys
.next() {
231 let v
= self.values
.next().unwrap();
237 fn size_hint(&self) -> (usize, Option
<usize>) {
238 self.keys
.size_hint()
242 impl<'a
, K
, V
> DoubleEndedIterator
for IterMut
<'a
, K
, V
> {
243 fn next_back(&mut self) -> Option
<(&'a K
, &'a
mut V
)> {
244 match self.keys
.next_back() {
246 let v
= self.values
.next_back().unwrap();
254 impl<'a
, K
, V
> ExactSizeIterator
for IterMut
<'a
, K
, V
> {}