use core::iter::{FusedIterator, TrustedLen};
use core::num::NonZeroUsize;
use core::{array, fmt, mem::MaybeUninit, ops::Try, ptr};

use crate::alloc::{Allocator, Global};

use super::VecDeque;

/// `VecDeque` 元素上的拥有的迭代器。
///
/// 这个 `struct` 是通过 [`VecDeque`] 上的 [`into_iter`] 方法创建的 (由 [`IntoIterator`] trait 提供)。
/// 有关更多信息，请参见其文档。
///
/// [`into_iter`]: VecDeque::into_iter
#[derive(Clone)]
#[stable(feature = "rust1", since = "1.0.0")]
pub struct IntoIter<
    T,
    #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global,
> {
    inner: VecDeque<T, A>,
}

impl<T, A: Allocator> IntoIter<T, A> {
    pub(super) fn new(inner: VecDeque<T, A>) -> Self {
        IntoIter { inner }
    }

    pub(super) fn into_vecdeque(self) -> VecDeque<T, A> {
        self.inner
    }
}

#[stable(feature = "collection_debug", since = "1.17.0")]
impl<T: fmt::Debug, A: Allocator> fmt::Debug for IntoIter<T, A> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_tuple("IntoIter").field(&self.inner).finish()
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<T, A: Allocator> Iterator for IntoIter<T, A> {
    type Item = T;

    #[inline]
    fn next(&mut self) -> Option<T> {
        self.inner.pop_front()
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        let len = self.inner.len();
        (len, Some(len))
    }

    #[inline]
    fn advance_by(&mut self, n: usize) -> Result<(), NonZeroUsize> {
        let len = self.inner.len;
        let rem = if len < n {
            self.inner.clear();
            n - len
        } else {
            self.inner.drain(..n);
            0
        };
        NonZeroUsize::new(rem).map_or(Ok(()), Err)
    }

    #[inline]
    fn count(self) -> usize {
        self.inner.len
    }

    fn try_fold<B, F, R>(&mut self, mut init: B, mut f: F) -> R
    where
        F: FnMut(B, Self::Item) -> R,
        R: Try<Output = B>,
    {
        struct Guard<'a, T, A: Allocator> {
            deque: &'a mut VecDeque<T, A>,
            // `consumed <= deque.len` 始终成立。
            consumed: usize,
        }

        impl<'a, T, A: Allocator> Drop for Guard<'a, T, A> {
            fn drop(&mut self) {
                self.deque.len -= self.consumed;
                self.deque.head = self.deque.to_physical_idx(self.consumed);
            }
        }

        let mut guard = Guard { deque: &mut self.inner, consumed: 0 };

        let (head, tail) = guard.deque.as_slices();

        init = head
            .iter()
            .map(|elem| {
                guard.consumed += 1;
                // SAFETY: 因为我们增加了 `guard.consumed`，双端队列有效地忘记了这个元素，所以我们可以取得所有权
                //
                //
                unsafe { ptr::read(elem) }
            })
            .try_fold(init, &mut f)?;

        tail.iter()
            .map(|elem| {
                guard.consumed += 1;
                // SAFETY: 同上。
                unsafe { ptr::read(elem) }
            })
            .try_fold(init, &mut f)
    }

    #[inline]
    fn fold<B, F>(mut self, init: B, mut f: F) -> B
    where
        F: FnMut(B, Self::Item) -> B,
    {
        match self.try_fold(init, |b, item| Ok::<B, !>(f(b, item))) {
            Ok(b) => b,
            Err(e) => match e {},
        }
    }

    #[inline]
    fn last(mut self) -> Option<Self::Item> {
        self.inner.pop_back()
    }

    fn next_chunk<const N: usize>(
        &mut self,
    ) -> Result<[Self::Item; N], array::IntoIter<Self::Item, N>> {
        let mut raw_arr = MaybeUninit::uninit_array();
        let raw_arr_ptr = raw_arr.as_mut_ptr().cast();
        let (head, tail) = self.inner.as_slices();

        if head.len() >= N {
            // SAFETY: 通过手动调整双端队列的头部和长度，我们有效地让它忘记了第一个 `N` 元素，因此获得它们的所有权是安全的。
            //
            unsafe { ptr::copy_nonoverlapping(head.as_ptr(), raw_arr_ptr, N) };
            self.inner.head = self.inner.to_physical_idx(N);
            self.inner.len -= N;
            // SAFETY: 我们用 `head` 中的项初始化了整个数组
            return Ok(unsafe { raw_arr.transpose().assume_init() });
        }

        // SAFETY: 同上参数。
        unsafe { ptr::copy_nonoverlapping(head.as_ptr(), raw_arr_ptr, head.len()) };
        let remaining = N - head.len();

        if tail.len() >= remaining {
            // SAFETY: 同上参数。
            unsafe {
                ptr::copy_nonoverlapping(tail.as_ptr(), raw_arr_ptr.add(head.len()), remaining)
            };
            self.inner.head = self.inner.to_physical_idx(N);
            self.inner.len -= N;
            // SAFETY: 我们用 `head` 和 `tail` 中的项初始化了整个数组
            Ok(unsafe { raw_arr.transpose().assume_init() })
        } else {
            // SAFETY: 同上参数。
            unsafe {
                ptr::copy_nonoverlapping(tail.as_ptr(), raw_arr_ptr.add(head.len()), tail.len())
            };
            let init = head.len() + tail.len();
            // 我们完全耗尽了所有的双端队列元素。
            self.inner.head = 0;
            self.inner.len = 0;
            // SAFETY: 我们将两个切片中的所有元素复制到数组的开头，因此给定范围已初始化。
            //
            Err(unsafe { array::IntoIter::new_unchecked(raw_arr, 0..init) })
        }
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<T, A: Allocator> DoubleEndedIterator for IntoIter<T, A> {
    #[inline]
    fn next_back(&mut self) -> Option<T> {
        self.inner.pop_back()
    }

    #[inline]
    fn advance_back_by(&mut self, n: usize) -> Result<(), NonZeroUsize> {
        let len = self.inner.len;
        let rem = if len < n {
            self.inner.clear();
            n - len
        } else {
            self.inner.truncate(len - n);
            0
        };
        NonZeroUsize::new(rem).map_or(Ok(()), Err)
    }

    fn try_rfold<B, F, R>(&mut self, mut init: B, mut f: F) -> R
    where
        F: FnMut(B, Self::Item) -> R,
        R: Try<Output = B>,
    {
        struct Guard<'a, T, A: Allocator> {
            deque: &'a mut VecDeque<T, A>,
            // `consumed <= deque.len` 始终成立。
            consumed: usize,
        }

        impl<'a, T, A: Allocator> Drop for Guard<'a, T, A> {
            fn drop(&mut self) {
                self.deque.len -= self.consumed;
            }
        }

        let mut guard = Guard { deque: &mut self.inner, consumed: 0 };

        let (head, tail) = guard.deque.as_slices();

        init = tail
            .iter()
            .map(|elem| {
                guard.consumed += 1;
                // SAFETY: 请参见 try_fold 的安全注释。
                unsafe { ptr::read(elem) }
            })
            .try_rfold(init, &mut f)?;

        head.iter()
            .map(|elem| {
                guard.consumed += 1;
                // SAFETY: 同上。
                unsafe { ptr::read(elem) }
            })
            .try_rfold(init, &mut f)
    }

    #[inline]
    fn rfold<B, F>(mut self, init: B, mut f: F) -> B
    where
        F: FnMut(B, Self::Item) -> B,
    {
        match self.try_rfold(init, |b, item| Ok::<B, !>(f(b, item))) {
            Ok(b) => b,
            Err(e) => match e {},
        }
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<T, A: Allocator> ExactSizeIterator for IntoIter<T, A> {
    #[inline]
    fn is_empty(&self) -> bool {
        self.inner.is_empty()
    }
}

#[stable(feature = "fused", since = "1.26.0")]
impl<T, A: Allocator> FusedIterator for IntoIter<T, A> {}

#[unstable(feature = "trusted_len", issue = "37572")]
unsafe impl<T, A: Allocator> TrustedLen for IntoIter<T, A> {}