use core::fmt::{self, Debug};
use core::marker::PhantomData;
use core::mem;

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

use super::super::borrow::DormantMutRef;
use super::super::node::{marker, Handle, NodeRef};
use super::BTreeMap;

use Entry::*;

/// map 中单个条目的视图，该条目可能是空的或被已占用。
///
/// `enum` 是根据 [`BTreeMap`] 上的 [`entry`] 方法构造的。
///
/// [`entry`]: BTreeMap::entry
#[stable(feature = "rust1", since = "1.0.0")]
#[cfg_attr(not(test), rustc_diagnostic_item = "BTreeEntry")]
pub enum Entry<
    'a,
    K: 'a,
    V: 'a,
    #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + Clone = Global,
> {
    /// 一个空的条目。
    #[stable(feature = "rust1", since = "1.0.0")]
    Vacant(#[stable(feature = "rust1", since = "1.0.0")] VacantEntry<'a, K, V, A>),

    /// 一个被占用的条目。
    #[stable(feature = "rust1", since = "1.0.0")]
    Occupied(#[stable(feature = "rust1", since = "1.0.0")] OccupiedEntry<'a, K, V, A>),
}

#[stable(feature = "debug_btree_map", since = "1.12.0")]
impl<K: Debug + Ord, V: Debug, A: Allocator + Clone> Debug for Entry<'_, K, V, A> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match *self {
            Vacant(ref v) => f.debug_tuple("Entry").field(v).finish(),
            Occupied(ref o) => f.debug_tuple("Entry").field(o).finish(),
        }
    }
}

/// `BTreeMap` 中空条目的视图。
/// 它是 [`Entry`] 枚举的一部分。
#[stable(feature = "rust1", since = "1.0.0")]
pub struct VacantEntry<
    'a,
    K,
    V,
    #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + Clone = Global,
> {
    pub(super) key: K,
    /// `None` 用于没有 root 的 (empty) map
    pub(super) handle: Option<Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>>,
    pub(super) dormant_map: DormantMutRef<'a, BTreeMap<K, V, A>>,

    /// BTreeMap 将比 IntoIter 活得长，所以我们不关心 `alloc` 的丢弃顺序。
    pub(super) alloc: A,

    // 在 `K` 和 `V` 中保持不变
    pub(super) _marker: PhantomData<&'a mut (K, V)>,
}

#[stable(feature = "debug_btree_map", since = "1.12.0")]
impl<K: Debug + Ord, V, A: Allocator + Clone> Debug for VacantEntry<'_, K, V, A> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_tuple("VacantEntry").field(self.key()).finish()
    }
}

/// `BTreeMap` 中已占用条目的视图。
/// 它是 [`Entry`] 枚举的一部分。
#[stable(feature = "rust1", since = "1.0.0")]
pub struct OccupiedEntry<
    'a,
    K,
    V,
    #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + Clone = Global,
> {
    pub(super) handle: Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::KV>,
    pub(super) dormant_map: DormantMutRef<'a, BTreeMap<K, V, A>>,

    /// BTreeMap 将比 IntoIter 活得长，所以我们不关心 `alloc` 的丢弃顺序。
    pub(super) alloc: A,

    // 在 `K` 和 `V` 中保持不变
    pub(super) _marker: PhantomData<&'a mut (K, V)>,
}

#[stable(feature = "debug_btree_map", since = "1.12.0")]
impl<K: Debug + Ord, V: Debug, A: Allocator + Clone> Debug for OccupiedEntry<'_, K, V, A> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("OccupiedEntry").field("key", self.key()).field("value", self.get()).finish()
    }
}

/// 当键已经存在时，由 [`try_insert`](BTreeMap::try_insert) 返回的错误。
///
/// 包含占用的条目和未插入的值。
#[unstable(feature = "map_try_insert", issue = "82766")]
pub struct OccupiedError<'a, K: 'a, V: 'a, A: Allocator + Clone = Global> {
    /// map 中已被占用的条目。
    pub entry: OccupiedEntry<'a, K, V, A>,
    /// 未插入的值，因为该条目已被占用。
    pub value: V,
}

#[unstable(feature = "map_try_insert", issue = "82766")]
impl<K: Debug + Ord, V: Debug, A: Allocator + Clone> Debug for OccupiedError<'_, K, V, A> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("OccupiedError")
            .field("key", self.entry.key())
            .field("old_value", self.entry.get())
            .field("new_value", &self.value)
            .finish()
    }
}

#[unstable(feature = "map_try_insert", issue = "82766")]
impl<'a, K: Debug + Ord, V: Debug, A: Allocator + Clone> fmt::Display
    for OccupiedError<'a, K, V, A>
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(
            f,
            "failed to insert {:?}, key {:?} already exists with value {:?}",
            self.value,
            self.entry.key(),
            self.entry.get(),
        )
    }
}

#[unstable(feature = "map_try_insert", issue = "82766")]
impl<'a, K: core::fmt::Debug + Ord, V: core::fmt::Debug> core::error::Error
    for crate::collections::btree_map::OccupiedError<'a, K, V>
{
    #[allow(deprecated)]
    fn description(&self) -> &str {
        "key already exists"
    }
}

impl<'a, K: Ord, V, A: Allocator + Clone> Entry<'a, K, V, A> {
    /// 如果为空，则通过插入默认值来确保该值在条目中，并返回对条目中值的可变引用。
    ///
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::BTreeMap;
    ///
    /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
    /// map.entry("poneyland").or_insert(12);
    ///
    /// assert_eq!(map["poneyland"], 12);
    /// ```
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn or_insert(self, default: V) -> &'a mut V {
        match self {
            Occupied(entry) => entry.into_mut(),
            Vacant(entry) => entry.insert(default),
        }
    }

    /// 如果为空，则通过插入默认函数的结果来确保该值在条目中，并返回对条目中值的可变引用。
    ///
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::BTreeMap;
    ///
    /// let mut map: BTreeMap<&str, String> = BTreeMap::new();
    /// let s = "hoho".to_string();
    ///
    /// map.entry("poneyland").or_insert_with(|| s);
    ///
    /// assert_eq!(map["poneyland"], "hoho".to_string());
    /// ```
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
        match self {
            Occupied(entry) => entry.into_mut(),
            Vacant(entry) => entry.insert(default()),
        }
    }

    /// 如果为空，则通过插入默认函数的结果，确保值在条目中。
    /// 通过为 `.entry(key)` 方法调用期间移动的键提供默认函数引用，此方法可以生成用于插入的键派生值。
    ///
    ///
    /// 提供了对已移动键的引用，因此不需要克隆或复制键，这与 `.or_insert_with(|| ... )` 不同。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::BTreeMap;
    ///
    /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
    ///
    /// map.entry("poneyland").or_insert_with_key(|key| key.chars().count());
    ///
    /// assert_eq!(map["poneyland"], 9);
    /// ```
    ///
    #[inline]
    #[stable(feature = "or_insert_with_key", since = "1.50.0")]
    pub fn or_insert_with_key<F: FnOnce(&K) -> V>(self, default: F) -> &'a mut V {
        match self {
            Occupied(entry) => entry.into_mut(),
            Vacant(entry) => {
                let value = default(entry.key());
                entry.insert(value)
            }
        }
    }

    /// 返回此条目的键的引用。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::BTreeMap;
    ///
    /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
    /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
    /// ```
    #[stable(feature = "map_entry_keys", since = "1.10.0")]
    pub fn key(&self) -> &K {
        match *self {
            Occupied(ref entry) => entry.key(),
            Vacant(ref entry) => entry.key(),
        }
    }

    /// 在任何潜在的插入 map 之前，提供对占用条目的就地可变访问。
    ///
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::BTreeMap;
    ///
    /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
    ///
    /// map.entry("poneyland")
    ///    .and_modify(|e| { *e += 1 })
    ///    .or_insert(42);
    /// assert_eq!(map["poneyland"], 42);
    ///
    /// map.entry("poneyland")
    ///    .and_modify(|e| { *e += 1 })
    ///    .or_insert(42);
    /// assert_eq!(map["poneyland"], 43);
    /// ```
    #[stable(feature = "entry_and_modify", since = "1.26.0")]
    pub fn and_modify<F>(self, f: F) -> Self
    where
        F: FnOnce(&mut V),
    {
        match self {
            Occupied(mut entry) => {
                f(entry.get_mut());
                Occupied(entry)
            }
            Vacant(entry) => Vacant(entry),
        }
    }
}

impl<'a, K: Ord, V: Default, A: Allocator + Clone> Entry<'a, K, V, A> {
    #[stable(feature = "entry_or_default", since = "1.28.0")]
    /// 如果为空，则通过插入默认值来确保值在条目中，并向条目中的值返回变量引用。
    ///
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::BTreeMap;
    ///
    /// let mut map: BTreeMap<&str, Option<usize>> = BTreeMap::new();
    /// map.entry("poneyland").or_default();
    ///
    /// assert_eq!(map["poneyland"], None);
    /// ```
    pub fn or_default(self) -> &'a mut V {
        match self {
            Occupied(entry) => entry.into_mut(),
            Vacant(entry) => entry.insert(Default::default()),
        }
    }
}

impl<'a, K: Ord, V, A: Allocator + Clone> VacantEntry<'a, K, V, A> {
    /// 获取对通过 VacantEntry 插入值时将使用的键的引用。
    ///
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::BTreeMap;
    ///
    /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
    /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
    /// ```
    #[stable(feature = "map_entry_keys", since = "1.10.0")]
    pub fn key(&self) -> &K {
        &self.key
    }

    /// 取得键的所有权。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::BTreeMap;
    /// use std::collections::btree_map::Entry;
    ///
    /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
    ///
    /// if let Entry::Vacant(v) = map.entry("poneyland") {
    ///     v.into_key();
    /// }
    /// ```
    #[stable(feature = "map_entry_recover_keys2", since = "1.12.0")]
    pub fn into_key(self) -> K {
        self.key
    }

    /// 用 `VacantEntry` 的键设置条目的值，并返回对它的可变引用。
    ///
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::BTreeMap;
    /// use std::collections::btree_map::Entry;
    ///
    /// let mut map: BTreeMap<&str, u32> = BTreeMap::new();
    ///
    /// if let Entry::Vacant(o) = map.entry("poneyland") {
    ///     o.insert(37);
    /// }
    /// assert_eq!(map["poneyland"], 37);
    /// ```
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn insert(mut self, value: V) -> &'a mut V {
        let out_ptr = match self.handle {
            None => {
                // SAFETY: 还没有树，所以不存在对它的引用。
                let map = unsafe { self.dormant_map.awaken() };
                let mut root = NodeRef::new_leaf(self.alloc.clone());
                let val_ptr = root.borrow_mut().push(self.key, value) as *mut V;
                map.root = Some(root.forget_type());
                map.length = 1;
                val_ptr
            }
            Some(handle) => {
                let new_handle =
                    handle.insert_recursing(self.key, value, self.alloc.clone(), |ins| {
                        drop(ins.left);
                        // SAFETY: 推送新的根节点不会使现有节点的句柄无效。
                        //
                        let map = unsafe { self.dormant_map.reborrow() };
                        let root = map.root.as_mut().unwrap(); // 与 ins.left 相同
                        root.push_internal_level(self.alloc).push(ins.kv.0, ins.kv.1, ins.right)
                    });

                // 获取指向值的指针
                let val_ptr = new_handle.into_val_mut();

                // SAFETY: 我们已经消耗了 self.handle。
                let map = unsafe { self.dormant_map.awaken() };
                map.length += 1;
                val_ptr
            }
        };

        // 现在我们已经完成了使用借来的引用完成了树的生长，解除对它的一部分的指针的引用，这是我们在开发过程中得到的。
        //
        unsafe { &mut *out_ptr }
    }
}

impl<'a, K: Ord, V, A: Allocator + Clone> OccupiedEntry<'a, K, V, A> {
    /// 获取条目中键的引用。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::BTreeMap;
    ///
    /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
    /// map.entry("poneyland").or_insert(12);
    /// assert_eq!(map.entry("poneyland").key(), &"poneyland");
    /// ```
    #[must_use]
    #[stable(feature = "map_entry_keys", since = "1.10.0")]
    pub fn key(&self) -> &K {
        self.handle.reborrow().into_kv().0
    }

    /// 从 map 获取键和值的所有权。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::BTreeMap;
    /// use std::collections::btree_map::Entry;
    ///
    /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
    /// map.entry("poneyland").or_insert(12);
    ///
    /// if let Entry::Occupied(o) = map.entry("poneyland") {
    ///     // 我们从 map 中删除了这个条目。
    ///     o.remove_entry();
    /// }
    ///
    /// // 如果现在尝试获取该值，它将为 panic：
    /// // println!("{}", map["poneyland"]);
    /// ```
    #[stable(feature = "map_entry_recover_keys2", since = "1.12.0")]
    pub fn remove_entry(self) -> (K, V) {
        self.remove_kv()
    }

    /// 获取条目中值的引用。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::BTreeMap;
    /// use std::collections::btree_map::Entry;
    ///
    /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
    /// map.entry("poneyland").or_insert(12);
    ///
    /// if let Entry::Occupied(o) = map.entry("poneyland") {
    ///     assert_eq!(o.get(), &12);
    /// }
    /// ```
    #[must_use]
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn get(&self) -> &V {
        self.handle.reborrow().into_kv().1
    }

    /// 获取条目中的值的可变引用。
    ///
    /// 如果您需要引用可能比销毁 `Entry` 值还长的 `OccupiedEntry`，请参阅 [`into_mut`]。
    ///
    ///
    /// [`into_mut`]: OccupiedEntry::into_mut
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::BTreeMap;
    /// use std::collections::btree_map::Entry;
    ///
    /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
    /// map.entry("poneyland").or_insert(12);
    ///
    /// assert_eq!(map["poneyland"], 12);
    /// if let Entry::Occupied(mut o) = map.entry("poneyland") {
    ///     *o.get_mut() += 10;
    ///     assert_eq!(*o.get(), 22);
    ///
    ///     // 我们可以多次使用同一个 Entry。
    ///     *o.get_mut() += 2;
    /// }
    /// assert_eq!(map["poneyland"], 24);
    /// ```
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn get_mut(&mut self) -> &mut V {
        self.handle.kv_mut().1
    }

    /// 将条目转换为其值的可变引用。
    ///
    /// 如果需要多次引用 `OccupiedEntry`，请参见 [`get_mut`]。
    ///
    /// [`get_mut`]: OccupiedEntry::get_mut
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::BTreeMap;
    /// use std::collections::btree_map::Entry;
    ///
    /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
    /// map.entry("poneyland").or_insert(12);
    ///
    /// assert_eq!(map["poneyland"], 12);
    /// if let Entry::Occupied(o) = map.entry("poneyland") {
    ///     *o.into_mut() += 10;
    /// }
    /// assert_eq!(map["poneyland"], 22);
    /// ```
    #[must_use = "`self` will be dropped if the result is not used"]
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn into_mut(self) -> &'a mut V {
        self.handle.into_val_mut()
    }

    /// 使用 `OccupiedEntry` 键设置条目的值，并返回条目的旧值。
    ///
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::BTreeMap;
    /// use std::collections::btree_map::Entry;
    ///
    /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
    /// map.entry("poneyland").or_insert(12);
    ///
    /// if let Entry::Occupied(mut o) = map.entry("poneyland") {
    ///     assert_eq!(o.insert(15), 12);
    /// }
    /// assert_eq!(map["poneyland"], 15);
    /// ```
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn insert(&mut self, value: V) -> V {
        mem::replace(self.get_mut(), value)
    }

    /// 从 map 中获取条目的值，并将其返回。
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::BTreeMap;
    /// use std::collections::btree_map::Entry;
    ///
    /// let mut map: BTreeMap<&str, usize> = BTreeMap::new();
    /// map.entry("poneyland").or_insert(12);
    ///
    /// if let Entry::Occupied(o) = map.entry("poneyland") {
    ///     assert_eq!(o.remove(), 12);
    /// }
    /// // 如果我们尝试获得 `poneyland` 的值，则它将为 panic：
    /// // println!("{}", map["poneyland"]);
    /// ```
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn remove(self) -> V {
        self.remove_kv().1
    }

    // `remove_entry` 的主体，可能是分开的，因为名称反映了返回的对。
    pub(super) fn remove_kv(self) -> (K, V) {
        let mut emptied_internal_root = false;
        let (old_kv, _) =
            self.handle.remove_kv_tracking(|| emptied_internal_root = true, self.alloc.clone());
        // SAFETY: 我们消耗了中间根借用，`self.handle`。
        let map = unsafe { self.dormant_map.awaken() };
        map.length -= 1;
        if emptied_internal_root {
            let root = map.root.as_mut().unwrap();
            root.pop_internal_level(self.alloc);
        }
        old_kv
    }
}