orx_linked_list/list/mut_doubly.rs
1use super::{List, helper_traits::HasDoublyEnds};
2use crate::{
3 ListSliceMut,
4 type_aliases::{BACK_IDX, DoublyIdx, FRONT_IDX},
5 variant::Doubly,
6};
7use core::ops::RangeBounds;
8use orx_pinned_vec::PinnedVec;
9use orx_selfref_col::{MemoryPolicy, Node, NodeIdx, Refs};
10
11impl<T, M, P> List<Doubly<T>, M, P>
12where
13 M: MemoryPolicy<Doubly<T>>,
14 P: PinnedVec<Node<Doubly<T>>>,
15{
16 /// ***O(1)*** Sets value of `front` of the list as `new_front` and:
17 /// * returns value of the front element;
18 /// * returns None if the list was empty.
19 ///
20 /// # Examples
21 ///
22 /// ```rust
23 /// use orx_linked_list::*;
24 ///
25 /// let mut list = DoublyList::new();
26 ///
27 /// assert_eq!(0, list.len());
28 ///
29 /// let prior_front = list.swap_front('a');
30 /// assert!(prior_front.is_none());
31 /// assert_eq!(Some(&'a'), list.front());
32 ///
33 /// let prior_front = list.swap_front('z');
34 /// assert_eq!(Some('a'), prior_front);
35 /// assert_eq!(Some(&'z'), list.front());
36 /// ```
37 pub fn swap_front(&mut self, new_front: T) -> Option<T> {
38 match self.0.ends().get(FRONT_IDX) {
39 Some(p) => Some(self.0.swap_data(p, new_front)),
40 None => {
41 self.push_front(new_front);
42 None
43 }
44 }
45 }
46
47 /// ***O(1)*** Sets value of `back` of the list as `new_back` and:
48 /// * returns value of the back element;
49 /// * returns None if the list was empty.
50 ///
51 /// # Examples
52 ///
53 /// ```rust
54 /// use orx_linked_list::*;
55 ///
56 /// let mut list = DoublyList::new();
57 ///
58 /// assert_eq!(0, list.len());
59 ///
60 /// let prior_back = list.swap_back('a');
61 /// assert!(prior_back.is_none());
62 /// assert_eq!(Some(&'a'), list.back());
63 ///
64 /// let prior_back = list.swap_back('z');
65 /// assert_eq!(Some('a'), prior_back);
66 /// assert_eq!(Some(&'z'), list.back());
67 /// ```
68 pub fn swap_back(&mut self, new_back: T) -> Option<T> {
69 match self.0.ends().get(BACK_IDX) {
70 Some(p) => Some(self.0.swap_data(p, new_back)),
71 None => {
72 self.push_back(new_back);
73 None
74 }
75 }
76 }
77
78 /// ***O(1)*** Pushes the `value` to the `front` of the list.
79 ///
80 /// # Examples
81 ///
82 /// ```rust
83 /// use orx_linked_list::*;
84 ///
85 /// let mut list = DoublyList::new();
86 ///
87 /// list.push_front('a');
88 /// list.push_front('b');
89 ///
90 /// assert_eq!(Some(&'b'), list.front());
91 /// assert_eq!(Some(&'a'), list.back());
92 ///
93 /// let popped = list.pop_front();
94 /// assert_eq!(Some('b'), popped);
95 /// ```
96 pub fn push_front(&mut self, value: T) -> DoublyIdx<T> {
97 let idx = self.0.push(value);
98
99 match self.0.ends().get(FRONT_IDX) {
100 Some(front) => {
101 self.0.node_mut(front).prev_mut().set_some(idx);
102 self.0.node_mut(idx).next_mut().set_some(front);
103 self.0.ends_mut().set_some(FRONT_IDX, idx);
104 }
105 None => {
106 self.0.ends_mut().set_some(FRONT_IDX, idx);
107 self.0.ends_mut().set_some(BACK_IDX, idx);
108 }
109 }
110
111 NodeIdx::new(self.0.memory_state(), idx)
112 }
113
114 /// ***O(1)*** Pushes the `value` to the `back` of 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 ///
126 /// assert_eq!(Some(&'b'), list.back());
127 /// assert_eq!(Some(&'a'), list.front());
128 ///
129 /// let popped = list.pop_back();
130 /// assert_eq!(Some('b'), popped);
131 /// ```
132 pub fn push_back(&mut self, value: T) -> DoublyIdx<T> {
133 let idx = self.0.push(value);
134
135 match self.0.ends().get(BACK_IDX) {
136 Some(back) => {
137 self.0.node_mut(back).next_mut().set_some(idx);
138 self.0.node_mut(idx).prev_mut().set_some(back);
139 self.0.ends_mut().set_some(BACK_IDX, idx);
140 }
141 None => {
142 self.0.ends_mut().set_some(FRONT_IDX, idx);
143 self.0.ends_mut().set_some(BACK_IDX, idx);
144 }
145 }
146
147 NodeIdx::new(self.0.memory_state(), idx)
148 }
149
150 /// ***O(1)*** Pops and returns the value at the `front` of the list; returns None if the list is empty.
151 ///
152 /// # Examples
153 ///
154 /// ```rust
155 /// use orx_linked_list::*;
156 ///
157 /// let mut list = DoublyList::new();
158 ///
159 /// let popped = list.pop_front();
160 /// assert!(popped.is_none());
161 ///
162 /// list.push_front('a');
163 /// assert_eq!(Some(&'a'), list.front());
164 ///
165 /// let popped = list.pop_front();
166 /// assert_eq!(Some('a'), popped);
167 /// assert!(list.is_empty());
168 /// ```
169 pub fn pop_front(&mut self) -> Option<T> {
170 self.0.ends().get(FRONT_IDX).map(|front| {
171 match self.0.node(front).next().get() {
172 Some(new_front) => {
173 self.0.node_mut(new_front).prev_mut().clear();
174 self.0.ends_mut().set_some(FRONT_IDX, new_front);
175 }
176 None => self.0.ends_mut().clear(),
177 }
178 self.0.close_and_reclaim(front)
179 })
180 }
181
182 /// ***O(1)*** Pops and returns the value at the `back` of the list; returns None if the list is empty.
183 ///
184 /// # Examples
185 ///
186 /// ```rust
187 /// use orx_linked_list::*;
188 ///
189 /// let mut list = DoublyList::new();
190 ///
191 /// let popped = list.pop_back();
192 /// assert!(popped.is_none());
193 ///
194 /// list.push_front('a');
195 /// assert_eq!(Some(&'a'), list.front());
196 ///
197 /// let popped = list.pop_back();
198 /// assert_eq!(Some('a'), popped);
199 /// assert!(list.is_empty());
200 /// ```
201 pub fn pop_back(&mut self) -> Option<T> {
202 self.0.ends().get(BACK_IDX).map(|back| {
203 match self.0.node(back).prev().get() {
204 Some(new_back) => {
205 self.0.node_mut(new_back).next_mut().clear();
206 self.0.ends_mut().set_some(BACK_IDX, new_back);
207 }
208 None => self.0.ends_mut().clear(),
209 }
210 self.0.close_and_reclaim(back)
211 })
212 }
213
214 /// Creates and returns a slice of the list between the given `range` of indices.
215 ///
216 /// Note that a linked list slice itself also behaves like a linked list,
217 /// reflecting the recursive nature of the data type.
218 /// However, it does not own the data.
219 /// It is rather a view, like a slice is a view to a vec.
220 ///
221 /// Note that slicing might be useful in various ways.
222 /// For instance, we can keep indices of several critical elements of the list.
223 /// We can then get all elements before, after or between any pair of these indices.
224 /// Or we can combine the list with an indices vector, which provides the linked list
225 /// a vec-like usage
226 /// * with the disadvantage of using more memory, and
227 /// * with the advantage of constant time insertions, removals or moves.
228 ///
229 /// # Panics
230 ///
231 /// Panics if any of indices of the range bounds is invalid.
232 ///
233 /// # Example
234 ///
235 /// ```rust
236 /// use orx_linked_list::*;
237 ///
238 /// let mut list = DoublyList::new();
239 ///
240 /// list.push_back(3);
241 /// list.push_front(1);
242 /// list.push_front(7);
243 /// list.push_back(4);
244 /// list.push_front(9);
245 ///
246 /// let expected_values = vec![9, 7, 1, 3, 4];
247 ///
248 /// assert!(list.eq_to_iter_refs(&expected_values));
249 /// assert!(list.slice(..).eq_to_iter_refs(&expected_values));
250 ///
251 /// let idx: Vec<_> = list.indices().collect();
252 ///
253 /// let slice = list.slice(idx[1]..=idx[3]);
254 /// assert_eq!(slice.front(), Some(&7));
255 /// assert_eq!(slice.back(), Some(&3));
256 /// assert!(slice.eq_to_iter_vals([7, 1, 3]));
257 ///
258 /// let sum: usize = slice.iter().sum();
259 /// assert_eq!(sum, 11);
260 /// ```
261 ///
262 /// Note that the linked list and its slices are directed.
263 /// In other words, it does not by default have a cyclic behavior.
264 /// Therefore, if the end of the `range` is before the beginning,
265 /// the slice will stop at the `back` of the list.
266 /// See the following example for clarification.
267 ///
268 /// Currently, cyclic or ring behavior can be achieved by `ring_iter` method.
269 ///
270 /// ```rust
271 /// use orx_linked_list::*;
272 ///
273 /// let mut list: DoublyList<_> = (0..10).collect();
274 /// let idx: Vec<_> = list.indices().collect();
275 ///
276 /// // a..b where b comes later, hence, we get the slice a..b
277 /// let slice = list.slice_mut(idx[1]..idx[4]);
278 /// assert!(slice.eq_to_iter_vals([1, 2, 3]));
279 ///
280 /// // a..b where b comes earlier, then, we get the slice a..back
281 /// let slice = list.slice_mut(idx[4]..idx[1]);
282 /// assert!(slice.eq_to_iter_vals([4, 5, 6, 7, 8, 9]));
283 /// ```
284 pub fn slice_mut<R>(&mut self, range: R) -> ListSliceMut<'_, Doubly<T>, M, P>
285 where
286 R: RangeBounds<DoublyIdx<T>>,
287 {
288 let ends = self.slice_ends(range).expect("invalid indices in range");
289 ListSliceMut { list: self, ends }
290 }
291}