orx_linked_list/list/idx_doubly.rs
1use crate::{
2 DoublyIdx, List,
3 type_aliases::{BACK_IDX, FRONT_IDX, IDX_ERR},
4 variant::Doubly,
5};
6use orx_selfref_col::{MemoryPolicy, NodeIdx, NodeIdxError};
7
8impl<T, M> List<Doubly<T>, M>
9where
10 M: MemoryPolicy<Doubly<T>>,
11{
12 // mut
13
14 /// ***O(1)*** Removes and returns value at the given `idx` of the list.
15 ///
16 /// # Panics
17 ///
18 /// Panics:
19 /// * if the `idx` is invalid (`idx_err` is not None for the index),
20 /// * if the element with the given `idx` is already removed from the list.
21 ///
22 /// # Example
23 ///
24 /// ```rust
25 /// use orx_linked_list::*;
26 ///
27 /// let mut list = DoublyList::new();
28 /// list.push_back('c');
29 /// list.push_back('d');
30 /// let idx = list.push_front('b');
31 /// list.push_front('a');
32 /// list.push_back('e');
33 ///
34 /// assert!(list.eq_to_iter_vals(['a', 'b', 'c', 'd', 'e']));
35 ///
36 /// let value = list.remove(idx);
37 ///
38 /// assert_eq!(value, 'b');
39 /// assert!(list.eq_to_iter_vals(['a', 'c', 'd', 'e']));
40 /// ```
41 pub fn remove(&mut self, idx: DoublyIdx<T>) -> T {
42 let idx = self.0.try_get_ptr(idx).expect(IDX_ERR);
43 let [prev, next] = {
44 let node = self.0.node(idx);
45 [node.prev().get(), node.next().get()]
46 };
47
48 match prev {
49 Some(prev) => self.0.node_mut(prev).next_mut().set(next),
50 None => self.0.ends_mut().set(FRONT_IDX, next),
51 }
52
53 match next {
54 Some(next) => self.0.node_mut(next).prev_mut().set(prev),
55 None => self.0.ends_mut().set(BACK_IDX, prev),
56 }
57
58 self.0.close_and_reclaim(idx)
59 }
60
61 /// ***O(1)*** Inserts the given `value` as the next of the node with the given `idx`.
62 ///
63 /// # Panics
64 ///
65 /// Panics:
66 /// * if the `idx` is invalid (`idx_err` is not None for the index),
67 /// * if the element with the given `idx` is already removed from the list.
68 ///
69 /// # Examples
70 ///
71 /// ```rust
72 /// use orx_linked_list::*;
73 ///
74 /// let mut list = DoublyList::new();
75 ///
76 /// list.push_back('a');
77 /// let b = list.push_back('b');
78 /// list.push_back('c');
79 /// list.push_back('d');
80 ///
81 /// assert!(list.eq_to_iter_vals(['a', 'b', 'c', 'd']));
82 ///
83 /// let x = list.insert_next_to(b, 'x');
84 ///
85 /// assert_eq!(list.get(x), Some(&'x'));
86 /// assert!(list.eq_to_iter_vals(['a', 'b', 'x', 'c', 'd']));
87 ///```
88 pub fn insert_next_to(&mut self, idx: DoublyIdx<T>, value: T) -> DoublyIdx<T> {
89 let prev = self.0.try_get_ptr(idx).expect(IDX_ERR);
90 let next = self.0.node(prev).next().get();
91 let idx = self.0.push(value);
92
93 self.0.node_mut(prev).next_mut().set_some(idx);
94 self.0.node_mut(idx).prev_mut().set_some(prev);
95
96 match next {
97 Some(next) => {
98 self.0.node_mut(next).prev_mut().set_some(idx);
99 self.0.node_mut(idx).next_mut().set_some(next);
100 }
101 None => self.0.ends_mut().set_some(BACK_IDX, idx),
102 }
103
104 NodeIdx::new(self.memory_state(), idx)
105 }
106
107 /// ***O(1)*** Inserts the given `value` as the next of the node with the given `idx`.
108 /// Returns the index of the inserted node.
109 ///
110 /// # Panics
111 ///
112 /// Panics:
113 /// * if the `idx` is invalid (`idx_err` is not None for the index),
114 /// * if the element with the given `idx` is already removed from the list.
115 ///
116 /// # Examples
117 ///
118 /// ```rust
119 /// use orx_linked_list::*;
120 ///
121 /// let mut list = DoublyList::new();
122 ///
123 /// list.push_back('a');
124 /// list.push_back('b');
125 /// let c = list.push_back('c');
126 /// list.push_back('d');
127 ///
128 /// assert!(list.eq_to_iter_vals(['a', 'b', 'c', 'd']));
129 ///
130 /// let x = list.insert_prev_to(c, 'x');
131 ///
132 /// assert_eq!(list.get(x), Some(&'x'));
133 /// assert!(list.eq_to_iter_vals(['a', 'b', 'x', 'c', 'd']));
134 ///```
135 pub fn insert_prev_to(&mut self, idx: DoublyIdx<T>, value: T) -> DoublyIdx<T> {
136 let next = self.0.try_get_ptr(idx).expect(IDX_ERR);
137 let prev = self.0.node(next).prev().get();
138 let idx = self.0.push(value);
139
140 self.0.node_mut(next).prev_mut().set_some(idx);
141 self.0.node_mut(idx).next_mut().set_some(next);
142
143 match prev {
144 Some(prev) => {
145 self.0.node_mut(prev).next_mut().set_some(idx);
146 self.0.node_mut(idx).prev_mut().set_some(prev);
147 }
148 None => self.0.ends_mut().set_some(FRONT_IDX, idx),
149 }
150
151 NodeIdx::new(self.memory_state(), idx)
152 }
153
154 /// ***O(1)*** Removes and returns value at the given `idx` of the list.
155 ///
156 /// Does not change the list and returns None:
157 /// * if the `idx` is invalid (`idx_err` is not None for the index),
158 /// * if the element with the given `idx` is already removed from the list.
159 ///
160 /// # Example
161 ///
162 /// ```rust
163 /// use orx_linked_list::*;
164 ///
165 /// let mut list = DoublyList::new();
166 /// list.push_back('c');
167 /// list.push_back('d');
168 /// let idx = list.push_front('b');
169 /// list.push_front('a');
170 /// list.push_back('e');
171 ///
172 /// assert!(list.eq_to_iter_vals(['a', 'b', 'c', 'd', 'e']));
173 ///
174 /// let value = list.try_remove(idx);
175 ///
176 /// assert_eq!(value, Some('b'));
177 /// assert!(list.eq_to_iter_vals(['a', 'c', 'd', 'e']));
178 /// assert_eq!(list.idx_err(idx), Some(NodeIdxError::RemovedNode));
179 ///
180 /// let value = list.try_remove(idx);
181 /// assert_eq!(value, None);
182 /// ```
183 pub fn try_remove(&mut self, idx: DoublyIdx<T>) -> Option<T> {
184 let can_remove = self.0.node_mut_from_idx(idx).is_some_and(|n| n.is_active());
185 match can_remove {
186 true => {
187 let idx = idx.node_ptr();
188 let [prev, next] = {
189 let node = self.0.node(idx);
190 [node.prev().get(), node.next().get()]
191 };
192
193 match prev {
194 Some(prev) => self.0.node_mut(prev).next_mut().set(next),
195 None => self.0.ends_mut().set(FRONT_IDX, next),
196 }
197
198 match next {
199 Some(next) => self.0.node_mut(next).prev_mut().set(prev),
200 None => self.0.ends_mut().set(BACK_IDX, prev),
201 }
202
203 Some(self.0.close_and_reclaim(idx))
204 }
205 false => None,
206 }
207 }
208
209 /// ***O(1)*** Inserts the given `value` as the next of the node with the given `idx`.
210 /// Returns the index of the inserted node.
211 ///
212 /// Does not change the list and returns None:
213 /// * if the `idx` is invalid (`idx_err` is not None for the index),
214 /// * if the element with the given `idx` is already removed from the list.
215 ///
216 /// # Examples
217 ///
218 /// ```rust
219 /// use orx_linked_list::*;
220 ///
221 /// let mut list = DoublyList::new();
222 ///
223 /// list.push_back('a');
224 /// let b = list.push_back('b');
225 /// list.push_back('c');
226 /// list.push_back('d');
227 ///
228 /// assert!(list.eq_to_iter_vals(['a', 'b', 'c', 'd']));
229 ///
230 /// let x = list.try_insert_next_to(b, 'x').unwrap();
231 ///
232 /// assert_eq!(list.get(x), Some(&'x'));
233 /// assert!(list.eq_to_iter_vals(['a', 'b', 'x', 'c', 'd']));
234 ///
235 /// let _ = list.remove(b);
236 /// assert!(list.eq_to_iter_vals(['a', 'x', 'c', 'd']));
237 ///
238 /// let y = list.try_insert_next_to(b, 'y');
239 /// assert_eq!(y, Err(NodeIdxError::RemovedNode));
240 /// assert!(list.eq_to_iter_vals(['a', 'x', 'c', 'd'])); // unchanged
241 ///```
242 pub fn try_insert_next_to(
243 &mut self,
244 idx: DoublyIdx<T>,
245 value: T,
246 ) -> Result<DoublyIdx<T>, NodeIdxError> {
247 let prev = self.0.try_get_ptr(idx)?;
248 let next = self.0.node(prev).next().get();
249 let idx = self.0.push(value);
250
251 self.0.node_mut(prev).next_mut().set_some(idx);
252 self.0.node_mut(idx).prev_mut().set_some(prev);
253
254 match next {
255 Some(next) => {
256 self.0.node_mut(next).prev_mut().set_some(idx);
257 self.0.node_mut(idx).next_mut().set_some(next);
258 }
259 None => self.0.ends_mut().set_some(BACK_IDX, idx),
260 }
261
262 Ok(NodeIdx::new(self.memory_state(), idx))
263 }
264
265 /// ***O(1)*** Inserts the given `value` as the next of the node with the given `idx`.
266 /// Returns the index of the inserted node.
267 ///
268 /// Does not change the list and returns None:
269 /// * if the `idx` is invalid (`idx_err` is not None for the index),
270 /// * if the element with the given `idx` is already removed from the list.
271 ///
272 /// # Examples
273 ///
274 /// ```rust
275 /// use orx_linked_list::*;
276 ///
277 /// let mut list = DoublyList::new();
278 ///
279 /// list.push_back('a');
280 /// list.push_back('b');
281 /// let c = list.push_back('c');
282 /// list.push_back('d');
283 ///
284 /// assert!(list.eq_to_iter_vals(['a', 'b', 'c', 'd']));
285 ///
286 /// let x = list.try_insert_prev_to(c, 'x').unwrap();
287 ///
288 /// assert_eq!(list.get(x), Some(&'x'));
289 /// assert!(list.eq_to_iter_vals(['a', 'b', 'x', 'c', 'd']));
290 ///
291 /// let _ = list.remove(c);
292 /// assert!(list.eq_to_iter_vals(['a', 'b', 'x', 'd']));
293 ///
294 /// let y = list.try_insert_prev_to(c, 'y');
295 /// assert_eq!(y, Err(NodeIdxError::RemovedNode));
296 /// assert!(list.eq_to_iter_vals(['a', 'b', 'x', 'd'])); // unchanged
297 ///```
298 pub fn try_insert_prev_to(
299 &mut self,
300 idx: DoublyIdx<T>,
301 value: T,
302 ) -> Result<DoublyIdx<T>, NodeIdxError> {
303 let next = self.0.try_get_ptr(idx)?;
304 let prev = self.0.node(next).prev().get();
305 let idx = self.0.push(value);
306
307 self.0.node_mut(next).prev_mut().set_some(idx);
308 self.0.node_mut(idx).next_mut().set_some(next);
309
310 match prev {
311 Some(prev) => {
312 self.0.node_mut(prev).next_mut().set_some(idx);
313 self.0.node_mut(idx).prev_mut().set_some(prev);
314 }
315 None => self.0.ends_mut().set_some(FRONT_IDX, idx),
316 }
317
318 Ok(NodeIdx::new(self.memory_state(), idx))
319 }
320}