orx_linked_list/list/linear.rs
1use crate::{Doubly, DoublyIterable, List, Singly, SinglyIterable, type_aliases::OOB};
2use orx_pinned_vec::PinnedVec;
3use orx_selfref_col::{MemoryPolicy, Node, NodeIdx};
4
5// singly
6
7impl<T, M, P> List<Singly<T>, M, P>
8where
9 M: MemoryPolicy<Singly<T>>,
10 P: PinnedVec<Node<Singly<T>>>,
11{
12 /// ***O(n)*** Inserts the given `value` at the `position`-th element of the list.
13 ///
14 /// Similar to push methods, returns an index to the inserted node to allow constant time access.
15 ///
16 /// Time complexity:
17 /// * starts from the `front`,
18 /// * ***O(n)*** iterates until reaching the element,
19 /// * ***O(1)*** inserts the value.
20 ///
21 /// # Panics
22 ///
23 /// Panics if `position > self.len()`.
24 ///
25 /// # Example
26 ///
27 /// ```rust
28 /// use orx_linked_list::*;
29 ///
30 /// let mut list = SinglyList::from_iter(['b', 'c', 'd']);
31 ///
32 /// list.insert_at(0, 'a');
33 /// assert!(list.eq_to_iter_vals(['a', 'b', 'c', 'd']));
34 ///
35 /// list.insert_at(4, 'e');
36 /// assert!(list.eq_to_iter_vals(['a', 'b', 'c', 'd', 'e']));
37 ///
38 /// list.insert_at(3, 'x');
39 /// assert!(list.eq_to_iter_vals(['a', 'b', 'c', 'x', 'd', 'e']));
40 /// ```
41 pub fn insert_at(&mut self, position: usize, value: T) -> NodeIdx<Singly<T>> {
42 match position {
43 0 => self.push_front(value),
44 x => {
45 let prev = self.iter_ptr().nth(x - 1).expect(OOB);
46 let idx = self.0.push(value);
47
48 if let Some(next) = self.0.node(&prev).next().get().cloned() {
49 self.0.node_mut(&idx).next_mut().set_some(next);
50 }
51
52 self.0.node_mut(&prev).next_mut().set_some(idx.clone());
53
54 NodeIdx::new(self.memory_state(), &idx)
55 }
56 }
57 }
58
59 /// ***O(n)*** Removes and returns value at the `position`-th element of the list.
60 /// Returns None if `position` is out-of-bounds.
61 ///
62 /// Time complexity:
63 /// * starts from the `front`,
64 /// * ***O(n)*** iterates until reaching the element,
65 /// * ***O(1)*** removes the value.
66 ///
67 /// # Example
68 ///
69 /// ```rust
70 /// use orx_linked_list::*;
71 ///
72 /// let mut list = SinglyList::from_iter(['a', 'b', 'c', 'd', 'e']);
73 ///
74 /// let value = list.remove_at(0);
75 /// assert_eq!(value, Some('a'));
76 /// assert!(list.eq_to_iter_vals(['b', 'c', 'd', 'e']));
77 ///
78 /// let value = list.remove_at(3);
79 /// assert_eq!(value, Some('e'));
80 /// assert!(list.eq_to_iter_vals(['b', 'c', 'd']));
81 ///
82 /// let value = list.remove_at(1);
83 /// assert_eq!(value, Some('c'));
84 /// assert!(list.eq_to_iter_vals(['b', 'd']));
85 /// ```
86 #[allow(clippy::missing_panics_doc, clippy::unwrap_in_result)]
87 pub fn remove_at(&mut self, position: usize) -> Option<T> {
88 match position {
89 x if x >= self.len() => None,
90 0 => self.pop_front(),
91 x => {
92 let (prev, idx) = {
93 let mut iter = self.iter_ptr();
94 let prev = iter.by_ref().nth(x - 1).expect(OOB);
95 let idx = iter.next().expect(OOB);
96 (prev, idx)
97 };
98
99 match self.0.node(&idx).next().get().cloned() {
100 Some(next) => self.0.node_mut(&prev).next_mut().set_some(next),
101 None => self.0.node_mut(&prev).next_mut().set_none(),
102 }
103
104 Some(self.0.close_and_reclaim(&idx))
105 }
106 }
107 }
108}
109
110// doubly
111
112impl<T, M, P> List<Doubly<T>, M, P>
113where
114 M: MemoryPolicy<Doubly<T>>,
115 P: PinnedVec<Node<Doubly<T>>>,
116{
117 /// ***O(n)*** Inserts the given `value` at the `position`-th element of the list.
118 ///
119 /// Time complexity:
120 /// * starts from the `front`,
121 /// * ***O(n)*** iterates until reaching the element,
122 /// * ***O(1)*** inserts the value.
123 ///
124 /// # Panics
125 ///
126 /// Panics if `position > self.len()`.
127 ///
128 /// # Example
129 ///
130 /// ```rust
131 /// use orx_linked_list::*;
132 ///
133 /// let mut list = DoublyList::from_iter(['b', 'c', 'd']);
134 ///
135 /// list.insert_at(0, 'a');
136 /// assert!(list.eq_to_iter_vals(['a', 'b', 'c', 'd']));
137 ///
138 /// list.insert_at(4, 'e');
139 /// assert!(list.eq_to_iter_vals(['a', 'b', 'c', 'd', 'e']));
140 ///
141 /// list.insert_at(3, 'x');
142 /// assert!(list.eq_to_iter_vals(['a', 'b', 'c', 'x', 'd', 'e']));
143 /// ```
144 pub fn insert_at(&mut self, position: usize, value: T) -> NodeIdx<Doubly<T>> {
145 match position {
146 0 => self.push_front(value),
147 x if x == self.len() => self.push_back(value),
148 _ => {
149 let prev = self.iter_ptr().nth(position - 1).expect(OOB);
150 let idx = self.0.push(value);
151 let next = self.0.node(&prev).next().get().cloned().expect("exists");
152
153 self.0.node_mut(&prev).next_mut().set_some(idx.clone());
154 self.0.node_mut(&next).prev_mut().set_some(idx.clone());
155
156 self.0.node_mut(&idx).prev_mut().set_some(prev);
157 self.0.node_mut(&idx).next_mut().set_some(next);
158
159 NodeIdx::new(self.memory_state(), &idx)
160 }
161 }
162 }
163
164 /// ***O(n)*** Inserts the given `value` at the `position_from_back`-th element of the list.
165 ///
166 /// Time complexity:
167 /// * starts from the `front`,
168 /// * ***O(n)*** iterates until reaching the element,
169 /// * ***O(1)*** inserts the value.
170 ///
171 /// # Panics
172 ///
173 /// Panics if `position_from_back > self.len()`.
174 ///
175 /// # Example
176 ///
177 /// ```rust
178 /// use orx_linked_list::*;
179 ///
180 /// let mut list = DoublyList::from_iter(['b', 'c', 'd']);
181 ///
182 /// list.insert_at_from_back(0, 'e');
183 /// assert!(list.eq_to_iter_vals(['b', 'c', 'd', 'e']));
184 ///
185 /// list.insert_at_from_back(4, 'a');
186 /// assert!(list.eq_to_iter_vals(['a', 'b', 'c', 'd', 'e']));
187 ///
188 /// list.insert_at_from_back(2, 'x');
189 /// assert!(list.eq_to_iter_vals(['a', 'b', 'c', 'x', 'd', 'e']));
190 /// ```
191 pub fn insert_at_from_back(
192 &mut self,
193 position_from_back: usize,
194 value: T,
195 ) -> NodeIdx<Doubly<T>> {
196 match position_from_back {
197 0 => self.push_back(value),
198 x if x == self.len() => self.push_front(value),
199 x => {
200 let mut iter = self.iter_ptr().rev();
201 let next = iter.nth(x - 1).expect(OOB);
202 let idx = self.0.push(value);
203 let prev = self.0.node(&next).prev().get().expect("exists").clone();
204
205 self.0.node_mut(&next).prev_mut().set_some(idx.clone());
206 self.0.node_mut(&prev).next_mut().set_some(idx.clone());
207
208 self.0.node_mut(&idx).prev_mut().set_some(prev);
209 self.0.node_mut(&idx).next_mut().set_some(next);
210
211 NodeIdx::new(self.memory_state(), &idx)
212 }
213 }
214 }
215
216 /// ***O(n)*** Removes and returns value at the `position`-th element of the list.
217 /// Returns None if `position` is out-of-bounds.
218 ///
219 /// Time complexity:
220 /// * starts from the `front`,
221 /// * ***O(n)*** iterates until reaching the element,
222 /// * ***O(1)*** removes the value.
223 ///
224 /// # Example
225 ///
226 /// ```rust
227 /// use orx_linked_list::*;
228 ///
229 /// let mut list = DoublyList::from_iter(['a', 'b', 'c', 'd', 'e']);
230 ///
231 /// let value = list.remove_at(0);
232 /// assert_eq!(value, Some('a'));
233 /// assert!(list.eq_to_iter_vals(['b', 'c', 'd', 'e']));
234 ///
235 /// let value = list.remove_at(3);
236 /// assert_eq!(value, Some('e'));
237 /// assert!(list.eq_to_iter_vals(['b', 'c', 'd']));
238 ///
239 /// let value = list.remove_at(1);
240 /// assert_eq!(value, Some('c'));
241 /// assert!(list.eq_to_iter_vals(['b', 'd']));
242 /// ```
243 #[allow(clippy::missing_panics_doc, clippy::unwrap_in_result)]
244 pub fn remove_at(&mut self, position: usize) -> Option<T> {
245 match position {
246 x if x >= self.len() => None,
247 0 => self.pop_front(),
248 x if x == self.len() - 1 => self.pop_back(),
249 x => {
250 let (prev, idx, next) = {
251 let mut iter = self.iter_ptr();
252 let prev = iter.by_ref().nth(x - 1).expect(OOB);
253 let idx = iter.next().expect(OOB);
254 let next = iter.next().expect(OOB);
255 (prev, idx, next)
256 };
257
258 self.0.node_mut(&prev).next_mut().set_some(next.clone());
259 self.0.node_mut(&next).prev_mut().set_some(prev);
260
261 Some(self.0.close_and_reclaim(&idx))
262 }
263 }
264 }
265
266 /// ***O(n)*** Removes and returns value at the `position_from_back`-th element from the back of the list.
267 /// Returns None if `position` is out-of-bounds.
268 ///
269 /// Time complexity:
270 /// * starts from the `back`,
271 /// * ***O(n)*** iterates until reaching the element,
272 /// * ***O(1)*** removes the value.
273 ///
274 /// # Example
275 ///
276 /// ```rust
277 /// use orx_linked_list::*;
278 ///
279 /// let mut list = DoublyList::from_iter(['a', 'b', 'c', 'd', 'e']);
280 ///
281 /// let value = list.remove_at_from_back(4);
282 /// assert_eq!(value, Some('a'));
283 /// assert!(list.eq_to_iter_vals(['b', 'c', 'd', 'e']));
284 ///
285 /// let value = list.remove_at_from_back(0);
286 /// assert_eq!(value, Some('e'));
287 /// assert!(list.eq_to_iter_vals(['b', 'c', 'd']));
288 ///
289 /// let value = list.remove_at_from_back(1);
290 /// assert_eq!(value, Some('c'));
291 /// assert!(list.eq_to_iter_vals(['b', 'd']));
292 /// ```
293 #[allow(clippy::missing_panics_doc, clippy::unwrap_in_result)]
294 pub fn remove_at_from_back(&mut self, position_from_back: usize) -> Option<T> {
295 match position_from_back {
296 x if x >= self.len() => None,
297 0 => self.pop_back(),
298 x if x == self.len() - 1 => self.pop_front(),
299 x => {
300 let (prev, idx, next) = {
301 let mut iter = self.iter_ptr().rev();
302 let next = iter.by_ref().nth(x - 1).expect(OOB);
303 let idx = iter.next().expect(OOB);
304 let prev = iter.next().expect(OOB);
305 (prev, idx, next)
306 };
307
308 self.0.node_mut(&prev).next_mut().set_some(next.clone());
309 self.0.node_mut(&next).prev_mut().set_some(prev);
310
311 Some(self.0.close_and_reclaim(&idx))
312 }
313 }
314 }
315}