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