orx_linked_list/list/linear_eq.rs
1use crate::{Doubly, DoublyIdx, DoublyIterable, List, Singly, SinglyIdx, SinglyIterable};
2use orx_pinned_vec::PinnedVec;
3use orx_selfref_col::{MemoryPolicy, Node, NodeIdx};
4
5// both
6
7impl<T, M, P> List<Singly<T>, M, P>
8where
9 M: MemoryPolicy<Singly<T>>,
10 T: PartialEq,
11 P: PinnedVec<Node<Singly<T>>>,
12{
13 /// ***O(n)*** Performs a forward search from the front and returns the index of the first node with value equal to the given `value`.
14 ///
15 /// Returns None if there is no element with the given value.
16 ///
17 /// Obtained `NodeIdx` can later be used for constant time access to the corresponding element.
18 ///
19 /// # Examples
20 ///
21 /// ```rust
22 /// use orx_linked_list::*;
23 ///
24 /// let mut list = DoublyList::from_iter(['a', 'b', 'c', 'd']);
25 ///
26 /// let x = list.idx_of(&'x');
27 /// assert!(x.is_none());
28 ///
29 /// let b = list.idx_of(&'b'); // O(n)
30 /// assert!(b.is_some());
31 ///
32 /// let b = b.unwrap();
33 ///
34 /// let data_b = list.get(&b); // O(1)
35 /// assert_eq!(data_b, Some(&'b'));
36 ///
37 /// // O(1) to create the iterators from the index
38 /// assert_eq!(&['b', 'c', 'd'], list.iter_from(&b).copied().collect::<Vec<_>>().as_slice());
39 /// assert_eq!(&['b', 'a'], list.iter_backward_from(&b).copied().collect::<Vec<_>>().as_slice());
40 ///
41 /// list.insert_prev_to(&b, 'X'); // O(1)
42 /// list.insert_next_to(&b, 'Y'); // O(1)
43 /// assert!(list.eq_to_iter_vals(['a', 'X', 'b', 'Y', 'c', 'd']));
44 ///
45 /// let removed = list.remove(&b); // O(1)
46 /// assert_eq!(removed, 'b');
47 /// assert!(list.eq_to_iter_vals(['a', 'X', 'Y', 'c', 'd']));
48 ///
49 /// assert_eq!(list.get(&b), None);
50 /// assert_eq!(list.idx_err(&b), Some(NodeIdxError::RemovedNode));
51 /// ```
52 pub fn idx_of(&self, value: &T) -> Option<SinglyIdx<T>> {
53 self.iter_ptr()
54 .find(|p| self.0.node(p).data().is_some_and(|d| d == value))
55 .map(|p| NodeIdx::new(self.memory_state(), &p))
56 }
57
58 /// ***O(n)*** Performs a forward search from the front and returns `true` if there exists a node with value equal to the given `value`.
59 ///
60 /// Returns false if there is no element with the given value.
61 ///
62 /// # Examples
63 ///
64 /// ```rust
65 /// use orx_linked_list::*;
66 ///
67 /// let list: DoublyList<_> = ['a', 'b', 'c', 'd'].into_iter().collect();
68 ///
69 /// assert!(list.contains(&'a'));
70 /// assert!(!list.contains(&'x'));
71 /// ```
72 pub fn contains(&self, value: &T) -> bool {
73 self.iter_ptr()
74 .any(|p| self.0.node(&p).data().is_some_and(|d| d == value))
75 }
76
77 /// ***O(n)*** Performs a forward search from the front and returns the position of the first node with value equal to the given `value`.
78 ///
79 /// Returns None if there is no element with the given value.
80 ///
81 /// # Examples
82 ///
83 /// ```rust
84 /// use orx_linked_list::*;
85 ///
86 /// let mut list = DoublyList::from_iter(['a', 'b', 'c', 'd']);
87 ///
88 /// let x = list.position_of_value(&'x');
89 /// assert_eq!(x, None);
90 ///
91 /// let b = list.position_of_value(&'b'); // O(n)
92 /// assert_eq!(b, Some(1));
93 /// ```
94 pub fn position_of_value(&self, value: &T) -> Option<usize> {
95 self.iter_ptr().enumerate().find_map(|(i, p)| {
96 self.0
97 .node(&p)
98 .data()
99 .is_some_and(|d| d == value)
100 .then_some(i)
101 })
102 }
103}
104
105// doubly
106
107impl<T, M, P> List<Doubly<T>, M, P>
108where
109 M: MemoryPolicy<Doubly<T>>,
110 T: PartialEq,
111 P: PinnedVec<Node<Doubly<T>>>,
112{
113 /// ***O(n)*** Performs a forward search from the front and returns the index of the first node with value equal to the given `value`.
114 ///
115 /// Returns None if there is no element with the given value.
116 ///
117 /// Obtained `NodeIdx` can later be used for constant time access to the corresponding element.
118 ///
119 /// # Examples
120 ///
121 /// ```rust
122 /// use orx_linked_list::*;
123 ///
124 /// let mut list = DoublyList::from_iter(['a', 'b', 'c', 'd']);
125 ///
126 /// let x = list.idx_of(&'x');
127 /// assert!(x.is_none());
128 ///
129 /// let b = list.idx_of(&'b'); // O(n)
130 /// assert!(b.is_some());
131 ///
132 /// let b = b.unwrap();
133 ///
134 /// let data_b = list.get(&b); // O(1)
135 /// assert_eq!(data_b, Some(&'b'));
136 ///
137 /// // O(1) to create the iterators from the index
138 /// assert_eq!(&['b', 'c', 'd'], list.iter_from(&b).copied().collect::<Vec<_>>().as_slice());
139 /// assert_eq!(&['b', 'a'], list.iter_backward_from(&b).copied().collect::<Vec<_>>().as_slice());
140 ///
141 /// list.insert_prev_to(&b, 'X'); // O(1)
142 /// list.insert_next_to(&b, 'Y'); // O(1)
143 /// assert!(list.eq_to_iter_vals(['a', 'X', 'b', 'Y', 'c', 'd']));
144 ///
145 /// let removed = list.remove(&b); // O(1)
146 /// assert_eq!(removed, 'b');
147 /// assert!(list.eq_to_iter_vals(['a', 'X', 'Y', 'c', 'd']));
148 ///
149 /// assert_eq!(list.get(&b), None);
150 /// assert_eq!(list.idx_err(&b), Some(NodeIdxError::RemovedNode));
151 /// ```
152 pub fn idx_of(&self, value: &T) -> Option<DoublyIdx<T>> {
153 self.iter_ptr()
154 .find(|p| self.0.node(p).data().is_some_and(|d| d == value))
155 .map(|p| NodeIdx::new(self.memory_state(), &p))
156 }
157
158 /// ***O(n)*** Performs a forward search from the front and returns `true` if there exists a node with value equal to the given `value`.
159 ///
160 /// Returns false if there is no element with the given value.
161 ///
162 /// # Examples
163 ///
164 /// ```rust
165 /// use orx_linked_list::*;
166 ///
167 /// let list: DoublyList<_> = ['a', 'b', 'c', 'd'].into_iter().collect();
168 ///
169 /// assert!(list.contains(&'a'));
170 /// assert!(!list.contains(&'x'));
171 /// ```
172 pub fn contains(&self, value: &T) -> bool {
173 self.iter_ptr()
174 .any(|p| self.0.node(&p).data().is_some_and(|d| d == value))
175 }
176
177 /// ***O(n)*** Performs a forward search from the front and returns the position of the first node with value equal to the given `value`.
178 ///
179 /// Returns None if there is no element with the given value.
180 ///
181 /// # Examples
182 ///
183 /// ```rust
184 /// use orx_linked_list::*;
185 ///
186 /// let mut list = DoublyList::from_iter(['a', 'b', 'c', 'd']);
187 ///
188 /// let x = list.position_of_value(&'x');
189 /// assert_eq!(x, None);
190 ///
191 /// let b = list.position_of_value(&'b'); // O(n)
192 /// assert_eq!(b, Some(1));
193 /// ```
194 pub fn position_of_value(&self, value: &T) -> Option<usize> {
195 self.iter_ptr().enumerate().find_map(|(i, p)| {
196 self.0
197 .node(&p)
198 .data()
199 .is_some_and(|d| d == value)
200 .then_some(i)
201 })
202 }
203
204 /// ***O(n)*** Performs a backward search from the back and returns the index of the first node with value equal to the given `value`.
205 ///
206 /// Returns None if there is no element with the given value.
207 ///
208 /// Obtained `NodeIdx` can later be used for constant time access to the corresponding element.
209 ///
210 /// # Examples
211 ///
212 /// ```rust
213 /// use orx_linked_list::*;
214 ///
215 /// let mut list = DoublyList::from_iter(['a', 'b', 'c', 'd']);
216 ///
217 /// let x = list.idx_of(&'x');
218 /// assert!(x.is_none());
219 ///
220 /// let b = list.idx_of_from_back(&'b'); // O(n)
221 /// assert!(b.is_some());
222 ///
223 /// let b = b.unwrap();
224 ///
225 /// let data_b = list.get(&b); // O(1)
226 /// assert_eq!(data_b, Some(&'b'));
227 ///
228 /// // O(1) to create the iterators from the index
229 /// assert_eq!(&['b', 'c', 'd'], list.iter_from(&b).copied().collect::<Vec<_>>().as_slice());
230 /// assert_eq!(&['b', 'a'], list.iter_backward_from(&b).copied().collect::<Vec<_>>().as_slice());
231 ///
232 /// list.insert_prev_to(&b, 'X'); // O(1)
233 /// list.insert_next_to(&b, 'Y'); // O(1)
234 /// assert!(list.eq_to_iter_vals(['a', 'X', 'b', 'Y', 'c', 'd']));
235 ///
236 /// let removed = list.remove(&b); // O(1)
237 /// assert_eq!(removed, 'b');
238 /// assert!(list.eq_to_iter_vals(['a', 'X', 'Y', 'c', 'd']));
239 ///
240 /// assert_eq!(list.get(&b), None);
241 /// assert_eq!(list.idx_err(&b), Some(NodeIdxError::RemovedNode));
242 /// ```
243 pub fn idx_of_from_back(&self, value: &T) -> Option<DoublyIdx<T>> {
244 self.iter_ptr()
245 .rev()
246 .find(|p| self.0.node(p).data().is_some_and(|d| d == value))
247 .map(|p| NodeIdx::new(self.memory_state(), &p))
248 }
249
250 /// ***O(n)*** Performs a backward search from the back and returns `true` if there exists a node with value equal to the given `value`.
251 ///
252 /// Returns false if there is no element with the given value.
253 ///
254 /// # Examples
255 ///
256 /// ```rust
257 /// use orx_linked_list::*;
258 ///
259 /// let list: DoublyList<_> = ['a', 'b', 'c', 'd'].into_iter().collect();
260 ///
261 /// assert!(list.contains(&'a'));
262 /// assert!(!list.contains(&'x'));
263 /// ```
264 pub fn contains_from_back(&self, value: &T) -> bool {
265 self.iter_ptr()
266 .rev()
267 .any(|p| self.0.node(&p).data().is_some_and(|d| d == value))
268 }
269
270 /// ***O(n)*** Performs a backward search from the back and returns the position of the first node with value equal to the given `value`.
271 ///
272 /// Returns None if there is no element with the given value.
273 ///
274 /// # Examples
275 ///
276 /// ```rust
277 /// use orx_linked_list::*;
278 ///
279 /// let mut list = DoublyList::from_iter(['a', 'b', 'c', 'd']);
280 ///
281 /// let x = list.position_of_from_back(&'x');
282 /// assert_eq!(x, None);
283 ///
284 /// let b = list.position_of_from_back(&'b'); // O(n)
285 /// assert_eq!(b, Some(2));
286 /// ```
287 pub fn position_of_from_back(&self, value: &T) -> Option<usize> {
288 self.iter_ptr().rev().enumerate().find_map(|(i, p)| {
289 self.0
290 .node(&p)
291 .data()
292 .is_some_and(|d| d == value)
293 .then_some(i)
294 })
295 }
296}