tether_map/linked_hash_map/
cursor.rs

1use core::hash::BuildHasher;
2use core::hash::Hash;
3
4use crate::Ptr;
5use crate::arena::ActiveSlotRef;
6use crate::linked_hash_map::Entry;
7use crate::linked_hash_map::Iter;
8use crate::linked_hash_map::LinkedHashMap;
9use crate::linked_hash_map::RemovedEntry;
10
11#[derive(Debug)]
12/// A cursor for navigating and modifying a linked hash map.
13///
14/// A `CursorMut` is like an iterator, except that it can freely seek
15/// back-and-forth and can safely mutate the map during iteration. This is
16/// because the lifetime is tied to the map, not the cursor itself.
17///
18/// Cursors always point to an element in the map. The `CursorMut` is positioned
19/// at a specific entry and allows for insertion and removal operations relative
20/// to that position.
21///
22/// # Examples
23///
24/// ```
25/// use tether_map::LinkedHashMap;
26///
27/// let mut map = LinkedHashMap::new();
28/// map.insert("a", 1);
29/// map.insert("b", 2);
30/// map.insert("c", 3);
31///
32/// let mut cursor = map.head_cursor_mut();
33/// if let Some((key, value)) = cursor.current_mut() {
34///     *value *= 10;
35/// }
36/// assert_eq!(map.get(&"a"), Some(&10));
37/// ```
38pub struct CursorMut<'m, K, T, S> {
39    pub(crate) ptr: Option<ActiveSlotRef<K, T>>,
40    pub(crate) map: &'m mut LinkedHashMap<K, T, S>,
41}
42
43impl<'m, K: Hash + Eq, T, S: BuildHasher> CursorMut<'m, K, T, S> {
44    /// Inserts a key-value pair after the cursor's current position and
45    /// moves the cursor to the inserted or updated entry.
46    #[inline]
47    pub fn insert_after_move_to(&mut self, key: K, value: T) -> Option<T> {
48        let ptr = if self.ptr.is_none() {
49            self.map.head_tail.as_ref().map(|ht| ht.tail)
50        } else {
51            self.ptr
52        };
53
54        match self.map.entry(key) {
55            Entry::Occupied(occupied_entry) => {
56                let mut map_ptr = *occupied_entry.entry.get();
57                if Some(map_ptr) != ptr {
58                    self.map.move_after_internal(map_ptr, ptr.unwrap());
59                }
60                self.ptr = Some(map_ptr);
61                Some(core::mem::replace(
62                    &mut map_ptr.data_mut(&mut self.map.nodes).value,
63                    value,
64                ))
65            }
66            Entry::Vacant(vacant_entry) => {
67                self.ptr = Some(vacant_entry.insert_after_internal(value, ptr).0);
68                None
69            }
70        }
71    }
72
73    /// Inserts a key-value pair before the cursor's current position and
74    /// moves the cursor to the inserted or updated entry.
75    #[inline]
76    pub fn insert_before_move_to(&mut self, key: K, value: T) -> Option<T> {
77        let ptr = if self.ptr.is_none() {
78            self.map.head_tail.as_ref().map(|ht| ht.head)
79        } else {
80            self.ptr
81        };
82
83        match self.map.entry(key) {
84            Entry::Occupied(occupied_entry) => {
85                let mut map_ptr = *occupied_entry.entry.get();
86                if Some(map_ptr) != ptr {
87                    self.map.move_before_internal(map_ptr, ptr.unwrap());
88                }
89                self.ptr = Some(map_ptr);
90                Some(core::mem::replace(
91                    &mut map_ptr.data_mut(&mut self.map.nodes).value,
92                    value,
93                ))
94            }
95            Entry::Vacant(vacant_entry) => {
96                self.ptr = Some(vacant_entry.insert_before_internal(value, ptr).0);
97                None
98            }
99        }
100    }
101
102    /// Returns the pointer to the entry with the given key.
103    ///
104    /// This is a convenience method that delegates to the underlying map's
105    /// `get_ptr` method.
106    ///
107    /// # Arguments
108    ///
109    /// * `key` - The key to search for
110    ///
111    /// # Returns
112    ///
113    /// * `Some(ptr)` if the key exists in the map
114    /// * `None` if the key is not found
115    #[inline]
116    pub fn get_ptr(&self, key: &K) -> Option<Ptr> {
117        self.map.get_ptr(key)
118    }
119}
120
121impl<'m, K: Hash + Eq, T, S: BuildHasher> CursorMut<'m, K, T, S> {
122    /// Removes the entry before the cursor's current position and returns it.
123    #[inline]
124    pub fn remove_prev(&mut self) -> Option<(Ptr, RemovedEntry<K, T>)> {
125        let prev = self.ptr.map(|slot| slot.prev(&self.map.nodes))?;
126        if Some(prev) == self.ptr {
127            // Only one element in the list, so removing prev would make the
128            // cursor invalid. We choose to keep the cursor at the same position
129            // (which will be None after removal).
130            self.ptr = None;
131        }
132        Some(self.map.remove_ptr_internal(prev))
133    }
134
135    /// Removes the entry after the cursor's current position and returns it.
136    #[inline]
137    pub fn remove_next(&mut self) -> Option<(Ptr, RemovedEntry<K, T>)> {
138        let next = self.ptr.map(|slot| slot.next(&self.map.nodes))?;
139        if Some(next) == self.ptr {
140            self.ptr = None;
141        }
142        Some(self.map.remove_ptr_internal(next))
143    }
144
145    /// Removes the entry at the cursor's current position and returns it.
146    #[inline]
147    pub fn remove(self) -> Option<(Ptr, RemovedEntry<K, T>)> {
148        let ptr = self.ptr?;
149        Some(self.map.remove_ptr_internal(ptr))
150    }
151}
152
153impl<'m, K, T, S> CursorMut<'m, K, T, S> {
154    /// Returns an iterator starting from the cursor's current position.
155    #[inline]
156    pub fn iter(&self) -> Iter<'_, K, T> {
157        Iter {
158            forward_ptr: self.ptr,
159            reverse_ptr: self.ptr.map(|slot| slot.prev(&self.map.nodes)),
160            nodes: &self.map.nodes,
161        }
162    }
163
164    /// Moves the cursor to the next entry in the linked list. The internal
165    /// linked list is **circular**, so moving next from the tail wraps around
166    /// to the head.
167    #[inline]
168    pub fn move_next(&mut self) {
169        self.ptr = self.ptr.map(|slot| slot.next(&self.map.nodes));
170    }
171
172    /// Moves the cursor to the previous entry in the linked list. The internal
173    /// linked list is **circular**, so moving previous from the head wraps
174    /// around to the tail.
175    #[inline]
176    pub fn move_prev(&mut self) {
177        self.ptr = self.ptr.map(|slot| slot.prev(&self.map.nodes));
178    }
179
180    /// Gets the current pointer of the cursor.
181    #[inline]
182    pub fn ptr(&self) -> Option<Ptr> {
183        self.ptr.map(|slot| slot.this(&self.map.nodes))
184    }
185
186    /// Checks if the cursor is currently at the tail of the linked list.
187    #[inline]
188    pub fn at_tail(&self) -> bool {
189        self.ptr == self.map.head_tail.as_ref().map(|ht| ht.tail)
190    }
191
192    /// Checks if the cursor is currently at the head of the linked list.
193    #[inline]
194    pub fn at_head(&self) -> bool {
195        self.ptr == self.map.head_tail.as_ref().map(|ht| ht.head)
196    }
197
198    /// Returns the entry at the cursor's current position.
199    #[inline]
200    pub fn current(&self) -> Option<(&K, &T)> {
201        let ptr = self.ptr?;
202        let data = ptr.data(&self.map.nodes);
203        Some((&data.key, &data.value))
204    }
205
206    /// Returns a mutable reference to the key-value pair at the cursor's
207    /// current position.
208    ///
209    /// The key reference is immutable while the value reference is mutable,
210    /// allowing modification of the value while preserving the key's
211    /// integrity.
212    ///
213    /// # Returns
214    ///
215    /// * `Some((&K, &mut T))` if the cursor is positioned at a valid entry
216    /// * `None` if the cursor is positioned at a null entry
217    ///
218    /// # Examples
219    ///
220    /// ```
221    /// use tether_map::LinkedHashMap;
222    ///
223    /// let mut map = LinkedHashMap::new();
224    /// map.insert("key", 42);
225    ///
226    /// let mut cursor = map.head_cursor_mut();
227    /// if let Some((key, value)) = cursor.current_mut() {
228    ///     assert_eq!(key, &"key");
229    ///     *value = 100;
230    /// }
231    /// assert_eq!(map.get(&"key"), Some(&100));
232    /// ```
233    #[inline]
234    pub fn current_mut(&mut self) -> Option<(&K, &mut T)> {
235        let mut ptr = self.ptr?;
236        let data = ptr.data_mut(&mut self.map.nodes);
237        Some((&data.key, &mut data.value))
238    }
239
240    /// Returns the pointer to the next entry in the linked list from the
241    /// cursor's position.
242    ///
243    /// # Returns
244    ///
245    /// * `Some(next_ptr)` if there is a next entry
246    /// * `None` if the cursor is positioned at a null entry
247    ///
248    /// # Examples
249    ///
250    /// ```
251    /// use tether_map::LinkedHashMap;
252    ///
253    /// let mut map = LinkedHashMap::new();
254    /// map.insert_tail("a", 1);
255    /// map.insert_tail("b", 2);
256    ///
257    /// let cursor = map.head_cursor_mut();
258    /// if let Some(next_ptr) = cursor.next_ptr() {
259    ///     assert_eq!(map.ptr_get(next_ptr), Some(&2));
260    /// }
261    /// ```
262    #[inline]
263    pub fn next_ptr(&self) -> Option<Ptr> {
264        self.ptr
265            .map(|slot| slot.next(&self.map.nodes).this(&self.map.nodes))
266    }
267
268    /// Returns a reference to the key-value pair of the next entry in the
269    /// linked list.
270    ///
271    /// This is a convenience method that combines `next_ptr()` and accessing
272    /// the entry.
273    ///
274    /// # Returns
275    ///
276    /// * `Some((&K, &T))` if there is a next entry
277    /// * `None` if the cursor is positioned at a null entry
278    ///
279    /// # Examples
280    ///
281    /// ```
282    /// use tether_map::LinkedHashMap;
283    ///
284    /// let mut map = LinkedHashMap::new();
285    /// map.insert_tail("a", 1);
286    /// map.insert_tail("b", 2);
287    ///
288    /// let cursor = map.head_cursor_mut();
289    /// if let Some((key, value)) = cursor.next() {
290    ///     assert_eq!(key, &"b");
291    ///     assert_eq!(value, &2);
292    /// }
293    /// ```
294    #[inline]
295    pub fn next(&self) -> Option<(&K, &T)> {
296        let ptr = self.next_ptr()?;
297        self.map.ptr_get_entry(ptr)
298    }
299
300    /// Returns a mutable reference to the key-value pair of the next entry in
301    /// the linked list.
302    ///
303    /// This is a convenience method that combines `next_ptr()` and accessing
304    /// the entry mutably. The key reference is immutable while the value
305    /// reference is mutable.
306    ///
307    /// # Returns
308    ///
309    /// * `Some((&K, &mut T))` if there is a next entry
310    /// * `None` if the cursor is positioned at a null entry
311    ///
312    /// # Examples
313    ///
314    /// ```
315    /// use tether_map::LinkedHashMap;
316    ///
317    /// let mut map = LinkedHashMap::new();
318    /// map.insert_tail("a", 1);
319    /// map.insert_tail("b", 2);
320    ///
321    /// let mut cursor = map.head_cursor_mut();
322    /// if let Some((key, value)) = cursor.next_mut() {
323    ///     assert_eq!(key, &"b");
324    ///     *value = 20;
325    /// }
326    /// assert_eq!(map.get(&"b"), Some(&20));
327    /// ```
328    #[inline]
329    pub fn next_mut(&mut self) -> Option<(&K, &mut T)> {
330        let ptr = self.next_ptr()?;
331        self.map.ptr_get_entry_mut(ptr)
332    }
333
334    /// Returns the pointer to the previous entry in the linked list from the
335    /// cursor's position.
336    ///
337    /// # Returns
338    ///
339    /// * `Some(prev_ptr)` if there is a previous entry
340    /// * `None` if the cursor positioned at a null entry
341    ///
342    /// # Examples
343    ///
344    /// ```
345    /// use tether_map::LinkedHashMap;
346    ///
347    /// let mut map = LinkedHashMap::new();
348    /// map.insert_tail("a", 1);
349    /// map.insert_tail("b", 2);
350    ///
351    /// let cursor = map.tail_cursor_mut();
352    /// if let Some(prev_ptr) = cursor.prev_ptr() {
353    ///     assert_eq!(map.ptr_get(prev_ptr), Some(&1));
354    /// }
355    /// ```
356    #[inline]
357    pub fn prev_ptr(&self) -> Option<Ptr> {
358        self.ptr
359            .map(|slot| slot.prev(&self.map.nodes).this(&self.map.nodes))
360    }
361
362    /// Returns a reference to the key-value pair of the previous entry in the
363    /// linked list.
364    ///
365    /// This is a convenience method that combines `prev_ptr()` and accessing
366    /// the entry.
367    ///
368    /// # Returns
369    ///
370    /// * `Some((&K, &T))` if there is a previous entry
371    /// * `None` if the cursor is positioned at a null entry
372    ///
373    /// # Examples
374    ///
375    /// ```
376    /// use tether_map::LinkedHashMap;
377    ///
378    /// let mut map = LinkedHashMap::new();
379    /// map.insert_tail("a", 1);
380    /// map.insert_tail("b", 2);
381    ///
382    /// let cursor = map.tail_cursor_mut();
383    /// if let Some((key, value)) = cursor.prev() {
384    ///     assert_eq!(key, &"a");
385    ///     assert_eq!(value, &1);
386    /// }
387    /// ```
388    #[inline]
389    pub fn prev(&self) -> Option<(&K, &T)> {
390        let ptr = self.prev_ptr()?;
391        self.map.ptr_get_entry(ptr)
392    }
393
394    /// Returns a mutable reference to the key-value pair of the previous entry
395    /// in the linked list.
396    ///
397    /// This is a convenience method that combines `prev_ptr()` and accessing
398    /// the entry mutably. The key reference is immutable while the value
399    /// reference is mutable.
400    ///
401    /// # Returns
402    ///
403    /// * `Some((&K, &mut T))` if there is a previous entry
404    /// * `None` if the cursor is positioned at a null entry
405    ///
406    /// # Examples
407    ///
408    /// ```
409    /// use tether_map::LinkedHashMap;
410    ///
411    /// let mut map = LinkedHashMap::new();
412    /// map.insert_tail("a", 1);
413    /// map.insert_tail("b", 2);
414    ///
415    /// let mut cursor = map.tail_cursor_mut();
416    /// if let Some((key, value)) = cursor.prev_mut() {
417    ///     assert_eq!(key, &"a");
418    ///     *value = 10;
419    /// }
420    /// assert_eq!(map.get(&"a"), Some(&10));
421    /// ```
422    #[inline]
423    pub fn prev_mut(&mut self) -> Option<(&K, &mut T)> {
424        let ptr = self.prev_ptr()?;
425        self.map.ptr_get_entry_mut(ptr)
426    }
427}
428
429#[cfg(test)]
430mod tests {
431    use alloc::vec;
432    use alloc::vec::Vec;
433
434    use crate::LinkedHashMap;
435
436    #[test]
437    fn test_cursor_insert_after_move_to_empty_map() {
438        let mut map = LinkedHashMap::new();
439        {
440            let mut cursor = map.head_cursor_mut();
441            assert_eq!(cursor.insert_after_move_to("first", 1), None);
442            assert_eq!(cursor.current(), Some((&"first", &1)));
443            assert!(cursor.at_head());
444            assert!(cursor.at_tail());
445        }
446        assert_eq!(map.len(), 1);
447    }
448
449    #[test]
450    fn test_cursor_insert_after_move_to_existing_key() {
451        let mut map = LinkedHashMap::new();
452        map.insert("a", 1);
453        map.insert("b", 2);
454
455        let mut cursor = map.head_cursor_mut();
456        let old_value = cursor.insert_after_move_to("aa", 10);
457
458        assert_eq!(old_value, None);
459        assert_eq!(cursor.current(), Some((&"aa", &10)));
460        assert_eq!(map.len(), 3);
461
462        let collected: Vec<_> = map.iter().map(|(k, v)| (*k, *v)).collect();
463        assert_eq!(collected, vec![("a", 1), ("aa", 10), ("b", 2)]);
464    }
465
466    #[test]
467    fn test_cursor_insert_after_move_to_new_key() {
468        let mut map = LinkedHashMap::new();
469        map.insert("a", 1);
470        map.insert("b", 2);
471
472        let mut cursor = map.head_cursor_mut();
473        assert_eq!(cursor.insert_after_move_to("c", 3), None);
474
475        assert_eq!(cursor.current(), Some((&"c", &3)));
476        assert_eq!(map.len(), 3);
477
478        let collected: Vec<_> = map.iter().map(|(k, v)| (*k, *v)).collect();
479        assert_eq!(collected, vec![("a", 1), ("c", 3), ("b", 2)]);
480    }
481
482    #[test]
483    fn test_cursor_insert_before_move_to_empty_map() {
484        let mut map = LinkedHashMap::new();
485        {
486            let mut cursor = map.tail_cursor_mut();
487            assert_eq!(cursor.insert_before_move_to("first", 1), None);
488            assert_eq!(cursor.current(), Some((&"first", &1)));
489            assert!(cursor.at_head());
490            assert!(cursor.at_tail());
491        }
492        assert_eq!(map.len(), 1);
493    }
494
495    #[test]
496    fn test_cursor_insert_before_move_to_existing_key() {
497        let mut map = LinkedHashMap::new();
498        map.insert("a", 1);
499        map.insert("b", 2);
500
501        let mut cursor = map.tail_cursor_mut();
502        let old_value = cursor.insert_before_move_to("a", 10);
503
504        assert_eq!(old_value, Some(1));
505        assert_eq!(cursor.current(), Some((&"a", &10)));
506        assert_eq!(map.len(), 2);
507
508        let collected: Vec<_> = map.iter().map(|(k, v)| (*k, *v)).collect();
509        assert_eq!(collected, vec![("a", 10), ("b", 2)]);
510    }
511
512    #[test]
513    fn test_cursor_insert_before_move_to_new_key() {
514        let mut map = LinkedHashMap::new();
515        map.insert("a", 1);
516        map.insert("b", 2);
517
518        let mut cursor = map.tail_cursor_mut();
519        assert_eq!(cursor.insert_before_move_to("c", 3), None);
520
521        assert_eq!(cursor.current(), Some((&"c", &3)));
522        assert_eq!(map.len(), 3);
523
524        let collected: Vec<_> = map.iter().map(|(k, v)| (*k, *v)).collect();
525        assert_eq!(collected, vec![("a", 1), ("c", 3), ("b", 2)]);
526    }
527
528    #[test]
529    fn test_cursor_remove_prev() {
530        let mut map = LinkedHashMap::new();
531        map.insert("a", 1);
532        map.insert("b", 2);
533        map.insert("c", 3);
534
535        {
536            let mut cursor = map.tail_cursor_mut();
537            let (_ptr, removed) = cursor.remove_prev().unwrap();
538
539            assert_eq!(removed.key, "b");
540            assert_eq!(removed.value, 2);
541            assert_eq!(cursor.current(), Some((&"c", &3)));
542        }
543        assert_eq!(map.len(), 2);
544        let collected: Vec<_> = map.iter().map(|(k, v)| (*k, *v)).collect();
545        assert_eq!(collected, vec![("a", 1), ("c", 3)]);
546    }
547
548    #[test]
549    fn test_cursor_remove_next() {
550        let mut map = LinkedHashMap::new();
551        map.insert("a", 1);
552        map.insert("b", 2);
553        map.insert("c", 3);
554
555        {
556            let mut cursor = map.head_cursor_mut();
557            let (_ptr, removed) = cursor.remove_next().unwrap();
558
559            assert_eq!(removed.key, "b");
560            assert_eq!(removed.value, 2);
561            assert_eq!(cursor.current(), Some((&"a", &1)));
562        }
563        assert_eq!(map.len(), 2);
564        let collected: Vec<_> = map.iter().map(|(k, v)| (*k, *v)).collect();
565        assert_eq!(collected, vec![("a", 1), ("c", 3)]);
566    }
567
568    #[test]
569    fn test_cursor_remove_current() {
570        let mut map = LinkedHashMap::new();
571        map.insert("a", 1);
572        map.insert("b", 2);
573        map.insert("c", 3);
574
575        {
576            let cursor = map.key_cursor_mut(&"b");
577            let (_ptr, removed) = cursor.remove().unwrap();
578
579            assert_eq!(removed.key, "b");
580            assert_eq!(removed.value, 2);
581        }
582        assert_eq!(map.len(), 2);
583        let collected: Vec<_> = map.iter().map(|(k, v)| (*k, *v)).collect();
584        assert_eq!(collected, vec![("a", 1), ("c", 3)]);
585    }
586
587    #[test]
588    fn test_cursor_remove_operations_empty_cases() {
589        let mut map = LinkedHashMap::new();
590        map.insert("only", 1);
591
592        let mut cursor = map.head_cursor_mut();
593        assert_ne!(cursor.remove_prev(), None);
594        assert!(cursor.remove_next().is_none());
595
596        let cursor = cursor.remove();
597        assert!(cursor.is_none());
598        assert_eq!(map.len(), 0);
599    }
600
601    #[test]
602    fn test_cursor_navigation_move_next_prev() {
603        let mut map = LinkedHashMap::new();
604        map.insert("a", 1);
605        map.insert("b", 2);
606        map.insert("c", 3);
607
608        let mut cursor = map.head_cursor_mut();
609        assert_eq!(cursor.current(), Some((&"a", &1)));
610        assert!(cursor.at_head());
611
612        cursor.move_next();
613        assert_eq!(cursor.current(), Some((&"b", &2)));
614        assert!(!cursor.at_head());
615        assert!(!cursor.at_tail());
616
617        cursor.move_next();
618        assert_eq!(cursor.current(), Some((&"c", &3)));
619        assert!(cursor.at_tail());
620
621        cursor.move_next();
622        assert_eq!(cursor.current(), Some((&"a", &1)));
623        assert!(cursor.at_head());
624
625        cursor.move_prev();
626        assert_eq!(cursor.current(), Some((&"c", &3)));
627        assert!(cursor.at_tail());
628
629        cursor.move_prev();
630        assert_eq!(cursor.current(), Some((&"b", &2)));
631        assert!(!cursor.at_head());
632        assert!(!cursor.at_tail());
633    }
634
635    #[test]
636    fn test_cursor_current_and_current_mut() {
637        let mut map = LinkedHashMap::new();
638        map.insert("test", 42);
639
640        let mut cursor = map.head_cursor_mut();
641        assert_eq!(cursor.current(), Some((&"test", &42)));
642
643        if let Some((key, value)) = cursor.current_mut() {
644            assert_eq!(key, &"test");
645            *value = 100;
646        }
647
648        assert_eq!(cursor.current(), Some((&"test", &100)));
649        assert_eq!(map.get(&"test"), Some(&100));
650    }
651
652    #[test]
653    fn test_cursor_next_and_next_mut() {
654        let mut map = LinkedHashMap::new();
655        map.insert("a", 1);
656        map.insert("b", 2);
657
658        let mut cursor = map.head_cursor_mut();
659        assert_eq!(cursor.next(), Some((&"b", &2)));
660
661        if let Some((key, value)) = cursor.next_mut() {
662            assert_eq!(key, &"b");
663            *value = 20;
664        }
665
666        assert_eq!(cursor.next(), Some((&"b", &20)));
667        assert_eq!(map.get(&"b"), Some(&20));
668    }
669
670    #[test]
671    fn test_cursor_prev_and_prev_mut() {
672        let mut map = LinkedHashMap::new();
673        map.insert("a", 1);
674        map.insert("b", 2);
675
676        let mut cursor = map.tail_cursor_mut();
677        assert_eq!(cursor.prev(), Some((&"a", &1)));
678
679        if let Some((key, value)) = cursor.prev_mut() {
680            assert_eq!(key, &"a");
681            *value = 10;
682        }
683
684        assert_eq!(cursor.prev(), Some((&"a", &10)));
685        assert_eq!(map.get(&"a"), Some(&10));
686    }
687
688    #[test]
689    fn test_cursor_ptr_operations() {
690        let mut map = LinkedHashMap::new();
691        map.insert("a", 1);
692        map.insert("b", 2);
693        map.insert("c", 3);
694
695        let current_ptr;
696        let next_ptr;
697        let prev_ptr;
698        {
699            let cursor = map.head_cursor_mut();
700            current_ptr = cursor.ptr().unwrap();
701            next_ptr = cursor.next_ptr().unwrap();
702            prev_ptr = cursor.prev_ptr().unwrap();
703
704            assert_eq!(cursor.get_ptr(&"b"), Some(next_ptr));
705            assert_eq!(cursor.get_ptr(&"nonexistent"), None);
706        }
707        assert_eq!(map.ptr_get(current_ptr), Some(&1));
708        assert_eq!(map.ptr_get(next_ptr), Some(&2));
709        assert_eq!(map.ptr_get(prev_ptr), Some(&3));
710    }
711
712    #[test]
713    fn test_cursor_at_head_tail_single_element() {
714        let mut map = LinkedHashMap::new();
715        map.insert("only", 1);
716
717        let cursor = map.head_cursor_mut();
718        assert!(cursor.at_head());
719        assert!(cursor.at_tail());
720        assert_eq!(cursor.current(), Some((&"only", &1)));
721    }
722
723    #[test]
724    fn test_cursor_iter_from_position() {
725        let mut map = LinkedHashMap::new();
726        map.insert("a", 1);
727        map.insert("b", 2);
728        map.insert("c", 3);
729        map.insert("d", 4);
730
731        let cursor = map.key_cursor_mut(&"b");
732        let collected: Vec<_> = cursor.iter().map(|(k, v)| (*k, *v)).collect();
733        assert_eq!(collected, vec![("b", 2), ("c", 3), ("d", 4), ("a", 1)]);
734    }
735
736    #[test]
737    fn test_cursor_complex_insertion_sequence() {
738        let mut map = LinkedHashMap::new();
739
740        let mut cursor = map.head_cursor_mut();
741        cursor.insert_after_move_to("b", 2);
742        cursor.insert_before_move_to("a", 1);
743        cursor.insert_after_move_to("c", 3);
744
745        let collected: Vec<_> = map.iter().map(|(k, v)| (*k, *v)).collect();
746        assert_eq!(collected, vec![("a", 1), ("c", 3), ("b", 2)]);
747    }
748
749    #[test]
750    fn test_cursor_mixed_operations() {
751        let mut map = LinkedHashMap::new();
752        map.insert("a", 1);
753        map.insert("b", 2);
754        map.insert("c", 3);
755        map.insert("d", 4);
756
757        {
758            let mut cursor = map.key_cursor_mut(&"b");
759
760            cursor.insert_after_move_to("e", 5);
761            assert_eq!(cursor.current(), Some((&"e", &5)));
762
763            cursor.remove_prev();
764
765            cursor.move_next();
766            let (_ptr, removed) = cursor.remove_next().unwrap();
767            assert_eq!(removed.key, "d");
768        }
769        assert_eq!(map.len(), 3);
770        let final_order: Vec<_> = map.iter().map(|(k, v)| (*k, *v)).collect();
771        assert_eq!(final_order, vec![("a", 1), ("e", 5), ("c", 3)]);
772    }
773
774    #[test]
775    fn test_cursor_boundary_conditions() {
776        let mut map = LinkedHashMap::new();
777        map.insert("a", 1);
778        map.insert("b", 2);
779
780        let mut cursor = map.head_cursor_mut();
781
782        cursor.move_prev();
783        assert!(cursor.at_tail());
784        assert_eq!(cursor.current(), Some((&"b", &2)));
785
786        cursor.move_next();
787        assert!(cursor.at_head());
788        assert_eq!(cursor.current(), Some((&"a", &1)));
789
790        let tail_cursor = map.tail_cursor_mut();
791        assert!(tail_cursor.at_tail());
792        assert_eq!(tail_cursor.current(), Some((&"b", &2)));
793    }
794
795    #[test]
796    fn test_cursor_empty_map_operations() {
797        let mut map: LinkedHashMap<&str, i32> = LinkedHashMap::new();
798        let cursor = map.head_cursor_mut();
799
800        assert!(cursor.current().is_none());
801        assert!(cursor.next().is_none());
802        assert!(cursor.prev().is_none());
803        assert!(cursor.ptr().is_none());
804        assert!(cursor.next_ptr().is_none());
805        assert!(cursor.prev_ptr().is_none());
806        assert!(cursor.at_head());
807        assert!(cursor.at_tail());
808    }
809
810    #[test]
811    fn test_cursor_modification_during_iteration() {
812        let mut map = LinkedHashMap::new();
813        map.insert("a", 1);
814        map.insert("b", 2);
815        map.insert("c", 3);
816
817        let mut cursor = map.head_cursor_mut();
818
819        while let Some((key, value)) = cursor.current_mut() {
820            *value *= 10;
821            if *key == "b" {
822                cursor.insert_after_move_to("x", 99);
823                break;
824            }
825            cursor.move_next();
826        }
827
828        let final_state: Vec<_> = map.iter().map(|(k, v)| (*k, *v)).collect();
829        assert_eq!(final_state, vec![("a", 10), ("b", 20), ("x", 99), ("c", 3)]);
830    }
831
832    #[test]
833    fn test_cursor_position_consistency_after_operations() {
834        let mut map = LinkedHashMap::new();
835        map.insert("a", 1);
836        map.insert("b", 2);
837        map.insert("c", 3);
838
839        {
840            let mut cursor = map.key_cursor_mut(&"b");
841            let original_ptr = cursor.ptr().unwrap();
842
843            cursor.insert_after_move_to("d", 4);
844            let new_ptr = cursor.ptr().unwrap();
845            assert_ne!(original_ptr, new_ptr);
846            assert_eq!(cursor.current(), Some((&"d", &4)));
847
848            cursor.insert_before_move_to("e", 5);
849            assert_eq!(cursor.current(), Some((&"e", &5)));
850        }
851        let final_order: Vec<_> = map.iter().map(|(k, v)| (*k, *v)).collect();
852        assert_eq!(
853            final_order,
854            vec![("a", 1), ("b", 2), ("e", 5), ("d", 4), ("c", 3)]
855        );
856    }
857}
tether_map/linked_hash_map/cursor.rs

tether_map/linked_hash_map/
cursor.rs
