{- Módulo para dicionários : tabela de associação entre chaves e valores -}
module Dict (
  Dict,
  insert, lookup, empty, fromList, toList
  ) where

import Prelude hiding (lookup)

data Dict k v
  = Empty                          -- empty dictionary
  | Node k v (Dict k v) (Dict k v) -- key, value, left & right

instance (Show k, Show v) => Show (Dict k v) where
  show dict = "fromList " ++ show (toList dict)


-- construir um dicionário vazio
empty :: Dict k v
empty = Empty

-- procurar um valor por chave
lookup :: Ord k => k -> Dict k v -> Maybe v
lookup k dict = worker dict
  where
    worker Empty = Nothing
    worker (Node k' v left right)
      = case compare k k' of
          EQ -> Just v
          LT -> worker left
          GT -> worker right

-- inserir um novo par chave,valores
insert :: Ord k => k -> v -> Dict k v -> Dict k v
insert k v dict = worker dict
  where
    worker Empty = Node k v Empty Empty
    worker (Node k' v' left right)
      = case compare k k' of
        EQ -> Node k v left right
        LT -> Node k' v' (worker left) right
        GT -> Node k' v' left (worker right)


-- inserir com função para resolver colisões
insertWith :: Ord k => (v -> v -> v) -> k -> v -> Dict k v -> Dict k v
insertWith f k v dict = worker dict
  where
    worker Empty = Node k v Empty Empty
    worker (Node k' v' left right)
      = case compare k k' of
        EQ -> Node k (f v v') left right
        LT -> Node k' v' (worker left) right
        GT -> Node k' v' left (worker right)


{-
toList :: Dict k v -> [(k,v)]
toList Empty = []
toList (Node k v left right) = toList left ++ [(k,v)] ++ toList right
-}


-- versão com parametro acumulador
toList :: Dict k v -> [(k,v)]
toList dict = toListAcc dict []

-- ideia: toListAcc dict acc == toList dict ++ acc
toListAcc :: Dict k v -> [(k,v)] -> [(k,v)]
toListAcc Empty acc = acc
toListAcc (Node k v left right) acc
    = toListAcc left ((k,v):toListAcc right acc)


fromList :: Ord k => [(k,v)] -> Dict k v
fromList [] = Empty
fromList ((k,v):kvs) = insert k v (fromList kvs)