intrex 0.1.1

//! Mutable linked list accessor.
use core::{cmp::Ordering, mem::swap};

use super::*;
use crate::sort_slist;

/// Mutably borrow the [`Link`] for `$index`. Panics if
/// [`ListAccessorMut::map_link`] returns `None`.
macro_rules! link {
    ($accessor:expr, $index:expr) => {
        ($accessor.map_link)($accessor.pool.index_mut($index))
            .as_mut()
            .unwrap()
    };
}

/// A storage for elements.
///
/// This is automatically implemented for all types implementing
/// [`ops::IndexMut`].
pub trait PoolMut<Index>: accessor::Pool<Index> {
    /// Mutably borrow the element at index `index`.
    fn index_mut(&mut self, index: Index) -> &mut Self::Element;
}

impl<T, Index> PoolMut<Index> for T
where
    T: ?Sized + ops::IndexMut<Index>,
{
    #[inline]
    fn index_mut(&mut self, index: Index) -> &mut Self::Element {
        ops::IndexMut::index_mut(self, index)
    }
}

impl<Index> Head<Index> {
    /// Create a mutable accessor to the list.
    #[inline]
    pub fn accessor_mut<'head, 'pool, Pool, MapLink, Element>(
        &'head mut self,
        pool: &'pool mut Pool,
        map_link: MapLink,
    ) -> ListAccessorMut<'head, 'pool, Index, Pool, MapLink>
    where
        Pool: ?Sized + PoolMut<Index, Element = Element>,
        MapLink: Fn(&mut Element) -> &mut Option<Link<Index>>,
    {
        ListAccessorMut {
            head: self,
            pool,
            map_link,
        }
    }
}

/// Mutable accessor to a linked list.
///
/// Created by [`Head::accessor_mut`].
#[derive(Debug)]
pub struct ListAccessorMut<'head, 'pool, Index, Pool: ?Sized, MapLink> {
    head: &'head mut Head<Index>,
    pool: &'pool mut Pool,
    map_link: MapLink,
}

impl<'head, 'pool, Index, Pool, MapLink, Element>
    ListAccessorMut<'head, 'pool, Index, Pool, MapLink>
where
    Pool: ?Sized + PoolMut<Index, Element = Element>,
    MapLink: Fn(&mut Element) -> &mut Option<Link<Index>>,
    Index: PartialEq + Clone,
{
    /// Borrow the list header.
    #[inline]
    pub fn head(&self) -> &Head<Index> {
        self.head
    }

    /// Mutably borrow the list header.
    #[inline]
    pub fn head_mut(&mut self) -> &mut Head<Index> {
        self.head
    }

    /// Borrow the element pool.
    #[inline]
    pub fn pool(&self) -> &Pool {
        self.pool
    }

    /// Mutably borrow the element pool.
    #[inline]
    pub fn pool_mut(&mut self) -> &mut Pool {
        self.pool
    }

    /// Check if the list is empty.
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.head.is_empty()
    }

    /// Get the first element's index.
    #[inline]
    pub fn front_index(&mut self) -> Option<Index> {
        self.head.first.clone()
    }

    /// Get the last element's index.
    #[inline]
    pub fn back_index(&mut self) -> Option<Index> {
        self.head.first.clone().map(|p| link!(self, p).prev.clone())
    }

    /// Mutably borrow the first element.
    #[doc(alias = "first_mut")]
    #[inline]
    pub fn front_mut(&mut self) -> Option<&mut Element> {
        if let Some(p) = self.front_index() {
            Some(self.pool.index_mut(p))
        } else {
            None
        }
    }

    /// Mutably borrow the last element.
    #[doc(alias = "last_mut")]
    #[inline]
    pub fn back_mut(&mut self) -> Option<&mut Element> {
        if let Some(p) = self.back_index() {
            Some(self.pool.index_mut(p))
        } else {
            None
        }
    }

    /// Reborrow `self` with [`Self::head`] replaced.
    #[inline]
    fn with_head<'head_>(
        &mut self,
        head: &'head_ mut Head<Index>,
    ) -> ListAccessorMut<'head_, '_, Index, Pool, &MapLink> {
        ListAccessorMut {
            head,
            pool: self.pool,
            map_link: &self.map_link,
        }
    }

    /// Unlink all elements.
    ///
    /// This is a linear time operation.
    /// If you do not reuse the elements (and therefore it is safe to leave
    /// their `Option<Link>` fields set), consider simply dropping `self`
    /// instead.
    pub fn clear(&mut self) {
        let Some(mut cur) = self.head.first.take() else {
            return;
        };
        loop {
            let Some(link) = (self.map_link)(self.pool.index_mut(cur)).take() else {
                return;
            };
            cur = link.next;
        }
    }

    /// Insert `item` before the position `p` (if `at` is `Some(p)`) or to the
    /// the list's back (if `at` is `None`).
    ///
    /// # Examples
    ///
    /// ```rust
    /// use intrex::list;
    ///
    /// let mut nodes: Vec<Option<list::Link>> = vec![None; 5];
    ///
    /// // `head` = `[0, 1, 2]`
    /// let mut head = list::Head::default();
    /// let mut accessor = head.accessor_mut(&mut nodes, |n| n);
    /// accessor.extend([0, 1, 2]);
    ///
    /// // Insert `3` before `1`
    /// accessor.insert(3, Some(1));
    ///
    /// assert_eq!(
    ///     head.accessor(&nodes, |n| n).indices().collect::<Vec<_>>(),
    ///     vec![0, 3, 1, 2],
    /// )
    /// ```
    pub fn insert(&mut self, item: Index, at: Option<Index>) {
        {
            debug_assert!(
                (self.map_link)(self.pool.index_mut(item.clone())).is_none(),
                "item is already linked"
            );
        }

        if let Some(first) = self.head.first.clone() {
            let (next, update_first) = if let Some(at) = at {
                let update_first = at == first;
                (at, update_first)
            } else {
                (first, false)
            };

            let prev = link!(self, next.clone()).prev.clone();
            link!(self, prev.clone()).next = item.clone();
            link!(self, next.clone()).prev = item.clone();
            *(self.map_link)(self.pool.index_mut(item.clone())) = Some(Link { prev, next });

            if update_first {
                self.head.first = Some(item);
            }
        } else {
            debug_assert!(at.is_none());

            let link = (self.map_link)(self.pool.index_mut(item.clone()));
            self.head.first = Some(item.clone());
            *link = Some(Link {
                prev: item.clone(),
                next: item,
            });
        }
    }

    /// Insert all elements from `other` before the position `at` (if `at` is
    /// `Some(p)`) or to the list's back (if `at` is `None`).
    ///
    /// `other` will be empty after this operation.
    ///
    /// This is a constant-time operation.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use intrex::list;
    ///
    /// let mut nodes: Vec<Option<list::Link>> = vec![None; 5];
    ///
    /// // `head` = `[0, 1, 2]`
    /// let mut head = list::Head::default();
    /// head.accessor_mut(&mut nodes, |n| n).extend([0, 1, 2]);
    ///
    /// // `other_head` = `[3, 4]`
    /// let mut other_head = list::Head::default();
    /// other_head.accessor_mut(&mut nodes, |n| n).extend([3, 4]);
    ///
    /// // Insert `other_head` before `1` in `head`
    /// let mut accessor = head.accessor_mut(&mut nodes, |n| n);
    /// accessor.insert_list(&mut other_head, Some(1));
    ///
    /// assert_eq!(
    ///     head.accessor(&nodes, |n| n).indices().collect::<Vec<_>>(),
    ///     vec![0, 3, 4, 1, 2],
    /// );
    /// assert!(other_head.is_empty());
    /// ```
    pub fn insert_list(&mut self, other: &mut Head<Index>, at: Option<Index>) {
        let mut other = core::mem::take(other);

        let Some(other_first) = other.first.clone() else {
            return;
        };

        let Some(first) = self.head.first.clone() else {
            debug_assert!(at.is_none());
            self.head.first = Some(other_first);
            return;
        };

        let other_last = self.with_head(&mut other).back_index().unwrap();

        let (next, update_first) = if let Some(at) = at {
            let update_first = at == first;
            (at, update_first)
        } else {
            (first, false)
        };

        let prev = link!(self, next.clone()).prev.clone();

        link!(self, prev.clone()).next = other_first.clone();
        link!(self, next.clone()).prev = other_last.clone();
        link!(self, other_first.clone()).prev = prev;
        link!(self, other_last.clone()).next = next;

        if update_first {
            self.head.first = Some(other_first);
        }
    }

    /// Append an element at index `item` to the back of the list.
    pub fn push_back(&mut self, item: Index) {
        self.insert(item, None);
    }

    /// Prepend an element at index `item` to the front of the list.
    pub fn push_front(&mut self, item: Index) {
        let at = self.front_index();
        self.insert(item, at);
    }

    /// Move all elements of `other` to the back of `self`, leaving `other` empty.
    ///
    /// This is a constant-time operation.
    #[inline]
    pub fn append(&mut self, other: &mut Head<Index>) {
        self.insert_list(other, None);
    }

    /// Move all elements of `other` to the front of `self`, leaving `other` empty.
    ///
    /// This is a constant-time operation.
    #[inline]
    pub fn prepend(&mut self, other: &mut Head<Index>) {
        let at = self.front_index();
        self.insert_list(other, at);
    }

    /// Remove `item` from the list. Returns `item`.
    pub fn remove(&mut self, item: Index) -> Index {
        {
            debug_assert!(
                (self.map_link)(self.pool.index_mut(item.clone())).is_some(),
                "item is not linked"
            );
        }

        let link: Link<Index> = {
            let link_ref = (self.map_link)(self.pool.index_mut(item.clone()));
            if self.head.first.as_ref() == Some(&item) {
                let next = link_ref.as_ref().unwrap().next.clone();
                if next == item {
                    // The list just became empty
                    self.head.first = None;
                    *link_ref = None;
                    return item;
                }

                // Move the head pointer
                self.head.first = Some(next);
            }

            link_ref.clone().unwrap()
        };

        link!(self, link.prev.clone()).next = link.next.clone();
        link!(self, link.next).prev = link.prev;
        *(self.map_link)(self.pool.index_mut(item.clone())) = None;

        item
    }

    /// Swap the elements in a given range with another list.
    ///
    /// This is a constant-time operation.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use intrex::list;
    ///
    /// let mut nodes: Vec<Option<list::Link>> = vec![None; 5];
    ///
    /// // `head` = `[0, 1, 2]`
    /// let mut head = list::Head::default();
    /// head.accessor_mut(&mut nodes, |n| n).extend([0, 1, 2]);
    ///
    /// // `other_head` = `[3, 4]`
    /// let mut other_head = list::Head::default();
    /// other_head.accessor_mut(&mut nodes, |n| n).extend([3, 4]);
    ///
    /// // Swap `[1, 2]` in `head` with `other_head`
    /// head.accessor_mut(&mut nodes, |n| n)
    ///     .swap_range(Some(1).., &mut other_head);
    ///
    /// assert_eq!(
    ///     head.accessor(&nodes, |n| n).indices().collect::<Vec<_>>(),
    ///     vec![0, 3, 4],
    /// );
    /// assert_eq!(
    ///     other_head.accessor(&nodes, |n| n).indices().collect::<Vec<_>>(),
    ///     vec![1, 2],
    /// );
    /// ```
    pub fn swap_range(
        &mut self,
        range: impl ops::RangeBounds<Option<Index>>,
        other: &mut Head<Index>,
    ) {
        let (range, range_next) =
            resolve_range(range, |i| link!(self, i).clone(), self.head.first.clone());

        let Some(range) = range else {
            // If `range` is empty, delegate to `insert_list`.
            return self.insert_list(other, range_next.clone());
        };

        self.swap_range_inner(range, range_next, other)
    }

    /// An internal method of [`Self::swap_range`]. Swaps
    /// `start_inner..=end_inner` (= `start_inner..range_next`) with `*other`.
    /// Returns `end-outer`.
    fn swap_range_inner(
        &mut self,
        [start_inner, end_inner]: [Index; 2],
        end_outer: Option<Index>,
        other: &mut Head<Index>,
    ) {
        // `self` is not empty.
        let self_start = self.front_index().unwrap();

        // Both-exclusive range with wrap around
        let start_outer_wrap = link!(self, start_inner.clone()).prev.clone();
        let end_outer_wrap = link!(self, end_inner.clone()).next.clone();

        // If `range` covers entire `self`, swap the `Head`s.
        if end_outer_wrap == start_inner {
            assert!(start_inner == self_start);
            swap(self.head, other);
            return;
        }

        let mut other_acc = self.with_head(other);
        if let (Some(other_first), Some(other_last)) =
            (other_acc.front_index(), other_acc.back_index())
        {
            // If `other` is not empty...

            // Link `range`'s outer elements to `other`'s elements
            link!(self, start_outer_wrap.clone()).next = other_first.clone();
            link!(self, end_outer_wrap.clone()).prev = other_last.clone();
            link!(self, other_first.clone()).prev = start_outer_wrap.clone();
            link!(self, other_last.clone()).next = end_outer_wrap.clone();

            if start_inner == self_start {
                self.head.first = Some(other_first);
            }
        } else {
            link!(self, start_outer_wrap.clone()).next = end_outer_wrap.clone();
            link!(self, end_outer_wrap.clone()).prev = start_outer_wrap.clone();

            if start_inner == self_start {
                debug_assert!(end_outer.is_some());
                self.head.first = end_outer.clone();
            }
        }

        // Update `other` to store `range`'s inner elements
        link!(self, start_inner.clone()).prev = end_inner.clone();
        link!(self, end_inner.clone()).next = start_inner.clone();

        *other = Head {
            first: Some(start_inner),
        };
    }

    /// Replace the elements in a given range with another list, returning a
    /// new list containing the replaced elements.
    ///
    /// This is a constant-time operation.
    #[must_use = "this method returns a new list"]
    #[inline]
    pub fn replace_range(
        &mut self,
        range: impl ops::RangeBounds<Option<Index>>,
        mut other: Head<Index>,
    ) -> Head<Index> {
        self.swap_range(range, &mut other);
        other
    }

    /// Remove the elements in a given range, returning a new list containing
    /// the removed elements.
    ///
    /// This is a constant-time operation.
    #[must_use = "this method returns a new list"]
    #[doc(alias = "split_off")]
    #[inline]
    pub fn take_range(&mut self, range: impl ops::RangeBounds<Option<Index>>) -> Head<Index> {
        self.replace_range(range, Head::default())
    }

    /// Remove and return the last element's index.
    pub fn pop_back(&mut self) -> Option<Index> {
        self.back_index().map(|item| self.remove(item))
    }

    /// Remove and return the first element's index.
    pub fn pop_front(&mut self) -> Option<Index> {
        self.front_index().map(|item| self.remove(item))
    }

    /// Find the next element of the element at index `i`.
    #[inline]
    pub fn next_index(&mut self, i: Index) -> Option<Index> {
        Some(link!(self, i).next.clone()).filter(|i| *i != *self.head.first.as_ref().unwrap())
    }

    /// Find the previous element of the element at index `i`.
    #[inline]
    pub fn prev_index(&mut self, i: Index) -> Option<Index> {
        (i != *self.head.first.as_ref().unwrap()).then(|| link!(self, i).prev.clone())
    }

    /// Call the specified closure for every element, passing a mutable
    /// reference for each of them.
    #[inline]
    pub fn for_each_mut<B>(
        &mut self,
        mut f: impl FnMut(Index, &mut Element) -> ops::ControlFlow<B>,
    ) -> ops::ControlFlow<B> {
        let Some(first) = self.head.first.clone() else {
            return ops::ControlFlow::Continue(());
        };
        let mut current = first.clone();
        loop {
            let next = link!(self, current.clone()).next.clone();
            f(current.clone(), self.pool.index_mut(current))?;
            if next == first {
                break;
            } else {
                current = next;
            }
        }
        ops::ControlFlow::Continue(())
    }

    /// Call the specified closure for every element in a given range, passing
    /// a mutable reference for each of them.
    #[inline]
    pub fn for_each_in_range_mut<B>(
        &mut self,
        range: impl ops::RangeBounds<Option<Index>>,
        mut f: impl FnMut(Index, &mut Element) -> ops::ControlFlow<B>,
    ) -> ops::ControlFlow<B> {
        let (Some([first, last]), _) =
            resolve_range(range, |i| link!(self, i).clone(), self.head.first.clone())
        else {
            return ops::ControlFlow::Continue(());
        };
        let mut current = first;
        loop {
            let next = (current != last).then(|| link!(self, current.clone()).next.clone());
            f(current.clone(), self.pool.index_mut(current))?;
            let Some(next) = next else { break };
            current = next;
        }
        ops::ControlFlow::Continue(())
    }

    /// Rotate the list in-place such that the first element move to the back
    /// while the last `len - 1` elements move to the front.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use intrex::list;
    ///
    /// let mut nodes: Vec<Option<list::Link>> = vec![None; 5];
    ///
    /// // `head` = `[0, 1, 2]`
    /// let mut head = list::Head::default();
    /// let mut accessor = head.accessor_mut(&mut nodes, |n| n);
    /// accessor.extend([0, 1, 2]);
    ///
    /// accessor.rotate_left_once();
    ///
    /// assert_eq!(
    ///     head.accessor(&nodes, |n| n).indices().collect::<Vec<_>>(),
    ///     vec![1, 2, 0],
    /// );
    /// ```
    pub fn rotate_left_once(&mut self) {
        let Some(front_index) = self.front_index() else {
            return;
        };
        self.head.first = self.next_index(front_index);
    }

    /// Rotate the list in-place such that the last element move to the front
    /// while the first `len - 1` elements move to the back.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use intrex::list;
    ///
    /// let mut nodes: Vec<Option<list::Link>> = vec![None; 5];
    ///
    /// // `head` = `[0, 1, 2]`
    /// let mut head = list::Head::default();
    /// let mut accessor = head.accessor_mut(&mut nodes, |n| n);
    /// accessor.extend([0, 1, 2]);
    ///
    /// accessor.rotate_right_once();
    ///
    /// assert_eq!(
    ///     head.accessor(&nodes, |n| n).indices().collect::<Vec<_>>(),
    ///     vec![2, 0, 1],
    /// );
    /// ```
    pub fn rotate_right_once(&mut self) {
        self.head.first = self.back_index();
    }

    /// Sort the list in ascending order, preserving the initial order of
    /// equal elements.
    ///
    /// This method uses [`sort_slist::sort`] for sorting.
    pub fn sort(&mut self)
    where
        Element: Ord,
    {
        self.sort_inner(|pool, lhs, rhs| pool.index(lhs) < pool.index(rhs));
    }

    /// Sort the list in ascending order with a key extraction function,
    /// preserving the initial order of equal elements.
    ///
    /// This method uses [`sort_slist::sort`] for sorting.
    pub fn sort_by_key<F, K>(&mut self, mut f: F)
    where
        F: FnMut(&mut Pool, Index) -> K,
        K: Ord,
    {
        self.sort_inner(|pool, lhs, rhs| f(pool, lhs) < f(pool, rhs));
    }

    /// Sort the list in ascending order with a comparison function,
    /// preserving the initial order of equal elements.
    ///
    /// This method uses [`sort_slist::sort`] for sorting.
    pub fn sort_by<F, K>(&mut self, mut f: F)
    where
        F: FnMut(&mut Pool, Index, Index) -> Ordering,
    {
        self.sort_inner(|pool, lhs, rhs| f(pool, lhs, rhs) == Ordering::Less);
    }

    fn sort_inner(&mut self, less_than: impl FnMut(&mut Pool, Index, Index) -> bool) {
        struct Accessor<'a, Pool: ?Sized, MapLink, LessThan> {
            pool: &'a mut Pool,
            map_link: &'a MapLink,
            less_than: LessThan,
        }

        impl<Pool, MapLink, LessThan, Element, Index> sort_slist::SortAccessor<Index>
            for Accessor<'_, Pool, MapLink, LessThan>
        where
            Pool: ?Sized + PoolMut<Index, Element = Element>,
            MapLink: Fn(&mut Element) -> &mut Option<Link<Index>>,
            Index: PartialEq + Clone,
            LessThan: FnMut(&mut Pool, Index, Index) -> bool,
        {
            #[inline]
            fn next(&mut self, index: Index) -> Option<Index> {
                Some(
                    (self.map_link)(self.pool.index_mut(index))
                        .as_mut()?
                        .next
                        .clone(),
                )
            }

            #[inline]
            fn set_next(&mut self, index: Index, next: Option<Index>) {
                *(self.map_link)(self.pool.index_mut(index)) = next.map(|i| Link {
                    prev: i.clone(),
                    next: i,
                });
            }

            #[inline]
            fn lt(&mut self, lhs: Index, rhs: Index) -> bool {
                (self.less_than)(self.pool, lhs, rhs)
            }
        }

        // Turn it into a non-circular list
        let (Some(front_index), Some(back_index)) = (self.front_index(), self.back_index()) else {
            // Empty
            return;
        };
        *(self.map_link)(self.pool.index_mut(back_index)) = None;

        // Sort it
        let front_index = sort_slist::sort(
            &mut Accessor {
                pool: self.pool,
                map_link: &self.map_link,
                less_than,
            },
            Some(front_index),
        )
        .unwrap();

        // Restore double links
        match (self.map_link)(self.pool.index_mut(front_index.clone())) {
            Some(front_link) => {
                // Fix links for all elements but the first
                let mut cur = front_index.clone();
                let mut next = front_link.next.clone();
                loop {
                    match (self.map_link)(self.pool.index_mut(next.clone())) {
                        Some(next_link) => {
                            next_link.prev = cur;
                            cur = next;
                            next = next_link.next.clone();
                        }
                        next_link @ None => {
                            // `next` is the last element
                            *next_link = Some(Link {
                                prev: cur,
                                next: front_index.clone(),
                            });
                            break;
                        }
                    }
                }

                // Fix the link for the first element
                link!(self, front_index.clone()).prev = next;
            }
            front_link @ None => {
                // Fix the link for the only element
                *front_link = Some(Link {
                    prev: front_index.clone(),
                    next: front_index.clone(),
                })
            }
        }

        self.head.first = Some(front_index);
    }
}

impl<'head, 'pool, Index, Pool, MapLink, Element> Extend<Index>
    for ListAccessorMut<'head, 'pool, Index, Pool, MapLink>
where
    Pool: ?Sized + PoolMut<Index, Element = Element>,
    MapLink: Fn(&mut Element) -> &mut Option<Link<Index>>,
    Index: PartialEq + Clone,
{
    fn extend<I: IntoIterator<Item = Index>>(&mut self, iter: I) {
        for item in iter {
            self.push_back(item);
        }
    }
}

#[cfg(test)]
mod tests {
    use proptest::prelude::*;
    use std::{println, vec, vec::Vec};

    use super::*;
    use crate::list::tests::push;

    #[test]
    fn basic_mut() {
        let mut pool = Vec::new();
        let mut head = Head::new();
        let mut accessor = head.accessor_mut(&mut pool, |&mut (_, ref mut link)| link);

        let ptr1 = push(accessor.pool_mut(), (1, None));
        accessor.push_back(ptr1);

        let ptr2 = push(accessor.pool_mut(), (2, None));
        accessor.push_back(ptr2);

        let ptr3 = push(accessor.pool_mut(), (3, None));
        accessor.push_front(ptr3);

        println!("{:?}", (accessor.pool(), accessor.head()));

        assert!(!accessor.is_empty());
        assert_eq!(accessor.front_index(), Some(ptr3));
        assert_eq!(accessor.back_index(), Some(ptr2));
        assert_eq!(accessor.front_mut().unwrap().0, 3);
        assert_eq!(accessor.back_mut().unwrap().0, 2);

        let mut items = Vec::new();
        _ = accessor.for_each_mut(|_, &mut (x, _)| {
            items.push(x);
            ops::ControlFlow::Continue::<()>(())
        });
        assert_eq!(items, vec![3, 1, 2]);

        accessor.remove(ptr1);
        accessor.remove(ptr2);
        accessor.remove(ptr3);

        assert!(accessor.is_empty());
    }

    #[proptest::property_test]
    fn pt_insert_list(elems1: Vec<u8>, elems2: Vec<u8>, insert_at: prop::sample::Index) {
        let mut pool: Vec<(u8, Option<Link>)> = Vec::new();
        let mut head1 = Head::new();
        let mut head2 = Head::new();

        for &value in &elems1 {
            let ptr = push(&mut pool, (value, None));
            head1
                .accessor_mut(&mut pool, |&mut (_, ref mut link)| link)
                .push_back(ptr);
        }

        for &value in &elems2 {
            let ptr = push(&mut pool, (value, None));
            head2
                .accessor_mut(&mut pool, |&mut (_, ref mut link)| link)
                .push_back(ptr);
        }

        let at_pos = insert_at.index(elems1.len() + 1);
        let at = head1
            .accessor(&pool, |(_, link)| link)
            .indices()
            .nth(at_pos);

        head1
            .accessor_mut(&mut pool, |&mut (_, ref mut link)| link)
            .insert_list(&mut head2, at);
        assert!(head2.is_empty());

        head1
            .accessor(&pool, |(_, link)| link)
            .validate()
            .expect("validate");

        let mut expected = Vec::new();
        expected.extend(&elems1[..at_pos]);
        expected.extend(&elems2);
        expected.extend(&elems1[at_pos..]);

        let got: Vec<u8> = head1
            .accessor(&pool, |(_, link)| link)
            .values()
            .map(|&(v, _)| v)
            .collect();
        assert_eq!(got, expected);
    }

    #[proptest::property_test]
    fn pt_swap_range(elems1: Vec<u8>, elems2: Vec<u8>, [start, end]: [prop::sample::Index; 2]) {
        let mut pool: Vec<(u8, Option<Link>)> = Vec::new();
        let mut head1 = Head::new();
        let mut head2 = Head::new();

        for &value in &elems1 {
            let ptr = push(&mut pool, (value, None));
            head1
                .accessor_mut(&mut pool, |&mut (_, ref mut link)| link)
                .push_back(ptr);
        }

        for &value in &elems2 {
            let ptr = push(&mut pool, (value, None));
            head2
                .accessor_mut(&mut pool, |&mut (_, ref mut link)| link)
                .push_back(ptr);
        }

        let start = start.index(elems1.len() + 1);
        let end = end.index(elems1.len() + 1 - start) + start;

        let [start_ind, end_ind] = [start, end].map(|i| (i < elems1.len()).then_some(i));

        head1
            .accessor_mut(&mut pool, |&mut (_, ref mut link)| link)
            .swap_range(start_ind..end_ind, &mut head2);

        head1
            .accessor(&pool, |(_, link)| link)
            .validate()
            .expect("validate head1");
        head2
            .accessor(&pool, |(_, link)| link)
            .validate()
            .expect("validate head2");

        let mut expected1: Vec<u8> = elems1.clone();
        let expected2: Vec<u8> = expected1
            .splice(start..end, elems2.iter().copied())
            .collect();

        let got1: Vec<u8> = head1
            .accessor(&pool, |(_, link)| link)
            .values()
            .map(|&(v, _)| v)
            .collect();
        let got2: Vec<u8> = head2
            .accessor(&pool, |(_, link)| link)
            .values()
            .map(|&(v, _)| v)
            .collect();

        assert_eq!(got1, expected1);
        assert_eq!(got2, expected2);
    }

    #[proptest::property_test]
    fn pt_sort(elems: Vec<u8>) {
        let mut pool: Vec<(u8, Option<Link>)> = elems.iter().map(|&value| (value, None)).collect();
        let mut head = Head::new();

        for i in 0..elems.len() {
            head.accessor_mut(&mut pool, |&mut (_, ref mut link)| link)
                .push_back(i);
        }

        head.accessor(&pool, |(_, link)| link)
            .validate()
            .expect("validate");

        // Sort it
        head.accessor_mut(&mut pool, |&mut (_, ref mut link)| link)
            .sort_by_key(|pool, index| pool[index].0);

        // Validate the result
        head.accessor(&pool, |(_, link)| link)
            .validate()
            .expect("post-sort validate");

        let mut elems_expected = elems;
        elems_expected.sort_unstable();

        let elems_got: Vec<u8> = head
            .accessor(&pool, |(_, link)| link)
            .values()
            .map(|&(value, _)| value)
            .collect();

        assert_eq!(elems_got, elems_expected);
    }
}