pub use premade::*;

mod premade
{
    use {
        super::{
            modes::{
                limited::{
                    LimitReached,
                    Limited,
                    Ticker,
                },
                unlimited::Unlimited,
            },
            recursion::callstack::CallStack,
        },
        crate::{
            anticipated_or_like::Infallible,
            generic::equiv::{
                self,
                Equiv,
            },
            Node,
        },
        core::marker::PhantomData,
    };

    #[cfg(not(feature = "anticipate"))]
    use crate::like_anticipated::IntoOk as _;


    /// Equivalence predicate that cannot handle cyclic nor very-deep graphs, and that has the
    /// least overhead.
    ///
    /// This is similar to `#[derive(PartialEq)]` and so usually is not better than that, but
    /// could be useful for types where implementing [`Node`] in peculiar ways is useful for
    /// having different behavior than derived `PartialEq`.
    #[inline]
    pub fn equiv<N: Node>(
        a: N,
        b: N,
    ) -> N::Cmp
    {
        struct Args<N>(PhantomData<N>);

        impl<N: Node> equiv::Params for Args<N>
        {
            type DescendMode = Unlimited;
            type Error = Infallible;
            type Node = N;
            type RecurMode = CallStack;
        }

        let mut e = Equiv::<Args<N>>::default();
        #[allow(unstable_name_collisions)]
        e.equiv(a, b).into_ok()
    }


    /// Equivalence predicate that limits how many nodes are traversed, and that aborts early if
    /// the limit is reached.  Like [`equiv`](equiv()), this cannot handle cyclic nor very-deep
    /// graphs and has minimal overhead.
    ///
    /// # Errors
    /// If the limit is reached before completing, return `Err(LimitReached)`.
    #[inline]
    pub fn limited_equiv<N: Node, L: Ticker>(
        limit: L,
        a: N,
        b: N,
    ) -> Result<N::Cmp, LimitReached>
    {
        struct Args<N, L>(PhantomData<(N, L)>);

        impl<N: Node, L: Ticker> equiv::Params for Args<N, L>
        {
            type DescendMode = Limited<L>;
            type Error = LimitReached;
            type Node = N;
            type RecurMode = CallStack;
        }

        let mut e = Equiv::<Args<N, L>>::new(Limited(limit));
        e.equiv(a, b)
    }
}


/// Basic support, that cannot handle very-deep graphs, for recursion of the algorithm.
pub mod recursion
{
    /// Use the normal call-stack for the recursions done to descend node edges.
    pub mod callstack
    {
        use crate::{
            generic::equiv::{
                self,
                CounterpartsResult,
                EdgesIter,
                Equiv,
                RecurMode,
            },
            Cmp,
            Node,
        };

        /// Specifies use of the normal call-stack.
        ///
        /// Does depth-first preorder traversals.
        #[derive(Default)]
        #[non_exhaustive]
        pub struct CallStack;

        /// Enables [`CallStack`] to be used with the algorithm.
        impl<P> RecurMode<P> for CallStack
        where P: equiv::Params<RecurMode = Self>
        {
            type Error = P::Error;

            #[inline]
            fn recur(
                it: &mut Equiv<P>,
                edges_iter: EdgesIter<P::Node>,
            ) -> Result<<P::Node as Node>::Cmp, Self::Error>
            {
                for next in edges_iter {
                    match next {
                        Ok([a, b]) => match it.equiv_main(a, b) {
                            Ok(cmp) if cmp.is_equiv() => (),
                            result => return result,
                        },
                        Err(cmp_amount_edges) => return Ok(cmp_amount_edges),
                    }
                }
                Ok(Cmp::new_equiv())
            }

            #[inline]
            fn next(&mut self) -> Option<CounterpartsResult<P::Node>>
            {
                None
            }

            /// Only for compatibility with generic uses of recursion-mode types.  The call-stack
            /// does not need to be reset, so this is a no-op for this type.
            #[inline]
            fn reset(self) -> Self
            {
                self
            }
        }
    }
}

/// Modes of the algorithm that are useful in basic ways.
pub mod modes
{
    /// Do not limit the algorithm in how many nodes are traversed, and never abort early.
    pub mod unlimited
    {
        use crate::{
            anticipated_or_like::Infallible,
            generic::equiv::{
                self,
                DescendMode,
            },
        };

        /// Specifies not limiting the amount of nodes traversed.
        #[derive(Default)]
        #[allow(clippy::exhaustive_structs)]
        pub struct Unlimited;

        /// Enables [`Unlimited`] to be used with the algorithm.
        impl<P> DescendMode<P> for Unlimited
        where
            P: equiv::Params<DescendMode = Self>,
            Infallible: Into<P::Error>,
        {
            type Error = Infallible;

            /// Always start handling node edges.
            #[inline]
            fn do_edges(
                &mut self,
                _a: &P::Node,
                _b: &P::Node,
            ) -> Result<bool, Self::Error>
            {
                Ok(true)
            }

            /// Always traverse nodes, without limit.
            #[inline]
            fn do_traverse(&mut self) -> Result<bool, Self::Error>
            {
                Ok(true)
            }
        }
    }

    /// Limit the algorithm in how many nodes it is allowed to traverse before aborting early.
    pub mod limited
    {
        mod sealed
        {
            use core::ops::SubAssign;

            /// Any type of unsigned integer may be used with [`Limited`](super::Limited).
            pub trait Ticker: Ord + From<u8> + SubAssign {}
            impl Ticker for u8 {}
            impl Ticker for u16 {}
            impl Ticker for u32 {}
            impl Ticker for u64 {}
            impl Ticker for u128 {}
            impl Ticker for usize {}
        }

        pub(crate) use sealed::Ticker;

        use crate::{
            anticipated_or_like::Infallible,
            generic::equiv::{
                self,
                DescendMode,
            },
        };

        /// Specifies limiting the amount of nodes traversed.  The inner value is the limit.
        #[allow(clippy::exhaustive_structs)]
        pub struct Limited<T>(pub T);

        /// [`Err`] type returned when aborting early because a limit was reached.
        #[derive(Debug)]
        #[allow(clippy::exhaustive_structs)]
        pub struct LimitReached;

        /// Enables `P: equiv::Params<Error = LimitReached, RecurMode = R>`
        /// where `R: RecurMode<Error = Infallible>`.
        impl From<Infallible> for LimitReached
        {
            #[inline]
            fn from(_: Infallible) -> Self
            {
                #![allow(clippy::unreachable)] // Truly unreachable.
                unreachable!()
            }
        }

        /// Enables [`Limited`] to be used with the algorithm.
        impl<T, P> DescendMode<P> for Limited<T>
        where
            T: Ticker,
            P: equiv::Params<DescendMode = Self>,
            LimitReached: Into<P::Error>,
        {
            type Error = LimitReached;

            /// Always start handling node edges.
            #[inline]
            fn do_edges(
                &mut self,
                _a: &P::Node,
                _b: &P::Node,
            ) -> Result<bool, Self::Error>
            {
                Ok(true)
            }

            /// Enforce the limit on the amount of nodes traversed.
            #[inline]
            fn do_traverse(&mut self) -> Result<bool, Self::Error>
            {
                if self.0 > 0.into() {
                    self.0 -= 1.into();
                    Ok(true)
                }
                else {
                    Err(LimitReached)
                }
            }
        }
    }
}


#[cfg(test)]
#[allow(clippy::enum_glob_use)]
mod tests
{
    extern crate alloc;

    use {
        super::{
            modes::limited::{
                LimitReached,
                Limited,
            },
            recursion::callstack::CallStack,
        },
        crate::{
            generic::equiv::{
                self,
                Equiv,
            },
            utils::RefId,
            Node,
        },
        alloc::boxed::Box,
        core::marker::PhantomData,
    };

    enum Datum
    {
        Leaf,
        Pair(Box<Self>, Box<Self>),
    }

    fn leaf() -> Datum
    {
        Datum::Leaf
    }

    fn pair(
        a: Datum,
        b: Datum,
    ) -> Datum
    {
        Datum::Pair(Box::new(a), Box::new(b))
    }

    fn end_pair() -> Datum
    {
        pair(leaf(), leaf())
    }

    impl<'l> Node for &'l Datum
    {
        type Cmp = bool;
        type Id = RefId<&'l Datum>;
        type Index = u8;

        fn id(&self) -> Self::Id
        {
            RefId(*self)
        }

        fn get_edge(
            &self,
            idx: &Self::Index,
        ) -> Option<Self>
        {
            match (idx, self) {
                (0, Datum::Pair(a, _)) => Some(a),
                (1, Datum::Pair(_, b)) => Some(b),
                _ => None,
            }
        }

        fn equiv_modulo_edges(
            &self,
            _other: &Self,
        ) -> bool
        {
            true
        }
    }

    #[test]
    fn limiting()
    {
        #[derive(PartialEq, Eq, Debug)]
        enum ResultLimit
        {
            True(u32),
            False(u32),
            Abort(u32),
        }

        fn eqv(
            a: &Datum,
            b: &Datum,
            limit: u32,
        ) -> ResultLimit
        {
            struct LimitedArgs<'l>(PhantomData<&'l ()>);

            impl<'l> equiv::Params for LimitedArgs<'l>
            {
                type DescendMode = Limited<u32>;
                type Error = LimitReached;
                type Node = &'l Datum;
                type RecurMode = CallStack;
            }

            let mut e = Equiv::<LimitedArgs<'_>>::new(Limited(limit));

            match e.equiv(a, b) {
                Ok(true) => True(e.descend_mode.0),
                Ok(false) => False(e.descend_mode.0),
                Err(LimitReached) => Abort(e.descend_mode.0),
            }
        }

        use ResultLimit::*;

        assert_eq!(eqv(&leaf(), &leaf(), 42), True(41));
        assert_eq!(eqv(&leaf(), &leaf(), 1), True(0));
        assert_eq!(eqv(&leaf(), &leaf(), 0), Abort(0));
        assert_eq!(eqv(&leaf(), &end_pair(), 42), False(41));
        assert_eq!(eqv(&end_pair(), &leaf(), 42), False(41));
        assert_eq!(eqv(&end_pair(), &end_pair(), 7), True(4));
        assert_eq!(eqv(&pair(leaf(), end_pair()), &pair(leaf(), end_pair()), 7), True(2));
        assert_eq!(eqv(&end_pair(), &end_pair(), 0), Abort(0));
        assert_eq!(eqv(&end_pair(), &end_pair(), 2), Abort(0));
        assert_eq!(eqv(&pair(leaf(), end_pair()), &pair(leaf(), end_pair()), 1), Abort(0));
        assert_eq!(eqv(&pair(leaf(), leaf()), &pair(leaf(), end_pair()), 42), False(39));
        assert_eq!(
            {
                let x = pair(end_pair(), leaf());
                eqv(&x, &x, 1)
            },
            True(0)
        );
    }
}
