intrex 0.2.0

//! Intrusive circular doubly linked list with items addressed by indices.
//!
//! # Node Access Traits
//!
//! The list accessors manipulate nodes through application-provided types
//! (supplied through a `Nodes` generic parameter) implementing *node access
//! traits*.
//! There are two categories of such traits, which are described in the
//! subsections below.
//!
//! ## Links
//!
//! The following traits provide access to [`Link`]s associated with nodes:
//!
//! | Trait            | Receiver         | Read | Write |
//! | ---------------- | ---------------- | ---- | ----- |
//! | [`NodesLink`]    | `&NodesLink`     | x    |       |
//! | [`NodesLinkMut`] | `&mut NodesLink` | x    | x     |
//!
//! They have straightforward forwarding implementations for reference types
//! (`&T`, `&mut T`).
//!
//! | Implementor                        | Implements       |
//! | ---------------------------------- | ---------------- |
//! | `&'this impl `[`NodesLink`]        | [`NodesLink`]    |
//! | `&'this mut impl `[`NodesLink`]    | [`NodesLink`]    |
//! | `&'this mut impl `[`NodesLinkMut`] | [`NodesLinkMut`] |
//!
//! ## Values
//!
//! This module uses the node value access traits defined in
//! [`crate::node_data`].
//!
//! # Ranges
//!
//! Methods, such as [`accessor_mut::ListAccessorMut::swap_range`], receive a
//! range inside the list.
//! The range is specified by a value of a type implementing
//! [`ops::RangeBounds`]`<`[`Option`]`<Index>>`.
//! The following rules apply:
//!
//! - `None` refers to the one-past-end imaginary element.
//!
//! - The start bound must not be [`ops::Bound::Excluded`]`(None)`.
//!
//! - The end bound must not be [`ops::Bound::Included`]`(None)`.
//!
//! - Let `P(Included(x) | Excluded(x)) := x`. If both `P(start_bound)` and
//!   `P(end_bound)` are defined, `P(end_bound)` must not precede
//!   `P(start_bound)`.
//!
//! - If both bounds are [`ops::Bound::Excluded`], they must not be equal.
//!   (Such ranges have the length of `-1`.)
//!
//! > Some violations are ignored and cause data corruption to maintain
//! > constant time complexity.
//!
//! Examples (assuming the `i`-th element of the list has index `i`):
//!
//! ```text
//!                            1   2   3   4   5   6   7
//! -------------------------------------------------------
//! Some(2) .. Some(5)            [𝟮   3   4]  𝟱                  
//! Some(2) .. None               [𝟮   3   4   5   6   7]
//! Some(2) ..                    [𝟮   3   4   5   6   7]
//! Some(2) ..=Some(5)            [𝟮   3   4   𝟱]              
//! None    .. None                                       []
//! None    ..                                            []
//!         .. Some(4)        [1   2   3]  𝟰
//!         .. None           [1   2   3   4   5   6   7]
//!         ..                [1   2   3   4   5   6   7]
//! ```
//!
//! Invalid examples:
//!
//! | Value | Reason |
//! | ----- | ------ |
//! | `Some(1)..=None` | The inclusive end bound must not be `None` |
//! | `Some(4)..Some(1)` | The item at index `1` precedes the item at index `4` |
//! | `None..Some(1)` | The item at index `1` precedes the one-past-end imaginary item (`None`) |
#![warn(missing_docs)]
use core::ops;

pub mod accessor;
pub mod accessor_mut;
// FIXME: Move to top-level?
mod nodes;

pub use nodes::*;

/// Circualr linked list header.
#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
pub struct Head<Index = usize> {
    /// The index of the first element, if the list is not empty.
    pub first: Option<Index>,
}

impl<Index> Default for Head<Index> {
    #[inline]
    fn default() -> Self {
        Self { first: None }
    }
}

/// Links to neighbor items.
#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
pub struct Link<Index = usize> {
    /// The index of the previous element.
    ///
    /// If the current element is the first element, this points to the last
    /// element.
    pub prev: Index,
    /// The index of the next element.
    ///
    /// If the current element is the last element, this points to the first
    /// element.
    pub next: Index,
}

impl<Index> Head<Index> {
    /// Construct an empty list header.
    #[inline]
    pub fn new() -> Self {
        Self::default()
    }

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

/// Normalize `range` into `(inclusive_range, next)`. May panic if it does not
/// follow [the range rules](self#ranges).
fn resolve_range<Index>(
    range: impl ops::RangeBounds<Option<Index>>,
    mut link: impl FnMut(Index) -> Link<Index>,
    head: Option<Index>,
) -> (Option<[Index; 2]>, Option<Index>)
where
    Index: Clone + PartialEq,
{
    let mut next = |i: Index| Some(link(i).next).filter(|i| Some(i) != head.as_ref());

    let [start, end] = [range.start_bound(), range.end_bound()];

    let out_next = match end {
        ops::Bound::Included(Some(i)) => next(i.clone()),
        ops::Bound::Included(None) => panic!("end bound must not be `Included(None)`"),
        ops::Bound::Excluded(i) => i.clone(),
        ops::Bound::Unbounded => None,
    };

    let Some(start_incl) = (match start {
        ops::Bound::Included(i) => i.clone(),
        ops::Bound::Excluded(Some(i)) => {
            assert!(
                start != end,
                "both-exclusive range must not have overlapping endpoints"
            );

            if let ops::Bound::Included(Some(j)) = end
                && j == i
            {
                return (None, out_next);
            }

            next(i.clone())
        }
        ops::Bound::Excluded(None) => panic!("start bound must not be `Excluded(None)`"),
        ops::Bound::Unbounded => head.clone(),
    }) else {
        return (None, out_next);
    };

    let end_incl = match end {
        ops::Bound::Included(Some(i)) => i.clone(),
        ops::Bound::Included(None) => panic!("end bound must not be `Included(None)`"),
        ops::Bound::Excluded(Some(i)) => {
            if *i == start_incl {
                return (None, out_next);
            } else {
                link(i.clone()).prev
            }
        }
        ops::Bound::Unbounded | ops::Bound::Excluded(None) => link(head.unwrap()).prev,
    };

    (Some([start_incl, end_incl]), out_next)
}

#[cfg(test)]
mod tests {
    use super::*;
    use core::mem::swap;
    use proptest::prelude::*;
    use std::vec::Vec;
    use try_match::match_ok;

    pub(crate) fn push<Element>(this: &mut Vec<Element>, x: Element) -> usize {
        let i = this.len();
        this.push(x);
        i
    }

    /// Test [`resolve_range`] for the zero-element list.
    #[test]
    fn test_resolve_range0() {
        for start in [ops::Bound::Unbounded, ops::Bound::Included(None)] {
            for end in [ops::Bound::Unbounded, ops::Bound::Excluded(None)] {
                assert_eq!(
                    resolve_range::<usize>((start, end), |_| unreachable!(), None),
                    (None, None)
                );
            }
        }
    }

    #[derive(Debug, Clone)]
    struct PtResolveRangeParams {
        len: usize,
        start: ops::Bound<Option<usize>>,
        end: ops::Bound<Option<usize>>,
    }

    fn any_pt_resolve_range_params() -> impl Strategy<Value = PtResolveRangeParams> {
        (1..5_usize)
            .prop_flat_map(|len| {
                (
                    Just(len),
                    prop_oneof![
                        Just(ops::Bound::Unbounded),
                        Just(ops::Bound::Included(None)),
                        (0..len).prop_map(|i| ops::Bound::Included(Some(i))),
                        (0..len).prop_map(|i| ops::Bound::Excluded(Some(i))),
                    ],
                    prop_oneof![
                        Just(ops::Bound::Unbounded),
                        Just(ops::Bound::Excluded(None)),
                        (0..len).prop_map(|i| ops::Bound::Included(Some(i))),
                        (0..len).prop_map(|i| ops::Bound::Excluded(Some(i))),
                    ],
                )
            })
            .prop_map(|(len, start, end)| PtResolveRangeParams { len, start, end })
            // Make the input range valid
            .prop_map(|mut params| {
                if let (
                    ops::Bound::Included(start) | ops::Bound::Excluded(start),
                    ops::Bound::Included(end) | ops::Bound::Excluded(end),
                ) = (params.start, params.end)
                    && start.map(|x| !x) < end.map(|x| !x)
                {
                    swap(&mut params.start, &mut params.end);
                }

                if params.start == ops::Bound::Excluded(None) {
                    params.start = ops::Bound::Unbounded;
                }

                if params.end == ops::Bound::Included(None) {
                    params.end = ops::Bound::Unbounded;
                }

                if let (ops::Bound::Excluded(start), ops::Bound::Excluded(end)) =
                    (params.start, params.end)
                    && start == end
                {
                    params.start = ops::Bound::Included(start);
                }

                params
            })
    }

    #[proptest::property_test]
    fn pt_resolve_range(
        #[strategy = any_pt_resolve_range_params()]
        PtResolveRangeParams { len, start, end }: PtResolveRangeParams,
    ) {
        let (range_got, next_got) = resolve_range(
            (start, end),
            |i| Link {
                prev: (i + len - 1) % len,
                next: (i + 1) % len,
            },
            Some(0),
        );

        // Convert `None` (one-past-end) into index
        let [start2, end2] = [start, end].map(|b| match b {
            ops::Bound::Included(None) => ops::Bound::Included(len),
            ops::Bound::Excluded(None) => ops::Bound::Excluded(len),
            ops::Bound::Included(Some(i)) => ops::Bound::Included(i),
            ops::Bound::Excluded(Some(i)) => ops::Bound::Excluded(i),
            ops::Bound::Unbounded => ops::Bound::Unbounded,
        });

        // Check the elements included in `range_got`
        let membership_expected =
            || (0..len).filter(|i| ops::RangeBounds::contains(&(start2, end2), i));
        let range_expected = match_ok!(
            (membership_expected().min(), membership_expected().max()),
            (Some(s), Some(e)) => [s, e]
        );

        assert_eq!(range_got, range_expected);

        // Compare `next_got` against independent implementation that exploits
        // the simple structure of this list
        let next_expected = match end2 {
            ops::Bound::Included(i) => i + 1,
            ops::Bound::Excluded(i) => i,
            ops::Bound::Unbounded => len,
        };
        assert_eq!(next_got.unwrap_or(len), next_expected);
    }
}