use std::{mem::transmute, ptr::NonNull};

use crate::mem::{
    header::LinksHeader,
    split::{
        generic::external_recursion_less_base::{
            ExternalRecursionlessSizeBalancedTreeBase,
            ExternalRecursionlessSizeBalancedTreeBaseAbstract,
        },
        DataPart, IndexPart,
    },
    traits::LinksTree,
    SplitTree,
};

use crate::{mem::SplitUpdateMem, Link};
use data::{Flow, LinkReference, LinksConstants};
use trees::{IterativeSizeBalancedTree, RecursiveSizeBalancedTree};

pub struct ExternalTargetsRecursionlessTree<T: LinkReference> {
    base: ExternalRecursionlessSizeBalancedTreeBase<T>,
}

impl<T: LinkReference> ExternalTargetsRecursionlessTree<T> {
    pub fn new(
        constants: LinksConstants<T>,
        data: NonNull<[DataPart<T>]>,
        indexes: NonNull<[IndexPart<T>]>,
    ) -> Self {
        Self {
            base: ExternalRecursionlessSizeBalancedTreeBase::new(constants, data, indexes),
        }
    }
}

impl<T: LinkReference> RecursiveSizeBalancedTree<T> for ExternalTargetsRecursionlessTree<T> {
    unsafe fn get_left_reference(&self, node: T) -> *const T {
        std::ptr::addr_of!(self.get_index_part(node).left_as_target)
    }

    unsafe fn get_right_reference(&self, node: T) -> *const T {
        std::ptr::addr_of!(self.get_index_part(node).right_as_target)
    }

    unsafe fn get_mut_left_reference(&mut self, node: T) -> *mut T {
        std::ptr::addr_of_mut!(self.get_mut_index_part(node).left_as_target)
    }

    unsafe fn get_mut_right_reference(&mut self, node: T) -> *mut T {
        std::ptr::addr_of_mut!(self.get_mut_index_part(node).right_as_target)
    }

    unsafe fn get_left(&self, node: T) -> T {
        self.get_index_part(node).left_as_target
    }

    unsafe fn get_right(&self, node: T) -> T {
        self.get_index_part(node).right_as_target
    }

    unsafe fn get_size(&self, node: T) -> T {
        self.get_index_part(node).size_as_target
    }

    unsafe fn set_left(&mut self, node: T, left: T) {
        self.get_mut_index_part(node).left_as_target = left;
    }

    unsafe fn set_right(&mut self, node: T, right: T) {
        self.get_mut_index_part(node).right_as_target = right;
    }

    unsafe fn set_size(&mut self, node: T, size: T) {
        self.get_mut_index_part(node).size_as_target = size;
    }

    unsafe fn first_is_to_the_left_of_second(&self, first: T, second: T) -> bool {
        let first = self.get_data_part(first);
        let second = self.get_data_part(second);
        self.first_is_to_the_left_of_second_4(
            first.source,
            first.target,
            second.source,
            second.target,
        )
    }

    unsafe fn first_is_to_the_right_of_second(&self, first: T, second: T) -> bool {
        let first = self.get_data_part(first);
        let second = self.get_data_part(second);
        self.first_is_to_the_right_of_second_4(
            first.source,
            first.target,
            second.source,
            second.target,
        )
    }

    unsafe fn clear_node(&mut self, node: T) {
        let link = self.get_mut_index_part(node);
        link.left_as_target = T::from_byte(0);
        link.right_as_target = T::from_byte(0);
        link.size_as_target = T::from_byte(0);
    }
}

impl<T: LinkReference> IterativeSizeBalancedTree<T> for ExternalTargetsRecursionlessTree<T> {}

fn each_usages_core<T: LinkReference, H: FnMut(Link<T>) -> Flow + ?Sized>(
    this: &ExternalTargetsRecursionlessTree<T>,
    base: T,
    link: T,
    handler: &mut H,
) -> Flow {
    if link == T::from_byte(0) {
        return Flow::Continue;
    }
    unsafe {
        let link_base_part = this.get_base_part(link);
        if link_base_part > base {
            if each_usages_core(this, base, this.get_left_or_default(link), handler).is_break() {
                return Flow::Break;
            }
        } else if link_base_part < base {
            if each_usages_core(this, base, this.get_right_or_default(link), handler).is_break() {
                return Flow::Break;
            }
        } else {
            if handler(this.get_link_value(link)).is_break() {
                return Flow::Break;
            }
            if each_usages_core(this, base, this.get_left_or_default(link), handler).is_break() {
                return Flow::Break;
            }
            if each_usages_core(this, base, this.get_right_or_default(link), handler).is_break() {
                return Flow::Break;
            }
        }
    }
    Flow::Continue
}

impl<T: LinkReference> LinksTree<T> for ExternalTargetsRecursionlessTree<T> {
    fn count_usages(&self, link: T) -> T {
        unsafe {
            let mut root = self.get_tree_root();
            let total = self.get_size(root);
            let mut total_right_ignore = T::from_byte(0);
            while root != T::from_byte(0) {
                let base = self.get_base_part(root);
                if base <= link {
                    root = self.get_right_or_default(root);
                } else {
                    total_right_ignore =
                        total_right_ignore + self.get_right_size(root) + T::from_byte(1);
                    root = self.get_left_or_default(root);
                }
            }
            root = self.get_tree_root();
            let mut total_left_ignore = T::from_byte(0);
            while root != T::from_byte(0) {
                let base = self.get_base_part(root);
                if base >= link {
                    root = self.get_left_or_default(root);
                } else {
                    total_left_ignore =
                        total_left_ignore + self.get_left_size(root) + T::from_byte(1);
                    root = self.get_right_or_default(root);
                }
            }
            total - total_right_ignore - total_left_ignore
        }
    }

    fn search(&self, source: T, target: T) -> T {
        unsafe {
            let mut root = self.get_tree_root();
            while root != T::from_byte(0) {
                let root_link = self.get_data_part(root);
                let root_source = root_link.source;
                let root_target = root_link.target;
                if self.first_is_to_the_left_of_second_4(source, target, root_source, root_target) {
                    root = self.get_left_or_default(root);
                } else if self.first_is_to_the_right_of_second_4(
                    source,
                    target,
                    root_source,
                    root_target,
                ) {
                    root = self.get_right_or_default(root);
                } else {
                    return root;
                }
            }
            T::from_byte(0)
        }
    }

    fn each_usages<H: FnMut(Link<T>) -> Flow + ?Sized>(&self, root: T, handler: &mut H) -> Flow {
        each_usages_core(self, root, self.get_tree_root(), handler)
    }

    fn detach(&mut self, root: &mut T, index: T) {
        unsafe { IterativeSizeBalancedTree::detach(self, root as *mut _, index) }
    }

    fn attach(&mut self, root: &mut T, index: T) {
        unsafe { IterativeSizeBalancedTree::attach(self, root as *mut _, index) }
    }
}

impl<T: LinkReference> SplitUpdateMem<T> for ExternalTargetsRecursionlessTree<T> {
    fn update_mem(&mut self, data: NonNull<[DataPart<T>]>, indexes: NonNull<[IndexPart<T>]>) {
        self.base.indexes = indexes;
        self.base.data = data;
    }
}

impl<T: LinkReference> SplitTree<T> for ExternalTargetsRecursionlessTree<T> {}

impl<T: LinkReference> ExternalRecursionlessSizeBalancedTreeBaseAbstract<T>
    for ExternalTargetsRecursionlessTree<T>
{
    fn get_header(&self) -> &LinksHeader<T> {
        unsafe { transmute(&self.base.indexes.as_ref()[0]) }
    }

    fn get_mut_header(&mut self) -> &mut LinksHeader<T> {
        unsafe { transmute(&mut self.base.indexes.as_mut()[0]) }
    }

    fn get_index_part(&self, link: T) -> &IndexPart<T> {
        unsafe { &self.base.indexes.as_ref()[link.as_()] }
    }

    fn get_mut_index_part(&mut self, link: T) -> &mut IndexPart<T> {
        unsafe { &mut self.base.indexes.as_mut()[link.as_()] }
    }

    fn get_data_part(&self, link: T) -> &DataPart<T> {
        unsafe { &self.base.data.as_ref()[link.as_()] }
    }

    fn get_mut_data_part(&mut self, link: T) -> &mut DataPart<T> {
        unsafe { &mut self.base.data.as_mut()[link.as_()] }
    }

    fn get_tree_root(&self) -> T {
        self.get_header().root_as_target
    }

    fn get_base_part(&self, link: T) -> T {
        self.get_data_part(link).target
    }

    fn first_is_to_the_left_of_second_4(
        &self,
        first_source: T,
        first_target: T,
        second_source: T,
        second_target: T,
    ) -> bool {
        (first_target < second_target)
            || (first_target == second_target && first_source < second_source)
    }

    fn first_is_to_the_right_of_second_4(
        &self,
        first_source: T,
        first_target: T,
        second_source: T,
        second_target: T,
    ) -> bool {
        (first_target > second_target)
            || (first_target == second_target && first_source > second_source)
    }
}
