Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #![allow(unused)]
- #[derive(Debug, PartialEq)]
- enum BST<T> {
- Empty,
- Node {
- value: T,
- left: Box<BST<T>>,
- right: Box<BST<T>>,
- }
- }
- impl<T: PartialOrd> BST<T> {
- /// Return leaf node
- fn leaf(value: T) -> Self {
- BST::Node{
- value,
- left: Box::new(BST::Empty),
- right: Box::new(BST::Empty),
- }
- }
- /// Associate function
- fn is_empty(&self) -> bool {
- matches::matches!(*self, BST::Empty)
- }
- /// Output an iterator with in-order-traversal
- fn in_order_iter(&'static self) -> Box<dyn Iterator<Item = &T>> {
- match self {
- BST::Empty => Box::new(std::iter::empty()) as Box<dyn Iterator<Item = &T>>,
- BST::Node { value, left, right } => Box::new(
- left.in_order_iter()
- .chain(std::iter::once(value))
- .chain(right.in_order_iter())
- ) as Box<dyn Iterator<Item = &T>>,
- }
- }
- }
- impl<T: PartialOrd> BST<T> {
- /// Insert a node
- fn insert(&mut self, to_insert: T) {
- match self {
- BST::Empty => *self = BST::leaf(to_insert),
- BST::Node {value, left, right} => {
- if to_insert < *value {
- left.insert(to_insert);
- } else {
- right.insert(to_insert);
- }
- },
- }
- }
- /// Get mutable min value ref
- fn min_mut(&mut self) -> Option<&mut T> {
- match self {
- BST::Empty => None,
- BST::Node {value, left, ..} => {
- if left.is_empty() {
- Some(value)
- } else {
- left.min_mut()
- }
- }
- }
- }
- /// Remove a node
- fn remove(&mut self, to_remove: T) {
- match self {
- BST::Empty => {},
- BST::Node {value, left, right} => {
- if to_remove < *value {
- left.remove(to_remove);
- } else if to_remove > *value {
- right.remove(to_remove);
- } else {
- match (&**left, &**right) {
- (BST::Empty, BST::Empty) => (),
- (_, BST::Empty) => *self = std::mem::replace(&mut **left, BST::Empty),
- (BST::Empty, _) => *self = std::mem::replace(&mut **right, BST::Empty),
- _ => {
- std::mem::swap(value, right.min_mut().unwrap());
- right.remove(to_remove);
- }
- }
- }
- }
- }
- }
- }
- fn main() {
- let root = BST::leaf(5);
- dbg!(root.is_empty());
- dbg!(root);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement