array_linked_list/lib.rs
1#![deny(missing_docs)]
2
3/*!
4The `ArrayLinkedList` data structure combines the benefit of an array and a linked list.
5
6Every supported operation, which does not (re-)allocate the array, is done in *O*(1):
7
8* inserting elements at the front and back
9* popping element at the front or back
10* getting the element count
11* removing elements at an arbitrary index
12* inserting elements at an arbitrary index
13* replacing elements at an arbitrary index
14
15It's stored like an array, but contains some additional information.
16
17You would typically use it, where you need to be able to do multiple of the following tasks efficiently:
18
19* accessing single elements by index
20* adding and removing elements without changing order or indices
21* sorting elements without changing indices or moving the content around.
22
23# Order and indexing
24
25You might also use it as a more convenient version of a `Vec<Option<T>>`.
26When iterating over it, only the elements, which are `Some` are given to the user.
27And even the checks for `Some` are optimized away.
28So when it's likely, that most of the options of a large array are `None`, this might be a huge performance improvement.
29
30Another advantage over a `LinkedList` is the cache locality.
31Everything is laid out in a contiguous region of memory.
32Compared to a `Vec` on the other hand, it might be bad.
33The iteration does not necessarily take place in the same order.
34That's mostly a problem for large arrays.
35The iterator would jump back and forth in the array.
36
37In order to understand this type, it's necessary to know about the iteration order.
38There is a logical order, which is used by the iterators, or when doing anything with the first and last elements.
39You can think of it as the order of a linked list, which is just packed into an array here.
40And then there is indexing, which has nothing to do with the order of the linked list.
41The indices just return the array elements.
42
43## Index Example
44
45So when adding an element to the linked array without specifying the index, you get the index, it was put to, as a result.
46The results are always added to the array in order, so the indices increase, no matter if you add the indices to the front or to the back:
47
48```
49use array_linked_list::ArrayLinkedList;
50
51let mut array = ArrayLinkedList::new();
52
53assert_eq!(array.push_front(1), 0);
54assert_eq!(array.push_back(2), 1);
55assert_eq!(array.push_front(3), 2);
56assert_eq!(array.push_front(4), 3);
57assert_eq!(array.push_back(5), 4);
58```
59
60## Order example
61
62When you just apped elements from the front or back, the indices even correlate to the order:
63
64```
65use array_linked_list::ArrayLinkedList;
66
67let mut array = ArrayLinkedList::new();
68
69array.push_front(1);
70array.push_front(2);
71array.push_front(3);
72
73for (i, element) in array.iter().rev().enumerate() {
74 assert_eq!(*element, array[i].unwrap());
75}
76```
77
78```
79use array_linked_list::ArrayLinkedList;
80
81let mut array = ArrayLinkedList::new();
82
83array.push_back(1);
84array.push_back(2);
85array.push_back(3);
86
87for (i, element) in array.iter().enumerate() {
88 assert_eq!(*element, array[i].unwrap());
89}
90```
91
92## Iteration over unsorted lists
93
94In realistic cases, you need to store the indices somewhere else, if you need them.
95Alternatively, you can also use
96
97```
98use array_linked_list::ArrayLinkedList;
99
100let mut array = ArrayLinkedList::new();
101
102array.push_back(1);
103array.push_front(2);
104array.push_front(3);
105array.push_back(4);
106array.push_front(5);
107
108for (index, element) in array.indexed().rev() {
109 assert_eq!(*element, array[index].unwrap());
110}
111```
112
113## Conclusion
114
115Just remember, that indices and order are two different things, which don't correlate, and you should be safe.
116
117**/
118
119use std::{
120 hint, mem,
121 ops::{Index, IndexMut},
122};
123
124#[derive(Copy, Clone, Debug, PartialEq)]
125struct LinkedListNode<T> {
126 next_index: usize,
127 prev_index: usize,
128 data: Option<T>,
129}
130
131impl<T> LinkedListNode<T> {
132 fn new(prev_index: usize, next_index: usize, data: T) -> Self {
133 Self {
134 next_index,
135 prev_index,
136 data: Some(data),
137 }
138 }
139
140 fn front(first_index: usize, data: T) -> Self {
141 Self {
142 next_index: first_index,
143 prev_index: 0,
144 data: Some(data),
145 }
146 }
147
148 fn back(last_index: usize, data: T) -> Self {
149 Self {
150 next_index: 0,
151 prev_index: last_index,
152 data: Some(data),
153 }
154 }
155
156 fn deleted(free_index: usize) -> Self {
157 Self {
158 next_index: free_index,
159 prev_index: 0,
160 data: None,
161 }
162 }
163}
164
165/// The `ArrayLinkedList` type, which combines the advantages of dynamic arrays and linked lists.
166#[derive(Clone, Debug, PartialEq)]
167pub struct ArrayLinkedList<T> {
168 count: usize,
169 first_index: usize,
170 last_index: usize,
171 free_index: usize,
172 end_index: usize,
173 elements: Vec<LinkedListNode<T>>,
174}
175
176impl<T> ArrayLinkedList<T> {
177 /// Constructs a new, empty ArrayLinkedList<T>.
178 ///
179 /// The linked array will not allocate until elements are pushed onto it.
180 pub fn new() -> Self {
181 Self {
182 count: 0,
183 first_index: 0,
184 last_index: 0,
185 free_index: 0,
186 end_index: 0,
187 elements: Vec::new(),
188 }
189 }
190
191 #[inline]
192 fn fill_elements(&mut self, capacity: usize) {
193 if capacity == 0 {
194 return;
195 }
196 for i in 1..capacity {
197 self.elements.push(LinkedListNode::deleted(i + 1))
198 }
199 self.elements.push(LinkedListNode::deleted(0));
200
201 self.free_index = 1;
202 self.end_index = capacity;
203 }
204
205 /// Constructs a new, empty `ArrayLinkedList<T>` with the specified capacity.
206 ///
207 /// The array will be able to hold exactly `capacity` elements without reallocating.
208 // If `capacity` is 0, the vector will not allocate.
209 pub fn with_capacity(capacity: usize) -> Self {
210 let mut result = Self::new();
211 result.elements = Vec::with_capacity(capacity);
212 result.fill_elements(capacity);
213 result
214 }
215
216 fn insert_free_element(&mut self, element: LinkedListNode<T>) -> usize {
217 if self.free_index == 0 {
218 self.elements.push(element);
219 self.elements.len()
220 } else {
221 let free_index = self.free_index;
222 let recycle_element = &mut self.elements[free_index - 1];
223 self.free_index = recycle_element.next_index;
224 *recycle_element = element;
225 free_index
226 }
227 }
228
229 /// Adds an element at the front of the array and returns its index.
230 /// The indices are returned in a raising order, starting with zero.
231 /// See the module description for more information.
232 ///
233 /// This operation should compute in *O*(1) time.
234 ///
235 /// # Examples
236 ///
237 /// ```
238 /// use array_linked_list::ArrayLinkedList;
239 ///
240 /// let mut array = ArrayLinkedList::new();
241 ///
242 /// assert_eq!(array.push_front(2), 0);
243 /// assert_eq!(array.front().unwrap(), &2);
244 ///
245 /// assert_eq!(array.push_front(1), 1);
246 /// assert_eq!(array.front().unwrap(), &1);
247 /// ```
248 pub fn push_front(&mut self, value: T) -> usize {
249 let element = LinkedListNode::front(self.first_index, value);
250
251 let next_index = self.insert_free_element(element);
252
253 *self.prev_of_next(self.first_index, true) = next_index;
254
255 self.first_index = next_index;
256 self.count += 1;
257
258 next_index - 1
259 }
260
261 /// Adds an element at the back of the array and returns its index.
262 /// The indices are returned in a raising order, starting with zero.
263 /// See the module description for more information.
264 ///
265 /// This operation should compute in *O*(1) time.
266 ///
267 /// # Examples
268 ///
269 /// ```
270 /// use array_linked_list::ArrayLinkedList;
271 ///
272 /// let mut array = ArrayLinkedList::new();
273 ///
274 /// assert_eq!(array.push_back(1), 0);
275 /// assert_eq!(array.push_back(3), 1);
276 /// assert_eq!(3, *array.back().unwrap());
277 /// ```
278 pub fn push_back(&mut self, value: T) -> usize {
279 let element = LinkedListNode::back(self.last_index, value);
280
281 let prev_index = self.insert_free_element(element);
282
283 *self.next_of_prev(self.last_index, true) = prev_index;
284
285 self.last_index = prev_index;
286 self.count += 1;
287
288 prev_index - 1
289 }
290
291 fn insert_between(&mut self, prev_index: usize, next_index: usize, value: T) -> usize {
292 let element = LinkedListNode::new(prev_index, next_index, value);
293
294 let index = self.insert_free_element(element);
295
296 *self.next_of_prev(prev_index, true) = index;
297 *self.prev_of_next(next_index, true) = index;
298
299 self.count += 1;
300
301 index - 1
302 }
303
304 /// Inserts an element after the element at the specified index.
305 /// Returns the index of the inserted element on success.
306 /// If no element was found at the specified index, `None` is returned.
307 ///
308 /// # Panics
309 /// Panics if prev_index >= capacity
310 ///
311 /// # Examples
312 ///
313 /// ```
314 /// use array_linked_list::ArrayLinkedList;
315 ///
316 /// let mut array = ArrayLinkedList::new();
317 ///
318 /// let first = array.push_back(1);
319 /// let second = array.push_back(2);
320 /// let third = array.push_back(3);
321 ///
322 /// array.insert_after(second, 100);
323 ///
324 /// assert_eq!(array.pop_front(), Some(1));
325 /// assert_eq!(array.pop_front(), Some(2));
326 /// assert_eq!(array.pop_front(), Some(100));
327 /// assert_eq!(array.pop_front(), Some(3));
328 /// assert_eq!(array.pop_front(), None);
329 /// ```
330 pub fn insert_after(&mut self, prev_index: usize, value: T) -> Option<usize> {
331 let LinkedListNode {
332 next_index, data, ..
333 } = &self.elements[prev_index];
334
335 if data.is_some() {
336 let next_index = *next_index;
337 Some(self.insert_between(prev_index + 1, next_index, value))
338 } else {
339 None
340 }
341 }
342
343 /// Inserts an element before the element at the specified index.
344 /// Returns the index of the inserted element on success.
345 /// If no element was found at the specified index, `None` is returned.
346 ///
347 /// # Panics
348 /// Panics if next_index >= capacity
349 ///
350 /// # Examples
351 ///
352 /// ```
353 /// use array_linked_list::ArrayLinkedList;
354 ///
355 /// let mut array = ArrayLinkedList::new();
356 ///
357 /// let first = array.push_back(1);
358 /// let second = array.push_back(2);
359 /// let third = array.push_back(3);
360 ///
361 /// array.insert_before(second, 100);
362 ///
363 /// assert_eq!(array.pop_front(), Some(1));
364 /// assert_eq!(array.pop_front(), Some(100));
365 /// assert_eq!(array.pop_front(), Some(2));
366 /// assert_eq!(array.pop_front(), Some(3));
367 /// assert_eq!(array.pop_front(), None);
368 /// ```
369 pub fn insert_before(&mut self, next_index: usize, value: T) -> Option<usize> {
370 let LinkedListNode {
371 prev_index, data, ..
372 } = &self.elements[next_index];
373
374 if data.is_some() {
375 let prev_index = *prev_index;
376 Some(self.insert_between(prev_index, next_index + 1, value))
377 } else {
378 None
379 }
380 }
381
382 #[inline]
383 fn prev_of_next(&mut self, index: usize, active: bool) -> &mut usize {
384 if index > 0 {
385 &mut self.elements[index - 1].prev_index
386 } else if active {
387 &mut self.last_index
388 } else {
389 &mut self.end_index
390 }
391 }
392
393 #[inline]
394 fn next_of_prev(&mut self, index: usize, active: bool) -> &mut usize {
395 if index > 0 {
396 &mut self.elements[index - 1].next_index
397 } else if active {
398 &mut self.first_index
399 } else {
400 &mut self.free_index
401 }
402 }
403
404 fn connect_indices(&mut self, prev_index: usize, next_index: usize, active: bool) {
405 *self.prev_of_next(next_index, active) = prev_index;
406 *self.next_of_prev(prev_index, active) = next_index;
407 }
408
409 /// Removes the element at the given index and returns it, or `None` if it is empty.
410 /// The indices of other items are not changed.
411 /// Indices, which have never been used (see `capacity`), will not be available, but panic instead.
412 ///
413 /// Indices are not the position they appear in, when iterating over them.
414 /// So you can't use enumerate to get the index to delete.
415 /// But the iteration order of the elements (in both directions) is preserved.
416 /// See the module description for more information.
417 ///
418 /// This operation should compute in *O*(1) time.
419 ///
420 /// # Panics
421 /// Panics if index >= capacity
422 ///
423 /// # Examples
424 ///
425 /// ```
426 /// use array_linked_list::ArrayLinkedList;
427 ///
428 /// let mut array = ArrayLinkedList::new();
429 ///
430 /// let first = array.push_front(1);
431 /// let second = array.push_back(2);
432 /// let third = array.push_front(3);
433 ///
434 ///
435 /// assert_eq!(array.len(), 3);
436 ///
437 /// assert_eq!(array.remove(second).unwrap(), 2);
438 /// assert_eq!(array[second], None);
439 /// assert_eq!(array.len(), 2);
440 /// assert_eq!(array.remove(second), None);
441 /// assert_eq!(array.len(), 2);
442 ///
443 /// assert_eq!(array.remove(first).unwrap(), 1);
444 /// assert_eq!(array.len(), 1);
445 /// assert_eq!(array.remove(third).unwrap(), 3);
446 /// assert_eq!(array.len(), 0);
447 /// assert!(array.is_empty());
448 /// ```
449 pub fn remove(&mut self, index: usize) -> Option<T> {
450 let LinkedListNode {
451 next_index,
452 prev_index,
453 data,
454 } = mem::replace(
455 &mut self.elements[index],
456 LinkedListNode::deleted(self.free_index),
457 );
458
459 let removed = data.is_some();
460 self.connect_indices(prev_index, next_index, removed);
461
462 if removed {
463 self.count -= 1;
464 }
465
466 if self.free_index > 0 {
467 self.elements[self.free_index - 1].prev_index = index + 1;
468 }
469 self.free_index = index + 1;
470 data
471 }
472
473 /// Adds element at specified index at the front of the list.
474 /// Useful for updating contents.
475 ///
476 /// It basically does the same as `remove` and `push_back`, even if the specified index is already removed.
477 ///
478 /// # Panics
479 /// Panics if index >= capacity
480 ///
481 /// # Examples
482 ///
483 /// ```
484 /// use array_linked_list::ArrayLinkedList;
485 ///
486 /// let mut array = ArrayLinkedList::new();
487 ///
488 /// array.push_front(1);
489 /// let first_index = array.push_back(2);
490 /// array.push_front(3);
491 /// let second_index = array.push_front(4);
492 /// array.push_back(5);
493 ///
494 /// let mut array2 = array.clone();
495 /// assert_eq!(array, array2);
496 ///
497 /// let first_element = array.replace_front(first_index, 100);
498 /// let first_element2 = array2.remove(first_index);
499 /// array2.push_front(100);
500 /// assert_eq!(first_element, first_element2);
501 /// assert_eq!(array, array2);
502 ///
503 /// let second_element = array.replace_front(first_index, 0);
504 /// let second_element2 = array2.remove(first_index);
505 /// array2.push_back(0);
506 /// assert_eq!(second_element, second_element2);
507 /// assert_ne!(array, array2);
508 ///
509 /// assert_eq!(array.len(), 5);
510 /// assert_eq!(array2.len(), 5);
511 /// ```
512 pub fn replace_front(&mut self, index: usize, value: T) -> Option<T> {
513 let LinkedListNode {
514 next_index,
515 prev_index,
516 data,
517 } = mem::replace(
518 &mut self.elements[index],
519 LinkedListNode::front(self.first_index, value),
520 );
521
522 let removed = data.is_some();
523 self.connect_indices(prev_index, next_index, removed);
524
525 if !removed {
526 self.count += 1;
527 }
528
529 if self.first_index > 0 {
530 self.elements[self.first_index - 1].prev_index = index + 1;
531 }
532
533 self.first_index = index + 1;
534 data
535 }
536
537 /// Adds element at specified index at the front of the list.
538 /// Useful for updating contents.
539 ///
540 /// It basically does the same as `remove` and `push_back`, even if the specified index is already removed.
541 ///
542 /// # Panics
543 /// Panics if index >= capacity
544 ///
545 /// # Examples
546 ///
547 /// ```
548 /// use array_linked_list::ArrayLinkedList;
549 ///
550 /// let mut array = ArrayLinkedList::new();
551 ///
552 /// array.push_front(1);
553 /// array.push_back(2);
554 /// let middle_index = array.push_back(3);
555 /// array.push_front(4);
556 /// array.push_back(5);
557 ///
558 /// let mut array2 = array.clone();
559 /// assert_eq!(array, array2);
560 ///
561 /// let element = array.replace_back(middle_index, 100);
562 /// let element2 = array2.remove(middle_index);
563 /// array2.push_back(100);
564 /// assert_eq!(element, element2);
565 /// assert_eq!(array, array2);
566 ///
567 /// assert_eq!(array.len(), 5);
568 /// assert_eq!(array2.len(), 5);
569 /// ```
570 pub fn replace_back(&mut self, index: usize, value: T) -> Option<T> {
571 let LinkedListNode {
572 next_index,
573 prev_index,
574 data,
575 } = mem::replace(
576 &mut self.elements[index],
577 LinkedListNode::back(self.last_index, value),
578 );
579
580 let removed = data.is_some();
581 self.connect_indices(prev_index, next_index, removed);
582
583 if !removed {
584 self.count += 1;
585 }
586
587 if self.last_index > 0 {
588 self.elements[self.last_index - 1].next_index = index + 1;
589 }
590
591 self.last_index = index + 1;
592 data
593 }
594
595 /// Removes the first element from the array and returns it, or `None` if it is empty.
596 ///
597 /// This operation should compute in *O*(1) time.
598 ///
599 /// # Examples
600 ///
601 /// ```
602 /// use array_linked_list::ArrayLinkedList;
603 ///
604 /// let mut array = ArrayLinkedList::new();
605 /// assert_eq!(array.pop_front(), None);
606 /// array.push_back(1);
607 /// array.push_back(3);
608 /// assert_eq!(array.pop_front(), Some(1));
609 /// ```
610 pub fn pop_front(&mut self) -> Option<T> {
611 if self.first_index == 0 {
612 return None;
613 }
614 let index = self.first_index - 1;
615 let LinkedListNode {
616 next_index, data, ..
617 } = mem::replace(
618 &mut self.elements[index],
619 LinkedListNode::deleted(self.free_index),
620 );
621
622 *self.prev_of_next(next_index, true) = 0;
623 self.first_index = next_index;
624
625 self.count -= 1;
626 if self.free_index > 0 {
627 self.elements[self.free_index - 1].prev_index = index;
628 }
629 self.free_index = index;
630 Some(data.unwrap_or_else(|| unsafe { hint::unreachable_unchecked() }))
631 }
632
633 /// Removes the last element from the array and returns it, or `None` if it is empty.
634 ///
635 /// This operation should compute in *O*(1) time.
636 ///
637 /// # Examples
638 ///
639 /// ```
640 /// use array_linked_list::ArrayLinkedList;
641 ///
642 /// let mut array = ArrayLinkedList::new();
643 /// assert_eq!(array.pop_back(), None);
644 /// array.push_back(1);
645 /// array.push_back(3);
646 /// assert_eq!(array.pop_back(), Some(3));
647 /// ```
648 pub fn pop_back(&mut self) -> Option<T> {
649 if self.last_index == 0 {
650 return None;
651 }
652 let index = self.last_index - 1;
653 let LinkedListNode {
654 prev_index, data, ..
655 } = mem::replace(
656 &mut self.elements[index],
657 LinkedListNode::deleted(self.free_index),
658 );
659
660 self.last_index = prev_index;
661 *self.next_of_prev(prev_index, true) = 0;
662
663 self.count -= 1;
664 if self.free_index > 0 {
665 self.elements[self.free_index - 1].prev_index = index;
666 }
667 self.free_index = index;
668 Some(data.unwrap_or_else(|| unsafe { hint::unreachable_unchecked() }))
669 }
670
671 /// The index of the first list element.
672 /// Returns `None` if array is empty.
673 pub fn front_index(&self) -> Option<usize> {
674 if self.first_index > 0 {
675 Some(self.first_index - 1)
676 } else {
677 None
678 }
679 }
680
681 /// The index of the last list element.
682 /// Returns `None` if array is empty.
683 pub fn back_index(&self) -> Option<usize> {
684 if self.last_index > 0 {
685 Some(self.last_index - 1)
686 } else {
687 None
688 }
689 }
690
691 /// The first list element.
692 /// Returns `None` if array is empty.
693 pub fn front(&self) -> Option<&T> {
694 if self.first_index > 0 {
695 Some(
696 self.elements[self.first_index - 1]
697 .data
698 .as_ref()
699 .unwrap_or_else(|| unsafe { hint::unreachable_unchecked() }),
700 )
701 } else {
702 None
703 }
704 }
705
706 /// The last list element.
707 /// Returns `None` if array is empty.
708 pub fn back(&self) -> Option<&T> {
709 if self.last_index > 0 {
710 Some(
711 self.elements[self.last_index - 1]
712 .data
713 .as_ref()
714 .unwrap_or_else(|| unsafe { hint::unreachable_unchecked() }),
715 )
716 } else {
717 None
718 }
719 }
720
721 /// The first list element as a mutable reference.
722 /// Returns `None` if array is empty.
723 pub fn front_mut(&mut self) -> Option<&mut T> {
724 if self.first_index > 0 {
725 Some(
726 self.elements[self.first_index - 1]
727 .data
728 .as_mut()
729 .unwrap_or_else(|| unsafe { hint::unreachable_unchecked() }),
730 )
731 } else {
732 None
733 }
734 }
735
736 /// The last list element as a mutable reference.
737 /// Returns `None` if array is empty.
738 pub fn back_mut(&mut self) -> Option<&mut T> {
739 if self.last_index > 0 {
740 Some(
741 self.elements[self.last_index - 1]
742 .data
743 .as_mut()
744 .unwrap_or_else(|| unsafe { hint::unreachable_unchecked() }),
745 )
746 } else {
747 None
748 }
749 }
750
751 /// Checks if the list is empty.
752 pub fn is_empty(&self) -> bool {
753 self.first_index == 0 && self.last_index == 0
754 }
755
756 /// Clears the linked array, removing all values.
757 ///
758 /// Note that this method has no effect on the allocated capacity of the array.
759 /// So all indices, which have already been used (see `capacity`), are still available.
760 pub fn clear(&mut self) {
761 self.count = 0;
762 self.first_index = 0;
763 self.last_index = 0;
764 self.free_index = 0;
765 self.end_index = 0;
766
767 let capacity = self.elements.len();
768 self.elements.clear();
769 self.fill_elements(capacity);
770 }
771
772 /// Returns the number of elements in the linked array.
773 pub fn len(&self) -> usize {
774 self.count
775 }
776
777 /// Returns the number of elements the vector can hold without reallocating.
778 ///
779 /// Methods, which take indices, require the specified index to be below the capacity.
780 ///
781 /// All the following methods require indices:
782 ///
783 /// * `insert_before`
784 /// * `insert_after`
785 /// * `remove`
786 /// * `replace_front`
787 /// * `replace_back`
788 ///
789 /// Besides that, some of the iterators are constructed using indices in the same range.
790 pub fn capacity(&self) -> usize {
791 self.elements.len()
792 }
793
794 /// Returns a borrowing iterator over its elements.
795 pub fn iter<'a>(&'a self) -> impl Iterator<Item = &'a T> + DoubleEndedIterator {
796 Values(Indexed::new(self))
797 }
798
799 /// Returns a borrowing iterator over its indexed elements.
800 pub fn indexed<'a>(&'a self) -> impl Iterator<Item = (usize, &'a T)> + DoubleEndedIterator {
801 Indexed::new(self)
802 }
803
804 /// Returns a borrowing iterator over its indices.
805 pub fn indices<'a>(&'a self) -> impl Iterator<Item = usize> + DoubleEndedIterator + 'a {
806 Indices(Indexed::new(self))
807 }
808
809 /// Returns a borrowing iterator over its elements, starting after the element at the specified index.
810 ///
811 /// # Panics
812 /// Panics if index >= capacity
813 pub fn iter_after<'a>(
814 &'a self,
815 index: usize,
816 ) -> impl Iterator<Item = &'a T> + DoubleEndedIterator {
817 Values(Indexed::after(self, index))
818 }
819
820 /// Returns a borrowing iterator over its indexed elements, starting after the element at the specified index.
821 ///
822 /// # Panics
823 /// Panics if index >= capacity
824 pub fn indexed_after<'a>(
825 &'a self,
826 index: usize,
827 ) -> impl Iterator<Item = (usize, &'a T)> + DoubleEndedIterator {
828 Indexed::after(self, index)
829 }
830
831 /// Returns a borrowing iterator over its indices, starting after the element at the specified index.
832 ///
833 /// # Panics
834 /// Panics if index >= capacity
835 pub fn indices_after<'a>(
836 &'a self,
837 index: usize,
838 ) -> impl Iterator<Item = usize> + DoubleEndedIterator + 'a {
839 Indices(Indexed::after(self, index))
840 }
841
842 /// Returns a borrowing iterator over its elements, ending before the element at the specified index.
843 ///
844 /// # Panics
845 /// Panics if index >= capacity
846 pub fn iter_before<'a>(
847 &'a self,
848 index: usize,
849 ) -> impl Iterator<Item = &'a T> + DoubleEndedIterator {
850 Values(Indexed::before(self, index))
851 }
852
853 /// Returns a borrowing iterator over its indexed elements, ending before the element at the specified index.
854 ///
855 /// # Panics
856 /// Panics if index >= capacity
857 pub fn indexed_before<'a>(
858 &'a self,
859 index: usize,
860 ) -> impl Iterator<Item = (usize, &'a T)> + DoubleEndedIterator {
861 Indexed::before(self, index)
862 }
863
864 /// Returns a borrowing iterator over its indices, ending before the element at the specified index.
865 ///
866 /// # Panics
867 /// Panics if index >= capacity
868 pub fn indices_before<'a>(
869 &'a self,
870 index: usize,
871 ) -> impl Iterator<Item = usize> + DoubleEndedIterator + 'a {
872 Indices(Indexed::before(self, index))
873 }
874
875 /// Returns an owning iterator returning its indexed elements.
876 pub fn into_indexed(self) -> impl Iterator<Item = (usize, T)> + DoubleEndedIterator {
877 IntoIndexed(self)
878 }
879
880 /// Returns an owning iterator returning its indices.
881 pub fn into_indices(self) -> impl Iterator<Item = usize> + DoubleEndedIterator {
882 IntoIndices(IntoIndexed(self))
883 }
884}
885
886impl<T> Index<usize> for ArrayLinkedList<T> {
887 type Output = Option<T>;
888 fn index(&self, index: usize) -> &Option<T> {
889 &self.elements[index].data
890 }
891}
892
893impl<T> IndexMut<usize> for ArrayLinkedList<T> {
894 fn index_mut(&mut self, index: usize) -> &mut Option<T> {
895 &mut self.elements[index].data
896 }
897}
898
899struct Indexed<'a, T> {
900 front_index: usize,
901 back_index: usize,
902 array: &'a ArrayLinkedList<T>,
903}
904
905impl<'a, T> Indexed<'a, T> {
906 fn empty(array: &'a ArrayLinkedList<T>) -> Self {
907 Self {
908 front_index: 0,
909 back_index: 0,
910 array,
911 }
912 }
913
914 fn new(array: &'a ArrayLinkedList<T>) -> Self {
915 Self {
916 front_index: array.first_index,
917 back_index: array.last_index,
918 array,
919 }
920 }
921
922 fn after(array: &'a ArrayLinkedList<T>, prev_index: usize) -> Self {
923 let element = &array.elements[prev_index];
924 if element.data.is_some() {
925 Self {
926 front_index: element.next_index,
927 back_index: array.last_index,
928 array,
929 }
930 } else {
931 Self::empty(array)
932 }
933 }
934
935 fn before(array: &'a ArrayLinkedList<T>, next_index: usize) -> Self {
936 let element = &array.elements[next_index];
937 if element.data.is_some() {
938 Self {
939 front_index: array.first_index,
940 back_index: element.prev_index,
941 array,
942 }
943 } else {
944 Self::empty(array)
945 }
946 }
947}
948
949struct Indices<'a, T>(Indexed<'a, T>);
950
951/// Borrowing iterator over values of the linked array.
952pub struct Values<'a, T>(Indexed<'a, T>);
953
954impl<'a, T> Iterator for Indexed<'a, T> {
955 type Item = (usize, &'a T);
956 #[inline]
957 fn next(&mut self) -> Option<Self::Item> {
958 if self.front_index > 0 {
959 let index = self.front_index - 1;
960 let element = &self.array.elements[index];
961 if self.front_index == self.back_index {
962 self.front_index = 0;
963 self.back_index = 0;
964 } else {
965 self.front_index = element.next_index;
966 }
967 Some((
968 index,
969 element
970 .data
971 .as_ref()
972 .unwrap_or_else(|| unsafe { hint::unreachable_unchecked() }),
973 ))
974 } else {
975 None
976 }
977 }
978}
979
980impl<'a, T> DoubleEndedIterator for Indexed<'a, T> {
981 #[inline]
982 fn next_back(&mut self) -> Option<Self::Item> {
983 if self.back_index > 0 {
984 let index = self.back_index - 1;
985 let element = &self.array.elements[index];
986 if self.front_index == self.back_index {
987 self.front_index = 0;
988 self.back_index = 0;
989 } else {
990 self.back_index = element.prev_index;
991 }
992 Some((
993 index,
994 element
995 .data
996 .as_ref()
997 .unwrap_or_else(|| unsafe { hint::unreachable_unchecked() }),
998 ))
999 } else {
1000 None
1001 }
1002 }
1003}
1004
1005impl<'a, T> Iterator for Indices<'a, T> {
1006 type Item = usize;
1007 fn next(&mut self) -> Option<Self::Item> {
1008 if let Some((index, _)) = self.0.next() {
1009 Some(index)
1010 } else {
1011 None
1012 }
1013 }
1014}
1015
1016impl<'a, T> DoubleEndedIterator for Indices<'a, T> {
1017 fn next_back(&mut self) -> Option<Self::Item> {
1018 if let Some((index, _)) = self.0.next_back() {
1019 Some(index)
1020 } else {
1021 None
1022 }
1023 }
1024}
1025
1026impl<'a, T> Iterator for Values<'a, T> {
1027 type Item = &'a T;
1028 fn next(&mut self) -> Option<Self::Item> {
1029 if let Some((_, value)) = self.0.next() {
1030 Some(value)
1031 } else {
1032 None
1033 }
1034 }
1035}
1036
1037impl<'a, T> DoubleEndedIterator for Values<'a, T> {
1038 fn next_back(&mut self) -> Option<Self::Item> {
1039 if let Some((_, value)) = self.0.next_back() {
1040 Some(value)
1041 } else {
1042 None
1043 }
1044 }
1045}
1046
1047impl<'a, T> IntoIterator for &'a ArrayLinkedList<T> {
1048 type Item = &'a T;
1049 type IntoIter = Values<'a, T>;
1050
1051 #[inline]
1052 fn into_iter(self) -> Self::IntoIter {
1053 Values(Indexed::new(self))
1054 }
1055}
1056
1057struct IntoIndexed<T>(ArrayLinkedList<T>);
1058struct IntoIndices<T>(IntoIndexed<T>);
1059
1060/// Owning iterator over values of the linked array.
1061pub struct IntoValues<T>(IntoIndexed<T>);
1062
1063impl<T> Iterator for IntoIndexed<T> {
1064 type Item = (usize, T);
1065 #[inline]
1066 fn next(&mut self) -> Option<Self::Item> {
1067 if self.0.first_index > 0 {
1068 let index = self.0.first_index - 1;
1069 let element = &mut self.0.elements[index];
1070 if self.0.first_index == self.0.last_index {
1071 self.0.first_index = 0;
1072 self.0.last_index = 0;
1073 } else {
1074 self.0.first_index = element.next_index;
1075 }
1076 Some((
1077 index,
1078 element
1079 .data
1080 .take()
1081 .unwrap_or_else(|| unsafe { hint::unreachable_unchecked() }),
1082 ))
1083 } else {
1084 None
1085 }
1086 }
1087}
1088
1089impl<T> DoubleEndedIterator for IntoIndexed<T> {
1090 fn next_back(&mut self) -> Option<Self::Item> {
1091 if self.0.first_index > 0 {
1092 let index = self.0.first_index - 1;
1093 let element = &mut self.0.elements[index];
1094 if self.0.first_index == self.0.last_index {
1095 self.0.first_index = 0;
1096 self.0.last_index = 0;
1097 } else {
1098 self.0.first_index = element.next_index;
1099 }
1100 Some((
1101 index,
1102 element
1103 .data
1104 .take()
1105 .unwrap_or_else(|| unsafe { hint::unreachable_unchecked() }),
1106 ))
1107 } else {
1108 None
1109 }
1110 }
1111}
1112
1113impl<T> Iterator for IntoIndices<T> {
1114 type Item = usize;
1115 fn next(&mut self) -> Option<Self::Item> {
1116 if let Some((index, _)) = self.0.next() {
1117 Some(index)
1118 } else {
1119 None
1120 }
1121 }
1122}
1123
1124impl<T> DoubleEndedIterator for IntoIndices<T> {
1125 fn next_back(&mut self) -> Option<Self::Item> {
1126 if let Some((index, _)) = self.0.next_back() {
1127 Some(index)
1128 } else {
1129 None
1130 }
1131 }
1132}
1133
1134impl<T> Iterator for IntoValues<T> {
1135 type Item = T;
1136 fn next(&mut self) -> Option<Self::Item> {
1137 if let Some((_, value)) = self.0.next() {
1138 Some(value)
1139 } else {
1140 None
1141 }
1142 }
1143}
1144
1145impl<T> DoubleEndedIterator for IntoValues<T> {
1146 fn next_back(&mut self) -> Option<Self::Item> {
1147 if let Some((_, value)) = self.0.next_back() {
1148 Some(value)
1149 } else {
1150 None
1151 }
1152 }
1153}
1154
1155impl<T> IntoIterator for ArrayLinkedList<T> {
1156 type Item = T;
1157 type IntoIter = IntoValues<T>;
1158
1159 fn into_iter(self) -> Self::IntoIter {
1160 IntoValues(IntoIndexed(self))
1161 }
1162}