fork(2) 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.         let elem = (next() & 0xffff_ffff) as usize;
  15.         bst = Node::insert(bst, elem);
  16.         let dep = Node::depth(&bst);
  17.         if cur_depth != dep {
  18.             println!("i = {}, depth = {}", i, dep);
  19.             cur_depth = dep;
  20.         }
  21.     }
  22. }
  23.  
  24.  
  25. #[allow(dead_code)]
  26. struct Node<T> {
  27.     val: T,
  28.     size: usize,
  29.     left: Option<Box<Node<T>>>,
  30.     right: Option<Box<Node<T>>>,
  31.     depth: usize,
  32.     priority: i64,
  33. }
  34.  
  35. #[allow(dead_code)]
  36. type Link<T> = Option<Box<Node<T>>>;
  37.  
  38. #[allow(dead_code)]
  39. impl<T: std::cmp::PartialOrd + Copy> Node<T> {
  40.     fn singleton(val: T) -> Node<T> {
  41.         Node {
  42.             val: val,
  43.             size: 1,
  44.             left: None,
  45.             right: None,
  46.             depth: 1,
  47.             priority: next()
  48.         }
  49.     }
  50.  
  51.     fn update(&mut self) {
  52.         self.size = Self::size(&self.left) + Self::size(&self.right) + 1;
  53.         self.depth = std::cmp::max(Self::depth(&self.left), Self::depth(&self.right)) + 1;
  54.     }
  55.  
  56.     fn insert(n: Link<T>, new_val: T) -> Link<T> {
  57.         let (left, right) = Self::split_less(n, new_val);
  58.         let single = Some(Box::new(Node::singleton(new_val)));
  59.         let n = Self::merge(left, single);
  60.         Self::merge(n, right)
  61.     }
  62.  
  63.     fn insert_at(n: Link<T>, k: usize, new_val: T) -> Link<T> {
  64.         let (left, right) = Self::split_at(n, k);
  65.         let single = Some(Box::new(Node::singleton(new_val)));
  66.         let n = Self::merge(left, single);
  67.         Self::merge(n, right)
  68.     }
  69.  
  70.     fn merge(left: Link<T>, right: Link<T>) -> Link<T> {
  71.         match (left, right) {
  72.             (None, r) => r,
  73.             (l, None) => l,
  74.             (mut l, mut r) => {
  75.                 let mut l = l.take().unwrap();
  76.                 let mut r = r.take().unwrap();
  77.                 if r.priority < l.priority {
  78.                     let lr = (*l).right.take();
  79.                     l.right = Self::merge(lr, Some(r));
  80.                     l.update();
  81.                     Some(l)
  82.                 } else {
  83.                     let rl = (*r).left.take();
  84.                     r.left = Self::merge(Some(l), rl);
  85.                     r.update();
  86.                     Some(r)
  87.                 }
  88.             }
  89.         }
  90.     }
  91.  
  92.     fn split_less(n: Link<T>, val: T) -> (Link<T>, Link<T>) {
  93.         Self::split_cmp_impl(n, &|n: &Box<Node<T>>| n.val < val)
  94.     }
  95.  
  96.     fn split_leq(n: Link<T>, val: T) -> (Link<T>, Link<T>) {
  97.         Self::split_cmp_impl(n, &|n: &Box<Node<T>>| n.val <= val)
  98.     }
  99.  
  100.     fn split_cmp_impl(n: Link<T>, f: &Fn(&Box<Node<T>>) -> bool) -> (Link<T>, Link<T>) {
  101.         match n {
  102.             None => (None, None),
  103.             Some(mut n) => {
  104.                 if f(&n) {
  105.                     let (l, r) = Self::split_cmp_impl(n.right.take(), f);
  106.                     n.right = l;
  107.                     n.update();
  108.                     (Some(n), r)
  109.                 } else {
  110.                     let (l, r) = Self::split_cmp_impl(n.left.take(), f);
  111.                     n.left = r;
  112.                     n.update();
  113.                     (l, Some(n))
  114.                 }
  115.             }
  116.         }
  117.     }
  118.  
  119.     fn split_at(n: Link<T>, k: usize) -> (Link<T>, Link<T>) {
  120.         match n {
  121.             None => (None, None),
  122.             Some(mut n) => {
  123.                 let ls = Self::size(&n.left);
  124.                 if k <= ls {
  125.                     let nl = n.left.take();
  126.                     let (l, r) = Self::split_at(nl, k);
  127.                     n.left = r;
  128.                     n.update();
  129.                     (l, Some(n))
  130.                 } else {
  131.                     let nr = n.right.take();
  132.                     let (l, r) = Self::split_at(nr, k - ls - 1);
  133.                     n.right = l;
  134.                     n.update();
  135.                     (Some(n), r)
  136.                 }
  137.             }
  138.         }
  139.     }
  140.  
  141.     fn size(n: &Link<T>) -> usize {
  142.         match n {
  143.             &None => 0,
  144.             &Some(ref n) => n.size,
  145.         }
  146.     }
  147.  
  148.     fn depth(n: &Link<T>) -> usize {
  149.         match n {
  150.             &None => 0,
  151.             &Some(ref n) => n.depth,
  152.         }
  153.     }
  154.  
  155.     fn at(n: &Link<T>, k: usize) -> Option<T> {
  156.         match n {
  157.             &None => None,
  158.             &Some(ref n) => {
  159.                 let ls = Node::size(&n.left);
  160.                 if k < ls {
  161.                     Self::at(&n.left, k)
  162.                 } else if k == ls {
  163.                     Some(n.val)
  164.                 } else {
  165.                     Self::at(&n.right, k - ls - 1)
  166.                 }
  167.             }
  168.         }
  169.     }
  170. }
  171.  
  172.  
Success #stdin #stdout 0.12s 14872KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
i = 0, depth = 1
i = 1, depth = 2
i = 2, depth = 3
i = 6, depth = 4
i = 7, depth = 5
i = 10, depth = 6
i = 13, depth = 7
i = 18, depth = 8
i = 29, depth = 9
i = 30, depth = 10
i = 45, depth = 11
i = 48, depth = 12
i = 49, depth = 13
i = 71, depth = 14
i = 87, depth = 15
i = 104, depth = 16
i = 134, depth = 17
i = 194, depth = 18
i = 202, depth = 19
i = 221, depth = 20
i = 279, depth = 18
i = 308, depth = 17
i = 313, depth = 18
i = 324, depth = 16
i = 339, depth = 17
i = 397, depth = 18
i = 409, depth = 16
i = 434, depth = 17
i = 437, depth = 18
i = 468, depth = 19
i = 606, depth = 20
i = 697, depth = 19
i = 710, depth = 20
i = 775, depth = 21
i = 842, depth = 19
i = 862, depth = 18
i = 875, depth = 19
i = 891, depth = 20
i = 901, depth = 21
i = 909, depth = 22
i = 1047, depth = 23
i = 1109, depth = 22
i = 1131, depth = 23
i = 1204, depth = 24
i = 1305, depth = 25
i = 1326, depth = 26
i = 1415, depth = 27
i = 1478, depth = 22
i = 1583, depth = 23
i = 1589, depth = 24
i = 1870, depth = 25
i = 1880, depth = 24
i = 1969, depth = 25
i = 2175, depth = 26
i = 2315, depth = 27
i = 2449, depth = 28
i = 2514, depth = 29
i = 2628, depth = 26
i = 2688, depth = 25
i = 2856, depth = 26
i = 2960, depth = 27
i = 3004, depth = 28
i = 3113, depth = 29
i = 3397, depth = 30
i = 3814, depth = 29
i = 3888, depth = 30
i = 3953, depth = 29
i = 3999, depth = 30
i = 4059, depth = 29
i = 4495, depth = 28
i = 4671, depth = 29
i = 4672, depth = 27
i = 4746, depth = 28
i = 4789, depth = 27
i = 4867, depth = 28
i = 4957, depth = 27
i = 5079, depth = 28
i = 5132, depth = 29
i = 6924, depth = 30
i = 8937, depth = 29
i = 9101, depth = 30
i = 9270, depth = 31
i = 9334, depth = 32
i = 10283, depth = 31
i = 10284, depth = 32
i = 11260, depth = 30
i = 11859, depth = 31
i = 12552, depth = 30
i = 12700, depth = 31
i = 12994, depth = 32
i = 13171, depth = 33
i = 13532, depth = 32
i = 13942, depth = 33
i = 14468, depth = 34
i = 14472, depth = 32
i = 15598, depth = 33
i = 16853, depth = 32
i = 17118, depth = 33
i = 17772, depth = 34
i = 17952, depth = 35
i = 19072, depth = 33
i = 19342, depth = 34
i = 19599, depth = 33
i = 21159, depth = 34
i = 21380, depth = 33
i = 22461, depth = 34
i = 23091, depth = 35
i = 24097, depth = 36
i = 24221, depth = 37
i = 25058, depth = 38
i = 25485, depth = 36
i = 25619, depth = 35
i = 27172, depth = 36
i = 27350, depth = 34
i = 28682, depth = 33
i = 29115, depth = 32
i = 29412, depth = 33
i = 29511, depth = 34
https://ideone.com/BeNbvZ
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!