{-# OPTIONS_GHC -Wall -fwarn-tabs #-}
{-# LANGUAGE NoImplicitPrelude, CPP #-}
#if __GLASGOW_HASKELL__ >= 701
{-# LANGUAGE Safe #-}
#endif
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 Data.Trie.Internal
import Data.ByteString (ByteString)
import qualified Data.ByteString as S
import Data.Maybe (isJust)
keys :: Trie a -> [ByteString]
{-# INLINE keys #-}
keys :: forall a. Trie a -> [ByteString]
keys = forall a b. (ByteString -> a -> b) -> Trie a -> [b]
toListBy forall a b. a -> b -> a
const
lookupBy :: (Maybe a -> Trie a -> b) -> ByteString -> Trie a -> b
{-# INLINE lookupBy #-}
lookupBy :: forall a b. (Maybe a -> Trie a -> b) -> ByteString -> Trie a -> b
lookupBy Maybe a -> Trie a -> b
f = forall a b.
(a -> Trie a -> b)
-> (Trie a -> b) -> b -> ByteString -> Trie a -> b
lookupBy_ (Maybe a -> Trie a -> b
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. a -> Maybe a
Just) (Maybe a -> Trie a -> b
f forall a. Maybe a
Nothing) (Maybe a -> Trie a -> b
f forall a. Maybe a
Nothing forall a. Trie a
empty)
lookup :: ByteString -> Trie a -> Maybe a
{-# INLINE lookup #-}
lookup :: forall a. ByteString -> Trie a -> Maybe a
lookup = forall a b. (Maybe a -> Trie a -> b) -> ByteString -> Trie a -> b
lookupBy forall a b. a -> b -> a
const
member :: ByteString -> Trie a -> Bool
{-# INLINE member #-}
member :: forall a. ByteString -> Trie a -> Bool
member ByteString
q = forall a. Maybe a -> Bool
isJust forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. ByteString -> Trie a -> Maybe a
lookup ByteString
q
getMatch :: ByteString -> (Int, a) -> (ByteString, a, ByteString)
{-# INLINE getMatch #-}
getMatch :: forall a. ByteString -> (Int, a) -> (ByteString, a, ByteString)
getMatch ByteString
q (Int
n,a
x) =
case Int -> ByteString -> (ByteString, ByteString)
S.splitAt Int
n ByteString
q of
(ByteString
p,ByteString
q') -> (ByteString
p, a
x, ByteString
q')
match :: Trie a -> ByteString -> Maybe (ByteString, a, ByteString)
{-# INLINE match #-}
match :: forall a. Trie a -> ByteString -> Maybe (ByteString, a, ByteString)
match Trie a
t ByteString
q = forall a. ByteString -> (Int, a) -> (ByteString, a, ByteString)
getMatch ByteString
q forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall a. Trie a -> ByteString -> Maybe (Int, a)
match_ Trie a
t ByteString
q
minMatch :: Trie a -> ByteString -> Maybe (ByteString, a, ByteString)
{-# INLINE minMatch #-}
minMatch :: forall a. Trie a -> ByteString -> Maybe (ByteString, a, ByteString)
minMatch Trie a
t ByteString
q =
case forall a. Trie a -> ByteString -> [(ByteString, a, ByteString)]
matches Trie a
t ByteString
q of
[] -> forall a. Maybe a
Nothing
(ByteString, a, ByteString)
x:[(ByteString, a, ByteString)]
_ -> forall a. a -> Maybe a
Just (ByteString, a, ByteString)
x
matches :: Trie a -> ByteString -> [(ByteString, a, ByteString)]
{-# INLINE matches #-}
matches :: forall a. Trie a -> ByteString -> [(ByteString, a, ByteString)]
matches Trie a
t ByteString
q = forall a. ByteString -> (Int, a) -> (ByteString, a, ByteString)
getMatch ByteString
q forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall a. Trie a -> ByteString -> [(Int, a)]
matches_ Trie a
t ByteString
q
insert :: ByteString -> a -> Trie a -> Trie a
{-# INLINE insert #-}
insert :: forall a. ByteString -> a -> Trie a -> Trie a
insert = forall a.
(ByteString -> a -> Maybe a -> Maybe a)
-> ByteString -> a -> Trie a -> Trie a
alterBy (\ByteString
_ a
x Maybe a
_ -> forall a. a -> Maybe a
Just a
x)
adjustBy :: (ByteString -> a -> a -> a)
-> ByteString -> a -> Trie a -> Trie a
{-# INLINE adjustBy #-}
adjustBy :: forall a.
(ByteString -> a -> a -> a) -> ByteString -> a -> Trie a -> Trie a
adjustBy ByteString -> a -> a -> a
f ByteString
q a
x = 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 :: forall a. ByteString -> Trie a -> Trie a
delete = forall a.
(Maybe a -> Trie a -> (Maybe a, Trie a))
-> ByteString -> Trie a -> Trie a
alterBy_ (\Maybe a
_ Trie a
t -> (forall a. Maybe a
Nothing, Trie a
t))
deleteSubmap :: ByteString -> Trie a -> Trie a
{-# INLINE deleteSubmap #-}
deleteSubmap :: forall a. ByteString -> Trie a -> Trie a
deleteSubmap = forall a.
(Maybe a -> Trie a -> (Maybe a, Trie a))
-> ByteString -> Trie a -> Trie a
alterBy_ (\Maybe a
_ Trie a
_ -> (forall a. Maybe a
Nothing, forall a. Trie a
empty))
unionL :: Trie a -> Trie a -> Trie a
{-# INLINE unionL #-}
unionL :: forall a. Trie a -> Trie a -> Trie a
unionL = forall a. (a -> a -> Maybe a) -> Trie a -> Trie a -> Trie a
mergeBy (\a
x a
_ -> forall a. a -> Maybe a
Just a
x)
unionR :: Trie a -> Trie a -> Trie a
{-# INLINE unionR #-}
unionR :: forall a. Trie a -> Trie a -> Trie a
unionR = forall a. (a -> a -> Maybe a) -> Trie a -> Trie a -> Trie a
mergeBy (\a
_ a
y -> forall a. a -> Maybe a
Just a
y)
intersectL :: Trie a -> Trie b -> Trie a
{-# INLINE intersectL #-}
intersectL :: forall a b. Trie a -> Trie b -> Trie a
intersectL = forall a b c. (a -> b -> Maybe c) -> Trie a -> Trie b -> Trie c
intersectBy (\a
x b
_ -> forall a. a -> Maybe a
Just a
x)
intersectR :: Trie a -> Trie b -> Trie b
{-# INLINE intersectR #-}
intersectR :: forall a b. Trie a -> Trie b -> Trie b
intersectR = forall a b c. (a -> b -> Maybe c) -> Trie a -> Trie b -> Trie c
intersectBy (\a
_ b
y -> forall a. a -> Maybe a
Just b
y)