doublets 0.3.0

Doublets (links) data structure implementation.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

use std::ptr::NonNull;

use crate::mem::traits::LinksTree;

use crate::{
    mem::split::{DataPart, IndexPart},
    Link,
};
use data::{LinkReference, LinksConstants};
use trees::IterativeSizeBalancedTree;

// TODO: why is there so much duplication in OOP!!! FIXME
pub(crate) struct InternalRecursionlessSizeBalancedTreeBase<T: LinkReference> {
    pub(crate) data: NonNull<[DataPart<T>]>,
    pub(crate) indexes: NonNull<[IndexPart<T>]>,
    pub(crate) r#break: T,
    pub(crate) r#continue: T,
}

impl<T: LinkReference> InternalRecursionlessSizeBalancedTreeBase<T> {
    pub(crate) fn new(
        constants: LinksConstants<T>,
        data: NonNull<[DataPart<T>]>,
        indexes: NonNull<[IndexPart<T>]>,
    ) -> Self {
        Self {
            data,
            indexes,
            r#break: constants.r#break,
            r#continue: constants.r#continue,
        }
    }
}

pub(crate) trait InternalRecursionlessSizeBalancedTreeBaseAbstract<T: LinkReference>:
    IterativeSizeBalancedTree<T> + LinksTree<T>
{
    fn get_index_part(&self, link: T) -> &IndexPart<T>;

    fn get_mut_index_part(&mut self, link: T) -> &mut IndexPart<T>;

    fn get_data_part(&self, link: T) -> &DataPart<T>;

    fn get_mut_data_part(&mut self, link: T) -> &mut DataPart<T>;

    fn get_tree_root(&self, link: T) -> T;

    fn get_base_part(&self, link: T) -> T;

    fn get_key_part(&self, link: T) -> T;

    fn get_link_value(&self, index: T) -> Link<T> {
        let link = self.get_data_part(index);
        Link::new(index, link.source, link.target)
    }

    fn search_core(&self, mut root: T, key: T) -> T {
        unsafe {
            while root != T::from_byte(0) {
                let root_key = self.get_key_part(root);
                if key < root_key {
                    root = self.get_left_or_default(root);
                } else if key > root_key {
                    root = self.get_right_or_default(root);
                } else {
                    return root;
                }
            }
            T::from_byte(0)
        }
    }

    fn count_usages_core(&self, link: T) -> T {
        unsafe { self.get_size_or_zero(self.get_tree_root(link)) }
    }
}