fork download
copy 
  1. fn next() -> i64 {
  2.     static mut seed: i64 = 0xdeadc0de;
  3.     unsafe {
  4.         seed = seed.wrapping_mul(0x12345678deadc0d1).wrapping_add(0x1551);
  5.         seed
  6.     }
  7. }
  8.  
  9. fn main() {
  10.     const N: usize = 30000;
  11.     let mut cur_depth = 0;
  12.     let mut bst = None;
  13.     for i in 0 .. N {
  14.         bst = Node::insert(bst, i);
  15.         let dep = Node::depth(&bst);
  16.         if cur_depth != dep {
  17.             println!("i = {}, depth = {}", i, dep);
  18.             cur_depth = dep;
  19.         }
  20.     }
  21. }
  22.  
  23.  
  24. #[allow(dead_code)]
  25. struct Node<T> {
  26.     val: T,
  27.     size: usize,
  28.     left: Option<Box<Node<T>>>,
  29.     right: Option<Box<Node<T>>>,
  30.     depth: usize,
  31.     priority: i64,
  32. }
  33.  
  34. #[allow(dead_code)]
  35. type Link<T> = Option<Box<Node<T>>>;
  36.  
  37. #[allow(dead_code)]
  38. impl<T: std::cmp::PartialOrd + Copy> Node<T> {
  39.     fn singleton(val: T) -> Node<T> {
  40.         Node {
  41.             val: val,
  42.             size: 1,
  43.             left: None,
  44.             right: None,
  45.             depth: 1,
  46.             priority: next()
  47.         }
  48.     }
  49.  
  50.     fn update(&mut self) {
  51.         self.size = Self::size(&self.left) + Self::size(&self.right) + 1;
  52.         self.depth = std::cmp::max(Self::depth(&self.left), Self::depth(&self.right)) + 1;
  53.     }
  54.  
  55.     fn insert(n: Link<T>, new_val: T) -> Link<T> {
  56.         let (left, right) = Self::split_less(n, new_val);
  57.         let single = Some(Box::new(Node::singleton(new_val)));
  58.         let n = Self::merge(left, single);
  59.         Self::merge(n, right)
  60.     }
  61.  
  62.     fn insert_at(n: Link<T>, k: usize, new_val: T) -> Link<T> {
  63.         let (left, right) = Self::split_at(n, k);
  64.         let single = Some(Box::new(Node::singleton(new_val)));
  65.         let n = Self::merge(left, single);
  66.         Self::merge(n, right)
  67.     }
  68.  
  69.     fn merge(left: Link<T>, right: Link<T>) -> Link<T> {
  70.         match (left, right) {
  71.             (None, r) => r,
  72.             (l, None) => l,
  73.             (mut l, mut r) => {
  74.                 let mut l = l.take().unwrap();
  75.                 let mut r = r.take().unwrap();
  76.                 if r.priority < l.priority {
  77.                     let lr = (*l).right.take();
  78.                     l.right = Self::merge(lr, Some(r));
  79.                     l.update();
  80.                     Some(l)
  81.                 } else {
  82.                     let rl = (*r).left.take();
  83.                     r.left = Self::merge(Some(l), rl);
  84.                     r.update();
  85.                     Some(r)
  86.                 }
  87.             }
  88.         }
  89.     }
  90.  
  91.     fn split_less(n: Link<T>, val: T) -> (Link<T>, Link<T>) {
  92.         Self::split_cmp_impl(n, &|n: &Box<Node<T>>| n.val < val)
  93.     }
  94.  
  95.     fn split_leq(n: Link<T>, val: T) -> (Link<T>, Link<T>) {
  96.         Self::split_cmp_impl(n, &|n: &Box<Node<T>>| n.val <= val)
  97.     }
  98.  
  99.     fn split_cmp_impl(n: Link<T>, f: &Fn(&Box<Node<T>>) -> bool) -> (Link<T>, Link<T>) {
  100.         match n {
  101.             None => (None, None),
  102.             Some(mut n) => {
  103.                 if f(&n) {
  104.                     let (l, r) = Self::split_cmp_impl(n.right.take(), f);
  105.                     n.right = l;
  106.                     n.update();
  107.                     (Some(n), r)
  108.                 } else {
  109.                     let (l, r) = Self::split_cmp_impl(n.left.take(), f);
  110.                     n.left = r;
  111.                     n.update();
  112.                     (l, Some(n))
  113.                 }
  114.             }
  115.         }
  116.     }
  117.  
  118.     fn split_at(n: Link<T>, k: usize) -> (Link<T>, Link<T>) {
  119.         match n {
  120.             None => (None, None),
  121.             Some(mut n) => {
  122.                 let ls = Self::size(&n.left);
  123.                 if k <= ls {
  124.                     let nl = n.left.take();
  125.                     let (l, r) = Self::split_at(nl, k);
  126.                     n.left = r;
  127.                     n.update();
  128.                     (l, Some(n))
  129.                 } else {
  130.                     let nr = n.right.take();
  131.                     let (l, r) = Self::split_at(nr, k - ls - 1);
  132.                     n.right = l;
  133.                     n.update();
  134.                     (Some(n), r)
  135.                 }
  136.             }
  137.         }
  138.     }
  139.  
  140.     fn size(n: &Link<T>) -> usize {
  141.         match n {
  142.             &None => 0,
  143.             &Some(ref n) => n.size,
  144.         }
  145.     }
  146.  
  147.     fn depth(n: &Link<T>) -> usize {
  148.         match n {
  149.             &None => 0,
  150.             &Some(ref n) => n.depth,
  151.         }
  152.     }
  153.  
  154.     fn at(n: &Link<T>, k: usize) -> Option<T> {
  155.         match n {
  156.             &None => None,
  157.             &Some(ref n) => {
  158.                 let ls = Node::size(&n.left);
  159.                 if k < ls {
  160.                     Self::at(&n.left, k)
  161.                 } else if k == ls {
  162.                     Some(n.val)
  163.                 } else {
  164.                     Self::at(&n.right, k - ls - 1)
  165.                 }
  166.             }
  167.         }
  168.     }
  169. }
  170.  
  171.  
Success #stdin #stdout 0.05s 14872KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
i = 0, depth = 1
i = 1, depth = 2
i = 2, depth = 3
i = 3, depth = 4
i = 5, depth = 5
i = 6, depth = 6
i = 9, depth = 7
i = 18, depth = 8
i = 21, depth = 9
i = 30, depth = 10
i = 53, depth = 11
i = 56, depth = 12
i = 87, depth = 13
i = 91, depth = 14
i = 99, depth = 15
i = 138, depth = 16
i = 457, depth = 17
i = 531, depth = 18
i = 540, depth = 19
i = 562, depth = 20
i = 1295, depth = 21
i = 1395, depth = 22
i = 1421, depth = 23
i = 1429, depth = 24
i = 1882, depth = 25
i = 2352, depth = 26
i = 2834, depth = 27
i = 2957, depth = 28
i = 3167, depth = 29
i = 12634, depth = 30
i = 12786, depth = 31
i = 17875, depth = 32
i = 18541, depth = 33
i = 18669, depth = 34
i = 27158, depth = 35
https://ideone.com/NZ8ra2
language:
Rust (rust 1.56)
created:
7 years ago
visibility:
secret

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!