diff options
Diffstat (limited to '')
-rw-r--r-- | src/main_custom_ord.rs | 61 | ||||
-rw-r--r-- | src/main_mono.rs | 45 |
2 files changed, 106 insertions, 0 deletions
diff --git a/src/main_custom_ord.rs b/src/main_custom_ord.rs new file mode 100644 index 0000000..d5bb8f9 --- /dev/null +++ b/src/main_custom_ord.rs @@ -0,0 +1,61 @@ +use std::cmp::Ordering; + +trait Ord { + fn cmp(&self, other: &Self) -> Ordering; +} + +struct AVLNode<T: Ord> { + value: T, + left: AVLTree<T>, + right: AVLTree<T>, +} + +type AVLTree<T> = Option<Box<AVLNode<T>>>; + +struct AVLTreeSet<T: Ord> { + root: AVLTree<T>, +} + +impl<T: Ord> AVLTreeSet<T> { + pub fn new() -> Self { + Self { root: None } + } + + pub fn insert(&mut self, value: T) -> bool { + let mut current_tree = &mut self.root; + + while let Some(current_node) = current_tree { + match current_node.value.cmp(&value) { + Ordering::Less => current_tree = &mut current_node.right, + Ordering::Equal => return false, + Ordering::Greater => current_tree = &mut current_node.left, + } + } + + *current_tree = Some(Box::new(AVLNode { + value, + left: None, + right: None, + })); + + true + } +} + +impl Ord for u32 { + fn cmp(&self, other: &Self) -> Ordering { + if *self < *other { + Ordering::Less + } else if *self == *other { + Ordering::Equal + } else { + Ordering::Greater + } + } +} + +fn main() { + let mut tree = AVLTreeSet::new(); + tree.insert(3); + tree.insert(2); +} diff --git a/src/main_mono.rs b/src/main_mono.rs new file mode 100644 index 0000000..68da0ff --- /dev/null +++ b/src/main_mono.rs @@ -0,0 +1,45 @@ +use std::cmp::Ordering; + +struct AVLNode { + value: u32, + left: AVLTree, + right: AVLTree, +} + +type AVLTree = Option<Box<AVLNode>>; + +struct AVLTreeSet<T: Ord> { + root: AVLTree<T>, +} + +impl<T: Ord> AVLTreeSet<T> { + pub fn new() -> Self { + Self { root: None } + } + + pub fn insert(&mut self, value: T) -> bool { + let mut current_tree = &mut self.root; + + while let Some(current_node) = current_tree { + match current_node.value.cmp(&value) { + Ordering::Less => current_tree = &mut current_node.right, + Ordering::Equal => return false, + Ordering::Greater => current_tree = &mut current_node.left, + } + } + + *current_tree = Some(Box::new(AVLNode { + value, + left: None, + right: None, + })); + + true + } +} + +fn main() { + let mut tree = AVLTreeSet::new(); + tree.insert(3); + tree.insert(2); +} |