]>
Commit | Line | Data |
---|---|---|
1a4d82fc JJ |
1 | //! A doubly-linked list with owned nodes. |
2 | //! | |
32a655c1 SL |
3 | //! The `LinkedList` allows pushing and popping elements at either end |
4 | //! in constant time. | |
5 | //! | |
60c5eb7d XL |
6 | //! NOTE: It is almost always better to use [`Vec`] or [`VecDeque`] because |
7 | //! array-based containers are generally faster, | |
8 | //! more memory efficient, and make better use of CPU cache. | |
32a655c1 | 9 | //! |
3dfed10e XL |
10 | //! [`Vec`]: crate::vec::Vec |
11 | //! [`VecDeque`]: super::vec_deque::VecDeque | |
1a4d82fc | 12 | |
85aaf69f | 13 | #![stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 14 | |
1a4d82fc | 15 | use core::cmp::Ordering; |
1a4d82fc | 16 | use core::fmt; |
dfeec247 | 17 | use core::hash::{Hash, Hasher}; |
9e0c209e | 18 | use core::iter::{FromIterator, FusedIterator}; |
5bcae85e | 19 | use core::marker::PhantomData; |
1a4d82fc | 20 | use core::mem; |
83c7162d | 21 | use core::ptr::NonNull; |
1a4d82fc | 22 | |
a7813a04 | 23 | use super::SpecExtend; |
dfeec247 | 24 | use crate::boxed::Box; |
a7813a04 | 25 | |
416331ca XL |
26 | #[cfg(test)] |
27 | mod tests; | |
28 | ||
32a655c1 SL |
29 | /// A doubly-linked list with owned nodes. |
30 | /// | |
31 | /// The `LinkedList` allows pushing and popping elements at either end | |
32 | /// in constant time. | |
33 | /// | |
94222f64 XL |
34 | /// A `LinkedList` with a known list of items can be initialized from an array: |
35 | /// ``` | |
36 | /// use std::collections::LinkedList; | |
37 | /// | |
38 | /// let list = LinkedList::from([1, 2, 3]); | |
39 | /// ``` | |
40 | /// | |
c295e0f8 | 41 | /// NOTE: It is almost always better to use [`Vec`] or [`VecDeque`] because |
60c5eb7d XL |
42 | /// array-based containers are generally faster, |
43 | /// more memory efficient, and make better use of CPU cache. | |
c295e0f8 XL |
44 | /// |
45 | /// [`Vec`]: crate::vec::Vec | |
46 | /// [`VecDeque`]: super::vec_deque::VecDeque | |
85aaf69f | 47 | #[stable(feature = "rust1", since = "1.0.0")] |
6a06907d | 48 | #[cfg_attr(not(test), rustc_diagnostic_item = "LinkedList")] |
94222f64 | 49 | #[rustc_insignificant_dtor] |
85aaf69f | 50 | pub struct LinkedList<T> { |
2c00a5a8 XL |
51 | head: Option<NonNull<Node<T>>>, |
52 | tail: Option<NonNull<Node<T>>>, | |
5bcae85e SL |
53 | len: usize, |
54 | marker: PhantomData<Box<Node<T>>>, | |
1a4d82fc JJ |
55 | } |
56 | ||
1a4d82fc | 57 | struct Node<T> { |
2c00a5a8 XL |
58 | next: Option<NonNull<Node<T>>>, |
59 | prev: Option<NonNull<Node<T>>>, | |
5bcae85e | 60 | element: T, |
1a4d82fc JJ |
61 | } |
62 | ||
cc61c64b XL |
63 | /// An iterator over the elements of a `LinkedList`. |
64 | /// | |
3dfed10e | 65 | /// This `struct` is created by [`LinkedList::iter()`]. See its |
cc61c64b | 66 | /// documentation for more. |
85aaf69f | 67 | #[stable(feature = "rust1", since = "1.0.0")] |
92a42be0 | 68 | pub struct Iter<'a, T: 'a> { |
2c00a5a8 XL |
69 | head: Option<NonNull<Node<T>>>, |
70 | tail: Option<NonNull<Node<T>>>, | |
5bcae85e SL |
71 | len: usize, |
72 | marker: PhantomData<&'a Node<T>>, | |
1a4d82fc JJ |
73 | } |
74 | ||
8bb4bdeb | 75 | #[stable(feature = "collection_debug", since = "1.17.0")] |
9fa01778 XL |
76 | impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> { |
77 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
17df50a5 XL |
78 | f.debug_tuple("Iter") |
79 | .field(&*mem::ManuallyDrop::new(LinkedList { | |
80 | head: self.head, | |
81 | tail: self.tail, | |
82 | len: self.len, | |
83 | marker: PhantomData, | |
84 | })) | |
85 | .field(&self.len) | |
86 | .finish() | |
8bb4bdeb XL |
87 | } |
88 | } | |
89 | ||
ea8adc8c | 90 | // FIXME(#26925) Remove in favor of `#[derive(Clone)]` |
85aaf69f | 91 | #[stable(feature = "rust1", since = "1.0.0")] |
9fa01778 | 92 | impl<T> Clone for Iter<'_, T> { |
5bcae85e SL |
93 | fn clone(&self) -> Self { |
94 | Iter { ..*self } | |
1a4d82fc JJ |
95 | } |
96 | } | |
97 | ||
cc61c64b XL |
98 | /// A mutable iterator over the elements of a `LinkedList`. |
99 | /// | |
3dfed10e | 100 | /// This `struct` is created by [`LinkedList::iter_mut()`]. See its |
cc61c64b | 101 | /// documentation for more. |
85aaf69f | 102 | #[stable(feature = "rust1", since = "1.0.0")] |
92a42be0 | 103 | pub struct IterMut<'a, T: 'a> { |
2c00a5a8 XL |
104 | head: Option<NonNull<Node<T>>>, |
105 | tail: Option<NonNull<Node<T>>>, | |
5bcae85e | 106 | len: usize, |
17df50a5 | 107 | marker: PhantomData<&'a mut Node<T>>, |
1a4d82fc JJ |
108 | } |
109 | ||
8bb4bdeb | 110 | #[stable(feature = "collection_debug", since = "1.17.0")] |
9fa01778 XL |
111 | impl<T: fmt::Debug> fmt::Debug for IterMut<'_, T> { |
112 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
17df50a5 XL |
113 | f.debug_tuple("IterMut") |
114 | .field(&*mem::ManuallyDrop::new(LinkedList { | |
115 | head: self.head, | |
116 | tail: self.tail, | |
117 | len: self.len, | |
118 | marker: PhantomData, | |
119 | })) | |
120 | .field(&self.len) | |
121 | .finish() | |
8bb4bdeb XL |
122 | } |
123 | } | |
124 | ||
cc61c64b XL |
125 | /// An owning iterator over the elements of a `LinkedList`. |
126 | /// | |
dfeec247 | 127 | /// This `struct` is created by the [`into_iter`] method on [`LinkedList`] |
c295e0f8 | 128 | /// (provided by the [`IntoIterator`] trait). See its documentation for more. |
cc61c64b | 129 | /// |
1b1a35ee | 130 | /// [`into_iter`]: LinkedList::into_iter |
c295e0f8 | 131 | /// [`IntoIterator`]: core::iter::IntoIterator |
1a4d82fc | 132 | #[derive(Clone)] |
85aaf69f | 133 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 134 | pub struct IntoIter<T> { |
92a42be0 | 135 | list: LinkedList<T>, |
1a4d82fc JJ |
136 | } |
137 | ||
8bb4bdeb XL |
138 | #[stable(feature = "collection_debug", since = "1.17.0")] |
139 | impl<T: fmt::Debug> fmt::Debug for IntoIter<T> { | |
9fa01778 | 140 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
dfeec247 | 141 | f.debug_tuple("IntoIter").field(&self.list).finish() |
8bb4bdeb XL |
142 | } |
143 | } | |
144 | ||
1a4d82fc | 145 | impl<T> Node<T> { |
5bcae85e | 146 | fn new(element: T) -> Self { |
dfeec247 | 147 | Node { next: None, prev: None, element } |
1a4d82fc | 148 | } |
62682a34 | 149 | |
5bcae85e SL |
150 | fn into_element(self: Box<Self>) -> T { |
151 | self.element | |
62682a34 | 152 | } |
1a4d82fc JJ |
153 | } |
154 | ||
1a4d82fc | 155 | // private methods |
85aaf69f | 156 | impl<T> LinkedList<T> { |
5bcae85e | 157 | /// Adds the given node to the front of the list. |
1a4d82fc | 158 | #[inline] |
5bcae85e | 159 | fn push_front_node(&mut self, mut node: Box<Node<T>>) { |
48663c56 XL |
160 | // This method takes care not to create mutable references to whole nodes, |
161 | // to maintain validity of aliasing pointers into `element`. | |
5bcae85e SL |
162 | unsafe { |
163 | node.next = self.head; | |
164 | node.prev = None; | |
f9f354fc | 165 | let node = Some(Box::leak(node).into()); |
5bcae85e SL |
166 | |
167 | match self.head { | |
168 | None => self.tail = node, | |
48663c56 XL |
169 | // Not creating new mutable (unique!) references overlapping `element`. |
170 | Some(head) => (*head.as_ptr()).prev = node, | |
1a4d82fc | 171 | } |
5bcae85e SL |
172 | |
173 | self.head = node; | |
174 | self.len += 1; | |
1a4d82fc | 175 | } |
1a4d82fc JJ |
176 | } |
177 | ||
5bcae85e | 178 | /// Removes and returns the node at the front of the list. |
1a4d82fc JJ |
179 | #[inline] |
180 | fn pop_front_node(&mut self) -> Option<Box<Node<T>>> { | |
48663c56 XL |
181 | // This method takes care not to create mutable references to whole nodes, |
182 | // to maintain validity of aliasing pointers into `element`. | |
5bcae85e | 183 | self.head.map(|node| unsafe { |
7cac9316 | 184 | let node = Box::from_raw(node.as_ptr()); |
5bcae85e SL |
185 | self.head = node.next; |
186 | ||
187 | match self.head { | |
188 | None => self.tail = None, | |
48663c56 XL |
189 | // Not creating new mutable (unique!) references overlapping `element`. |
190 | Some(head) => (*head.as_ptr()).prev = None, | |
1a4d82fc | 191 | } |
5bcae85e SL |
192 | |
193 | self.len -= 1; | |
194 | node | |
1a4d82fc JJ |
195 | }) |
196 | } | |
197 | ||
5bcae85e | 198 | /// Adds the given node to the back of the list. |
1a4d82fc | 199 | #[inline] |
5bcae85e | 200 | fn push_back_node(&mut self, mut node: Box<Node<T>>) { |
48663c56 XL |
201 | // This method takes care not to create mutable references to whole nodes, |
202 | // to maintain validity of aliasing pointers into `element`. | |
5bcae85e SL |
203 | unsafe { |
204 | node.next = None; | |
205 | node.prev = self.tail; | |
f9f354fc | 206 | let node = Some(Box::leak(node).into()); |
5bcae85e SL |
207 | |
208 | match self.tail { | |
209 | None => self.head = node, | |
48663c56 XL |
210 | // Not creating new mutable (unique!) references overlapping `element`. |
211 | Some(tail) => (*tail.as_ptr()).next = node, | |
1a4d82fc | 212 | } |
5bcae85e SL |
213 | |
214 | self.tail = node; | |
215 | self.len += 1; | |
1a4d82fc | 216 | } |
1a4d82fc JJ |
217 | } |
218 | ||
5bcae85e | 219 | /// Removes and returns the node at the back of the list. |
1a4d82fc JJ |
220 | #[inline] |
221 | fn pop_back_node(&mut self) -> Option<Box<Node<T>>> { | |
48663c56 XL |
222 | // This method takes care not to create mutable references to whole nodes, |
223 | // to maintain validity of aliasing pointers into `element`. | |
5bcae85e | 224 | self.tail.map(|node| unsafe { |
7cac9316 | 225 | let node = Box::from_raw(node.as_ptr()); |
5bcae85e SL |
226 | self.tail = node.prev; |
227 | ||
228 | match self.tail { | |
229 | None => self.head = None, | |
48663c56 XL |
230 | // Not creating new mutable (unique!) references overlapping `element`. |
231 | Some(tail) => (*tail.as_ptr()).next = None, | |
5bcae85e SL |
232 | } |
233 | ||
234 | self.len -= 1; | |
235 | node | |
236 | }) | |
1a4d82fc | 237 | } |
ff7c6d11 XL |
238 | |
239 | /// Unlinks the specified node from the current list. | |
240 | /// | |
241 | /// Warning: this will not check that the provided node belongs to the current list. | |
48663c56 XL |
242 | /// |
243 | /// This method takes care not to create mutable references to `element`, to | |
244 | /// maintain validity of aliasing pointers. | |
ff7c6d11 | 245 | #[inline] |
2c00a5a8 | 246 | unsafe fn unlink_node(&mut self, mut node: NonNull<Node<T>>) { |
f035d41b | 247 | let node = unsafe { node.as_mut() }; // this one is ours now, we can create an &mut. |
ff7c6d11 | 248 | |
48663c56 | 249 | // Not creating new mutable (unique!) references overlapping `element`. |
ff7c6d11 | 250 | match node.prev { |
f035d41b | 251 | Some(prev) => unsafe { (*prev.as_ptr()).next = node.next }, |
ff7c6d11 | 252 | // this node is the head node |
416331ca | 253 | None => self.head = node.next, |
ff7c6d11 XL |
254 | }; |
255 | ||
256 | match node.next { | |
f035d41b | 257 | Some(next) => unsafe { (*next.as_ptr()).prev = node.prev }, |
ff7c6d11 | 258 | // this node is the tail node |
416331ca | 259 | None => self.tail = node.prev, |
ff7c6d11 XL |
260 | }; |
261 | ||
262 | self.len -= 1; | |
263 | } | |
dfeec247 XL |
264 | |
265 | /// Splices a series of nodes between two existing nodes. | |
266 | /// | |
267 | /// Warning: this will not check that the provided node belongs to the two existing lists. | |
268 | #[inline] | |
269 | unsafe fn splice_nodes( | |
270 | &mut self, | |
271 | existing_prev: Option<NonNull<Node<T>>>, | |
272 | existing_next: Option<NonNull<Node<T>>>, | |
273 | mut splice_start: NonNull<Node<T>>, | |
274 | mut splice_end: NonNull<Node<T>>, | |
275 | splice_length: usize, | |
276 | ) { | |
277 | // This method takes care not to create multiple mutable references to whole nodes at the same time, | |
278 | // to maintain validity of aliasing pointers into `element`. | |
279 | if let Some(mut existing_prev) = existing_prev { | |
f035d41b XL |
280 | unsafe { |
281 | existing_prev.as_mut().next = Some(splice_start); | |
282 | } | |
dfeec247 XL |
283 | } else { |
284 | self.head = Some(splice_start); | |
285 | } | |
286 | if let Some(mut existing_next) = existing_next { | |
f035d41b XL |
287 | unsafe { |
288 | existing_next.as_mut().prev = Some(splice_end); | |
289 | } | |
dfeec247 XL |
290 | } else { |
291 | self.tail = Some(splice_end); | |
292 | } | |
f035d41b XL |
293 | unsafe { |
294 | splice_start.as_mut().prev = existing_prev; | |
295 | splice_end.as_mut().next = existing_next; | |
296 | } | |
dfeec247 XL |
297 | |
298 | self.len += splice_length; | |
299 | } | |
300 | ||
301 | /// Detaches all nodes from a linked list as a series of nodes. | |
302 | #[inline] | |
303 | fn detach_all_nodes(mut self) -> Option<(NonNull<Node<T>>, NonNull<Node<T>>, usize)> { | |
304 | let head = self.head.take(); | |
305 | let tail = self.tail.take(); | |
306 | let len = mem::replace(&mut self.len, 0); | |
307 | if let Some(head) = head { | |
94222f64 XL |
308 | // SAFETY: In a LinkedList, either both the head and tail are None because |
309 | // the list is empty, or both head and tail are Some because the list is populated. | |
310 | // Since we have verified the head is Some, we are sure the tail is Some too. | |
311 | let tail = unsafe { tail.unwrap_unchecked() }; | |
dfeec247 XL |
312 | Some((head, tail, len)) |
313 | } else { | |
314 | None | |
315 | } | |
316 | } | |
317 | ||
318 | #[inline] | |
319 | unsafe fn split_off_before_node( | |
320 | &mut self, | |
321 | split_node: Option<NonNull<Node<T>>>, | |
322 | at: usize, | |
323 | ) -> Self { | |
324 | // The split node is the new head node of the second part | |
325 | if let Some(mut split_node) = split_node { | |
326 | let first_part_head; | |
327 | let first_part_tail; | |
f035d41b XL |
328 | unsafe { |
329 | first_part_tail = split_node.as_mut().prev.take(); | |
330 | } | |
dfeec247 | 331 | if let Some(mut tail) = first_part_tail { |
f035d41b XL |
332 | unsafe { |
333 | tail.as_mut().next = None; | |
334 | } | |
dfeec247 XL |
335 | first_part_head = self.head; |
336 | } else { | |
337 | first_part_head = None; | |
338 | } | |
339 | ||
340 | let first_part = LinkedList { | |
341 | head: first_part_head, | |
342 | tail: first_part_tail, | |
343 | len: at, | |
344 | marker: PhantomData, | |
345 | }; | |
346 | ||
347 | // Fix the head ptr of the second part | |
348 | self.head = Some(split_node); | |
349 | self.len = self.len - at; | |
350 | ||
351 | first_part | |
352 | } else { | |
353 | mem::replace(self, LinkedList::new()) | |
354 | } | |
355 | } | |
356 | ||
357 | #[inline] | |
358 | unsafe fn split_off_after_node( | |
359 | &mut self, | |
360 | split_node: Option<NonNull<Node<T>>>, | |
361 | at: usize, | |
362 | ) -> Self { | |
363 | // The split node is the new tail node of the first part and owns | |
364 | // the head of the second part. | |
365 | if let Some(mut split_node) = split_node { | |
366 | let second_part_head; | |
367 | let second_part_tail; | |
f035d41b XL |
368 | unsafe { |
369 | second_part_head = split_node.as_mut().next.take(); | |
370 | } | |
dfeec247 | 371 | if let Some(mut head) = second_part_head { |
f035d41b XL |
372 | unsafe { |
373 | head.as_mut().prev = None; | |
374 | } | |
dfeec247 XL |
375 | second_part_tail = self.tail; |
376 | } else { | |
377 | second_part_tail = None; | |
378 | } | |
379 | ||
380 | let second_part = LinkedList { | |
381 | head: second_part_head, | |
382 | tail: second_part_tail, | |
383 | len: self.len - at, | |
384 | marker: PhantomData, | |
385 | }; | |
386 | ||
387 | // Fix the tail ptr of the first part | |
388 | self.tail = Some(split_node); | |
389 | self.len = at; | |
390 | ||
391 | second_part | |
392 | } else { | |
393 | mem::replace(self, LinkedList::new()) | |
394 | } | |
395 | } | |
1a4d82fc JJ |
396 | } |
397 | ||
85aaf69f SL |
398 | #[stable(feature = "rust1", since = "1.0.0")] |
399 | impl<T> Default for LinkedList<T> { | |
9e0c209e | 400 | /// Creates an empty `LinkedList<T>`. |
1a4d82fc | 401 | #[inline] |
5bcae85e SL |
402 | fn default() -> Self { |
403 | Self::new() | |
92a42be0 | 404 | } |
1a4d82fc JJ |
405 | } |
406 | ||
85aaf69f SL |
407 | impl<T> LinkedList<T> { |
408 | /// Creates an empty `LinkedList`. | |
5bcae85e SL |
409 | /// |
410 | /// # Examples | |
411 | /// | |
412 | /// ``` | |
413 | /// use std::collections::LinkedList; | |
414 | /// | |
415 | /// let list: LinkedList<u32> = LinkedList::new(); | |
416 | /// ``` | |
1a4d82fc | 417 | #[inline] |
dfeec247 | 418 | #[rustc_const_stable(feature = "const_linked_list_new", since = "1.32.0")] |
85aaf69f | 419 | #[stable(feature = "rust1", since = "1.0.0")] |
c295e0f8 | 420 | #[must_use] |
e1599b0c | 421 | pub const fn new() -> Self { |
dfeec247 | 422 | LinkedList { head: None, tail: None, len: 0, marker: PhantomData } |
1a4d82fc JJ |
423 | } |
424 | ||
85aaf69f | 425 | /// Moves all elements from `other` to the end of the list. |
1a4d82fc | 426 | /// |
85aaf69f SL |
427 | /// This reuses all the nodes from `other` and moves them into `self`. After |
428 | /// this operation, `other` becomes empty. | |
429 | /// | |
3dfed10e | 430 | /// This operation should compute in *O*(1) time and *O*(1) memory. |
1a4d82fc JJ |
431 | /// |
432 | /// # Examples | |
433 | /// | |
85aaf69f SL |
434 | /// ``` |
435 | /// use std::collections::LinkedList; | |
1a4d82fc | 436 | /// |
5bcae85e SL |
437 | /// let mut list1 = LinkedList::new(); |
438 | /// list1.push_back('a'); | |
1a4d82fc | 439 | /// |
5bcae85e SL |
440 | /// let mut list2 = LinkedList::new(); |
441 | /// list2.push_back('b'); | |
442 | /// list2.push_back('c'); | |
1a4d82fc | 443 | /// |
5bcae85e SL |
444 | /// list1.append(&mut list2); |
445 | /// | |
446 | /// let mut iter = list1.iter(); | |
447 | /// assert_eq!(iter.next(), Some(&'a')); | |
448 | /// assert_eq!(iter.next(), Some(&'b')); | |
449 | /// assert_eq!(iter.next(), Some(&'c')); | |
450 | /// assert!(iter.next().is_none()); | |
451 | /// | |
452 | /// assert!(list2.is_empty()); | |
1a4d82fc | 453 | /// ``` |
c34b1796 | 454 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e SL |
455 | pub fn append(&mut self, other: &mut Self) { |
456 | match self.tail { | |
457 | None => mem::swap(self, other), | |
7cac9316 | 458 | Some(mut tail) => { |
48663c56 XL |
459 | // `as_mut` is okay here because we have exclusive access to the entirety |
460 | // of both lists. | |
7cac9316 | 461 | if let Some(mut other_head) = other.head.take() { |
32a655c1 | 462 | unsafe { |
7cac9316 XL |
463 | tail.as_mut().next = Some(other_head); |
464 | other_head.as_mut().prev = Some(tail); | |
32a655c1 | 465 | } |
5bcae85e | 466 | |
32a655c1 SL |
467 | self.tail = other.tail.take(); |
468 | self.len += mem::replace(&mut other.len, 0); | |
469 | } | |
470 | } | |
1a4d82fc JJ |
471 | } |
472 | } | |
473 | ||
474 | /// Provides a forward iterator. | |
5bcae85e SL |
475 | /// |
476 | /// # Examples | |
477 | /// | |
478 | /// ``` | |
479 | /// use std::collections::LinkedList; | |
480 | /// | |
481 | /// let mut list: LinkedList<u32> = LinkedList::new(); | |
482 | /// | |
483 | /// list.push_back(0); | |
484 | /// list.push_back(1); | |
485 | /// list.push_back(2); | |
486 | /// | |
487 | /// let mut iter = list.iter(); | |
488 | /// assert_eq!(iter.next(), Some(&0)); | |
489 | /// assert_eq!(iter.next(), Some(&1)); | |
490 | /// assert_eq!(iter.next(), Some(&2)); | |
491 | /// assert_eq!(iter.next(), None); | |
492 | /// ``` | |
1a4d82fc | 493 | #[inline] |
85aaf69f | 494 | #[stable(feature = "rust1", since = "1.0.0")] |
9fa01778 | 495 | pub fn iter(&self) -> Iter<'_, T> { |
dfeec247 | 496 | Iter { head: self.head, tail: self.tail, len: self.len, marker: PhantomData } |
1a4d82fc JJ |
497 | } |
498 | ||
499 | /// Provides a forward iterator with mutable references. | |
5bcae85e SL |
500 | /// |
501 | /// # Examples | |
502 | /// | |
503 | /// ``` | |
504 | /// use std::collections::LinkedList; | |
505 | /// | |
506 | /// let mut list: LinkedList<u32> = LinkedList::new(); | |
507 | /// | |
508 | /// list.push_back(0); | |
509 | /// list.push_back(1); | |
510 | /// list.push_back(2); | |
511 | /// | |
512 | /// for element in list.iter_mut() { | |
513 | /// *element += 10; | |
514 | /// } | |
515 | /// | |
516 | /// let mut iter = list.iter(); | |
517 | /// assert_eq!(iter.next(), Some(&10)); | |
518 | /// assert_eq!(iter.next(), Some(&11)); | |
519 | /// assert_eq!(iter.next(), Some(&12)); | |
520 | /// assert_eq!(iter.next(), None); | |
521 | /// ``` | |
1a4d82fc | 522 | #[inline] |
85aaf69f | 523 | #[stable(feature = "rust1", since = "1.0.0")] |
9fa01778 | 524 | pub fn iter_mut(&mut self) -> IterMut<'_, T> { |
17df50a5 | 525 | IterMut { head: self.head, tail: self.tail, len: self.len, marker: PhantomData } |
dfeec247 XL |
526 | } |
527 | ||
528 | /// Provides a cursor at the front element. | |
529 | /// | |
530 | /// The cursor is pointing to the "ghost" non-element if the list is empty. | |
531 | #[inline] | |
532 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
533 | pub fn cursor_front(&self) -> Cursor<'_, T> { | |
534 | Cursor { index: 0, current: self.head, list: self } | |
535 | } | |
536 | ||
537 | /// Provides a cursor with editing operations at the front element. | |
538 | /// | |
539 | /// The cursor is pointing to the "ghost" non-element if the list is empty. | |
540 | #[inline] | |
541 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
542 | pub fn cursor_front_mut(&mut self) -> CursorMut<'_, T> { | |
543 | CursorMut { index: 0, current: self.head, list: self } | |
544 | } | |
545 | ||
546 | /// Provides a cursor at the back element. | |
547 | /// | |
548 | /// The cursor is pointing to the "ghost" non-element if the list is empty. | |
549 | #[inline] | |
550 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
551 | pub fn cursor_back(&self) -> Cursor<'_, T> { | |
552 | Cursor { index: self.len.checked_sub(1).unwrap_or(0), current: self.tail, list: self } | |
553 | } | |
554 | ||
555 | /// Provides a cursor with editing operations at the back element. | |
556 | /// | |
557 | /// The cursor is pointing to the "ghost" non-element if the list is empty. | |
558 | #[inline] | |
559 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
560 | pub fn cursor_back_mut(&mut self) -> CursorMut<'_, T> { | |
561 | CursorMut { index: self.len.checked_sub(1).unwrap_or(0), current: self.tail, list: self } | |
1a4d82fc JJ |
562 | } |
563 | ||
85aaf69f | 564 | /// Returns `true` if the `LinkedList` is empty. |
1a4d82fc | 565 | /// |
3dfed10e | 566 | /// This operation should compute in *O*(1) time. |
85aaf69f SL |
567 | /// |
568 | /// # Examples | |
569 | /// | |
570 | /// ``` | |
571 | /// use std::collections::LinkedList; | |
572 | /// | |
573 | /// let mut dl = LinkedList::new(); | |
574 | /// assert!(dl.is_empty()); | |
575 | /// | |
576 | /// dl.push_front("foo"); | |
577 | /// assert!(!dl.is_empty()); | |
578 | /// ``` | |
1a4d82fc | 579 | #[inline] |
85aaf69f | 580 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 581 | pub fn is_empty(&self) -> bool { |
5bcae85e | 582 | self.head.is_none() |
1a4d82fc JJ |
583 | } |
584 | ||
85aaf69f | 585 | /// Returns the length of the `LinkedList`. |
1a4d82fc | 586 | /// |
3dfed10e | 587 | /// This operation should compute in *O*(1) time. |
85aaf69f SL |
588 | /// |
589 | /// # Examples | |
590 | /// | |
591 | /// ``` | |
592 | /// use std::collections::LinkedList; | |
593 | /// | |
594 | /// let mut dl = LinkedList::new(); | |
595 | /// | |
596 | /// dl.push_front(2); | |
597 | /// assert_eq!(dl.len(), 1); | |
598 | /// | |
599 | /// dl.push_front(1); | |
600 | /// assert_eq!(dl.len(), 2); | |
601 | /// | |
602 | /// dl.push_back(3); | |
603 | /// assert_eq!(dl.len(), 3); | |
85aaf69f | 604 | /// ``` |
1a4d82fc | 605 | #[inline] |
85aaf69f SL |
606 | #[stable(feature = "rust1", since = "1.0.0")] |
607 | pub fn len(&self) -> usize { | |
5bcae85e | 608 | self.len |
1a4d82fc JJ |
609 | } |
610 | ||
85aaf69f | 611 | /// Removes all elements from the `LinkedList`. |
1a4d82fc | 612 | /// |
3dfed10e | 613 | /// This operation should compute in *O*(*n*) time. |
85aaf69f SL |
614 | /// |
615 | /// # Examples | |
616 | /// | |
617 | /// ``` | |
618 | /// use std::collections::LinkedList; | |
619 | /// | |
620 | /// let mut dl = LinkedList::new(); | |
621 | /// | |
622 | /// dl.push_front(2); | |
623 | /// dl.push_front(1); | |
624 | /// assert_eq!(dl.len(), 2); | |
625 | /// assert_eq!(dl.front(), Some(&1)); | |
626 | /// | |
627 | /// dl.clear(); | |
628 | /// assert_eq!(dl.len(), 0); | |
629 | /// assert_eq!(dl.front(), None); | |
85aaf69f | 630 | /// ``` |
1a4d82fc | 631 | #[inline] |
85aaf69f | 632 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 633 | pub fn clear(&mut self) { |
5bcae85e | 634 | *self = Self::new(); |
1a4d82fc JJ |
635 | } |
636 | ||
a7813a04 XL |
637 | /// Returns `true` if the `LinkedList` contains an element equal to the |
638 | /// given value. | |
5bcae85e | 639 | /// |
c295e0f8 XL |
640 | /// This operation should compute in *O*(*n*) time. |
641 | /// | |
5bcae85e SL |
642 | /// # Examples |
643 | /// | |
644 | /// ``` | |
645 | /// use std::collections::LinkedList; | |
646 | /// | |
647 | /// let mut list: LinkedList<u32> = LinkedList::new(); | |
648 | /// | |
649 | /// list.push_back(0); | |
650 | /// list.push_back(1); | |
651 | /// list.push_back(2); | |
652 | /// | |
653 | /// assert_eq!(list.contains(&0), true); | |
654 | /// assert_eq!(list.contains(&10), false); | |
655 | /// ``` | |
656 | #[stable(feature = "linked_list_contains", since = "1.12.0")] | |
a7813a04 | 657 | pub fn contains(&self, x: &T) -> bool |
dfeec247 XL |
658 | where |
659 | T: PartialEq<T>, | |
a7813a04 XL |
660 | { |
661 | self.iter().any(|e| e == x) | |
662 | } | |
663 | ||
1a4d82fc JJ |
664 | /// Provides a reference to the front element, or `None` if the list is |
665 | /// empty. | |
85aaf69f | 666 | /// |
c295e0f8 XL |
667 | /// This operation should compute in *O*(1) time. |
668 | /// | |
85aaf69f SL |
669 | /// # Examples |
670 | /// | |
671 | /// ``` | |
672 | /// use std::collections::LinkedList; | |
673 | /// | |
674 | /// let mut dl = LinkedList::new(); | |
675 | /// assert_eq!(dl.front(), None); | |
676 | /// | |
677 | /// dl.push_front(1); | |
678 | /// assert_eq!(dl.front(), Some(&1)); | |
85aaf69f | 679 | /// ``` |
1a4d82fc | 680 | #[inline] |
85aaf69f | 681 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 682 | pub fn front(&self) -> Option<&T> { |
dfeec247 | 683 | unsafe { self.head.as_ref().map(|node| &node.as_ref().element) } |
1a4d82fc JJ |
684 | } |
685 | ||
686 | /// Provides a mutable reference to the front element, or `None` if the list | |
687 | /// is empty. | |
85aaf69f | 688 | /// |
c295e0f8 XL |
689 | /// This operation should compute in *O*(1) time. |
690 | /// | |
85aaf69f SL |
691 | /// # Examples |
692 | /// | |
693 | /// ``` | |
694 | /// use std::collections::LinkedList; | |
695 | /// | |
696 | /// let mut dl = LinkedList::new(); | |
697 | /// assert_eq!(dl.front(), None); | |
698 | /// | |
699 | /// dl.push_front(1); | |
700 | /// assert_eq!(dl.front(), Some(&1)); | |
701 | /// | |
702 | /// match dl.front_mut() { | |
703 | /// None => {}, | |
704 | /// Some(x) => *x = 5, | |
705 | /// } | |
706 | /// assert_eq!(dl.front(), Some(&5)); | |
85aaf69f | 707 | /// ``` |
1a4d82fc | 708 | #[inline] |
85aaf69f | 709 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 710 | pub fn front_mut(&mut self) -> Option<&mut T> { |
dfeec247 | 711 | unsafe { self.head.as_mut().map(|node| &mut node.as_mut().element) } |
1a4d82fc JJ |
712 | } |
713 | ||
714 | /// Provides a reference to the back element, or `None` if the list is | |
715 | /// empty. | |
85aaf69f | 716 | /// |
c295e0f8 XL |
717 | /// This operation should compute in *O*(1) time. |
718 | /// | |
85aaf69f SL |
719 | /// # Examples |
720 | /// | |
721 | /// ``` | |
722 | /// use std::collections::LinkedList; | |
723 | /// | |
724 | /// let mut dl = LinkedList::new(); | |
725 | /// assert_eq!(dl.back(), None); | |
726 | /// | |
727 | /// dl.push_back(1); | |
728 | /// assert_eq!(dl.back(), Some(&1)); | |
85aaf69f | 729 | /// ``` |
1a4d82fc | 730 | #[inline] |
85aaf69f | 731 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 732 | pub fn back(&self) -> Option<&T> { |
dfeec247 | 733 | unsafe { self.tail.as_ref().map(|node| &node.as_ref().element) } |
1a4d82fc JJ |
734 | } |
735 | ||
736 | /// Provides a mutable reference to the back element, or `None` if the list | |
737 | /// is empty. | |
85aaf69f | 738 | /// |
c295e0f8 XL |
739 | /// This operation should compute in *O*(1) time. |
740 | /// | |
85aaf69f SL |
741 | /// # Examples |
742 | /// | |
743 | /// ``` | |
744 | /// use std::collections::LinkedList; | |
745 | /// | |
746 | /// let mut dl = LinkedList::new(); | |
747 | /// assert_eq!(dl.back(), None); | |
748 | /// | |
749 | /// dl.push_back(1); | |
750 | /// assert_eq!(dl.back(), Some(&1)); | |
751 | /// | |
752 | /// match dl.back_mut() { | |
753 | /// None => {}, | |
754 | /// Some(x) => *x = 5, | |
755 | /// } | |
756 | /// assert_eq!(dl.back(), Some(&5)); | |
85aaf69f | 757 | /// ``` |
1a4d82fc | 758 | #[inline] |
85aaf69f | 759 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 760 | pub fn back_mut(&mut self) -> Option<&mut T> { |
dfeec247 | 761 | unsafe { self.tail.as_mut().map(|node| &mut node.as_mut().element) } |
1a4d82fc JJ |
762 | } |
763 | ||
764 | /// Adds an element first in the list. | |
765 | /// | |
3dfed10e | 766 | /// This operation should compute in *O*(1) time. |
85aaf69f SL |
767 | /// |
768 | /// # Examples | |
769 | /// | |
770 | /// ``` | |
771 | /// use std::collections::LinkedList; | |
772 | /// | |
773 | /// let mut dl = LinkedList::new(); | |
774 | /// | |
775 | /// dl.push_front(2); | |
776 | /// assert_eq!(dl.front().unwrap(), &2); | |
777 | /// | |
778 | /// dl.push_front(1); | |
779 | /// assert_eq!(dl.front().unwrap(), &1); | |
85aaf69f SL |
780 | /// ``` |
781 | #[stable(feature = "rust1", since = "1.0.0")] | |
1a4d82fc | 782 | pub fn push_front(&mut self, elt: T) { |
5bcae85e | 783 | self.push_front_node(box Node::new(elt)); |
1a4d82fc JJ |
784 | } |
785 | ||
786 | /// Removes the first element and returns it, or `None` if the list is | |
787 | /// empty. | |
788 | /// | |
3dfed10e | 789 | /// This operation should compute in *O*(1) time. |
85aaf69f SL |
790 | /// |
791 | /// # Examples | |
792 | /// | |
793 | /// ``` | |
794 | /// use std::collections::LinkedList; | |
795 | /// | |
796 | /// let mut d = LinkedList::new(); | |
797 | /// assert_eq!(d.pop_front(), None); | |
798 | /// | |
799 | /// d.push_front(1); | |
800 | /// d.push_front(3); | |
801 | /// assert_eq!(d.pop_front(), Some(3)); | |
802 | /// assert_eq!(d.pop_front(), Some(1)); | |
803 | /// assert_eq!(d.pop_front(), None); | |
85aaf69f | 804 | /// ``` |
85aaf69f | 805 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 806 | pub fn pop_front(&mut self) -> Option<T> { |
5bcae85e | 807 | self.pop_front_node().map(Node::into_element) |
1a4d82fc JJ |
808 | } |
809 | ||
0731742a XL |
810 | /// Appends an element to the back of a list. |
811 | /// | |
3dfed10e | 812 | /// This operation should compute in *O*(1) time. |
1a4d82fc JJ |
813 | /// |
814 | /// # Examples | |
815 | /// | |
85aaf69f SL |
816 | /// ``` |
817 | /// use std::collections::LinkedList; | |
1a4d82fc | 818 | /// |
85aaf69f SL |
819 | /// let mut d = LinkedList::new(); |
820 | /// d.push_back(1); | |
1a4d82fc JJ |
821 | /// d.push_back(3); |
822 | /// assert_eq!(3, *d.back().unwrap()); | |
823 | /// ``` | |
85aaf69f | 824 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 825 | pub fn push_back(&mut self, elt: T) { |
5bcae85e | 826 | self.push_back_node(box Node::new(elt)); |
1a4d82fc JJ |
827 | } |
828 | ||
829 | /// Removes the last element from a list and returns it, or `None` if | |
830 | /// it is empty. | |
831 | /// | |
3dfed10e | 832 | /// This operation should compute in *O*(1) time. |
0731742a | 833 | /// |
1a4d82fc JJ |
834 | /// # Examples |
835 | /// | |
85aaf69f SL |
836 | /// ``` |
837 | /// use std::collections::LinkedList; | |
1a4d82fc | 838 | /// |
85aaf69f | 839 | /// let mut d = LinkedList::new(); |
1a4d82fc | 840 | /// assert_eq!(d.pop_back(), None); |
85aaf69f | 841 | /// d.push_back(1); |
1a4d82fc JJ |
842 | /// d.push_back(3); |
843 | /// assert_eq!(d.pop_back(), Some(3)); | |
844 | /// ``` | |
85aaf69f | 845 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 846 | pub fn pop_back(&mut self) -> Option<T> { |
5bcae85e | 847 | self.pop_back_node().map(Node::into_element) |
1a4d82fc | 848 | } |
85aaf69f SL |
849 | |
850 | /// Splits the list into two at the given index. Returns everything after the given index, | |
851 | /// including the index. | |
852 | /// | |
3dfed10e | 853 | /// This operation should compute in *O*(*n*) time. |
cc61c64b | 854 | /// |
85aaf69f SL |
855 | /// # Panics |
856 | /// | |
857 | /// Panics if `at > len`. | |
858 | /// | |
85aaf69f SL |
859 | /// # Examples |
860 | /// | |
861 | /// ``` | |
862 | /// use std::collections::LinkedList; | |
863 | /// | |
864 | /// let mut d = LinkedList::new(); | |
865 | /// | |
866 | /// d.push_front(1); | |
867 | /// d.push_front(2); | |
868 | /// d.push_front(3); | |
869 | /// | |
74b04a01 | 870 | /// let mut split = d.split_off(2); |
85aaf69f | 871 | /// |
74b04a01 XL |
872 | /// assert_eq!(split.pop_front(), Some(1)); |
873 | /// assert_eq!(split.pop_front(), None); | |
85aaf69f SL |
874 | /// ``` |
875 | #[stable(feature = "rust1", since = "1.0.0")] | |
876 | pub fn split_off(&mut self, at: usize) -> LinkedList<T> { | |
877 | let len = self.len(); | |
878 | assert!(at <= len, "Cannot split off at a nonexistent index"); | |
879 | if at == 0 { | |
416331ca | 880 | return mem::take(self); |
85aaf69f | 881 | } else if at == len { |
5bcae85e | 882 | return Self::new(); |
85aaf69f SL |
883 | } |
884 | ||
885 | // Below, we iterate towards the `i-1`th node, either from the start or the end, | |
886 | // depending on which would be faster. | |
5bcae85e | 887 | let split_node = if at - 1 <= len - 1 - (at - 1) { |
85aaf69f SL |
888 | let mut iter = self.iter_mut(); |
889 | // instead of skipping using .skip() (which creates a new struct), | |
890 | // we skip manually so we can access the head field without | |
891 | // depending on implementation details of Skip | |
892 | for _ in 0..at - 1 { | |
893 | iter.next(); | |
894 | } | |
895 | iter.head | |
92a42be0 | 896 | } else { |
85aaf69f SL |
897 | // better off starting from the end |
898 | let mut iter = self.iter_mut(); | |
899 | for _ in 0..len - 1 - (at - 1) { | |
900 | iter.next_back(); | |
901 | } | |
902 | iter.tail | |
903 | }; | |
dfeec247 | 904 | unsafe { self.split_off_after_node(split_node, at) } |
85aaf69f | 905 | } |
7453a54e | 906 | |
74b04a01 XL |
907 | /// Removes the element at the given index and returns it. |
908 | /// | |
3dfed10e | 909 | /// This operation should compute in *O*(*n*) time. |
74b04a01 XL |
910 | /// |
911 | /// # Panics | |
912 | /// Panics if at >= len | |
913 | /// | |
914 | /// # Examples | |
915 | /// | |
916 | /// ``` | |
917 | /// #![feature(linked_list_remove)] | |
918 | /// use std::collections::LinkedList; | |
919 | /// | |
920 | /// let mut d = LinkedList::new(); | |
921 | /// | |
922 | /// d.push_front(1); | |
923 | /// d.push_front(2); | |
924 | /// d.push_front(3); | |
925 | /// | |
926 | /// assert_eq!(d.remove(1), 2); | |
927 | /// assert_eq!(d.remove(0), 3); | |
928 | /// assert_eq!(d.remove(0), 1); | |
929 | /// ``` | |
930 | #[unstable(feature = "linked_list_remove", issue = "69210")] | |
931 | pub fn remove(&mut self, at: usize) -> T { | |
932 | let len = self.len(); | |
933 | assert!(at < len, "Cannot remove at an index outside of the list bounds"); | |
934 | ||
935 | // Below, we iterate towards the node at the given index, either from | |
936 | // the start or the end, depending on which would be faster. | |
937 | let offset_from_end = len - at - 1; | |
938 | if at <= offset_from_end { | |
939 | let mut cursor = self.cursor_front_mut(); | |
940 | for _ in 0..at { | |
941 | cursor.move_next(); | |
942 | } | |
943 | cursor.remove_current().unwrap() | |
944 | } else { | |
945 | let mut cursor = self.cursor_back_mut(); | |
946 | for _ in 0..offset_from_end { | |
947 | cursor.move_prev(); | |
948 | } | |
949 | cursor.remove_current().unwrap() | |
950 | } | |
951 | } | |
952 | ||
ff7c6d11 XL |
953 | /// Creates an iterator which uses a closure to determine if an element should be removed. |
954 | /// | |
955 | /// If the closure returns true, then the element is removed and yielded. | |
0531ce1d XL |
956 | /// If the closure returns false, the element will remain in the list and will not be yielded |
957 | /// by the iterator. | |
ff7c6d11 XL |
958 | /// |
959 | /// Note that `drain_filter` lets you mutate every element in the filter closure, regardless of | |
960 | /// whether you choose to keep or remove it. | |
961 | /// | |
962 | /// # Examples | |
963 | /// | |
964 | /// Splitting a list into evens and odds, reusing the original list: | |
965 | /// | |
966 | /// ``` | |
967 | /// #![feature(drain_filter)] | |
968 | /// use std::collections::LinkedList; | |
969 | /// | |
970 | /// let mut numbers: LinkedList<u32> = LinkedList::new(); | |
971 | /// numbers.extend(&[1, 2, 3, 4, 5, 6, 8, 9, 11, 13, 14, 15]); | |
972 | /// | |
973 | /// let evens = numbers.drain_filter(|x| *x % 2 == 0).collect::<LinkedList<_>>(); | |
974 | /// let odds = numbers; | |
975 | /// | |
976 | /// assert_eq!(evens.into_iter().collect::<Vec<_>>(), vec![2, 4, 6, 8, 14]); | |
977 | /// assert_eq!(odds.into_iter().collect::<Vec<_>>(), vec![1, 3, 5, 9, 11, 13, 15]); | |
978 | /// ``` | |
979 | #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")] | |
9fa01778 | 980 | pub fn drain_filter<F>(&mut self, filter: F) -> DrainFilter<'_, T, F> |
dfeec247 XL |
981 | where |
982 | F: FnMut(&mut T) -> bool, | |
ff7c6d11 XL |
983 | { |
984 | // avoid borrow issues. | |
985 | let it = self.head; | |
986 | let old_len = self.len; | |
987 | ||
74b04a01 | 988 | DrainFilter { list: self, it, pred: filter, idx: 0, old_len } |
ff7c6d11 | 989 | } |
1a4d82fc JJ |
990 | } |
991 | ||
85aaf69f | 992 | #[stable(feature = "rust1", since = "1.0.0")] |
32a655c1 | 993 | unsafe impl<#[may_dangle] T> Drop for LinkedList<T> { |
1a4d82fc | 994 | fn drop(&mut self) { |
60c5eb7d XL |
995 | struct DropGuard<'a, T>(&'a mut LinkedList<T>); |
996 | ||
997 | impl<'a, T> Drop for DropGuard<'a, T> { | |
998 | fn drop(&mut self) { | |
999 | // Continue the same loop we do below. This only runs when a destructor has | |
1000 | // panicked. If another one panics this will abort. | |
f9f354fc | 1001 | while self.0.pop_front_node().is_some() {} |
60c5eb7d XL |
1002 | } |
1003 | } | |
1004 | ||
1005 | while let Some(node) = self.pop_front_node() { | |
1006 | let guard = DropGuard(self); | |
1007 | drop(node); | |
1008 | mem::forget(guard); | |
1009 | } | |
1a4d82fc JJ |
1010 | } |
1011 | } | |
1012 | ||
85aaf69f | 1013 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e SL |
1014 | impl<'a, T> Iterator for Iter<'a, T> { |
1015 | type Item = &'a T; | |
1a4d82fc JJ |
1016 | |
1017 | #[inline] | |
5bcae85e SL |
1018 | fn next(&mut self) -> Option<&'a T> { |
1019 | if self.len == 0 { | |
1020 | None | |
1021 | } else { | |
1022 | self.head.map(|node| unsafe { | |
7cac9316 XL |
1023 | // Need an unbound lifetime to get 'a |
1024 | let node = &*node.as_ptr(); | |
5bcae85e SL |
1025 | self.len -= 1; |
1026 | self.head = node.next; | |
1027 | &node.element | |
1028 | }) | |
1a4d82fc | 1029 | } |
1a4d82fc JJ |
1030 | } |
1031 | ||
1032 | #[inline] | |
85aaf69f | 1033 | fn size_hint(&self) -> (usize, Option<usize>) { |
5bcae85e | 1034 | (self.len, Some(self.len)) |
1a4d82fc | 1035 | } |
416331ca XL |
1036 | |
1037 | #[inline] | |
1038 | fn last(mut self) -> Option<&'a T> { | |
1039 | self.next_back() | |
1040 | } | |
1a4d82fc JJ |
1041 | } |
1042 | ||
85aaf69f | 1043 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e | 1044 | impl<'a, T> DoubleEndedIterator for Iter<'a, T> { |
1a4d82fc | 1045 | #[inline] |
5bcae85e SL |
1046 | fn next_back(&mut self) -> Option<&'a T> { |
1047 | if self.len == 0 { | |
1048 | None | |
1049 | } else { | |
1050 | self.tail.map(|node| unsafe { | |
7cac9316 XL |
1051 | // Need an unbound lifetime to get 'a |
1052 | let node = &*node.as_ptr(); | |
5bcae85e SL |
1053 | self.len -= 1; |
1054 | self.tail = node.prev; | |
1055 | &node.element | |
62682a34 SL |
1056 | }) |
1057 | } | |
1a4d82fc JJ |
1058 | } |
1059 | } | |
1060 | ||
85aaf69f | 1061 | #[stable(feature = "rust1", since = "1.0.0")] |
9fa01778 | 1062 | impl<T> ExactSizeIterator for Iter<'_, T> {} |
1a4d82fc | 1063 | |
0531ce1d | 1064 | #[stable(feature = "fused", since = "1.26.0")] |
9fa01778 | 1065 | impl<T> FusedIterator for Iter<'_, T> {} |
9e0c209e | 1066 | |
85aaf69f | 1067 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e SL |
1068 | impl<'a, T> Iterator for IterMut<'a, T> { |
1069 | type Item = &'a mut T; | |
1070 | ||
1a4d82fc | 1071 | #[inline] |
5bcae85e SL |
1072 | fn next(&mut self) -> Option<&'a mut T> { |
1073 | if self.len == 0 { | |
1074 | None | |
1075 | } else { | |
1076 | self.head.map(|node| unsafe { | |
7cac9316 XL |
1077 | // Need an unbound lifetime to get 'a |
1078 | let node = &mut *node.as_ptr(); | |
5bcae85e SL |
1079 | self.len -= 1; |
1080 | self.head = node.next; | |
1081 | &mut node.element | |
62682a34 SL |
1082 | }) |
1083 | } | |
1a4d82fc JJ |
1084 | } |
1085 | ||
1086 | #[inline] | |
85aaf69f | 1087 | fn size_hint(&self) -> (usize, Option<usize>) { |
5bcae85e | 1088 | (self.len, Some(self.len)) |
1a4d82fc | 1089 | } |
416331ca XL |
1090 | |
1091 | #[inline] | |
1092 | fn last(mut self) -> Option<&'a mut T> { | |
1093 | self.next_back() | |
1094 | } | |
1a4d82fc JJ |
1095 | } |
1096 | ||
85aaf69f | 1097 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e | 1098 | impl<'a, T> DoubleEndedIterator for IterMut<'a, T> { |
1a4d82fc | 1099 | #[inline] |
5bcae85e SL |
1100 | fn next_back(&mut self) -> Option<&'a mut T> { |
1101 | if self.len == 0 { | |
1102 | None | |
1103 | } else { | |
1104 | self.tail.map(|node| unsafe { | |
7cac9316 XL |
1105 | // Need an unbound lifetime to get 'a |
1106 | let node = &mut *node.as_ptr(); | |
5bcae85e SL |
1107 | self.len -= 1; |
1108 | self.tail = node.prev; | |
1109 | &mut node.element | |
62682a34 SL |
1110 | }) |
1111 | } | |
1a4d82fc JJ |
1112 | } |
1113 | } | |
1114 | ||
85aaf69f | 1115 | #[stable(feature = "rust1", since = "1.0.0")] |
9fa01778 | 1116 | impl<T> ExactSizeIterator for IterMut<'_, T> {} |
1a4d82fc | 1117 | |
0531ce1d | 1118 | #[stable(feature = "fused", since = "1.26.0")] |
9fa01778 | 1119 | impl<T> FusedIterator for IterMut<'_, T> {} |
9e0c209e | 1120 | |
dfeec247 XL |
1121 | /// A cursor over a `LinkedList`. |
1122 | /// | |
1123 | /// A `Cursor` is like an iterator, except that it can freely seek back-and-forth. | |
1124 | /// | |
1125 | /// Cursors always rest between two elements in the list, and index in a logically circular way. | |
1126 | /// To accommodate this, there is a "ghost" non-element that yields `None` between the head and | |
1127 | /// tail of the list. | |
1128 | /// | |
1129 | /// When created, cursors start at the front of the list, or the "ghost" non-element if the list is empty. | |
1130 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1131 | pub struct Cursor<'a, T: 'a> { | |
1132 | index: usize, | |
1133 | current: Option<NonNull<Node<T>>>, | |
1134 | list: &'a LinkedList<T>, | |
1135 | } | |
1136 | ||
ba9703b0 XL |
1137 | #[unstable(feature = "linked_list_cursors", issue = "58533")] |
1138 | impl<T> Clone for Cursor<'_, T> { | |
1139 | fn clone(&self) -> Self { | |
1140 | let Cursor { index, current, list } = *self; | |
1141 | Cursor { index, current, list } | |
1142 | } | |
1143 | } | |
1144 | ||
dfeec247 XL |
1145 | #[unstable(feature = "linked_list_cursors", issue = "58533")] |
1146 | impl<T: fmt::Debug> fmt::Debug for Cursor<'_, T> { | |
1147 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
1148 | f.debug_tuple("Cursor").field(&self.list).field(&self.index()).finish() | |
1149 | } | |
1150 | } | |
1151 | ||
1152 | /// A cursor over a `LinkedList` with editing operations. | |
1153 | /// | |
1154 | /// A `Cursor` is like an iterator, except that it can freely seek back-and-forth, and can | |
1155 | /// safely mutate the list during iteration. This is because the lifetime of its yielded | |
1156 | /// references is tied to its own lifetime, instead of just the underlying list. This means | |
1157 | /// cursors cannot yield multiple elements at once. | |
1158 | /// | |
1159 | /// Cursors always rest between two elements in the list, and index in a logically circular way. | |
1160 | /// To accommodate this, there is a "ghost" non-element that yields `None` between the head and | |
1161 | /// tail of the list. | |
1162 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1163 | pub struct CursorMut<'a, T: 'a> { | |
1164 | index: usize, | |
1165 | current: Option<NonNull<Node<T>>>, | |
1166 | list: &'a mut LinkedList<T>, | |
1167 | } | |
1168 | ||
1169 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1170 | impl<T: fmt::Debug> fmt::Debug for CursorMut<'_, T> { | |
1171 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
1172 | f.debug_tuple("CursorMut").field(&self.list).field(&self.index()).finish() | |
1173 | } | |
1174 | } | |
1175 | ||
1176 | impl<'a, T> Cursor<'a, T> { | |
1177 | /// Returns the cursor position index within the `LinkedList`. | |
1178 | /// | |
1179 | /// This returns `None` if the cursor is currently pointing to the | |
1180 | /// "ghost" non-element. | |
1181 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1182 | pub fn index(&self) -> Option<usize> { | |
1183 | let _ = self.current?; | |
1184 | Some(self.index) | |
1185 | } | |
1186 | ||
1187 | /// Moves the cursor to the next element of the `LinkedList`. | |
1188 | /// | |
1189 | /// If the cursor is pointing to the "ghost" non-element then this will move it to | |
1190 | /// the first element of the `LinkedList`. If it is pointing to the last | |
1191 | /// element of the `LinkedList` then this will move it to the "ghost" non-element. | |
1192 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1193 | pub fn move_next(&mut self) { | |
1194 | match self.current.take() { | |
1195 | // We had no current element; the cursor was sitting at the start position | |
1196 | // Next element should be the head of the list | |
1197 | None => { | |
1198 | self.current = self.list.head; | |
1199 | self.index = 0; | |
1200 | } | |
1201 | // We had a previous element, so let's go to its next | |
1202 | Some(current) => unsafe { | |
1203 | self.current = current.as_ref().next; | |
1204 | self.index += 1; | |
1205 | }, | |
1206 | } | |
1207 | } | |
1208 | ||
1209 | /// Moves the cursor to the previous element of the `LinkedList`. | |
1210 | /// | |
1211 | /// If the cursor is pointing to the "ghost" non-element then this will move it to | |
1212 | /// the last element of the `LinkedList`. If it is pointing to the first | |
1213 | /// element of the `LinkedList` then this will move it to the "ghost" non-element. | |
1214 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1215 | pub fn move_prev(&mut self) { | |
1216 | match self.current.take() { | |
1217 | // No current. We're at the start of the list. Yield None and jump to the end. | |
1218 | None => { | |
1219 | self.current = self.list.tail; | |
1220 | self.index = self.list.len().checked_sub(1).unwrap_or(0); | |
1221 | } | |
1222 | // Have a prev. Yield it and go to the previous element. | |
1223 | Some(current) => unsafe { | |
1224 | self.current = current.as_ref().prev; | |
1225 | self.index = self.index.checked_sub(1).unwrap_or_else(|| self.list.len()); | |
1226 | }, | |
1227 | } | |
1228 | } | |
1229 | ||
1230 | /// Returns a reference to the element that the cursor is currently | |
1231 | /// pointing to. | |
1232 | /// | |
1233 | /// This returns `None` if the cursor is currently pointing to the | |
1234 | /// "ghost" non-element. | |
1235 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1236 | pub fn current(&self) -> Option<&'a T> { | |
1237 | unsafe { self.current.map(|current| &(*current.as_ptr()).element) } | |
1238 | } | |
1239 | ||
1240 | /// Returns a reference to the next element. | |
1241 | /// | |
1242 | /// If the cursor is pointing to the "ghost" non-element then this returns | |
1243 | /// the first element of the `LinkedList`. If it is pointing to the last | |
1244 | /// element of the `LinkedList` then this returns `None`. | |
1245 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1246 | pub fn peek_next(&self) -> Option<&'a T> { | |
1247 | unsafe { | |
1248 | let next = match self.current { | |
1249 | None => self.list.head, | |
1250 | Some(current) => current.as_ref().next, | |
1251 | }; | |
1252 | next.map(|next| &(*next.as_ptr()).element) | |
1253 | } | |
1254 | } | |
1255 | ||
1256 | /// Returns a reference to the previous element. | |
1257 | /// | |
1258 | /// If the cursor is pointing to the "ghost" non-element then this returns | |
1259 | /// the last element of the `LinkedList`. If it is pointing to the first | |
1260 | /// element of the `LinkedList` then this returns `None`. | |
1261 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1262 | pub fn peek_prev(&self) -> Option<&'a T> { | |
1263 | unsafe { | |
1264 | let prev = match self.current { | |
1265 | None => self.list.tail, | |
1266 | Some(current) => current.as_ref().prev, | |
1267 | }; | |
1268 | prev.map(|prev| &(*prev.as_ptr()).element) | |
1269 | } | |
1270 | } | |
136023e0 XL |
1271 | |
1272 | /// Provides a reference to the front element of the cursor's parent list, | |
1273 | /// or None if the list is empty. | |
1274 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1275 | pub fn front(&self) -> Option<&'a T> { | |
1276 | self.list.front() | |
1277 | } | |
1278 | ||
1279 | /// Provides a reference to the back element of the cursor's parent list, | |
1280 | /// or None if the list is empty. | |
1281 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1282 | pub fn back(&self) -> Option<&'a T> { | |
1283 | self.list.back() | |
1284 | } | |
dfeec247 XL |
1285 | } |
1286 | ||
1287 | impl<'a, T> CursorMut<'a, T> { | |
1288 | /// Returns the cursor position index within the `LinkedList`. | |
1289 | /// | |
1290 | /// This returns `None` if the cursor is currently pointing to the | |
1291 | /// "ghost" non-element. | |
1292 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1293 | pub fn index(&self) -> Option<usize> { | |
1294 | let _ = self.current?; | |
1295 | Some(self.index) | |
1296 | } | |
1297 | ||
1298 | /// Moves the cursor to the next element of the `LinkedList`. | |
1299 | /// | |
1300 | /// If the cursor is pointing to the "ghost" non-element then this will move it to | |
1301 | /// the first element of the `LinkedList`. If it is pointing to the last | |
1302 | /// element of the `LinkedList` then this will move it to the "ghost" non-element. | |
1303 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1304 | pub fn move_next(&mut self) { | |
1305 | match self.current.take() { | |
1306 | // We had no current element; the cursor was sitting at the start position | |
1307 | // Next element should be the head of the list | |
1308 | None => { | |
1309 | self.current = self.list.head; | |
1310 | self.index = 0; | |
1311 | } | |
1312 | // We had a previous element, so let's go to its next | |
1313 | Some(current) => unsafe { | |
1314 | self.current = current.as_ref().next; | |
1315 | self.index += 1; | |
1316 | }, | |
1317 | } | |
1318 | } | |
1319 | ||
1320 | /// Moves the cursor to the previous element of the `LinkedList`. | |
1321 | /// | |
1322 | /// If the cursor is pointing to the "ghost" non-element then this will move it to | |
1323 | /// the last element of the `LinkedList`. If it is pointing to the first | |
1324 | /// element of the `LinkedList` then this will move it to the "ghost" non-element. | |
1325 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1326 | pub fn move_prev(&mut self) { | |
1327 | match self.current.take() { | |
1328 | // No current. We're at the start of the list. Yield None and jump to the end. | |
1329 | None => { | |
1330 | self.current = self.list.tail; | |
1331 | self.index = self.list.len().checked_sub(1).unwrap_or(0); | |
1332 | } | |
1333 | // Have a prev. Yield it and go to the previous element. | |
1334 | Some(current) => unsafe { | |
1335 | self.current = current.as_ref().prev; | |
1336 | self.index = self.index.checked_sub(1).unwrap_or_else(|| self.list.len()); | |
1337 | }, | |
1338 | } | |
1339 | } | |
1340 | ||
1341 | /// Returns a reference to the element that the cursor is currently | |
1342 | /// pointing to. | |
1343 | /// | |
1344 | /// This returns `None` if the cursor is currently pointing to the | |
1345 | /// "ghost" non-element. | |
1346 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1347 | pub fn current(&mut self) -> Option<&mut T> { | |
1348 | unsafe { self.current.map(|current| &mut (*current.as_ptr()).element) } | |
1349 | } | |
1350 | ||
1351 | /// Returns a reference to the next element. | |
1352 | /// | |
1353 | /// If the cursor is pointing to the "ghost" non-element then this returns | |
1354 | /// the first element of the `LinkedList`. If it is pointing to the last | |
1355 | /// element of the `LinkedList` then this returns `None`. | |
1356 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1357 | pub fn peek_next(&mut self) -> Option<&mut T> { | |
1358 | unsafe { | |
1359 | let next = match self.current { | |
1360 | None => self.list.head, | |
1361 | Some(current) => current.as_ref().next, | |
1362 | }; | |
1363 | next.map(|next| &mut (*next.as_ptr()).element) | |
1364 | } | |
1365 | } | |
1366 | ||
1367 | /// Returns a reference to the previous element. | |
1368 | /// | |
1369 | /// If the cursor is pointing to the "ghost" non-element then this returns | |
1370 | /// the last element of the `LinkedList`. If it is pointing to the first | |
1371 | /// element of the `LinkedList` then this returns `None`. | |
1372 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1373 | pub fn peek_prev(&mut self) -> Option<&mut T> { | |
1374 | unsafe { | |
1375 | let prev = match self.current { | |
1376 | None => self.list.tail, | |
1377 | Some(current) => current.as_ref().prev, | |
1378 | }; | |
1379 | prev.map(|prev| &mut (*prev.as_ptr()).element) | |
1380 | } | |
1381 | } | |
1382 | ||
1383 | /// Returns a read-only cursor pointing to the current element. | |
1384 | /// | |
1385 | /// The lifetime of the returned `Cursor` is bound to that of the | |
1386 | /// `CursorMut`, which means it cannot outlive the `CursorMut` and that the | |
1387 | /// `CursorMut` is frozen for the lifetime of the `Cursor`. | |
c295e0f8 | 1388 | #[must_use] |
dfeec247 | 1389 | #[unstable(feature = "linked_list_cursors", issue = "58533")] |
ba9703b0 | 1390 | pub fn as_cursor(&self) -> Cursor<'_, T> { |
dfeec247 XL |
1391 | Cursor { list: self.list, current: self.current, index: self.index } |
1392 | } | |
1393 | } | |
1394 | ||
1395 | // Now the list editing operations | |
1396 | ||
1397 | impl<'a, T> CursorMut<'a, T> { | |
1398 | /// Inserts a new element into the `LinkedList` after the current one. | |
1399 | /// | |
1400 | /// If the cursor is pointing at the "ghost" non-element then the new element is | |
1401 | /// inserted at the front of the `LinkedList`. | |
1402 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1403 | pub fn insert_after(&mut self, item: T) { | |
1404 | unsafe { | |
f9f354fc | 1405 | let spliced_node = Box::leak(Box::new(Node::new(item))).into(); |
dfeec247 XL |
1406 | let node_next = match self.current { |
1407 | None => self.list.head, | |
1408 | Some(node) => node.as_ref().next, | |
1409 | }; | |
1410 | self.list.splice_nodes(self.current, node_next, spliced_node, spliced_node, 1); | |
1411 | if self.current.is_none() { | |
1412 | // The "ghost" non-element's index has changed. | |
1413 | self.index = self.list.len; | |
1414 | } | |
1415 | } | |
1416 | } | |
1417 | ||
1418 | /// Inserts a new element into the `LinkedList` before the current one. | |
1419 | /// | |
1420 | /// If the cursor is pointing at the "ghost" non-element then the new element is | |
1421 | /// inserted at the end of the `LinkedList`. | |
1422 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1423 | pub fn insert_before(&mut self, item: T) { | |
1424 | unsafe { | |
f9f354fc | 1425 | let spliced_node = Box::leak(Box::new(Node::new(item))).into(); |
dfeec247 XL |
1426 | let node_prev = match self.current { |
1427 | None => self.list.tail, | |
1428 | Some(node) => node.as_ref().prev, | |
1429 | }; | |
1430 | self.list.splice_nodes(node_prev, self.current, spliced_node, spliced_node, 1); | |
1431 | self.index += 1; | |
1432 | } | |
1433 | } | |
1434 | ||
1435 | /// Removes the current element from the `LinkedList`. | |
1436 | /// | |
1437 | /// The element that was removed is returned, and the cursor is | |
1438 | /// moved to point to the next element in the `LinkedList`. | |
1439 | /// | |
1440 | /// If the cursor is currently pointing to the "ghost" non-element then no element | |
1441 | /// is removed and `None` is returned. | |
1442 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1443 | pub fn remove_current(&mut self) -> Option<T> { | |
1444 | let unlinked_node = self.current?; | |
1445 | unsafe { | |
1446 | self.current = unlinked_node.as_ref().next; | |
1447 | self.list.unlink_node(unlinked_node); | |
1448 | let unlinked_node = Box::from_raw(unlinked_node.as_ptr()); | |
1449 | Some(unlinked_node.element) | |
1450 | } | |
1451 | } | |
1452 | ||
f9f354fc XL |
1453 | /// Removes the current element from the `LinkedList` without deallocating the list node. |
1454 | /// | |
1455 | /// The node that was removed is returned as a new `LinkedList` containing only this node. | |
1456 | /// The cursor is moved to point to the next element in the current `LinkedList`. | |
1457 | /// | |
1458 | /// If the cursor is currently pointing to the "ghost" non-element then no element | |
1459 | /// is removed and `None` is returned. | |
1460 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1461 | pub fn remove_current_as_list(&mut self) -> Option<LinkedList<T>> { | |
1462 | let mut unlinked_node = self.current?; | |
1463 | unsafe { | |
1464 | self.current = unlinked_node.as_ref().next; | |
1465 | self.list.unlink_node(unlinked_node); | |
1466 | ||
1467 | unlinked_node.as_mut().prev = None; | |
1468 | unlinked_node.as_mut().next = None; | |
1469 | Some(LinkedList { | |
1470 | head: Some(unlinked_node), | |
1471 | tail: Some(unlinked_node), | |
1472 | len: 1, | |
1473 | marker: PhantomData, | |
1474 | }) | |
1475 | } | |
1476 | } | |
1477 | ||
dfeec247 XL |
1478 | /// Inserts the elements from the given `LinkedList` after the current one. |
1479 | /// | |
1480 | /// If the cursor is pointing at the "ghost" non-element then the new elements are | |
1481 | /// inserted at the start of the `LinkedList`. | |
1482 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1483 | pub fn splice_after(&mut self, list: LinkedList<T>) { | |
1484 | unsafe { | |
1485 | let (splice_head, splice_tail, splice_len) = match list.detach_all_nodes() { | |
1486 | Some(parts) => parts, | |
1487 | _ => return, | |
1488 | }; | |
1489 | let node_next = match self.current { | |
1490 | None => self.list.head, | |
1491 | Some(node) => node.as_ref().next, | |
1492 | }; | |
1493 | self.list.splice_nodes(self.current, node_next, splice_head, splice_tail, splice_len); | |
1494 | if self.current.is_none() { | |
1495 | // The "ghost" non-element's index has changed. | |
1496 | self.index = self.list.len; | |
7cac9316 | 1497 | } |
62682a34 | 1498 | } |
1a4d82fc | 1499 | } |
dfeec247 XL |
1500 | |
1501 | /// Inserts the elements from the given `LinkedList` before the current one. | |
1502 | /// | |
1503 | /// If the cursor is pointing at the "ghost" non-element then the new elements are | |
1504 | /// inserted at the end of the `LinkedList`. | |
1505 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1506 | pub fn splice_before(&mut self, list: LinkedList<T>) { | |
1507 | unsafe { | |
1508 | let (splice_head, splice_tail, splice_len) = match list.detach_all_nodes() { | |
1509 | Some(parts) => parts, | |
1510 | _ => return, | |
1511 | }; | |
1512 | let node_prev = match self.current { | |
1513 | None => self.list.tail, | |
1514 | Some(node) => node.as_ref().prev, | |
1515 | }; | |
1516 | self.list.splice_nodes(node_prev, self.current, splice_head, splice_tail, splice_len); | |
1517 | self.index += splice_len; | |
1518 | } | |
1519 | } | |
1520 | ||
1521 | /// Splits the list into two after the current element. This will return a | |
1522 | /// new list consisting of everything after the cursor, with the original | |
1523 | /// list retaining everything before. | |
1524 | /// | |
1525 | /// If the cursor is pointing at the "ghost" non-element then the entire contents | |
1526 | /// of the `LinkedList` are moved. | |
1527 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1528 | pub fn split_after(&mut self) -> LinkedList<T> { | |
1529 | let split_off_idx = if self.index == self.list.len { 0 } else { self.index + 1 }; | |
1530 | if self.index == self.list.len { | |
1531 | // The "ghost" non-element's index has changed to 0. | |
1532 | self.index = 0; | |
1533 | } | |
1534 | unsafe { self.list.split_off_after_node(self.current, split_off_idx) } | |
1535 | } | |
1536 | ||
1537 | /// Splits the list into two before the current element. This will return a | |
1538 | /// new list consisting of everything before the cursor, with the original | |
1539 | /// list retaining everything after. | |
1540 | /// | |
1541 | /// If the cursor is pointing at the "ghost" non-element then the entire contents | |
1542 | /// of the `LinkedList` are moved. | |
1543 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1544 | pub fn split_before(&mut self) -> LinkedList<T> { | |
1545 | let split_off_idx = self.index; | |
1546 | self.index = 0; | |
1547 | unsafe { self.list.split_off_before_node(self.current, split_off_idx) } | |
1548 | } | |
136023e0 XL |
1549 | |
1550 | /// Appends an element to the front of the cursor's parent list. The node | |
1551 | /// that the cursor points to is unchanged, even if it is the "ghost" node. | |
1552 | /// | |
1553 | /// This operation should compute in O(1) time. | |
1554 | // `push_front` continues to point to "ghost" when it addes a node to mimic | |
1555 | // the behavior of `insert_before` on an empty list. | |
1556 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1557 | pub fn push_front(&mut self, elt: T) { | |
1558 | // Safety: We know that `push_front` does not change the position in | |
1559 | // memory of other nodes. This ensures that `self.current` remains | |
1560 | // valid. | |
1561 | self.list.push_front(elt); | |
1562 | self.index += 1; | |
1563 | } | |
1564 | ||
1565 | /// Appends an element to the back of the cursor's parent list. The node | |
1566 | /// that the cursor points to is unchanged, even if it is the "ghost" node. | |
1567 | /// | |
1568 | /// This operation should compute in O(1) time. | |
1569 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1570 | pub fn push_back(&mut self, elt: T) { | |
1571 | // Safety: We know that `push_back` does not change the position in | |
1572 | // memory of other nodes. This ensures that `self.current` remains | |
1573 | // valid. | |
1574 | self.list.push_back(elt); | |
1575 | if self.current().is_none() { | |
1576 | // The index of "ghost" is the length of the list, so we just need | |
1577 | // to increment self.index to reflect the new length of the list. | |
1578 | self.index += 1; | |
1579 | } | |
1580 | } | |
1581 | ||
1582 | /// Removes the first element from the cursor's parent list and returns it, | |
1583 | /// or None if the list is empty. The element the cursor points to remains | |
1584 | /// unchanged, unless it was pointing to the front element. In that case, it | |
1585 | /// points to the new front element. | |
1586 | /// | |
1587 | /// This operation should compute in O(1) time. | |
1588 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1589 | pub fn pop_front(&mut self) -> Option<T> { | |
1590 | // We can't check if current is empty, we must check the list directly. | |
1591 | // It is possible for `self.current == None` and the list to be | |
1592 | // non-empty. | |
1593 | if self.list.is_empty() { | |
1594 | None | |
1595 | } else { | |
1596 | // We can't point to the node that we pop. Copying the behavior of | |
1597 | // `remove_current`, we move on the the next node in the sequence. | |
1598 | // If the list is of length 1 then we end pointing to the "ghost" | |
1599 | // node at index 0, which is expected. | |
1600 | if self.list.head == self.current { | |
1601 | self.move_next(); | |
1602 | } else { | |
1603 | self.index -= 1; | |
1604 | } | |
1605 | self.list.pop_front() | |
1606 | } | |
1607 | } | |
1608 | ||
1609 | /// Removes the last element from the cursor's parent list and returns it, | |
1610 | /// or None if the list is empty. The element the cursor points to remains | |
1611 | /// unchanged, unless it was pointing to the back element. In that case, it | |
1612 | /// points to the "ghost" element. | |
1613 | /// | |
1614 | /// This operation should compute in O(1) time. | |
1615 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1616 | pub fn pop_back(&mut self) -> Option<T> { | |
1617 | if self.list.is_empty() { | |
1618 | None | |
1619 | } else { | |
1620 | if self.list.tail == self.current { | |
1621 | // The index now reflects the length of the list. It was the | |
1622 | // length of the list minus 1, but now the list is 1 smaller. No | |
1623 | // change is needed for `index`. | |
1624 | self.current = None; | |
1625 | } else if self.current.is_none() { | |
1626 | self.index = self.list.len - 1; | |
1627 | } | |
1628 | self.list.pop_back() | |
1629 | } | |
1630 | } | |
1631 | ||
1632 | /// Provides a reference to the front element of the cursor's parent list, | |
1633 | /// or None if the list is empty. | |
1634 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1635 | pub fn front(&self) -> Option<&T> { | |
1636 | self.list.front() | |
1637 | } | |
1638 | ||
1639 | /// Provides a mutable reference to the front element of the cursor's | |
1640 | /// parent list, or None if the list is empty. | |
1641 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1642 | pub fn front_mut(&mut self) -> Option<&mut T> { | |
1643 | self.list.front_mut() | |
1644 | } | |
1645 | ||
1646 | /// Provides a reference to the back element of the cursor's parent list, | |
1647 | /// or None if the list is empty. | |
1648 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1649 | pub fn back(&self) -> Option<&T> { | |
1650 | self.list.back() | |
1651 | } | |
1652 | ||
1653 | /// Provides a mutable reference to back element of the cursor's parent | |
1654 | /// list, or `None` if the list is empty. | |
1655 | /// | |
1656 | /// # Examples | |
1657 | /// Building and mutating a list with a cursor, then getting the back element: | |
1658 | /// ``` | |
1659 | /// #![feature(linked_list_cursors)] | |
1660 | /// use std::collections::LinkedList; | |
1661 | /// let mut dl = LinkedList::new(); | |
1662 | /// dl.push_front(3); | |
1663 | /// dl.push_front(2); | |
1664 | /// dl.push_front(1); | |
1665 | /// let mut cursor = dl.cursor_front_mut(); | |
1666 | /// *cursor.current().unwrap() = 99; | |
1667 | /// *cursor.back_mut().unwrap() = 0; | |
1668 | /// let mut contents = dl.into_iter(); | |
1669 | /// assert_eq!(contents.next(), Some(99)); | |
1670 | /// assert_eq!(contents.next(), Some(2)); | |
1671 | /// assert_eq!(contents.next(), Some(0)); | |
1672 | /// assert_eq!(contents.next(), None); | |
1673 | /// ``` | |
1674 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1675 | pub fn back_mut(&mut self) -> Option<&mut T> { | |
1676 | self.list.back_mut() | |
1677 | } | |
1a4d82fc JJ |
1678 | } |
1679 | ||
ff7c6d11 XL |
1680 | /// An iterator produced by calling `drain_filter` on LinkedList. |
1681 | #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")] | |
1682 | pub struct DrainFilter<'a, T: 'a, F: 'a> | |
dfeec247 XL |
1683 | where |
1684 | F: FnMut(&mut T) -> bool, | |
ff7c6d11 XL |
1685 | { |
1686 | list: &'a mut LinkedList<T>, | |
2c00a5a8 | 1687 | it: Option<NonNull<Node<T>>>, |
ff7c6d11 XL |
1688 | pred: F, |
1689 | idx: usize, | |
1690 | old_len: usize, | |
1691 | } | |
1692 | ||
1693 | #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")] | |
9fa01778 | 1694 | impl<T, F> Iterator for DrainFilter<'_, T, F> |
dfeec247 XL |
1695 | where |
1696 | F: FnMut(&mut T) -> bool, | |
ff7c6d11 XL |
1697 | { |
1698 | type Item = T; | |
1699 | ||
1700 | fn next(&mut self) -> Option<T> { | |
1701 | while let Some(mut node) = self.it { | |
1702 | unsafe { | |
1703 | self.it = node.as_ref().next; | |
1704 | self.idx += 1; | |
1705 | ||
1706 | if (self.pred)(&mut node.as_mut().element) { | |
48663c56 | 1707 | // `unlink_node` is okay with aliasing `element` references. |
ff7c6d11 XL |
1708 | self.list.unlink_node(node); |
1709 | return Some(Box::from_raw(node.as_ptr()).element); | |
1710 | } | |
1711 | } | |
1712 | } | |
1713 | ||
1714 | None | |
1715 | } | |
1716 | ||
1717 | fn size_hint(&self) -> (usize, Option<usize>) { | |
1718 | (0, Some(self.old_len - self.idx)) | |
1719 | } | |
1720 | } | |
1721 | ||
1722 | #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")] | |
9fa01778 | 1723 | impl<T, F> Drop for DrainFilter<'_, T, F> |
dfeec247 XL |
1724 | where |
1725 | F: FnMut(&mut T) -> bool, | |
ff7c6d11 XL |
1726 | { |
1727 | fn drop(&mut self) { | |
74b04a01 XL |
1728 | struct DropGuard<'r, 'a, T, F>(&'r mut DrainFilter<'a, T, F>) |
1729 | where | |
1730 | F: FnMut(&mut T) -> bool; | |
1731 | ||
1732 | impl<'r, 'a, T, F> Drop for DropGuard<'r, 'a, T, F> | |
1733 | where | |
1734 | F: FnMut(&mut T) -> bool, | |
1735 | { | |
1736 | fn drop(&mut self) { | |
1737 | self.0.for_each(drop); | |
1738 | } | |
1739 | } | |
1740 | ||
1741 | while let Some(item) = self.next() { | |
1742 | let guard = DropGuard(self); | |
1743 | drop(item); | |
1744 | mem::forget(guard); | |
1745 | } | |
ff7c6d11 XL |
1746 | } |
1747 | } | |
1748 | ||
1749 | #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")] | |
9fa01778 | 1750 | impl<T: fmt::Debug, F> fmt::Debug for DrainFilter<'_, T, F> |
dfeec247 XL |
1751 | where |
1752 | F: FnMut(&mut T) -> bool, | |
ff7c6d11 | 1753 | { |
9fa01778 | 1754 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
dfeec247 | 1755 | f.debug_tuple("DrainFilter").field(&self.list).finish() |
ff7c6d11 XL |
1756 | } |
1757 | } | |
1758 | ||
85aaf69f | 1759 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e SL |
1760 | impl<T> Iterator for IntoIter<T> { |
1761 | type Item = T; | |
1a4d82fc JJ |
1762 | |
1763 | #[inline] | |
5bcae85e | 1764 | fn next(&mut self) -> Option<T> { |
92a42be0 SL |
1765 | self.list.pop_front() |
1766 | } | |
1a4d82fc JJ |
1767 | |
1768 | #[inline] | |
85aaf69f | 1769 | fn size_hint(&self) -> (usize, Option<usize>) { |
5bcae85e | 1770 | (self.list.len, Some(self.list.len)) |
1a4d82fc JJ |
1771 | } |
1772 | } | |
1773 | ||
85aaf69f | 1774 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e | 1775 | impl<T> DoubleEndedIterator for IntoIter<T> { |
1a4d82fc | 1776 | #[inline] |
5bcae85e | 1777 | fn next_back(&mut self) -> Option<T> { |
92a42be0 SL |
1778 | self.list.pop_back() |
1779 | } | |
1a4d82fc JJ |
1780 | } |
1781 | ||
92a42be0 | 1782 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e | 1783 | impl<T> ExactSizeIterator for IntoIter<T> {} |
c34b1796 | 1784 | |
0531ce1d | 1785 | #[stable(feature = "fused", since = "1.26.0")] |
9e0c209e SL |
1786 | impl<T> FusedIterator for IntoIter<T> {} |
1787 | ||
85aaf69f | 1788 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e SL |
1789 | impl<T> FromIterator<T> for LinkedList<T> { |
1790 | fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self { | |
1791 | let mut list = Self::new(); | |
1792 | list.extend(iter); | |
1793 | list | |
1a4d82fc JJ |
1794 | } |
1795 | } | |
1796 | ||
85aaf69f SL |
1797 | #[stable(feature = "rust1", since = "1.0.0")] |
1798 | impl<T> IntoIterator for LinkedList<T> { | |
1799 | type Item = T; | |
1800 | type IntoIter = IntoIter<T>; | |
1801 | ||
9346a6ac AL |
1802 | /// Consumes the list into an iterator yielding elements by value. |
1803 | #[inline] | |
85aaf69f | 1804 | fn into_iter(self) -> IntoIter<T> { |
92a42be0 | 1805 | IntoIter { list: self } |
85aaf69f SL |
1806 | } |
1807 | } | |
1808 | ||
1809 | #[stable(feature = "rust1", since = "1.0.0")] | |
1810 | impl<'a, T> IntoIterator for &'a LinkedList<T> { | |
1811 | type Item = &'a T; | |
1812 | type IntoIter = Iter<'a, T>; | |
1813 | ||
1814 | fn into_iter(self) -> Iter<'a, T> { | |
1815 | self.iter() | |
1816 | } | |
1817 | } | |
1818 | ||
92a42be0 | 1819 | #[stable(feature = "rust1", since = "1.0.0")] |
85aaf69f SL |
1820 | impl<'a, T> IntoIterator for &'a mut LinkedList<T> { |
1821 | type Item = &'a mut T; | |
1822 | type IntoIter = IterMut<'a, T>; | |
1823 | ||
5bcae85e | 1824 | fn into_iter(self) -> IterMut<'a, T> { |
85aaf69f | 1825 | self.iter_mut() |
1a4d82fc JJ |
1826 | } |
1827 | } | |
1828 | ||
85aaf69f | 1829 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e SL |
1830 | impl<T> Extend<T> for LinkedList<T> { |
1831 | fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) { | |
1832 | <Self as SpecExtend<I>>::spec_extend(self, iter); | |
a7813a04 | 1833 | } |
f9f354fc XL |
1834 | |
1835 | #[inline] | |
1836 | fn extend_one(&mut self, elem: T) { | |
1837 | self.push_back(elem); | |
1838 | } | |
a7813a04 XL |
1839 | } |
1840 | ||
1841 | impl<I: IntoIterator> SpecExtend<I> for LinkedList<I::Item> { | |
1842 | default fn spec_extend(&mut self, iter: I) { | |
532ac7d7 | 1843 | iter.into_iter().for_each(move |elt| self.push_back(elt)); |
85aaf69f SL |
1844 | } |
1845 | } | |
1846 | ||
a7813a04 XL |
1847 | impl<T> SpecExtend<LinkedList<T>> for LinkedList<T> { |
1848 | fn spec_extend(&mut self, ref mut other: LinkedList<T>) { | |
1849 | self.append(other); | |
1850 | } | |
1851 | } | |
1852 | ||
62682a34 SL |
1853 | #[stable(feature = "extend_ref", since = "1.2.0")] |
1854 | impl<'a, T: 'a + Copy> Extend<&'a T> for LinkedList<T> { | |
92a42be0 | 1855 | fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) { |
62682a34 SL |
1856 | self.extend(iter.into_iter().cloned()); |
1857 | } | |
f9f354fc XL |
1858 | |
1859 | #[inline] | |
1860 | fn extend_one(&mut self, &elem: &'a T) { | |
1861 | self.push_back(elem); | |
1862 | } | |
62682a34 SL |
1863 | } |
1864 | ||
85aaf69f | 1865 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e SL |
1866 | impl<T: PartialEq> PartialEq for LinkedList<T> { |
1867 | fn eq(&self, other: &Self) -> bool { | |
1868 | self.len() == other.len() && self.iter().eq(other) | |
1a4d82fc JJ |
1869 | } |
1870 | ||
5bcae85e SL |
1871 | fn ne(&self, other: &Self) -> bool { |
1872 | self.len() != other.len() || self.iter().ne(other) | |
1a4d82fc JJ |
1873 | } |
1874 | } | |
1875 | ||
85aaf69f | 1876 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e | 1877 | impl<T: Eq> Eq for LinkedList<T> {} |
1a4d82fc | 1878 | |
85aaf69f | 1879 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e SL |
1880 | impl<T: PartialOrd> PartialOrd for LinkedList<T> { |
1881 | fn partial_cmp(&self, other: &Self) -> Option<Ordering> { | |
1882 | self.iter().partial_cmp(other) | |
1a4d82fc JJ |
1883 | } |
1884 | } | |
1885 | ||
85aaf69f | 1886 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e | 1887 | impl<T: Ord> Ord for LinkedList<T> { |
1a4d82fc | 1888 | #[inline] |
5bcae85e SL |
1889 | fn cmp(&self, other: &Self) -> Ordering { |
1890 | self.iter().cmp(other) | |
1a4d82fc JJ |
1891 | } |
1892 | } | |
1893 | ||
85aaf69f | 1894 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e SL |
1895 | impl<T: Clone> Clone for LinkedList<T> { |
1896 | fn clone(&self) -> Self { | |
85aaf69f | 1897 | self.iter().cloned().collect() |
1a4d82fc | 1898 | } |
e74abb32 XL |
1899 | |
1900 | fn clone_from(&mut self, other: &Self) { | |
1901 | let mut iter_other = other.iter(); | |
1902 | if self.len() > other.len() { | |
1903 | self.split_off(other.len()); | |
1904 | } | |
1905 | for (elem, elem_other) in self.iter_mut().zip(&mut iter_other) { | |
1906 | elem.clone_from(elem_other); | |
1907 | } | |
1908 | if !iter_other.is_empty() { | |
1909 | self.extend(iter_other.cloned()); | |
1910 | } | |
1911 | } | |
1a4d82fc JJ |
1912 | } |
1913 | ||
85aaf69f | 1914 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e | 1915 | impl<T: fmt::Debug> fmt::Debug for LinkedList<T> { |
9fa01778 | 1916 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
5bcae85e | 1917 | f.debug_list().entries(self).finish() |
1a4d82fc JJ |
1918 | } |
1919 | } | |
1920 | ||
85aaf69f | 1921 | #[stable(feature = "rust1", since = "1.0.0")] |
5bcae85e | 1922 | impl<T: Hash> Hash for LinkedList<T> { |
85aaf69f SL |
1923 | fn hash<H: Hasher>(&self, state: &mut H) { |
1924 | self.len().hash(state); | |
1925 | for elt in self { | |
1a4d82fc JJ |
1926 | elt.hash(state); |
1927 | } | |
1928 | } | |
1929 | } | |
1930 | ||
94222f64 XL |
1931 | #[stable(feature = "std_collections_from_array", since = "1.56.0")] |
1932 | impl<T, const N: usize> From<[T; N]> for LinkedList<T> { | |
1933 | /// ``` | |
1934 | /// use std::collections::LinkedList; | |
1935 | /// | |
1936 | /// let list1 = LinkedList::from([1, 2, 3, 4]); | |
1937 | /// let list2: LinkedList<_> = [1, 2, 3, 4].into(); | |
1938 | /// assert_eq!(list1, list2); | |
1939 | /// ``` | |
1940 | fn from(arr: [T; N]) -> Self { | |
1941 | core::array::IntoIter::new(arr).collect() | |
1942 | } | |
1943 | } | |
1944 | ||
9cc50fc6 SL |
1945 | // Ensure that `LinkedList` and its read-only iterators are covariant in their type parameters. |
1946 | #[allow(dead_code)] | |
1947 | fn assert_covariance() { | |
32a655c1 SL |
1948 | fn a<'a>(x: LinkedList<&'static str>) -> LinkedList<&'a str> { |
1949 | x | |
1950 | } | |
1951 | fn b<'i, 'a>(x: Iter<'i, &'static str>) -> Iter<'i, &'a str> { | |
1952 | x | |
1953 | } | |
1954 | fn c<'a>(x: IntoIter<&'static str>) -> IntoIter<&'a str> { | |
1955 | x | |
1956 | } | |
9cc50fc6 SL |
1957 | } |
1958 | ||
5bcae85e SL |
1959 | #[stable(feature = "rust1", since = "1.0.0")] |
1960 | unsafe impl<T: Send> Send for LinkedList<T> {} | |
1961 | ||
1962 | #[stable(feature = "rust1", since = "1.0.0")] | |
1963 | unsafe impl<T: Sync> Sync for LinkedList<T> {} | |
1964 | ||
1965 | #[stable(feature = "rust1", since = "1.0.0")] | |
9fa01778 | 1966 | unsafe impl<T: Sync> Send for Iter<'_, T> {} |
5bcae85e SL |
1967 | |
1968 | #[stable(feature = "rust1", since = "1.0.0")] | |
9fa01778 | 1969 | unsafe impl<T: Sync> Sync for Iter<'_, T> {} |
5bcae85e SL |
1970 | |
1971 | #[stable(feature = "rust1", since = "1.0.0")] | |
9fa01778 | 1972 | unsafe impl<T: Send> Send for IterMut<'_, T> {} |
5bcae85e SL |
1973 | |
1974 | #[stable(feature = "rust1", since = "1.0.0")] | |
9fa01778 | 1975 | unsafe impl<T: Sync> Sync for IterMut<'_, T> {} |
f9f354fc XL |
1976 | |
1977 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1978 | unsafe impl<T: Sync> Send for Cursor<'_, T> {} | |
1979 | ||
1980 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1981 | unsafe impl<T: Sync> Sync for Cursor<'_, T> {} | |
1982 | ||
1983 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1984 | unsafe impl<T: Send> Send for CursorMut<'_, T> {} | |
1985 | ||
1986 | #[unstable(feature = "linked_list_cursors", issue = "58533")] | |
1987 | unsafe impl<T: Sync> Sync for CursorMut<'_, T> {} |