index_list/lib.rs
1/*
2 * This Source Code Form is subject to the terms of the Mozilla Public
3 * License, v. 2.0. If a copy of the MPL was not distributed with this
4 * file, You can obtain one at https://mozilla.org/MPL/2.0/.
5 */
6//! A doubly-linked list implemented in safe Rust.
7//!
8//! The list elements are stored in a vector which provides an index to the
9//! element, where it stores the index of the next and previous element in the
10//! list. The index does not change as long as the element is not removed, even
11//! when the element changes its position in the list.
12//!
13//! A new IndexList can be created empty with the `new` method, or created from
14//! an existing vector with `IndexList::from`.
15//!
16#![no_std]
17#![cfg_attr(not(feature = "iter_mut"), forbid(unsafe_code))]
18extern crate alloc;
19
20pub mod listdrainiter;
21pub mod listindex;
22pub mod listiter;
23#[cfg(feature = "iter_mut")]
24pub mod listitermut;
25mod listnode;
26mod listends;
27
28use core::{cmp::Ordering, default::Default, fmt};
29use core::iter::{DoubleEndedIterator, Extend, FromIterator, FusedIterator};
30use alloc::{vec::Vec, string::String, format};
31use crate::{listnode::ListNode, listends::ListEnds};
32pub use crate::listindex::ListIndex as ListIndex;
33pub use crate::listiter::ListIter as ListIter;
34#[cfg(feature = "iter_mut")]
35pub use crate::listitermut::ListIterMut as ListIterMut;
36pub use crate::listdrainiter::ListDrainIter as ListDrainIter;
37pub type Index = ListIndex; // for backwards compatibility with 0.2.7
38
39/// Doubly-linked list implemented in safe Rust.
40#[derive(Debug, Clone)]
41pub struct IndexList<T> {
42 elems: Vec<Option<T>>,
43 nodes: Vec<ListNode>,
44 used: ListEnds,
45 free: ListEnds,
46 size: usize,
47}
48
49impl<T> Default for IndexList<T> {
50 fn default() -> Self {
51 IndexList::<T> {
52 elems: Vec::new(),
53 nodes: Vec::new(),
54 used: ListEnds::new(),
55 free: ListEnds::new(),
56 size: 0,
57 }
58 }
59}
60
61impl<T> IndexList<T> {
62 /// Creates a new empty index list.
63 ///
64 /// Example:
65 /// ```rust
66 /// use index_list::IndexList;
67 ///
68 /// let list = IndexList::<u64>::new();
69 /// ```
70 #[allow(dead_code)]
71 #[inline]
72 pub fn new() -> Self {
73 Default::default()
74 }
75 /// Creates an empty `IndexList` with at least the specified capacity.
76 ///
77 /// Example:
78 /// ```rust
79 /// use index_list::IndexList;
80 /// let list = IndexList::<u64>::with_capacity(233);
81 /// ```
82 #[inline]
83 pub fn with_capacity(capacity: usize) -> Self {
84 IndexList {
85 elems: Vec::with_capacity(capacity),
86 nodes: Vec::with_capacity(capacity),
87 used: ListEnds::new(),
88 free: ListEnds::new(),
89 size: 0,
90 }
91 }
92 /// Returns the current capacity of the list.
93 ///
94 /// This value is always greater than or equal to the length.
95 ///
96 /// Example:
97 /// ```rust
98 /// # use index_list::IndexList;
99 /// # let list = IndexList::<u64>::new();
100 /// let cap = list.capacity();
101 /// assert!(cap >= list.len());
102 /// ```
103 #[inline]
104 pub fn capacity(&self) -> usize {
105 self.elems.len()
106 }
107 /// Returns the number of valid elements in the list.
108 ///
109 /// This value is always less than or equal to the capacity.
110 ///
111 /// Example:
112 /// ```rust
113 /// # use index_list::IndexList;
114 /// # let mut list = IndexList::<u64>::new();
115 /// # list.insert_first(42);
116 /// let first = list.remove_first();
117 /// assert!(list.len() < list.capacity());
118 /// ```
119 #[inline]
120 pub fn len(&self) -> usize {
121 self.size
122 }
123 /// Clears the list be removing all elements, making it empty.
124 ///
125 /// Example:
126 /// ```rust
127 /// # use index_list::IndexList;
128 /// # let mut list = IndexList::<u64>::new();
129 /// list.clear();
130 /// assert!(list.is_empty());
131 /// ```
132 #[inline]
133 pub fn clear(&mut self) {
134 self.elems.clear();
135 self.nodes.clear();
136 self.used.clear();
137 self.free.clear();
138 self.size = 0;
139 }
140 /// Returns `true` when the list is empty.
141 ///
142 /// Example:
143 /// ```rust
144 /// # use index_list::IndexList;
145 /// let list = IndexList::<u64>::new();
146 /// assert!(list.is_empty());
147 /// ```
148 #[inline]
149 pub fn is_empty(&self) -> bool {
150 self.used.is_empty()
151 }
152 /// Returns `true` if the index is valid.
153 #[inline]
154 pub fn is_index_used(&self, index: ListIndex) -> bool {
155 self.get(index).is_some()
156 }
157 /// Returns the index of the first element, or `None` if the list is empty.
158 ///
159 /// Example:
160 /// ```rust
161 /// # use index_list::IndexList;
162 /// # let list = IndexList::<u64>::new();
163 /// let index = list.first_index();
164 /// ```
165 #[inline]
166 pub fn first_index(&self) -> ListIndex {
167 self.used.head
168 }
169 /// Returns the index of the last element, or `None` if the list is empty.
170 ///
171 /// Example:
172 /// ```rust
173 /// # use index_list::IndexList;
174 /// # let list = IndexList::<u64>::new();
175 /// let index = list.last_index();
176 /// ```
177 #[inline]
178 pub fn last_index(&self) -> ListIndex {
179 self.used.tail
180 }
181 /// Returns the index of the next element, after index, or `None` when the
182 /// end is reached.
183 ///
184 /// If index is `None` then the first index in the list is returned.
185 ///
186 /// *NOTE* that indexes are likely not sequential.
187 ///
188 /// Example:
189 /// ```rust
190 /// # use index_list::IndexList;
191 /// # let list = IndexList::<u64>::new();
192 /// let mut index = list.first_index();
193 /// while index.is_some() {
194 /// // Do something
195 /// index = list.next_index(index);
196 /// }
197 /// ```
198 #[inline]
199 pub fn next_index(&self, index: ListIndex) -> ListIndex {
200 if let Some(ndx) = index.get() {
201 if let Some(node) = self.nodes.get(ndx) {
202 node.next
203 } else {
204 ListIndex::new()
205 }
206 } else {
207 self.first_index()
208 }
209 }
210 /// Returns the index of the previous element, before index, or `None` when
211 /// the beginning is reached.
212 ///
213 /// If index is `None` then the last index in the list is returned.
214 ///
215 /// *NOTE* that indexes are likely not sequential.
216 ///
217 /// Example:
218 /// ```rust
219 /// # use index_list::IndexList;
220 /// # let list = IndexList::<u64>::new();
221 /// let mut index = list.last_index();
222 /// while index.is_some() {
223 /// // Do something
224 /// index = list.prev_index(index);
225 /// }
226 /// ```
227 #[inline]
228 pub fn prev_index(&self, index: ListIndex) -> ListIndex {
229 if let Some(ndx) = index.get() {
230 if let Some(node) = self.nodes.get(ndx) {
231 node.prev
232 } else {
233 ListIndex::new()
234 }
235 } else {
236 self.last_index()
237 }
238 }
239 /// Move to an index `steps` number of elements away. Positive numbers will
240 /// move in the next direction, while negative number in the prev direction.
241 ///
242 /// Returns the index `steps` elements away, or `None` when the end is
243 /// reached.
244 ///
245 /// *NOTE* that indexes are likely not sequential.
246 ///
247 /// Example:
248 /// ```rust
249 /// # use index_list::IndexList;
250 /// # let list = IndexList::from(&mut vec!["A", "B", "C", "D", "E"]);
251 /// let mut index = list.first_index();
252 /// index = list.move_index(index, 3);
253 /// // Do something with the 4:th element
254 /// # assert_eq!(list.get(index), Some(&"D"));
255 /// index = list.move_index(index, -2);
256 /// // Do something with the 2:nd element
257 /// # assert_eq!(list.get(index), Some(&"B"));
258 /// index = list.move_index(index, -2);
259 /// assert!(index.is_none());
260 /// ```
261 #[inline]
262 pub fn move_index(&self, index: ListIndex, steps: i32) -> ListIndex {
263 let mut index = index;
264 match steps.cmp(&0) {
265 Ordering::Greater => {
266 (0..steps).for_each(|_| {
267 index = self.next_index(index);
268 });
269 }
270 Ordering::Less => {
271 (0..-steps).for_each(|_| {
272 index = self.prev_index(index);
273 });
274 }
275 Ordering::Equal => (),
276 }
277 index
278 }
279 /// Make the index `this` (and associated element) come before the index `that` (and associated element).
280 ///
281 /// Returns `true` if the operation was successful. This will fail if either index is invalid or if `this` and `that`
282 /// are the same index.
283 ///
284 /// This is similar to calling `let elem = self.remove(this);` followed by `self.insert_before(that, elem)`
285 /// except that it doesn't invalidate or change the index `this`. That is, the index `this` is guaranteed
286 /// to still point to the same element `elem` after this operation completes.
287 ///
288 /// Example:
289 /// ```rust
290 /// # use index_list::IndexList;
291 /// let mut list = IndexList::from(&mut vec![1, 2, 3]);
292 /// let index = list.first_index();
293 /// let moved = list.shift_index_before(index, list.last_index());
294 /// assert!(moved);
295 /// assert_eq!(list.get(index), Some(&1));
296 /// assert_eq!(list.to_string(), "[2 >< 1 >< 3]");
297 /// ```
298 pub fn shift_index_before(&mut self, this: ListIndex, that: ListIndex) -> bool {
299 let valid = self.is_index_used(this) && self.is_index_used(that) && this != that;
300 if valid {
301 self.linkout_used(this);
302 self.linkin_this_before_that(this, that)
303 }
304 valid
305 }
306 /// Make the index `this` (and associated element) come after the index `that` (and associated element).
307 ///
308 /// Returns `true` if the operation was successful. This will fail if either index is invalid or if `this` and `that`
309 /// are the same index.
310 ///
311 /// This is similar to calling `let elem = self.remove(this);` followed by `self.insert_after(that, elem)`
312 /// except that it doesn't invalidate or change the index `this`. That is, the index `this` is guaranteed
313 /// to still point to the same element `elem` after this operation completes.
314 ///
315 /// Example:
316 /// ```rust
317 /// # use index_list::IndexList;
318 /// let mut list = IndexList::from(&mut vec![1, 2, 3]);
319 /// let index = list.first_index();
320 /// let next_index = list.next_index(index);
321 /// let moved = list.shift_index_after(index, next_index);
322 /// assert!(moved);
323 /// assert_eq!(list.get(index), Some(&1));
324 /// assert_eq!(list.to_string(), "[2 >< 1 >< 3]");
325 /// ```
326 pub fn shift_index_after(&mut self, this: ListIndex, that: ListIndex) -> bool {
327 let valid = self.is_index_used(this) && self.is_index_used(that) && this != that;
328 if valid {
329 self.linkout_used(this);
330 self.linkin_this_after_that(this, that)
331 }
332 valid
333 }
334 /// Make the index `this` (and associated element) come first in the list.
335 ///
336 /// Returns `true` if the operation was successful. This will fail if `this` is an invalid index.
337 ///
338 /// This is similar to calling `let elem = self.remove(this);` followed by `self.insert_first(elem)`
339 /// except that it doesn't invalidate or change the index `this`. That is, the index `this` is guaranteed
340 /// to still point to the same element `elem` after this operation completes.
341 ///
342 /// Example:
343 /// ```rust
344 /// # use index_list::IndexList;
345 /// let mut list = IndexList::from(&mut vec![1, 2, 3]);
346 /// let index = list.last_index();
347 /// let moved = list.shift_index_to_front(index);
348 /// assert!(moved);
349 /// assert_eq!(list.get(index), Some(&3));
350 /// assert_eq!(list.to_string(), "[3 >< 1 >< 2]");
351 /// ```
352 pub fn shift_index_to_front(&mut self, this: ListIndex) -> bool {
353 let valid = self.is_index_used(this);
354 if valid {
355 self.linkout_used(this);
356 self.linkin_first(this);
357 }
358 valid
359 }
360 /// Make the index `this` (and associated element) come last in the list.
361 ///
362 /// Returns `true` if the operation was successful. This will fail if `this` is an invalid index.
363 ///
364 /// This is similar to calling `let elem = self.remove(this);` followed by `self.insert_last(elem)`
365 /// except that it doesn't invalidate or change the index `this`. That is, the index `this` is guaranteed
366 /// to still point to the same element `elem` after this operation completes.
367 ///
368 /// Example:
369 /// ```rust
370 /// # use index_list::IndexList;
371 /// let mut list = IndexList::from(&mut vec![1, 2, 3]);
372 /// let index = list.first_index();
373 /// let moved = list.shift_index_to_back(index);
374 /// assert!(moved);
375 /// assert_eq!(list.get(index), Some(&1));
376 /// assert_eq!(list.to_string(), "[2 >< 3 >< 1]");
377 /// ```
378 pub fn shift_index_to_back(&mut self, this: ListIndex) -> bool {
379 let valid = self.is_index_used(this);
380 if valid {
381 self.linkout_used(this);
382 self.linkin_last(this);
383 }
384 valid
385 }
386 /// Get a reference to the first element data, or `None`.
387 ///
388 /// Example:
389 /// ```rust
390 /// # use index_list::IndexList;
391 /// # let list = IndexList::<u64>::new();
392 /// let data = list.get_first();
393 /// ```
394 #[inline]
395 pub fn get_first(&self) -> Option<&T> {
396 self.get(self.first_index())
397 }
398 /// Get a reference to the last element data, or `None`.
399 ///
400 /// Example:
401 /// ```rust
402 /// # use index_list::IndexList;
403 /// # let list = IndexList::<u64>::new();
404 /// let data = list.get_last();
405 /// ```
406 #[inline]
407 pub fn get_last(&self) -> Option<&T> {
408 self.get(self.last_index())
409 }
410 /// Get an immutable reference to the element data at the index, or `None`.
411 ///
412 /// Example:
413 /// ```rust
414 /// # use index_list::IndexList;
415 /// # let list = IndexList::<u64>::new();
416 /// # let index = list.first_index();
417 /// let data = list.get(index);
418 /// ```
419 #[inline]
420 pub fn get(&self, index: ListIndex) -> Option<&T> {
421 let ndx = index.get().unwrap_or(usize::MAX);
422 self.elems.get(ndx)?.as_ref()
423 }
424 /// Get a mutable reference to the first element data, or `None`.
425 ///
426 /// Example:
427 /// ```rust
428 /// # use index_list::IndexList;
429 /// # let mut list = IndexList::<u64>::new();
430 /// # list.insert_first(1);
431 /// if let Some(data) = list.get_mut_first() {
432 /// // Update the data somehow
433 /// *data = 0;
434 /// }
435 /// # assert_eq!(list.get_first(), Some(&0u64));
436 /// ```
437 #[inline]
438 pub fn get_mut_first(&mut self) -> Option<&mut T> {
439 self.get_mut(self.first_index())
440 }
441 /// Get a mutable reference to the last element data, or `None`.
442 ///
443 /// Example:
444 /// ```rust
445 /// # use index_list::IndexList;
446 /// # let mut list = IndexList::<u64>::new();
447 /// # list.insert_first(2);
448 /// if let Some(data) = list.get_mut_last() {
449 /// // Update the data somehow
450 /// *data *= 2;
451 /// }
452 /// # assert_eq!(list.get_last(), Some(&4u64));
453 /// ```
454 #[inline]
455 pub fn get_mut_last(&mut self) -> Option<&mut T> {
456 self.get_mut(self.last_index())
457 }
458 /// Get a mutable reference to the element data at the index, or `None`.
459 ///
460 /// Example:
461 /// ```rust
462 /// # use index_list::IndexList;
463 /// # let mut list = IndexList::<u64>::new();
464 /// # list.insert_first(0);
465 /// # let index = list.first_index();
466 /// if let Some(data) = list.get_mut(index) {
467 /// // Update the data somehow
468 /// *data += 1;
469 /// }
470 /// # assert_eq!(list.get_last(), Some(&1u64));
471 /// ```
472 #[inline]
473 pub fn get_mut(&mut self, index: ListIndex) -> Option<&mut T> {
474 if let Some(ndx) = index.get() {
475 if ndx < self.capacity() {
476 return self.elems[ndx].as_mut();
477 }
478 }
479 None
480 }
481 /// Swap the element data between two indexes.
482 ///
483 /// Both indexes must be valid.
484 ///
485 /// Example:
486 /// ```rust
487 /// # use index_list::IndexList;
488 /// # let mut list = IndexList::<u64>::new();
489 /// # list.insert_first(1);
490 /// # list.insert_last(2);
491 /// list.swap_index(list.first_index(), list.last_index());
492 /// # assert_eq!(list.get_first(), Some(&2u64));
493 /// # assert_eq!(list.get_last(), Some(&1u64));
494 /// ```
495 #[inline]
496 pub fn swap_index(&mut self, this: ListIndex, that: ListIndex) {
497 if let Some(here) = this.get() {
498 if let Some(there) = that.get() {
499 self.swap_data(here, there);
500 }
501 }
502 }
503 /// Peek at next element data, after the index, if any.
504 ///
505 /// Returns `None` if there is no next index in the list.
506 ///
507 /// Example:
508 /// ```rust
509 /// # use index_list::IndexList;
510 /// # let mut list = IndexList::from(&mut vec![1, 2, 3]);
511 /// # let index = list.first_index();
512 /// if let Some(data) = list.peek_next(index) {
513 /// // Consider the next data
514 /// # assert_eq!(*data, 2);
515 /// }
516 /// ```
517 #[inline]
518 pub fn peek_next(&self, index: ListIndex) -> Option<&T> {
519 self.get(self.next_index(index))
520 }
521 /// Peek at previous element data, before the index, if any.
522 ///
523 /// Returns `None` if there is no previous index in the list.
524 ///
525 /// Example:
526 /// ```rust
527 /// # use index_list::IndexList;
528 /// # let mut list = IndexList::from(&mut vec![1, 2, 3]);
529 /// # let index = list.last_index();
530 /// if let Some(data) = list.peek_prev(index) {
531 /// // Consider the previous data
532 /// # assert_eq!(*data, 2);
533 /// }
534 /// ```
535 #[inline]
536 pub fn peek_prev(&self, index: ListIndex) -> Option<&T> {
537 self.get(self.prev_index(index))
538 }
539 /// Returns `true` if the element is in the list.
540 ///
541 /// Example:
542 /// ```rust
543 /// # use index_list::IndexList;
544 /// # let mut list = IndexList::<u64>::new();
545 /// # let index = list.insert_first(42);
546 /// if list.contains(42) {
547 /// // Find it?
548 /// } else {
549 /// // Insert it?
550 /// }
551 /// ```
552 #[inline]
553 pub fn contains(&self, elem: T) -> bool
554 where T: PartialEq {
555 self.elems.contains(&Some(elem))
556 }
557 /// Returns the index of the element containg the data.
558 ///
559 /// If there is more than one element with the same data, the one with the
560 /// lowest index will always be returned.
561 ///
562 /// Example:
563 /// ```rust
564 /// # use index_list::{ListIndex, IndexList};
565 /// # let mut list = IndexList::from(&mut vec![1, 2, 3]);
566 /// let index = list.index_of(2);
567 /// # assert_eq!(index, ListIndex::from(1u32))
568 /// ```
569 #[inline]
570 pub fn index_of(&self, elem: T) -> ListIndex
571 where T: PartialEq {
572 ListIndex::from(self.elems.iter().position(|e| {
573 if let Some(data) = e {
574 data == &elem
575 } else {
576 false
577 }
578 }))
579 }
580 /// Insert a new element at the beginning.
581 ///
582 /// It is usually not necessary to keep the index, as the element data
583 /// can always be found again by walking the list.
584 ///
585 /// Example:
586 /// ```rust
587 /// # use index_list::IndexList;
588 /// # let mut list = IndexList::<u64>::new();
589 /// let index = list.insert_first(42);
590 /// ```
591 pub fn insert_first(&mut self, elem: T) -> ListIndex {
592 let this = self.new_node(Some(elem));
593 self.linkin_first(this);
594 this
595 }
596 /// Insert a new element at the end.
597 ///
598 /// It is typically not necessary to store the index, as the data will be
599 /// there when walking the list.
600 ///
601 /// Example:
602 /// ```rust
603 /// # use index_list::IndexList;
604 /// # let mut list = IndexList::<u64>::new();
605 /// let index = list.insert_last(42);
606 /// ```
607 pub fn insert_last(&mut self, elem: T) -> ListIndex {
608 let this = self.new_node(Some(elem));
609 self.linkin_last(this);
610 this
611 }
612 /// Insert a new element before the index.
613 ///
614 /// If the index is `None` then the new element will be inserted first.
615 ///
616 /// Example:
617 /// ```rust
618 /// # use index_list::IndexList;
619 /// # let mut list = IndexList::<u64>::new();
620 /// # let mut index = list.last_index();
621 /// index = list.insert_before(index, 42);
622 /// ```
623 pub fn insert_before(&mut self, index: ListIndex, elem: T) -> ListIndex {
624 if index.is_none() {
625 return self.insert_first(elem);
626 }
627 let this = self.new_node(Some(elem));
628 self.linkin_this_before_that(this, index);
629 this
630 }
631 /// Insert a new element after the index.
632 ///
633 /// If the index is `None` then the new element will be inserted last.
634 ///
635 /// Example:
636 /// ```rust
637 /// # use index_list::IndexList;
638 /// # let mut list = IndexList::<u64>::new();
639 /// # let mut index = list.first_index();
640 /// index = list.insert_after(index, 42);
641 /// ```
642 pub fn insert_after(&mut self, index: ListIndex, elem: T) -> ListIndex {
643 if index.is_none() {
644 return self.insert_last(elem);
645 }
646 let this = self.new_node(Some(elem));
647 self.linkin_this_after_that(this, index);
648 this
649 }
650 /// Remove the first element and return its data.
651 ///
652 /// Example:
653 /// ```rust
654 /// # use index_list::IndexList;
655 /// # let mut list = IndexList::<u64>::new();
656 /// # list.insert_first(42);
657 /// let data = list.remove_first();
658 /// # assert_eq!(data, Some(42));
659 /// ```
660 pub fn remove_first(&mut self) -> Option<T> {
661 self.remove(self.first_index())
662 }
663 /// Remove the last element and return its data.
664 ///
665 /// Example:
666 /// ```rust
667 /// # use index_list::IndexList;
668 /// # let mut list = IndexList::<u64>::new();
669 /// # list.insert_last(42);
670 /// let data = list.remove_last();
671 /// # assert_eq!(data, Some(42));
672 /// ```
673 pub fn remove_last(&mut self) -> Option<T> {
674 self.remove(self.last_index())
675 }
676 /// Remove the element at the index and return its data.
677 ///
678 /// Example:
679 /// ```rust
680 /// # use index_list::IndexList;
681 /// # let mut list = IndexList::from(&mut vec!["A", "B", "C"]);
682 /// # let mut index = list.first_index();
683 /// # index = list.next_index(index);
684 /// let data = list.remove(index);
685 /// # assert_eq!(data, Some("B"));
686 /// ```
687 pub fn remove(&mut self, index: ListIndex) -> Option<T> {
688 let elem_opt = self.remove_elem_at_index(index);
689 if elem_opt.is_some() {
690 self.linkout_used(index);
691 self.linkin_free(index);
692 }
693 elem_opt
694 }
695 /// Create a new iterator over all the elements.
696 ///
697 /// Example:
698 /// ```rust
699 /// # use index_list::IndexList;
700 /// # let mut list = IndexList::from(&mut vec![120, 240, 360]);
701 /// let total: usize = list.iter().sum();
702 /// assert_eq!(total, 720);
703 /// ```
704 #[inline]
705 pub fn iter(&self) -> ListIter<'_, T> {
706 ListIter {
707 list: self,
708 start: self.first_index(),
709 end: self.last_index(),
710 len: self.len(),
711 }
712 }
713 /// Create a new mutating iterator over all the elements.
714 ///
715 /// Example:
716 /// ```rust
717 /// # use index_list::IndexList;
718 /// # let mut list = IndexList::from(&mut vec![120, 240, 360]);
719 /// for elem in list.iter_mut() {
720 /// *elem *= 2;
721 /// }
722 /// assert_eq!(Vec::from_iter(list.drain_iter()), vec![240, 480, 720]);
723 /// ```
724 #[inline]
725 #[cfg(feature = "iter_mut")]
726 pub fn iter_mut(&mut self) -> ListIterMut<'_, T> {
727 ListIterMut {
728 start: self.first_index(),
729 end: self.last_index(),
730 len: self.len(),
731 elems: self.elems.as_mut_ptr(),
732 nodes: &self.nodes,
733 }
734 }
735 /// Create a draining iterator over all the elements.
736 ///
737 /// This iterator will remove the elements as it is iterating over them.
738 ///
739 /// Example:
740 /// ```rust
741 /// # use index_list::IndexList;
742 /// # let mut list = IndexList::from(&mut vec!["A", "B", "C"]);
743 /// let items: Vec<&str> = list.drain_iter().collect();
744 /// assert_eq!(list.len(), 0);
745 /// assert_eq!(items, vec!["A", "B", "C"]);
746 /// ```
747 #[inline]
748 pub fn drain_iter(&mut self) -> ListDrainIter<'_, T> {
749 ListDrainIter::new(self)
750 }
751 /// Create a vector for all elements.
752 ///
753 /// Returns a new vector with immutable reference to the elements data.
754 ///
755 /// Example:
756 /// ```rust
757 /// # use index_list::IndexList;
758 /// # let mut list = IndexList::from(&mut vec![1, 2, 3]);
759 /// let vector: Vec<&u64> = list.to_vec();
760 /// # assert_eq!(format!("{:?}", vector), "[1, 2, 3]");
761 /// ```
762 pub fn to_vec(&self) -> Vec<&T> {
763 self.iter().collect()
764 }
765 /// Insert all the elements from the vector, which will be drained.
766 ///
767 /// Example:
768 /// ```rust
769 /// # use index_list::IndexList;
770 /// let mut the_numbers = vec![4, 8, 15, 16, 23, 42];
771 /// let list = IndexList::from(&mut the_numbers);
772 /// assert_eq!(the_numbers.len(), 0);
773 /// assert_eq!(list.len(), 6);
774 /// ```
775 pub fn from(vec: &mut Vec<T>) -> IndexList<T> {
776 let mut list = IndexList::<T>::new();
777 vec.drain(..).for_each(|elem| {
778 list.insert_last(elem);
779 });
780 list
781 }
782 /// Remove any unused indexes at the end by truncating.
783 ///
784 /// If the unused indexes don't appear at the end, then nothing happens.
785 ///
786 /// No valid indexes are changed.
787 ///
788 /// Example:
789 /// ```rust
790 /// # use index_list::IndexList;
791 /// # let mut list = IndexList::from(&mut vec![4, 8, 15, 16, 23, 42]);
792 /// list.remove_last();
793 /// assert!(list.len() < list.capacity());
794 /// list.trim_safe();
795 /// assert_eq!(list.len(), list.capacity());
796 /// ```
797 pub fn trim_safe(&mut self) {
798 let removed: Vec<usize> = (self.len()..self.capacity())
799 .rev()
800 .take_while(|&i| self.is_free(i))
801 .collect();
802 removed.iter().for_each(|&i| {
803 self.linkout_free(ListIndex::from(i));
804 });
805 if !removed.is_empty() {
806 let left = self.capacity() - removed.len();
807 self.nodes.truncate(left);
808 self.elems.truncate(left);
809 }
810 }
811 /// Remove all unused elements by swapping indexes and then truncating.
812 ///
813 /// This will reduce the capacity of the list, but only if there are any
814 /// unused elements. Length and capacity will be equal after the call.
815 ///
816 /// *NOTE* that this call may invalidate some indexes.
817 ///
818 /// While it is possible to tell if an index has become invalid, because
819 /// only indexes at or above the new capacity limit has been moved, it is
820 /// not recommended to rely on that fact or test for it.
821 ///
822 /// Example:
823 /// ```rust
824 /// # use index_list::IndexList;
825 /// # let mut list = IndexList::from(&mut vec![4, 8, 15, 16, 23, 42]);
826 /// list.remove_first();
827 /// assert!(list.len() < list.capacity());
828 /// list.trim_swap();
829 /// assert_eq!(list.len(), list.capacity());
830 /// ```
831 pub fn trim_swap(&mut self) {
832 let need = self.size;
833 // destination is all free node indexes below the needed limit
834 let dst: Vec<usize> = self.elems[..need]
835 .iter()
836 .enumerate()
837 .filter(|(n, e)| e.is_none() && n < &need)
838 .map(|(n, _e)| n)
839 .collect();
840 // source is all used node indexes above the needed limit
841 let src: Vec<usize> = self.elems[need..]
842 .iter()
843 .enumerate()
844 .filter(|(_n, e)| e.is_some())
845 .map(|(n, _e)| n + need)
846 .collect();
847 debug_assert_eq!(dst.len(), src.len());
848 src.iter()
849 .zip(dst.iter())
850 .for_each(|(s, d)| self.replace_dest_with_source(*s, *d));
851 self.free.new_both(ListIndex::new());
852 self.elems.truncate(need);
853 self.nodes.truncate(need);
854 }
855 /// Add the elements of the other list at the end.
856 ///
857 /// The other list will be empty after the call as all its elements have
858 /// been moved to this list.
859 ///
860 /// Example:
861 /// ```rust
862 /// # use index_list::IndexList;
863 /// # let mut list = IndexList::from(&mut vec![4, 8, 15]);
864 /// # let mut other = IndexList::from(&mut vec![16, 23, 42]);
865 /// let sum_both = list.len() + other.len();
866 /// list.append(&mut other);
867 /// assert!(other.is_empty());
868 /// assert_eq!(list.len(), sum_both);
869 /// # assert_eq!(list.to_string(), "[4 >< 8 >< 15 >< 16 >< 23 >< 42]");
870 /// ```
871 pub fn append(&mut self, other: &mut IndexList<T>) {
872 while let Some(elem) = other.remove_first() {
873 self.insert_last(elem);
874 }
875 }
876 /// Add the elements of the other list at the beginning.
877 ///
878 /// The other list will be empty after the call as all its elements have
879 /// been moved to this list.
880 ///
881 /// Example:
882 /// ```rust
883 /// # use index_list::IndexList;
884 /// # let mut list = IndexList::from(&mut vec![16, 23, 42]);
885 /// # let mut other = IndexList::from(&mut vec![4, 8, 15]);
886 /// let sum_both = list.len() + other.len();
887 /// list.prepend(&mut other);
888 /// assert!(other.is_empty());
889 /// assert_eq!(list.len(), sum_both);
890 /// # assert_eq!(list.to_string(), "[4 >< 8 >< 15 >< 16 >< 23 >< 42]");
891 /// ```
892 pub fn prepend(&mut self, other: &mut IndexList<T>) {
893 while let Some(elem) = other.remove_last() {
894 self.insert_first(elem);
895 }
896 }
897 /// Split the list by moving the elements from the index to a new list.
898 ///
899 /// The original list will no longer contain the elements data that was
900 /// moved to the other list.
901 ///
902 /// Example:
903 /// ```rust
904 /// # use index_list::IndexList;
905 /// # let mut list = IndexList::from(&mut vec![4, 8, 15, 16, 23, 42]);
906 /// # let mut index = list.first_index();
907 /// # index = list.next_index(index);
908 /// # index = list.next_index(index);
909 /// # index = list.next_index(index);
910 /// let total = list.len();
911 /// let other = list.split(index);
912 /// assert!(list.len() < total);
913 /// assert_eq!(list.len() + other.len(), total);
914 /// # assert_eq!(list.to_string(), "[4 >< 8 >< 15]");
915 /// # assert_eq!(other.to_string(), "[16 >< 23 >< 42]");
916 /// ```
917 pub fn split(&mut self, index: ListIndex) -> IndexList<T> {
918 let mut list = IndexList::<T>::new();
919 while self.is_index_used(index) {
920 list.insert_first(self.remove_last().unwrap());
921 }
922 list
923 }
924
925 #[inline]
926 fn is_used(&self, at: usize) -> bool {
927 self.elems[at].is_some()
928 }
929 fn is_free(&self, at: usize) -> bool {
930 self.elems[at].is_none()
931 }
932 #[inline]
933 fn get_mut_indexnode(&mut self, at: usize) -> &mut ListNode {
934 &mut self.nodes[at]
935 }
936 #[inline]
937 fn get_indexnode(&self, at: usize) -> &ListNode {
938 &self.nodes[at]
939 }
940 #[inline]
941 fn swap_data(&mut self, here: usize, there: usize) {
942 self.elems.swap(here, there);
943 }
944 #[inline]
945 fn set_prev(&mut self, index: ListIndex, new_prev: ListIndex) -> ListIndex {
946 if let Some(at) = index.get() {
947 self.get_mut_indexnode(at).new_prev(new_prev)
948 } else {
949 index
950 }
951 }
952 #[inline]
953 fn set_next(&mut self, index: ListIndex, new_next: ListIndex) -> ListIndex {
954 if let Some(at) = index.get() {
955 self.get_mut_indexnode(at).new_next(new_next)
956 } else {
957 index
958 }
959 }
960 #[inline]
961 fn linkin_tail(&mut self, prev: ListIndex, this: ListIndex, next: ListIndex) {
962 if next.is_none() {
963 let old_tail = self.used.new_tail(this);
964 debug_assert_eq!(old_tail, prev);
965 }
966 }
967 #[inline]
968 fn linkin_head(&mut self, prev: ListIndex, this: ListIndex, next: ListIndex) {
969 if prev.is_none() {
970 let old_head = self.used.new_head(this);
971 debug_assert_eq!(old_head, next);
972 }
973 }
974 #[inline]
975 fn insert_elem_at_index(&mut self, this: ListIndex, elem: Option<T>) {
976 if let Some(at) = this.get() {
977 self.elems[at] = elem;
978 self.size += 1;
979 }
980 }
981 #[inline]
982 fn remove_elem_at_index(&mut self, this: ListIndex) -> Option<T> {
983 let at = this.get()?;
984 let removed = self.elems[at].take()?;
985 self.size -= 1;
986 Some(removed)
987 }
988 fn new_node(&mut self, elem: Option<T>) -> ListIndex {
989 let reuse = self.free.head;
990 if reuse.is_some() {
991 self.insert_elem_at_index(reuse, elem);
992 self.linkout_free(reuse);
993 return reuse;
994 }
995 let pos = self.nodes.len();
996 self.nodes.push(ListNode::new());
997 self.elems.push(elem);
998 self.size += 1;
999 ListIndex::from(pos)
1000 }
1001 fn linkin_free(&mut self, this: ListIndex) {
1002 debug_assert!(!self.is_index_used(this));
1003 let prev = self.free.tail;
1004 self.set_next(prev, this);
1005 self.set_prev(this, prev);
1006 if self.free.is_empty() {
1007 self.free.new_both(this);
1008 } else {
1009 let old_tail = self.free.new_tail(this);
1010 debug_assert_eq!(old_tail, prev);
1011 }
1012 }
1013 fn linkin_first(&mut self, this: ListIndex) {
1014 debug_assert!(self.is_index_used(this));
1015 let next = self.used.head;
1016 self.set_prev(next, this);
1017 self.set_next(this, next);
1018 if self.used.is_empty() {
1019 self.used.new_both(this);
1020 } else {
1021 let old_head = self.used.new_head(this);
1022 debug_assert_eq!(old_head, next);
1023 }
1024 }
1025 fn linkin_last(&mut self, this: ListIndex) {
1026 debug_assert!(self.is_index_used(this));
1027 let prev = self.used.tail;
1028 self.set_next(prev, this);
1029 self.set_prev(this, prev);
1030 if self.used.is_empty() {
1031 self.used.new_both(this);
1032 } else {
1033 let old_tail = self.used.new_tail(this);
1034 debug_assert_eq!(old_tail, prev);
1035 }
1036 }
1037 // prev? >< that => prev? >< this >< that
1038 fn linkin_this_before_that(&mut self, this: ListIndex, that: ListIndex) {
1039 debug_assert!(self.is_index_used(this));
1040 debug_assert!(self.is_index_used(that));
1041 let prev = self.set_prev(that, this);
1042 let old_next = self.set_next(prev, this);
1043 if old_next.is_some() {
1044 debug_assert_eq!(old_next, that);
1045 }
1046 self.set_prev(this, prev);
1047 self.set_next(this, that);
1048 self.linkin_head(prev, this, that);
1049 }
1050 // that >< next? => that >< this >< next?
1051 fn linkin_this_after_that(&mut self, this: ListIndex, that: ListIndex) {
1052 debug_assert!(self.is_index_used(this));
1053 debug_assert!(self.is_index_used(that));
1054 let next = self.set_next(that, this);
1055 let old_prev = self.set_prev(next, this);
1056 if old_prev.is_some() {
1057 debug_assert_eq!(old_prev, that);
1058 }
1059 self.set_prev(this, that);
1060 self.set_next(this, next);
1061 self.linkin_tail(that, this, next);
1062 }
1063 // prev >< this >< next => prev >< next
1064 fn linkout_node(&mut self, this: ListIndex) -> (ListIndex, ListIndex) {
1065 let next = self.set_next(this, ListIndex::new());
1066 let prev = self.set_prev(this, ListIndex::new());
1067 let old_prev = self.set_prev(next, prev);
1068 if old_prev.is_some() {
1069 debug_assert_eq!(old_prev, this);
1070 }
1071 let old_next = self.set_next(prev, next);
1072 if old_next.is_some() {
1073 debug_assert_eq!(old_next, this);
1074 }
1075 (prev, next)
1076 }
1077 fn linkout_used(&mut self, this: ListIndex) {
1078 let (prev, next) = self.linkout_node(this);
1079 if next.is_none() {
1080 let old_tail = self.used.new_tail(prev);
1081 debug_assert_eq!(old_tail, this);
1082 }
1083 if prev.is_none() {
1084 let old_head = self.used.new_head(next);
1085 debug_assert_eq!(old_head, this);
1086 }
1087 }
1088 fn linkout_free(&mut self, this: ListIndex) {
1089 let (prev, next) = self.linkout_node(this);
1090 if next.is_none() {
1091 let old_tail = self.free.new_tail(prev);
1092 debug_assert_eq!(old_tail, this);
1093 }
1094 if prev.is_none() {
1095 let old_head = self.free.new_head(next);
1096 debug_assert_eq!(old_head, this);
1097 }
1098 }
1099 fn replace_dest_with_source(&mut self, src: usize, dst: usize) {
1100 debug_assert!(self.is_free(dst));
1101 debug_assert!(self.is_used(src));
1102 self.linkout_free(ListIndex::from(dst));
1103 let src_node = self.get_indexnode(src);
1104 let next = src_node.next;
1105 let prev = src_node.prev;
1106 self.linkout_used(ListIndex::from(src));
1107 self.elems[dst] = self.elems[src].take();
1108 let this = ListIndex::from(dst);
1109 if next.is_some() {
1110 self.linkin_this_before_that(this, next);
1111 } else if prev.is_some() {
1112 self.linkin_this_after_that(this, prev);
1113 } else {
1114 self.linkin_first(this);
1115 }
1116 }
1117}
1118
1119impl<T> fmt::Display for IndexList<T>
1120where
1121 T: fmt::Display,
1122{
1123 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1124 let elems: Vec<String> = self.iter().map(|x| format!("{}", x)).collect();
1125 write!(f, "[{}]", elems.join(" >< "))
1126 }
1127}
1128
1129impl<T> From<T> for IndexList<T> {
1130 fn from(elem: T) -> IndexList<T> {
1131 let mut list = IndexList::new();
1132 list.insert_last(elem);
1133 list
1134 }
1135}
1136
1137impl<T> FromIterator<T> for IndexList<T> {
1138 fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
1139 let mut list = IndexList::new();
1140 for elem in iter {
1141 list.insert_last(elem);
1142 }
1143 list
1144 }
1145}
1146
1147impl<T> Extend<T> for IndexList<T> {
1148 fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
1149 for elem in iter {
1150 self.insert_last(elem);
1151 }
1152 }
1153}
1154
1155impl<T: PartialEq> PartialEq for IndexList<T> {
1156 fn eq(&self, other: &Self) -> bool {
1157 self.len() == other.len() && self.iter().eq(other.iter())
1158 }
1159}
1160
1161impl<T: Eq> Eq for IndexList<T> {}
1162
1163/// An owning iterator over the elements of an `IndexList`.
1164pub struct IntoIter<T> {
1165 list: IndexList<T>,
1166}
1167
1168impl<T> Iterator for IntoIter<T> {
1169 type Item = T;
1170 #[inline]
1171 fn next(&mut self) -> Option<Self::Item> {
1172 self.list.remove_first()
1173 }
1174 #[inline]
1175 fn size_hint(&self) -> (usize, Option<usize>) {
1176 let len = self.list.len();
1177 (len, Some(len))
1178 }
1179}
1180
1181impl<T> DoubleEndedIterator for IntoIter<T> {
1182 #[inline]
1183 fn next_back(&mut self) -> Option<Self::Item> {
1184 self.list.remove_last()
1185 }
1186}
1187
1188impl<T> ExactSizeIterator for IntoIter<T> {}
1189impl<T> FusedIterator for IntoIter<T> {}
1190
1191impl<T> IntoIterator for IndexList<T> {
1192 type Item = T;
1193 type IntoIter = IntoIter<T>;
1194
1195 fn into_iter(self) -> Self::IntoIter {
1196 IntoIter { list: self }
1197 }
1198}
1199
1200#[cfg(test)]
1201mod tests {
1202 use super::*;
1203 use core::mem::size_of;
1204 use alloc::vec;
1205
1206 #[test]
1207 fn test_struct_sizes() {
1208 assert_eq!(size_of::<ListIndex>(), 4);
1209 assert_eq!(size_of::<ListNode>(), 8);
1210 assert_eq!(size_of::<ListEnds>(), 8);
1211 assert_eq!(size_of::<IndexList<u32>>(), 72);
1212 }
1213 #[test]
1214 fn test_index_alias() {
1215 let list = IndexList::from(&mut vec![1, 2, 3]);
1216 let ndx: Index = list.first_index();
1217 assert_eq!(ndx.get(), Some(0));
1218 assert_eq!(list.get(ndx), Some(&1));
1219 }
1220}