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

tether_map/linked_hash_map/
cursor.rs
