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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133

mod iter;
mod node;
mod update;

pub use iter::AvltrieeIter;
pub use node::AvltrieeNode;
pub use update::AvltrieeHolder;

use std::{cmp::Ordering, mem::ManuallyDrop, ops::Deref};

#[derive(Debug)]
pub struct Found {
    row: u32,
    ord: Ordering,
}
impl Found {
    #[inline(always)]
    pub fn row(&self) -> u32 {
        self.row
    }

    #[inline(always)]
    pub fn ord(&self) -> Ordering {
        self.ord
    }
}

pub struct Avltriee<T> {
    node_list: ManuallyDrop<Box<AvltrieeNode<T>>>,
}

impl<T> Avltriee<T> {
    #[inline(always)]
    pub fn new(node_list: *mut AvltrieeNode<T>) -> Avltriee<T> {
        Avltriee {
            node_list: ManuallyDrop::new(unsafe { Box::from_raw(node_list) }),
        }
    }

    #[inline(always)]
    pub unsafe fn node<'a>(&self, row: u32) -> Option<&'a AvltrieeNode<T>> {
        let node = self.offset(row);
        (node.height > 0).then_some(node)
    }

    #[inline(always)]
    pub unsafe fn value<'a>(&self, row: u32) -> Option<&'a T> {
        self.node(row).map(|x| x.deref())
    }

    #[inline(always)]
    pub unsafe fn value_unchecked<'a>(&self, row: u32) -> &'a T {
        self.offset(row)
    }

    #[inline(always)]
    pub fn root(&self) -> u32 {
        self.node_list.parent
    }

    #[inline(always)]
    pub fn search_end<F>(&self, cmp: F) -> Found
    where
        F: Fn(&T) -> Ordering,
    {
        let mut row = self.root();
        let mut ord = Ordering::Equal;
        while row != 0 {
            let node = unsafe { self.offset(row) };
            ord = cmp(node);
            match ord {
                Ordering::Greater => {
                    if node.left == 0 {
                        break;
                    }
                    row = node.left;
                }
                Ordering::Equal => {
                    break;
                }
                Ordering::Less => {
                    if node.right == 0 {
                        break;
                    }
                    row = node.right;
                }
            }
        }
        Found { row, ord }
    }

    #[inline(always)]
    pub unsafe fn is_unique(&self, row: u32) -> bool {
        let node = self.offset(row);
        node.same == 0 && self.offset(node.parent).same != row
    }

    #[inline(always)]
    unsafe fn offset<'a>(&self, offset: u32) -> &'a AvltrieeNode<T> {
        &*(self.node_list.as_ref() as *const AvltrieeNode<T>).offset(offset as isize)
    }

    #[inline(always)]
    unsafe fn offset_mut<'a>(&mut self, offset: u32) -> &'a mut AvltrieeNode<T> {
        &mut *(self.node_list.as_mut() as *mut AvltrieeNode<T>).offset(offset as isize)
    }

    #[inline(always)]
    fn min(&self, t: u32) -> u32 {
        let mut t = t;
        while t != 0 {
            let l = unsafe { self.offset(t) }.left;
            if l == 0 {
                break;
            }
            t = l;
        }
        t
    }

    #[inline(always)]
    fn max(&self, t: u32) -> u32 {
        let mut t = t;
        while t != 0 {
            let r = unsafe { self.offset(t) }.right;
            if r == 0 {
                break;
            }
            t = r;
        }
        t
    }
}