-- from http://groups.csail.mit.edu/mac/users/adams/BB/

Size EmptyDict = 0
Size (T _ count _ _) = count

N v l r = T v (1 + (Size l) + (Size r)) l r

Lookup x EmptyDict = None
Lookup x (T (key, val) count l r) =
    if x < key then
        Lookup x l
    else if key < x then
        Lookup x r
    else
        Some val

Has x dict = IsSome (Lookup x dict)

RotateSingleLeft a x (T b count y z) = N b (N a x y) z
RotateSingleRight b (T a count x y) z = N a x (N b y z)

RotateDoubleLeft a x (T c count (T b count2 y1 y2) z) = N b (N a x y1) (N c y2 z)
RotateDoubleRight c (T a count1 x (T b count2 y1 y2)) z = N b (N a x y1) (N c y2 z)

T' v l r = T'' (Size l) (Size r) v l r
T'' ln rn v l r = 
    if (ln + rn) < 2 then
        N v l r
    else if rn > (2 * ln) then
        TR r v l r
    else if ln > (2 * rn) then
        TL l v l r
    else N v l r

TR (T x count rl rr) v l r =
    if Size rl < Size rr then
        RotateSingleLeft v l r
    else
        RotateDoubleLeft v l r

TL (T x count ll lr) v l r = 
    if Size lr < Size ll then
        RotateSingleRight v l r
    else
        RotateDoubleRight v l r

(k1, v1) < (k2, vs) = k1 < k2

Insert x EmptyDict = T x 1 EmptyDict EmptyDict
Insert x (T v count l r) =
    if x < v then
        T' v (Insert x l) r
    else if v < x then
        T' v l (Insert x r)
    else
        T x count l r

-- TODO: Traverse in ascending order of keys
Traverse EmptyDict = EmptyIt
Traverse (T v _ l r) = It v (NextTraverse l r)
Iter (NextTraverse l r) = (Traverse l) `JoinIt` (Traverse r)
 
ArrayOf lst = ArrayOf' lst EmptyDict 0
ArrayOf' [] dict i = dict
ArrayOf' (h:tl) dict i = ArrayOf' tl (Insert (i, h) dict) (i + 1)