{-# LANGUAGE CPP #-}
---------------------------------------------------------
-- |
-- Copyright   : (c) 2006-2016, alpheccar.org
-- 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.Strict as M
import qualified Data.Text as T

data MapString v = EmptyTrie
                 | Trie (Maybe v) (M.Map Char (MapString v))
                 deriving(MapString v -> MapString v -> Bool
forall v. Eq v => MapString v -> MapString v -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: MapString v -> MapString v -> Bool
$c/= :: forall v. Eq v => MapString v -> MapString v -> Bool
== :: MapString v -> MapString v -> Bool
$c== :: forall v. Eq v => MapString v -> MapString v -> Bool
Eq,Int -> MapString v -> ShowS
forall v. Show v => Int -> MapString v -> ShowS
forall v. Show v => [MapString v] -> ShowS
forall v. Show v => MapString v -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [MapString v] -> ShowS
$cshowList :: forall v. Show v => [MapString v] -> ShowS
show :: MapString v -> String
$cshow :: forall v. Show v => MapString v -> String
showsPrec :: Int -> MapString v -> ShowS
$cshowsPrec :: forall v. Show v => Int -> MapString v -> ShowS
Show)
                 
myLookup :: Ord k => k -> M.Map k a ->[a]
myLookup :: forall k a. Ord k => k -> Map k a -> [a]
myLookup k
k Map k a
d = case forall k a. Ord k => k -> Map k a -> Maybe a
M.lookup k
k Map k a
d of
    Just a
r -> [a
r]
    Maybe a
_ -> []
                 
fromList :: [(T.Text,v)] -> MapString v
fromList :: forall v. [(Text, v)] -> MapString v
fromList = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr forall {v}. (Text, v) -> MapString v -> MapString v
addElem forall v. MapString v
EmptyTrie
 where
     addElem :: (Text, v) -> MapString v -> MapString v
addElem (Text
key,v
v) MapString v
a = forall v. Text -> v -> MapString v -> MapString v
insert Text
key v
v MapString v
a
                
lookup :: T.Text
       -> MapString v
       -> [v]
lookup :: forall v. Text -> MapString v -> [v]
lookup Text
_ MapString v
EmptyTrie = []
lookup Text
t (Trie (Just v
tn) Map Char (MapString v)
tc) | Text -> Bool
T.null Text
t = [v
tn]
                             | Bool
otherwise = 
                                  let c :: Char
c = Text -> Char
T.head Text
t 
                                      s :: Text
s = Text -> Text
T.tail Text
t
                                  in 
                                  v
tnforall a. a -> [a] -> [a]
:(forall k a. Ord k => k -> Map k a -> [a]
myLookup Char
c Map Char (MapString v)
tc forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall v. Text -> MapString v -> [v]
lookup Text
s)

lookup Text
t  (Trie Maybe v
Nothing Map Char (MapString v)
tc) | Text -> Bool
T.null Text
t = []
                            | Bool
otherwise = 
                                  let c :: Char
c = Text -> Char
T.head Text
t 
                                      s :: Text
s = Text -> Text
T.tail Text
t
                                  in 
                                  forall k a. Ord k => k -> Map k a -> [a]
myLookup Char
c Map Char (MapString v)
tc forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall v. Text -> MapString v -> [v]
lookup Text
s

   
insert :: T.Text
       -> v
       -> MapString v
       -> MapString v
insert :: forall v. Text -> v -> MapString v -> MapString v
insert Text
t v
v MapString v
EmptyTrie | Text -> Bool
T.null Text
t = forall v. Maybe v -> Map Char (MapString v) -> MapString v
Trie (forall a. a -> Maybe a
Just v
v) forall k a. Map k a
M.empty
                     | Bool
otherwise = 
                          let k :: Char
k = Text -> Char
T.head Text
t 
                              l :: Text
l = Text -> Text
T.tail Text
t
                          in 
                          forall v. Maybe v -> Map Char (MapString v) -> MapString v
Trie forall a. Maybe a
Nothing (forall k a. k -> a -> Map k a
M.singleton Char
k (forall v. Text -> v -> MapString v -> MapString v
insert Text
l v
v forall v. MapString v
EmptyTrie))

insert Text
t v
v (Trie Maybe v
tn Map Char (MapString v)
tc) | Text -> Bool
T.null Text
t = forall v. Maybe v -> Map Char (MapString v) -> MapString v
Trie (forall a. a -> Maybe a
Just v
v) Map Char (MapString v)
tc
                        | Bool
otherwise = 
                            let k :: Char
k = Text -> Char
T.head Text
t 
                                s :: Text
s = Text -> Text
T.tail Text
t
                            in 
                            case forall k a. Ord k => k -> Map k a -> Maybe a
M.lookup Char
k Map Char (MapString v)
tc of
                              Maybe (MapString v)
Nothing -> forall v. Maybe v -> Map Char (MapString v) -> MapString v
Trie Maybe v
tn (forall k a. Ord k => k -> a -> Map k a -> Map k a
M.insert Char
k (forall v. Text -> v -> MapString v -> MapString v
insert Text
s v
v forall v. MapString v
EmptyTrie) Map Char (MapString v)
tc)
                              Just MapString v
f -> forall v. Maybe v -> Map Char (MapString v) -> MapString v
Trie Maybe v
tn (forall k a. Ord k => k -> a -> Map k a -> Map k a
M.insert Char
k (forall v. Text -> v -> MapString v -> MapString v
insert Text
s v
v MapString v
f) Map Char (MapString v)
tc)