Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- %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
Add Comment
Please, Sign In to add comment