{-# 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
(MapString v -> MapString v -> Bool)
-> (MapString v -> MapString v -> Bool) -> Eq (MapString v)
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
[MapString v] -> ShowS
MapString v -> String
(Int -> MapString v -> ShowS)
-> (MapString v -> String)
-> ([MapString v] -> ShowS)
-> Show (MapString v)
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 :: k -> Map k a -> [a]
myLookup k
k Map k a
d = case k -> Map k a -> Maybe a
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 :: [(Text, v)] -> MapString v
fromList = ((Text, v) -> MapString v -> MapString v)
-> MapString v -> [(Text, v)] -> MapString v
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (Text, v) -> MapString v -> MapString v
forall v. (Text, v) -> MapString v -> MapString v
addElem MapString v
forall v. MapString v
EmptyTrie
 where
     addElem :: (Text, v) -> MapString v -> MapString v
addElem (Text
key,v
v) MapString v
a = Text -> v -> MapString v -> MapString v
forall v. Text -> v -> MapString v -> MapString v
insert Text
key v
v MapString v
a
                
lookup :: T.Text
       -> MapString v
       -> [v]
lookup :: 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
tnv -> [v] -> [v]
forall a. a -> [a] -> [a]
:(Char -> Map Char (MapString v) -> [MapString v]
forall k a. Ord k => k -> Map k a -> [a]
myLookup Char
c Map Char (MapString v)
tc [MapString v] -> (MapString v -> [v]) -> [v]
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= Text -> MapString v -> [v]
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 
                                  Char -> Map Char (MapString v) -> [MapString v]
forall k a. Ord k => k -> Map k a -> [a]
myLookup Char
c Map Char (MapString v)
tc [MapString v] -> (MapString v -> [v]) -> [v]
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= Text -> MapString v -> [v]
forall v. Text -> MapString v -> [v]
lookup Text
s

   
insert :: T.Text
       -> v
       -> MapString v
       -> MapString v
insert :: Text -> v -> MapString v -> MapString v
insert Text
t v
v MapString v
EmptyTrie | Text -> Bool
T.null Text
t = Maybe v -> Map Char (MapString v) -> MapString v
forall v. Maybe v -> Map Char (MapString v) -> MapString v
Trie (v -> Maybe v
forall a. a -> Maybe a
Just v
v) Map Char (MapString 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 
                          Maybe v -> Map Char (MapString v) -> MapString v
forall v. Maybe v -> Map Char (MapString v) -> MapString v
Trie Maybe v
forall a. Maybe a
Nothing (Char -> MapString v -> Map Char (MapString v)
forall k a. k -> a -> Map k a
M.singleton Char
k (Text -> v -> MapString v -> MapString v
forall v. Text -> v -> MapString v -> MapString v
insert Text
l v
v MapString 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 = Maybe v -> Map Char (MapString v) -> MapString v
forall v. Maybe v -> Map Char (MapString v) -> MapString v
Trie (v -> Maybe v
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 Char -> Map Char (MapString v) -> Maybe (MapString v)
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 -> Maybe v -> Map Char (MapString v) -> MapString v
forall v. Maybe v -> Map Char (MapString v) -> MapString v
Trie Maybe v
tn (Char
-> MapString v -> Map Char (MapString v) -> Map Char (MapString v)
forall k a. Ord k => k -> a -> Map k a -> Map k a
M.insert Char
k (Text -> v -> MapString v -> MapString v
forall v. Text -> v -> MapString v -> MapString v
insert Text
s v
v MapString v
forall v. MapString v
EmptyTrie) Map Char (MapString v)
tc)
                              Just MapString v
f -> Maybe v -> Map Char (MapString v) -> MapString v
forall v. Maybe v -> Map Char (MapString v) -> MapString v
Trie Maybe v
tn (Char
-> MapString v -> Map Char (MapString v) -> Map Char (MapString v)
forall k a. Ord k => k -> a -> Map k a -> Map k a
M.insert Char
k (Text -> v -> MapString v -> MapString v
forall v. Text -> v -> MapString v -> MapString v
insert Text
s v
v MapString v
f) Map Char (MapString v)
tc)