Skip to main content

xorlist_rs/
lib.rs

1//! A doubly-linked list that packs both links of every node into a single
2//! word, backed by a single `Vec` instead of per-node allocations.
3//!
4//! [`XorList`] is a XOR doubly linked list: instead of separate `prev` and
5//! `next` pointers, each node stores the two folded together, and traversal
6//! recovers one from the other. The links here are also *self-relative* — a
7//! node in slot `curr` stores `(prev - curr) ^ (next - curr)` (with wrapping
8//! arithmetic) rather than `prev ^ next`, so interior nodes stay valid when
9//! a whole run of slots is relocated by a constant offset. [`XorList::append`]
10//! exploits this to splice another list's storage in wholesale, rewriting
11//! only the three links at the seam.
12//!
13//! Decoding a link needs one known neighbor: coming from `prev`, the next
14//! slot is `(npx ^ (prev - curr)) + curr`. Iterators and cursors therefore
15//! track a pair of adjacent slots as they walk, and the list can be
16//! traversed equally cheaply in either direction.
17//!
18//! Rather than giving each node its own heap allocation, all nodes live in
19//! slots of one backing `Vec`, and links name slots instead of
20//! addresses — pushes fill the `Vec` left to right, while the XOR links
21//! define the logical order on top of it. This raises the question of what
22//! to do when a node is removed from the middle of the `Vec`: shifting or
23//! swapping the remaining nodes would invalidate the links that name their
24//! slots. The opinionated answer here is to not move anything — the vacated
25//! slot is unlinked, marked dirty, and left in place. Subsequent pushes pop
26//! a dirty slot and construct the new node in it, growing the `Vec` only
27//! when no dirty slot is available, so removal never disturbs other nodes
28//! and the capacity is recycled. [`XorList::compact`] rebuilds the buffer
29//! in traversal order to shed accumulated dirty slots.
30//!
31//! Because a node stays in its slot for as long as its element lives, the
32//! slot doubles as a stable *handle* to the element. Pushes return the
33//! slot they filled, and [`XorList::slot`] / [`XorList::slot_mut`] turn a
34//! saved slot back into the element in *O*(1) — no traversal — which is
35//! what makes patterns like an LRU cache (a map from key to slot, with
36//! the recency order kept in the list) practical. See the
37//! [slots](XorList#slots) section on [`XorList`] for the rules on when a
38//! slot stays valid.
39//!
40//! # Examples
41//!
42//! ```
43//! use xorlist_rs::XorList;
44//!
45//! let mut list: XorList<u32> = (1..=3).collect();
46//! list.push_front(0);
47//! list.push_back(4);
48//!
49//! assert_eq!(list.len(), 5);
50//! assert!(list.iter().eq(&[0, 1, 2, 3, 4]));
51//! assert_eq!(list.pop_back(), Some(4));
52//! ```
53
54#![warn(missing_docs)]
55
56pub mod cursor;
57#[cfg(test)]
58mod tests;
59
60use core::{cmp, fmt, hash, iter::FusedIterator, marker::PhantomData, mem};
61pub use cursor::{Cursor, CursorMut};
62
63#[derive(Debug, Eq)]
64struct Node<T> {
65    value: Option<T>,
66    npx: usize,
67}
68
69impl<T> Node<T> {
70    const fn next_slot(&self, curr: usize, prev: usize) -> usize {
71        (self.npx ^ prev.wrapping_sub(curr)).wrapping_add(curr)
72    }
73
74    // this is the exact same calculation as next_slot(), but exists
75    // for code clarity
76    const fn prev_slot(&self, curr: usize, next: usize) -> usize {
77        self.next_slot(curr, next)
78    }
79}
80
81impl<T: PartialEq> PartialEq for Node<T> {
82    fn eq(&self, other: &Self) -> bool {
83        self.value == other.value
84    }
85}
86
87impl<T: PartialOrd> PartialOrd for Node<T> {
88    fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> {
89        self.value.partial_cmp(&other.value)
90    }
91}
92
93impl<T: Ord> Ord for Node<T> {
94    fn cmp(&self, other: &Self) -> cmp::Ordering {
95        self.value.cmp(&other.value)
96    }
97}
98
99/// A doubly-linked list with XOR-compressed links, backed by a single
100/// contiguous buffer.
101///
102/// The `XorList` allows pushing and popping elements at either end in
103/// amortized constant time, without allocating each node separately: all
104/// nodes live in slots of one buffer, and slots vacated by pops are reused
105/// by later pushes.
106///
107/// A `XorList` with a known list of items can be initialized from an
108/// iterator:
109///
110/// ```
111/// use xorlist_rs::XorList;
112///
113/// let list: XorList<u32> = (0..5).collect();
114/// assert_eq!(list.len(), 5);
115/// ```
116///
117/// See the [crate-level documentation](crate) for how the links are encoded.
118///
119/// # Slots
120///
121/// Every element occupies one *slot* of the backing buffer, named by a
122/// `usize`. [`push_front`](Self::push_front) and
123/// [`push_back`](Self::push_back) (and their `_mut` variants) return the
124/// slot they stored the element in, and [`slot`](Self::slot) /
125/// [`slot_mut`](Self::slot_mut) resolve a saved slot back to the element
126/// in *O*(1) time, without walking the list. A slot is therefore a
127/// lightweight handle: e.g. an LRU cache can keep a map from key to slot
128/// alongside the list and touch any entry in constant time.
129///
130/// Slot handles obey the following stability rules:
131///
132/// - A slot stays valid, and keeps naming the same element, for as long as
133///   that element remains in the list. Pushing and popping *other*
134///   elements never moves a node between slots, even when the buffer grows.
135/// - Removing an element marks its slot dirty. While the slot is dirty,
136///   [`slot`](Self::slot) returns `None` — but a later push **reuses** the
137///   slot, after which a stale handle silently resolves to the new
138///   occupant. The list does not detect stale handles; discard a slot when
139///   its element is removed.
140/// - Operations that rebuild or move the buffer renumber slots wholesale
141///   and invalidate every outstanding handle: [`compact`](Self::compact)
142///   (all slots), [`split_off`](Self::split_off) (slots in either half),
143///   [`append`](Self::append) (slots in `other`; slots in `self` survive),
144///   and [`clear`](Self::clear). An invalidated slot is never dangling in
145///   the memory-safety sense — resolving it just yields `None` or a
146///   different element.
147///
148/// Slots are unrelated to *logical* indices: [`get`](Self::get) takes the
149/// element's position in traversal order, while [`slot`](Self::slot) takes
150/// a position in the buffer. The two coincide only when the buffer
151/// [is linear](Self::is_linear). Mixing them up is not caught by the API,
152/// so keep the two kinds of `usize` apart.
153#[derive(Eq)]
154pub struct XorList<T> {
155    nodes: Vec<Node<T>>,
156    dirty: Vec<usize>,
157    head: usize,
158    tail: usize,
159}
160
161impl<T> XorList<T> {
162    /// Creates an empty `XorList`.
163    ///
164    /// # Examples
165    ///
166    /// ```
167    /// use xorlist_rs::XorList;
168    ///
169    /// let list: XorList<u32> = XorList::new();
170    /// assert!(list.is_empty());
171    /// ```
172    #[inline]
173    #[must_use]
174    pub const fn new() -> Self {
175        Self {
176            nodes: Vec::new(),
177            dirty: Vec::new(),
178            head: usize::MAX,
179            tail: usize::MAX,
180        }
181    }
182
183    /// Provides a reference to the front element, or `None` if the list is
184    /// empty.
185    ///
186    /// This operation should compute in *O*(1) time.
187    ///
188    /// # Examples
189    ///
190    /// ```
191    /// use xorlist_rs::XorList;
192    ///
193    /// let mut dl = XorList::new();
194    /// assert_eq!(dl.front(), None);
195    ///
196    /// dl.push_front(1);
197    /// assert_eq!(dl.front(), Some(&1));
198    /// ```
199    #[inline]
200    #[must_use]
201    pub fn front(&self) -> Option<&T> {
202        self.nodes
203            .get(self.head)
204            .and_then(|node| node.value.as_ref())
205    }
206
207    /// Provides a mutable reference to the front element, or `None` if the
208    /// list is empty.
209    ///
210    /// This operation should compute in *O*(1) time.
211    ///
212    /// # Examples
213    ///
214    /// ```
215    /// use xorlist_rs::XorList;
216    ///
217    /// let mut dl = XorList::new();
218    /// assert_eq!(dl.front(), None);
219    ///
220    /// dl.push_front(1);
221    /// assert_eq!(dl.front(), Some(&1));
222    ///
223    /// match dl.front_mut() {
224    ///     None => {}
225    ///     Some(x) => *x = 5,
226    /// }
227    /// assert_eq!(dl.front(), Some(&5));
228    /// ```
229    #[inline]
230    #[must_use]
231    pub fn front_mut(&mut self) -> Option<&mut T> {
232        self.nodes
233            .get_mut(self.head)
234            .and_then(|node| node.value.as_mut())
235    }
236
237    /// Provides a reference to the back element, or `None` if the list is
238    /// empty.
239    ///
240    /// This operation should compute in *O*(1) time.
241    ///
242    /// # Examples
243    ///
244    /// ```
245    /// use xorlist_rs::XorList;
246    ///
247    /// let mut dl = XorList::new();
248    /// assert_eq!(dl.back(), None);
249    ///
250    /// dl.push_back(1);
251    /// assert_eq!(dl.back(), Some(&1));
252    /// ```
253    #[inline]
254    #[must_use]
255    pub fn back(&self) -> Option<&T> {
256        self.nodes
257            .get(self.tail)
258            .and_then(|node| node.value.as_ref())
259    }
260
261    /// Provides a mutable reference to the back element, or `None` if the
262    /// list is empty.
263    ///
264    /// This operation should compute in *O*(1) time.
265    ///
266    /// # Examples
267    ///
268    /// ```
269    /// use xorlist_rs::XorList;
270    ///
271    /// let mut dl = XorList::new();
272    /// assert_eq!(dl.back(), None);
273    ///
274    /// dl.push_back(1);
275    /// assert_eq!(dl.back(), Some(&1));
276    ///
277    /// match dl.back_mut() {
278    ///     None => {}
279    ///     Some(x) => *x = 5,
280    /// }
281    /// assert_eq!(dl.back(), Some(&5));
282    /// ```
283    #[inline]
284    #[must_use]
285    pub fn back_mut(&mut self) -> Option<&mut T> {
286        self.nodes
287            .get_mut(self.tail)
288            .and_then(|node| node.value.as_mut())
289    }
290
291    /// Returns the number of elements in the `XorList`.
292    ///
293    /// This operation should compute in *O*(1) time.
294    ///
295    /// # Examples
296    ///
297    /// ```
298    /// use xorlist_rs::XorList;
299    ///
300    /// let mut dl = XorList::new();
301    ///
302    /// dl.push_front(2);
303    /// assert_eq!(dl.len(), 1);
304    ///
305    /// dl.push_front(1);
306    /// assert_eq!(dl.len(), 2);
307    ///
308    /// dl.push_back(3);
309    /// assert_eq!(dl.len(), 3);
310    /// ```
311    #[inline]
312    pub const fn len(&self) -> usize {
313        self.nodes.len() - self.dirty.len()
314    }
315
316    /// Returns `true` if the `XorList` contains no elements.
317    ///
318    /// This operation should compute in *O*(1) time.
319    ///
320    /// # Examples
321    ///
322    /// ```
323    /// use xorlist_rs::XorList;
324    ///
325    /// let mut dl = XorList::new();
326    /// assert!(dl.is_empty());
327    ///
328    /// dl.push_front("foo");
329    /// assert!(!dl.is_empty());
330    /// ```
331    pub const fn is_empty(&self) -> bool {
332        self.len() == 0
333    }
334
335    /// Removes all elements from the `XorList`.
336    ///
337    /// The backing buffer is kept, and its slots are reused by subsequent
338    /// pushes, so outstanding [slots](Self#slots) are invalidated: a saved
339    /// slot resolves to `None` until it is reused, and to the new occupant
340    /// afterwards.
341    ///
342    /// This operation should compute in *O*(*n*) time.
343    ///
344    /// # Examples
345    ///
346    /// ```
347    /// use xorlist_rs::XorList;
348    ///
349    /// let mut dl = XorList::new();
350    ///
351    /// dl.push_front(2);
352    /// dl.push_front(1);
353    /// assert_eq!(dl.len(), 2);
354    /// assert_eq!(dl.front(), Some(&1));
355    ///
356    /// dl.clear();
357    /// assert_eq!(dl.len(), 0);
358    /// assert_eq!(dl.front(), None);
359    /// ```
360    #[inline]
361    pub fn clear(&mut self) {
362        for node in &mut self.nodes {
363            node.value = None;
364        }
365        self.dirty = (0..self.nodes.len()).collect();
366        self.head = usize::MAX;
367        self.tail = usize::MAX;
368    }
369
370    /// Returns `true` if the `XorList` contains an element equal to the
371    /// given value.
372    ///
373    /// This operation should compute linearly in *O*(*n*) time.
374    ///
375    /// # Examples
376    ///
377    /// ```
378    /// use xorlist_rs::XorList;
379    ///
380    /// let mut list: XorList<u32> = XorList::new();
381    ///
382    /// list.push_back(0);
383    /// list.push_back(1);
384    /// list.push_back(2);
385    ///
386    /// assert_eq!(list.contains(&0), true);
387    /// assert_eq!(list.contains(&10), false);
388    /// ```
389    pub fn contains(&self, x: &T) -> bool
390    where
391        T: PartialEq<T>,
392    {
393        self.iter().any(|e| e == x)
394    }
395
396    /// Provides a reference to the element at the given index, or `None` if
397    /// `at` is out of bounds.
398    ///
399    /// `at` is a position in traversal order, not a [slot](Self#slots);
400    /// for *O*(1) access through a slot returned by a push, see
401    /// [`slot`](Self::slot).
402    ///
403    /// The list is walked from whichever end is closer to `at`, so this
404    /// operation should compute in *O*(min(`at`, *n* − `at`)) time.
405    ///
406    /// # Examples
407    ///
408    /// ```
409    /// use xorlist_rs::XorList;
410    ///
411    /// let list: XorList<u32> = (0..5).collect();
412    ///
413    /// assert_eq!(list.get(2), Some(&2));
414    /// assert_eq!(list.get(5), None);
415    /// ```
416    #[inline]
417    #[must_use]
418    pub fn get(&self, at: usize) -> Option<&T> {
419        let len = self.len();
420        if at >= len {
421            return None;
422        }
423        if at < len - at {
424            self.iter().nth(at)
425        } else {
426            self.iter().rev().nth(len - at - 1)
427        }
428    }
429
430    /// Provides a mutable reference to the element at the given index, or
431    /// `None` if `at` is out of bounds.
432    ///
433    /// `at` is a position in traversal order, not a [slot](Self#slots);
434    /// for *O*(1) access through a slot returned by a push, see
435    /// [`slot_mut`](Self::slot_mut).
436    ///
437    /// The list is walked from whichever end is closer to `at`, so this
438    /// operation should compute in *O*(min(`at`, *n* − `at`)) time.
439    ///
440    /// # Examples
441    ///
442    /// ```
443    /// use xorlist_rs::XorList;
444    ///
445    /// let mut list: XorList<u32> = (0..5).collect();
446    ///
447    /// if let Some(x) = list.get_mut(2) {
448    ///     *x = 20;
449    /// }
450    /// assert_eq!(list.get(2), Some(&20));
451    /// ```
452    #[inline]
453    #[must_use]
454    pub fn get_mut(&mut self, at: usize) -> Option<&mut T> {
455        let len = self.len();
456        if at >= len {
457            return None;
458        }
459        if at < len - at {
460            self.iter_mut().nth(at)
461        } else {
462            self.iter_mut().rev().nth(len - at - 1)
463        }
464    }
465
466    /// Returns a reference to the element at the given index, without doing
467    /// bounds checking.
468    ///
469    /// For a safe alternative see [`get`](Self::get).
470    ///
471    /// # Safety
472    ///
473    /// `at` must be less than [`len`](Self::len). Calling this method with
474    /// an out-of-bounds index is *[undefined behavior]*.
475    ///
476    /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
477    ///
478    /// # Examples
479    ///
480    /// ```
481    /// use xorlist_rs::XorList;
482    ///
483    /// let list: XorList<u32> = (1..=3).collect();
484    ///
485    /// unsafe {
486    ///     assert_eq!(list.get_unchecked(1), &2);
487    /// }
488    /// ```
489    #[inline]
490    #[must_use]
491    #[track_caller]
492    pub unsafe fn get_unchecked(&self, at: usize) -> &T {
493        let len = self.len();
494        let mut next_slot = if at < len - at { self.head } else { self.tail };
495        let mut curr_slot = usize::MAX;
496        let count = if at < len - at { at } else { len - at - 1 };
497        for _ in 0..count {
498            let temp = next_slot;
499            next_slot = self.nodes[temp].next_slot(temp, curr_slot);
500            curr_slot = temp;
501        }
502        // SAFETY: index is assumed to be less than the length; values are
503        // guaranteed to be non-null if they are not in the dirty pile
504        unsafe {
505            self.nodes
506                .get_unchecked(next_slot)
507                .value
508                .as_ref()
509                .unwrap_unchecked()
510        }
511    }
512
513    /// Returns a mutable reference to the element at the given index,
514    /// without doing bounds checking.
515    ///
516    /// For a safe alternative see [`get_mut`](Self::get_mut).
517    ///
518    /// # Safety
519    ///
520    /// `at` must be less than [`len`](Self::len). Calling this method with
521    /// an out-of-bounds index is *[undefined behavior]*.
522    ///
523    /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
524    ///
525    /// # Examples
526    ///
527    /// ```
528    /// use xorlist_rs::XorList;
529    ///
530    /// let mut list: XorList<u32> = (1..=3).collect();
531    ///
532    /// unsafe {
533    ///     *list.get_unchecked_mut(1) = 20;
534    /// }
535    /// assert_eq!(list.get(1), Some(&20));
536    /// ```
537    #[inline]
538    #[must_use]
539    #[track_caller]
540    pub unsafe fn get_unchecked_mut(&mut self, at: usize) -> &mut T {
541        let len = self.len();
542        let mut next_slot = if at < len - at { self.head } else { self.tail };
543        let mut curr_slot = usize::MAX;
544        let count = if at < len - at { at } else { len - at - 1 };
545        for _ in 0..count {
546            let temp = next_slot;
547            next_slot = self.nodes[temp].next_slot(temp, curr_slot);
548            curr_slot = temp;
549        }
550        // SAFETY: index is assumed to be less than the length; values are
551        // guaranteed to be non-null if they are not in the dirty pile
552        unsafe {
553            self.nodes
554                .get_unchecked_mut(next_slot)
555                .value
556                .as_mut()
557                .unwrap_unchecked()
558        }
559    }
560
561    /// Provides a forward iterator.
562    ///
563    /// # Examples
564    ///
565    /// ```
566    /// use xorlist_rs::XorList;
567    ///
568    /// let mut list: XorList<u32> = XorList::new();
569    ///
570    /// list.push_back(0);
571    /// list.push_back(1);
572    /// list.push_back(2);
573    ///
574    /// let mut iter = list.iter();
575    /// assert_eq!(iter.next(), Some(&0));
576    /// assert_eq!(iter.next(), Some(&1));
577    /// assert_eq!(iter.next(), Some(&2));
578    /// assert_eq!(iter.next(), None);
579    /// ```
580    #[inline]
581    pub fn iter(&self) -> Iter<'_, T> {
582        Iter::new(self)
583    }
584
585    /// Provides a forward iterator with mutable references.
586    ///
587    /// # Examples
588    ///
589    /// ```
590    /// use xorlist_rs::XorList;
591    ///
592    /// let mut list: XorList<u32> = XorList::new();
593    ///
594    /// list.push_back(0);
595    /// list.push_back(1);
596    /// list.push_back(2);
597    ///
598    /// for element in list.iter_mut() {
599    ///     *element += 10;
600    /// }
601    ///
602    /// let mut iter = list.iter();
603    /// assert_eq!(iter.next(), Some(&10));
604    /// assert_eq!(iter.next(), Some(&11));
605    /// assert_eq!(iter.next(), Some(&12));
606    /// assert_eq!(iter.next(), None);
607    /// ```
608    #[inline]
609    pub fn iter_mut(&mut self) -> IterMut<'_, T> {
610        IterMut::new(self)
611    }
612
613    /// Provides a cursor resting on the front element, with read-only
614    /// access to the list.
615    ///
616    /// The cursor rests on the ghost non-element if the list is empty.
617    ///
618    /// # Examples
619    ///
620    /// ```
621    /// use xorlist_rs::XorList;
622    ///
623    /// let list: XorList<u32> = (0..3).collect();
624    ///
625    /// let mut cursor = list.cursor_front();
626    /// assert_eq!(cursor.current(), Some(&0));
627    /// cursor.move_next();
628    /// assert_eq!(cursor.current(), Some(&1));
629    /// ```
630    #[inline]
631    #[must_use]
632    pub const fn cursor_front(&self) -> Cursor<'_, T> {
633        Cursor {
634            curr_slot: self.head,
635            prev_slot: usize::MAX,
636            index: 0,
637            list: self,
638        }
639    }
640
641    /// Provides a cursor resting on the front element, with editing access
642    /// to the elements.
643    ///
644    /// The cursor rests on the ghost non-element if the list is empty.
645    ///
646    /// # Examples
647    ///
648    /// ```
649    /// use xorlist_rs::XorList;
650    ///
651    /// let mut list: XorList<u32> = (0..3).collect();
652    ///
653    /// let mut cursor = list.cursor_front_mut();
654    /// if let Some(x) = cursor.current() {
655    ///     *x = 10;
656    /// }
657    /// assert_eq!(list.front(), Some(&10));
658    /// ```
659    #[inline]
660    #[must_use]
661    pub fn cursor_front_mut(&mut self) -> CursorMut<'_, T> {
662        CursorMut {
663            curr_slot: self.head,
664            prev_slot: usize::MAX,
665            index: 0,
666            list: self,
667        }
668    }
669
670    /// Provides a cursor resting on the back element, with read-only access
671    /// to the list.
672    ///
673    /// The cursor rests on the ghost non-element if the list is empty.
674    ///
675    /// # Examples
676    ///
677    /// ```
678    /// use xorlist_rs::XorList;
679    ///
680    /// let list: XorList<u32> = (0..3).collect();
681    ///
682    /// let mut cursor = list.cursor_back();
683    /// assert_eq!(cursor.current(), Some(&2));
684    /// cursor.move_prev();
685    /// assert_eq!(cursor.current(), Some(&1));
686    /// ```
687    #[inline]
688    #[must_use]
689    pub fn cursor_back(&self) -> Cursor<'_, T> {
690        let prev_slot = if self.tail == usize::MAX {
691            usize::MAX
692        } else {
693            self.nodes[self.tail].prev_slot(self.tail, usize::MAX)
694        };
695        Cursor {
696            curr_slot: self.tail,
697            prev_slot,
698            index: self.len().saturating_sub(1),
699            list: self,
700        }
701    }
702
703    /// Provides a cursor resting on the back element, with editing access
704    /// to the elements.
705    ///
706    /// The cursor rests on the ghost non-element if the list is empty.
707    ///
708    /// # Examples
709    ///
710    /// ```
711    /// use xorlist_rs::XorList;
712    ///
713    /// let mut list: XorList<u32> = (0..3).collect();
714    ///
715    /// let mut cursor = list.cursor_back_mut();
716    /// if let Some(x) = cursor.current() {
717    ///     *x = 10;
718    /// }
719    /// assert_eq!(list.back(), Some(&10));
720    /// ```
721    #[inline]
722    #[must_use]
723    pub fn cursor_back_mut(&mut self) -> CursorMut<'_, T> {
724        let prev_slot = if self.tail == usize::MAX {
725            usize::MAX
726        } else {
727            self.nodes[self.tail].prev_slot(self.tail, usize::MAX)
728        };
729        CursorMut {
730            curr_slot: self.tail,
731            prev_slot,
732            index: self.len().saturating_sub(1),
733            list: self,
734        }
735    }
736
737    /// Adds an element to the front of the list.
738    ///
739    /// Returns the slot the element was stored in, which can later be
740    /// passed to [`slot`](Self::slot) or [`slot_mut`](Self::slot_mut) for
741    /// *O*(1) access to the element; see the [slots](Self#slots) section
742    /// for how long the slot stays valid. The returned slot may be freely
743    /// discarded.
744    ///
745    /// This operation should compute in amortized *O*(1) time.
746    ///
747    /// # Examples
748    ///
749    /// ```
750    /// use xorlist_rs::XorList;
751    ///
752    /// let mut dl = XorList::new();
753    ///
754    /// dl.push_front(2);
755    /// assert_eq!(dl.front().unwrap(), &2);
756    ///
757    /// let slot = dl.push_front(1);
758    /// assert_eq!(dl.front().unwrap(), &1);
759    /// assert_eq!(dl.slot(slot), Some(&1));
760    /// ```
761    #[inline]
762    pub fn push_front(&mut self, value: T) -> usize {
763        let (slot, _) = self.push_front_mut(value);
764        slot
765    }
766
767    /// Adds an element to the front of the list, returning the slot it was
768    /// stored in along with a mutable reference to it.
769    ///
770    /// The slot can later be passed to [`slot`](Self::slot) or
771    /// [`slot_mut`](Self::slot_mut) for *O*(1) access to the element; see
772    /// the [slots](Self#slots) section for how long the slot stays valid.
773    ///
774    /// This operation should compute in amortized *O*(1) time.
775    ///
776    /// # Examples
777    ///
778    /// ```
779    /// use xorlist_rs::XorList;
780    ///
781    /// let mut dl: XorList<u32> = (1..=3).collect();
782    ///
783    /// let (slot, front) = dl.push_front_mut(0);
784    /// *front += 10;
785    /// assert_eq!(dl.front(), Some(&10));
786    /// assert_eq!(dl.slot(slot), Some(&10));
787    /// ```
788    pub fn push_front_mut(&mut self, value: T) -> (usize, &mut T) {
789        if self.nodes.is_empty() {
790            return (0, self.push_empty(value));
791        }
792
793        let slot = if let Some(idx) = self.dirty.pop() {
794            self.nodes[idx].value = Some(value);
795            self.nodes[idx].npx = Self::compute_npx(idx, usize::MAX, self.head);
796            idx
797        } else {
798            let idx = self.nodes.len();
799            self.nodes.push(Node {
800                value: Some(value),
801                npx: Self::compute_npx(idx, usize::MAX, self.head),
802            });
803            idx
804        };
805        if self.head == usize::MAX {
806            // The list was empty prior to the push, make the tail point to
807            // the added element as well
808            self.tail = slot;
809        } else {
810            let next_idx = self.nodes[self.head].next_slot(self.head, usize::MAX);
811            self.nodes[self.head].npx = Self::compute_npx(self.head, slot, next_idx);
812        }
813        self.head = slot;
814        (
815            slot,
816            // SAFETY: the index is either pointing to a pre-existing node, or a
817            // newly created node pushed to the vector; value is also explicitly
818            // assigned as Some
819            unsafe {
820                self.nodes
821                    .get_unchecked_mut(slot)
822                    .value
823                    .as_mut()
824                    .unwrap_unchecked()
825            },
826        )
827    }
828
829    /// Appends an element to the back of the list.
830    ///
831    /// Returns the slot the element was stored in, which can later be
832    /// passed to [`slot`](Self::slot) or [`slot_mut`](Self::slot_mut) for
833    /// *O*(1) access to the element; see the [slots](Self#slots) section
834    /// for how long the slot stays valid. The returned slot may be freely
835    /// discarded.
836    ///
837    /// This operation should compute in amortized *O*(1) time.
838    ///
839    /// # Examples
840    ///
841    /// ```
842    /// use xorlist_rs::XorList;
843    ///
844    /// let mut dl = XorList::new();
845    ///
846    /// dl.push_back(2);
847    /// let slot = dl.push_back(3);
848    /// assert_eq!(3, *dl.back().unwrap());
849    /// assert_eq!(dl.slot(slot), Some(&3));
850    /// ```
851    #[inline]
852    pub fn push_back(&mut self, value: T) -> usize {
853        let (slot, _) = self.push_back_mut(value);
854        slot
855    }
856
857    /// Appends an element to the back of the list, returning the slot it
858    /// was stored in along with a mutable reference to it.
859    ///
860    /// The slot can later be passed to [`slot`](Self::slot) or
861    /// [`slot_mut`](Self::slot_mut) for *O*(1) access to the element; see
862    /// the [slots](Self#slots) section for how long the slot stays valid.
863    ///
864    /// This operation should compute in amortized *O*(1) time.
865    ///
866    /// # Examples
867    ///
868    /// ```
869    /// use xorlist_rs::XorList;
870    ///
871    /// let mut dl: XorList<u32> = (1..=3).collect();
872    ///
873    /// let (slot, back) = dl.push_back_mut(4);
874    /// *back += 10;
875    /// assert_eq!(dl.back(), Some(&14));
876    /// assert_eq!(dl.slot(slot), Some(&14));
877    /// ```
878    pub fn push_back_mut(&mut self, value: T) -> (usize, &mut T) {
879        if self.nodes.is_empty() {
880            return (0, self.push_empty(value));
881        }
882
883        let slot = if let Some(idx) = self.dirty.pop() {
884            self.nodes[idx].value = Some(value);
885            self.nodes[idx].npx = Self::compute_npx(idx, self.tail, usize::MAX);
886            idx
887        } else {
888            let idx = self.nodes.len();
889            self.nodes.push(Node {
890                value: Some(value),
891                npx: Self::compute_npx(idx, self.tail, usize::MAX),
892            });
893            idx
894        };
895
896        if self.tail == usize::MAX {
897            // The list was empty prior to the push, make the head point to
898            // the added element as well
899            self.head = slot;
900        } else {
901            let prev_idx = self.nodes[self.tail].prev_slot(self.tail, usize::MAX);
902            self.nodes[self.tail].npx = Self::compute_npx(self.tail, prev_idx, slot);
903        }
904        self.tail = slot;
905        (
906            slot,
907            // SAFETY: the index is either pointing to a pre-existing node, or a
908            // newly created node pushed to the vector; value is also explicitly
909            // assigned as Some
910            unsafe {
911                self.nodes
912                    .get_unchecked_mut(slot)
913                    .value
914                    .as_mut()
915                    .unwrap_unchecked()
916            },
917        )
918    }
919
920    fn push_empty(&mut self, value: T) -> &mut T {
921        self.head = 0;
922        self.tail = 0;
923        let node = Node {
924            value: Some(value),
925            npx: 0,
926        };
927        // SAFETY: the value is explicitly instantiated as Some
928        unsafe { self.nodes.push_mut(node).value.as_mut().unwrap_unchecked() }
929    }
930
931    /// Removes the first element and returns it, or `None` if the list is
932    /// empty.
933    ///
934    /// The vacated slot is kept for reuse by later pushes.
935    ///
936    /// This operation should compute in *O*(1) time.
937    ///
938    /// # Examples
939    ///
940    /// ```
941    /// use xorlist_rs::XorList;
942    ///
943    /// let mut d = XorList::new();
944    /// assert_eq!(d.pop_front(), None);
945    ///
946    /// d.push_front(1);
947    /// d.push_front(3);
948    /// assert_eq!(d.pop_front(), Some(3));
949    /// assert_eq!(d.pop_front(), Some(1));
950    /// assert_eq!(d.pop_front(), None);
951    /// ```
952    pub fn pop_front(&mut self) -> Option<T> {
953        if self.is_empty() {
954            return None;
955        }
956
957        let next_idx = self.nodes[self.head].next_slot(self.head, usize::MAX);
958        if next_idx == usize::MAX {
959            self.tail = usize::MAX;
960        } else {
961            let next_next_idx = self.nodes[next_idx].next_slot(next_idx, self.head);
962            self.nodes[next_idx].npx = Self::compute_npx(next_idx, usize::MAX, next_next_idx);
963        }
964        let removed_value = self.nodes[self.head].value.take();
965        self.dirty.push(self.head);
966        self.head = next_idx;
967        removed_value
968    }
969
970    /// Removes the last element and returns it, or `None` if the list is
971    /// empty.
972    ///
973    /// The vacated slot is kept for reuse by later pushes.
974    ///
975    /// This operation should compute in *O*(1) time.
976    ///
977    /// # Examples
978    ///
979    /// ```
980    /// use xorlist_rs::XorList;
981    ///
982    /// let mut d = XorList::new();
983    /// assert_eq!(d.pop_back(), None);
984    ///
985    /// d.push_back(1);
986    /// d.push_back(3);
987    /// assert_eq!(d.pop_back(), Some(3));
988    /// assert_eq!(d.pop_back(), Some(1));
989    /// assert_eq!(d.pop_back(), None);
990    /// ```
991    pub fn pop_back(&mut self) -> Option<T> {
992        if self.is_empty() {
993            return None;
994        }
995
996        let prev_idx = self.nodes[self.tail].prev_slot(self.tail, usize::MAX);
997        if prev_idx == usize::MAX {
998            self.head = usize::MAX;
999        } else {
1000            let prev_prev_idx = self.nodes[prev_idx].prev_slot(prev_idx, self.tail);
1001            self.nodes[prev_idx].npx = Self::compute_npx(prev_idx, prev_prev_idx, usize::MAX);
1002        }
1003        let removed_value = self.nodes[self.tail].value.take();
1004        self.dirty.push(self.tail);
1005        self.tail = prev_idx;
1006        removed_value
1007    }
1008
1009    /// Splits the list into two at the given index. Returns everything
1010    /// after the given index, including the index.
1011    ///
1012    /// The split point is located from whichever end is closer, and the
1013    /// shorter of the two halves is moved into fresh storage, so this
1014    /// operation should compute in *O*(min(`at`, *n* − `at`)) time.
1015    ///
1016    /// Because either half may be the one that is rebuilt, outstanding
1017    /// [slots](Self#slots) in **both** halves are invalidated by a split.
1018    ///
1019    /// # Panics
1020    ///
1021    /// Panics if `at > len`.
1022    ///
1023    /// # Examples
1024    ///
1025    /// ```
1026    /// use xorlist_rs::XorList;
1027    ///
1028    /// let mut d = XorList::new();
1029    ///
1030    /// d.push_front(1);
1031    /// d.push_front(2);
1032    /// d.push_front(3);
1033    ///
1034    /// let mut split = d.split_off(2);
1035    ///
1036    /// assert_eq!(split.pop_front(), Some(1));
1037    /// assert_eq!(split.pop_front(), None);
1038    /// assert!(d.iter().eq(&[3, 2]));
1039    /// ```
1040    pub fn split_off(&mut self, at: usize) -> XorList<T> {
1041        let len = self.len();
1042        assert!(at <= len, "Cannot split off at an out-of-bounds index");
1043        if at == 0 {
1044            return mem::take(self);
1045        } else if at == len {
1046            return Self::new();
1047        }
1048
1049        let Cursor {
1050            mut curr_slot,
1051            mut prev_slot,
1052            ..
1053        } = if at < len - at {
1054            let mut iter = self.iter();
1055            for _ in 0..(at - 1) {
1056                iter.next();
1057            }
1058            iter.cursor_front()
1059        } else {
1060            let mut iter = self.iter();
1061            for _ in 0..(len - at - 1) {
1062                iter.next_back();
1063            }
1064            iter.cursor_back()
1065        };
1066
1067        let mut new_list = Self::new();
1068        let mut count = 0;
1069
1070        let value = self.nodes[curr_slot].value.take();
1071        let next_slot = self.nodes[curr_slot].next_slot(curr_slot, prev_slot);
1072        let next = if (at < len - at && prev_slot != usize::MAX)
1073            || (at >= len - at && next_slot != usize::MAX)
1074        {
1075            1
1076        } else {
1077            usize::MAX
1078        };
1079        let npx = Self::compute_npx(0, usize::MAX, next);
1080        new_list.nodes.push(Node { value, npx });
1081        self.dirty.push(curr_slot);
1082
1083        // we reverse the direction of travel so that we loop through the
1084        // shorter list
1085        if at < len - at {
1086            let next_next_slot = self.nodes[next_slot].next_slot(next_slot, curr_slot);
1087            self.nodes[next_slot].npx = Self::compute_npx(next_slot, usize::MAX, next_next_slot);
1088            self.head = next_slot;
1089            prev_slot = next_slot;
1090        } else {
1091            let prev_prev_slot = self.nodes[prev_slot].prev_slot(prev_slot, curr_slot);
1092            self.nodes[prev_slot].npx = Self::compute_npx(prev_slot, prev_prev_slot, usize::MAX);
1093            self.tail = prev_slot;
1094        }
1095        let temp = curr_slot;
1096        curr_slot = self.nodes[temp].next_slot(temp, prev_slot);
1097        prev_slot = temp;
1098
1099        while curr_slot != usize::MAX {
1100            self.dirty.push(curr_slot);
1101            count += 1;
1102            let next_slot = self.nodes[curr_slot].next_slot(curr_slot, prev_slot);
1103            let value = self.nodes[curr_slot].value.take();
1104            let next = if next_slot != usize::MAX {
1105                count + 1
1106            } else {
1107                next_slot
1108            };
1109            let npx = Self::compute_npx(count, count - 1, next);
1110            new_list.nodes.push(Node { value, npx });
1111
1112            prev_slot = curr_slot;
1113            curr_slot = next_slot;
1114        }
1115
1116        if at < len - at {
1117            new_list.head = count;
1118            new_list.tail = 0;
1119            mem::swap(self, &mut new_list);
1120        } else {
1121            new_list.head = 0;
1122            new_list.tail = count;
1123        }
1124
1125        new_list
1126    }
1127
1128    /// Moves all elements from `other` to the end of the list.
1129    ///
1130    /// This reuses all the nodes from `other` and moves them into `self`.
1131    /// After this operation, `other` becomes empty.
1132    ///
1133    /// `other`'s storage is spliced in wholesale: thanks to the
1134    /// self-relative link encoding, only the three links at the seam are
1135    /// rewritten and no per-node fix-ups are needed, though moving the
1136    /// buffer itself is *O*(*m*) in `other`'s slot count.
1137    ///
1138    /// [Slots](Self#slots) in `self` remain valid; the moved elements land
1139    /// in new slots, so slots previously obtained from `other` are
1140    /// invalidated.
1141    ///
1142    /// # Examples
1143    ///
1144    /// ```
1145    /// use xorlist_rs::XorList;
1146    ///
1147    /// let mut list1 = XorList::new();
1148    /// list1.push_back('a');
1149    ///
1150    /// let mut list2 = XorList::new();
1151    /// list2.push_back('b');
1152    /// list2.push_back('c');
1153    ///
1154    /// list1.append(&mut list2);
1155    ///
1156    /// let mut iter = list1.iter();
1157    /// assert_eq!(iter.next(), Some(&'a'));
1158    /// assert_eq!(iter.next(), Some(&'b'));
1159    /// assert_eq!(iter.next(), Some(&'c'));
1160    /// assert!(iter.next().is_none());
1161    ///
1162    /// // `other` is now empty
1163    /// assert!(list2.is_empty());
1164    /// ```
1165    pub fn append(&mut self, other: &mut Self) {
1166        if other.is_empty() {
1167            return;
1168        }
1169        if self.is_empty() {
1170            mem::swap(self, other);
1171            return;
1172        }
1173
1174        let offset = self.nodes.len();
1175        let other_head_slot = offset + other.head;
1176        let other_tail_slot = offset + other.tail;
1177
1178        let prev_slot = self.nodes[self.tail].prev_slot(self.tail, usize::MAX);
1179        self.nodes[self.tail].npx = Self::compute_npx(self.tail, prev_slot, other_head_slot);
1180
1181        if other.head == other.tail {
1182            other.nodes[other.head].npx = Self::compute_npx(other_head_slot, self.tail, usize::MAX);
1183        } else {
1184            let next_slot = offset + other.nodes[other.head].next_slot(other.head, usize::MAX);
1185            other.nodes[other.head].npx = Self::compute_npx(other_head_slot, self.tail, next_slot);
1186            let tail_prev = offset + other.nodes[other.tail].prev_slot(other.tail, usize::MAX);
1187            other.nodes[other.tail].npx = Self::compute_npx(other_tail_slot, tail_prev, usize::MAX);
1188        }
1189
1190        self.nodes.append(&mut other.nodes);
1191        self.dirty
1192            .extend(other.dirty.drain(..).map(|slot| slot + offset));
1193        self.tail = other_tail_slot;
1194        other.head = usize::MAX;
1195        other.tail = usize::MAX;
1196    }
1197
1198    pub(crate) const fn compute_npx(curr: usize, prev: usize, next: usize) -> usize {
1199        prev.wrapping_sub(curr) ^ next.wrapping_sub(curr)
1200    }
1201
1202    // --- Methods related to the backing storage of the list ---
1203
1204    /// Provides a reference to the element stored in the given slot of the
1205    /// backing buffer, or `None` if the slot is out of bounds or dirty.
1206    ///
1207    /// `at` is a slot — a handle returned by
1208    /// [`push_front`](Self::push_front), [`push_back`](Self::push_back), or
1209    /// their `_mut` variants — **not** a position in traversal order (for
1210    /// that, see [`get`](Self::get)). See the [slots](Self#slots) section
1211    /// for how long a slot stays valid; in particular, a stale handle
1212    /// whose slot has been reused resolves to the new occupant with no
1213    /// error.
1214    ///
1215    /// This operation computes in *O*(1) time.
1216    ///
1217    /// # Examples
1218    ///
1219    /// ```
1220    /// use xorlist_rs::XorList;
1221    ///
1222    /// let mut list: XorList<u32> = (0..100).collect();
1223    /// let slot = list.push_back(100);
1224    ///
1225    /// // No traversal: the handle goes straight to the element
1226    /// assert_eq!(list.slot(slot), Some(&100));
1227    ///
1228    /// assert_eq!(list.pop_back(), Some(100));
1229    /// // The slot is now dirty
1230    /// assert_eq!(list.slot(slot), None);
1231    /// ```
1232    #[inline]
1233    #[must_use]
1234    pub fn slot(&self, at: usize) -> Option<&T> {
1235        self.nodes.get(at).and_then(|node| node.value.as_ref())
1236    }
1237
1238    /// Provides a mutable reference to the element stored in the given slot
1239    /// of the backing buffer, or `None` if the slot is out of bounds or
1240    /// dirty.
1241    ///
1242    /// `at` is a slot — a handle returned by
1243    /// [`push_front`](Self::push_front), [`push_back`](Self::push_back), or
1244    /// their `_mut` variants — **not** a position in traversal order (for
1245    /// that, see [`get_mut`](Self::get_mut)). See the
1246    /// [slots](Self#slots) section for how long a slot stays valid; in
1247    /// particular, a stale handle whose slot has been reused resolves to
1248    /// the new occupant with no error.
1249    ///
1250    /// This operation computes in *O*(1) time.
1251    ///
1252    /// # Examples
1253    ///
1254    /// ```
1255    /// use xorlist_rs::XorList;
1256    ///
1257    /// let mut list: XorList<u32> = (1..=3).collect();
1258    /// let slot = list.push_front(0);
1259    ///
1260    /// *list.slot_mut(slot).unwrap() += 10;
1261    /// assert_eq!(list.front(), Some(&10));
1262    /// ```
1263    #[inline]
1264    #[must_use]
1265    pub fn slot_mut(&mut self, at: usize) -> Option<&mut T> {
1266        self.nodes.get_mut(at).and_then(|node| node.value.as_mut())
1267    }
1268
1269    /// Provides a reference to the element stored in the given slot of the
1270    /// backing buffer, without checking that the slot holds one.
1271    ///
1272    /// For a safe alternative, see [`slot`](Self::slot).
1273    ///
1274    /// This operation computes in *O*(1) time.
1275    ///
1276    /// # Panics
1277    ///
1278    /// Panics if `at` is outside the backing buffer. Note that panicking on
1279    /// an in-bounds dirty slot is *not* guaranteed — that is undefined
1280    /// behavior instead.
1281    ///
1282    /// # Safety
1283    ///
1284    /// `at` must be an occupied slot: one obtained from a push whose
1285    /// element has not since been removed, with no intervening operation
1286    /// that renumbers slots (see the [slots](Self#slots) section). Calling
1287    /// this with a dirty slot is *[undefined behavior]* even if the
1288    /// resulting reference is not used.
1289    ///
1290    /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
1291    ///
1292    /// # Examples
1293    ///
1294    /// ```
1295    /// use xorlist_rs::XorList;
1296    ///
1297    /// let mut list: XorList<u32> = (1..=3).collect();
1298    /// let slot = list.push_back(4);
1299    ///
1300    /// // SAFETY: the element in `slot` has not been removed
1301    /// assert_eq!(unsafe { list.slot_unchecked(slot) }, &4);
1302    /// ```
1303    #[inline]
1304    #[must_use]
1305    #[track_caller]
1306    pub unsafe fn slot_unchecked(&self, at: usize) -> &T {
1307        unsafe { self.nodes[at].value.as_ref().unwrap_unchecked() }
1308    }
1309
1310    /// Provides a mutable reference to the element stored in the given slot
1311    /// of the backing buffer, without checking that the slot holds one.
1312    ///
1313    /// For a safe alternative, see [`slot_mut`](Self::slot_mut).
1314    ///
1315    /// This operation computes in *O*(1) time.
1316    ///
1317    /// # Panics
1318    ///
1319    /// Panics if `at` is outside the backing buffer. Note that panicking on
1320    /// an in-bounds dirty slot is *not* guaranteed — that is undefined
1321    /// behavior instead.
1322    ///
1323    /// # Safety
1324    ///
1325    /// `at` must be an occupied slot: one obtained from a push whose
1326    /// element has not since been removed, with no intervening operation
1327    /// that renumbers slots (see the [slots](Self#slots) section). Calling
1328    /// this with a dirty slot is *[undefined behavior]* even if the
1329    /// resulting reference is not used.
1330    ///
1331    /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
1332    ///
1333    /// # Examples
1334    ///
1335    /// ```
1336    /// use xorlist_rs::XorList;
1337    ///
1338    /// let mut list: XorList<u32> = (1..=3).collect();
1339    /// let slot = list.push_back(4);
1340    ///
1341    /// // SAFETY: the element in `slot` has not been removed
1342    /// unsafe { *list.slot_unchecked_mut(slot) += 10 };
1343    /// assert_eq!(list.back(), Some(&14));
1344    /// ```
1345    #[inline]
1346    #[must_use]
1347    #[track_caller]
1348    pub unsafe fn slot_unchecked_mut(&mut self, at: usize) -> &mut T {
1349        unsafe { self.nodes[at].value.as_mut().unwrap_unchecked() }
1350    }
1351
1352    /// Repacks the backing buffer so that the slots lie in traversal order,
1353    /// discarding the dirty slots left behind by removals.
1354    ///
1355    /// The elements themselves are unaffected. The buffer is rebuilt even
1356    /// when no slots are dirty, so this reliably relinearizes a scattered
1357    /// slot layout (such as one built with
1358    /// [`push_front`](Self::push_front)). This operation should compute in
1359    /// *O*(*n*) time; check [`is_linear`](Self::is_linear) first to skip
1360    /// the rebuild when the buffer is already in order.
1361    ///
1362    /// Repacking renumbers every slot, so all outstanding
1363    /// [slots](Self#slots) are invalidated: a saved slot resolves to
1364    /// whichever element now occupies it, with no error. Do not call this
1365    /// while slot handles are live.
1366    ///
1367    /// # Examples
1368    ///
1369    /// ```
1370    /// use xorlist_rs::XorList;
1371    ///
1372    /// let mut list: XorList<u32> = (0..100).collect();
1373    /// for _ in 0..99 {
1374    ///     list.pop_front();
1375    /// }
1376    ///
1377    /// // 99 of the 100 slots are now dirty; repack them away
1378    /// list.compact();
1379    /// assert_eq!(list.len(), 1);
1380    /// assert_eq!(list.front(), Some(&99));
1381    /// ```
1382    pub fn compact(&mut self) {
1383        if self.head == usize::MAX {
1384            self.nodes.clear();
1385            self.dirty.clear();
1386            return;
1387        }
1388        let len = self.len();
1389        let mut nodes = Vec::with_capacity(len);
1390        let mut cursor = self.cursor_front_mut();
1391
1392        while let Some((node, index)) = cursor.current_node() {
1393            let prev = index.wrapping_sub(1);
1394            let next = if index == len - 1 {
1395                usize::MAX
1396            } else {
1397                index + 1
1398            };
1399            let npx = Self::compute_npx(index, prev, next);
1400            let value = node.value.take();
1401            nodes.push(Node { value, npx });
1402            cursor.move_next();
1403        }
1404
1405        self.nodes = nodes;
1406        self.dirty.clear();
1407        self.head = 0;
1408        self.tail = len - 1;
1409    }
1410
1411    /// Returns `true` if the slots of the backing buffer already lie in
1412    /// traversal order with no dirty slots — that is, if
1413    /// [`compact`](Self::compact) would leave the buffer unchanged.
1414    ///
1415    /// This allows callers to skip the *O*(*n*) rebuild that `compact` performs
1416    /// unconditionally:
1417    ///
1418    /// ```
1419    /// use xorlist_rs::XorList;
1420    ///
1421    /// let mut list: XorList<u32> = (0..4).collect();
1422    /// assert!(list.is_linear());
1423    ///
1424    /// list.pop_front();
1425    /// assert!(!list.is_linear());
1426    ///
1427    /// if !list.is_linear() {
1428    ///     list.compact();
1429    /// }
1430    /// assert!(list.is_linear());
1431    /// ```
1432    ///
1433    /// This operation should compute in *O*(*n*) time, but performs no
1434    /// allocation and only scans the link words.
1435    #[must_use]
1436    pub fn is_linear(&self) -> bool {
1437        if !self.dirty.is_empty() {
1438            return false;
1439        }
1440
1441        let len = self.len();
1442        if len == 0 {
1443            return true;
1444        }
1445        if len == 1 {
1446            return self.head == 0;
1447        }
1448
1449        self.head == 0
1450            && self.nodes[..(len - 1)]
1451                .iter()
1452                .all(|node| node.npx == usize::MAX ^ 1)
1453            && self.nodes[len - 1].npx == Self::compute_npx(len - 1, len - 2, usize::MAX)
1454    }
1455}
1456
1457impl<T> Default for XorList<T> {
1458    fn default() -> XorList<T> {
1459        XorList::new()
1460    }
1461}
1462
1463impl<T> Extend<T> for XorList<T> {
1464    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
1465        iter.into_iter().for_each(move |node| {
1466            self.push_back(node);
1467        });
1468    }
1469}
1470
1471impl<'a, T: 'a + Copy> Extend<&'a T> for XorList<T> {
1472    fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
1473        self.extend(iter.into_iter().copied())
1474    }
1475}
1476
1477impl<T: Clone> Clone for XorList<T> {
1478    fn clone(&self) -> Self {
1479        let mut list = Self::new();
1480        list.extend(self.iter().cloned());
1481        list
1482    }
1483
1484    fn clone_from(&mut self, source: &Self) {
1485        let mut source_iter = source.iter();
1486        if self.len() > source.len() {
1487            self.split_off(source.len());
1488        }
1489        for (elem, source_elem) in self.iter_mut().zip(&mut source_iter) {
1490            elem.clone_from(source_elem);
1491        }
1492        if !source_iter.is_empty() {
1493            self.extend(source_iter.cloned());
1494        }
1495    }
1496}
1497
1498impl<T: PartialEq> PartialEq for XorList<T> {
1499    fn eq(&self, other: &Self) -> bool {
1500        self.len() == other.len() && self.iter().eq(other)
1501    }
1502}
1503
1504impl<T: PartialOrd> PartialOrd for XorList<T> {
1505    fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> {
1506        self.iter().partial_cmp(other)
1507    }
1508}
1509
1510impl<T: Ord> Ord for XorList<T> {
1511    #[inline]
1512    fn cmp(&self, other: &Self) -> cmp::Ordering {
1513        self.iter().cmp(other)
1514    }
1515}
1516
1517impl<T: hash::Hash> hash::Hash for XorList<T> {
1518    fn hash<H: hash::Hasher>(&self, state: &mut H) {
1519        state.write_usize(self.len());
1520        for value in self {
1521            value.hash(state);
1522        }
1523    }
1524}
1525
1526impl<T: fmt::Debug> fmt::Debug for XorList<T> {
1527    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1528        let mut entries = String::new();
1529        let mut iter = self.iter();
1530
1531        if f.alternate() {
1532            if let Some(entry) = iter.next() {
1533                entries.push_str(&format!("\n    {entry:?}(slot #{})", iter.prev_head));
1534            } else {
1535                return write!(f, "XorList()");
1536            }
1537            while let Some(entry) = iter.next() {
1538                entries.push_str(&format!("\n    <=> {entry:?}(slot #{})", iter.prev_head));
1539            }
1540            write!(f, "XorList({entries}\n)")
1541        } else {
1542            if let Some(entry) = iter.next() {
1543                entries.push_str(&format!("{entry:?}(slot #{})", iter.prev_head));
1544            }
1545            while let Some(entry) = iter.next() {
1546                entries.push_str(&format!(" <=> {entry:?}(slot #{})", iter.prev_head));
1547            }
1548            write!(f, "XorList({entries})")
1549        }
1550    }
1551}
1552
1553impl<T, const N: usize> From<[T; N]> for XorList<T> {
1554    /// Converts a `[T; N]` into a `XorList<T>`.
1555    ///
1556    /// ```
1557    /// use xorlist_rs::XorList;
1558    ///
1559    /// let list1 = XorList::from([1, 2, 3, 4]);
1560    /// let list2: XorList<_> = [1, 2, 3, 4].into();
1561    /// assert_eq!(list1, list2);
1562    /// ```
1563    fn from(arr: [T; N]) -> Self {
1564        Self::from_iter(arr)
1565    }
1566}
1567
1568impl<T> From<Vec<T>> for XorList<T> {
1569    /// Converts a `Vec<T>` into a `XorList<T>`.
1570    ///
1571    /// ```
1572    /// use xorlist_rs::XorList;
1573    /// let list1 = XorList::from(vec![1, 2, 3, 4]);
1574    /// let list2: XorList<_> = vec![1, 2, 3, 4].into();
1575    /// assert_eq!(list1, list2);
1576    /// ```
1577    fn from(vec: Vec<T>) -> Self {
1578        let len = vec.len();
1579        if len == 0 {
1580            return Self {
1581                nodes: Vec::new(),
1582                dirty: Vec::new(),
1583                head: usize::MAX,
1584                tail: usize::MAX,
1585            };
1586        }
1587
1588        let nodes = vec
1589            .into_iter()
1590            .enumerate()
1591            .map(|(slot, value)| {
1592                let prev = slot.wrapping_sub(1);
1593                let next = if slot == len - 1 {
1594                    usize::MAX
1595                } else {
1596                    slot + 1
1597                };
1598                let npx = Self::compute_npx(slot, prev, next);
1599                Node {
1600                    value: Some(value),
1601                    npx,
1602                }
1603            })
1604            .collect();
1605        Self {
1606            nodes,
1607            dirty: Vec::new(),
1608            head: 0,
1609            tail: len - 1,
1610        }
1611    }
1612}
1613
1614/// An iterator over the elements of a [`XorList`].
1615///
1616/// This `struct` is created by [`XorList::iter`]. See its documentation for
1617/// more.
1618#[derive(Clone)]
1619pub struct Iter<'a, T: 'a> {
1620    head: usize,
1621    prev_head: usize,
1622    tail: usize,
1623    prev_tail: usize,
1624    index: usize,
1625    rem: usize,
1626    list: &'a XorList<T>,
1627}
1628
1629impl<'a, T> Iter<'a, T> {
1630    const fn new(list: &'a XorList<T>) -> Self {
1631        let head = list.head;
1632        let prev_head = usize::MAX;
1633        let tail = list.tail;
1634        let prev_tail = usize::MAX;
1635        Self {
1636            head,
1637            prev_head,
1638            tail,
1639            prev_tail,
1640            index: 0,
1641            rem: list.len(),
1642            list,
1643        }
1644    }
1645
1646    /// Creates an iterator that starts at `cursor`'s position and runs to
1647    /// the back of the list.
1648    ///
1649    /// A cursor resting on the ghost non-element produces an empty
1650    /// iterator.
1651    ///
1652    /// # Examples
1653    ///
1654    /// ```
1655    /// use xorlist_rs::{Iter, XorList};
1656    ///
1657    /// let list: XorList<u32> = (0..5).collect();
1658    /// let mut cursor = list.cursor_front();
1659    /// cursor.move_next();
1660    ///
1661    /// let iter = Iter::with_cursor_front(cursor);
1662    /// assert!(iter.eq(&[1, 2, 3, 4]));
1663    /// ```
1664    pub const fn with_cursor_front(
1665        Cursor {
1666            curr_slot,
1667            prev_slot,
1668            index,
1669            list,
1670        }: Cursor<'a, T>,
1671    ) -> Self {
1672        let rem = list.len() - index;
1673        Self {
1674            head: curr_slot,
1675            prev_head: prev_slot,
1676            tail: list.tail,
1677            prev_tail: usize::MAX,
1678            index,
1679            rem,
1680            list,
1681        }
1682    }
1683
1684    /// Creates an iterator that starts at the front of the list and runs up
1685    /// to and including `cursor`'s position.
1686    ///
1687    /// A cursor resting on the ghost non-element produces an empty
1688    /// iterator.
1689    ///
1690    /// # Examples
1691    ///
1692    /// ```
1693    /// use xorlist_rs::{Iter, XorList};
1694    ///
1695    /// let list: XorList<u32> = (0..5).collect();
1696    /// let mut cursor = list.cursor_back();
1697    /// cursor.move_prev();
1698    ///
1699    /// let iter = Iter::with_cursor_back(cursor);
1700    /// assert!(iter.eq(&[0, 1, 2, 3]));
1701    /// ```
1702    pub fn with_cursor_back(
1703        Cursor {
1704            curr_slot,
1705            prev_slot,
1706            index,
1707            list,
1708        }: Cursor<'a, T>,
1709    ) -> Self {
1710        if curr_slot == usize::MAX {
1711            return Self {
1712                head: list.head,
1713                prev_head: usize::MAX,
1714                tail: usize::MAX,
1715                prev_tail: list.head,
1716                index: 0,
1717                rem: 0,
1718                list,
1719            };
1720        }
1721        let prev_tail = list.nodes[curr_slot].next_slot(curr_slot, prev_slot);
1722        Self {
1723            head: list.head,
1724            prev_head: usize::MAX,
1725            tail: curr_slot,
1726            prev_tail,
1727            index: 0,
1728            rem: index + 1,
1729            list,
1730        }
1731    }
1732
1733    /// Returns a cursor over the underlying list, resting on the element
1734    /// the next call to [`next`](Iterator::next) would yield.
1735    ///
1736    /// If the iterator is exhausted, the cursor rests on the ghost
1737    /// non-element.
1738    #[inline]
1739    #[must_use]
1740    pub const fn cursor_front(&self) -> Cursor<'a, T> {
1741        Cursor {
1742            curr_slot: self.head,
1743            prev_slot: self.prev_head,
1744            index: self.index,
1745            list: self.list,
1746        }
1747    }
1748
1749    /// Returns a cursor over the underlying list, resting on the element
1750    /// the next call to [`next_back`](DoubleEndedIterator::next_back) would
1751    /// yield.
1752    ///
1753    /// If the iterator was exhausted from the back, the cursor rests on the
1754    /// last element yielded, oriented so that it can still move toward the
1755    /// back of the list; for an empty list it rests on the ghost
1756    /// non-element.
1757    #[inline]
1758    #[must_use]
1759    pub fn cursor_back(&self) -> Cursor<'a, T> {
1760        if self.tail == usize::MAX {
1761            return Cursor {
1762                curr_slot: self.prev_tail,
1763                prev_slot: self.tail,
1764                index: 0,
1765                list: self.list,
1766            };
1767        }
1768        let prev_slot = self.list.nodes[self.tail].prev_slot(self.tail, self.prev_tail);
1769        Cursor {
1770            curr_slot: self.tail,
1771            prev_slot,
1772            index: (self.index + self.rem).saturating_sub(1),
1773            list: self.list,
1774        }
1775    }
1776
1777    /// Returns `true` if the iterator has no more elements to yield.
1778    #[inline]
1779    #[must_use]
1780    pub const fn is_empty(&self) -> bool {
1781        self.rem == 0
1782    }
1783}
1784
1785impl<'a, T> Iterator for Iter<'a, T> {
1786    type Item = &'a T;
1787
1788    #[inline]
1789    fn next(&mut self) -> Option<&'a T> {
1790        let curr_slot = (!Self::is_empty(self)).then_some(self.head)?;
1791        self.index += 1;
1792        self.rem -= 1;
1793        self.head = self.list.nodes[curr_slot].next_slot(curr_slot, self.prev_head);
1794        self.prev_head = curr_slot;
1795        self.list.nodes[curr_slot].value.as_ref()
1796    }
1797
1798    #[inline]
1799    fn size_hint(&self) -> (usize, Option<usize>) {
1800        (self.rem, Some(self.rem))
1801    }
1802
1803    #[inline]
1804    fn last(mut self) -> Option<&'a T> {
1805        self.next_back()
1806    }
1807}
1808
1809impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
1810    fn next_back(&mut self) -> Option<Self::Item> {
1811        let curr_slot = (!Self::is_empty(self)).then_some(self.tail)?;
1812        self.rem -= 1;
1813        self.tail = self.list.nodes[curr_slot].prev_slot(curr_slot, self.prev_tail);
1814        self.prev_tail = curr_slot;
1815        self.list.nodes[curr_slot].value.as_ref()
1816    }
1817}
1818
1819impl<T> ExactSizeIterator for Iter<'_, T> {}
1820
1821impl<T> FusedIterator for Iter<'_, T> {}
1822
1823impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> {
1824    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1825        let mut cursor = self.cursor_front();
1826        let mut entries = String::new();
1827
1828        if f.alternate() {
1829            if let Some(val) = cursor.current() {
1830                entries.push_str(&format!("\n    {val:?}(slot #{})", cursor.curr_slot));
1831                cursor.move_next();
1832            } else {
1833                return write!(f, "Iter()");
1834            }
1835            while let Some(val) = cursor.current() {
1836                entries.push_str(&format!("\n    <=> {val:?}(slot #{})", cursor.curr_slot));
1837                cursor.move_next();
1838            }
1839
1840            write!(f, "Iter({entries}\n)")
1841        } else {
1842            if let Some(val) = cursor.current() {
1843                entries.push_str(&format!("{val:?}(slot #{})", cursor.curr_slot));
1844                cursor.move_next();
1845            }
1846            while let Some(val) = cursor.current() {
1847                entries.push_str(&format!(" <=> {val:?}(slot #{})", cursor.curr_slot));
1848                cursor.move_next();
1849            }
1850
1851            write!(f, "Iter({entries})")
1852        }
1853    }
1854}
1855
1856/// A mutable iterator over the elements of a [`XorList`].
1857///
1858/// This `struct` is created by [`XorList::iter_mut`]. See its documentation
1859/// for more.
1860pub struct IterMut<'a, T: 'a> {
1861    head: usize,
1862    prev_head: usize,
1863    tail: usize,
1864    prev_tail: usize,
1865    index: usize,
1866    rem: usize,
1867    ptr: *mut Node<T>,
1868    _marker: PhantomData<&'a mut Node<T>>,
1869}
1870
1871impl<'a, T> IterMut<'a, T> {
1872    fn new(list: &'a mut XorList<T>) -> Self {
1873        let head = list.head;
1874        let prev_head = usize::MAX;
1875        let tail = list.tail;
1876        let prev_tail = usize::MAX;
1877        Self {
1878            head,
1879            prev_head,
1880            tail,
1881            prev_tail,
1882            index: 0,
1883            rem: list.len(),
1884            ptr: list.nodes.as_mut_ptr(),
1885            _marker: PhantomData,
1886        }
1887    }
1888
1889    /// Returns `true` if the iterator has no more elements to yield.
1890    #[inline]
1891    pub const fn is_empty(&self) -> bool {
1892        self.rem == 0
1893    }
1894}
1895
1896impl<'a, T> Iterator for IterMut<'a, T> {
1897    type Item = &'a mut T;
1898
1899    #[inline]
1900    fn next(&mut self) -> Option<&'a mut T> {
1901        if Self::is_empty(self) {
1902            return None;
1903        }
1904
1905        self.index += 1;
1906        self.rem -= 1;
1907        let curr_slot = self.head;
1908        // SAFETY: slots form an acyclic chain, so each slot is yielded at most
1909        // once per traversal; no two returned &mut T alias
1910        let node = unsafe { &mut *self.ptr.add(curr_slot) };
1911        self.head = node.next_slot(curr_slot, self.prev_head);
1912        self.prev_head = curr_slot;
1913        node.value.as_mut()
1914    }
1915
1916    #[inline]
1917    fn size_hint(&self) -> (usize, Option<usize>) {
1918        (self.rem, Some(self.rem))
1919    }
1920
1921    #[inline]
1922    fn last(mut self) -> Option<&'a mut T> {
1923        self.next_back()
1924    }
1925}
1926
1927impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
1928    fn next_back(&mut self) -> Option<Self::Item> {
1929        if Self::is_empty(self) {
1930            return None;
1931        }
1932
1933        self.rem -= 1;
1934        let curr_slot = self.tail;
1935        // SAFETY: slots form an acyclic chain, so each slot is yielded at most
1936        // once per traversal; no two returned &mut T alias
1937        let node = unsafe { &mut *self.ptr.add(curr_slot) };
1938        self.tail = node.prev_slot(curr_slot, self.prev_tail);
1939        self.prev_tail = curr_slot;
1940        node.value.as_mut()
1941    }
1942}
1943
1944impl<'a, T> ExactSizeIterator for IterMut<'a, T> {}
1945
1946impl<'a, T> FusedIterator for IterMut<'a, T> {}
1947
1948impl<T> FromIterator<T> for XorList<T> {
1949    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
1950        let mut list = Self::new();
1951        list.extend(iter);
1952        list
1953    }
1954}
1955
1956impl<T> IntoIterator for XorList<T> {
1957    type Item = T;
1958    type IntoIter = IntoIter<T>;
1959
1960    fn into_iter(self) -> Self::IntoIter {
1961        IntoIter { list: self }
1962    }
1963}
1964
1965impl<'a, T> IntoIterator for &'a XorList<T> {
1966    type Item = &'a T;
1967    type IntoIter = Iter<'a, T>;
1968
1969    fn into_iter(self) -> Self::IntoIter {
1970        self.iter()
1971    }
1972}
1973
1974impl<'a, T> IntoIterator for &'a mut XorList<T> {
1975    type Item = &'a mut T;
1976    type IntoIter = IterMut<'a, T>;
1977
1978    fn into_iter(self) -> Self::IntoIter {
1979        self.iter_mut()
1980    }
1981}
1982
1983/// An owning iterator over the elements of a [`XorList`].
1984///
1985/// This `struct` is created by the [`into_iter`](IntoIterator::into_iter)
1986/// method on [`XorList`] (provided by the [`IntoIterator`] trait). See its
1987/// documentation for more.
1988#[derive(Clone)]
1989pub struct IntoIter<T> {
1990    list: XorList<T>,
1991}
1992
1993impl<T> Iterator for IntoIter<T> {
1994    type Item = T;
1995
1996    #[inline]
1997    fn next(&mut self) -> Option<T> {
1998        self.list.pop_front()
1999    }
2000
2001    #[inline]
2002    fn size_hint(&self) -> (usize, Option<usize>) {
2003        (self.list.len(), Some(self.list.len()))
2004    }
2005
2006    #[inline]
2007    fn last(mut self) -> Option<T> {
2008        self.next_back()
2009    }
2010}
2011
2012impl<T> DoubleEndedIterator for IntoIter<T> {
2013    fn next_back(&mut self) -> Option<T> {
2014        self.list.pop_back()
2015    }
2016}
2017
2018impl<T> ExactSizeIterator for IntoIter<T> {}
2019
2020impl<T> FusedIterator for IntoIter<T> {}
2021
2022impl<T: fmt::Debug> fmt::Debug for IntoIter<T> {
2023    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2024        f.debug_tuple("IntoIter").field(&self.list).finish()
2025    }
2026}