module Graphmod.Trie where

import qualified Data.Map as Map
import Data.Maybe(fromMaybe)

data Trie a b = Sub (Map.Map a (Trie a b)) (Maybe b)
                deriving (Trie a b -> Trie a b -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall a b. (Eq a, Eq b) => Trie a b -> Trie a b -> Bool
/= :: Trie a b -> Trie a b -> Bool
$c/= :: forall a b. (Eq a, Eq b) => Trie a b -> Trie a b -> Bool
== :: Trie a b -> Trie a b -> Bool
$c== :: forall a b. (Eq a, Eq b) => Trie a b -> Trie a b -> Bool
Eq, Trie a b -> Trie a b -> Bool
Trie a b -> Trie a b -> Ordering
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall {a} {b}. (Ord a, Ord b) => Eq (Trie a b)
forall a b. (Ord a, Ord b) => Trie a b -> Trie a b -> Bool
forall a b. (Ord a, Ord b) => Trie a b -> Trie a b -> Ordering
forall a b. (Ord a, Ord b) => Trie a b -> Trie a b -> Trie a b
min :: Trie a b -> Trie a b -> Trie a b
$cmin :: forall a b. (Ord a, Ord b) => Trie a b -> Trie a b -> Trie a b
max :: Trie a b -> Trie a b -> Trie a b
$cmax :: forall a b. (Ord a, Ord b) => Trie a b -> Trie a b -> Trie a b
>= :: Trie a b -> Trie a b -> Bool
$c>= :: forall a b. (Ord a, Ord b) => Trie a b -> Trie a b -> Bool
> :: Trie a b -> Trie a b -> Bool
$c> :: forall a b. (Ord a, Ord b) => Trie a b -> Trie a b -> Bool
<= :: Trie a b -> Trie a b -> Bool
$c<= :: forall a b. (Ord a, Ord b) => Trie a b -> Trie a b -> Bool
< :: Trie a b -> Trie a b -> Bool
$c< :: forall a b. (Ord a, Ord b) => Trie a b -> Trie a b -> Bool
compare :: Trie a b -> Trie a b -> Ordering
$ccompare :: forall a b. (Ord a, Ord b) => Trie a b -> Trie a b -> Ordering
Ord, Int -> Trie a b -> ShowS
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall a b. (Show a, Show b) => Int -> Trie a b -> ShowS
forall a b. (Show a, Show b) => [Trie a b] -> ShowS
forall a b. (Show a, Show b) => Trie a b -> String
showList :: [Trie a b] -> ShowS
$cshowList :: forall a b. (Show a, Show b) => [Trie a b] -> ShowS
show :: Trie a b -> String
$cshow :: forall a b. (Show a, Show b) => Trie a b -> String
showsPrec :: Int -> Trie a b -> ShowS
$cshowsPrec :: forall a b. (Show a, Show b) => Int -> Trie a b -> ShowS
Show)

empty :: Trie a b
empty :: forall a b. Trie a b
empty = forall a b. Map a (Trie a b) -> Maybe b -> Trie a b
Sub forall k a. Map k a
Map.empty forall a. Maybe a
Nothing

lookup :: Ord a => [a] -> Trie a b -> Maybe b
lookup :: forall a b. Ord a => [a] -> Trie a b -> Maybe b
lookup [] (Sub Map a (Trie a b)
_ Maybe b
b)       = Maybe b
b
lookup (a
k:[a]
ks) (Sub Map a (Trie a b)
as Maybe b
_)  = forall a b. Ord a => [a] -> Trie a b -> Maybe b
Graphmod.Trie.lookup [a]
ks forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup a
k Map a (Trie a b)
as

insert :: (Ord a) => [a] -> (Maybe b -> b) -> Trie a b -> Trie a b
insert :: forall a b. Ord a => [a] -> (Maybe b -> b) -> Trie a b -> Trie a b
insert [] Maybe b -> b
f (Sub Map a (Trie a b)
as Maybe b
b)     = forall a b. Map a (Trie a b) -> Maybe b -> Trie a b
Sub Map a (Trie a b)
as (forall a. a -> Maybe a
Just (Maybe b -> b
f Maybe b
b))
insert (a
k:[a]
ks) Maybe b -> b
f (Sub Map a (Trie a b)
as Maybe b
b) = forall a b. Map a (Trie a b) -> Maybe b -> Trie a b
Sub (forall k a.
Ord k =>
(Maybe a -> Maybe a) -> k -> Map k a -> Map k a
Map.alter Maybe (Trie a b) -> Maybe (Trie a b)
upd a
k Map a (Trie a b)
as) Maybe b
b
  where upd :: Maybe (Trie a b) -> Maybe (Trie a b)
upd Maybe (Trie a b)
j = forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$ forall a b. Ord a => [a] -> (Maybe b -> b) -> Trie a b -> Trie a b
insert [a]
ks Maybe b -> b
f forall a b. (a -> b) -> a -> b
$ forall a. a -> Maybe a -> a
fromMaybe forall a b. Trie a b
empty Maybe (Trie a b)
j

instance Functor (Trie a) where
  fmap :: forall a b. (a -> b) -> Trie a a -> Trie a b
fmap a -> b
f (Sub Map a (Trie a a)
m Maybe a
mb) = forall a b. Map a (Trie a b) -> Maybe b -> Trie a b
Sub (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
f) Map a (Trie a a)
m) (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
f Maybe a
mb)