use core::borrow::Borrow;
use core::cmp::Ordering;
use core::ops::{Bound, RangeBounds};

use super::node::{marker, ForceResult::*, Handle, NodeRef};

use SearchBound::*;
use SearchResult::*;

pub enum SearchBound<T> {
    /// 就像 `Bound::Included(T)` 一样，要寻找的包容性范围。
    Included(T),
    /// 就像 `Bound::Excluded(T)` 一样，需要寻找的专有绑定。
    Excluded(T),
    /// 就像 `Bound::Unbounded` 一样，是一个无条件的包含范围。
    AllIncluded,
    /// 无条件排他绑定。
    AllExcluded,
}

impl<T> SearchBound<T> {
    pub fn from_range(range_bound: Bound<T>) -> Self {
        match range_bound {
            Bound::Included(t) => Included(t),
            Bound::Excluded(t) => Excluded(t),
            Bound::Unbounded => AllIncluded,
        }
    }
}

pub enum SearchResult<BorrowType, K, V, FoundType, GoDownType> {
    Found(Handle<NodeRef<BorrowType, K, V, FoundType>, marker::KV>),
    GoDown(Handle<NodeRef<BorrowType, K, V, GoDownType>, marker::Edge>),
}

pub enum IndexResult {
    KV(usize),
    Edge(usize),
}

impl<BorrowType: marker::BorrowType, K, V> NodeRef<BorrowType, K, V, marker::LeafOrInternal> {
    /// 递归地在以该节点为首的 (子) 树中查找给定的键。
    /// 返回带有匹配 KV 句柄的 `Found` (如果有)。
    /// 否则，返回 `GoDown`，该 `GoDown` 具有键所属的叶子 edge 的句柄。
    ///
    /// 仅当按键对树进行排序 (如 `BTreeMap` 中的树) 时，结果才有意义。
    ///
    pub fn search_tree<Q: ?Sized>(
        mut self,
        key: &Q,
    ) -> SearchResult<BorrowType, K, V, marker::LeafOrInternal, marker::Leaf>
    where
        Q: Ord,
        K: Borrow<Q>,
    {
        loop {
            self = match self.search_node(key) {
                Found(handle) => return Found(handle),
                GoDown(handle) => match handle.force() {
                    Leaf(leaf) => return GoDown(leaf),
                    Internal(internal) => internal.descend(),
                },
            }
        }
    }

    /// 下降到最近的节点，其中与范围下限匹配的 edge 与匹配上限的 edge 不同，即，具有至少一个包含在范围内的键的最近节点。
    ///
    /// 如果找到，则返回带有该节点的 `Ok`，该节点中限定范围的严格递增的一对边缘索引，以及在该节点是内部节点的情况下，在子节点中继续搜索的相应一对边界。
    ///
    ///
    /// 如果未找到，则返回 `Err`，其叶 edge 匹配整个范围。
    ///
    /// 作为诊断服务，如果范围指定不可能的界限，则会发生 panics。
    ///
    /// 仅当树通过键排序时，结果才有意义。
    ///
    ///
    ///
    ///
    ///
    pub fn search_tree_for_bifurcation<'r, Q: ?Sized, R>(
        mut self,
        range: &'r R,
    ) -> Result<
        (
            NodeRef<BorrowType, K, V, marker::LeafOrInternal>,
            usize,
            usize,
            SearchBound<&'r Q>,
            SearchBound<&'r Q>,
        ),
        Handle<NodeRef<BorrowType, K, V, marker::Leaf>, marker::Edge>,
    >
    where
        Q: Ord,
        K: Borrow<Q>,
        R: RangeBounds<Q>,
    {
        // 确定是否正在搜索 map 或集合
        let is_set = <V as super::set_val::IsSetVal>::is_set_val();

        // 应该避免内联这些变量。
        // 我们假设 `range` 所报告的范围保持不变，但是在 (#81138) 调用之间可能会发生对抗性实现。
        let (start, end) = (range.start_bound(), range.end_bound());
        match (start, end) {
            (Bound::Excluded(s), Bound::Excluded(e)) if s == e => {
                if is_set {
                    panic!("range start and end are equal and excluded in BTreeSet")
                } else {
                    panic!("range start and end are equal and excluded in BTreeMap")
                }
            }
            (Bound::Included(s) | Bound::Excluded(s), Bound::Included(e) | Bound::Excluded(e))
                if s > e =>
            {
                if is_set {
                    panic!("range start is greater than range end in BTreeSet")
                } else {
                    panic!("range start is greater than range end in BTreeMap")
                }
            }
            _ => {}
        }
        let mut lower_bound = SearchBound::from_range(start);
        let mut upper_bound = SearchBound::from_range(end);
        loop {
            let (lower_edge_idx, lower_child_bound) = self.find_lower_bound_index(lower_bound);
            let (upper_edge_idx, upper_child_bound) =
                unsafe { self.find_upper_bound_index(upper_bound, lower_edge_idx) };
            if lower_edge_idx < upper_edge_idx {
                return Ok((
                    self,
                    lower_edge_idx,
                    upper_edge_idx,
                    lower_child_bound,
                    upper_child_bound,
                ));
            }
            debug_assert_eq!(lower_edge_idx, upper_edge_idx);
            let common_edge = unsafe { Handle::new_edge(self, lower_edge_idx) };
            match common_edge.force() {
                Leaf(common_edge) => return Err(common_edge),
                Internal(common_edge) => {
                    self = common_edge.descend();
                    lower_bound = lower_child_bound;
                    upper_bound = upper_child_bound;
                }
            }
        }
    }

    /// 在界定范围下限的节点中找到 edge。
    /// 如果 `self` 是内部节点，则还返回用于在匹配子节点中继续搜索的下限。
    ///
    ///
    /// 仅当树通过键排序时，结果才有意义。
    pub fn find_lower_bound_edge<'r, Q>(
        self,
        bound: SearchBound<&'r Q>,
    ) -> (Handle<Self, marker::Edge>, SearchBound<&'r Q>)
    where
        Q: ?Sized + Ord,
        K: Borrow<Q>,
    {
        let (edge_idx, bound) = self.find_lower_bound_index(bound);
        let edge = unsafe { Handle::new_edge(self, edge_idx) };
        (edge, bound)
    }

    /// `find_lower_bound_edge` 的上限克隆。
    pub fn find_upper_bound_edge<'r, Q>(
        self,
        bound: SearchBound<&'r Q>,
    ) -> (Handle<Self, marker::Edge>, SearchBound<&'r Q>)
    where
        Q: ?Sized + Ord,
        K: Borrow<Q>,
    {
        let (edge_idx, bound) = unsafe { self.find_upper_bound_index(bound, 0) };
        let edge = unsafe { Handle::new_edge(self, edge_idx) };
        (edge, bound)
    }
}

impl<BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> {
    /// 在节点中查找给定的键，而无需递归。
    /// 返回带有匹配 KV 句柄的 `Found` (如果有)。
    /// 否则，返回带有 edge 句柄的 `GoDown`，在该句柄中可能找到键 (如果该节点位于内部) 或可以插入键。
    ///
    ///
    /// 仅当按键对树进行排序 (如 `BTreeMap` 中的树) 时，结果才有意义。
    ///
    pub fn search_node<Q: ?Sized>(self, key: &Q) -> SearchResult<BorrowType, K, V, Type, Type>
    where
        Q: Ord,
        K: Borrow<Q>,
    {
        match unsafe { self.find_key_index(key, 0) } {
            IndexResult::KV(idx) => Found(unsafe { Handle::new_kv(self, idx) }),
            IndexResult::Edge(idx) => GoDown(unsafe { Handle::new_edge(self, idx) }),
        }
    }

    /// 返回键 (或等效项) 所在节点中的 KV 索引，或键所属的 edge 索引，从特定索引开始。
    ///
    ///
    /// 仅当按键对树进行排序 (如 `BTreeMap` 中的树) 时，结果才有意义。
    ///
    /// # Safety
    /// `start_index` 必须是节点的有效的边界索引。
    ///
    unsafe fn find_key_index<Q: ?Sized>(&self, key: &Q, start_index: usize) -> IndexResult
    where
        Q: Ord,
        K: Borrow<Q>,
    {
        let node = self.reborrow();
        let keys = node.keys();
        debug_assert!(start_index <= keys.len());
        for (offset, k) in unsafe { keys.get_unchecked(start_index..) }.iter().enumerate() {
            match key.cmp(k.borrow()) {
                Ordering::Greater => {}
                Ordering::Equal => return IndexResult::KV(start_index + offset),
                Ordering::Less => return IndexResult::Edge(start_index + offset),
            }
        }
        IndexResult::Edge(keys.len())
    }

    /// 在界定范围下限的节点中找到 edge 索引。
    /// 如果 `self` 是内部节点，则还返回用于在匹配子节点中继续搜索的下限。
    ///
    ///
    /// 仅当树通过键排序时，结果才有意义。
    fn find_lower_bound_index<'r, Q>(
        &self,
        bound: SearchBound<&'r Q>,
    ) -> (usize, SearchBound<&'r Q>)
    where
        Q: ?Sized + Ord,
        K: Borrow<Q>,
    {
        match bound {
            Included(key) => match unsafe { self.find_key_index(key, 0) } {
                IndexResult::KV(idx) => (idx, AllExcluded),
                IndexResult::Edge(idx) => (idx, bound),
            },
            Excluded(key) => match unsafe { self.find_key_index(key, 0) } {
                IndexResult::KV(idx) => (idx + 1, AllIncluded),
                IndexResult::Edge(idx) => (idx, bound),
            },
            AllIncluded => (0, AllIncluded),
            AllExcluded => (self.len(), AllExcluded),
        }
    }

    /// 上限的 `find_lower_bound_index` 的镜像，使用一个附加参数来跳过键数组的一部分。
    ///
    ///
    /// # Safety
    /// `start_index` 必须是节点的有效的边界索引。
    unsafe fn find_upper_bound_index<'r, Q>(
        &self,
        bound: SearchBound<&'r Q>,
        start_index: usize,
    ) -> (usize, SearchBound<&'r Q>)
    where
        Q: ?Sized + Ord,
        K: Borrow<Q>,
    {
        match bound {
            Included(key) => match unsafe { self.find_key_index(key, start_index) } {
                IndexResult::KV(idx) => (idx + 1, AllExcluded),
                IndexResult::Edge(idx) => (idx, bound),
            },
            Excluded(key) => match unsafe { self.find_key_index(key, start_index) } {
                IndexResult::KV(idx) => (idx, AllIncluded),
                IndexResult::Edge(idx) => (idx, bound),
            },
            AllIncluded => (self.len(), AllIncluded),
            AllExcluded => (start_index, AllExcluded),
        }
    }
}