splay_tree_rs/
node.rs

1use std::cell::RefCell;
2use std::fmt::Debug;
3use std::mem;
4use std::rc::Rc;
5
6#[derive(Clone, Debug)]
7pub struct Node<K> {
8    pub left: SplayNode<K>,
9    pub right: SplayNode<K>,
10    pub key: K,
11}
12
13pub type SplayNode<K> = Option<Rc<RefCell<Node<K>>>>;
14
15impl<K: Ord> PartialEq for Node<K> {
16    fn eq(&self, other: &Self) -> bool {
17        self.key == other.key && self.left == other.left && self.right == other.right
18    }
19    fn ne(&self, other: &Self) -> bool {
20        !self.eq(other)
21    }
22}
23
24impl<K: Ord + Clone + Debug> Node<K> {
25    pub fn new(k: K) -> Rc<RefCell<Self>> {
26        Rc::new(RefCell::new(Node {
27            left: None,
28            right: None,
29            key: k,
30        }))
31    }
32
33    pub fn insert_left_most(&mut self, inserted: SplayNode<K>) {
34        if inserted.is_none() {
35            return;
36        }
37        let mut temp = self;
38
39        if let Some(ref mut current) = temp.left {
40            if current.borrow().left.is_none() {
41                current.borrow_mut().left = inserted;
42            } else {
43                current.borrow_mut().insert_left_most(inserted);
44            }
45        } else {
46            temp.left = inserted;
47        }
48    }
49
50    pub fn insert_right_most(&mut self, inserted: SplayNode<K>) {
51        if inserted.is_none() {
52            return;
53        }
54        let mut temp = self;
55
56        if let Some(ref mut current) = temp.right {
57            if current.borrow().right.is_none() {
58                current.borrow_mut().right = inserted;
59            } else {
60                current.borrow_mut().insert_right_most(inserted);
61            }
62        } else {
63            temp.right = inserted;
64        }
65    }
66
67    pub fn left_most_key(&self) -> K {
68        if let Some(ref left) = self.left {
69            return left.borrow().left_most_key();
70        } else {
71            return self.key.clone();
72        }
73    }
74
75    pub fn right_most_key(&self) -> K {
76        if let Some(ref right) = self.right {
77            return right.borrow().right_most_key();
78        } else {
79            return self.key.clone();
80        }
81    }
82
83    pub fn bstinsert(&mut self, inserted: &mut Rc<RefCell<Node<K>>>) {
84        let key = inserted.borrow().key.clone();
85        if self.key == key {
86            let mut temp = mem::take(&mut self.left);
87
88            // new node inserted to self's left
89            self.left = Some(inserted.clone());
90
91            // update nodes
92            self.left.as_mut().unwrap().borrow_mut().left = temp;
93        } else if self.key > key {
94            if self.left.is_some() {
95                self.left.as_mut().unwrap().borrow_mut().bstinsert(inserted);
96            } else {
97                // insert node as left child
98                self.left = Some(inserted.clone());
99            }
100        } else if self.key < key {
101            if self.right.is_some() {
102                self.right
103                    .as_mut()
104                    .unwrap()
105                    .borrow_mut()
106                    .bstinsert(inserted);
107            } else {
108                // insert node as right child
109                self.right = Some(inserted.clone());
110            }
111        }
112    }
113}
splay_tree_rs/node.rs

splay_tree_rs/
node.rs
