%Dict.oz

%<BT T> ::= leaf | node(T <BT T> <BT T>)

functor
import
   Key
export
   create: Create
   insert: Insert
   lookup: Lookup
   delete: Delete
define
   fun {Create} leaf end
   fun {Insert Tree Klucz#Value}
      case Tree
      of leaf then node(Klucz#Value leaf leaf)
      [] node(K#V L R) then
     case {Key.compare Klucz K}
     of ~1 then node(K#V {Insert L Klucz#Value} R)
     [] 0 then raise duplicatedKey(Klucz) end
     [] 1 then node(K#V L {Insert R Klucz#Value})
     end
      end
   end
   fun {Lookup Tree Klucz}
      case Tree
      of leaf then raise notFound(Klucz) end
      [] node(K#V L R) then
     case {Key.compare Klucz K}
     of ~1 then {Lookup L Klucz}
     [] 0 then V
     [] 1 then {Lookup R Klucz}
     end
      end
   end
   fun {DeleteMin Tree}
      case Tree
      of node(K#V leaf R) then K#V#R
      [] node(K#V L R) then local Key#Value#Left = {DeleteMin L}
                in Key#Value#node(K#V Left R) end
      end
   end
   fun {Delete Tree Klucz}
      case Tree
      of leaf then leaf
      [] node(K#V L R) then
     case {Key.compare Klucz K}
     of ~1 then node(K#V {Delete L Key} R)
     [] 0 then
        case L#R
        of leaf#R then R
        [] L#leaf then L
        [] _ then local Ki#Vi#T_right = {DeleteMin R}
              in node(Ki#Vi L T_right) end
        end
     [] 1 then node(K#V L {Delete R Key})
     end
      end
   end
end





%Key.oz

functor
export compare:Compare
define
   fun {Compare X Y}
      if X<Y then ~1
      elseif X==Y then 0
      else 1
      end
   end
end