```  #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);
}
}

```