---------------------------------------------------------
-- |
-- Copyright   : (c) alpha 2006
-- License     : BSD-style
--
-- Maintainer  : misc@NOSPAMalpheccar.org
-- Stability   : experimental
-- Portability : portable
--
-- Trie data structure
---------------------------------------------------------
-- #hide
module Graphics.PDF.Data.Trie(
   MapString(..)
 , lookup
 , insert
 , fromList
 )
 where
    
import Prelude hiding(lookup)
import qualified Data.Map as M

data MapString v = EmptyTrie
                 | Trie (Maybe v) (M.Map Char (MapString v))
                 deriving(Eq,Show)
                 
fromList :: [(String,v)] -> MapString v
fromList = foldr addElem EmptyTrie
 where
     addElem (key,v) a = insert key v a
                
lookup :: String
       -> MapString v
       -> [v]
lookup _ EmptyTrie = []
lookup [] (Trie (Just a) _) = [a]
lookup [] (Trie Nothing _) = []
lookup (c:s) (Trie Nothing tc) = (M.lookup c tc >>= lookup s)
lookup (c:s) (Trie (Just tn) tc) = tn:(M.lookup c tc >>= lookup s)
   
insert :: String
       -> v
       -> MapString v
       -> MapString v
insert [] v EmptyTrie = Trie (Just v) M.empty
insert (k:l) v EmptyTrie = Trie Nothing (M.singleton k (insert l v EmptyTrie))

insert [] v (Trie _ b) = Trie (Just v) b
insert (k:s) v (Trie tn tc) = 
  case M.lookup k tc of
    Nothing -> Trie tn (M.insert k (insert s v EmptyTrie) tc)
    Just f -> Trie tn (M.insert k (insert s v f) tc)