{-# OPTIONS_GHC -Wall -fwarn-tabs -fno-warn-unused-imports #-}
{-# LANGUAGE NoImplicitPrelude #-}
module Data.Trie
(
Trie()
, empty, null, singleton, size
, fromList, toListBy, toList, keys, elems
, lookupBy, lookup, member, submap, match, minMatch, matches
, insert, adjust, adjustBy, alterBy, delete, deleteSubmap
, mergeBy, unionL, unionR
, intersectBy, intersectL, intersectR
, mapBy, filterMap
) where
import Prelude hiding (null, lookup)
import qualified Prelude (null, lookup)
import Data.Trie.Internal
import Data.ByteString (ByteString)
import qualified Data.ByteString as S
import Data.Maybe (isJust)
import Control.Monad (liftM)
fromList :: [(ByteString,a)] -> Trie a
{-# INLINE fromList #-}
fromList :: [(ByteString, a)] -> Trie a
fromList = ((ByteString, a) -> Trie a -> Trie a)
-> Trie a -> [(ByteString, a)] -> Trie a
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr ((ByteString -> a -> Trie a -> Trie a)
-> (ByteString, a) -> Trie a -> Trie a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry ByteString -> a -> Trie a -> Trie a
forall a. ByteString -> a -> Trie a -> Trie a
insert) Trie a
forall a. Trie a
empty
toList :: Trie a -> [(ByteString,a)]
{-# INLINE toList #-}
toList :: Trie a -> [(ByteString, a)]
toList = (ByteString -> a -> (ByteString, a)) -> Trie a -> [(ByteString, a)]
forall a b. (ByteString -> a -> b) -> Trie a -> [b]
toListBy (,)
keys :: Trie a -> [ByteString]
{-# INLINE keys #-}
keys :: Trie a -> [ByteString]
keys = (ByteString -> a -> ByteString) -> Trie a -> [ByteString]
forall a b. (ByteString -> a -> b) -> Trie a -> [b]
toListBy ByteString -> a -> ByteString
forall a b. a -> b -> a
const
elems :: Trie a -> [a]
{-# INLINE elems #-}
elems :: Trie a -> [a]
elems = (ByteString -> a -> a) -> Trie a -> [a]
forall a b. (ByteString -> a -> b) -> Trie a -> [b]
toListBy ((a -> ByteString -> a) -> ByteString -> a -> a
forall a b c. (a -> b -> c) -> b -> a -> c
flip a -> ByteString -> a
forall a b. a -> b -> a
const)
lookupBy :: (Maybe a -> Trie a -> b) -> ByteString -> Trie a -> b
{-# INLINE lookupBy #-}
lookupBy :: (Maybe a -> Trie a -> b) -> ByteString -> Trie a -> b
lookupBy Maybe a -> Trie a -> b
f = (Maybe a -> Trie a -> b)
-> b -> (Trie a -> b) -> ByteString -> Trie a -> b
forall a b.
(Maybe a -> Trie a -> b)
-> b -> (Trie a -> b) -> ByteString -> Trie a -> b
lookupBy_ Maybe a -> Trie a -> b
f (Maybe a -> Trie a -> b
f Maybe a
forall a. Maybe a
Nothing Trie a
forall a. Trie a
empty) (Maybe a -> Trie a -> b
f Maybe a
forall a. Maybe a
Nothing)
lookup :: ByteString -> Trie a -> Maybe a
{-# INLINE lookup #-}
lookup :: ByteString -> Trie a -> Maybe a
lookup = (Maybe a -> Trie a -> Maybe a) -> ByteString -> Trie a -> Maybe a
forall a b. (Maybe a -> Trie a -> b) -> ByteString -> Trie a -> b
lookupBy Maybe a -> Trie a -> Maybe a
forall a b. a -> b -> a
const
member :: ByteString -> Trie a -> Bool
{-# INLINE member #-}
member :: ByteString -> Trie a -> Bool
member ByteString
q = Maybe a -> Bool
forall a. Maybe a -> Bool
isJust (Maybe a -> Bool) -> (Trie a -> Maybe a) -> Trie a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ByteString -> Trie a -> Maybe a
forall a. ByteString -> Trie a -> Maybe a
lookup ByteString
q
match :: Trie a -> ByteString -> Maybe (ByteString, a, ByteString)
match :: Trie a -> ByteString -> Maybe (ByteString, a, ByteString)
match Trie a
t ByteString
q =
case Trie a -> ByteString -> Maybe (Int, a)
forall a. Trie a -> ByteString -> Maybe (Int, a)
match_ Trie a
t ByteString
q of
Maybe (Int, a)
Nothing -> Maybe (ByteString, a, ByteString)
forall a. Maybe a
Nothing
Just (Int
n,a
x) ->
case Int -> ByteString -> (ByteString, ByteString)
S.splitAt Int
n ByteString
q of
(ByteString
p,ByteString
q') -> (ByteString, a, ByteString) -> Maybe (ByteString, a, ByteString)
forall a. a -> Maybe a
Just (ByteString
p, a
x, ByteString
q')
minMatch :: Trie a -> ByteString -> Maybe (ByteString, a, ByteString)
minMatch :: Trie a -> ByteString -> Maybe (ByteString, a, ByteString)
minMatch Trie a
t ByteString
q =
case Trie a -> ByteString -> [(ByteString, a, ByteString)]
forall a. Trie a -> ByteString -> [(ByteString, a, ByteString)]
matches Trie a
t ByteString
q of
[] -> Maybe (ByteString, a, ByteString)
forall a. Maybe a
Nothing
(ByteString, a, ByteString)
x:[(ByteString, a, ByteString)]
_ -> (ByteString, a, ByteString) -> Maybe (ByteString, a, ByteString)
forall a. a -> Maybe a
Just (ByteString, a, ByteString)
x
matches :: Trie a -> ByteString -> [(ByteString, a, ByteString)]
{-# INLINE matches #-}
matches :: Trie a -> ByteString -> [(ByteString, a, ByteString)]
matches Trie a
t ByteString
q = ((Int, a) -> (ByteString, a, ByteString))
-> [(Int, a)] -> [(ByteString, a, ByteString)]
forall a b. (a -> b) -> [a] -> [b]
map (Int, a) -> (ByteString, a, ByteString)
forall b. (Int, b) -> (ByteString, b, ByteString)
f (Trie a -> ByteString -> [(Int, a)]
forall a. Trie a -> ByteString -> [(Int, a)]
matches_ Trie a
t ByteString
q)
where
f :: (Int, b) -> (ByteString, b, ByteString)
f (Int
n,b
x) =
case Int -> ByteString -> (ByteString, ByteString)
S.splitAt Int
n ByteString
q of
(ByteString
p,ByteString
q') -> (ByteString
p, b
x, ByteString
q')
insert :: ByteString -> a -> Trie a -> Trie a
{-# INLINE insert #-}
insert :: ByteString -> a -> Trie a -> Trie a
insert = (ByteString -> a -> Maybe a -> Maybe a)
-> ByteString -> a -> Trie a -> Trie a
forall a.
(ByteString -> a -> Maybe a -> Maybe a)
-> ByteString -> a -> Trie a -> Trie a
alterBy (\ByteString
_ a
x Maybe a
_ -> a -> Maybe a
forall a. a -> Maybe a
Just a
x)
adjustBy :: (ByteString -> a -> a -> a)
-> ByteString -> a -> Trie a -> Trie a
{-# INLINE adjustBy #-}
adjustBy :: (ByteString -> a -> a -> a) -> ByteString -> a -> Trie a -> Trie a
adjustBy ByteString -> a -> a -> a
f ByteString
q a
x = (a -> a) -> ByteString -> Trie a -> Trie a
forall a. (a -> a) -> ByteString -> Trie a -> Trie a
adjust (ByteString -> a -> a -> a
f ByteString
q a
x) ByteString
q
delete :: ByteString -> Trie a -> Trie a
{-# INLINE delete #-}
delete :: ByteString -> Trie a -> Trie a
delete = (Maybe a -> Trie a -> (Maybe a, Trie a))
-> ByteString -> Trie a -> Trie a
forall a.
(Maybe a -> Trie a -> (Maybe a, Trie a))
-> ByteString -> Trie a -> Trie a
alterBy_ (\Maybe a
_ Trie a
t -> (Maybe a
forall a. Maybe a
Nothing, Trie a
t))
deleteSubmap :: ByteString -> Trie a -> Trie a
{-# INLINE deleteSubmap #-}
deleteSubmap :: ByteString -> Trie a -> Trie a
deleteSubmap = (Maybe a -> Trie a -> (Maybe a, Trie a))
-> ByteString -> Trie a -> Trie a
forall a.
(Maybe a -> Trie a -> (Maybe a, Trie a))
-> ByteString -> Trie a -> Trie a
alterBy_ (\Maybe a
_ Trie a
_ -> (Maybe a
forall a. Maybe a
Nothing, Trie a
forall a. Trie a
empty))
unionL :: Trie a -> Trie a -> Trie a
{-# INLINE unionL #-}
unionL :: Trie a -> Trie a -> Trie a
unionL = (a -> a -> Maybe a) -> Trie a -> Trie a -> Trie a
forall a. (a -> a -> Maybe a) -> Trie a -> Trie a -> Trie a
mergeBy (\a
x a
_ -> a -> Maybe a
forall a. a -> Maybe a
Just a
x)
unionR :: Trie a -> Trie a -> Trie a
{-# INLINE unionR #-}
unionR :: Trie a -> Trie a -> Trie a
unionR = (a -> a -> Maybe a) -> Trie a -> Trie a -> Trie a
forall a. (a -> a -> Maybe a) -> Trie a -> Trie a -> Trie a
mergeBy (\a
_ a
y -> a -> Maybe a
forall a. a -> Maybe a
Just a
y)
intersectL :: Trie a -> Trie b -> Trie a
{-# INLINE intersectL #-}
intersectL :: Trie a -> Trie b -> Trie a
intersectL = (a -> b -> Maybe a) -> Trie a -> Trie b -> Trie a
forall a b c. (a -> b -> Maybe c) -> Trie a -> Trie b -> Trie c
intersectBy (\a
x b
_ -> a -> Maybe a
forall a. a -> Maybe a
Just a
x)
intersectR :: Trie a -> Trie b -> Trie b
{-# INLINE intersectR #-}
intersectR :: Trie a -> Trie b -> Trie b
intersectR = (a -> b -> Maybe b) -> Trie a -> Trie b -> Trie b
forall a b c. (a -> b -> Maybe c) -> Trie a -> Trie b -> Trie c
intersectBy (\a
_ b
y -> b -> Maybe b
forall a. a -> Maybe a
Just b
y)