#line 101 "/home/travis/build/felix-lang/felix/src/packages/trees.fdoc"
  
  class Avl
  {
    union avl[T] =
      | Nil
      | Tree of int * T * avl[T] * avl[T] // (Height,Object,Left,Right)
    ;
  
    //==============================
  
    fun _ctor_avl[T] () => Nil[T];
  
    fun _ctor_avl[T] (x : T, left : avl[T], right : avl[T]) =>
      Tree (max(height(left), height(right)) + 1, x, left, right)
    ;
  
    //==============================
  
    private fun height[T] : avl[T]->int =
      | #Nil => 0
      | Tree(H, _, _, _) => H
    ;
  
    private fun slope[T] : avl[T]->int =
      | #Nil => 0
      | Tree(_, _, left, right) => height(left) - height(right)
    ;
  
    private fun rot_l[T](tree : avl[T]) =>
      match tree with
        | Tree(_, x, leftL, Tree(_, y, rightL, rightR)) =>
          avl(y, avl(x, leftL, rightL), rightR)
        | x => x
      endmatch
    ;
  
    private fun shift_l[T](tree : avl[T]) =>
      match tree with
        | Tree(H, x, left, right) =>
          if (slope(right) == 1) then
            rot_l(avl(x, left, rot_r(right)))
          else
            rot_l(tree)
          endif
        | x => x
      endmatch
    ;
  
    private fun rot_r[T](tree : avl[T]) =>
      match tree with
        | Tree(_, x, Tree(_, y, leftL, leftR), rightR) =>
          avl(y, leftL, avl(x, leftR, rightR))
        | x => x
      endmatch
    ;
  
    private fun shift_r[T](tree : avl[T]) =>
      match tree with
        | Tree(H, x, left, right) =>
          if (slope(right) == -1) then
            rot_r(avl(x, rot_r(left), right))
          else
            rot_r(tree)
          endif
        | x => x
      endmatch
    ;
  
    private fun balance[T](tree : avl[T]) =>
      match slope(tree) with
        | x when x == -2 => shift_l(tree)
        | 2 => shift_r(tree)
        | _ => tree
      endmatch
    ;
  
    //==============================
  
    fun insert[T] (tree : avl[T], y : T, cmp : T*T->int) =>
      match tree with
        | #Nil =>
          Tree(1, y, Nil[T], Nil[T])
        | Tree(H, x, left, right) =>
          if cmp(x, y) > 0 then
            balance(avl(x, (insert(left, y, cmp)), right))
          elif cmp(x, y) < 0 then
            balance(avl(x, left, insert(right, y, cmp)))
          else
            Tree(H, x, left, right)
          endif
      endmatch
    ;
  
    fun insert[T] (y : T, cmp : T*T->int) =>
      insert(Nil[T], y, cmp)
    ;
  
    //=================================
  
    fun find[T] (tree : avl[T], y : T, cmp : T*T->int) : opt[T] =>
        match tree with
          | #Nil => None[T]
          | Tree(H, x, left, right) =>
            if cmp(x, y) > 0 then
              find(left, y, cmp)
            elif cmp(x, y) < 0 then
              find(right, y, cmp)
            else
              Some x
            endif
        endmatch
      ;
  
    //=================================
  
    fun last[T] : avl[T]->T =
      | Tree(_, x, _, #Nil) => x
      | Tree(_, _, _, right) => last(right)
    ;
  
    fun all_but_last[T] : avl[T]->avl[T] =
      | Tree(_, _, left, #Nil) => left
      | Tree(_, x, left, right) => balance(avl(x, left, all_but_last(right)))
    ;
  
    //=================================
  
    fun first[T] : avl[T]->T =
      | Tree(_, x, #Nil, _) => x
      | Tree(_, _, left, _) => first(left)
    ;
  
    fun all_but_first[T] : avl[T]->avl[T] =
      | Tree(_, _, #Nil, right) => right
      | Tree(_, x, left, right) => balance(avl(x, all_but_first(left), right))
    ;
  
    //=================================
  
    fun join[T] (A : avl[T], B : avl[T]) =>
      match A with
        | #Nil => B
        | x => balance(avl(last(A), all_but_last(A), B))
      endmatch
    ;
  
    fun remove[T] (tree : avl[T], y : T, cmp : T*T->int) =>
      match tree with
        | #Nil => Nil[T]
        | Tree(_, x, left, right) =>
          if cmp(x, y) == 1 then
            balance(avl(x, remove(left, y, cmp), right))
          elif cmp(x, y) == -1 then
            balance(avl(x, left, remove(right, y, cmp)))
          else
            join(left, right)
          endif
      endmatch
    ;
  
    //==============================
  
    fun fold_left[T, U] (f:U->T->U) (accumulated:U) (tree:avl[T]):U =>
      match tree with
        | #Nil => accumulated
        | Tree (_, x, left, right) =>
          fold_left f  (f (fold_left f accumulated left)  x) right
      endmatch
    ;
  
    fun fold_right[T, U] (f:T->U->U) (tree:avl[T]) (accumulated:U) =>
      match tree with
        | #Nil => accumulated
        | Tree (_, x, left, right) =>
          fold_right f left (f x (fold_right f right accumulated))
      endmatch
    ;
  
    //==============================
  
    proc iter[T] (f:T->void, tree:avl[T])
    {
      match tree with
        | #Nil => {}
        | Tree (H, x, left, right) => {
          iter(f, left);
          f(x);
          iter(f, right);
        }
      endmatch;
    }
  
    proc iter[T] (f:int*T->void, tree:avl[T])
    {
      proc aux (depth:int, f:int*T->void, tree:avl[T]) {
        match tree with
          | #Nil => {}
          | Tree (H, x, left, right) => {
            aux(depth + 1, f, left);
            f(depth, x);
            aux(depth + 1, f, right);
          }
        endmatch;
      }
      aux(0, f, tree);
    }
  }