platform_trees/lists/
relative_circular_linked_list.rs

1use crate::RelativeLinkedList;
2use platform_num::LinkReference;
3
4/// Circular doubly-linked list with head-relative positioning.
5///
6/// Like [`AbsoluteCircularLinkedList`](super::AbsoluteCircularLinkedList)
7/// but takes a `head` parameter to support multiple independent circular
8/// lists sharing the same node storage.
9///
10/// All methods have default implementations — an empty `impl` block
11/// is sufficient once [`RelativeLinkedList`] is implemented.
12pub trait RelativeCircularLinkedList<T: LinkReference>: RelativeLinkedList<T> {
13    /// Inserts `new_element` immediately before `base_element` in the
14    /// list identified by `head`.
15    fn attach_before(&mut self, head: T, base_element: T, new_element: T) {
16        let base_element_previous = self.get_previous(base_element);
17        self.set_previous(new_element, base_element_previous);
18        self.set_next(new_element, base_element);
19        if base_element == self.get_first(head) {
20            self.set_first(head, new_element);
21        }
22        self.set_next(base_element_previous, new_element);
23        self.set_previous(base_element, new_element);
24        self.inc_size(head);
25    }
26
27    /// Inserts `new_element` immediately after `base_element` in the
28    /// list identified by `head`.
29    fn attach_after(&mut self, head: T, base_element: T, new_element: T) {
30        let base_element_next = self.get_next(base_element);
31        self.set_previous(new_element, base_element);
32        self.set_next(new_element, base_element_next);
33        if base_element == self.get_last(head) {
34            self.set_last(head, new_element);
35        }
36        self.set_previous(base_element_next, new_element);
37        self.set_next(base_element, new_element);
38        self.inc_size(head);
39    }
40
41    /// Inserts `element` as the first element of the list identified
42    /// by `head`.
43    fn attach_as_first(&mut self, head: T, element: T) {
44        let first = self.get_first(head);
45        if first == T::from_byte(0) {
46            self.set_first(head, element);
47            self.set_last(head, element);
48            self.set_previous(element, element);
49            self.set_next(element, element);
50            self.inc_size(head);
51        } else {
52            self.attach_before(head, first, element);
53        }
54    }
55
56    /// Inserts `element` as the last element of the list identified
57    /// by `head`.
58    fn attach_as_last(&mut self, head: T, element: T) {
59        let last = self.get_last(head);
60        if last == T::from_byte(0) {
61            self.attach_as_first(head, element);
62        } else {
63            self.attach_after(head, last, element);
64        }
65    }
66
67    /// Removes `element` from the list identified by `head`.
68    fn detach(&mut self, head: T, element: T) {
69        let element_previous = self.get_previous(element);
70        let element_next = self.get_next(element);
71        if element_next == element {
72            self.set_first(head, T::from_byte(0));
73            self.set_last(head, T::from_byte(0));
74        } else {
75            self.set_next(element_previous, element_next);
76            self.set_previous(element_next, element_previous);
77            if element == self.get_first(head) {
78                self.set_first(head, element_next);
79            }
80            if element == self.get_last(head) {
81                self.set_last(head, element_previous);
82            }
83        }
84        self.set_previous(element, T::from_byte(0));
85        self.set_next(element, T::from_byte(0));
86        self.dec_size(head);
87    }
88}
platform_trees/lists/relative_circular_linked_list.rs

platform_trees/lists/
relative_circular_linked_list.rs
