orx_linked_list/list/
mut_doubly_recursive.rs

1use super::List;
2use crate::{
3    type_aliases::{BACK_IDX, FRONT_IDX},
4    variant::Doubly,
5};
6use orx_selfref_col::{MemoryPolicy, Node, Refs};
7use orx_split_vec::{Recursive, SplitVec};
8
9impl<T, M> List<Doubly<T>, M, SplitVec<Node<Doubly<T>>, Recursive>>
10where
11    M: MemoryPolicy<Doubly<T>>,
12{
13    /// ***O(1)*** Appends the `other` list to the `front` of this list.
14    ///
15    /// Time complexity:
16    /// * ***O(1)*** gets `front` of this list, say a,
17    /// * ***O(1)*** gets `back` of the other list, say b,
18    /// * ***O(1)*** connects `b -> a`.
19    ///
20    /// # Examples
21    ///
22    /// ```rust
23    /// use orx_linked_list::*;
24    ///
25    /// let mut list = DoublyList::new();
26    /// list.push_front('b');
27    /// list.push_front('a');
28    /// list.push_back('c');
29    ///
30    /// let other = DoublyList::from_iter(['d', 'e'].into_iter());
31    ///
32    /// list.append_front(other);
33    /// assert!(list.eq_to_iter_vals(['d', 'e', 'a', 'b', 'c']));
34    /// ```
35    #[allow(clippy::missing_panics_doc)]
36    pub fn append_front<M2: MemoryPolicy<Doubly<T>>>(&mut self, other: List<Doubly<T>, M2>) {
37        let (col, other_state) = other.0.into_inner();
38        let (nodes, ends, _len) = col.into_inner();
39
40        self.0.append_nodes(nodes);
41
42        let old_front_exists = !self.0.ends().is_empty();
43        let new_front_exists = !ends.is_empty();
44
45        match (old_front_exists, new_front_exists) {
46            (_, false) => { /* no update when new is empty */ }
47            (false, true) => {
48                let new_front = ends.get(FRONT_IDX).expect("exists");
49                self.0.ends_mut().set_some(FRONT_IDX, new_front);
50            }
51            (true, true) => {
52                let new_front = ends.get(FRONT_IDX).expect("exists");
53                let new_back = ends.get(BACK_IDX).expect("exists");
54                let old_front = self.0.ends().get(FRONT_IDX).expect("exists");
55
56                self.0.node_mut(old_front).prev_mut().set_some(new_back);
57                self.0.node_mut(new_back).next_mut().set_some(old_front);
58
59                self.0.ends_mut().set_some(FRONT_IDX, new_front);
60            }
61        }
62
63        // update state if necessary
64        if other_state != self.memory_state() {
65            self.0.update_state(true);
66            while self.memory_state() == other_state {
67                self.0.update_state(true);
68            }
69        }
70    }
71
72    /// ***O(1)*** Appends the `other` list to the `back` of this list.
73    ///
74    /// Time complexity:
75    /// * ***O(1)*** gets `back` of this list, say a,
76    /// * ***O(1)*** gets `front` of the other list, say b,
77    /// * ***O(1)*** connects `a -> b`.
78    ///
79    /// # Examples
80    ///
81    /// ```rust
82    /// use orx_linked_list::*;
83    ///
84    /// let mut list = DoublyList::new();
85    /// list.push_front('b');
86    /// list.push_front('a');
87    /// list.push_back('c');
88    ///
89    /// let other = DoublyList::from_iter(['d', 'e'].into_iter());
90    ///
91    /// list.append_back(other);
92    /// assert!(list.eq_to_iter_vals(['a', 'b', 'c', 'd', 'e']));
93    /// ```
94    #[allow(clippy::missing_panics_doc)]
95    pub fn append_back<M2: MemoryPolicy<Doubly<T>>>(&mut self, other: List<Doubly<T>, M2>) {
96        let (col, other_state) = other.0.into_inner();
97        let (nodes, ends, _len) = col.into_inner();
98
99        self.0.append_nodes(nodes);
100
101        let old_back_exists = !self.0.ends().is_empty();
102        let new_back_exists = !ends.is_empty();
103
104        match (old_back_exists, new_back_exists) {
105            (_, false) => { /* no update when new is empty */ }
106            (false, true) => {
107                let new_back = ends.get(BACK_IDX).expect("exists");
108                self.0.ends_mut().set_some(BACK_IDX, new_back);
109            }
110            (true, true) => {
111                let new_front = ends.get(FRONT_IDX).expect("exists");
112                let new_back = ends.get(BACK_IDX).expect("exists");
113                let old_back = self.0.ends().get(BACK_IDX).expect("exists");
114
115                self.0.node_mut(old_back).next_mut().set_some(new_front);
116                self.0.node_mut(new_front).prev_mut().set_some(old_back);
117
118                self.0.ends_mut().set_some(BACK_IDX, new_back);
119            }
120        }
121
122        // update state if necessary
123        if other_state != self.memory_state() {
124            self.0.update_state(true);
125            while self.memory_state() == other_state {
126                self.0.update_state(true);
127            }
128        }
129    }
130}
orx_linked_list/list/mut_doubly_recursive.rs

orx_linked_list/list/
mut_doubly_recursive.rs
