fork download
copy 
  1. use std::rc::Rc;
  2. use std::cell::RefCell;
  3. use std::fmt;
  4. type Handle<T> = Rc<RefCell<Option<Node<T>>>>;
  5. struct Node<T> {
  6.     level: i32,
  7.     value: T,
  8.     left: Handle<T>,
  9.     right: Handle<T>,
  10. }
  11. impl<T> Node<T> {
  12.     fn new(value: T) -> Node<T> {Node {level: 1i32, value: value, left: Node::none(), right: Node::none()}}
  13.     fn _handle(op: Option<Node<T>>) -> Handle<T> {Rc::new(RefCell::new(op))}
  14.     fn none() -> Handle<T> {Node::_handle(None)}
  15.     fn handle(value: T) -> Handle<T> {Node::_handle(Some(Node::new(value)))}
  16.     fn clone_left(&self) -> Handle<T> {Rc::clone(&self.left)}
  17.     fn clone_right(&self) -> Handle<T> {Rc::clone(&self.right)}
  18. }
  19. impl<T: fmt::Debug> fmt::Debug for Node<T> {
  20.     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
  21.         if let Some(l) = self.left.borrow().as_ref() {
  22.             if let Some(r) = self.right.borrow().as_ref() {
  23.                 write!(f, "[{:?}] {:?}:{} [{:?}]", l, self.value, self.level, r)
  24.             } else {
  25.                 write!(f, "[{:?}] {:?}:{}", l, self.value, self.level)
  26.             }
  27.         } else {
  28.             if let Some(r) = self.right.borrow().as_ref() {
  29.                 write!(f, "{:?}:{} [{:?}]", self.value, self.level, r)
  30.             } else {
  31.                 write!(f, "{:?}:{}", self.value, self.level)
  32.             }
  33.         }
  34.     }
  35. }
  36. trait HandleFunctions<T> {
  37.     fn recursive_left(&self) -> Handle<T>;
  38.     fn recursive_right(&self) -> Handle<T>;
  39.     fn to_op(&self) -> Option<Handle<T>>;
  40. }
  41. impl<T: Copy> HandleFunctions<T> for Handle<T> {
  42.     fn recursive_left(&self) -> Handle<T> {
  43.         match self.borrow().as_ref() {
  44.             Some(node) if !node.left.nil() => node.left.recursive_left(),
  45.             _ => Rc::clone(self),
  46.         }
  47.     }
  48.     fn recursive_right(&self) -> Handle<T> {
  49.         match self.borrow().as_ref() {
  50.             Some(node) if !node.right.nil() => node.right.recursive_right(),
  51.             _ => Rc::clone(self),
  52.         }
  53.     }
  54.     fn to_op(&self) -> Option<Handle<T>> {Some(Rc::clone(self))}
  55. }
  56. trait OptionHandleFunctions<T> {
  57.     fn nil(&self) -> bool;
  58.     fn level(&self) -> Option<i32>;
  59.     fn value(&self) -> Option<T>;
  60.     fn left(&self) -> Option<Handle<T>>;
  61.     fn right(&self) -> Option<Handle<T>>;
  62.     fn set_left(&self, op: Option<Handle<T>>);
  63.     fn set_right(&self, op: Option<Handle<T>>);
  64.     fn node<F>(&self, f: F) where F: Fn(&Node<T>);
  65.     fn node_mut<F>(&self, f: F) where F: Fn(&mut Node<T>);
  66. }
  67. impl<T: Copy> OptionHandleFunctions<T> for Handle<T> {
  68.     fn nil(&self) -> bool {self.borrow().is_none()}
  69.     fn level(&self) -> Option<i32> {self.borrow().as_ref().map(|node| node.level)}
  70.     fn value(&self) -> Option<T> {self.borrow().as_ref().map(|node| node.value)}
  71.     fn left(&self) -> Option<Handle<T>> {self.borrow().as_ref().map(|node| node.clone_left())}
  72.     fn right(&self) -> Option<Handle<T>> {self.borrow().as_ref().map(|node| node.clone_right())}
  73.     fn set_left(&self, op: Option<Handle<T>>) {
  74.         if let Some(h) = op {self.node_mut (|n| n.left = Rc::clone(&h))}
  75.     }
  76.     fn set_right(&self, op: Option<Handle<T>>) {
  77.         if let Some(h) = op {self.node_mut (|n| n.right = Rc::clone(&h))}
  78.     }
  79.     fn node<F>(&self, f: F) where F: Fn(&Node<T>) {
  80.         if let Some(node) = self.borrow().as_ref() {f(node)}
  81.     }
  82.     fn node_mut<F>(&self, f: F) where F: Fn(&mut Node<T>) {
  83.         if let Some(node) = self.borrow_mut().as_mut() {f(node)}
  84.     }
  85. }
  86. impl<T: Copy> OptionHandleFunctions<T> for Option<Handle<T>> {
  87.     fn nil(&self) -> bool {self.as_ref().map_or(true, |h| h.nil())}
  88.     fn level(&self) -> Option<i32> {self.as_ref().map_or(None, |h| h.level())}
  89.     fn value(&self) -> Option<T> {self.as_ref().map_or(None, |h| h.value())}
  90.     fn left(&self) -> Option<Handle<T>> {self.as_ref().map_or(None, |h| h.left())}
  91.     fn right(&self) -> Option<Handle<T>> {self.as_ref().map_or(None, |h| h.right())}
  92.     fn set_left(&self, op: Option<Handle<T>>) {if let Some(h) = self.as_ref() {h.set_left(op)}}
  93.     fn set_right(&self, op: Option<Handle<T>>) {if let Some(h) = self.as_ref() {h.set_right(op)}}
  94.     fn node<F>(&self, f: F) where F: Fn(&Node<T>) {if let Some(h) = self.as_ref() {h.node(f)}}
  95.     fn node_mut<F>(&self, f: F) where F: Fn(&mut Node<T>) {if let Some(h) = self.as_ref() {h.node_mut(f)}}
  96. }
  97. #[derive(Debug)]
  98. struct Tree<T> {
  99.     root: Handle<T>,
  100. }
  101. impl<T: PartialEq + PartialOrd + Copy + fmt::Debug> Tree<T> {
  102.     fn new() -> Tree<T> {Tree {root: Node::none()}}
  103.     fn add(&mut self, value: T) {self.root = Tree::insert(Rc::clone(&self.root), value)}
  104.     fn remove(&mut self, value: T) {self.root = Tree::delete(Rc::clone(&self.root), value)}
  105.     fn insert(h: Handle<T>, value: T) -> Handle<T> {
  106.         match h.borrow_mut().as_mut() {
  107.             None => return Node::handle(value),
  108.             Some(node) => {
  109.                 if value < node.value {
  110.                     node.left = Tree::insert(node.clone_left(), value);
  111.                 } else if node.value < value {
  112.                     node.right = Tree::insert(node.clone_right(), value);
  113.                 }
  114.             },
  115.         }
  116.         Tree::split(Tree::skew(h))
  117.     }
  118.     fn delete(mut h: Handle<T>, value: T) -> Handle<T> {
  119.         if h.nil() {return h}
  120.         if let Some(node) = h.borrow_mut().as_mut() {
  121.             if node.value < value {
  122.                 node.right = Tree::delete(node.clone_right(), value);
  123.             } else if value < node.value {
  124.                 node.left = Tree::delete(node.clone_left(), value);
  125.             } else {
  126.                 if node.left.nil() && node.right.nil() {
  127.                     return Node::none();
  128.                 } else if node.left.nil() {
  129.                     if let Some(successor_value) = node.right.recursive_left().value() {
  130.                         node.right = Tree::delete(node.clone_right(), successor_value);
  131.                         node.value = successor_value;
  132.                     }
  133.                 } else {
  134.                     if let Some(predecessor_value) = node.left.recursive_right().value() {
  135.                         node.left = Tree::delete(node.clone_left(), predecessor_value);
  136.                         node.value = predecessor_value;
  137.                     }
  138.                 }
  139.             }
  140.         }
  141.         h = Tree::skew(Tree::decrease_level(h));
  142.         h.node_mut(|n| n.right = Tree::skew(n.clone_right()));
  143.         h.right().node_mut(|n| n.right = Tree::skew(n.clone_right()));
  144.         h = Tree::split(h);
  145.         h.node_mut(|n| n.right = Tree::split(n.clone_right()));
  146.         h
  147.     }
  148.     fn skew(h: Handle<T>) -> Handle<T> {
  149.         if h.nil() {
  150.             Node::none()
  151.         } else if h.left().nil() {
  152.             h
  153.         } else if h.left().level() == h.level() {
  154.             let l = h.left();
  155.             h.set_left(l.right());
  156.             l.set_right(h.to_op());
  157.             l.unwrap_or(h)
  158.         } else {
  159.             h
  160.         }
  161.     }
  162.     fn split(h: Handle<T>) -> Handle<T> {
  163.         if h.nil() {
  164.             Node::none()
  165.         } else if h.right().nil() || h.right().right().nil() {
  166.             h
  167.         } else if h.level() == h.right().right().level() {
  168.             let r = h.right();
  169.             h.set_right(r.left());
  170.             r.set_left(h.to_op());
  171.             r.node_mut(|n| n.level += 1);
  172.             r.unwrap_or(h)
  173.         } else {
  174.             h
  175.         }
  176.     }
  177.     fn decrease_level(h: Handle<T>) -> Handle<T> {
  178.         let should_be = std::cmp::min(h.left().level(), h.right().level()).unwrap_or(1) + 1;
  179.         if Some(should_be) < h.level() {
  180.             h.node_mut(|n| n.level = should_be);
  181.             if Some(should_be) < h.right().level() {
  182.                 h.right().node_mut(|n| n.level = should_be);
  183.             }
  184.         }
  185.         h
  186.     }
  187. }
  188. fn main() {
  189.     let mut tree = Tree::new();
  190.     println!("{:?}", &tree);
  191.     tree.add(100);
  192.     println!("{:?}", &tree);
  193.     tree.add(200);
  194.     println!("{:?}", &tree);
  195.     tree.add(50);
  196.     println!("{:?}", &tree);
  197.     tree.add(300);
  198.     println!("{:?}", &tree);
  199.     println!("--");
  200.     tree.remove(100);
  201.     println!("{:?}", &tree);
  202.     tree.add(400);
  203.     println!("{:?}", &tree);
  204. }
  205.  
Success #stdin #stdout 0s 14880KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Tree { root: RefCell { value: None } }
Tree { root: RefCell { value: Some(100:1) } }
Tree { root: RefCell { value: Some(100:1 [200:1]) } }
Tree { root: RefCell { value: Some([50:1] 100:2 [200:1]) } }
Tree { root: RefCell { value: Some([50:1] 100:2 [200:1 [300:1]]) } }
--
Tree { root: RefCell { value: Some(50:2 [200:1 [300:1]]) } }
Tree { root: RefCell { value: Some(50:2 [[200:1] 300:2 [400:1]]) } }
https://ideone.com/XBh9VX
language:
Rust (rust 1.56)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!