1use super::raw::RawTableEntry;
2use super::IndexMapCore;
3use crate::HashValue;
4use core::{fmt, mem};
5
6impl<K, V> IndexMapCore<K, V> {
7 pub(crate) fn entry(&mut self, hash: HashValue, key: K) -> Entry<'_, K, V>
8 where
9 K: Eq,
10 {
11 match self.raw_entry(hash, |k: &K| *k == key) {
12 Ok(raw: RawTableEntry<'_, K, V>) => Entry::Occupied(OccupiedEntry { raw }),
13 Err(map: &mut IndexMapCore) => Entry::Vacant(VacantEntry { map, hash, key }),
14 }
15 }
16}
17
18/// Entry for an existing key-value pair in an [`IndexMap`][crate::IndexMap]
19/// or a vacant location to insert one.
20pub enum Entry<'a, K, V> {
21 /// Existing slot with equivalent key.
22 Occupied(OccupiedEntry<'a, K, V>),
23 /// Vacant slot (no equivalent key in the map).
24 Vacant(VacantEntry<'a, K, V>),
25}
26
27impl<'a, K, V> Entry<'a, K, V> {
28 /// Return the index where the key-value pair exists or will be inserted.
29 pub fn index(&self) -> usize {
30 match *self {
31 Entry::Occupied(ref entry) => entry.index(),
32 Entry::Vacant(ref entry) => entry.index(),
33 }
34 }
35
36 /// Inserts the given default value in the entry if it is vacant and returns a mutable
37 /// reference to it. Otherwise a mutable reference to an already existent value is returned.
38 ///
39 /// Computes in **O(1)** time (amortized average).
40 pub fn or_insert(self, default: V) -> &'a mut V {
41 match self {
42 Entry::Occupied(entry) => entry.into_mut(),
43 Entry::Vacant(entry) => entry.insert(default),
44 }
45 }
46
47 /// Inserts the result of the `call` function in the entry if it is vacant and returns a mutable
48 /// reference to it. Otherwise a mutable reference to an already existent value is returned.
49 ///
50 /// Computes in **O(1)** time (amortized average).
51 pub fn or_insert_with<F>(self, call: F) -> &'a mut V
52 where
53 F: FnOnce() -> V,
54 {
55 match self {
56 Entry::Occupied(entry) => entry.into_mut(),
57 Entry::Vacant(entry) => entry.insert(call()),
58 }
59 }
60
61 /// Inserts the result of the `call` function with a reference to the entry's key if it is
62 /// vacant, and returns a mutable reference to the new value. Otherwise a mutable reference to
63 /// an already existent value is returned.
64 ///
65 /// Computes in **O(1)** time (amortized average).
66 pub fn or_insert_with_key<F>(self, call: F) -> &'a mut V
67 where
68 F: FnOnce(&K) -> V,
69 {
70 match self {
71 Entry::Occupied(entry) => entry.into_mut(),
72 Entry::Vacant(entry) => {
73 let value = call(&entry.key);
74 entry.insert(value)
75 }
76 }
77 }
78
79 /// Gets a reference to the entry's key, either within the map if occupied,
80 /// or else the new key that was used to find the entry.
81 pub fn key(&self) -> &K {
82 match *self {
83 Entry::Occupied(ref entry) => entry.key(),
84 Entry::Vacant(ref entry) => entry.key(),
85 }
86 }
87
88 /// Modifies the entry if it is occupied.
89 pub fn and_modify<F>(mut self, f: F) -> Self
90 where
91 F: FnOnce(&mut V),
92 {
93 if let Entry::Occupied(entry) = &mut self {
94 f(entry.get_mut());
95 }
96 self
97 }
98
99 /// Inserts a default-constructed value in the entry if it is vacant and returns a mutable
100 /// reference to it. Otherwise a mutable reference to an already existent value is returned.
101 ///
102 /// Computes in **O(1)** time (amortized average).
103 pub fn or_default(self) -> &'a mut V
104 where
105 V: Default,
106 {
107 match self {
108 Entry::Occupied(entry) => entry.into_mut(),
109 Entry::Vacant(entry) => entry.insert(V::default()),
110 }
111 }
112}
113
114impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for Entry<'_, K, V> {
115 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
116 let mut tuple: DebugTuple<'_, '_> = f.debug_tuple(name:"Entry");
117 match self {
118 Entry::Vacant(v: &VacantEntry<'_, K, V>) => tuple.field(v),
119 Entry::Occupied(o: &OccupiedEntry<'_, K, V>) => tuple.field(o),
120 };
121 tuple.finish()
122 }
123}
124
125/// A view into an occupied entry in an [`IndexMap`][crate::IndexMap].
126/// It is part of the [`Entry`] enum.
127pub struct OccupiedEntry<'a, K, V> {
128 raw: RawTableEntry<'a, K, V>,
129}
130
131impl<'a, K, V> OccupiedEntry<'a, K, V> {
132 /// Return the index of the key-value pair
133 #[inline]
134 pub fn index(&self) -> usize {
135 self.raw.index()
136 }
137
138 /// Gets a reference to the entry's key in the map.
139 ///
140 /// Note that this is not the key that was used to find the entry. There may be an observable
141 /// difference if the key type has any distinguishing features outside of `Hash` and `Eq`, like
142 /// extra fields or the memory address of an allocation.
143 pub fn key(&self) -> &K {
144 &self.raw.bucket().key
145 }
146
147 /// Gets a reference to the entry's value in the map.
148 pub fn get(&self) -> &V {
149 &self.raw.bucket().value
150 }
151
152 /// Gets a mutable reference to the entry's value in the map.
153 ///
154 /// If you need a reference which may outlive the destruction of the
155 /// [`Entry`] value, see [`into_mut`][Self::into_mut].
156 pub fn get_mut(&mut self) -> &mut V {
157 &mut self.raw.bucket_mut().value
158 }
159
160 /// Converts into a mutable reference to the entry's value in the map,
161 /// with a lifetime bound to the map itself.
162 pub fn into_mut(self) -> &'a mut V {
163 &mut self.raw.into_bucket().value
164 }
165
166 /// Sets the value of the entry to `value`, and returns the entry's old value.
167 pub fn insert(&mut self, value: V) -> V {
168 mem::replace(self.get_mut(), value)
169 }
170
171 /// Remove the key, value pair stored in the map for this entry, and return the value.
172 ///
173 /// **NOTE:** This is equivalent to [`.swap_remove()`][Self::swap_remove], replacing this
174 /// entry's position with the last element, and it is deprecated in favor of calling that
175 /// explicitly. If you need to preserve the relative order of the keys in the map, use
176 /// [`.shift_remove()`][Self::shift_remove] instead.
177 #[deprecated(note = "`remove` disrupts the map order -- \
178 use `swap_remove` or `shift_remove` for explicit behavior.")]
179 pub fn remove(self) -> V {
180 self.swap_remove()
181 }
182
183 /// Remove the key, value pair stored in the map for this entry, and return the value.
184 ///
185 /// Like [`Vec::swap_remove`][crate::Vec::swap_remove], the pair is removed by swapping it with
186 /// the last element of the map and popping it off.
187 /// **This perturbs the position of what used to be the last element!**
188 ///
189 /// Computes in **O(1)** time (average).
190 pub fn swap_remove(self) -> V {
191 self.swap_remove_entry().1
192 }
193
194 /// Remove the key, value pair stored in the map for this entry, and return the value.
195 ///
196 /// Like [`Vec::remove`][crate::Vec::remove], the pair is removed by shifting all of the
197 /// elements that follow it, preserving their relative order.
198 /// **This perturbs the index of all of those elements!**
199 ///
200 /// Computes in **O(n)** time (average).
201 pub fn shift_remove(self) -> V {
202 self.shift_remove_entry().1
203 }
204
205 /// Remove and return the key, value pair stored in the map for this entry
206 ///
207 /// **NOTE:** This is equivalent to [`.swap_remove_entry()`][Self::swap_remove_entry],
208 /// replacing this entry's position with the last element, and it is deprecated in favor of
209 /// calling that explicitly. If you need to preserve the relative order of the keys in the map,
210 /// use [`.shift_remove_entry()`][Self::shift_remove_entry] instead.
211 #[deprecated(note = "`remove_entry` disrupts the map order -- \
212 use `swap_remove_entry` or `shift_remove_entry` for explicit behavior.")]
213 pub fn remove_entry(self) -> (K, V) {
214 self.swap_remove_entry()
215 }
216
217 /// Remove and return the key, value pair stored in the map for this entry
218 ///
219 /// Like [`Vec::swap_remove`][crate::Vec::swap_remove], the pair is removed by swapping it with
220 /// the last element of the map and popping it off.
221 /// **This perturbs the position of what used to be the last element!**
222 ///
223 /// Computes in **O(1)** time (average).
224 pub fn swap_remove_entry(self) -> (K, V) {
225 let (map, index) = self.raw.remove_index();
226 map.swap_remove_finish(index)
227 }
228
229 /// Remove and return the key, value pair stored in the map for this entry
230 ///
231 /// Like [`Vec::remove`][crate::Vec::remove], the pair is removed by shifting all of the
232 /// elements that follow it, preserving their relative order.
233 /// **This perturbs the index of all of those elements!**
234 ///
235 /// Computes in **O(n)** time (average).
236 pub fn shift_remove_entry(self) -> (K, V) {
237 let (map, index) = self.raw.remove_index();
238 map.shift_remove_finish(index)
239 }
240
241 /// Moves the position of the entry to a new index
242 /// by shifting all other entries in-between.
243 ///
244 /// This is equivalent to [`IndexMap::move_index`][`crate::IndexMap::move_index`]
245 /// coming `from` the current [`.index()`][Self::index].
246 ///
247 /// * If `self.index() < to`, the other pairs will shift down while the targeted pair moves up.
248 /// * If `self.index() > to`, the other pairs will shift up while the targeted pair moves down.
249 ///
250 /// ***Panics*** if `to` is out of bounds.
251 ///
252 /// Computes in **O(n)** time (average).
253 pub fn move_index(self, to: usize) {
254 let (map, index) = self.raw.into_inner();
255 map.move_index(index, to);
256 }
257
258 /// Swaps the position of entry with another.
259 ///
260 /// This is equivalent to [`IndexMap::swap_indices`][`crate::IndexMap::swap_indices`]
261 /// with the current [`.index()`][Self::index] as one of the two being swapped.
262 ///
263 /// ***Panics*** if the `other` index is out of bounds.
264 ///
265 /// Computes in **O(1)** time (average).
266 pub fn swap_indices(self, other: usize) {
267 let (map, index) = self.raw.into_inner();
268 map.swap_indices(index, other)
269 }
270}
271
272impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for OccupiedEntry<'_, K, V> {
273 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
274 f&mut DebugStruct<'_, '_>.debug_struct("OccupiedEntry")
275 .field("key", self.key())
276 .field(name:"value", self.get())
277 .finish()
278 }
279}
280
281/// A view into a vacant entry in an [`IndexMap`][crate::IndexMap].
282/// It is part of the [`Entry`] enum.
283pub struct VacantEntry<'a, K, V> {
284 map: &'a mut IndexMapCore<K, V>,
285 hash: HashValue,
286 key: K,
287}
288
289impl<'a, K, V> VacantEntry<'a, K, V> {
290 /// Return the index where a key-value pair may be inserted.
291 pub fn index(&self) -> usize {
292 self.map.indices.len()
293 }
294
295 /// Gets a reference to the key that was used to find the entry.
296 pub fn key(&self) -> &K {
297 &self.key
298 }
299
300 /// Takes ownership of the key, leaving the entry vacant.
301 pub fn into_key(self) -> K {
302 self.key
303 }
304
305 /// Inserts the entry's key and the given value into the map, and returns a mutable reference
306 /// to the value.
307 pub fn insert(self, value: V) -> &'a mut V {
308 let Self { map, hash, key } = self;
309 let i = map.insert_unique(hash, key, value);
310 &mut map.entries[i].value
311 }
312
313 /// Inserts the entry's key and the given value into the map at its ordered
314 /// position among sorted keys, and returns the new index and a mutable
315 /// reference to the value.
316 ///
317 /// If the existing keys are **not** already sorted, then the insertion
318 /// index is unspecified (like [`slice::binary_search`]), but the key-value
319 /// pair is inserted at that position regardless.
320 ///
321 /// Computes in **O(n)** time (average).
322 pub fn insert_sorted(self, value: V) -> (usize, &'a mut V)
323 where
324 K: Ord,
325 {
326 let slice = crate::map::Slice::from_slice(&self.map.entries);
327 let i = slice.binary_search_keys(&self.key).unwrap_err();
328 (i, self.shift_insert(i, value))
329 }
330
331 /// Inserts the entry's key and the given value into the map at the given index,
332 /// shifting others to the right, and returns a mutable reference to the value.
333 ///
334 /// ***Panics*** if `index` is out of bounds.
335 ///
336 /// Computes in **O(n)** time (average).
337 pub fn shift_insert(self, index: usize, value: V) -> &'a mut V {
338 let Self { map, hash, key } = self;
339 map.shift_insert_unique(index, hash, key, value);
340 &mut map.entries[index].value
341 }
342}
343
344impl<K: fmt::Debug, V> fmt::Debug for VacantEntry<'_, K, V> {
345 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
346 f.debug_tuple(name:"VacantEntry").field(self.key()).finish()
347 }
348}
349
350/// A view into an occupied entry in an [`IndexMap`][crate::IndexMap] obtained by index.
351///
352/// This `struct` is created from the [`get_index_entry`][crate::IndexMap::get_index_entry] method.
353pub struct IndexedEntry<'a, K, V> {
354 map: &'a mut IndexMapCore<K, V>,
355 // We have a mutable reference to the map, which keeps the index
356 // valid and pointing to the correct entry.
357 index: usize,
358}
359
360impl<'a, K, V> IndexedEntry<'a, K, V> {
361 pub(crate) fn new(map: &'a mut IndexMapCore<K, V>, index: usize) -> Self {
362 Self { map, index }
363 }
364
365 /// Return the index of the key-value pair
366 #[inline]
367 pub fn index(&self) -> usize {
368 self.index
369 }
370
371 /// Gets a reference to the entry's key in the map.
372 pub fn key(&self) -> &K {
373 &self.map.entries[self.index].key
374 }
375
376 /// Gets a reference to the entry's value in the map.
377 pub fn get(&self) -> &V {
378 &self.map.entries[self.index].value
379 }
380
381 /// Gets a mutable reference to the entry's value in the map.
382 ///
383 /// If you need a reference which may outlive the destruction of the
384 /// `IndexedEntry` value, see [`into_mut`][Self::into_mut].
385 pub fn get_mut(&mut self) -> &mut V {
386 &mut self.map.entries[self.index].value
387 }
388
389 /// Sets the value of the entry to `value`, and returns the entry's old value.
390 pub fn insert(&mut self, value: V) -> V {
391 mem::replace(self.get_mut(), value)
392 }
393
394 /// Converts into a mutable reference to the entry's value in the map,
395 /// with a lifetime bound to the map itself.
396 pub fn into_mut(self) -> &'a mut V {
397 &mut self.map.entries[self.index].value
398 }
399
400 /// Remove and return the key, value pair stored in the map for this entry
401 ///
402 /// Like [`Vec::swap_remove`][crate::Vec::swap_remove], the pair is removed by swapping it with
403 /// the last element of the map and popping it off.
404 /// **This perturbs the position of what used to be the last element!**
405 ///
406 /// Computes in **O(1)** time (average).
407 pub fn swap_remove_entry(self) -> (K, V) {
408 self.map.swap_remove_index(self.index).unwrap()
409 }
410
411 /// Remove and return the key, value pair stored in the map for this entry
412 ///
413 /// Like [`Vec::remove`][crate::Vec::remove], the pair is removed by shifting all of the
414 /// elements that follow it, preserving their relative order.
415 /// **This perturbs the index of all of those elements!**
416 ///
417 /// Computes in **O(n)** time (average).
418 pub fn shift_remove_entry(self) -> (K, V) {
419 self.map.shift_remove_index(self.index).unwrap()
420 }
421
422 /// Remove the key, value pair stored in the map for this entry, and return the value.
423 ///
424 /// Like [`Vec::swap_remove`][crate::Vec::swap_remove], the pair is removed by swapping it with
425 /// the last element of the map and popping it off.
426 /// **This perturbs the position of what used to be the last element!**
427 ///
428 /// Computes in **O(1)** time (average).
429 pub fn swap_remove(self) -> V {
430 self.swap_remove_entry().1
431 }
432
433 /// Remove the key, value pair stored in the map for this entry, and return the value.
434 ///
435 /// Like [`Vec::remove`][crate::Vec::remove], the pair is removed by shifting all of the
436 /// elements that follow it, preserving their relative order.
437 /// **This perturbs the index of all of those elements!**
438 ///
439 /// Computes in **O(n)** time (average).
440 pub fn shift_remove(self) -> V {
441 self.shift_remove_entry().1
442 }
443
444 /// Moves the position of the entry to a new index
445 /// by shifting all other entries in-between.
446 ///
447 /// This is equivalent to [`IndexMap::move_index`][`crate::IndexMap::move_index`]
448 /// coming `from` the current [`.index()`][Self::index].
449 ///
450 /// * If `self.index() < to`, the other pairs will shift down while the targeted pair moves up.
451 /// * If `self.index() > to`, the other pairs will shift up while the targeted pair moves down.
452 ///
453 /// ***Panics*** if `to` is out of bounds.
454 ///
455 /// Computes in **O(n)** time (average).
456 pub fn move_index(self, to: usize) {
457 self.map.move_index(self.index, to);
458 }
459
460 /// Swaps the position of entry with another.
461 ///
462 /// This is equivalent to [`IndexMap::swap_indices`][`crate::IndexMap::swap_indices`]
463 /// with the current [`.index()`][Self::index] as one of the two being swapped.
464 ///
465 /// ***Panics*** if the `other` index is out of bounds.
466 ///
467 /// Computes in **O(1)** time (average).
468 pub fn swap_indices(self, other: usize) {
469 self.map.swap_indices(self.index, other)
470 }
471}
472
473impl<K: fmt::Debug, V: fmt::Debug> fmt::Debug for IndexedEntry<'_, K, V> {
474 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
475 f&mut DebugStruct<'_, '_>.debug_struct("IndexedEntry")
476 .field("index", &self.index)
477 .field("key", self.key())
478 .field(name:"value", self.get())
479 .finish()
480 }
481}
482