diff options
Diffstat (limited to 'map.sml')
| -rw-r--r-- | map.sml | 42 |
1 files changed, 21 insertions, 21 deletions
@@ -16,8 +16,8 @@ struct type key = k datatype color = Red | Black - datatype 'a node = Node of color * (key * 'a) * ('a node) option * ('a node) option - type 'a map = ('a node) option + datatype 'a node = Node of color * (key * 'a) * 'a node option * 'a node option + type 'a map = 'a node option val empty = NONE @@ -60,9 +60,9 @@ struct fun insertNode NONE = Node (Red, kv, NONE, NONE) | insertNode (SOME (Node (color, nodeKV as (nodeKey, _), left, right))) = case cmp (k, nodeKey) of - LESS => rebalance (Node (color, nodeKV, SOME (insertNode left), right)) - | EQUAL => Node (color, kv, left, right) - | GREATER => rebalance (Node (color, nodeKV, left, SOME (insertNode right))) + LESS => rebalance (Node (color, nodeKV, SOME (insertNode left), right)) + | EQUAL => Node (color, kv, left, right) + | GREATER => rebalance (Node (color, nodeKV, left, SOME (insertNode right))) val Node (_, nodeKV, left, right) = insertNode m in SOME (Node (Black, nodeKV, left, right)) @@ -72,9 +72,9 @@ struct let fun loop NONE = NONE | loop (SOME (Node (_, (nodeKey, nodeVal), left, right))) = case cmp (k, nodeKey) of - LESS => loop left - | EQUAL => SOME nodeVal - | GREATER => loop right + LESS => loop left + | EQUAL => SOME nodeVal + | GREATER => loop right in loop m end @@ -87,9 +87,9 @@ struct fun del NONE = NONE | del (SOME (Node (_, (nodeKV as (nodeKey, _)), left, right))) = case cmp (k, nodeKey) of - LESS => SOME (delLeft nodeKV left right) - | EQUAL => merge left right - | GREATER => SOME (delRight nodeKV left right) + LESS => SOME (delLeft nodeKV left right) + | EQUAL => merge left right + | GREATER => SOME (delRight nodeKV left right) and delLeft nodeKV (a as SOME (Node (Black, _, _, _))) b = balLeft nodeKV (del a) b | delLeft nodeKV a b = Node (Red, nodeKV, del a, b) @@ -115,21 +115,21 @@ struct | merge x NONE = x | merge (SOME (Node (Red, x, a, b))) (SOME (Node (Red, y, c, d))) = (case merge b c of - SOME (Node (Red, z, b', c')) => - SOME (Node (Red, z, SOME (Node (Red, x, a, b')), - SOME (Node (Red, y, c', d)))) - | bc => SOME (Node (Red, x, a, SOME (Node (Red, y, bc, d))))) + SOME (Node (Red, z, b', c')) => + SOME (Node (Red, z, SOME (Node (Red, x, a, b')), + SOME (Node (Red, y, c', d)))) + | bc => SOME (Node (Red, x, a, SOME (Node (Red, y, bc, d))))) | merge (SOME (Node (Black, x, a, b))) (SOME (Node (Black, y, c, d))) = (case merge b c of - SOME (Node (Red, z, b', c')) => - SOME (Node (Red, z, SOME (Node (Black, x, a, b')), - SOME (Node (Black, y, c', d)))) - | bc => SOME (balLeft x a (SOME (Node (Black, y, bc, d))))) + SOME (Node (Red, z, b', c')) => + SOME (Node (Red, z, SOME (Node (Black, x, a, b')), + SOME (Node (Black, y, c', d)))) + | bc => SOME (balLeft x a (SOME (Node (Black, y, bc, d))))) | merge a (SOME (Node (Red, x, b, c))) = SOME (Node (Red, x, merge a b, c)) | merge (SOME (Node (Red, x, a, b))) c = SOME (Node (Red, x, a, merge b c)) in case del t of - NONE => NONE - | SOME (Node (_, kv, left, right)) => SOME (Node (Black, kv, left, right)) + NONE => NONE + | SOME (Node (_, kv, left, right)) => SOME (Node (Black, kv, left, right)) end end |