hibit_tree 0.1.0-beta.1

use std::ops::RangeTo;
use crate::{BitBlock, HierarchyIndex};
use crate::const_utils::{ConstBool, ConstInteger, ConstTrue, IsConstTrue};
use crate::iter::Iter;
use crate::ops::Map;
use crate::utils::Borrowable;
use crate::utils::function::*;

/// [HibitTree] lifetime-dependent types.
pub trait HibitTreeTypes<'this, ImplicitBounds = &'this Self>{
    type Data;
    type DataUnchecked;
    type DataOrDefault;
    type Cursor: HibitTreeCursor<'this, Tree=Self>;
}

/// Hierarchical bitmap tree interface.
/// 
/// HibitTree is a base trait for [RegularHibitTree] and [MultiHibitTree],
/// which you will use most of the time. Only multi_* operations over non-[RegularHibitTree]'ies
/// return bare `HibitTree`.
/// 
/// # Design choices
///
/// This split is needed, because multi_* operations ([MultiHibitTree]'ies) 
/// return Items as Iterators, that produce values on the fly. [Self::data()], [Self::data_unchecked()] 
/// and [Self::iter()] - all get source data from different functions, and also
/// process it in different ways. Alternative to this would be collect all items
/// into intermediate container, and then return it to the user. Or aggregate them
/// during access call - but this way you would not have a meaningful way of processing
/// individual items. So we split process - multi_* returns [MultiHibitTree], which
/// you can iterate with [LendingIterator], or you can aggregate it to [RegularHibitTree]
/// with [map()]. 
/// 
/// [LendingIterator]: crate::utils::LendingIterator
/// [map()]: HibitTree::map()
///
/// # HibitTreeTypes
/// 
/// HibitTree "inherits" HibitTreeTypes with lifetime argument. 
/// This is workaround for Rust's basically non-usable GATs[^gat_problems].
/// 
/// If you need concrete types - use [HibitTreeData] and 
/// [MultiHibitTreeIterItem] helpers. Or get them from [HibitTreeTypes],
/// as if it were super-trait:
/// ```
/// # use hibit_tree::{HibitTree, HibitTreeData, HibitTreeTypes};
/// # fn myfn<MyTree: HibitTree>(my_sparse_container: MyTree){
/// let i: HibitTreeData<MyTree> = my_sparse_container.get(1).unwrap();
/// let i: <MyTree as HibitTreeTypes>::Data = my_sparse_container.get(1).unwrap();
/// # }
/// ```
/// 
/// Same technique used for other HibitTree related traits.
/// 
/// [^gat_problems]: With GAT's we always end up with this <https://blog.rust-lang.org/2022/10/28/gats-stabilization.html#implied-static-requirement-from-higher-ranked-trait-bounds>
/// error.
/// We use this technique <https://sabrinajewson.org/blog/the-better-alternative-to-lifetime-gats#the-better-gats> 
/// as a workaround.
pub trait HibitTree: Sized + Borrowable<Borrowed=Self>
where
	Self: for<'this> HibitTreeTypes<'this>,
{
    /// Marker that this tree as a bitmap hierarchy does not have
    /// false-positive bits in bitmasks.
    const EXACT_HIERARCHY: bool;
    
    /// Tree capability of returning Default value for absent elements FAST.
    /// 
    /// Makes [data_or_default](Self::data_or_default) available.
    type DefaultData: ConstBool;
    
    /// Hierarchy levels count (without a data level).
    type LevelCount: ConstInteger;
    
    /// Bitmask used in each Node.
    type LevelMask : BitBlock;
 
    /// # Safety
    /// 
    /// Element may not exist, but `index` must be in range, and `level_indices` must
    /// correspond to `index`.
    /// 
    /// `level_indices` must be [LevelCount] size[^1].
    /// 
    /// [LevelCount]: Self::LevelCount
    /// 
    /// [^1]: It is not just `[usize; LevelCount::VALUE]` due to troublesome 
    ///       Rust const expressions in generic context. 
    fn data(&self, index: &HierarchyIndex<Self::LevelMask, Self::LevelCount>)
        -> Option<<Self as HibitTreeTypes<'_>>::Data>;
 
    // TODO: try pass HierarchyIndex by value
    /// # Safety
    /// 
    /// pointed element must exist, and `level_indices` must
    /// corresponds to `index`.
    /// 
    /// `level_indices` must be [LevelCount] size[^1].
    /// 
    /// [LevelCount]: Self::LevelCount
    /// 
    /// [^1]: It is not just `[usize; LevelCount::VALUE]` due to troublesome 
    ///       Rust const expressions in generic context. 
    unsafe fn data_unchecked(&self, index: &HierarchyIndex<Self::LevelMask, Self::LevelCount>)
        -> <Self as HibitTreeTypes<'_>>::DataUnchecked;
    
    // Should be safe + "where Self::DefaultData: IsConstTrue". Or just be in
    // separate super trait HibitTreeWithDefault. But it's just way too tedious 
    // to work with that in RUST.
    /// # Safety
    /// 
    /// Unsafe to call if DefaultData is not true.
    unsafe fn data_or_default(&self, index: &HierarchyIndex<Self::LevelMask, Self::LevelCount>)
        -> <Self as HibitTreeTypes<'_>>::DataOrDefault;
    
    /// You can use `usize` or [HierarchyIndex] for `index`.
    /// 
    /// # Panic
    /// 
    /// Will panic if `index.try_into() -> Err`.
    #[inline]
    fn get(&self, index: impl TryInto<HierarchyIndex<<Self as HibitTree>::LevelMask, Self::LevelCount>>) 
        -> Option<<Self as HibitTreeTypes<'_>>::Data> 
    {
        let index = index.try_into().unwrap_or_else(|_| panic!());
        self.data(&index)
    }

    /// # Safety
    ///
    /// * `index` must be valid.
    /// * Item at `index` must exist.
    #[inline]
    unsafe fn get_unchecked(&self, index: impl TryInto<HierarchyIndex<<Self as HibitTree>::LevelMask, Self::LevelCount>>) 
        -> <Self as HibitTreeTypes<'_>>::DataUnchecked 
    {
        let index = index.try_into().unwrap_unchecked();
        self.data_unchecked(&index)
    }

    /// # Panic
    /// 
    /// Will panic if `index.try_into() -> Err`.
    #[inline]
    fn get_or_default(&self, index: impl TryInto<HierarchyIndex<<Self as HibitTree>::LevelMask, Self::LevelCount>>)
        -> <Self as HibitTreeTypes<'_>>::DataOrDefault
    where 
        Self::DefaultData: IsConstTrue
    {
        let index = index.try_into().unwrap_or_else(|_| panic!());
        unsafe{ self.data_or_default(&index) }
    }
    
    #[inline]
    fn iter(&self) -> Iter<Self>{
        Iter::new(self)
    }
    
    /// See [crate::map]
    #[inline]
    fn map<F>(self, f: F) -> Map<Self, F>
    where
        for<'a, 'b> F: 
            UnaryFunction<<Self as HibitTreeTypes<'a>>::Data> +
            UnaryFunction<<Self as HibitTreeTypes<'a>>::DataUnchecked> +
            UnaryFunction<<Self as HibitTreeTypes<'a>>::DataOrDefault> +
    
            UnaryFunction<<<Self as HibitTreeTypes<'a>>::Cursor as HibitTreeCursorTypes<'b>>::Data > +
            UnaryFunction<<<Self as HibitTreeTypes<'a>>::Cursor as HibitTreeCursorTypes<'b>>::DataUnchecked > + 
            UnaryFunction<<<Self as HibitTreeTypes<'a>>::Cursor as HibitTreeCursorTypes<'b>>::DataOrDefault >,    
    {
        crate::map(self, f)
    }
    
    /// See [crate::map_w_default]
    #[inline]
    fn map_w_default<F>(self, f: F) -> Map<Self, F, ConstTrue>
    where
        Self::DefaultData: IsConstTrue,
        for<'a, 'b> F: 
            UnaryFunction<<Self as HibitTreeTypes<'a>>::Data> +
            UnaryFunction<<Self as HibitTreeTypes<'a>>::DataUnchecked> +
            UnaryFunction<<Self as HibitTreeTypes<'a>>::DataOrDefault> +
    
            UnaryFunction<<<Self as HibitTreeTypes<'a>>::Cursor as HibitTreeCursorTypes<'b>>::Data > +
            UnaryFunction<<<Self as HibitTreeTypes<'a>>::Cursor as HibitTreeCursorTypes<'b>>::DataUnchecked > + 
            UnaryFunction<<<Self as HibitTreeTypes<'a>>::Cursor as HibitTreeCursorTypes<'b>>::DataOrDefault >,    
    {
        crate::map_w_default(self, f)
    }

    /// See [crate::map]
    #[inline]
    fn ref_map<F>(&self, f: F) -> Map<&Self, F>
    where
        for<'a, 'b> F: 
            UnaryFunction<<Self as HibitTreeTypes<'a>>::Data> +
            UnaryFunction<<Self as HibitTreeTypes<'a>>::DataUnchecked> +
            UnaryFunction<<Self as HibitTreeTypes<'a>>::DataOrDefault> +
    
            UnaryFunction<<<Self as HibitTreeTypes<'a>>::Cursor as HibitTreeCursorTypes<'b>>::Data > +
            UnaryFunction<<<Self as HibitTreeTypes<'a>>::Cursor as HibitTreeCursorTypes<'b>>::DataUnchecked > + 
            UnaryFunction<<<Self as HibitTreeTypes<'a>>::Cursor as HibitTreeCursorTypes<'b>>::DataOrDefault >,    
    {
        crate::map(self, f)
    }
    
    /// See [crate::map_w_default]
    #[inline]
    fn ref_map_w_default<F>(&self, f: F) -> Map<&Self, F, ConstTrue>
    where
        Self::DefaultData: IsConstTrue,
        for<'a, 'b> F: 
            UnaryFunction<<Self as HibitTreeTypes<'a>>::Data> +
            UnaryFunction<<Self as HibitTreeTypes<'a>>::DataUnchecked> +
            UnaryFunction<<Self as HibitTreeTypes<'a>>::DataOrDefault> +
    
            UnaryFunction<<<Self as HibitTreeTypes<'a>>::Cursor as HibitTreeCursorTypes<'b>>::Data > +
            UnaryFunction<<<Self as HibitTreeTypes<'a>>::Cursor as HibitTreeCursorTypes<'b>>::DataUnchecked > + 
            UnaryFunction<<<Self as HibitTreeTypes<'a>>::Cursor as HibitTreeCursorTypes<'b>>::DataOrDefault >,
    {
        crate::map_w_default(self, f)
    }       

    /// Index range this SparseHierarchy can handle - `0..width^depth`.
    /// 
    /// Indices outside of this range considered to be invalid.
    /// 
    /// Act as `const`.
    #[inline]
    /*const*/ fn index_range() -> RangeTo<usize> {
        RangeTo{ 
            end: <Self::LevelMask as BitBlock>::Size::VALUE.pow(Self::LevelCount::VALUE as _) 
        }
    }
}


/// [HibitTree] that is not a concrete collection.
/// 
/// Most results of operations are.
pub trait LazyHibitTree: HibitTree {
    /// Make a concrete collection from a lazy/virtual one.
    #[inline]
    fn materialize<T>(self) -> T
    where
        Self: RegularHibitTree,
        T: FromHibitTree<
            Self,
            LevelMask  = Self::LevelMask,
            LevelCount = Self::LevelCount,
        >
    {
        T::from_tree(self)
    }
    
    #[inline]
    fn materialize_filtered<T, F>(self, f: F) -> T
    where
        Self: RegularHibitTree,
        T: FromHibitTree<
            Self,
            LevelMask  = Self::LevelMask,
            LevelCount = Self::LevelCount,
        >,
        for<'a, 'b> F: UnaryFunction<&'a HibitTreeData<'b, Self>, Output=bool>
    {
        T::from_filtered_tree(self, f)
    }    
}

/// Construct a [HibitTree] collection from any [HibitTree].
pub trait FromHibitTree<From: RegularHibitTree>: HibitTree
where
    From: RegularHibitTree<
        LevelMask  = Self::LevelMask,
        LevelCount = Self::LevelCount,
    >
{
    fn from_tree(from: From) -> Self;
    
    fn from_filtered_tree<F>(from: From, f: F) -> Self
    where
        for<'a, 'b> F: UnaryFunction<&'a HibitTreeData<'b, From>, Output=bool>;
}

/// [HibitTreeCursor] lifetime-dependent types.
pub trait HibitTreeCursorTypes<'this, ImplicitBounds = &'this Self>{
    type Data;
    type DataUnchecked;
    type DataOrDefault;
}

/// Stateful [HibitTree] traverse interface.
/// 
/// Having state allows implementations to have cache level meta-info.
/// If level block changed seldom and not sporadically (like during iteration) -
/// this can get a significant performance boost, especially in generative [HibitTree]'ies.
/// 
/// Block levels must be selected top(0) to bottom(last N) level.
/// When you [select_level_node], all levels below considered **not** selected.
/// For example, for 3-level hierarchy you select level 0, 1, 2 and then you can
/// access data level. But if after that, you change/select level 1 block - 
/// you should select level 2 block too, before accessing data level again. 
/// Imagine that you are traversing a tree.
///
///[select_level_node]: Self::select_level_node    
///
/// # Example
/// 
/// For 2-level 64bit hierarchy:
///```
/// use hibit_tree::{HibitTreeTypes, HibitTreeCursor, Tree};
/// use hibit_tree::config::_64bit;
/// use hibit_tree::const_utils::ConstUsize;
/// 
/// type Array = Tree<usize, _64bit<2>>; 
/// let mut array = Array::default();
/// array.insert(201, 500);
/// 
/// let mut cursor = <Array as HibitTreeTypes>::Cursor::new(&array);
/// unsafe{
///    // Select the only level0 block (corresponds to array indices [0..4096))
///    let mask0 = cursor.select_level_node(&array, ConstUsize::<0>, 0);
///    // Select 4th level1 block (corresponds to array indices [192..256))
///    let mask1 = cursor.select_level_node(&array, ConstUsize::<1>, 3);
///    // Select 9th data block (array index 201)
///    let data = cursor.data(&array, 9);
/// 
///    assert_eq!(data, Some(&500));
/// }
/// ``` 
pub trait HibitTreeCursor<'tree>
where
	Self: for<'this> HibitTreeCursorTypes<'this>,
{
    type Tree: HibitTree;
    
    fn new(tree: &'tree Self::Tree) -> Self;
    
    /// Item at index may not exist. Will return empty mask in such case.
    unsafe fn select_level_node<N: ConstInteger>(
        &mut self,
        tree: &'tree Self::Tree,
        level_n: N,
        level_index: usize,
    ) -> <Self::Tree as HibitTree>::LevelMask;
    
    /// # Safety
    /// 
    /// * Pointed node must exist.
    /// * `level_n` must be valid.
    /// * Do not mix with `select_level_node`. 
    unsafe fn select_level_node_unchecked<N: ConstInteger>(
        &mut self,
        tree: &'tree Self::Tree,
        level_n: N,
        level_index: usize
    ) -> <Self::Tree as HibitTree>::LevelMask;
    
    // We need this for union operations.
    /// Item at `index` may not exist.
    /// 
    /// # Safety
    /// 
    /// * `index` must be within block range. 
    /// * Use only with [select_level_node].
    /// 
    /// [select_level_node]: Self::select_level_node
    unsafe fn data<'a>(
        &'a self,
        tree: &'tree Self::Tree,
        level_index: usize
    ) -> Option<<Self as HibitTreeCursorTypes<'a>>::Data>;      
 
    /// # Safety
    /// 
    /// Pointed data must exist.
    unsafe fn data_unchecked<'a>(
        &'a self,
        tree: &'tree Self::Tree,
        level_index: usize
    ) -> <Self as HibitTreeCursorTypes<'a>>::DataUnchecked;
    
    /// Return Default, if item at index does not exist.
    /// 
    /// # Safety
    /// 
    /// - Should be used with [select_level_node]. 
    /// - Unsafe to call if Self::Tree::DataValue is not true.
    /// 
    /// [select_level_node]: Self::select_level_node
    unsafe fn data_or_default<'a>(
        &'a self,
        tree: &'tree Self::Tree,
        level_index: usize
    ) -> <Self as HibitTreeCursorTypes<'a>>::DataOrDefault;
}

/// [HibitTree]::Data
pub type HibitTreeData<'a, T> = <T as HibitTreeTypes<'a>>::Data;
/// [MultiHibitTree]::Data
pub type MultiHibitTreeIterItem<'a, T> = <T as MultiHibitTreeTypes<'a>>::IterItem;

/// [RegularHibitTree] lifetime-dependent types.
/// 
/// This is actually requirement/bound for [HibitTreeTypes], that all
/// Data types are the same.  
pub trait RegularHibitTreeTypes<'this, ImplicitBounds = &'this Self>
    : HibitTreeTypes<'this, ImplicitBounds,
        DataUnchecked = <Self as HibitTreeTypes<'this, ImplicitBounds>>::Data,
        DataOrDefault = <Self as HibitTreeTypes<'this, ImplicitBounds>>::Data,
        Cursor: for<'a> HibitTreeCursorTypes<'a, 
            Data = Self::Data,
            DataUnchecked = Self::Data,
            DataOrDefault = Self::Data,
        >,
    >
{}

/// [HibitTree] where all Data types are the same.
/// [Data] = [DataUnchecked] = [Cursor::Data].
/// 
/// [Data]: HibitTreeTypes::Data
/// [DataUnchecked]: HibitTreeTypes::DataUnchecked
/// [Cursor::Data]: HibitTreeCursorTypes::Data
/// 
/// Think of it as "the usual" [HibitTree].
/// 
/// All containers and all "non-multi" operations results are `RegularHibitTree`. 
pub trait RegularHibitTree: HibitTree
where
    Self: for<'this> RegularHibitTreeTypes<'this>
{}

impl<'this, T> RegularHibitTreeTypes<'this> for T
where
    T: HibitTreeTypes<'this,
        DataUnchecked = <Self as HibitTreeTypes<'this>>::Data,
        DataOrDefault = <Self as HibitTreeTypes<'this>>::Data,
        Cursor: for<'a> HibitTreeCursorTypes<'a, 
            Data = Self::Data,
            DataUnchecked = Self::Data,
            DataOrDefault = Self::Data,
        >,
    >
{} 

// TODO: impl manually?
impl<T> RegularHibitTree for T
where
    T: HibitTree,
    T: for<'this> RegularHibitTreeTypes<'this>
{}

/// [MultiHibitTree] lifetime-dependent types. 
/// 
/// This is actually requirement/bound for [HibitTreeTypes], that all
/// Data types `impl Iterator<IterItem>`.
pub trait MultiHibitTreeTypes<'this, ImplicitBounds = &'this Self>
    : HibitTreeTypes<'this, ImplicitBounds, 
        Data: Iterator<Item=Self::IterItem>,
        DataUnchecked: Iterator<Item=Self::IterItem>,
        DataOrDefault: Iterator<Item=Self::IterItem>,
        Cursor: for<'a> HibitTreeCursorTypes<'a, 
            Data: Iterator<Item=Self::IterItem>,
            DataUnchecked: Iterator<Item=Self::IterItem>,
            DataOrDefault: Iterator<Item=Self::IterItem>,
        >,
    >
{
    /// [Iterator::Item] of all Data types: [Data], [DataUnchecked], 
    /// [HibitTreeCursor::Data], [HibitTreeCursor::DataUnchecked].
    /// 
    /// [Data]: HibitTreeTypes::Data
    /// [DataUnchecked]: HibitTreeTypes::DataUnchecked
    /// [HibitTreeCursor::Data]: HibitTreeCursorTypes::Data
    /// [HibitTreeCursor::DataUnchecked]: HibitTreeCursorTypes::DataUnchecked 
    type IterItem;
}

/// [HibitTree], where all Data types are `Iterator<Self::IterItem>`.
/// 
/// `multi_*` operations return [MultiHibitTree]'ies.
/// 
/// You can convert `MultiHibitTree` to [RegularHibitTree] with [map()].
///
/// [map()]: HibitTree::map()
pub trait MultiHibitTree: HibitTree
where
    Self: for<'this> MultiHibitTreeTypes<'this>
{
    /*/// See [crate::multi_map_fold].
    #[inline]
    fn map_fold<I, F>(self, init: I, f: F) -> MultiMapFold<Self, I, F>
    where 
        I: NullaryFunction,
        F: for<'a> BinaryFunction<
            I::Output, 
            <Self as MultiHibitTreeTypes<'a>>::IterItem,
            Output = I::Output
        >,    
    {
        multi_map_fold(self, init, f)
    }*/
}