/// # Examples
/// ```rust
/// use hicollections::{RbTree, RbTreeNode, rbtree};
/// use std::mem::MaybeUninit;
/// use std::cmp::{PartialEq, PartialOrd, Ord, Ordering};
/// use std::ptr;
/// use std::borrow::Borrow;
///
/// struct Foo {
///     val: i32,
///     node: RbTreeNode,
/// }
///
/// // Foo本身无需支持Ord Trait
/// impl Borrow<i32> for Foo {
///     fn borrow(&self) -> &i32 {
///         &self.val
///     }
/// }
///
/// let mut tree = rbtree!(Foo, node);
///
/// let mut foos: [Foo; 100] = unsafe { MaybeUninit::uninit().assume_init() };
///
/// for (n, foo) in foos.iter_mut().enumerate() {
///     foo.val = n as i32;
///     unsafe { ptr::write(&mut foo.node, RbTreeNode::new()) };
///     assert!(unsafe { tree.insert_borrow::<i32>(foo, false) }.is_some());
/// };
///
/// assert!(!tree.empty());
/// assert_eq!(tree.first().unwrap().val, 0);
/// assert_eq!(tree.last().unwrap().val, 99);
///
/// for (n, foo) in tree.iter().enumerate() {
///     assert_eq!(foo.val, n as i32);
/// };
///
/// for (n, foo) in tree.iter().rev().enumerate() {
///     assert_eq!(99 - foo.val, n as i32);
/// };
///
/// assert_eq!(tree.iter().count(), foos.iter().count());
/// assert_eq!(tree.iter().rev().count(), foos.iter().count());
///
/// for foo in &foos {
///     let found = tree.find(&foo.val);
///     assert!(found.is_some());
///     assert!(ptr::eq(found.unwrap(), foo));
/// };
///
/// for foo in &foos {
///     let removed = tree.remove(&foo.val);
///     assert!(removed.is_some());
///     assert!(ptr::eq(removed.unwrap(), foo));
/// };
///
/// assert!(tree.empty());
/// assert!(tree.first().is_none());
/// assert!(tree.last().is_none());
///
/// ```
///

use crate::Link;
use core::borrow::Borrow;
use core::cell::UnsafeCell;
use core::cmp::{Ord, Ordering};
use core::debug_assert;
use core::marker::{PhantomData, PhantomPinned};
use core::ops::{
    Bound::{self, Excluded, Included, Unbounded},
    RangeBounds,
};
use core::ops::{Deref, DerefMut};
use core::ptr::{self, NonNull};

/// 方便构造一个RbTree.
/// ```rust
/// use hicollections::{rbtree, RbTree, RbTreeNode};
/// let tree: RbTree<RbTreeNode> = rbtree!();
/// struct Foo {
///     val: i32,
///     node: RbTreeNode,
/// }
/// let tree: RbTree<Foo> = rbtree!(Foo, node);
/// ```
#[macro_export]
macro_rules! rbtree {
    ($type: ty, $($mem: ident).*) => {
        $crate::RbTree::<$type>::new(|node| unsafe {
            ::core::ptr::addr_of!((*node).$($mem).*)
        })
    };
    () => {
        $crate::RbTree::<RbTreeNode>::new(|node| node)
    };
}

/// 类似List的设计思路，RbTree支持Send.
/// 支持基于`Borrow<Q>`实现比较插入，无需强制节点数据结构实现Ord Trait
#[repr(C)]
pub struct RbTree<T> {
    root: Option<RbTreeNodeRef>,
    offset: usize,
    mark: PhantomData<*const T>,
}

unsafe impl<T: Sync> Send for RbTree<T> {}
unsafe impl<T: Sync> Sync for RbTree<T> {}

/// 需要在用户数据结构中定义此类型的成员才能加入到RbTree.
#[repr(transparent)]
pub struct RbTreeNode(UnsafeCell<Inner>);

#[repr(C)]
struct Inner {
    parent: usize,
    left: Option<RbTreeNodeRef>,
    right: Option<RbTreeNodeRef>,
    mark: PhantomData<*mut RbTreeNode>,
    pin: PhantomPinned,
}

#[derive(Copy, Clone)]
struct RbTreeNodeRef {
    ptr: NonNull<RbTreeNode>,
}

impl RbTreeNodeRef {
    fn as_ptr(&self) -> *mut RbTreeNode {
        self.ptr.as_ptr()
    }
}

impl From<&'_ RbTreeNode> for RbTreeNodeRef {
    fn from(src: &'_ RbTreeNode) -> Self {
        Self {
            ptr: NonNull::from(src),
        }
    }
}

impl Deref for RbTreeNodeRef {
    type Target = RbTreeNode;
    fn deref(&self) -> &Self::Target {
        unsafe { self.ptr.as_ref() }
    }
}

impl DerefMut for RbTreeNodeRef {
    fn deref_mut(&mut self) -> &mut Self::Target {
        unsafe { self.ptr.as_mut() }
    }
}

#[derive(Copy, Clone)]
enum Color {
    Black = 0,
    Red = 1,
}

#[derive(Copy, Clone)]
enum Pos {
    Left = 0,
    Right = 2,
}

/// 实际上这应该是一个unsafe Drop，但当前Rust还不支持.
/// 如果RbTree还可用，RbTreeNode应该在析构前确保从RbTree中删除.
impl Drop for RbTreeNode {
    fn drop(&mut self) {}
}

impl<T> RbTree<T> {
    pub fn new<F>(f: F) -> Self
    where
        F: FnOnce(*const T) -> *const RbTreeNode,
    {
        Self {
            root: None,
            offset: crate::node_offset(f),
            mark: PhantomData,
        }
    }

    pub fn empty(&self) -> bool {
        self.root.is_none()
    }

    pub fn first<'a>(&self) -> Option<&'a T> {
        if let Some(root) = self.root {
            Some(self.obj_from(root.first()))
        } else {
            None
        }
    }

    pub fn last<'a>(&self) -> Option<&'a T> {
        if let Some(root) = self.root {
            Some(self.obj_from(root.last()))
        } else {
            None
        }
    }

    /// # Safety
    /// 插入树的节点，需要保证在析构前从树中删除，或者生命周期长于树的生命周期
    pub unsafe fn insert<'a>(&mut self, item: &'a T, overwrite: bool) -> Option<Link<'a>>
    where
        T: Ord,
    {
        self.insert_borrow::<T>(item, overwrite)
    }

    /// # Safety
    /// 插入树的节点，需要保证在析构前从树中删除，或者生命周期长于树的生命周期
    pub unsafe fn insert_borrow<'a, Q>(&mut self, item: &'a T, overwrite: bool) -> Option<Link<'a>>
    where
        Q: Ord,
        T: Borrow<Q>,
    {
        let node = self.node_from(item);
        debug_assert!(!node.linked());
        let key: &Q = item.borrow();

        if let Some(root) = self.root {
            match root.search(|node| key.cmp(self.obj_from(node).borrow())) {
                (parent, Ordering::Less) => {
                    parent.link_left(Some(node));
                    self.insert_rotation(node);
                }
                (parent, Ordering::Greater) => {
                    parent.link_right(Some(node));
                    self.insert_rotation(node);
                }
                (found, Ordering::Equal) => {
                    if overwrite {
                        self.replace_with(found, node);
                    } else {
                        return None;
                    }
                }
            }
        } else {
            node.set_color(Color::Black);
            self.set_root(Some(node));
        }
        Some(Link::new())
    }

    pub fn remove<'a, Q>(&mut self, key: &Q) -> Option<&'a T>
    where
        Q: Ord,
        T: Borrow<Q>,
    {
        let ret = self.find(key);
        if let Some(found) = ret {
            let found = self.node_from(found);
            self.del(found);
        }
        ret
    }

    ///
    /// 提供先序遍历机制，
    ///
    pub fn walk<F>(&self, mut f: F)
    where
        F: FnMut(&T),
    {
        if let Some(root) = self.root {
            root.walk(|node, _| f(self.obj_from(node)));
        }
    }

    ///
    /// 验证是否满足红黑树的规则之一, 到外部节点的所有路径上黑色节点的数量相同
    ///
    pub fn assert(&self, msg: &str) {
        let mut black = 0_usize;
        if let Some(root) = self.root {
            root.walk(|node, cnt| {
                if node.get_left().is_none() || node.get_right().is_none() {
                    if black == 0 {
                        black = cnt;
                    }
                    assert!(cnt == black, "{msg} cnt = {cnt}, black = {black}");
                }
            });
        }
    }

    pub fn find<'a, Q>(&self, key: &Q) -> Option<&'a T>
    where
        Q: Ord,
        T: Borrow<Q>,
    {
        match self
            .root?
            .search(|node| key.cmp(self.obj_from(node).borrow()))
        {
            (found, Ordering::Equal) => Some(self.obj_from(found)),
            _ => None,
        }
    }

    pub fn iter(&self) -> Iter<'_, T> {
        Iter::new(self, self.first_node(), None)
    }

    pub fn iter_mut(&mut self) -> IterMut<'_, T> {
        IterMut::new(self, self.first_node(), None)
    }

    pub fn range<Q, R>(&self, range: R) -> Iter<'_, T>
    where
        Q: Ord,
        T: Borrow<Q>,
        R: RangeBounds<Q>,
    {
        Iter::new(
            self,
            self.find_start(range.start_bound()),
            self.find_end(range.end_bound()),
        )
    }

    pub fn range_mut<Q, R>(&mut self, range: R) -> IterMut<'_, T>
    where
        Q: Ord,
        T: Borrow<Q>,
        R: RangeBounds<Q>,
    {
        IterMut::new(
            self,
            self.find_start(range.start_bound()),
            self.find_end(range.end_bound()),
        )
    }

    fn first_node(&self) -> Option<RbTreeNodeRef> {
        Some(self.root?.first())
    }

    fn find_start<Q>(&self, key: Bound<&Q>) -> Option<RbTreeNodeRef>
    where
        Q: Ord,
        T: Borrow<Q>,
    {
        let root = self.root?;
        match key {
            Included(key) => {
                let (node, ordering) = root.search(|node| key.cmp(self.obj_from(node).borrow()));
                if ordering == Ordering::Greater {
                    node.next()
                } else {
                    Some(node)
                }
            }
            Excluded(key) => {
                let (node, ordering) = root.search(|node| key.cmp(self.obj_from(node).borrow()));
                if ordering != Ordering::Less {
                    node.next()
                } else {
                    Some(node)
                }
            }
            Unbounded => Some(root.first()),
        }
    }

    fn find_end<Q>(&self, key: Bound<&Q>) -> Option<RbTreeNodeRef>
    where
        Q: Ord,
        T: Borrow<Q>,
    {
        let root = self.root?;
        match key {
            Included(key) => {
                let (node, ordering) = root.search(|node| key.cmp(self.obj_from(node).borrow()));
                if ordering != Ordering::Less {
                    node.next()
                } else {
                    Some(node)
                }
            }
            Excluded(key) => {
                let (node, ordering) = root.search(|node| key.cmp(self.obj_from(node).borrow()));
                if ordering == Ordering::Greater {
                    node.next()
                } else {
                    Some(node)
                }
            }
            Unbounded => None,
        }
    }

    fn node_from(&self, obj: &T) -> RbTreeNodeRef {
        let addr = obj as *const _ as usize + self.offset;
        unsafe { &*(addr as *const RbTreeNode) }.into()
    }

    fn obj_from<'a>(&self, node: RbTreeNodeRef) -> &'a T {
        let addr = node.as_ptr() as usize - self.offset;
        unsafe { &*(addr as *const T) }
    }

    fn obj_from_mut<'a>(&self, node: RbTreeNodeRef) -> &'a mut T {
        let addr = node.as_ptr() as usize - self.offset;
        unsafe { &mut *(addr as *mut T) }
    }

    fn set_root(&mut self, node: Option<RbTreeNodeRef>) {
        self.root = node;
        if let Some(node) = node {
            node.set_null_parent();
        }
    }

    fn replace_with(&mut self, old: RbTreeNodeRef, new: RbTreeNodeRef) {
        debug_assert!(!new.linked());
        self.link_child(old.get_parent(), Some(new), old.get_pos());
        new.set_color(old.get_color());
        new.link_left(old.get_left());
        new.link_right(old.get_right());
        old.init_node();
    }

    fn insert_rotation(&mut self, mut node: RbTreeNodeRef) {
        node.set_color(Color::Red);
        while let Some(parent) = node.get_parent() {
            if matches!(parent.get_color(), Color::Black) {
                return;
            }
            let pparent = parent.get_parent().unwrap();
            let sibling = pparent.get_sibling(parent.get_pos());
            if let Some(sibling) = sibling {
                if matches!(sibling.get_color(), Color::Red) {
                    sibling.set_color(Color::Black);
                    parent.set_color(Color::Black);
                    if pparent.get_parent().is_some() {
                        pparent.set_color(Color::Red);
                        node = pparent;
                        continue;
                    } else {
                        return;
                    }
                }
            }

            match node.get_pos() {
                Pos::Left => match parent.get_pos() {
                    Pos::Left => {
                        self.lr_rotation(parent, pparent);
                        parent.set_color(Color::Black);
                        pparent.set_color(Color::Red);
                    }
                    _ => {
                        self.ll_rotation(node, parent, pparent);
                        node.set_color(Color::Black);
                        pparent.set_color(Color::Red);
                    }
                },
                _ => match parent.get_pos() {
                    Pos::Right => {
                        self.rl_rotation(parent, pparent);
                        parent.set_color(Color::Black);
                        pparent.set_color(Color::Red);
                    }
                    _ => {
                        self.rr_rotation(node, parent, pparent);
                        node.set_color(Color::Black);
                        pparent.set_color(Color::Red);
                    }
                },
            }
            return;
        }
    }

    #[inline]
    fn lr_rotation(&mut self, node: RbTreeNodeRef, parent: RbTreeNodeRef) {
        debug_assert!(ptr::eq(node.as_ptr(), parent.get_left().unwrap().as_ptr()));
        self.link_child(parent.get_parent(), Some(node), parent.get_pos());
        parent.link_left(node.get_right());
        node.link_right(Some(parent));
    }

    #[inline]
    fn rr_rotation(&mut self, node: RbTreeNodeRef, parent: RbTreeNodeRef, pparent: RbTreeNodeRef) {
        debug_assert!(ptr::eq(node.as_ptr(), parent.get_right().unwrap().as_ptr()));
        debug_assert!(ptr::eq(
            parent.as_ptr(),
            pparent.get_left().unwrap().as_ptr()
        ));
        self.link_child(pparent.get_parent(), Some(node), pparent.get_pos());
        parent.link_right(node.get_left());
        pparent.link_left(node.get_right());
        node.link_left(Some(parent));
        node.link_right(Some(pparent));
    }

    #[inline]
    fn rl_rotation(&mut self, node: RbTreeNodeRef, parent: RbTreeNodeRef) {
        debug_assert!(ptr::eq(node.as_ptr(), parent.get_right().unwrap().as_ptr()));
        self.link_child(parent.get_parent(), Some(node), parent.get_pos());
        parent.link_right(node.get_left());
        node.link_left(Some(parent));
    }

    #[inline]
    fn ll_rotation(&mut self, node: RbTreeNodeRef, parent: RbTreeNodeRef, pparent: RbTreeNodeRef) {
        debug_assert!(ptr::eq(node.as_ptr(), parent.get_left().unwrap().as_ptr()));
        debug_assert!(ptr::eq(
            parent.as_ptr(),
            pparent.get_right().unwrap().as_ptr()
        ));
        self.link_child(pparent.get_parent(), Some(node), pparent.get_pos());
        parent.link_left(node.get_right());
        pparent.link_right(node.get_left());
        node.link_right(Some(parent));
        node.link_left(Some(pparent));
    }

    fn del(&mut self, node: RbTreeNodeRef) {
        let parent = node.get_parent();
        let (parent, pos) = self.prepare_del(node, parent);
        if matches!(node.get_color(), Color::Black) {
            //如果删除的是root节点，则无需旋转处理
            if let Some(parent) = parent {
                self.del_rotation(parent, pos);
            } else if let Some(root) = self.root {
                if matches!(root.get_color(), Color::Red) {
                    root.set_color(Color::Black);
                }
            }
        }
        node.init_node();
    }

    fn del_rotation(&mut self, mut parent: RbTreeNodeRef, mut pos: Pos) {
        // 正常情况下pos子树少了一个黑色节点，这里sibling一定存在
        while let Some(mut sibling) = parent.get_sibling(pos) {
            if matches!(sibling.get_color(), Color::Red) {
                match pos {
                    Pos::Right => {
                        self.lr_rotation(sibling, parent);
                    }
                    _ => {
                        self.rl_rotation(sibling, parent);
                    }
                }
                sibling.set_color(Color::Black);
                parent.set_color(Color::Red);
                sibling = parent.get_sibling(pos).unwrap();
            }

            if let Some(left) = sibling.get_left() {
                if matches!(left.get_color(), Color::Red) {
                    match pos {
                        Pos::Left => {
                            self.ll_rotation(left, sibling, parent);
                            left.set_color(parent.get_color());
                            parent.set_color(Color::Black);
                        }
                        _ => {
                            left.set_color(Color::Black);
                            self.lr_rotation(sibling, parent);
                            sibling.set_color(parent.get_color());
                            parent.set_color(Color::Black);
                        }
                    }
                    return;
                }
            }

            if let Some(right) = sibling.get_right() {
                if matches!(right.get_color(), Color::Red) {
                    match pos {
                        Pos::Left => {
                            right.set_color(Color::Black);
                            self.rl_rotation(sibling, parent);
                            sibling.set_color(parent.get_color());
                            parent.set_color(Color::Black);
                        }
                        _ => {
                            self.rr_rotation(right, sibling, parent);
                            right.set_color(parent.get_color());
                            parent.set_color(Color::Black);
                        }
                    }
                    return;
                }
            }

            sibling.set_color(Color::Red);

            if matches!(parent.get_color(), Color::Red) {
                parent.set_color(Color::Black);
                return;
            }

            if let Some(pparent) = parent.get_parent() {
                pos = parent.get_pos();
                parent = pparent;
                continue;
            }

            return;
        }
    }

    fn prepare_del(
        &mut self,
        node: RbTreeNodeRef,
        parent: Option<RbTreeNodeRef>,
    ) -> (Option<RbTreeNodeRef>, Pos) {
        if node.get_left().is_none() {
            self.link_child(parent, node.get_right(), node.get_pos());
            (parent, node.get_pos())
        } else if node.get_right().is_none() {
            self.link_child(parent, node.get_left(), node.get_pos());
            (parent, node.get_pos())
        } else if matches!(node.get_right().unwrap().get_color(), Color::Red) {
            self.swap_next_del(node, node.next().unwrap(), parent)
        } else {
            self.swap_prev_del(node, node.prev().unwrap(), parent)
        }
    }

    #[inline]
    fn swap_next_del(
        &mut self,
        node: RbTreeNodeRef,
        item: RbTreeNodeRef,
        parent: Option<RbTreeNodeRef>,
    ) -> (Option<RbTreeNodeRef>, Pos) {
        let item_parent = item.get_parent().unwrap();
        node.swap_color(item);
        if !ptr::eq(item_parent.as_ptr(), node.as_ptr()) {
            item_parent.link_left(item.get_right());
            self.link_child(parent, Some(item), node.get_pos());
            item.link_left(node.get_left());
            item.link_right(node.get_right());
            (Some(item_parent), Pos::Left)
        } else {
            item.link_left(node.get_left());
            self.link_child(parent, Some(item), node.get_pos());
            (Some(item), Pos::Right)
        }
    }

    #[inline]
    fn swap_prev_del(
        &mut self,
        node: RbTreeNodeRef,
        item: RbTreeNodeRef,
        parent: Option<RbTreeNodeRef>,
    ) -> (Option<RbTreeNodeRef>, Pos) {
        let item_parent = item.get_parent().unwrap();
        node.swap_color(item);
        if !ptr::eq(item_parent.as_ptr(), node.as_ptr()) {
            item_parent.link_right(item.get_left());
            self.link_child(parent, Some(item), node.get_pos());
            item.link_left(node.get_left());
            item.link_right(node.get_right());
            (Some(item_parent), Pos::Right)
        } else {
            item.link_right(node.get_right());
            self.link_child(parent, Some(item), node.get_pos());
            (Some(item), Pos::Left)
        }
    }

    fn link_child(&mut self, parent: Option<RbTreeNodeRef>, node: Option<RbTreeNodeRef>, pos: Pos) {
        if let Some(parent) = parent {
            parent.link_child(node, pos);
        } else {
            self.set_root(node);
        }
    }
}

impl Default for RbTreeNode {
    fn default() -> Self {
        Self::new()
    }
}

impl RbTreeNode {
    pub const fn new() -> Self {
        Self(UnsafeCell::new(Inner {
            parent: 0,
            left: None,
            right: None,
            pin: PhantomPinned,
            mark: PhantomData,
        }))
    }

    fn get_color(&self) -> Color {
        match self.inner().parent & 0x01 {
            0x00 => Color::Black,
            _ => Color::Red,
        }
    }

    fn set_color(&self, color: Color) {
        let inner = unsafe { &mut *self.0.get() };
        inner.parent = (inner.parent & !0x01) | color as usize;
    }

    fn next(&self) -> Option<RbTreeNodeRef> {
        if let Some(right) = self.get_right() {
            Some(right.first())
        } else {
            let mut node = RbTreeNodeRef::from(self);
            while let Some(parent) = node.get_parent() {
                if matches!(node.get_pos(), Pos::Left) {
                    return Some(parent);
                }
                node = parent;
            }
            None
        }
    }

    fn prev(&self) -> Option<RbTreeNodeRef> {
        if let Some(left) = self.get_left() {
            Some(left.last())
        } else if matches!(self.get_pos(), Pos::Right) {
            self.get_parent()
        } else {
            let mut node = RbTreeNodeRef::from(self);
            while let Some(parent) = node.get_parent() {
                if matches!(parent.get_pos(), Pos::Right) {
                    return parent.get_parent();
                }
                node = parent;
            }
            None
        }
    }

    fn walk<F>(&self, mut f: F)
    where
        F: FnMut(RbTreeNodeRef, usize),
    {
        let mut black = 0;
        let mut node = RbTreeNodeRef::from(self);
        'start: loop {
            if matches!(node.get_color(), Color::Black) {
                black += 1;
            }
            f(node, black);
            if let Some(left) = node.get_left() {
                node = left;
            } else if let Some(right) = node.get_right() {
                node = right;
            } else {
                while let Some(parent) = node.get_parent() {
                    if ptr::eq(node.as_ptr(), self) {
                        return;
                    }
                    if matches!(node.get_color(), Color::Black) {
                        black -= 1;
                    }
                    if matches!(node.get_pos(), Pos::Left) {
                        if let Some(sibling) = parent.get_right() {
                            node = sibling;
                            continue 'start;
                        }
                    }
                    node = parent;
                }
                return;
            }
        }
    }

    fn link_child(&self, child: Option<RbTreeNodeRef>, pos: Pos) {
        match pos {
            Pos::Left => self.link_left(child),
            _ => self.link_right(child),
        }
    }

    fn get_sibling(&self, pos: Pos) -> Option<RbTreeNodeRef> {
        match pos {
            Pos::Left => self.get_right(),
            _ => self.get_left(),
        }
    }

    fn search<F>(&self, comp: F) -> (RbTreeNodeRef, Ordering)
    where
        F: Fn(RbTreeNodeRef) -> Ordering,
    {
        let mut cur = RbTreeNodeRef::from(self);
        loop {
            match comp(cur) {
                Ordering::Less => {
                    if let Some(left) = cur.get_left() {
                        cur = left;
                    } else {
                        return (cur, Ordering::Less);
                    }
                }
                Ordering::Greater => {
                    if let Some(right) = cur.get_right() {
                        cur = right;
                    } else {
                        return (cur, Ordering::Greater);
                    }
                }
                _ => {
                    return (cur, Ordering::Equal);
                }
            }
        }
    }

    fn swap_color(&self, rhs: RbTreeNodeRef) {
        let color = self.get_color();
        self.set_color(rhs.get_color());
        rhs.set_color(color);
    }

    #[inline]
    fn first(&self) -> RbTreeNodeRef {
        if let Some(mut left) = self.get_left() {
            while let Some(item) = left.get_left() {
                left = item;
            }
            left
        } else {
            RbTreeNodeRef::from(self)
        }
    }

    #[inline]
    fn last(&self) -> RbTreeNodeRef {
        if let Some(mut right) = self.get_right() {
            while let Some(item) = right.get_right() {
                right = item;
            }
            right
        } else {
            RbTreeNodeRef::from(self)
        }
    }

    fn get_parent(&self) -> Option<RbTreeNodeRef> {
        let parent = self.inner().parent & !0x03;
        if parent > 0 {
            let parent = unsafe { &*(parent as *const Self) };
            Some(RbTreeNodeRef::from(parent))
        } else {
            None
        }
    }

    fn get_pos(&self) -> Pos {
        match self.inner().parent & 0x02 {
            0x02 => Pos::Right,
            _ => Pos::Left,
        }
    }

    fn get_left(&self) -> Option<RbTreeNodeRef> {
        self.inner().left
    }

    fn get_right(&self) -> Option<RbTreeNodeRef> {
        self.inner().right
    }

    fn link_left(&self, left: Option<RbTreeNodeRef>) {
        let inner = unsafe { &mut *self.0.get() };
        if let Some(left) = left {
            inner.left = Some(left);
            left.set_parent(self, Pos::Left);
        } else {
            inner.left = None;
        }
    }

    fn link_right(&self, right: Option<RbTreeNodeRef>) {
        let inner = unsafe { &mut *self.0.get() };
        if let Some(right) = right {
            inner.right = Some(right);
            right.set_parent(self, Pos::Right);
        } else {
            inner.right = None;
        }
    }

    fn set_parent(&self, parent: &Self, pos: Pos) {
        let inner = unsafe { &mut *self.0.get() };
        inner.parent = (inner.parent & 0x01) | parent as *const _ as usize | pos as usize;
    }

    fn set_null_parent(&self) {
        let inner = unsafe { &mut *self.0.get() };
        inner.parent = 0;
    }

    fn init_node(&self) {
        let inner = unsafe { &mut *self.0.get() };
        inner.parent = 0;
        inner.left = None;
        inner.right = None;
    }

    fn inner(&self) -> &Inner {
        unsafe { &*self.0.get() }
    }

    fn linked(&self) -> bool {
        let inner = self.inner();
        (inner.parent & !0x03) > 0 || inner.left.is_some() || inner.right.is_some()
    }
}

pub struct Iter<'a, T> {
    tree: &'a RbTree<T>,
    start: Option<RbTreeNodeRef>,
    end: Option<RbTreeNodeRef>,
}

impl<'a, T> Iter<'a, T> {
    fn new(tree: &'a RbTree<T>, start: Option<RbTreeNodeRef>, end: Option<RbTreeNodeRef>) -> Self {
        Self { tree, start, end }
    }
}

fn pos_equal(lhs: Option<RbTreeNodeRef>, rhs: Option<RbTreeNodeRef>) -> bool {
    lhs.map(|node| node.as_ptr()) == rhs.map(|node| node.as_ptr())
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<Self::Item> {
        if let Some(start) = self.start {
            if !pos_equal(self.start, self.end) {
                self.start = start.next();
                return Some(self.tree.obj_from(start));
            }
        }
        None
    }
}

impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
    fn next_back(&mut self) -> Option<Self::Item> {
        if pos_equal(self.start, self.end) {
            return None;
        }
        if let Some(end) = self.end {
            if let Some(prev) = end.prev() {
                self.end = Some(prev);
                return Some(self.tree.obj_from(prev));
            }
            None
        } else {
            self.end = Some(self.tree.root?.last());
            self.end.map(|node| self.tree.obj_from(node))
        }
    }
}

impl<'a, T> IntoIterator for &'a RbTree<T> {
    type Item = &'a T;
    type IntoIter = Iter<'a, T>;
    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

pub struct IterMut<'a, T> {
    tree: &'a RbTree<T>,
    start: Option<RbTreeNodeRef>,
    end: Option<RbTreeNodeRef>,
}

impl<'a, T> IterMut<'a, T> {
    fn new(tree: &'a RbTree<T>, start: Option<RbTreeNodeRef>, end: Option<RbTreeNodeRef>) -> Self {
        Self { tree, start, end }
    }
}

impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;
    fn next(&mut self) -> Option<Self::Item> {
        if let Some(start) = self.start {
            if !pos_equal(self.start, self.end) {
                self.start = start.next();
                return Some(self.tree.obj_from_mut(start));
            }
        }
        None
    }
}

impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
    fn next_back(&mut self) -> Option<Self::Item> {
        if pos_equal(self.start, self.end) {
            return None;
        }
        if let Some(end) = self.end {
            if let Some(prev) = end.prev() {
                self.end = Some(prev);
                return Some(self.tree.obj_from_mut(prev));
            }
            None
        } else {
            self.end = Some(self.tree.root?.last());
            self.end.map(|node| self.tree.obj_from_mut(node))
        }
    }
}

impl<'a, T> IntoIterator for &'a mut RbTree<T> {
    type Item = &'a mut T;
    type IntoIter = IterMut<'a, T>;
    fn into_iter(self) -> Self::IntoIter {
        self.iter_mut()
    }
}

#[cfg(test)]
mod test {
    extern crate std;
    use crate::RbTreeNode;
    use rand;
    use std::borrow::Borrow;
    use std::cmp::{Ordering, PartialEq, PartialOrd};
    use std::format;
    use std::mem::MaybeUninit;
    use std::println;
    use std::ptr;

    struct Foo {
        val: i32,
        node: RbTreeNode,
    }

    impl Borrow<i32> for Foo {
        fn borrow(&self) -> &i32 {
            &self.val
        }
    }

    impl Eq for Foo {}
    impl PartialOrd for Foo {
        fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
            self.val.partial_cmp(&other.val)
        }
    }

    impl PartialEq for Foo {
        fn eq(&self, other: &Self) -> bool {
            self.val == other.val
        }
    }

    impl Ord for Foo {
        fn cmp(&self, other: &Self) -> Ordering {
            self.val.cmp(&other.val)
        }
    }

    #[test]
    fn test_insert_0_99() {
        let mut tree = rbtree!(Foo, node);

        let mut foos: [Foo; 100] = unsafe { MaybeUninit::zeroed().assume_init() };
        foos.iter_mut().fold(0, |n, foo| {
            foo.val = n;
            let link = unsafe { tree.insert(foo, false) };
            assert!(link.is_some());
            tree.assert(format!("insert {}", foo.val).as_str());
            n + 1
        });

        foos.iter().for_each(|foo| {
            let found = tree.find(foo);
            assert!(found.is_some());
            assert!(ptr::eq(found.unwrap(), foo));
        });

        let first = tree.first().unwrap();
        let last = tree.last().unwrap();
        assert_eq!(first.val, 0);
        assert_eq!(last.val, 99);
    }

    #[test]
    fn test_insert_99_0() {
        let mut tree = rbtree!(Foo, node);

        let mut foos: [Foo; 100] = unsafe { MaybeUninit::zeroed().assume_init() };
        foos.iter_mut().fold(0, |n, foo| {
            foo.val = 100 - n;
            let link = unsafe { tree.insert_borrow::<i32>(foo, false) };
            assert!(link.is_some());
            tree.assert(format!("insert {}", foo.val).as_str());
            n + 1
        });

        foos.iter().for_each(|foo| {
            let found = tree.find(&foo.val);
            assert!(found.is_some());
            assert!(ptr::eq(found.unwrap(), foo));
        });

        let first = tree.first().unwrap();
        let last = tree.last().unwrap();
        assert_eq!(first.val, 1);
        assert_eq!(last.val, 100);
    }

    #[test]
    fn test_del_0_99() {
        let mut tree = rbtree!(Foo, node);

        let mut foos: [Foo; 1000] = unsafe { MaybeUninit::zeroed().assume_init() };
        /*
                foos.iter_mut().fold(0, |n, foo| {
                    foo.val = n;
                    foo.node = RbTreeNode::new();
                    n + 1
                });

                let orders = [2, 1, 4, 3, 5, 0];
                for i in orders {
                    println!("insert {}", foos[i].val);
                    tree.insert(&foos[i], false);
                }
                tree.assert("after insert");
                let orders = [2, 1, 4, 3, 5, 0];
                for i in orders {
                    println!("remove {}", foos[i].val);
                    tree.remove(&foos[i]);
                    tree.assert("after after remove");
                }
        */
        foos.iter_mut().fold(0, |n, foo| {
            foo.val = rand::random::<i32>();
            println!("set foo.val = {}", foo.val);
            while unsafe { tree.insert_borrow::<i32>(foo, false) }.is_none() {
                foo.val += 3;
                println!("reset foo.val = {}", foo.val);
            }
            tree.assert(format!("insert {}", foo.val).as_str());
            n + 1
        });
        tree.assert("after insert");
        foos.iter().for_each(|foo| {
            let found = tree.find(&foo.val);
            assert!(found.is_some());
            assert!(ptr::eq(found.unwrap(), foo));

            tree.assert(format!("before remove {}", foo.val).as_str());
            println!(
                "remove: {} color: {} pos: {}",
                foo.val,
                foo.node.get_color() as usize,
                foo.node.get_pos() as usize
            );
            let ret = tree.remove(&foo.val);
            assert!(ret.is_some());
            assert!(ptr::eq(ret.unwrap(), foo));
            tree.assert(format!("after remove {}", foo.val).as_str());
        });

        assert!(tree.first().is_none());
        assert!(tree.last().is_none());
        assert!(tree.empty());
    }

    #[test]
    fn test_iter() {
        let mut tree = rbtree!(Foo, node);

        let mut foos: [Foo; 100] = unsafe { MaybeUninit::zeroed().assume_init() };
        for (n, foo) in foos.iter_mut().enumerate() {
            foo.val = n as i32;
            unsafe { tree.insert_borrow::<i32>(foo, false) };
            tree.assert(format!("insert {}", foo.val).as_str());
        }

        let iter = tree.iter();
        let mut min = tree.first().unwrap().val - 1;
        iter.for_each(|foo| {
            assert!(foo.val > min);
            min = foo.val;
        });

        assert_eq!(tree.iter().count(), 100);
    }

    #[test]
    fn test_range() {
        let mut tree = rbtree!(Foo, node);
        let mut foos: [Foo; 100] = unsafe { MaybeUninit::zeroed().assume_init() };
        for (n, foo) in foos.iter_mut().enumerate() {
            foo.val = n as i32;
            unsafe { tree.insert(foo, false) };
        }

        assert_eq!(tree.range(0..).count(), 100);
        assert_eq!(tree.range(-1..).rev().count(), 100);
        assert_eq!(tree.range(100..201).count(), 0);
        assert_eq!(tree.range(99..100).count(), 1);
        assert_eq!(tree.range(0..0).count(), 0);
        assert_eq!(tree.range(0..=0).count(), 1);
        assert_eq!(tree.range(0..1).count(), 1);

        assert_eq!(0, tree.range(100..101).count());
        assert_eq!(1, tree.range(99..101).count());
        assert_eq!(100, tree.range(0..101).count());
        assert_eq!(50, tree.range(1..51).count());

        let mut iter = tree.range(50..=50);
        assert_eq!(iter.next_back().unwrap().val, 50);
        assert!(iter.next_back().is_none());
        assert!(iter.next().is_none());
    }

    #[test]
    fn test_iter_mut() {
        let mut tree = rbtree!(Foo, node);

        let mut foos: [Foo; 100] = unsafe { MaybeUninit::zeroed().assume_init() };
        foos.iter_mut().fold(0, |n, foo| {
            foo.val = n;
            unsafe { tree.insert_borrow::<i32>(foo, false) };
            tree.assert(format!("insert {}", foo.val).as_str());
            n + 1
        });

        tree.iter_mut().fold(0, |n, foo| {
            foo.val += n;
            n + 1
        });

        foos.iter().fold(0, |n, foo| {
            assert_eq!(foo.val, n + n);
            n + 1
        });

        assert_eq!(foos.iter().count(), tree.iter_mut().count());
        assert_eq!(foos.iter_mut().count(), tree.iter_mut().rev().count());
    }

    #[test]
    fn test_replace() {
        let mut tree = rbtree!(Foo, node);
        let foo = Foo {
            val: 100,
            node: RbTreeNode::new(),
        };
        unsafe { tree.insert_borrow::<i32>(&foo, false) };

        let bar = Foo {
            val: 100,
            node: RbTreeNode::new(),
        };
        assert!(unsafe { tree.insert_borrow::<i32>(&bar, false) }.is_none());
        assert!(unsafe { tree.insert_borrow::<i32>(&bar, true) }.is_some());

        let found = tree.find(&foo.val);
        assert!(found.is_some());
        assert!(ptr::eq(found.unwrap(), &bar));

        let baz = Foo {
            val: 101,
            node: RbTreeNode::new(),
        };
        assert!(unsafe { tree.insert_borrow::<i32>(&baz, false) }.is_some());
        assert!(unsafe { tree.insert_borrow::<i32>(&foo, true) }.is_some());

        let found = tree.find(&bar.val);
        assert!(found.is_some());
        assert!(ptr::eq(found.unwrap(), &foo));
    }
}
