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

pub mod search_tree;

use core::mem::MaybeUninit;
use core::ptr;

use crate::allocator::Nodable;

#[derive(Debug)]
pub struct TreeNode<K, V> {
    pub key: MaybeUninit<K>,
    pub right: *mut TreeNode<K, V>,
    pub left: TreePtr<K, V>,
}

impl<K, V> Default for TreeNode<K, V> {
    fn default() -> Self {
        Self {
            key: MaybeUninit::uninit(),
            right: ptr::null_mut(),
            left: TreePtr::Null,
        }
    }
}

impl<K, V> Nodable for TreeNode<K, V> {
    fn next(&self) -> *mut Self {
        self.right
    }

    fn next_mut(&mut self) -> &mut *mut Self {
        &mut self.right
    }
}

#[derive(Debug, Default)]
pub enum TreePtr<K, V> {
    #[default]
    Null,
    Node(*mut TreeNode<K, V>),
    Val(*mut V),
}

impl<K, V> Clone for TreePtr<K, V> {
    fn clone(&self) -> Self {
        *self
    }
}

impl<K, V> Copy for TreePtr<K, V> {}

impl<K, V> TreePtr<K, V> {
    pub fn is_null(&self) -> bool {
        matches!(self, Self::Null)
    }

    pub fn is_val(&self) -> bool {
        matches!(self, Self::Val(_))
    }

    pub fn is_node(&self) -> bool {
        matches!(self, Self::Node(_))
    }

    pub fn as_node(&self) -> *mut TreeNode<K, V> {
        match *self {
            Self::Node(ptr) => ptr,
            _ => panic!("tree pointer is not a node"),
        }
    }

    pub fn as_val(&self) -> *mut V {
        match *self {
            Self::Val(ptr) => ptr,
            _ => panic!("tree pointer is not a value"),
        }
    }

    pub fn as_val_mut(&mut self) -> &mut *mut V {
        match self {
            Self::Val(ptr) => ptr,
            _ => panic!("tree pointer is not a value"),
        }
    }
}

impl<K, V> TreeNode<K, V> {
    pub fn is_empty(&self) -> bool {
        self.left.is_null() && self.right.is_null()
    }

    pub fn is_leaf(&self) -> bool {
        self.left.is_val() && self.right.is_null()
    }

    pub fn has_subtrees(&self) -> bool {
        self.left.is_node() && !self.right.is_null()
    }

    pub fn left_rotation(&mut self) {
        assert!(
            self.has_subtrees() && unsafe { (*self.right).has_subtrees() },
            "invalid left rotation"
        );
        unsafe {
            let tmp_node = self.left;
            let tmp_key = self.key.assume_init_read();
            self.left = TreePtr::Node(self.right);
            self.key = MaybeUninit::new((*self.right).key.assume_init_read());
            self.right = (*(self.left).as_node()).right;
            (*(self.left).as_node()).right = (*(self.left).as_node()).left.as_node();
            (*(self.left).as_node()).left = tmp_node;
            (*(self.left).as_node()).key = MaybeUninit::new(tmp_key);
        }
    }

    pub fn right_rotation(&mut self) {
        assert!(
            self.has_subtrees() && unsafe { (*(self.left).as_node()).has_subtrees() },
            "invalid right rotation"
        );
        unsafe {
            let tmp_node = self.right;
            let tmp_key = self.key.assume_init_read();
            self.right = self.left.as_node();
            self.key = MaybeUninit::new((*self.left.as_node()).key.assume_init_read());
            self.left = (*self.right).left;
            (*self.right).left = TreePtr::Node((*self.right).right);
            (*self.right).right = tmp_node;
            (*self.right).key = MaybeUninit::new(tmp_key);
        }
    }
}