platform_trees/lists/
relative_circular_linked_list.rs

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

platform_trees/lists/
relative_circular_linked_list.rs
