fork download
copy 
  1. use std::rc::Rc;
  2. use std::fmt;
  3. type Handle<T> = Option<Box<Node<T>>>;
  4. struct Node<T> {
  5.     level: i32,
  6.     value: T,
  7.     left: Handle<T>,
  8.     right: Handle<T>,
  9. }
  10. impl<T> Node<T> {
  11.     fn new(value: T) -> Node<T> {Node {level: 1i32, value: value, left: None, right: None}}
  12.     fn handle(value: T) -> Handle<T> {Some(Box::new(Node::new(value)))}
  13. }
  14. impl<T: fmt::Debug> fmt::Debug for Node<T> {
  15.     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
  16.         if let Some(l) = self.left.as_ref() {
  17.             if let Some(r) = self.right.as_ref() {
  18.                 write!(f, "[{:?}] {:?}:{} [{:?}]", l, self.value, self.level, r)
  19.             } else {
  20.                 write!(f, "[{:?}] {:?}:{}", l, self.value, self.level)
  21.             }
  22.         } else {
  23.             if let Some(r) = self.right.as_ref() {
  24.                 write!(f, "{:?}:{} [{:?}]", self.value, self.level, r)
  25.             } else {
  26.                 write!(f, "{:?}:{}", self.value, self.level)
  27.             }
  28.         }
  29.     }
  30. }
  31. trait HandleFunctions<T> {
  32.     fn recursive_left(&self) -> &Handle<T>;
  33.     fn recursive_right(&self) -> &Handle<T>;
  34.     fn take_left(&mut self) -> Handle<T>;
  35.     fn take_right(&mut self) -> Handle<T>;
  36. }
  37. impl<T> HandleFunctions<T> for Handle<T> {
  38.     fn recursive_left(&self) -> &Handle<T> {
  39.         match self.as_ref() {
  40.             Some(node) if node.left.is_some() => node.left.recursive_left(),
  41.             _ => self,
  42.         }
  43.     }
  44.     fn recursive_right(&self) -> &Handle<T> {
  45.         match self.as_ref() {
  46.             Some(node) if node.right.is_some() => node.right.recursive_right(),
  47.             _ => self
  48.         }
  49.     }
  50.     fn take_left(&mut self) -> Handle<T> {
  51.         self.as_mut().map_or(None, |node| node.left.take())
  52.     }
  53.     fn take_right(&mut self) -> Handle<T> {
  54.         self.as_mut().map_or(None, |node| node.right.take())
  55.     }
  56. }
  57. trait OptionHandleFunctions<T> {
  58.     fn nil(&self) -> bool;
  59.     fn level(&self) -> Option<i32>;
  60.     fn value(&self) -> Option<T>;
  61.     fn left(&mut self) -> Option<&mut Handle<T>>;
  62.     fn right(&mut self) -> Option<&mut Handle<T>>;
  63.     fn node<F>(&self, f: F) where F: FnOnce(&Node<T>);
  64.     fn node_mut<F>(&mut self, f: F) where F: FnOnce(&mut Node<T>);
  65. }
  66. impl<T: Clone> OptionHandleFunctions<T> for Handle<T> {
  67.     fn nil(&self) -> bool {self.is_none()}
  68.     fn level(&self) -> Option<i32> {self.as_ref().map(|node| node.level)}
  69.     fn value(&self) -> Option<T> {self.as_ref().map(|node| node.value.clone())}
  70.     fn left(&mut self) -> Option<&mut Handle<T>> {self.as_mut().map(|node| &mut node.left)}
  71.     fn right(&mut self) -> Option<&mut Handle<T>> {self.as_mut().map(|node| &mut node.right)}
  72.     fn node<F>(&self, f: F) where F: FnOnce(&Node<T>) {
  73.         if let Some(node) = self.as_ref() {f(node)}
  74.     }
  75.     fn node_mut<F>(&mut self, f: F) where F: FnOnce(&mut Node<T>) {
  76.         if let Some(node) = self.as_mut() {f(node)}
  77.     }
  78. }
  79. impl<'a, T: Clone> OptionHandleFunctions<T> for Option<&'a mut Handle<T>> {
  80.     fn nil(&self) -> bool {self.as_ref().map_or(true, |h| h.nil())}
  81.     fn level(&self) -> Option<i32> {self.as_ref().map_or(None, |h| h.level())}
  82.     fn value(&self) -> Option<T> {self.as_ref().map_or(None, |h| h.value())}
  83.     fn left(&mut self) -> Option<&mut Handle<T>> {self.as_mut().map_or(None, |h| h.left())}
  84.     fn right(&mut self) -> Option<&mut Handle<T>> {self.as_mut().map_or(None, |h| h.right())}
  85.     fn node<F>(&self, f: F) where F: FnOnce(&Node<T>) {if let Some(h) = self.as_ref() {h.node(f)}}
  86.     fn node_mut<F>(&mut self, f: F) where F: FnOnce(&mut Node<T>) {if let Some(h) = self.as_mut() {h.node_mut(f)}}
  87. }
  88. #[derive(Debug)]
  89. struct Tree<T> {
  90.     root: Handle<T>,
  91. }
  92. impl<T: PartialEq + PartialOrd + Clone + fmt::Debug> Tree<T> {
  93.     fn new() -> Tree<T> {Tree {root: None}}
  94.     fn add(&mut self, value: T) {self.root = Tree::insert(self.root.take(), value)}
  95.     fn remove(&mut self, value: T) {self.root = Tree::delete(self.root.take(), value)}
  96.     fn insert(mut h: Handle<T>, value: T) -> Handle<T> {
  97.         match h.as_mut() {
  98.             None => return Node::handle(value),
  99.             Some(node) => {
  100.                 if value < node.value {
  101.                     node.left = Tree::insert(node.left.take(), value);
  102.                 } else if node.value < value {
  103.                     node.right = Tree::insert(node.right.take(), value);
  104.                 }
  105.             },
  106.         }
  107.         Tree::split(Tree::skew(h))
  108.     }
  109.     fn delete(mut h: Handle<T>, value: T) -> Handle<T> {
  110.         if h.nil() {return h}
  111.         if let Some(node) = h.as_mut() {
  112.             if node.value < value {
  113.                 node.right = Tree::delete(node.right.take(), value);
  114.             } else if value < node.value {
  115.                 node.left = Tree::delete(node.left.take(), value);
  116.             } else {
  117.                 if node.left.nil() && node.right.nil() {
  118.                     return None;
  119.                 } else if node.left.nil() {
  120.                     if let Some(successor_value) = node.right.recursive_left().value() {
  121.                         node.right = Tree::delete(node.right.take(), successor_value.clone());
  122.                         node.value = successor_value;
  123.                     }
  124.                 } else {
  125.                     if let Some(predecessor_value) = node.left.recursive_right().value() {
  126.                         node.left = Tree::delete(node.left.take(), predecessor_value.clone());
  127.                         node.value = predecessor_value;
  128.                     }
  129.                 }
  130.             }
  131.         }
  132.         h = Tree::skew(Tree::decrease_level(h));
  133.         h.node_mut(|n| n.right = Tree::skew(n.right.take()));
  134.         h.right().node_mut(|n| n.right = Tree::skew(n.right.take()));
  135.         h = Tree::split(h);
  136.         h.node_mut(|n| n.right = Tree::split(n.right.take()));
  137.         h
  138.     }
  139.     fn skew(mut h: Handle<T>) -> Handle<T> {
  140.         if h.nil() {
  141.             None
  142.         } else if h.left().nil() {
  143.             h
  144.         } else if h.left().level() == h.level() {
  145.             let mut l = h.take_left();
  146.             h.node_mut(|n| n.left = l.take_right());
  147.             l.node_mut(|n| n.right = h);
  148.             l
  149.         } else {
  150.             h
  151.         }
  152.     }
  153.     fn split(mut h: Handle<T>) -> Handle<T> {
  154.         if h.nil() {
  155.             None
  156.         } else if h.right().nil() || h.right().right().nil() {
  157.             h
  158.         } else if h.level() == h.right().right().level() {
  159.             let mut r = h.take_right();
  160.             h.node_mut(|n| n.right = r.take_left());
  161.             r.node_mut(|n| n.left = h);
  162.             r.node_mut(|n| n.level += 1);
  163.             r
  164.         } else {
  165.             h
  166.         }
  167.     }
  168.     fn decrease_level(mut h: Handle<T>) -> Handle<T> {
  169.         let should_be = std::cmp::min(h.left().level(), h.right().level()).unwrap_or(1) + 1;
  170.         if Some(should_be) < h.level() {
  171.             h.node_mut(|n| n.level = should_be);
  172.             if Some(should_be) < h.right().level() {
  173.                 h.right().node_mut(|n| n.level = should_be);
  174.             }
  175.         }
  176.         h
  177.     }
  178. }
  179. #[derive(PartialOrd, PartialEq, Clone)]
  180. struct Huge {name: &'static str,} // '
  181. impl Huge {fn new(name: &'static str) -> Huge {Huge {name: name}}} // '
  182. impl Drop for Huge {fn drop(&mut self) {println!("> Dropping {}", self.name)}}
  183. impl fmt::Debug for Huge {
  184.     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {write!(f, "{:?}", self.name)}
  185. }
  186. #[derive(Debug)]
  187. struct TreeAua<T> { // avoid unnecessary allocations.
  188.     root: Handle<Rc<T>>,
  189. }
  190. impl<T: PartialEq + PartialOrd + Clone + fmt::Debug> TreeAua<T> {
  191.     fn new() -> TreeAua<T> {TreeAua {root: None}}
  192.     fn add(&mut self, value: T) {self.root = Tree::insert(self.root.take(), Rc::new(value))}
  193.     fn remove(&mut self, value: T) {self.root = Tree::delete(self.root.take(), Rc::new(value))}
  194. }
  195. fn main() {
  196.     let mut tree = TreeAua::new();
  197.     println!("{:?}", &tree);
  198.     tree.add(100);
  199.     println!("{:?}", &tree);
  200.     tree.add(200);
  201.     println!("{:?}", &tree);
  202.     tree.add(50);
  203.     println!("{:?}", &tree);
  204.     tree.add(300);
  205.     println!("{:?}", &tree);
  206.     println!("--");
  207.     tree.remove(100);
  208.     println!("{:?}", &tree);
  209.     tree.add(400);
  210.     println!("{:?}", &tree);
  211.     {
  212.         println!("--");
  213.         let mut a = Tree::new();
  214.         a.add(Huge::new("A"));
  215.         a.add(Huge::new("B"));
  216.         a.add(Huge::new("C"));
  217.         a.remove(Huge::new("B"));
  218.         println!("{:?}", &a);
  219.     }
  220.     {
  221.         println!("--");
  222.         let mut a = TreeAua::new();
  223.         a.add(Huge::new("A"));
  224.         a.add(Huge::new("B"));
  225.         a.add(Huge::new("C"));
  226.         a.remove(Huge::new("B"));
  227.         println!("{:?}", &a);
  228.     }
  229.     {
  230.         println!("--");
  231.         let mut a = Tree::new();
  232.         a.add(Rc::new(Huge::new("A")));
  233.         let b = Rc::new(Huge::new("B"));
  234.         a.add(b.clone());
  235.         a.add(Rc::new(Huge::new("C")));
  236.         a.remove(b);
  237.         println!("{:?}", &a);
  238.     }
  239. }
  240.  
Success #stdin #stdout 0s 14880KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
TreeAua { root: None }
TreeAua { root: Some(100:1) }
TreeAua { root: Some(100:1 [200:1]) }
TreeAua { root: Some([50:1] 100:2 [200:1]) }
TreeAua { root: Some([50:1] 100:2 [200:1 [300:1]]) }
--
TreeAua { root: Some(50:2 [200:1 [300:1]]) }
TreeAua { root: Some(50:2 [[200:1] 300:2 [400:1]]) }
--
> Dropping A
> Dropping A
> Dropping B
> Dropping B
Tree { root: Some("A":2 ["C":1]) }
> Dropping A
> Dropping C
--
> Dropping B
> Dropping B
TreeAua { root: Some("A":2 ["C":1]) }
> Dropping A
> Dropping C
--
> Dropping B
Tree { root: Some("A":2 ["C":1]) }
> Dropping A
> Dropping C
https://ideone.com/dFoFa9
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!