//! 使用可增长的环形缓冲区实现的双端队列。
//!
//! 此队列具有 *O*(1) 容器两端的摊销插入和删除。
//! 它还具有像 vector 一样的 *O*(1) 索引。
//! 所包含的元素不需要是可复制的，并且如果所包含的类型是可发送的，则队列将是可发送的。
//!

#![stable(feature = "rust1", since = "1.0.0")]

use core::cmp::{self, Ordering};
use core::fmt;
use core::hash::{Hash, Hasher};
use core::iter::{repeat_with, FromIterator};
use core::marker::PhantomData;
use core::mem::{self, ManuallyDrop};
use core::ops::{Index, IndexMut, Range, RangeBounds};
use core::ptr::{self, NonNull};
use core::slice;

use crate::collections::TryReserveError;
use crate::raw_vec::RawVec;
use crate::vec::Vec;

#[macro_use]
mod macros;

#[stable(feature = "drain", since = "1.6.0")]
pub use self::drain::Drain;

mod drain;

#[stable(feature = "rust1", since = "1.0.0")]
pub use self::iter_mut::IterMut;

mod iter_mut;

#[stable(feature = "rust1", since = "1.0.0")]
pub use self::into_iter::IntoIter;

mod into_iter;

#[stable(feature = "rust1", since = "1.0.0")]
pub use self::iter::Iter;

mod iter;

use self::pair_slices::PairSlices;

mod pair_slices;

use self::ring_slices::RingSlices;

mod ring_slices;

#[cfg(test)]
mod tests;

const INITIAL_CAPACITY: usize = 7; // 2^3 - 1
const MINIMUM_CAPACITY: usize = 1; // 2 - 1

const MAXIMUM_ZST_CAPACITY: usize = 1 << (usize::BITS - 1); // 可能的最大两倍

/// 使用可增长的环形缓冲区实现的双端队列。
///
/// "default" 作为队列的这种用法是使用 [`push_back`] 添加到队列，使用 [`pop_front`] 从队列中删除。
///
/// [`extend`] [`append`] 以这种方式推向后部，并且在 `VecDeque` 上进行迭代从前到后。
///
/// 由于 `VecDeque` 是环形缓冲区，因此它的元素在内存中不一定是连续的。
/// 如果要以单个切片的形式访问元素 (例如为了进行有效的排序)，则可以使用 [`make_contiguous`]。
/// 它旋转 `VecDeque`，以使其元素不环绕，并向当前连续的元素序列返回可变切片。
///
/// [`push_back`]: VecDeque::push_back
/// [`pop_front`]: VecDeque::pop_front
/// [`extend`]: VecDeque::extend
/// [`append`]: VecDeque::append
/// [`make_contiguous`]: VecDeque::make_contiguous
///
///
///
#[cfg_attr(not(test), rustc_diagnostic_item = "vecdeque_type")]
#[stable(feature = "rust1", since = "1.0.0")]
pub struct VecDeque<T> {
    // tail 和 head 是指向缓冲区的指针。
    // Tail 总是指向可以读取的第一个元素，Head 总是指向应该写入数据的位置。
    //
    // 如果 tail == head，则缓冲区为空。环形缓冲区的长度定义为两者之间的距离。
    //
    tail: usize,
    head: usize,
    buf: RawVec<T>,
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<T: Clone> Clone for VecDeque<T> {
    fn clone(&self) -> VecDeque<T> {
        self.iter().cloned().collect()
    }

    fn clone_from(&mut self, other: &Self) {
        self.truncate(other.len());

        let mut iter = PairSlices::from(self, other);
        while let Some((dst, src)) = iter.next() {
            dst.clone_from_slice(&src);
        }

        if iter.has_remainder() {
            for remainder in iter.remainder() {
                self.extend(remainder.iter().cloned());
            }
        }
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
unsafe impl<#[may_dangle] T> Drop for VecDeque<T> {
    fn drop(&mut self) {
        /// 当切片被丢弃时 (正常情况下或在展开期间)，对切片中的所有项运行析构函数。
        ///
        struct Dropper<'a, T>(&'a mut [T]);

        impl<'a, T> Drop for Dropper<'a, T> {
            fn drop(&mut self) {
                unsafe {
                    ptr::drop_in_place(self.0);
                }
            }
        }

        let (front, back) = self.as_mut_slices();
        unsafe {
            let _back_dropper = Dropper(back);
            // use drop for [T]
            ptr::drop_in_place(front);
        }
        // RawVec 处理重新分配
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<T> Default for VecDeque<T> {
    /// 创建一个空的 `VecDeque<T>`。
    #[inline]
    fn default() -> VecDeque<T> {
        VecDeque::new()
    }
}

impl<T> VecDeque<T> {
    /// 稍微方便一点
    #[inline]
    fn ptr(&self) -> *mut T {
        self.buf.ptr()
    }

    /// 稍微方便一点
    #[inline]
    fn cap(&self) -> usize {
        if mem::size_of::<T>() == 0 {
            // 对于零大小类型，我们始终处于最大容量
            MAXIMUM_ZST_CAPACITY
        } else {
            self.buf.capacity()
        }
    }

    /// 将 ptr 变成切片
    #[inline]
    unsafe fn buffer_as_slice(&self) -> &[T] {
        unsafe { slice::from_raw_parts(self.ptr(), self.cap()) }
    }

    /// 将 ptr 变成 mut 切片
    #[inline]
    unsafe fn buffer_as_mut_slice(&mut self) -> &mut [T] {
        unsafe { slice::from_raw_parts_mut(self.ptr(), self.cap()) }
    }

    /// 将元素移出缓冲区
    #[inline]
    unsafe fn buffer_read(&mut self, off: usize) -> T {
        unsafe { ptr::read(self.ptr().add(off)) }
    }

    /// 将元素写入缓冲区，然后将其移动。
    #[inline]
    unsafe fn buffer_write(&mut self, off: usize, value: T) {
        unsafe {
            ptr::write(self.ptr().add(off), value);
        }
    }

    /// 如果缓冲区已满，则返回 `true`。
    #[inline]
    fn is_full(&self) -> bool {
        self.cap() - self.len() == 1
    }

    /// 返回给定逻辑元素索引的基础缓冲区中的索引。
    ///
    #[inline]
    fn wrap_index(&self, idx: usize) -> usize {
        wrap_index(idx, self.cap())
    }

    /// 返回给定逻辑元素索引 + 加数的基础缓冲区中的索引。
    ///
    #[inline]
    fn wrap_add(&self, idx: usize, addend: usize) -> usize {
        wrap_index(idx.wrapping_add(addend), self.cap())
    }

    /// 返回给定逻辑元素索引 - subtrahend 的基础缓冲区中的索引。
    ///
    #[inline]
    fn wrap_sub(&self, idx: usize, subtrahend: usize) -> usize {
        wrap_index(idx.wrapping_sub(subtrahend), self.cap())
    }

    /// 将一个连续的 len 长的内存块从 src 复制到 dst
    #[inline]
    unsafe fn copy(&self, dst: usize, src: usize, len: usize) {
        debug_assert!(
            dst + len <= self.cap(),
            "cpy dst={} src={} len={} cap={}",
            dst,
            src,
            len,
            self.cap()
        );
        debug_assert!(
            src + len <= self.cap(),
            "cpy dst={} src={} len={} cap={}",
            dst,
            src,
            len,
            self.cap()
        );
        unsafe {
            ptr::copy(self.ptr().add(src), self.ptr().add(dst), len);
        }
    }

    /// 将一个连续的 len 长的内存块从 src 复制到 dst
    #[inline]
    unsafe fn copy_nonoverlapping(&self, dst: usize, src: usize, len: usize) {
        debug_assert!(
            dst + len <= self.cap(),
            "cno dst={} src={} len={} cap={}",
            dst,
            src,
            len,
            self.cap()
        );
        debug_assert!(
            src + len <= self.cap(),
            "cno dst={} src={} len={} cap={}",
            dst,
            src,
            len,
            self.cap()
        );
        unsafe {
            ptr::copy_nonoverlapping(self.ptr().add(src), self.ptr().add(dst), len);
        }
    }

    /// 从 src 复制一个长度为 len 的潜在包装内存块到 dest。
    /// (abs(dst - src) + len) 不得大于 cap() (src 与 dest 之间最多应有一个连续的重叠区域)。
    ///
    unsafe fn wrap_copy(&self, dst: usize, src: usize, len: usize) {
        #[allow(dead_code)]
        fn diff(a: usize, b: usize) -> usize {
            if a <= b { b - a } else { a - b }
        }
        debug_assert!(
            cmp::min(diff(dst, src), self.cap() - diff(dst, src)) + len <= self.cap(),
            "wrc dst={} src={} len={} cap={}",
            dst,
            src,
            len,
            self.cap()
        );

        if src == dst || len == 0 {
            return;
        }

        let dst_after_src = self.wrap_sub(dst, src) < len;

        let src_pre_wrap_len = self.cap() - src;
        let dst_pre_wrap_len = self.cap() - dst;
        let src_wraps = src_pre_wrap_len < len;
        let dst_wraps = dst_pre_wrap_len < len;

        match (dst_after_src, src_wraps, dst_wraps) {
            (_, false, false) => {
                // src 不换行，dst 不换行
                //
                //
                //        S . . .
                // 1 [_ _ A A B B C C _]
                // 2 [_ _ A A A A B B _] D . . .
                //
                unsafe {
                    self.copy(dst, src, len);
                }
            }
            (false, false, true) => {
                // src 之前的 dst，src 不环绕，dst 环绕
                //
                //
                //    S . . .
                // 1 [A A B B _ _ _ C C]
                // 2 [A A B B _ _ _ A A]
                // 3 [B B B B _ _ _ A A] .. D .
                //
                unsafe {
                    self.copy(dst, src, dst_pre_wrap_len);
                    self.copy(0, src + dst_pre_wrap_len, len - dst_pre_wrap_len);
                }
            }
            (true, false, true) => {
                // dst 之前的 src，src 不换行，dst 换行
                //
                //
                //              S . . .
                // 1 [C C _ _ _ A A B B]
                // 2 [B B _ _ _ A A B B]
                // 3 [B B _ _ _ A A A A] .. D .
                //
                unsafe {
                    self.copy(0, src + dst_pre_wrap_len, len - dst_pre_wrap_len);
                    self.copy(dst, src, dst_pre_wrap_len);
                }
            }
            (false, true, false) => {
                // src 之前的 dst，src 换行，dst 不换行
                //
                //
                //    .. S .
                // 1 [C C _ _ _ A A B B]
                // 2 [C C _ _ _ B B B B]
                // 3 [C C _ _ _ B B C C] D . . .
                //
                unsafe {
                    self.copy(dst, src, src_pre_wrap_len);
                    self.copy(dst + src_pre_wrap_len, 0, len - src_pre_wrap_len);
                }
            }
            (true, true, false) => {
                // dst 之前的 src，src 换行，dst 不换行
                //
                //
                //    .. S .
                // 1 [A A B B _ _ _ C C]
                // 2 [A A A A _ _ _ C C]
                // 3 [C C A A _ _ _ C C] D . . .
                //
                unsafe {
                    self.copy(dst + src_pre_wrap_len, 0, len - src_pre_wrap_len);
                    self.copy(dst, src, src_pre_wrap_len);
                }
            }
            (false, true, true) => {
                // src 之前的 dst，src 换行，dst 换行
                //
                //
                //    . .. S .
                // 1 [A B C D _ E F G H]
                // 2 [A B C D _ E G H H]
                // 3 [A B C D _ E G H A]
                // 4 [B C C D _ E G H A] .. D . .
                //
                debug_assert!(dst_pre_wrap_len > src_pre_wrap_len);
                let delta = dst_pre_wrap_len - src_pre_wrap_len;
                unsafe {
                    self.copy(dst, src, src_pre_wrap_len);
                    self.copy(dst + src_pre_wrap_len, 0, delta);
                    self.copy(0, delta, len - dst_pre_wrap_len);
                }
            }
            (true, true, true) => {
                // dst 之前的 src，src 换行，dst 换行
                //
                //
                //    .. S . .
                // 1 [A B C D _ E F G H]
                // 2 [A A B D _ E F G H]
                // 3 [H A B D _ E F G H]
                // 4 [H A B D _ E F F G] . .. D .
                //
                debug_assert!(src_pre_wrap_len > dst_pre_wrap_len);
                let delta = src_pre_wrap_len - dst_pre_wrap_len;
                unsafe {
                    self.copy(delta, 0, len - src_pre_wrap_len);
                    self.copy(0, self.cap() - delta, delta);
                    self.copy(dst, src, dst_pre_wrap_len);
                }
            }
        }
    }

    /// 绕着 head 和 tail 进行处理，以处理我们刚刚重新分配的事实。
    /// 不安全，因为它信任 old_capacity。
    #[inline]
    unsafe fn handle_capacity_increase(&mut self, old_capacity: usize) {
        let new_capacity = self.cap();

        // 移动环形缓冲区 TH 的最短连续部分
        //
        //   [o o o o o o o . ]
        //    T             H A [o o o o o o o . . . . . . . . . ] H T
        //   [o o . o o o o o ]
        //          T             H B [. . . o o o o o o o . . . . . . ] H T
        //   [o o o o o . o o ]
        //              H                 T C [o o o o o . . . . . . . . . o o ]
        //
        //
        //
        //
        //

        if self.tail <= self.head {
            // A Nop
            //
        } else if self.head < old_capacity - self.tail {
            // B
            unsafe {
                self.copy_nonoverlapping(old_capacity, 0, self.head);
            }
            self.head += old_capacity;
            debug_assert!(self.head > self.tail);
        } else {
            // C
            let new_tail = new_capacity - (old_capacity - self.tail);
            unsafe {
                self.copy_nonoverlapping(new_tail, self.tail, old_capacity - self.tail);
            }
            self.tail = new_tail;
            debug_assert!(self.head < self.tail);
        }
        debug_assert!(self.head < self.cap());
        debug_assert!(self.tail < self.cap());
        debug_assert!(self.cap().count_ones() == 1);
    }
}

impl<T> VecDeque<T> {
    /// 创建一个空的 `VecDeque`。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let vector: VecDeque<u32> = VecDeque::new();
    /// ```
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn new() -> VecDeque<T> {
        VecDeque::with_capacity(INITIAL_CAPACITY)
    }

    /// 创建一个空的 `VecDeque`，其中至少有 `capacity` 元素的空间。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let vector: VecDeque<u32> = VecDeque::with_capacity(10);
    /// ```
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn with_capacity(capacity: usize) -> VecDeque<T> {
        // +1，因为环形缓冲区始终将一个空间留空
        let cap = cmp::max(capacity + 1, MINIMUM_CAPACITY + 1).next_power_of_two();
        assert!(cap > capacity, "capacity overflow");

        VecDeque { tail: 0, head: 0, buf: RawVec::with_capacity(cap) }
    }

    /// 提供给定索引处元素的引用。
    ///
    /// 索引为 0 的元素在队列的最前面。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let mut buf = VecDeque::new();
    /// buf.push_back(3);
    /// buf.push_back(4);
    /// buf.push_back(5);
    /// assert_eq!(buf.get(1), Some(&4));
    /// ```
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn get(&self, index: usize) -> Option<&T> {
        if index < self.len() {
            let idx = self.wrap_add(self.tail, index);
            unsafe { Some(&*self.ptr().add(idx)) }
        } else {
            None
        }
    }

    /// 提供给定索引处元素的可变引用。
    ///
    /// 索引为 0 的元素在队列的最前面。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let mut buf = VecDeque::new();
    /// buf.push_back(3);
    /// buf.push_back(4);
    /// buf.push_back(5);
    /// if let Some(elem) = buf.get_mut(1) {
    ///     *elem = 7;
    /// }
    ///
    /// assert_eq!(buf[1], 7);
    /// ```
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
        if index < self.len() {
            let idx = self.wrap_add(self.tail, index);
            unsafe { Some(&mut *self.ptr().add(idx)) }
        } else {
            None
        }
    }

    /// 交换索引为 `i` 和 `j` 的元素。
    ///
    /// `i` `j` 可能相等。
    ///
    /// 索引为 0 的元素在队列的最前面。
    ///
    /// # Panics
    ///
    /// Panics (如果任一索引越界)。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let mut buf = VecDeque::new();
    /// buf.push_back(3);
    /// buf.push_back(4);
    /// buf.push_back(5);
    /// assert_eq!(buf, [3, 4, 5]);
    /// buf.swap(0, 2);
    /// assert_eq!(buf, [5, 4, 3]);
    /// ```
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn swap(&mut self, i: usize, j: usize) {
        assert!(i < self.len());
        assert!(j < self.len());
        let ri = self.wrap_add(self.tail, i);
        let rj = self.wrap_add(self.tail, j);
        unsafe { ptr::swap(self.ptr().add(ri), self.ptr().add(rj)) }
    }

    /// 返回 `VecDeque` 无需重新分配即可容纳的元素数。
    ///
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let buf: VecDeque<i32> = VecDeque::with_capacity(10);
    /// assert!(buf.capacity() >= 10);
    /// ```
    #[inline]
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn capacity(&self) -> usize {
        self.cap() - 1
    }

    /// 保留最小容量，以便在给定的 `VecDeque` 中精确插入 `additional` 个元素。
    /// 如果容量已经足够，则不执行任何操作。
    ///
    /// 请注意，分配器可能会给集合提供比其请求更多的空间。
    /// 因此，不能依靠容量来精确地将其最小化。
    /// 如果预计将来会插入，则最好使用 [`reserve`]。
    ///
    /// # Panics
    ///
    /// 如果新容量溢出 `usize`，则为 Panics。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let mut buf: VecDeque<i32> = vec![1].into_iter().collect();
    /// buf.reserve_exact(10);
    /// assert!(buf.capacity() >= 11);
    /// ```
    ///
    /// [`reserve`]: VecDeque::reserve
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn reserve_exact(&mut self, additional: usize) {
        self.reserve(additional);
    }

    /// 为给定的 `VecDeque` 至少保留 `additional` 个要插入的元素保留容量。
    /// 该集合可以保留更多空间，以避免频繁的重新分配。
    ///
    /// # Panics
    ///
    /// 如果新容量溢出 `usize`，则为 Panics。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let mut buf: VecDeque<i32> = vec![1].into_iter().collect();
    /// buf.reserve(10);
    /// assert!(buf.capacity() >= 11);
    /// ```
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn reserve(&mut self, additional: usize) {
        let old_cap = self.cap();
        let used_cap = self.len() + 1;
        let new_cap = used_cap
            .checked_add(additional)
            .and_then(|needed_cap| needed_cap.checked_next_power_of_two())
            .expect("capacity overflow");

        if new_cap > old_cap {
            self.buf.reserve_exact(used_cap, new_cap - used_cap);
            unsafe {
                self.handle_capacity_increase(old_cap);
            }
        }
    }

    /// 尝试保留最小容量，以便在给定的 `VecDeque<T>` 中精确插入 `additional` 个元素。
    ///
    /// 调用 `try_reserve_exact` 后，容量将大于或等于 `self.len() + additional`。
    /// 如果容量已经足够，则不执行任何操作。
    ///
    /// 请注意，分配器可能会给集合提供比其请求更多的空间。
    /// 因此，不能依靠容量来精确地最小化。
    ///  如果希望将来插入，则最好使用 `reserve`。
    ///
    /// # Errors
    ///
    /// 如果容量溢出 `usize`，或者分配器报告失败，则返回错误。
    ///
    /// # Examples
    ///
    /// ```
    /// #![feature(try_reserve)]
    /// use std::collections::TryReserveError;
    /// use std::collections::VecDeque;
    ///
    /// fn process_data(data: &[u32]) -> Result<VecDeque<u32>, TryReserveError> {
    ///     let mut output = VecDeque::new();
    ///
    ///     // 预先保留内存，如果不能，则退出
    ///     output.try_reserve_exact(data.len())?;
    ///
    ///     // 现在我们知道这不能 OOM(Out-Of-Memory) 完成我们复杂的工作
    ///     output.extend(data.iter().map(|&val| {
    ///         val * 2 + 5 // 非常复杂
    ///     }));
    ///
    ///     Ok(output)
    /// }
    /// # process_data(&[1, 2, 3]).expect("why is the test harness OOMing on 12 bytes?");
    /// ```
    ///
    #[unstable(feature = "try_reserve", reason = "new API", issue = "48043")]
    pub fn try_reserve_exact(&mut self, additional: usize) -> Result<(), TryReserveError> {
        self.try_reserve(additional)
    }

    /// 尝试为给 `VecDeque<T>` 至少插入 `additional` 个元素保留容量。
    /// 该集合可以保留更多空间，以避免频繁的重新分配。
    /// 调用 `try_reserve` 后，容量将大于或等于 `self.len() + additional`。
    /// 如果容量已经足够，则不执行任何操作。
    ///
    /// # Errors
    ///
    /// 如果容量溢出 `usize`，或者分配器报告失败，则返回错误。
    ///
    /// # Examples
    ///
    /// ```
    /// #![feature(try_reserve)]
    /// use std::collections::TryReserveError;
    /// use std::collections::VecDeque;
    ///
    /// fn process_data(data: &[u32]) -> Result<VecDeque<u32>, TryReserveError> {
    ///     let mut output = VecDeque::new();
    ///
    ///     // 预先保留内存，如果不能，则退出
    ///     output.try_reserve(data.len())?;
    ///
    ///     // 现在我们知道在我们复杂的工作中这不能 OOM
    ///     output.extend(data.iter().map(|&val| {
    ///         val * 2 + 5 // 非常复杂
    ///     }));
    ///
    ///     Ok(output)
    /// }
    /// # process_data(&[1, 2, 3]).expect("why is the test harness OOMing on 12 bytes?");
    /// ```
    ///
    ///
    #[unstable(feature = "try_reserve", reason = "new API", issue = "48043")]
    pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
        let old_cap = self.cap();
        let used_cap = self.len() + 1;
        let new_cap = used_cap
            .checked_add(additional)
            .and_then(|needed_cap| needed_cap.checked_next_power_of_two())
            .ok_or(TryReserveError::CapacityOverflow)?;

        if new_cap > old_cap {
            self.buf.try_reserve_exact(used_cap, new_cap - used_cap)?;
            unsafe {
                self.handle_capacity_increase(old_cap);
            }
        }
        Ok(())
    }

    /// 尽可能缩小 `VecDeque` 的容量。
    ///
    /// 它将 drop 到尽可能接近长度的位置，但分配器仍可能通知 `VecDeque` 还有空间容纳更多的元素。
    ///
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let mut buf = VecDeque::with_capacity(15);
    /// buf.extend(0..4);
    /// assert_eq!(buf.capacity(), 15);
    /// buf.shrink_to_fit();
    /// assert!(buf.capacity() >= 4);
    /// ```
    #[stable(feature = "deque_extras_15", since = "1.5.0")]
    pub fn shrink_to_fit(&mut self) {
        self.shrink_to(0);
    }

    /// 降低 `VecDeque` 的容量。
    ///
    /// 容量将至少保持与长度和提供的值一样大。
    ///
    ///
    /// 如果当前容量小于下限，则为无操作。
    ///
    /// # Examples
    ///
    /// ```
    /// #![feature(shrink_to)]
    /// use std::collections::VecDeque;
    ///
    /// let mut buf = VecDeque::with_capacity(15);
    /// buf.extend(0..4);
    /// assert_eq!(buf.capacity(), 15);
    /// buf.shrink_to(6);
    /// assert!(buf.capacity() >= 6);
    /// buf.shrink_to(0);
    /// assert!(buf.capacity() >= 4);
    /// ```
    #[unstable(feature = "shrink_to", reason = "new API", issue = "56431")]
    pub fn shrink_to(&mut self, min_capacity: usize) {
        let min_capacity = cmp::min(min_capacity, self.capacity());
        // 我们不必担心溢出，因为 `self.len()` 和 `self.capacity()` 都不可能是 `usize::MAX`。
        // +1，因为环形缓冲区始终将一个空间留空。
        let target_cap = cmp::max(cmp::max(min_capacity, self.len()) + 1, MINIMUM_CAPACITY + 1)
            .next_power_of_two();

        if target_cap < self.cap() {
            // 有以下三种有趣的情况:
            //   所有元素都超出期望的范围元素是连续的，并且头超出了期望的范围元素是不连续的，并且尾部超出了期望的范围
            //
            //
            // 在其他所有时间，元素位置均不受影响。
            //
            // 指示应该移动顶部的元素。
            //
            let head_outside = self.head == 0 || self.head >= target_cap;
            // 将元素移出所需范围 (位于 target_cap 之后的位置)
            if self.tail >= target_cap && head_outside {
                // T             H
                //   [. . . . . . . . o o o o o o o . ]
                //    T             H
                //   [o o o o o o o . ]
                unsafe {
                    self.copy_nonoverlapping(0, self.tail, self.len());
                }
                self.head = self.len();
                self.tail = 0;
            } else if self.tail != 0 && self.tail < target_cap && head_outside {
                // T             H
                //   [. . . o o o o o o o . . . . . . ]
                //        H T
                //   [o o . o o o o o ]
                let len = self.wrap_sub(self.head, target_cap);
                unsafe {
                    self.copy_nonoverlapping(0, target_cap, len);
                }
                self.head = len;
                debug_assert!(self.head < self.tail);
            } else if self.tail >= target_cap {
                // H                 T
                //   [o o o o o . . . . . . . . . o o ]
                //              H T
                //   [o o o o o . o o ]
                debug_assert!(self.wrap_sub(self.head, 1) < target_cap);
                let len = self.cap() - self.tail;
                let new_tail = target_cap - len;
                unsafe {
                    self.copy_nonoverlapping(new_tail, self.tail, len);
                }
                self.tail = new_tail;
                debug_assert!(self.head < self.tail);
            }

            self.buf.shrink_to_fit(target_cap);

            debug_assert!(self.head < self.cap());
            debug_assert!(self.tail < self.cap());
            debug_assert!(self.cap().count_ones() == 1);
        }
    }

    /// 缩短 `VecDeque`，保留第一个 `len` 元素，然后丢弃其余的元素。
    ///
    ///
    /// 如果 `len` 大于 `VecDeque' 的当前长度，则无效。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let mut buf = VecDeque::new();
    /// buf.push_back(5);
    /// buf.push_back(10);
    /// buf.push_back(15);
    /// assert_eq!(buf, [5, 10, 15]);
    /// buf.truncate(1);
    /// assert_eq!(buf, [5]);
    /// ```
    ///
    #[stable(feature = "deque_extras", since = "1.16.0")]
    pub fn truncate(&mut self, len: usize) {
        /// 当切片被丢弃时 (正常情况下或在展开期间)，对切片中的所有项运行析构函数。
        ///
        struct Dropper<'a, T>(&'a mut [T]);

        impl<'a, T> Drop for Dropper<'a, T> {
            fn drop(&mut self) {
                unsafe {
                    ptr::drop_in_place(self.0);
                }
            }
        }

        // 安全是因为:
        //
        // * 传递给 `drop_in_place` 的任何切片都是有效的; 第二种情况为 `len <= front.len()`，返回 `len > self.len()` 可确保第一种情况为 `begin <= back.len()`
        //
        // * VecDeque 的头部在调用 `drop_in_place` 之前已移动，因此如果 `drop_in_place` panics 没有两次删除任何值
        //
        //
        unsafe {
            if len > self.len() {
                return;
            }
            let num_dropped = self.len() - len;
            let (front, back) = self.as_mut_slices();
            if len > front.len() {
                let begin = len - front.len();
                let drop_back = back.get_unchecked_mut(begin..) as *mut _;
                self.head = self.wrap_sub(self.head, num_dropped);
                ptr::drop_in_place(drop_back);
            } else {
                let drop_back = back as *mut _;
                let drop_front = front.get_unchecked_mut(len..) as *mut _;
                self.head = self.wrap_sub(self.head, num_dropped);

                // 即使第一个中的析构函数发生 panic，也要确保后半部分被丢弃。
                //
                let _back_dropper = Dropper(&mut *drop_back);
                ptr::drop_in_place(drop_front);
            }
        }
    }

    /// 返回从前到后的迭代器。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let mut buf = VecDeque::new();
    /// buf.push_back(5);
    /// buf.push_back(3);
    /// buf.push_back(4);
    /// let b: &[_] = &[&5, &3, &4];
    /// let c: Vec<&i32> = buf.iter().collect();
    /// assert_eq!(&c[..], b);
    /// ```
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn iter(&self) -> Iter<'_, T> {
        Iter { tail: self.tail, head: self.head, ring: unsafe { self.buffer_as_slice() } }
    }

    /// 返回从前到后的迭代器，该迭代器返回可变引用。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let mut buf = VecDeque::new();
    /// buf.push_back(5);
    /// buf.push_back(3);
    /// buf.push_back(4);
    /// for num in buf.iter_mut() {
    ///     *num = *num - 2;
    /// }
    /// let b: &[_] = &[&mut 3, &mut 1, &mut 2];
    /// assert_eq!(&buf.iter_mut().collect::<Vec<&mut i32>>()[..], b);
    /// ```
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn iter_mut(&mut self) -> IterMut<'_, T> {
        // SAFETY: 之所以建立内部 `IterMut` 安全不变式，是因为我们创建的 `ring` 是生命周期 '_的可引用切片。
        //
        IterMut {
            tail: self.tail,
            head: self.head,
            ring: ptr::slice_from_raw_parts_mut(self.ptr(), self.cap()),
            phantom: PhantomData,
        }
    }

    /// 返回一对切片，这些切片按顺序包含 `VecDeque` 的内容。
    ///
    /// 如果先前调用了 [`make_contiguous`]，则 `VecDeque` 的所有元素都将位于第一个切片中，而第二个切片将为空。
    ///
    ///
    /// [`make_contiguous`]: VecDeque::make_contiguous
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let mut vector = VecDeque::new();
    ///
    /// vector.push_back(0);
    /// vector.push_back(1);
    /// vector.push_back(2);
    ///
    /// assert_eq!(vector.as_slices(), (&[0, 1, 2][..], &[][..]));
    ///
    /// vector.push_front(10);
    /// vector.push_front(9);
    ///
    /// assert_eq!(vector.as_slices(), (&[9, 10][..], &[0, 1, 2][..]));
    /// ```
    ///
    #[inline]
    #[stable(feature = "deque_extras_15", since = "1.5.0")]
    pub fn as_slices(&self) -> (&[T], &[T]) {
        unsafe {
            let buf = self.buffer_as_slice();
            RingSlices::ring_slices(buf, self.head, self.tail)
        }
    }

    /// 返回一对切片，这些切片按顺序包含 `VecDeque` 的内容。
    ///
    /// 如果先前调用了 [`make_contiguous`]，则 `VecDeque` 的所有元素都将位于第一个切片中，而第二个切片将为空。
    ///
    ///
    /// [`make_contiguous`]: VecDeque::make_contiguous
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let mut vector = VecDeque::new();
    ///
    /// vector.push_back(0);
    /// vector.push_back(1);
    ///
    /// vector.push_front(10);
    /// vector.push_front(9);
    ///
    /// vector.as_mut_slices().0[0] = 42;
    /// vector.as_mut_slices().1[0] = 24;
    /// assert_eq!(vector.as_slices(), (&[42, 10][..], &[24, 1][..]));
    /// ```
    ///
    #[inline]
    #[stable(feature = "deque_extras_15", since = "1.5.0")]
    pub fn as_mut_slices(&mut self) -> (&mut [T], &mut [T]) {
        unsafe {
            let head = self.head;
            let tail = self.tail;
            let buf = self.buffer_as_mut_slice();
            RingSlices::ring_slices(buf, head, tail)
        }
    }

    /// 返回 `VecDeque` 中的元素数。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let mut v = VecDeque::new();
    /// assert_eq!(v.len(), 0);
    /// v.push_back(1);
    /// assert_eq!(v.len(), 1);
    /// ```
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn len(&self) -> usize {
        count(self.tail, self.head, self.cap())
    }

    /// 如果 `VecDeque` 为空，则返回 `true`。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let mut v = VecDeque::new();
    /// assert!(v.is_empty());
    /// v.push_front(1);
    /// assert!(!v.is_empty());
    /// ```
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn is_empty(&self) -> bool {
        self.tail == self.head
    }

    fn range_tail_head<R>(&self, range: R) -> (usize, usize)
    where
        R: RangeBounds<usize>,
    {
        let Range { start, end } = slice::range(range, ..self.len());
        let tail = self.wrap_add(self.tail, start);
        let head = self.wrap_add(self.tail, end);
        (tail, head)
    }

    /// 创建一个覆盖 `VecDeque` 中指定范围的迭代器。
    ///
    /// # Panics
    ///
    /// 如果起点大于终点或终点大于 vector 的长度，则为 Panics。
    ///
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let v: VecDeque<_> = vec![1, 2, 3].into_iter().collect();
    /// let range = v.range(2..).copied().collect::<VecDeque<_>>();
    /// assert_eq!(range, [3]);
    ///
    /// // 全方位涵盖所有内容
    /// let all = v.range(..);
    /// assert_eq!(all.len(), 3);
    /// ```
    #[inline]
    #[stable(feature = "deque_range", since = "1.51.0")]
    pub fn range<R>(&self, range: R) -> Iter<'_, T>
    where
        R: RangeBounds<usize>,
    {
        let (tail, head) = self.range_tail_head(range);
        Iter {
            tail,
            head,
            // &self 中的共享引用保留在 Iter 的 '_中。
            ring: unsafe { self.buffer_as_slice() },
        }
    }

    /// 创建一个覆盖 `VecDeque` 中指定的可变范围的迭代器。
    ///
    /// # Panics
    ///
    /// 如果起点大于终点或终点大于 vector 的长度，则为 Panics。
    ///
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let mut v: VecDeque<_> = vec![1, 2, 3].into_iter().collect();
    /// for v in v.range_mut(2..) {
    ///   *v *= 2;
    /// }
    /// assert_eq!(v, vec![1, 2, 6]);
    ///
    /// // 全方位涵盖所有内容
    /// for v in v.range_mut(..) {
    ///   *v *= 2;
    /// }
    /// assert_eq!(v, vec![2, 4, 12]);
    /// ```
    #[inline]
    #[stable(feature = "deque_range", since = "1.51.0")]
    pub fn range_mut<R>(&mut self, range: R) -> IterMut<'_, T>
    where
        R: RangeBounds<usize>,
    {
        let (tail, head) = self.range_tail_head(range);

        // SAFETY: 之所以建立内部 `IterMut` 安全不变式，是因为我们创建的 `ring` 是生命周期 '_的可引用切片。
        //
        IterMut {
            tail,
            head,
            ring: ptr::slice_from_raw_parts_mut(self.ptr(), self.cap()),
            phantom: PhantomData,
        }
    }

    /// 创建一个 draining 迭代器，该迭代器将删除 `VecDeque` 中的指定范围并产生已删除的项。
    ///
    /// 注意 1: 即使直到最后才消耗迭代器，元素范围也会被删除。
    ///
    /// 注意 2: 如果 `Drain` 值没有被丢弃，但持有的借用已过期 (例如，由于 `mem::forget`)，则未指定从双端队列中删除了多少个元素。
    ///
    ///
    /// # Panics
    ///
    /// 如果起点大于终点或终点大于 vector 的长度，则为 Panics。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let mut v: VecDeque<_> = vec![1, 2, 3].into_iter().collect();
    /// let drained = v.drain(2..).collect::<VecDeque<_>>();
    /// assert_eq!(drained, [3]);
    /// assert_eq!(v, [1, 2]);
    ///
    /// // 全系列清除所有内容
    /// v.drain(..);
    /// assert!(v.is_empty());
    /// ```
    ///
    ///
    ///
    ///
    #[inline]
    #[stable(feature = "drain", since = "1.6.0")]
    pub fn drain<R>(&mut self, range: R) -> Drain<'_, T>
    where
        R: RangeBounds<usize>,
    {
        // 内存安全
        //
        // 首次创建 Drain 时，将缩短源双端队列，以确保在 Drain 的析构函数从不运行的情况下，根本无法访问未初始化或移出的元素。
        //
        //
        // Drain 将 ptr::read 取出要删除的值。
        // 完成后，剩余的数据将被复制回以覆盖 hole，并且 head/tail 值将被正确恢复。
        //
        //
        //
        let (drain_tail, drain_head) = self.range_tail_head(range);

        // 双端队列的元素分为三个部分:
        // * self.tail  -> drain_tail
        // * drain_tail -> drain_head
        // * drain_head -> self.head
        //
        // T = self.tail; H = self.head; t = drain_tail; h = drain_head
        //
        // 我们将 drain_tail 存储为 self.head，并将 drain_head 和 self.head 分别存储为 Drain 上的 after_tail 和 after_head。
        // 这也将截断有效数组，以使如果 Drain 泄漏，我们将在 drain 开始后忘记可能移动的值。
        //
        //
        //        T   t   h   H
        // [. . . o o x x o o . . .]
        //
        //
        //
        let head = self.head;

        // "forget" 关于 drain 开始之后直到 drain 完成并且 Drain 析构函数运行之后的值。
        //
        self.head = drain_tail;

        Drain {
            deque: NonNull::from(&mut *self),
            after_tail: drain_head,
            after_head: head,
            iter: Iter {
                tail: drain_tail,
                head: drain_head,
                // 至关重要的是，我们仅在此处从 `self` 创建共享引用并从中读取。
                // 我们既不写 `self`，也不重新借用可变引用。
                // 因此，我们上面为 `deque` 创建的裸指针仍然有效。
                ring: unsafe { self.buffer_as_slice() },
            },
        }
    }

    /// 清除 `VecDeque`，删除所有值。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let mut v = VecDeque::new();
    /// v.push_back(1);
    /// v.clear();
    /// assert!(v.is_empty());
    /// ```
    #[stable(feature = "rust1", since = "1.0.0")]
    #[inline]
    pub fn clear(&mut self) {
        self.truncate(0);
    }

    /// 如果 `VecDeque` 包含等于给定值的元素，则返回 `true`。
    ///
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let mut vector: VecDeque<u32> = VecDeque::new();
    ///
    /// vector.push_back(0);
    /// vector.push_back(1);
    ///
    /// assert_eq!(vector.contains(&1), true);
    /// assert_eq!(vector.contains(&10), false);
    /// ```
    #[stable(feature = "vec_deque_contains", since = "1.12.0")]
    pub fn contains(&self, x: &T) -> bool
    where
        T: PartialEq<T>,
    {
        let (a, b) = self.as_slices();
        a.contains(x) || b.contains(x)
    }

    /// 提供对前元素的引用，如果 `VecDeque` 为空，则为 `None`。
    ///
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let mut d = VecDeque::new();
    /// assert_eq!(d.front(), None);
    ///
    /// d.push_back(1);
    /// d.push_back(2);
    /// assert_eq!(d.front(), Some(&1));
    /// ```
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn front(&self) -> Option<&T> {
        self.get(0)
    }

    /// 为前元素提供可变引用，如果 `VecDeque` 为空，则为 `None`。
    ///
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let mut d = VecDeque::new();
    /// assert_eq!(d.front_mut(), None);
    ///
    /// d.push_back(1);
    /// d.push_back(2);
    /// match d.front_mut() {
    ///     Some(x) => *x = 9,
    ///     None => (),
    /// }
    /// assert_eq!(d.front(), Some(&9));
    /// ```
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn front_mut(&mut self) -> Option<&mut T> {
        self.get_mut(0)
    }

    /// 提供对 back 元素的引用，如果 `VecDeque` 为空，则提供 `None`。
    ///
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let mut d = VecDeque::new();
    /// assert_eq!(d.back(), None);
    ///
    /// d.push_back(1);
    /// d.push_back(2);
    /// assert_eq!(d.back(), Some(&2));
    /// ```
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn back(&self) -> Option<&T> {
        self.get(self.len().wrapping_sub(1))
    }

    /// 提供对 back 元素的可变引用，如果 `VecDeque` 为空，则提供 `None`。
    ///
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let mut d = VecDeque::new();
    /// assert_eq!(d.back(), None);
    ///
    /// d.push_back(1);
    /// d.push_back(2);
    /// match d.back_mut() {
    ///     Some(x) => *x = 9,
    ///     None => (),
    /// }
    /// assert_eq!(d.back(), Some(&9));
    /// ```
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn back_mut(&mut self) -> Option<&mut T> {
        self.get_mut(self.len().wrapping_sub(1))
    }

    /// 删除第一个元素并返回它，如果 `VecDeque` 为空，则返回 `None`。
    ///
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let mut d = VecDeque::new();
    /// d.push_back(1);
    /// d.push_back(2);
    ///
    /// assert_eq!(d.pop_front(), Some(1));
    /// assert_eq!(d.pop_front(), Some(2));
    /// assert_eq!(d.pop_front(), None);
    /// ```
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn pop_front(&mut self) -> Option<T> {
        if self.is_empty() {
            None
        } else {
            let tail = self.tail;
            self.tail = self.wrap_add(self.tail, 1);
            unsafe { Some(self.buffer_read(tail)) }
        }
    }

    /// 从 `VecDeque` 中删除最后一个元素并返回它; 如果它为空，则返回 `None`。
    ///
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let mut buf = VecDeque::new();
    /// assert_eq!(buf.pop_back(), None);
    /// buf.push_back(1);
    /// buf.push_back(3);
    /// assert_eq!(buf.pop_back(), Some(3));
    /// ```
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn pop_back(&mut self) -> Option<T> {
        if self.is_empty() {
            None
        } else {
            self.head = self.wrap_sub(self.head, 1);
            let head = self.head;
            unsafe { Some(self.buffer_read(head)) }
        }
    }

    /// 将元素添加到 `VecDeque`。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let mut d = VecDeque::new();
    /// d.push_front(1);
    /// d.push_front(2);
    /// assert_eq!(d.front(), Some(&2));
    /// ```
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn push_front(&mut self, value: T) {
        if self.is_full() {
            self.grow();
        }

        self.tail = self.wrap_sub(self.tail, 1);
        let tail = self.tail;
        unsafe {
            self.buffer_write(tail, value);
        }
    }

    /// 在 `VecDeque` 的后面附加一个元素。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let mut buf = VecDeque::new();
    /// buf.push_back(1);
    /// buf.push_back(3);
    /// assert_eq!(3, *buf.back().unwrap());
    /// ```
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn push_back(&mut self, value: T) {
        if self.is_full() {
            self.grow();
        }

        let head = self.head;
        self.head = self.wrap_add(self.head, 1);
        unsafe { self.buffer_write(head, value) }
    }

    #[inline]
    fn is_contiguous(&self) -> bool {
        // FIXME: 我们是否应该认为 `head == 0` 表示 `self` 是连续的?
        //
        self.tail <= self.head
    }

    /// 从 `VecDeque` 的任何位置删除一个元素并返回，并用第一个元素替换它。
    ///
    ///
    /// 这不会保留顺序，而是 *O*(1)。
    ///
    /// 如果 `index` 越界，则返回 `None`。
    ///
    /// 索引为 0 的元素在队列的最前面。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let mut buf = VecDeque::new();
    /// assert_eq!(buf.swap_remove_front(0), None);
    /// buf.push_back(1);
    /// buf.push_back(2);
    /// buf.push_back(3);
    /// assert_eq!(buf, [1, 2, 3]);
    ///
    /// assert_eq!(buf.swap_remove_front(2), Some(3));
    /// assert_eq!(buf, [2, 1]);
    /// ```
    #[stable(feature = "deque_extras_15", since = "1.5.0")]
    pub fn swap_remove_front(&mut self, index: usize) -> Option<T> {
        let length = self.len();
        if length > 0 && index < length && index != 0 {
            self.swap(index, 0);
        } else if index >= length {
            return None;
        }
        self.pop_front()
    }

    /// 从 `VecDeque` 中的任何位置删除元素，然后将其返回，并用最后一个元素替换。
    ///
    ///
    /// 这不会保留顺序，而是 *O*(1)。
    ///
    /// 如果 `index` 越界，则返回 `None`。
    ///
    /// 索引为 0 的元素在队列的最前面。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let mut buf = VecDeque::new();
    /// assert_eq!(buf.swap_remove_back(0), None);
    /// buf.push_back(1);
    /// buf.push_back(2);
    /// buf.push_back(3);
    /// assert_eq!(buf, [1, 2, 3]);
    ///
    /// assert_eq!(buf.swap_remove_back(0), Some(1));
    /// assert_eq!(buf, [3, 2]);
    /// ```
    #[stable(feature = "deque_extras_15", since = "1.5.0")]
    pub fn swap_remove_back(&mut self, index: usize) -> Option<T> {
        let length = self.len();
        if length > 0 && index < length - 1 {
            self.swap(index, length - 1);
        } else if index >= length {
            return None;
        }
        self.pop_back()
    }

    /// 在 `VecDeque` 内的 `index` 处插入一个元素，将所有索引大于或等于 `index` 的元素向后移动。
    ///
    ///
    /// 索引为 0 的元素在队列的最前面。
    ///
    /// # Panics
    ///
    /// 如果 `index` 大于 `VecDeque` 的长度，则为 Panics
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let mut vec_deque = VecDeque::new();
    /// vec_deque.push_back('a');
    /// vec_deque.push_back('b');
    /// vec_deque.push_back('c');
    /// assert_eq!(vec_deque, &['a', 'b', 'c']);
    ///
    /// vec_deque.insert(1, 'd');
    /// assert_eq!(vec_deque, &['a', 'd', 'b', 'c']);
    /// ```
    #[stable(feature = "deque_extras_15", since = "1.5.0")]
    pub fn insert(&mut self, index: usize, value: T) {
        assert!(index <= self.len(), "index out of bounds");
        if self.is_full() {
            self.grow();
        }

        // 在环形缓冲区中移动最少数量的元素并插入给定的对象
        //
        // 最多移动 `len/2 - 1`个元素。O(min(n, n-i))
        //
        // 主要有以下三种情况:
        //  元素是连续的
        //      - tail 为 0 时的特殊情况元素不连续且插入在尾部元素不连续且插入在头部
        //
        //
        // 对于每种情况，还有两种情况:
        //  插入物更靠近尾部插入物更靠近头
        //
        // Key: H - self.head T - self.tail o - 有效元素 I - 插入元素 A - 插入点之后的元素 M - 指示元素已移动
        //
        //
        //
        //
        //
        //
        //
        //

        let idx = self.wrap_add(self.tail, index);

        let distance_to_tail = index;
        let distance_to_head = self.len() - index;

        let contiguous = self.is_contiguous();

        match (contiguous, distance_to_tail <= distance_to_head, idx >= self.tail) {
            (true, true, _) if index == 0 => {
                // push_front
                //
                //       T I             H
                //      [A o o o o o o . . . . . . .
                //      .
                //      .]
                //
                //                       H         T
                //      [A o o o o o o o . . . . . I]

                self.tail = self.wrap_sub(self.tail, 1);
            }
            (true, true, _) => {
                unsafe {
                    // 连续的，插入到更靠近尾部的位置:
                    //
                    //             T   I         H
                    //      [. . . o o A o o o o . . . . . .]
                    //
                    //           T               H
                    //      [. . o o I A o o o o . . . . . .]
                    //           M M
                    //
                    // 连续，插入时靠近尾部 ，并且尾部为 0:
                    //
                    //
                    //       T   I         H
                    //      [o o A o o o o . . . . . . . . .]
                    //
                    //                       H             T
                    //      [o I A o o o o o . . . . . . . o]
                    //       M                             M

                    let new_tail = self.wrap_sub(self.tail, 1);

                    self.copy(new_tail, self.tail, 1);
                    // 已经移动了尾部，因此我们仅复制 `index - 1` 元素。
                    self.copy(self.tail, self.tail + 1, index - 1);

                    self.tail = new_tail;
                }
            }
            (true, false, _) => {
                unsafe {
                    // 连续的，靠近头部插入:
                    //
                    //             T       I     H
                    //      [. . . o o o o A o o . . . . . .]
                    //
                    //             T               H
                    //      [. . . o o o o I A o o . . . . .]
                    //                       M M M

                    self.copy(idx + 1, idx, self.head - idx);
                    self.head = self.wrap_add(self.head, 1);
                }
            }
            (false, true, true) => {
                unsafe {
                    // 不连续的，靠近尾部插入，尾部部分:
                    //
                    //                   H         T   I
                    //      [o o o o o o . . . . . o o A o o]
                    //
                    //                   H       T
                    //      [o o o o o o . . . . o o I A o o]
                    //                           M M

                    self.copy(self.tail - 1, self.tail, index);
                    self.tail -= 1;
                }
            }
            (false, false, true) => {
                unsafe {
                    // 不连续的，插入得更靠近头部，尾部部分:
                    //
                    //           H             T         I
                    //      [o o . . . . . . . o o o o o A o]
                    //
                    //             H           T
                    //      [o o o . . . . . . o o o o o I A]
                    //       M M M                         M

                    // 复制元素直到新的头部
                    self.copy(1, 0, self.head);

                    // 将最后一个元素复制到缓冲区底部的空白处
                    self.copy(0, self.cap() - 1, 1);

                    // 将元素从 idx 移动到结束，不包括 ^ 元素
                    self.copy(idx + 1, idx, self.cap() - 1 - idx);

                    self.head += 1;
                }
            }
            (false, true, false) if idx == 0 => {
                unsafe {
                    // 不连续，insert 更靠近尾部，头部，并且在内部缓冲区中的索引为零:
                    //
                    //
                    //       I                   H     T
                    //      [A o o o o o o o o o . . . o o o]
                    //
                    //                           H   T
                    //      [A o o o o o o o o o . . o o o I]
                    //                               M M M

                    // 复制元素直到新尾
                    self.copy(self.tail - 1, self.tail, self.cap() - self.tail);

                    // 将最后一个元素复制到缓冲区底部的空白处
                    self.copy(self.cap() - 1, 0, 1);

                    self.tail -= 1;
                }
            }
            (false, true, false) => {
                unsafe {
                    // 不连续的，靠近尾部插入，头部部分:
                    //
                    //             I             H     T
                    //      [o o o A o o o o o o . . . o o o]
                    //
                    //                           H   T
                    //      [o o I A o o o o o o . . o o o o]
                    //       M M                     M M M M

                    // 复制元素直到新尾
                    self.copy(self.tail - 1, self.tail, self.cap() - self.tail);

                    // 将最后一个元素复制到缓冲区底部的空白处
                    self.copy(self.cap() - 1, 0, 1);

                    // 将元素从 idx-1 移至末尾，不包括 ^ 元素
                    self.copy(0, 1, idx - 1);

                    self.tail -= 1;
                }
            }
            (false, false, false) => {
                unsafe {
                    // 不连续的，靠近尾部插入，头部部分:
                    //
                    //               I     H           T
                    //      [o o o o A o o . . . . . . o o o]
                    //
                    //                     H           T
                    //      [o o o o I A o o . . . . . o o o]
                    //                 M M M

                    self.copy(idx + 1, idx, self.head - idx);
                    self.head += 1;
                }
            }
        }

        // 尾部可能已更改，因此我们需要重新计算
        let new_idx = self.wrap_add(self.tail, index);
        unsafe {
            self.buffer_write(new_idx, value);
        }
    }

    /// 从 `VecDeque` 删除 `index` 处的元素，并返回该元素。
    /// 靠近移除点的任意一端将被移动以腾出空间，所有受影响的元素将被移动到新位置。
    ///
    /// 如果 `index` 越界，则返回 `None`。
    ///
    /// 索引为 0 的元素在队列的最前面。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let mut buf = VecDeque::new();
    /// buf.push_back(1);
    /// buf.push_back(2);
    /// buf.push_back(3);
    /// assert_eq!(buf, [1, 2, 3]);
    ///
    /// assert_eq!(buf.remove(1), Some(2));
    /// assert_eq!(buf, [1, 3]);
    /// ```
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn remove(&mut self, index: usize) -> Option<T> {
        if self.is_empty() || self.len() <= index {
            return None;
        }

        // 主要有以下三种情况:
        //  元素是连续的元素是不连续的，并且去除在尾部元素是不连续的，并且去除在头部
        //      - 特殊情况下，元素在技术上是连续的，但是 self.head = 0
        //
        // 对于每种情况，还有两种情况:
        //  插入物更靠近尾部插入物更靠近头
        //
        // Key: H-self.head T-self.tail o - 有效元素 x - 标记为要删除的元素 R - 表示要删除的元素 M - 表示元素已移动
        //
        //
        //
        //
        //
        //
        //
        //
        //

        let idx = self.wrap_add(self.tail, index);

        let elem = unsafe { Some(self.buffer_read(idx)) };

        let distance_to_tail = index;
        let distance_to_head = self.len() - index;

        let contiguous = self.is_contiguous();

        match (contiguous, distance_to_tail <= distance_to_head, idx >= self.tail) {
            (true, true, _) => {
                unsafe {
                    // 连续，移近尾部:
                    //
                    //             T   R         H
                    //      [. . . o o x o o o o . . . . . .]
                    //
                    //               T           H
                    //      [. . . . o o o o o o . . . . . .]
                    //               M M

                    self.copy(self.tail + 1, self.tail, index);
                    self.tail += 1;
                }
            }
            (true, false, _) => {
                unsafe {
                    // 连续，移近头部:
                    //
                    //             T       R     H
                    //      [. . . o o o o x o o . . . . . .]
                    //
                    //             T           H
                    //      [. . . o o o o o o . . . . . . .]
                    //                     M M

                    self.copy(idx, idx + 1, self.head - idx - 1);
                    self.head -= 1;
                }
            }
            (false, true, true) => {
                unsafe {
                    // 不连续的，去掉更靠近尾部的地方，尾部部分:
                    //
                    //                   H         T   R
                    //      [o o o o o o . . . . . o o x o o]
                    //
                    //                   H           T
                    //      [o o o o o o . . . . . . o o o o]
                    //                               M M

                    self.copy(self.tail + 1, self.tail, index);
                    self.tail = self.wrap_add(self.tail, 1);
                }
            }
            (false, false, false) => {
                unsafe {
                    // 不连续的，移近头部，头部:
                    //
                    //               R     H           T
                    //      [o o o o x o o . . . . . . o o o]
                    //
                    //                   H             T
                    //      [o o o o o o . . . . . . . o o o]
                    //               M M

                    self.copy(idx, idx + 1, self.head - idx - 1);
                    self.head -= 1;
                }
            }
            (false, false, true) => {
                unsafe {
                    // 不连续的，移至离头部，尾部更近的位置:
                    //
                    //             H           T         R
                    //      [o o o . . . . . . o o o o o x o]
                    //
                    //           H             T
                    //      [o o . . . . . . . o o o o o o o]
                    //       M M                         M M
                    //
                    // 或准不连续，在头部，尾部旁边移除:
                    //
                    //       H                 T         R
                    //      [. . . . . . . . . o o o o o x o]
                    //
                    //                         T           H
                    //      [. . . . . . . . . o o o o o o .]
                    //                                   M

                    // 在尾部绘制元素
                    self.copy(idx, idx + 1, self.cap() - idx - 1);

                    // 防止下溢。
                    if self.head != 0 {
                        // 将第一个元素复制到空白处
                        self.copy(self.cap() - 1, 0, 1);

                        // 向后移动头部的元素
                        self.copy(0, 1, self.head - 1);
                    }

                    self.head = self.wrap_sub(self.head, 1);
                }
            }
            (false, true, false) => {
                unsafe {
                    // 不连续的，移至靠近尾部，头部的部分:
                    //
                    //           R               H     T
                    //      [o o x o o o o o o o . . . o o o]
                    //
                    //                           H       T
                    //      [o o o o o o o o o o . . . . o o]
                    //       M M M                       M M

                    // 绘制多达 idx 的元素
                    self.copy(1, 0, idx);

                    // 将最后一个元素复制到空白处
                    self.copy(0, self.cap() - 1, 1);

                    // 将元素从尾部向前移动到末尾，不包括最后一个
                    self.copy(self.tail + 1, self.tail, self.cap() - self.tail - 1);

                    self.tail = self.wrap_add(self.tail, 1);
                }
            }
        }

        elem
    }

    /// 在给定的索引处将 `VecDeque` 拆分为两个。
    ///
    /// 返回新分配的 `VecDeque`。
    /// `self` 包含元素 `[0, at)`，返回的 `VecDeque` 包含元素 `[at, len)`。
    ///
    /// 请注意，`self` 的容量不会改变。
    ///
    /// 索引为 0 的元素在队列的最前面。
    ///
    /// # Panics
    ///
    /// 如果为 `at > len`，则为 Panics。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let mut buf: VecDeque<_> = vec![1, 2, 3].into_iter().collect();
    /// let buf2 = buf.split_off(1);
    /// assert_eq!(buf, [1]);
    /// assert_eq!(buf2, [2, 3]);
    /// ```
    #[inline]
    #[must_use = "use `.truncate()` if you don't need the other half"]
    #[stable(feature = "split_off", since = "1.4.0")]
    pub fn split_off(&mut self, at: usize) -> Self {
        let len = self.len();
        assert!(at <= len, "`at` out of bounds");

        let other_len = len - at;
        let mut other = VecDeque::with_capacity(other_len);

        unsafe {
            let (first_half, second_half) = self.as_slices();

            let first_len = first_half.len();
            let second_len = second_half.len();
            if at < first_len {
                // `at` 位于上半部分。
                let amount_in_first = first_len - at;

                ptr::copy_nonoverlapping(first_half.as_ptr().add(at), other.ptr(), amount_in_first);

                // 下半部分全部拿下。
                ptr::copy_nonoverlapping(
                    second_half.as_ptr(),
                    other.ptr().add(amount_in_first),
                    second_len,
                );
            } else {
                // `at` 在于下半部分，需要考虑上半部分我们跳过的元素。
                //
                let offset = at - first_len;
                let amount_in_second = second_len - offset;
                ptr::copy_nonoverlapping(
                    second_half.as_ptr().add(offset),
                    other.ptr(),
                    amount_in_second,
                );
            }
        }

        // 清理缓冲区末端的位置
        self.head = self.wrap_sub(self.head, other_len);
        other.head = other.wrap_index(other_len);

        other
    }

    /// 将 `other` 的所有元素移到 `self`，将 `other` 留空。
    ///
    /// # Panics
    ///
    /// Panics，如果 self 中新的元素数量溢出 `usize`。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let mut buf: VecDeque<_> = vec![1, 2].into_iter().collect();
    /// let mut buf2: VecDeque<_> = vec![3, 4].into_iter().collect();
    /// buf.append(&mut buf2);
    /// assert_eq!(buf, [1, 2, 3, 4]);
    /// assert_eq!(buf2, []);
    /// ```
    #[inline]
    #[stable(feature = "append", since = "1.4.0")]
    pub fn append(&mut self, other: &mut Self) {
        // 单纯的实现
        self.extend(other.drain(..));
    }

    /// 仅保留谓词指定的元素。
    ///
    /// 换句话说，删除所有元素 `e`，以使 `f(&e)` 返回 false。
    /// 此方法在原位运行，以原始顺序恰好一次访问每个元素，并保留保留元素的顺序。
    ///
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let mut buf = VecDeque::new();
    /// buf.extend(1..5);
    /// buf.retain(|&x| x % 2 == 0);
    /// assert_eq!(buf, [2, 4]);
    /// ```
    ///
    /// 确切的顺序对于跟踪外部状态 (例如索引) 可能很有用。
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let mut buf = VecDeque::new();
    /// buf.extend(1..6);
    ///
    /// let keep = [false, true, true, false, true];
    /// let mut i = 0;
    /// buf.retain(|_| (keep[i], i += 1).0);
    /// assert_eq!(buf, [2, 3, 5]);
    /// ```
    #[stable(feature = "vec_deque_retain", since = "1.4.0")]
    pub fn retain<F>(&mut self, mut f: F)
    where
        F: FnMut(&T) -> bool,
    {
        let len = self.len();
        let mut del = 0;
        for i in 0..len {
            if !f(&self[i]) {
                del += 1;
            } else if del > 0 {
                self.swap(i - del, i);
            }
        }
        if del > 0 {
            self.truncate(len - del);
        }
    }

    // 这可能是 panic 或终止
    #[inline(never)]
    fn grow(&mut self) {
        if self.is_full() {
            let old_cap = self.cap();
            // 缓冲区大小加倍。
            self.buf.reserve_exact(old_cap, old_cap);
            assert!(self.cap() == old_cap * 2);
            unsafe {
                self.handle_capacity_increase(old_cap);
            }
            debug_assert!(!self.is_full());
        }
    }

    /// 在原位修改 `VecDeque`，以使 `len()` 等于 `new_len`，方法是从后面移除多余的元素，或者通过在后面附加调用 `generator` 生成的元素。
    ///
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let mut buf = VecDeque::new();
    /// buf.push_back(5);
    /// buf.push_back(10);
    /// buf.push_back(15);
    /// assert_eq!(buf, [5, 10, 15]);
    ///
    /// buf.resize_with(5, Default::default);
    /// assert_eq!(buf, [5, 10, 15, 0, 0]);
    ///
    /// buf.resize_with(2, || unreachable!());
    /// assert_eq!(buf, [5, 10]);
    ///
    /// let mut state = 100;
    /// buf.resize_with(5, || { state += 1; state });
    /// assert_eq!(buf, [5, 10, 101, 102, 103]);
    /// ```
    ///
    #[stable(feature = "vec_resize_with", since = "1.33.0")]
    pub fn resize_with(&mut self, new_len: usize, generator: impl FnMut() -> T) {
        let len = self.len();

        if new_len > len {
            self.extend(repeat_with(generator).take(new_len - len))
        } else {
            self.truncate(new_len);
        }
    }

    /// 重新排列此双端队列的内部存储，使其成为一个连续的切片，然后将其返回。
    ///
    /// 此方法不分配也不更改插入元素的顺序。当它返回可变切片时，可用于对双端队列进行排序。
    ///
    /// 内部存储器连续后，[`as_slices`] 和 [`as_mut_slices`] 方法将在单个切片中返回 `VecDeque` 的全部内容。
    ///
    ///
    /// [`as_slices`]: VecDeque::as_slices
    /// [`as_mut_slices`]: VecDeque::as_mut_slices
    ///
    /// # Examples
    ///
    /// 排序双端队列的内容。
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let mut buf = VecDeque::with_capacity(15);
    ///
    /// buf.push_back(2);
    /// buf.push_back(1);
    /// buf.push_front(3);
    ///
    /// // 排序双端队列
    /// buf.make_contiguous().sort();
    /// assert_eq!(buf.as_slices(), (&[1, 2, 3] as &[_], &[] as &[_]));
    ///
    /// // 反向排序
    /// buf.make_contiguous().sort_by(|a, b| b.cmp(a));
    /// assert_eq!(buf.as_slices(), (&[3, 2, 1] as &[_], &[] as &[_]));
    /// ```
    ///
    /// 不可变地访问连续的切片。
    ///
    /// ```rust
    /// use std::collections::VecDeque;
    ///
    /// let mut buf = VecDeque::new();
    ///
    /// buf.push_back(2);
    /// buf.push_back(1);
    /// buf.push_front(3);
    ///
    /// buf.make_contiguous();
    /// if let (slice, &[]) = buf.as_slices() {
    ///     // 现在，我们可以确定 `slice` 包含了双端队列的所有元素，同时仍具有对 `buf` 的不可变访问权限。
    /////
    ///     assert_eq!(buf.len(), slice.len());
    ///     assert_eq!(slice, &[3, 2, 1] as &[_]);
    /// }
    /// ```
    ///
    ///
    ///
    ///
    #[stable(feature = "deque_make_contiguous", since = "1.48.0")]
    pub fn make_contiguous(&mut self) -> &mut [T] {
        if self.is_contiguous() {
            let tail = self.tail;
            let head = self.head;
            return unsafe { RingSlices::ring_slices(self.buffer_as_mut_slice(), head, tail).0 };
        }

        let buf = self.buf.ptr();
        let cap = self.cap();
        let len = self.len();

        let free = self.tail - self.head;
        let tail_len = cap - self.tail;

        if free >= tail_len {
            // 有足够的可用空间来一次性复制尾部，这意味着我们先将头向后移动，然后再将尾部复制到正确的位置。
            //
            //
            // 从: DEFGH....ABC 到: ABCDEFGH....
            //
            //
            unsafe {
                ptr::copy(buf, buf.add(tail_len), self.head);
                // ...DEFGH.ABC
                ptr::copy_nonoverlapping(buf.add(self.tail), buf, tail_len);
                // ABCDEFGH....

                self.tail = 0;
                self.head = len;
            }
        } else if free > self.head {
            // FIXME: 我们目前不认为 ....ABCDEFGH 是连续的，因为在这种情况下 `head` 将为 `0`。
            // 尽管我们可能想更改它，但这并不是一件容易的事，因为有些地方期望 `is_contiguous` 表示我们可以使用 `buf[tail..head]` 进行切片。
            //
            //
            //

            // 有足够的自由空间可以一次性复制头部，这意味着我们先将尾部向前移动，然后再将头部复制到正确的位置。
            //
            //
            // 从: FGH....ABCDE 到: ...ABCDEFGH。
            //
            //
            unsafe {
                ptr::copy(buf.add(self.tail), buf.add(self.head), tail_len);
                // FGHABCDE....
                ptr::copy_nonoverlapping(buf, buf.add(self.head + tail_len), self.head);
                // ...ABCDEFGH.

                self.tail = self.head;
                self.head = self.wrap_add(self.tail, len);
            }
        } else {
            // free 小于头和尾，这意味着我们必须缓慢地 "swap" 尾和头。
            //
            //
            // 从: EFGHI...ABCD  或 HIJK.ABCDEFG 到: ABCDEFGHI... or ABCDEFGHIJK.
            //
            let mut left_edge: usize = 0;
            let mut right_edge: usize = self.tail;
            unsafe {
                // 一般问题如下所示: GHIJKLM ... ABCDEF - 进行任何交换之前 ABCDEFM ... GHIJKL - 进行 1 次交换之后 ABCDEFGHIJM ... KL - 交换直到左 edge 到达临时存储
                //                  - 然后使用新的 (smaller) 存储区重新启动算法。有时，当正确的 edge 位于缓冲区的末尾时，便达到了临时存储区 - 这意味着我们以更少的交换找到了正确的顺序!
                //
                // E.g
                // EF..ABCD ABCDEF.. - 经过四次交换，我们已经完成了
                //
                //
                //
                //
                //
                while left_edge < len && right_edge != cap {
                    let mut right_offset = 0;
                    for i in left_edge..right_edge {
                        right_offset = (i - left_edge) % (cap - right_edge);
                        let src: isize = (right_edge + right_offset) as isize;
                        ptr::swap(buf.add(i), buf.offset(src));
                    }
                    let n_ops = right_edge - left_edge;
                    left_edge += n_ops;
                    right_edge += right_offset + 1;
                }

                self.tail = 0;
                self.head = len;
            }
        }

        let tail = self.tail;
        let head = self.head;
        unsafe { RingSlices::ring_slices(self.buffer_as_mut_slice(), head, tail).0 }
    }

    /// 将双端队列 `mid` 放置到左侧。
    ///
    /// Equivalently,
    /// - 将项 `mid` 旋转到第一个位置。
    /// - 弹出第一个 `mid` 项并将其推到末尾。
    /// - 向右旋转 `len() - mid` 位置。
    ///
    /// # Panics
    ///
    /// 如果 `mid` 大于 `len()`。
    /// 请注意，`mid == len()` 执行 _not_ panic，并且是无操作旋转。
    ///
    /// # Complexity
    ///
    /// 花费 `*O*(min(mid, len() - mid))` 的时间，没有多余的空间。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let mut buf: VecDeque<_> = (0..10).collect();
    ///
    /// buf.rotate_left(3);
    /// assert_eq!(buf, [3, 4, 5, 6, 7, 8, 9, 0, 1, 2]);
    ///
    /// for i in 1..10 {
    ///     assert_eq!(i * 3 % 10, buf[0]);
    ///     buf.rotate_left(3);
    /// }
    /// assert_eq!(buf, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
    /// ```
    #[stable(feature = "vecdeque_rotate", since = "1.36.0")]
    pub fn rotate_left(&mut self, mid: usize) {
        assert!(mid <= self.len());
        let k = self.len() - mid;
        if mid <= k {
            unsafe { self.rotate_left_inner(mid) }
        } else {
            unsafe { self.rotate_right_inner(k) }
        }
    }

    /// 向右旋转 `k` 位置的双端队列。
    ///
    /// Equivalently,
    /// - 将第一个项旋转到位置 `k`。
    /// - 弹出最后一个 `k` 项并将其推到前面。
    /// - 将 `len() - k` 位置向左旋转。
    ///
    /// # Panics
    ///
    /// 如果 `k` 大于 `len()`。
    /// 请注意，`k == len()` 执行 _not_ panic，并且是无操作旋转。
    ///
    /// # Complexity
    ///
    /// 花费 `*O*(min(k, len() - k))` 的时间，没有多余的空间。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let mut buf: VecDeque<_> = (0..10).collect();
    ///
    /// buf.rotate_right(3);
    /// assert_eq!(buf, [7, 8, 9, 0, 1, 2, 3, 4, 5, 6]);
    ///
    /// for i in 1..10 {
    ///     assert_eq!(0, buf[i * 3 % 10]);
    ///     buf.rotate_right(3);
    /// }
    /// assert_eq!(buf, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
    /// ```
    #[stable(feature = "vecdeque_rotate", since = "1.36.0")]
    pub fn rotate_right(&mut self, k: usize) {
        assert!(k <= self.len());
        let mid = self.len() - k;
        if k <= mid {
            unsafe { self.rotate_right_inner(k) }
        } else {
            unsafe { self.rotate_left_inner(mid) }
        }
    }

    // SAFETY: 以下两种方法要求旋转量小于双端队列的长度的一半。
    //
    // `wrap_copy` 要求 `min(x, cap() - x) + copy_len <= cap()`，但是 `min` 永远不超过容量的一半，而与 x 无关，因此在这里调用是合理的，因为我们所调用的长度小于长度的一半，永远不超过容量的一半。
    //
    //
    //
    //

    unsafe fn rotate_left_inner(&mut self, mid: usize) {
        debug_assert!(mid * 2 <= self.len());
        unsafe {
            self.wrap_copy(self.head, self.tail, mid);
        }
        self.head = self.wrap_add(self.head, mid);
        self.tail = self.wrap_add(self.tail, mid);
    }

    unsafe fn rotate_right_inner(&mut self, k: usize) {
        debug_assert!(k * 2 <= self.len());
        self.head = self.wrap_sub(self.head, k);
        self.tail = self.wrap_sub(self.tail, k);
        unsafe {
            self.wrap_copy(self.tail, self.head, k);
        }
    }

    /// Binary 在此排序的 `VecDeque` 上搜索给定的元素。
    ///
    /// 如果找到该值，则返回 [`Result::Ok`]，其中包含匹配元素的索引。
    /// 如果有多个匹配项，则可以返回任何一个匹配项。
    /// 如果找不到该值，则返回 [`Result::Err`]，其中包含在保留排序顺序的同时可以在其中插入匹配元素的索引。
    ///
    ///
    /// 另请参见 [`binary_search_by`]，[`binary_search_by_key`] 和 [`partition_point`]。
    ///
    /// [`binary_search_by`]: VecDeque::binary_search_by
    /// [`binary_search_by_key`]: VecDeque::binary_search_by_key
    /// [`partition_point`]: VecDeque::partition_point
    ///
    /// # Examples
    ///
    /// 查找一系列四个元素。
    /// 找到第一个，具有唯一确定的位置; 找不到第二和第三个; 第四个可以匹配 `[1, 4]` 中的任何位置。
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let deque: VecDeque<_> = vec![0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55].into();
    ///
    /// assert_eq!(deque.binary_search(&13),  Ok(9));
    /// assert_eq!(deque.binary_search(&4),   Err(7));
    /// assert_eq!(deque.binary_search(&100), Err(13));
    /// let r = deque.binary_search(&1);
    /// assert!(matches!(r, Ok(1..=4)));
    /// ```
    ///
    /// 如果要在已排序的 `VecDeque` 上插入项目，同时保持排序顺序:
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let mut deque: VecDeque<_> = vec![0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55].into();
    /// let num = 42;
    /// let idx = deque.binary_search(&num).unwrap_or_else(|x| x);
    /// deque.insert(idx, num);
    /// assert_eq!(deque, &[0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 42, 55]);
    /// ```
    ///
    ///
    ///
    #[stable(feature = "vecdeque_binary_search", since = "1.54.0")]
    #[inline]
    pub fn binary_search(&self, x: &T) -> Result<usize, usize>
    where
        T: Ord,
    {
        self.binary_search_by(|e| e.cmp(x))
    }

    /// Binary 使用比较器函数搜索此排序的 `VecDeque`。
    ///
    /// 比较器函数应实现与基础 `VecDeque` 的排序顺序一致的顺序，并返回指示其参数比所需目标高 `Less`，`Equal` 或 `Greater` 的顺序代码。
    ///
    ///
    /// 如果找到该值，则返回 [`Result::Ok`]，其中包含匹配元素的索引。如果有多个匹配项，则可以返回任何一个匹配项。
    /// 如果找不到该值，则返回 [`Result::Err`]，其中包含在保留排序顺序的同时可以在其中插入匹配元素的索引。
    ///
    /// 另请参见 [`binary_search`]，[`binary_search_by_key`] 和 [`partition_point`]。
    ///
    /// [`binary_search`]: VecDeque::binary_search
    /// [`binary_search_by_key`]: VecDeque::binary_search_by_key
    /// [`partition_point`]: VecDeque::partition_point
    ///
    /// # Examples
    ///
    /// 查找一系列四个元素。找到第一个，具有唯一确定的位置; 找不到第二和第三个; 第四个可以匹配 `[1, 4]` 中的任何位置。
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let deque: VecDeque<_> = vec![0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55].into();
    ///
    /// assert_eq!(deque.binary_search_by(|x| x.cmp(&13)),  Ok(9));
    /// assert_eq!(deque.binary_search_by(|x| x.cmp(&4)),   Err(7));
    /// assert_eq!(deque.binary_search_by(|x| x.cmp(&100)), Err(13));
    /// let r = deque.binary_search_by(|x| x.cmp(&1));
    /// assert!(matches!(r, Ok(1..=4)));
    /// ```
    ///
    ///
    ///
    ///
    ///
    ///
    ///
    #[stable(feature = "vecdeque_binary_search", since = "1.54.0")]
    pub fn binary_search_by<'a, F>(&'a self, mut f: F) -> Result<usize, usize>
    where
        F: FnMut(&'a T) -> Ordering,
    {
        let (front, back) = self.as_slices();
        let cmp_back = back.first().map(|elem| f(elem));

        if let Some(Ordering::Equal) = cmp_back {
            Ok(front.len())
        } else if let Some(Ordering::Less) = cmp_back {
            back.binary_search_by(f).map(|idx| idx + front.len()).map_err(|idx| idx + front.len())
        } else {
            front.binary_search_by(f)
        }
    }

    /// Binary 使用关键字提取函数搜索此排序的 `VecDeque`。
    ///
    /// 假设 `VecDeque` 是按键排序的，例如 [`make_contiguous().sort_by_key()`] 使用相同的键提取函数。
    ///
    /// 如果找到该值，则返回 [`Result::Ok`]，其中包含匹配元素的索引。
    /// 如果有多个匹配项，则可以返回任何一个匹配项。
    /// 如果找不到该值，则返回 [`Result::Err`]，其中包含在保留排序顺序的同时可以在其中插入匹配元素的索引。
    ///
    ///
    /// 另请参见 [`binary_search`]，[`binary_search_by`] 和 [`partition_point`]。
    ///
    /// [`make_contiguous().sort_by_key()`]: VecDeque::make_contiguous
    /// [`binary_search`]: VecDeque::binary_search
    /// [`binary_search_by`]: VecDeque::binary_search_by
    /// [`partition_point`]: VecDeque::partition_point
    ///
    /// # Examples
    ///
    /// 在成对的切片中按其第二个元素排序的一系列四个元素中查找。
    /// 找到第一个，具有唯一确定的位置; 找不到第二和第三个; 第四个可以匹配 `[1, 4]` 中的任何位置。
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let deque: VecDeque<_> = vec![(0, 0), (2, 1), (4, 1), (5, 1),
    ///          (3, 1), (1, 2), (2, 3), (4, 5), (5, 8), (3, 13),
    ///          (1, 21), (2, 34), (4, 55)].into();
    ///
    /// assert_eq!(deque.binary_search_by_key(&13, |&(a, b)| b),  Ok(9));
    /// assert_eq!(deque.binary_search_by_key(&4, |&(a, b)| b),   Err(7));
    /// assert_eq!(deque.binary_search_by_key(&100, |&(a, b)| b), Err(13));
    /// let r = deque.binary_search_by_key(&1, |&(a, b)| b);
    /// assert!(matches!(r, Ok(1..=4)));
    /// ```
    ///
    ///
    ///
    ///
    #[stable(feature = "vecdeque_binary_search", since = "1.54.0")]
    #[inline]
    pub fn binary_search_by_key<'a, B, F>(&'a self, b: &B, mut f: F) -> Result<usize, usize>
    where
        F: FnMut(&'a T) -> B,
        B: Ord,
    {
        self.binary_search_by(|k| f(k).cmp(b))
    }

    /// 根据给定的谓词返回分区点的索引 (第二个分区的第一个元素的索引)。
    ///
    /// 假定双端队列根据给定的谓词进行了分区。
    /// 这意味着谓词返回 true 的所有元素都在双端队列的开头，而谓词返回 false 的所有元素都在末尾。
    ///
    /// 例如，[7, 15, 3, 5, 4, 12, 6] 在谓词 `x % 2 != 0` 下进行了分区 (所有的奇数都在开头，所有的偶数都在结尾)。
    ///
    /// 如果此双端队列未分区，则返回的结果是未指定且无意义的，因为此方法执行一种二分查找。
    ///
    /// 另请参见 [`binary_search`]，[`binary_search_by`] 和 [`binary_search_by_key`]。
    ///
    /// [`binary_search`]: VecDeque::binary_search
    /// [`binary_search_by`]: VecDeque::binary_search_by
    /// [`binary_search_by_key`]: VecDeque::binary_search_by_key
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let deque: VecDeque<_> = vec![1, 2, 3, 3, 5, 6, 7].into();
    /// let i = deque.partition_point(|&x| x < 5);
    ///
    /// assert_eq!(i, 4);
    /// assert!(deque.iter().take(i).all(|&x| x < 5));
    /// assert!(deque.iter().skip(i).all(|&x| !(x < 5)));
    /// ```
    ///
    ///
    ///
    #[stable(feature = "vecdeque_binary_search", since = "1.54.0")]
    pub fn partition_point<P>(&self, mut pred: P) -> usize
    where
        P: FnMut(&T) -> bool,
    {
        let (front, back) = self.as_slices();

        if let Some(true) = back.first().map(|v| pred(v)) {
            back.partition_point(pred) + front.len()
        } else {
            front.partition_point(pred)
        }
    }
}

impl<T: Clone> VecDeque<T> {
    /// 通过从后面移除多余的元素或在后面附加 `value` 的克隆，就地修改 `VecDeque`，以使 `len()` 等于 new_len。
    ///
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// let mut buf = VecDeque::new();
    /// buf.push_back(5);
    /// buf.push_back(10);
    /// buf.push_back(15);
    /// assert_eq!(buf, [5, 10, 15]);
    ///
    /// buf.resize(2, 0);
    /// assert_eq!(buf, [5, 10]);
    ///
    /// buf.resize(5, 20);
    /// assert_eq!(buf, [5, 10, 20, 20, 20]);
    /// ```
    ///
    #[stable(feature = "deque_extras", since = "1.16.0")]
    pub fn resize(&mut self, new_len: usize, value: T) {
        self.resize_with(new_len, || value.clone());
    }
}

/// 返回给定逻辑元素索引的基础缓冲区中的索引。
#[inline]
fn wrap_index(index: usize, size: usize) -> usize {
    // 大小始终是 2 的幂
    debug_assert!(size.is_power_of_two());
    index & (size - 1)
}

/// 计算要在缓冲区中读取的剩余元素数
#[inline]
fn count(tail: usize, head: usize, size: usize) -> usize {
    // 大小始终是 2 的幂
    (head.wrapping_sub(tail)) & (size - 1)
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<A: PartialEq> PartialEq for VecDeque<A> {
    fn eq(&self, other: &VecDeque<A>) -> bool {
        if self.len() != other.len() {
            return false;
        }
        let (sa, sb) = self.as_slices();
        let (oa, ob) = other.as_slices();
        if sa.len() == oa.len() {
            sa == oa && sb == ob
        } else if sa.len() < oa.len() {
            // 始终可分为三部分，例如:
            // self:  [a b c|d e f] other: [0 1 2 3|4 5] front = 3, mid = 1, [a b c] == [0 1 2] && [d] == [3] && [e f] == [4 5]
            //
            //
            //
            let front = sa.len();
            let mid = oa.len() - front;

            let (oa_front, oa_mid) = oa.split_at(front);
            let (sb_mid, sb_back) = sb.split_at(mid);
            debug_assert_eq!(sa.len(), oa_front.len());
            debug_assert_eq!(sb_mid.len(), oa_mid.len());
            debug_assert_eq!(sb_back.len(), ob.len());
            sa == oa_front && sb_mid == oa_mid && sb_back == ob
        } else {
            let front = oa.len();
            let mid = sa.len() - front;

            let (sa_front, sa_mid) = sa.split_at(front);
            let (ob_mid, ob_back) = ob.split_at(mid);
            debug_assert_eq!(sa_front.len(), oa.len());
            debug_assert_eq!(sa_mid.len(), ob_mid.len());
            debug_assert_eq!(sb.len(), ob_back.len());
            sa_front == oa && sa_mid == ob_mid && sb == ob_back
        }
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<A: Eq> Eq for VecDeque<A> {}

__impl_slice_eq1! { [] VecDeque<A>, Vec<B>, }
__impl_slice_eq1! { [] VecDeque<A>, &[B], }
__impl_slice_eq1! { [] VecDeque<A>, &mut [B], }
__impl_slice_eq1! { [const N: usize] VecDeque<A>, [B; N], }
__impl_slice_eq1! { [const N: usize] VecDeque<A>, &[B; N], }
__impl_slice_eq1! { [const N: usize] VecDeque<A>, &mut [B; N], }

#[stable(feature = "rust1", since = "1.0.0")]
impl<A: PartialOrd> PartialOrd for VecDeque<A> {
    fn partial_cmp(&self, other: &VecDeque<A>) -> Option<Ordering> {
        self.iter().partial_cmp(other.iter())
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<A: Ord> Ord for VecDeque<A> {
    #[inline]
    fn cmp(&self, other: &VecDeque<A>) -> Ordering {
        self.iter().cmp(other.iter())
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<A: Hash> Hash for VecDeque<A> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.len().hash(state);
        // 在 as_slices 方法返回的切片上无法使用 Hash::hash_slice，因为它们的长度会因其他双端队列相同而有所不同。
        //
        //
        // Hasher 仅保证对其方法的完全相同的调用集是等效的。
        //
        //
        self.iter().for_each(|elem| elem.hash(state));
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<A> Index<usize> for VecDeque<A> {
    type Output = A;

    #[inline]
    fn index(&self, index: usize) -> &A {
        self.get(index).expect("Out of bounds access")
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<A> IndexMut<usize> for VecDeque<A> {
    #[inline]
    fn index_mut(&mut self, index: usize) -> &mut A {
        self.get_mut(index).expect("Out of bounds access")
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<A> FromIterator<A> for VecDeque<A> {
    fn from_iter<T: IntoIterator<Item = A>>(iter: T) -> VecDeque<A> {
        let iterator = iter.into_iter();
        let (lower, _) = iterator.size_hint();
        let mut deq = VecDeque::with_capacity(lower);
        deq.extend(iterator);
        deq
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<T> IntoIterator for VecDeque<T> {
    type Item = T;
    type IntoIter = IntoIter<T>;

    /// 将 `VecDeque` 消费为从前到后的迭代器，按值产生元素。
    ///
    fn into_iter(self) -> IntoIter<T> {
        IntoIter { inner: self }
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<'a, T> IntoIterator for &'a VecDeque<T> {
    type Item = &'a T;
    type IntoIter = Iter<'a, T>;

    fn into_iter(self) -> Iter<'a, T> {
        self.iter()
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<'a, T> IntoIterator for &'a mut VecDeque<T> {
    type Item = &'a mut T;
    type IntoIter = IterMut<'a, T>;

    fn into_iter(self) -> IterMut<'a, T> {
        self.iter_mut()
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<A> Extend<A> for VecDeque<A> {
    fn extend<T: IntoIterator<Item = A>>(&mut self, iter: T) {
        // 此函数应在道德上等同于:
        //
        //      for item in iter.into_iter() {
        //          self.push_back(item);
        //      }
        let mut iter = iter.into_iter();
        while let Some(element) = iter.next() {
            if self.len() == self.capacity() {
                let (lower, _) = iter.size_hint();
                self.reserve(lower.saturating_add(1));
            }

            let head = self.head;
            self.head = self.wrap_add(self.head, 1);
            unsafe {
                self.buffer_write(head, element);
            }
        }
    }

    #[inline]
    fn extend_one(&mut self, elem: A) {
        self.push_back(elem);
    }

    #[inline]
    fn extend_reserve(&mut self, additional: usize) {
        self.reserve(additional);
    }
}

#[stable(feature = "extend_ref", since = "1.2.0")]
impl<'a, T: 'a + Copy> Extend<&'a T> for VecDeque<T> {
    fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
        self.extend(iter.into_iter().cloned());
    }

    #[inline]
    fn extend_one(&mut self, &elem: &T) {
        self.push_back(elem);
    }

    #[inline]
    fn extend_reserve(&mut self, additional: usize) {
        self.reserve(additional);
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<T: fmt::Debug> fmt::Debug for VecDeque<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_list().entries(self).finish()
    }
}

#[stable(feature = "vecdeque_vec_conversions", since = "1.10.0")]
impl<T> From<Vec<T>> for VecDeque<T> {
    /// 将 [`Vec<T>`] 变成 [`VecDeque<T>`]。
    ///
    /// [`Vec<T>`]: crate::vec::Vec
    /// [`VecDeque<T>`]: crate::collections::VecDeque
    ///
    /// 这样可以避免在可能的情况下进行重新分配，但是这样做的条件很严格，并且随时可能更改，因此除非 `Vec<T>` 来自 `From<VecDeque<T>>` 并且尚未重新分配，否则不应依赖它。
    ///
    ///
    fn from(mut other: Vec<T>) -> Self {
        let len = other.len();
        if mem::size_of::<T>() == 0 {
            // 没有实际分配给 ZST 来担心容量的问题，但是 `VecDeque` 不能处理比 `Vec` 更长的长度。
            //
            assert!(len < MAXIMUM_ZST_CAPACITY, "capacity overflow");
        } else {
            // 如果容量不是 2 的幂，太小或没有至少一个可用空间，则需要调整大小。
            // 我们在它仍在 `Vec` 中时执行此操作，所以该项会因为 panic 而被丢弃。
            //
            let min_cap = cmp::max(MINIMUM_CAPACITY, len) + 1;
            let cap = cmp::max(min_cap, other.capacity()).next_power_of_two();
            if other.capacity() != cap {
                other.reserve_exact(cap - len);
            }
        }

        unsafe {
            let (other_buf, len, capacity) = other.into_raw_parts();
            let buf = RawVec::from_raw_parts(other_buf, capacity);
            VecDeque { tail: 0, head: len, buf }
        }
    }
}

#[stable(feature = "vecdeque_vec_conversions", since = "1.10.0")]
impl<T> From<VecDeque<T>> for Vec<T> {
    /// 将 [`VecDeque<T>`] 变成 [`Vec<T>`]。
    ///
    /// [`Vec<T>`]: crate::vec::Vec
    /// [`VecDeque<T>`]: crate::collections::VecDeque
    ///
    /// 这永远不需要重新分配，但是如果循环缓冲区恰好不在分配开始时，则确实需要进行 *O*(*n*) 数据移动。
    ///
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::VecDeque;
    ///
    /// // 这是 *O*(1)。
    /// let deque: VecDeque<_> = (1..5).collect();
    /// let ptr = deque.as_slices().0.as_ptr();
    /// let vec = Vec::from(deque);
    /// assert_eq!(vec, [1, 2, 3, 4]);
    /// assert_eq!(vec.as_ptr(), ptr);
    ///
    /// // 这一项需要重新整理数据。
    /// let mut deque: VecDeque<_> = (1..5).collect();
    /// deque.push_front(9);
    /// deque.push_front(8);
    /// let ptr = deque.as_slices().1.as_ptr();
    /// let vec = Vec::from(deque);
    /// assert_eq!(vec, [8, 9, 1, 2, 3, 4]);
    /// assert_eq!(vec.as_ptr(), ptr);
    /// ```
    fn from(mut other: VecDeque<T>) -> Self {
        other.make_contiguous();

        unsafe {
            let other = ManuallyDrop::new(other);
            let buf = other.buf.ptr();
            let len = other.len();
            let cap = other.cap();

            if other.tail != 0 {
                ptr::copy(buf.add(other.tail), buf, len);
            }
            Vec::from_raw_parts(buf, len, cap)
        }
    }
}