/*
  type t = data ref
  and data =
    | Array of int array
    | Diff of int * int * t
*/
#[derive(Debug)]
enum Data {
    Array(Vec<u32>),
    Diff(usize, u32, T)
}

type T = Box<Data>;

/*
  let create n v = ref (Array (Array.create n v))
  let init n f = ref (Array (Array.init n f))
*/
fn create(n: usize, v: u32) -> T {
    let mut data = Vec::new();
    data.resize(n, v);
    Box::new(Data::Array(data))
}

#[allow(dead_code)]
fn init<F>(n: usize, f: F) -> T where F : Fn(usize) -> u32 {
    let mut data = Vec::new();
    data.resize(n, 0);
    for i in 0..n {
        data[i] = f(i);
    }
    Box::new(Data::Array(data))
}

/*
  (* reroot t ensures that t becomes an Array node *)
  let rec reroot t = match !t with
    | Array _ -> ()
    | Diff (i, v, t') ->
        reroot t';
        begin match !t' with
          | Array a as n ->
              let v' = a.(i) in
              a.(i) <- v;
              t := n;
              t' := Diff (i, v', t)
          | Diff _ -> assert false
        end
*/
fn reroot(t: &mut T) {
    match &mut **t {
        Data::Array(_) => (),
        Data::Diff(i, v, t2) => {
            reroot(t2);
            match &mut **t2 {
                Data::Array(array) => {
                    let mut tarray = std::mem::take(array);
                    let v2 = tarray[*i];
                    tarray[*i] = *v;
                    **t = Data::Array(tarray);
// the next line triggers an error. Everything is fine without it
                    **t2 = Data::Diff(*i, v2, *t)
/*
error[E0506]: cannot assign to `**t` because it is borrowed
  --> src/main.rs:62:21
   |
53 |     match &mut **t {
   |           -------- borrow of `**t` occurs here
...
62 |                     **t = Data::Array(tarray);
   |                     ^^^ assignment to borrowed `**t` occurs here
63 |                     **t2 = Data::Diff(*i, v2, *t)
   |                                       -- borrow later used here

error[E0507]: cannot move out of `*t` which is behind a mutable reference
  --> src/main.rs:63:47
   |
63 |                     **t2 = Data::Diff(*i, v2, *t)
   |                                               ^^ move occurs because `*t` has type `std::boxed::Box<Data>`, which does not implement the `Copy` trait

error[E0505]: cannot move out of `*t` because it is borrowed
  --> src/main.rs:63:47
   |
53 |     match &mut **t {
   |           -------- borrow of `**t` occurs here
...
63 |                     **t2 = Data::Diff(*i, v2, *t)
   |                     ----                      ^^ move out of `*t` occurs here
   |                     |
   |                     borrow later used here
*/
                }
                Data::Diff(_, _, _) => panic!("reroot")
            }
        }
    }
}