dsalgo/binary_tree.rs
1use crate::{
2 height::Height,
3 insertion::Insert,
4 join::Join,
5 pop::Pop,
6 size::Size,
7 split::Split,
8 tree_node::{
9 Parent,
10 ParentMut,
11 },
12};
13
14#[cfg(test)]
15
16mod tests {
17
18 #[test]
19
20 fn test() {
21 use super::*;
22
23 #[derive(Clone, Debug)]
24
25 struct Node<T> {
26 data: T,
27 left: Option<Box<Self>>,
28 right: Option<Box<Self>>,
29 }
30
31 struct Tree<V> {
32 root: Option<V>,
33 }
34
35 impl<V> From<Option<Box<V>>> for Tree<V> {
36 fn from(root: Option<Box<V>>) -> Self {
37 if let Some(root) = root {
38 Tree { root: Some(*root) }
39 } else {
40 Tree { root: None }
41 }
42 }
43 }
44
45 impl<T> Node<T> {
46 fn new(data: T) -> Self {
47 Node { data, left: None, right: None }
48 }
49 }
50
51 impl<T> Size for Option<Node<T>>
52 where
53 T: Size,
54 {
55 fn size(&self) -> usize {
56 match self {
57 Some(node) => node.data.size(),
58 None => 0,
59 }
60 }
61 }
62
63 impl<T: Size> Split<usize> for Option<Node<T>> {
64 // pseudo
65 fn split(
66 mut self,
67 index: usize,
68 ) -> (Self, Self) {
69 assert!(index <= self.size());
70
71 (None, None)
72 }
73 }
74
75 impl<T> Join for Option<Node<T>> {
76 // pseudo
77 fn join(
78 self,
79 rhs: Self,
80 ) -> Self {
81 None
82 }
83 }
84
85 impl<T> Pop for Tree<T>
86 where
87 Option<T>: Split<usize> + Join + Size,
88 {
89 type Data = T;
90
91 fn pop(
92 &mut self,
93 index: usize,
94 ) -> Self::Data {
95 assert!(self.root.is_some());
96
97 let size = self.root.size();
98
99 assert!(size > 0 && index < size);
100
101 let (lhs, rhs) = self.root.take().split(index);
102
103 let (popped, rhs) = rhs.split(1);
104
105 self.root = lhs.join(rhs);
106
107 popped.unwrap()
108 }
109 }
110
111 impl<T> Insert for Tree<T>
112 where
113 Option<T>: Split<usize> + Join + Size,
114 {
115 type Data = T;
116
117 fn insert(
118 &mut self,
119 index: usize,
120 data: Self::Data,
121 ) {
122 let size = self.root.size();
123 }
124 }
125 }
126}
127
128// pub struct BinaryTree<K, V> {
129// key: K,
130// value: V,
131// left: Option<Box<Self>>,
132// right: Option<Box<Self>>,
133// // size: usize,
134// }
135// impl<K: PartialOrd, V> BinaryTree<K, V> {
136// pub fn get_size(&self) -> usize { 1 +
137// self.left.get_size() + self.right.get_size() }
138// pub fn update(&mut self) { self.size = self.get_size();
139// }
140// pub fn rotate_left(&mut self) {
141// assert!(self.right.left.is_some());
142// let mut new_root = self.right.left.take().unwrap();
143// assert!(self.right.left.is_none());
144// self.right.left = new_root.right.take();
145// self.update();
146// new_root.right = Some(self);
147// self.update();
148// *self = new_root;
149// }
150// pub fn rotate_right(&mut self) {
151// assert!(self.left.right.is_some());
152// let mut new_root = self.left.right.take().unwrap();
153// assert!(self.left.right.is_none());
154// self.left.right = new_root.left.take();
155// self.update();
156// new_root.left = Some(self);
157// self.update();
158// *self = new_root;
159// }
160// // pub fn splay(root: Option<BinaryTree<K, V>>, key: &K)
161// -> // Option<BinaryTree<K, V>> { if root.is_none() {
162// // return None;
163// // }
164// // let mut root = root.unwrap();
165// // if &root.key == key {
166// // return Some(root);
167// // }
168// // if key < &root.key {
169// // if root.left.is_none() {
170// // return Some(root);
171// // }
172// // }
173// // }
174// }
175// pub trait BinaryTreeNode {}
176// pub trait Childs {
177// fn left(&self) -> &Option<Box<Self>>;
178// fn right(&self) -> &Option<Box<Self>>;
179// }
180// pub trait Size {
181// fn size(&self) -> usize;
182// }
183// pub trait GetSize {
184// fn get_size(_: &Option<Box<Self>>) -> usize;
185// }
186// impl<K, V> Childs for Node<K, V> {
187// fn left(&self) -> &Option<Box<Self>> { &self.left }
188// fn right(&self) -> &Option<Box<Self>> { &self.right }
189// }
190// impl<K, V> Size for Node<K, V> {
191// fn size(&self) -> usize { self.size }
192// }
193// impl<K, V> GetSize for Node<K, V> {
194// fn get_size(root: &Option<Box<Self>>) -> usize {
195// if let Some(root) = root { root.size } else { 0 }
196// }
197// }
198// pub trait Update {
199// fn update(&mut self);
200// }
201// impl<K, V> Update for Node<K, V> {
202// fn update(&mut self) {
203// self.size = Self::get_size(&self.left) +
204// Self::get_size(&self.right) + 1; }
205// }
206// pub trait Rotation {
207// // fn rotate_left(root: Box<Self>) -> Box<Self>;
208// // fn rotate_right(root: Self) -> Self>;
209// fn rotate_left(self) -> Box<Self>;
210// fn rotate_right(self) -> Box<Self>;
211// }
212// impl<T: Childs> Rotation for T {
213// fn rotate_left(mut self) -> Box<Self> {
214// assert!(self.right().is_some());
215// let mut new_root = self.right().take().unwrap();
216// assert!(self.right().is_none());
217// self.right() = new_root.left().take();
218// self.update();
219// new_root.left = Some(Box::new(self));
220// new_root.update();
221// new_root
222// }
223// fn rotate_right(mut self) -> Box<Self> {
224// let mut new_root = self.left.take().unwrap();
225// self.left = new_root.right.take();
226// self.update();
227// new_root.right = Some(Box::new(self));
228// new_root.update();
229// new_root
230// }
231// }
232// #[cfg(test)]
233// mod tests {
234// #[test]
235// fn test() { let mut node = super::BinaryTree::new(1, 1);
236// } }