platform_trees/lists/
absolute_circular_linked_list.rs

1use crate::AbsoluteLinkedList;
2use platform_num::LinkReference;
3
4/// Circular doubly-linked list with absolute (direct) head/tail access.
5///
6/// Provides `attach_before`, `attach_after`, `attach_as_first`,
7/// `attach_as_last`, and `detach` operations that maintain circular
8/// links and update the head/tail/size automatically.
9///
10/// All methods have default implementations — an empty `impl` block
11/// is sufficient once [`AbsoluteLinkedList`] is implemented.
12pub trait AbsoluteCircularLinkedList<T: LinkReference>: AbsoluteLinkedList<T> {
13    /// Inserts `new_element` immediately before `base_element`.
14    ///
15    /// If `base_element` is the current first element, the first
16    /// pointer is updated to `new_element`.
17    fn attach_before(&mut self, base_element: T, new_element: T) {
18        let base_element_previous = self.get_previous(base_element);
19        self.set_previous(new_element, base_element_previous);
20        self.set_next(new_element, base_element);
21        if base_element == self.get_first() {
22            self.set_first(new_element);
23        }
24        self.set_next(base_element_previous, new_element);
25        self.set_previous(base_element, new_element);
26        self.inc_size();
27    }
28
29    /// Inserts `new_element` immediately after `base_element`.
30    ///
31    /// If `base_element` is the current last element, the last
32    /// pointer is updated to `new_element`.
33    fn attach_after(&mut self, base_element: T, new_element: T) {
34        let base_element_next = self.get_next(base_element);
35        self.set_previous(new_element, base_element);
36        self.set_next(new_element, base_element_next);
37        if base_element == self.get_last() {
38            self.set_last(new_element);
39        }
40        self.set_previous(base_element_next, new_element);
41        self.set_next(base_element, new_element);
42        self.inc_size();
43    }
44
45    /// Inserts `element` as the first element of the list.
46    ///
47    /// If the list is empty, `element` becomes both first and last,
48    /// with its previous and next pointers pointing to itself.
49    fn attach_as_first(&mut self, element: T) {
50        let first = self.get_first();
51        if first == T::from_byte(0) {
52            self.set_first(element);
53            self.set_last(element);
54            self.set_previous(element, element);
55            self.set_next(element, element);
56            self.inc_size();
57        } else {
58            self.attach_before(first, element);
59        }
60    }
61
62    /// Inserts `element` as the last element of the list.
63    ///
64    /// If the list is empty, delegates to [`attach_as_first`](Self::attach_as_first).
65    fn attach_as_last(&mut self, element: T) {
66        let last = self.get_last();
67        if last == T::from_byte(0) {
68            self.attach_as_first(element);
69        } else {
70            self.attach_after(last, element);
71        }
72    }
73
74    /// Removes `element` from the list.
75    ///
76    /// Updates head/tail pointers as needed and clears the element's
77    /// previous and next pointers to `T::from_byte(0)`.
78    fn detach(&mut self, element: T) {
79        let element_previous = self.get_previous(element);
80        let element_next = self.get_next(element);
81        if element_next == element {
82            self.set_first(T::from_byte(0));
83            self.set_last(T::from_byte(0));
84        } else {
85            self.set_next(element_previous, element_next);
86            self.set_previous(element_next, element_previous);
87            if element == self.get_first() {
88                self.set_first(element_next);
89            }
90            if element == self.get_last() {
91                self.set_last(element_previous);
92            }
93        }
94        self.set_previous(element, T::from_byte(0));
95        self.set_next(element, T::from_byte(0));
96        self.dec_size();
97    }
98}
platform_trees/lists/absolute_circular_linked_list.rs

platform_trees/lists/
absolute_circular_linked_list.rs
