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}