use core::iter::FusedIterator;
use core::marker::PhantomData;
use core::mem::{self, SizedTypeProperties};
use core::ptr::NonNull;
use core::{fmt, ptr};

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

use super::VecDeque;

/// `VecDeque` 的元素上的 draining 迭代器。
///
/// 该 `struct` 是通过 [`VecDeque`] 上的 [`drain`] 方法创建的。
/// 有关更多信息，请参见其文档。
///
/// [`drain`]: VecDeque::drain
#[stable(feature = "drain", since = "1.6.0")]
pub struct Drain<
    'a,
    T: 'a,
    #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global,
> {
    // 我们不能只使用 &mut VecDeque<T, A>，因为那样会使 Drain 在 T 上不变，我们希望它是协变的
    //
    deque: NonNull<VecDeque<T, A>>,
    // drain_start 存放在 deque.len
    drain_len: usize,
    // 索引到逻辑数组，而不是物理数组 (总是位于 [0..deque.len))
    idx: usize,
    // drain 范围之后的元素数
    tail_len: usize,
    remaining: usize,
    // 需要使 Drain 在 T 上协变
    _marker: PhantomData<&'a T>,
}

impl<'a, T, A: Allocator> Drain<'a, T, A> {
    pub(super) unsafe fn new(
        deque: &'a mut VecDeque<T, A>,
        drain_start: usize,
        drain_len: usize,
    ) -> Self {
        let orig_len = mem::replace(&mut deque.len, drain_start);
        let tail_len = orig_len - drain_start - drain_len;
        Drain {
            deque: NonNull::from(deque),
            drain_len,
            idx: drain_start,
            tail_len,
            remaining: drain_len,
            _marker: PhantomData,
        }
    }

    // 只返回指向切片的指针，因为这就是我们丢弃它们所需要的。
    // 只能在 `self.remaining != 0` 时调用。
    unsafe fn as_slices(&self) -> (*mut [T], *mut [T]) {
        unsafe {
            let deque = self.deque.as_ref();

            // 我们知道 `self.idx + self.remaining <= deque.len <= usize::MAX`，所以这不会溢出。
            let logical_remaining_range = self.idx..self.idx + self.remaining;

            // SAFETY: `logical_remaining_range` 表示尚未耗尽的元素进入逻辑缓冲区的范围，因此它们都已初始化，而 `slice::range(start..end, end) == start..end` 则满足 `slice_ranges` 的前提条件。
            //
            //
            //
            //
            let (a_range, b_range) =
                deque.slice_ranges(logical_remaining_range.clone(), logical_remaining_range.end);
            (deque.buffer_range(a_range), deque.buffer_range(b_range))
        }
    }
}

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

#[stable(feature = "drain", since = "1.6.0")]
unsafe impl<T: Sync, A: Allocator + Sync> Sync for Drain<'_, T, A> {}
#[stable(feature = "drain", since = "1.6.0")]
unsafe impl<T: Send, A: Allocator + Send> Send for Drain<'_, T, A> {}

#[stable(feature = "drain", since = "1.6.0")]
impl<T, A: Allocator> Drop for Drain<'_, T, A> {
    fn drop(&mut self) {
        struct DropGuard<'r, 'a, T, A: Allocator>(&'r mut Drain<'a, T, A>);

        impl<'r, 'a, T, A: Allocator> Drop for DropGuard<'r, 'a, T, A> {
            fn drop(&mut self) {
                if self.0.remaining != 0 {
                    unsafe {
                        // SAFETY: 我们刚刚检查了 `self.remaining != 0`。
                        let (front, back) = self.0.as_slices();
                        ptr::drop_in_place(front);
                        ptr::drop_in_place(back);
                    }
                }

                let source_deque = unsafe { self.0.deque.as_mut() };

                let drain_start = source_deque.len();
                let drain_len = self.0.drain_len;
                let drain_end = drain_start + drain_len;

                let orig_len = self.0.tail_len + drain_end;

                if T::IS_ZST {
                    // 如果 T 是 ZST，则无需复制任何内存
                    source_deque.len = orig_len - drain_len;
                    return;
                }

                let head_len = drain_start;
                let tail_len = self.0.tail_len;

                match (head_len, tail_len) {
                    (0, 0) => {
                        source_deque.head = 0;
                        source_deque.len = 0;
                    }
                    (0, _) => {
                        source_deque.head = source_deque.to_physical_idx(drain_len);
                        source_deque.len = orig_len - drain_len;
                    }
                    (_, 0) => {
                        source_deque.len = orig_len - drain_len;
                    }
                    _ => unsafe {
                        if head_len <= tail_len {
                            source_deque.wrap_copy(
                                source_deque.head,
                                source_deque.to_physical_idx(drain_len),
                                head_len,
                            );
                            source_deque.head = source_deque.to_physical_idx(drain_len);
                            source_deque.len = orig_len - drain_len;
                        } else {
                            source_deque.wrap_copy(
                                source_deque.to_physical_idx(head_len + drain_len),
                                source_deque.to_physical_idx(head_len),
                                tail_len,
                            );
                            source_deque.len = orig_len - drain_len;
                        }
                    },
                }
            }
        }

        let guard = DropGuard(self);
        if guard.0.remaining != 0 {
            unsafe {
                // SAFETY: 我们刚刚检查了 `self.remaining != 0`。
                let (front, back) = guard.0.as_slices();
                // 因为 idx 是一个逻辑索引，所以我们不需要担心换行。
                guard.0.idx += front.len();
                guard.0.remaining -= front.len();
                ptr::drop_in_place(front);
                guard.0.remaining = 0;
                ptr::drop_in_place(back);
            }
        }

        // 丢弃 `guard` 处理将剩余元素移动到位。
    }
}

#[stable(feature = "drain", since = "1.6.0")]
impl<T, A: Allocator> Iterator for Drain<'_, T, A> {
    type Item = T;

    #[inline]
    fn next(&mut self) -> Option<T> {
        if self.remaining == 0 {
            return None;
        }
        let wrapped_idx = unsafe { self.deque.as_ref().to_physical_idx(self.idx) };
        self.idx += 1;
        self.remaining -= 1;
        Some(unsafe { self.deque.as_mut().buffer_read(wrapped_idx) })
    }

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

#[stable(feature = "drain", since = "1.6.0")]
impl<T, A: Allocator> DoubleEndedIterator for Drain<'_, T, A> {
    #[inline]
    fn next_back(&mut self) -> Option<T> {
        if self.remaining == 0 {
            return None;
        }
        self.remaining -= 1;
        let wrapped_idx = unsafe { self.deque.as_ref().to_physical_idx(self.idx + self.remaining) };
        Some(unsafe { self.deque.as_mut().buffer_read(wrapped_idx) })
    }
}

#[stable(feature = "drain", since = "1.6.0")]
impl<T, A: Allocator> ExactSizeIterator for Drain<'_, T, A> {}

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