graph_safe_compare 0.2.1

#[cfg(feature = "alloc")]
pub(crate) use lazy_collections::{
    LazierIterator,
    LazyVecQueue,
    LazyVecStack,
};
pub(crate) use non_advancing_iterator::NonAdvancingIterator;
pub use ref_id::RefId;


mod ref_id
{
    use core::{
        cmp::Ordering,
        hash::Hash,
        ops::Deref,
        ptr,
    };

    /// Compare and hash references by pointer.
    ///
    /// This should be used as the [`Node::Id`](crate::Node::Id), instead of `*const U`, where
    /// possible, where `T` is some type of reference to the primary inner type `U` of an `N:
    /// Node` (and must not be a reference to an `N` itself).  This is safer for avoiding logic
    /// bugs, because it keeps any lifetimes of `T`.  While `*const U` can be safely used for some
    /// types, it is not guaranteed that some refactoring does not invalidate the (imaginary)
    /// lifetime of such a pointer.  (This crate is `forbid(unsafe_code)` but since such pointers
    /// would only be used as identifiers (and never dereferenced), such lifetime logic bugs could
    /// become hypothetically possible).
    ///
    /// If the `T` type is a "fat" reference, the additional metadata is compared and hashed,
    /// because such values with differing metadata could have different behavior and should be
    /// considered distinct.
    #[derive(Copy, Clone)]
    #[allow(clippy::exhaustive_structs)]
    pub struct RefId<T>(pub T);

    impl<T: Deref> RefId<T>
    {
        #[inline]
        fn as_ptr(&self) -> *const T::Target
        {
            let p: *const T::Target = {
                let r: &T::Target = &*self.0;
                r
            };
            p
        }
    }

    impl<T: Deref> PartialEq for RefId<T>
    {
        #[inline]
        fn eq(
            &self,
            other: &Self,
        ) -> bool
        {
            ptr::eq(self.as_ptr(), other.as_ptr())
        }
    }
    impl<T: Deref> Eq for RefId<T> {}

    impl<T: Deref> Hash for RefId<T>
    {
        #[inline]
        fn hash<H: core::hash::Hasher>(
            &self,
            state: &mut H,
        )
        {
            ptr::hash(self.as_ptr(), state);
        }
    }

    impl<T: Deref> PartialOrd for RefId<T>
    {
        #[inline]
        fn partial_cmp(
            &self,
            other: &Self,
        ) -> Option<Ordering>
        {
            Some(Ord::cmp(self, other))
        }

        #[inline]
        fn lt(
            &self,
            other: &Self,
        ) -> bool
        {
            self.as_ptr() < other.as_ptr()
        }

        #[inline]
        fn le(
            &self,
            other: &Self,
        ) -> bool
        {
            self.as_ptr() <= other.as_ptr()
        }

        #[inline]
        fn gt(
            &self,
            other: &Self,
        ) -> bool
        {
            self.as_ptr() > other.as_ptr()
        }

        #[inline]
        fn ge(
            &self,
            other: &Self,
        ) -> bool
        {
            self.as_ptr() >= other.as_ptr()
        }
    }

    impl<T: Deref> Ord for RefId<T>
    {
        #[inline]
        fn cmp(
            &self,
            other: &Self,
        ) -> Ordering
        {
            Ord::cmp(&self.as_ptr(), &other.as_ptr())
        }
    }
}


#[cfg(feature = "alloc")]
mod lazy_collections
{
    extern crate alloc;
    use {
        super::NonAdvancingIterator,
        alloc::{
            collections::VecDeque,
            vec::Vec,
        },
    };

    /// A logical stack of items yielded by an internal stack of [`Iterator`]s.  Enables lazily
    /// generating items to reduce memory usage.
    pub(crate) struct LazyVecStack<I>(Vec<I>);

    /// A logical queue of items yielded by an internal queue of [`Iterator`]s.  Enables lazily
    /// generating items to reduce memory usage.
    pub(crate) struct LazyVecQueue<I>(VecDeque<I>);

    /// Somewhat similar to [`Flatten`](core::iter::Flatten) but designed to not consume ownership
    /// and not hold a "current" sub-iterator so that mutating to `extend` with further items may
    /// be done between `next` calls.
    pub(crate) trait LazierIterator
    {
        type SubIter: NonAdvancingIterator;

        fn extend(
            &mut self,
            subiter: Self::SubIter,
        );

        fn next_subiter_as_mut(&mut self) -> Option<&mut Self::SubIter>;

        fn next_subiter(&mut self) -> Option<Self::SubIter>;

        #[allow(clippy::inline_always)]
        #[inline(always)] // Actually makes a big difference.
        fn next(&mut self) -> Option<<Self::SubIter as Iterator>::Item>
        {
            while let Some(subiter) = self.next_subiter_as_mut() {
                let next = subiter.next();
                if !subiter.has_next() {
                    drop(self.next_subiter()); // Remove empty iterators, before returning `Some`.
                }
                if next.is_some() {
                    return next;
                }
            }
            None
        }
    }

    macro_rules! provided_impls {
        {
            $($t:ty {
                $with_capacity:path,
                $extend:ident,
                $next_subiter_as_mut:ident,
                $next_subiter:ident
            },)*
        } => {
            $(
                impl<I> $t
                {
                    pub(crate) fn with_capacity(capacity: usize) -> Self
                    {
                        Self($with_capacity(capacity))
                    }

                    pub(crate) fn clear(&mut self)
                    {
                        self.0.clear()
                    }
                }

                impl<I: NonAdvancingIterator> LazierIterator for $t
                {
                    type SubIter = I;

                    fn extend(
                        &mut self,
                        subiter: Self::SubIter,
                    )
                    {
                        self.0.$extend(subiter);
                    }

                    fn next_subiter_as_mut(&mut self) -> Option<&mut Self::SubIter>
                    {
                        self.0.$next_subiter_as_mut()
                    }

                    fn next_subiter(&mut self) -> Option<Self::SubIter>
                    {
                        self.0.$next_subiter()
                    }
                }
            )*
        };
    }

    provided_impls! {
        LazyVecStack<I> { Vec::with_capacity, push, last_mut, pop },
        LazyVecQueue<I> { VecDeque::with_capacity, push_back, front_mut, pop_front },
    }
}


mod non_advancing_iterator
{
    /// An `Iterator` that can repeatedly yield the same next item without advancing.
    ///
    /// Unlike [`Peekable`](core::iter::Peekable), this is not required to store and repeatedly
    /// yield the same value.  The logically-same next item may be dynamically regenerated as
    /// distinct equivalent values.
    pub(crate) trait NonAdvancingIterator: Iterator
    {
        /// Returns the next item without advancing the iterator.
        ///
        /// Multiple calls return the logically-same item, when the iterator is not advanced by
        /// some other means.  In such case, this may or may not be the same value.
        fn next_no_adv(&mut self) -> Option<Self::Item>;

        /// Returns `true` if the iterator has a next item, without advancing the iterator.
        fn has_next(&mut self) -> bool
        {
            self.next_no_adv().is_some()
        }
    }
}