SHARE
TWEET

Untitled

a guest Aug 20th, 2019 74 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #![allow(unused)]
  2.  
  3. #[derive(Debug, PartialEq)]
  4. enum BST<T> {
  5.     Empty,
  6.     Node {
  7.         value: T,
  8.         left: Box<BST<T>>,
  9.         right: Box<BST<T>>,
  10.     }
  11. }
  12.  
  13. impl<T: PartialOrd> BST<T> {
  14.     /// Return leaf node
  15.     fn leaf(value: T) -> Self {
  16.         BST::Node{
  17.             value,
  18.             left: Box::new(BST::Empty),
  19.             right: Box::new(BST::Empty),
  20.         }
  21.     }
  22.  
  23.     /// Associate function
  24.     fn is_empty(&self) -> bool {
  25.         matches::matches!(*self, BST::Empty)
  26.     }
  27.  
  28.     /// Output an iterator with in-order-traversal
  29.     fn in_order_iter(&'static self) -> Box<dyn Iterator<Item = &T>> {
  30.         match self {
  31.             BST::Empty => Box::new(std::iter::empty()) as Box<dyn Iterator<Item = &T>>,
  32.             BST::Node { value, left, right } => Box::new(
  33.                 left.in_order_iter()
  34.                     .chain(std::iter::once(value))
  35.                     .chain(right.in_order_iter())
  36.             ) as Box<dyn Iterator<Item = &T>>,
  37.         }
  38.     }
  39. }
  40.  
  41. impl<T: PartialOrd> BST<T> {
  42.     /// Insert a node
  43.     fn insert(&mut self, to_insert: T) {
  44.         match self {
  45.             BST::Empty => *self = BST::leaf(to_insert),
  46.             BST::Node {value, left, right} => {
  47.                 if to_insert < *value {
  48.                     left.insert(to_insert);
  49.                 } else {
  50.                     right.insert(to_insert);
  51.                 }
  52.             },
  53.         }
  54.     }
  55.    
  56.     /// Get mutable min value ref
  57.     fn min_mut(&mut self) -> Option<&mut T> {
  58.         match self {
  59.             BST::Empty => None,
  60.             BST::Node {value, left, ..} => {
  61.                 if left.is_empty() {
  62.                     Some(value)
  63.                 } else {
  64.                     left.min_mut()
  65.                 }
  66.             }
  67.         }
  68.     }
  69.    
  70.     /// Remove a node
  71.     fn remove(&mut self, to_remove: T) {
  72.         match self {
  73.             BST::Empty => {},
  74.             BST::Node {value, left, right} => {
  75.                 if to_remove < *value {
  76.                     left.remove(to_remove);
  77.                 } else if to_remove > *value {
  78.                     right.remove(to_remove);
  79.                 } else {
  80.                     match (&**left, &**right) {
  81.                         (BST::Empty, BST::Empty) => (),
  82.                         (_, BST::Empty) => *self = std::mem::replace(&mut **left, BST::Empty),
  83.                         (BST::Empty, _) => *self = std::mem::replace(&mut **right, BST::Empty),
  84.                         _ => {
  85.                             std::mem::swap(value, right.min_mut().unwrap());
  86.                             right.remove(to_remove);
  87.                         }
  88.                     }
  89.                 }
  90.             }
  91.         }
  92.     }
  93. }
  94.  
  95. fn main() {
  96.     let root = BST::leaf(5);
  97.     dbg!(root.is_empty());
  98.     dbg!(root);
  99. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top