{-# LANGUAGE BangPatterns
, DeriveLift
, GADTs
, RankNTypes
, ScopedTypeVariables
, UnboxedTuples #-}
module Data.Patricia.Word.Strict.Internal
( StrictPatricia
, Patricia (..)
, Data.Patricia.Word.Strict.Internal.null
, size
, Data.Patricia.Word.Strict.Internal.map
, map'
, mapWithKey
, mapWithKey'
, Data.Patricia.Word.Strict.Internal.foldl
, Data.Patricia.Word.Strict.Internal.foldl'
, foldlWithKey
, foldlWithKey'
, Data.Patricia.Word.Strict.Internal.foldr
, Data.Patricia.Word.Strict.Internal.foldr'
, foldrWithKey
, foldrWithKey'
, Data.Patricia.Word.Strict.Internal.foldMap
, foldMapWithKey
, Data.Patricia.Word.Strict.Internal.traverse
, traverseWithKey
, union
, unionL
, unionWith'
, unionWithKey'
, difference
, differenceWith
, differenceWithKey
, Data.Patricia.Word.Strict.Internal.compare
, disjoint
, intersection
, intersectionL
, intersectionWith'
, intersectionWithKey'
, merge
, Data.Patricia.Word.Strict.Internal.lookup
, Data.Patricia.Word.Strict.Internal.find
, member
, takeOne
, dirtyLookup
, dirtyFind
, dirtyMember
, insert
, insertWith
, insertWith'
, adjust
, adjust'
, delete
, update
, alter
, lookupL
, lookupR
, adjustL
, adjustL'
, adjustLWithKey
, adjustLWithKey'
, adjustR
, adjustR'
, adjustRWithKey
, adjustRWithKey'
, deleteL
, deleteR
, updateL
, updateR
, updateLWithKey
, updateRWithKey
, adjustRange
, unsafeAdjustRange
, adjustRange'
, unsafeAdjustRange'
, adjustRangeWithKey
, unsafeAdjustRangeWithKey
, adjustRangeWithKey'
, unsafeAdjustRangeWithKey'
, deleteRange
, unsafeDeleteRange
, updateRange
, unsafeUpdateRange
, updateRangeWithKey
, unsafeUpdateRangeWithKey
, takeRange
, unsafeTakeRange
, takeL
, takeR
, Split (..)
, splitL
, splitR
, SplitLookup (..)
, splitLookup
, Data.Patricia.Word.Strict.Internal.filter
, filterWithKey
, mapMaybe
, mapMaybeWithKey
, partition
, partitionWithKey
, mapEither
, mapEitherWithKey
, lookupMin
, lookupMinWithKey
, lookupMax
, lookupMaxWithKey
, unsafeLookupMin
, unsafeLookupMinWithKey
, unsafeLookupMax
, unsafeLookupMaxWithKey
, deleteMin
, deleteMax
, adjustMin
, adjustMin'
, adjustMinWithKey
, adjustMinWithKey'
, adjustMax
, adjustMax'
, adjustMaxWithKey
, adjustMaxWithKey'
, updateMin
, updateMinWithKey
, updateMax
, updateMaxWithKey
, ViewL (..)
, minView
, unsafeMinView
, ViewR (..)
, maxView
, unsafeMaxView
) where
import Data.Patricia.Word.Common
import Radix.Common
import Radix.Exception
import Radix.Word.Common
import Radix.Word.Foundation
import Control.Applicative
import Control.DeepSeq
import Control.Exception (throw)
import Data.Bits
import Data.Foldable
import Data.Functor.Classes
import Language.Haskell.TH.Syntax (Lift)
import Text.Read
import Text.Show
type StrictPatricia = Patricia
data Patricia a = Bin
{-# UNPACK #-} !Prefix
!(Patricia a)
!(Patricia a)
| Tip
{-# UNPACK #-} !Key
a
| Nil
deriving (forall (m :: * -> *). Quote m => Patricia a -> m Exp)
-> (forall (m :: * -> *).
Quote m =>
Patricia a -> Code m (Patricia a))
-> Lift (Patricia a)
forall a (m :: * -> *). (Lift a, Quote m) => Patricia a -> m Exp
forall a (m :: * -> *).
(Lift a, Quote m) =>
Patricia a -> Code m (Patricia a)
forall t.
(forall (m :: * -> *). Quote m => t -> m Exp)
-> (forall (m :: * -> *). Quote m => t -> Code m t) -> Lift t
forall (m :: * -> *). Quote m => Patricia a -> m Exp
forall (m :: * -> *). Quote m => Patricia a -> Code m (Patricia a)
$clift :: forall a (m :: * -> *). (Lift a, Quote m) => Patricia a -> m Exp
lift :: forall (m :: * -> *). Quote m => Patricia a -> m Exp
$cliftTyped :: forall a (m :: * -> *).
(Lift a, Quote m) =>
Patricia a -> Code m (Patricia a)
liftTyped :: forall (m :: * -> *). Quote m => Patricia a -> Code m (Patricia a)
Lift
instance Show a => Show (Patricia a) where
showsPrec :: Int -> Patricia a -> ShowS
showsPrec = (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> Patricia a -> ShowS
forall a.
(Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> Patricia a -> ShowS
forall (f :: * -> *) a.
Show1 f =>
(Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> f a -> ShowS
liftShowsPrec Int -> a -> ShowS
forall a. Show a => Int -> a -> ShowS
showsPrec [a] -> ShowS
forall a. Show a => [a] -> ShowS
showList
instance Show1 Patricia where
liftShowsPrec :: forall a.
(Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> Patricia a -> ShowS
liftShowsPrec Int -> a -> ShowS
showsPrec_ [a] -> ShowS
showList_ Int
_ Patricia a
t =
((Prefix, a) -> ShowS) -> [(Prefix, a)] -> ShowS
forall a. (a -> ShowS) -> [a] -> ShowS
showListWith ((Int -> a -> ShowS)
-> ([a] -> ShowS) -> Int -> (Prefix, a) -> ShowS
forall a.
(Int -> a -> ShowS)
-> ([a] -> ShowS) -> Int -> (Prefix, a) -> ShowS
forall (f :: * -> *) a.
Show1 f =>
(Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> f a -> ShowS
liftShowsPrec Int -> a -> ShowS
showsPrec_ [a] -> ShowS
showList_ Int
0) ([(Prefix, a)] -> ShowS) -> [(Prefix, a)] -> ShowS
forall a b. (a -> b) -> a -> b
$
(Prefix -> a -> [(Prefix, a)] -> [(Prefix, a)])
-> [(Prefix, a)] -> Patricia a -> [(Prefix, a)]
forall a b. (Prefix -> a -> b -> b) -> b -> Patricia a -> b
foldrWithKey (\Prefix
k a
a -> (:) (Prefix
k, a
a)) [] Patricia a
t
instance Read a => Read (Patricia a) where
readPrec :: ReadPrec (Patricia a)
readPrec = ReadPrec a -> ReadPrec [a] -> ReadPrec (Patricia a)
forall a. ReadPrec a -> ReadPrec [a] -> ReadPrec (Patricia a)
forall (f :: * -> *) a.
Read1 f =>
ReadPrec a -> ReadPrec [a] -> ReadPrec (f a)
liftReadPrec ReadPrec a
forall a. Read a => ReadPrec a
readPrec ReadPrec [a]
forall a. Read a => ReadPrec [a]
readListPrec
instance Read1 Patricia where
liftReadPrec :: forall a. ReadPrec a -> ReadPrec [a] -> ReadPrec (Patricia a)
liftReadPrec ReadPrec a
readPrec_ ReadPrec [a]
readList_ =
([(Prefix, a)] -> Patricia a)
-> ReadPrec [(Prefix, a)] -> ReadPrec (Patricia a)
forall a b. (a -> b) -> ReadPrec a -> ReadPrec b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((Patricia a -> (Prefix, a) -> Patricia a)
-> Patricia a -> [(Prefix, a)] -> Patricia a
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
Data.Foldable.foldl' (\Patricia a
z (Prefix
k, a
a) -> Prefix -> a -> Patricia a -> Patricia a
forall a. Prefix -> a -> Patricia a -> Patricia a
insert Prefix
k a
a Patricia a
z) Patricia a
forall a. Patricia a
Nil)
(ReadPrec a -> ReadPrec [a] -> ReadPrec [(Prefix, a)]
forall a. ReadPrec a -> ReadPrec [a] -> ReadPrec [(Prefix, a)]
forall (f :: * -> *) a.
Read1 f =>
ReadPrec a -> ReadPrec [a] -> ReadPrec [f a]
liftReadListPrec ReadPrec a
readPrec_ ReadPrec [a]
readList_)
instance Eq a => Eq (Patricia a) where
== :: Patricia a -> Patricia a -> Bool
(==) = (a -> a -> Bool) -> Patricia a -> Patricia a -> Bool
forall a b. (a -> b -> Bool) -> Patricia a -> Patricia b -> Bool
forall (f :: * -> *) a b.
Eq1 f =>
(a -> b -> Bool) -> f a -> f b -> Bool
liftEq a -> a -> Bool
forall a. Eq a => a -> a -> Bool
(==)
instance Eq1 Patricia where
liftEq :: forall a b. (a -> b -> Bool) -> Patricia a -> Patricia b -> Bool
liftEq a -> b -> Bool
eq = Patricia a -> Patricia b -> Bool
go
where
go :: Patricia a -> Patricia b -> Bool
go Patricia a
l Patricia b
r =
case Patricia a
l of
Bin Prefix
p Patricia a
xl Patricia a
xr ->
case Patricia b
r of
Bin Prefix
q Patricia b
yl Patricia b
yr -> Prefix
p Prefix -> Prefix -> Bool
forall a. Eq a => a -> a -> Bool
== Prefix
q Bool -> Bool -> Bool
&& Patricia a -> Patricia b -> Bool
go Patricia a
xl Patricia b
yl Bool -> Bool -> Bool
&& Patricia a -> Patricia b -> Bool
go Patricia a
xr Patricia b
yr
Patricia b
_ -> Bool
False
Tip Prefix
kA a
a ->
case Patricia b
r of
Tip Prefix
kB b
b -> Prefix
kA Prefix -> Prefix -> Bool
forall a. Eq a => a -> a -> Bool
== Prefix
kB Bool -> Bool -> Bool
&& a -> b -> Bool
eq a
a b
b
Patricia b
_ -> Bool
False
Patricia a
Nil ->
case Patricia b
r of
Patricia b
Nil -> Bool
True
Patricia b
_ -> Bool
False
instance Functor Patricia where
fmap :: forall a b. (a -> b) -> Patricia a -> Patricia b
fmap = (a -> b) -> Patricia a -> Patricia b
forall a b. (a -> b) -> Patricia a -> Patricia b
Data.Patricia.Word.Strict.Internal.map
instance Foldable Patricia where
foldl :: forall b a. (b -> a -> b) -> b -> Patricia a -> b
foldl = (b -> a -> b) -> b -> Patricia a -> b
forall b a. (b -> a -> b) -> b -> Patricia a -> b
Data.Patricia.Word.Strict.Internal.foldl
foldr :: forall a b. (a -> b -> b) -> b -> Patricia a -> b
foldr = (a -> b -> b) -> b -> Patricia a -> b
forall a b. (a -> b -> b) -> b -> Patricia a -> b
Data.Patricia.Word.Strict.Internal.foldr
foldMap :: forall m a. Monoid m => (a -> m) -> Patricia a -> m
foldMap = (a -> m) -> Patricia a -> m
forall m a. Monoid m => (a -> m) -> Patricia a -> m
Data.Patricia.Word.Strict.Internal.foldMap
foldl' :: forall b a. (b -> a -> b) -> b -> Patricia a -> b
foldl' = (b -> a -> b) -> b -> Patricia a -> b
forall b a. (b -> a -> b) -> b -> Patricia a -> b
Data.Patricia.Word.Strict.Internal.foldl'
foldr' :: forall a b. (a -> b -> b) -> b -> Patricia a -> b
foldr' = (a -> b -> b) -> b -> Patricia a -> b
forall a b. (a -> b -> b) -> b -> Patricia a -> b
Data.Patricia.Word.Strict.Internal.foldr'
null :: forall a. Patricia a -> Bool
null = Patricia a -> Bool
forall a. Patricia a -> Bool
Data.Patricia.Word.Strict.Internal.null
length :: forall a. Patricia a -> Int
length = Int -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int -> Int) -> (Patricia a -> Int) -> Patricia a -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Patricia a -> Int
forall a. Patricia a -> Int
size
instance Traversable Patricia where
traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Patricia a -> f (Patricia b)
traverse = (a -> f b) -> Patricia a -> f (Patricia b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Patricia a -> f (Patricia b)
Data.Patricia.Word.Strict.Internal.traverse
instance NFData a => NFData (Patricia a) where
rnf :: Patricia a -> ()
rnf = (a -> ()) -> Patricia a -> ()
forall a. (a -> ()) -> Patricia a -> ()
forall (f :: * -> *) a. NFData1 f => (a -> ()) -> f a -> ()
liftRnf a -> ()
forall a. NFData a => a -> ()
rnf
instance NFData1 Patricia where
liftRnf :: forall a. (a -> ()) -> Patricia a -> ()
liftRnf a -> ()
nf = Patricia a -> ()
go
where
go :: Patricia a -> ()
go Patricia a
t =
case Patricia a
t of
Bin Prefix
_ Patricia a
l Patricia a
r -> Patricia a -> ()
go Patricia a
l () -> () -> ()
forall a b. a -> b -> b
`seq` Patricia a -> ()
go Patricia a
r
Tip Prefix
_ a
a -> a -> ()
nf a
a
Patricia a
Nil -> ()
{-# INLINE join #-}
join :: Prefix -> Patricia a -> Prefix -> Patricia a -> Patricia a
join :: forall a.
Prefix -> Patricia a -> Prefix -> Patricia a -> Patricia a
join Prefix
p0 Patricia a
t0 Prefix
p1 Patricia a
t1 =
let m :: Prefix
m = Prefix -> Prefix -> Prefix
branchingBit Prefix
p0 Prefix
p1
p :: Prefix
p = Prefix -> Prefix -> Prefix
mask Prefix
p0 Prefix
m Prefix -> Prefix -> Prefix
forall a. Bits a => a -> a -> a
.|. Prefix
m
in if Prefix -> Prefix -> Bool
zeroBit Prefix
p0 Prefix
m
then Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p Patricia a
t0 Patricia a
t1
else Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p Patricia a
t1 Patricia a
t0
{-# INLINE safeJoin #-}
safeJoin :: Prefix -> Patricia a -> Prefix -> Patricia a -> Patricia a
safeJoin :: forall a.
Prefix -> Patricia a -> Prefix -> Patricia a -> Patricia a
safeJoin Prefix
_ Patricia a
Nil Prefix
_ Patricia a
t1 = Patricia a
t1
safeJoin Prefix
_ Patricia a
t0 Prefix
_ Patricia a
Nil = Patricia a
t0
safeJoin Prefix
p0 Patricia a
t0 Prefix
p1 Patricia a
t1 = Prefix -> Patricia a -> Prefix -> Patricia a -> Patricia a
forall a.
Prefix -> Patricia a -> Prefix -> Patricia a -> Patricia a
join Prefix
p0 Patricia a
t0 Prefix
p1 Patricia a
t1
{-# INLINE rebin #-}
rebin :: Prefix -> Patricia a -> Patricia a -> Patricia a
rebin :: forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebin Prefix
p Patricia a
l Patricia a
r =
case Patricia a
l of
Patricia a
Nil -> Patricia a
r
Patricia a
_ ->
case Patricia a
r of
Patricia a
Nil -> Patricia a
l
Patricia a
_ -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p Patricia a
l Patricia a
r
{-# INLINE rebinL #-}
rebinL :: Prefix -> Patricia a -> Patricia a -> Patricia a
rebinL :: forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinL Prefix
p Patricia a
l Patricia a
r =
case Patricia a
l of
Patricia a
Nil -> Patricia a
r
Patricia a
_ -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p Patricia a
l Patricia a
r
{-# INLINE rebinR #-}
rebinR :: Prefix -> Patricia a -> Patricia a -> Patricia a
rebinR :: forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinR Prefix
p Patricia a
l Patricia a
r =
case Patricia a
r of
Patricia a
Nil -> Patricia a
l
Patricia a
_ -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p Patricia a
l Patricia a
r
{-# INLINE retip #-}
retip :: Key -> Maybe a -> Patricia a
retip :: forall a. Prefix -> Maybe a -> Patricia a
retip Prefix
w (Just a
a) = Prefix -> a -> Patricia a
forall a. Prefix -> a -> Patricia a
Tip Prefix
w a
a
retip Prefix
_ Maybe a
Nothing = Patricia a
forall a. Patricia a
Nil
null :: Patricia a -> Bool
null :: forall a. Patricia a -> Bool
null Patricia a
Nil = Bool
True
null Patricia a
_ = Bool
False
size :: Patricia a -> Int
size :: forall a. Patricia a -> Int
size Patricia a
t =
case Patricia a
t of
Bin Prefix
_ Patricia a
l Patricia a
r -> let !m :: Int
m = Patricia a -> Int
forall a. Patricia a -> Int
size Patricia a
l
!n :: Int
n = Patricia a -> Int
forall a. Patricia a -> Int
size Patricia a
r
in Int
m Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
n
Tip Prefix
_ a
_ -> Int
1
Patricia a
Nil -> Int
0
map :: (a -> b) -> Patricia a -> Patricia b
map :: forall a b. (a -> b) -> Patricia a -> Patricia b
map a -> b
f = Patricia a -> Patricia b
go
where
go :: Patricia a -> Patricia b
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r -> Prefix -> Patricia b -> Patricia b -> Patricia b
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p (Patricia a -> Patricia b
go Patricia a
l) (Patricia a -> Patricia b
go Patricia a
r)
Tip Prefix
k a
a -> Prefix -> b -> Patricia b
forall a. Prefix -> a -> Patricia a
Tip Prefix
k (a -> b
f a
a)
Patricia a
Nil -> Patricia b
forall a. Patricia a
Nil
map' :: (a -> b) -> Patricia a -> Patricia b
map' :: forall a b. (a -> b) -> Patricia a -> Patricia b
map' a -> b
f = Patricia a -> Patricia b
go
where
go :: Patricia a -> Patricia b
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r -> Prefix -> Patricia b -> Patricia b -> Patricia b
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p (Patricia a -> Patricia b
go Patricia a
l) (Patricia a -> Patricia b
go Patricia a
r)
Tip Prefix
k a
a -> Prefix -> b -> Patricia b
forall a. Prefix -> a -> Patricia a
Tip Prefix
k (b -> Patricia b) -> b -> Patricia b
forall a b. (a -> b) -> a -> b
$! a -> b
f a
a
Patricia a
Nil -> Patricia b
forall a. Patricia a
Nil
mapWithKey :: (Word -> a -> b) -> Patricia a -> Patricia b
mapWithKey :: forall a b. (Prefix -> a -> b) -> Patricia a -> Patricia b
mapWithKey Prefix -> a -> b
f = Patricia a -> Patricia b
go
where
go :: Patricia a -> Patricia b
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r -> Prefix -> Patricia b -> Patricia b -> Patricia b
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p (Patricia a -> Patricia b
go Patricia a
l) (Patricia a -> Patricia b
go Patricia a
r)
Tip Prefix
k a
a -> Prefix -> b -> Patricia b
forall a. Prefix -> a -> Patricia a
Tip Prefix
k (Prefix -> a -> b
f Prefix
k a
a)
Patricia a
Nil -> Patricia b
forall a. Patricia a
Nil
mapWithKey' :: (Word -> a -> b) -> Patricia a -> Patricia b
mapWithKey' :: forall a b. (Prefix -> a -> b) -> Patricia a -> Patricia b
mapWithKey' Prefix -> a -> b
f = Patricia a -> Patricia b
go
where
go :: Patricia a -> Patricia b
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r -> Prefix -> Patricia b -> Patricia b -> Patricia b
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p (Patricia a -> Patricia b
go Patricia a
l) (Patricia a -> Patricia b
go Patricia a
r)
Tip Prefix
k a
a -> Prefix -> b -> Patricia b
forall a. Prefix -> a -> Patricia a
Tip Prefix
k (b -> Patricia b) -> b -> Patricia b
forall a b. (a -> b) -> a -> b
$! Prefix -> a -> b
f Prefix
k a
a
Patricia a
Nil -> Patricia b
forall a. Patricia a
Nil
foldl :: (b -> a -> b) -> b -> Patricia a -> b
foldl :: forall b a. (b -> a -> b) -> b -> Patricia a -> b
foldl b -> a -> b
f = b -> Patricia a -> b
go
where
go :: b -> Patricia a -> b
go b
z Patricia a
t =
case Patricia a
t of
Bin Prefix
_ Patricia a
l Patricia a
r -> b -> Patricia a -> b
go (b -> Patricia a -> b
go b
z Patricia a
l) Patricia a
r
Tip Prefix
_ a
a -> b -> a -> b
f b
z a
a
Patricia a
Nil -> b
z
foldlWithKey :: (b -> Word -> a -> b) -> b -> Patricia a -> b
foldlWithKey :: forall b a. (b -> Prefix -> a -> b) -> b -> Patricia a -> b
foldlWithKey b -> Prefix -> a -> b
f = b -> Patricia a -> b
go
where
go :: b -> Patricia a -> b
go b
z Patricia a
t =
case Patricia a
t of
Bin Prefix
_ Patricia a
l Patricia a
r -> b -> Patricia a -> b
go (b -> Patricia a -> b
go b
z Patricia a
l) Patricia a
r
Tip Prefix
k a
a -> b -> Prefix -> a -> b
f b
z Prefix
k a
a
Patricia a
Nil -> b
z
foldl' :: (b -> a -> b) -> b -> Patricia a -> b
foldl' :: forall b a. (b -> a -> b) -> b -> Patricia a -> b
foldl' b -> a -> b
f = b -> Patricia a -> b
go
where
go :: b -> Patricia a -> b
go !b
z Patricia a
t =
case Patricia a
t of
Bin Prefix
_ Patricia a
l Patricia a
r -> let !z' :: b
z' = b -> Patricia a -> b
go b
z Patricia a
l
in b -> Patricia a -> b
go b
z' Patricia a
r
Tip Prefix
_ a
a -> b -> a -> b
f b
z a
a
Patricia a
Nil -> b
z
foldlWithKey' :: (b -> Word -> a -> b) -> b -> Patricia a -> b
foldlWithKey' :: forall b a. (b -> Prefix -> a -> b) -> b -> Patricia a -> b
foldlWithKey' b -> Prefix -> a -> b
f = b -> Patricia a -> b
go
where
go :: b -> Patricia a -> b
go !b
z Patricia a
t =
case Patricia a
t of
Bin Prefix
_ Patricia a
l Patricia a
r -> let !z' :: b
z' = b -> Patricia a -> b
go b
z Patricia a
l
in b -> Patricia a -> b
go b
z' Patricia a
r
Tip Prefix
k a
a -> b -> Prefix -> a -> b
f b
z Prefix
k a
a
Patricia a
Nil -> b
z
foldr :: (a -> b -> b) -> b -> Patricia a -> b
foldr :: forall a b. (a -> b -> b) -> b -> Patricia a -> b
foldr a -> b -> b
f = b -> Patricia a -> b
go
where
go :: b -> Patricia a -> b
go b
z Patricia a
t =
case Patricia a
t of
Bin Prefix
_ Patricia a
l Patricia a
r -> b -> Patricia a -> b
go (b -> Patricia a -> b
go b
z Patricia a
r) Patricia a
l
Tip Prefix
_ a
a -> a -> b -> b
f a
a b
z
Patricia a
Nil -> b
z
foldrWithKey :: (Word -> a -> b -> b) -> b -> Patricia a -> b
foldrWithKey :: forall a b. (Prefix -> a -> b -> b) -> b -> Patricia a -> b
foldrWithKey Prefix -> a -> b -> b
f = b -> Patricia a -> b
go
where
go :: b -> Patricia a -> b
go b
z Patricia a
t =
case Patricia a
t of
Bin Prefix
_ Patricia a
l Patricia a
r -> b -> Patricia a -> b
go (b -> Patricia a -> b
go b
z Patricia a
r) Patricia a
l
Tip Prefix
k a
a -> Prefix -> a -> b -> b
f Prefix
k a
a b
z
Patricia a
Nil -> b
z
foldr' :: (a -> b -> b) -> b -> Patricia a -> b
foldr' :: forall a b. (a -> b -> b) -> b -> Patricia a -> b
foldr' a -> b -> b
f = b -> Patricia a -> b
go
where
go :: b -> Patricia a -> b
go !b
z Patricia a
t =
case Patricia a
t of
Bin Prefix
_ Patricia a
l Patricia a
r -> let !z' :: b
z' = b -> Patricia a -> b
go b
z Patricia a
r
in b -> Patricia a -> b
go b
z' Patricia a
l
Tip Prefix
_ a
a -> a -> b -> b
f a
a b
z
Patricia a
Nil -> b
z
foldrWithKey' :: (Word -> a -> b -> b) -> b -> Patricia a -> b
foldrWithKey' :: forall a b. (Prefix -> a -> b -> b) -> b -> Patricia a -> b
foldrWithKey' Prefix -> a -> b -> b
f = b -> Patricia a -> b
go
where
go :: b -> Patricia a -> b
go !b
z Patricia a
t =
case Patricia a
t of
Bin Prefix
_ Patricia a
l Patricia a
r -> let !z' :: b
z' = b -> Patricia a -> b
go b
z Patricia a
r
in b -> Patricia a -> b
go b
z' Patricia a
l
Tip Prefix
k a
a -> Prefix -> a -> b -> b
f Prefix
k a
a b
z
Patricia a
Nil -> b
z
foldMap :: Monoid m => (a -> m) -> Patricia a -> m
foldMap :: forall m a. Monoid m => (a -> m) -> Patricia a -> m
foldMap a -> m
f = Patricia a -> m
go
where
go :: Patricia a -> m
go Patricia a
t =
case Patricia a
t of
Bin Prefix
_ Patricia a
l Patricia a
r -> Patricia a -> m
go Patricia a
l m -> m -> m
forall a. Semigroup a => a -> a -> a
<> Patricia a -> m
go Patricia a
r
Tip Prefix
_ a
a -> a -> m
f a
a
Patricia a
Nil -> m
forall a. Monoid a => a
mempty
foldMapWithKey :: Monoid m => (Word -> a -> m) -> Patricia a -> m
foldMapWithKey :: forall m a. Monoid m => (Prefix -> a -> m) -> Patricia a -> m
foldMapWithKey Prefix -> a -> m
f = Patricia a -> m
go
where
go :: Patricia a -> m
go Patricia a
t =
case Patricia a
t of
Bin Prefix
_ Patricia a
l Patricia a
r -> Patricia a -> m
go Patricia a
l m -> m -> m
forall a. Semigroup a => a -> a -> a
<> Patricia a -> m
go Patricia a
r
Tip Prefix
k a
a -> Prefix -> a -> m
f Prefix
k a
a
Patricia a
Nil -> m
forall a. Monoid a => a
mempty
traverse :: Applicative f => (a -> f b) -> Patricia a -> f (Patricia b)
traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Patricia a -> f (Patricia b)
traverse a -> f b
f = Patricia a -> f (Patricia b)
go
where
go :: Patricia a -> f (Patricia b)
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r -> (Patricia b -> Patricia b -> Patricia b)
-> f (Patricia b) -> f (Patricia b) -> f (Patricia b)
forall a b c. (a -> b -> c) -> f a -> f b -> f c
forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 (Prefix -> Patricia b -> Patricia b -> Patricia b
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p) (Patricia a -> f (Patricia b)
go Patricia a
l) (Patricia a -> f (Patricia b)
go Patricia a
r)
Tip Prefix
k a
a -> Prefix -> b -> Patricia b
forall a. Prefix -> a -> Patricia a
Tip Prefix
k (b -> Patricia b) -> f b -> f (Patricia b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> f b
f a
a
Patricia a
Nil -> Patricia b -> f (Patricia b)
forall a. a -> f a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Patricia b
forall a. Patricia a
Nil
traverseWithKey :: Applicative f => (Word -> a -> f b) -> Patricia a -> f (Patricia b)
traverseWithKey :: forall (f :: * -> *) a b.
Applicative f =>
(Prefix -> a -> f b) -> Patricia a -> f (Patricia b)
traverseWithKey Prefix -> a -> f b
f = Patricia a -> f (Patricia b)
go
where
go :: Patricia a -> f (Patricia b)
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r -> (Patricia b -> Patricia b -> Patricia b)
-> f (Patricia b) -> f (Patricia b) -> f (Patricia b)
forall a b c. (a -> b -> c) -> f a -> f b -> f c
forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 (Prefix -> Patricia b -> Patricia b -> Patricia b
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p) (Patricia a -> f (Patricia b)
go Patricia a
l) (Patricia a -> f (Patricia b)
go Patricia a
r)
Tip Prefix
k a
a -> Prefix -> b -> Patricia b
forall a. Prefix -> a -> Patricia a
Tip Prefix
k (b -> Patricia b) -> f b -> f (Patricia b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Prefix -> a -> f b
f Prefix
k a
a
Patricia a
Nil -> Patricia b -> f (Patricia b)
forall a. a -> f a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Patricia b
forall a. Patricia a
Nil
type UBin a = (# Prefix, Patricia a, Patricia a #)
type UTip a = (# Word, a #)
union :: Patricia a -> Patricia a -> Patricia a
union :: forall a. Patricia a -> Patricia a -> Patricia a
union = Patricia a -> Patricia a -> Patricia a
forall a. Patricia a -> Patricia a -> Patricia a
anyAny
where
anyAny :: Patricia a -> Patricia a -> Patricia a
anyAny Patricia a
tA Patricia a
tB =
case Patricia a
tA of
Bin Prefix
pA Patricia a
lA Patricia a
rA -> (# Prefix, Patricia a, Patricia a #)
-> Patricia a -> Patricia a -> Patricia a
binAny (# Prefix
pA, Patricia a
lA, Patricia a
rA #) Patricia a
tA Patricia a
tB
Tip Prefix
kA a
_ -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
tipAny Prefix
kA Patricia a
tA Patricia a
tB
Patricia a
Nil -> Patricia a
tB
tipAny :: Prefix -> Patricia a -> Patricia a -> Patricia a
tipAny Prefix
kA Patricia a
tA Patricia a
tB =
case Patricia a
tB of
Bin Prefix
pB Patricia a
lB Patricia a
rB -> Prefix
-> Patricia a
-> (# Prefix, Patricia a, Patricia a #)
-> Patricia a
-> Patricia a
tipBin Prefix
kA Patricia a
tA (# Prefix
pB, Patricia a
lB, Patricia a
rB #) Patricia a
tB
Tip Prefix
kB a
_
| Prefix
kA Prefix -> Prefix -> Bool
forall a. Eq a => a -> a -> Bool
== Prefix
kB -> Patricia a
tA
| Bool
otherwise -> Prefix -> Patricia a -> Prefix -> Patricia a -> Patricia a
forall a.
Prefix -> Patricia a -> Prefix -> Patricia a -> Patricia a
join Prefix
kA Patricia a
tA Prefix
kB Patricia a
tB
Patricia a
Nil -> Patricia a
tA
binAny :: (# Prefix, Patricia a, Patricia a #)
-> Patricia a -> Patricia a -> Patricia a
binAny (# Prefix, Patricia a, Patricia a #)
uA Patricia a
tA Patricia a
tB =
case Patricia a
tB of
Bin Prefix
pB Patricia a
lB Patricia a
rB -> (# Prefix, Patricia a, Patricia a #)
-> Patricia a
-> (# Prefix, Patricia a, Patricia a #)
-> Patricia a
-> Patricia a
binBin (# Prefix, Patricia a, Patricia a #)
uA Patricia a
tA (# Prefix
pB, Patricia a
lB, Patricia a
rB #) Patricia a
tB
Tip Prefix
kB a
_ -> Prefix
-> Patricia a
-> (# Prefix, Patricia a, Patricia a #)
-> Patricia a
-> Patricia a
forall {a}.
Prefix
-> Patricia a
-> (# Prefix, Patricia a, Patricia a #)
-> Patricia a
-> Patricia a
tipBin Prefix
kB Patricia a
tB (# Prefix, Patricia a, Patricia a #)
uA Patricia a
tA
Patricia a
Nil -> Patricia a
tA
tipBin :: Prefix
-> Patricia a
-> (# Prefix, Patricia a, Patricia a #)
-> Patricia a
-> Patricia a
tipBin Prefix
kA Patricia a
tA (# Prefix
pB, Patricia a
lB, Patricia a
rB #) Patricia a
tB
| Prefix -> Prefix -> Bool
beyond Prefix
pB Prefix
kA = Prefix -> Patricia a -> Prefix -> Patricia a -> Patricia a
forall a.
Prefix -> Patricia a -> Prefix -> Patricia a -> Patricia a
join Prefix
kA Patricia a
tA Prefix
pB Patricia a
tB
| Prefix
kA Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
pB = Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
pB (Prefix -> Patricia a -> Patricia a -> Patricia a
tipAny Prefix
kA Patricia a
tA Patricia a
lB) Patricia a
rB
| Bool
otherwise = Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
pB Patricia a
lB (Prefix -> Patricia a -> Patricia a -> Patricia a
tipAny Prefix
kA Patricia a
tA Patricia a
rB)
binBin :: (# Prefix, Patricia a, Patricia a #)
-> Patricia a
-> (# Prefix, Patricia a, Patricia a #)
-> Patricia a
-> Patricia a
binBin uA :: (# Prefix, Patricia a, Patricia a #)
uA@(# Prefix
pA, Patricia a
lA, Patricia a
rA #) Patricia a
tA uB :: (# Prefix, Patricia a, Patricia a #)
uB@(# Prefix
pB, Patricia a
lB, Patricia a
rB #) Patricia a
tB =
let {-# NOINLINE no #-}
no :: Patricia a
no = Prefix -> Patricia a -> Prefix -> Patricia a -> Patricia a
forall a.
Prefix -> Patricia a -> Prefix -> Patricia a -> Patricia a
join Prefix
pA Patricia a
tA Prefix
pB Patricia a
tB
in case Prefix -> Prefix -> Ordering
forall a. Ord a => a -> a -> Ordering
Prelude.compare Prefix
pA Prefix
pB of
Ordering
EQ -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
pA (Patricia a -> Patricia a -> Patricia a
anyAny Patricia a
lA Patricia a
lB) (Patricia a -> Patricia a -> Patricia a
anyAny Patricia a
rA Patricia a
rB)
Ordering
LT | Prefix
pB Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
pA -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
pA Patricia a
lA ((# Prefix, Patricia a, Patricia a #)
-> Patricia a -> Patricia a -> Patricia a
binAny (# Prefix, Patricia a, Patricia a #)
uB Patricia a
tB Patricia a
rA)
| Prefix
pA Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
pB -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
pB ((# Prefix, Patricia a, Patricia a #)
-> Patricia a -> Patricia a -> Patricia a
binAny (# Prefix, Patricia a, Patricia a #)
uA Patricia a
tA Patricia a
lB) Patricia a
rB
| Bool
otherwise -> Patricia a
no
Ordering
GT | Prefix
pA Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
pB -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
pB Patricia a
lB ((# Prefix, Patricia a, Patricia a #)
-> Patricia a -> Patricia a -> Patricia a
binAny (# Prefix, Patricia a, Patricia a #)
uA Patricia a
tA Patricia a
rB)
| Prefix
pB Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
pA -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
pA ((# Prefix, Patricia a, Patricia a #)
-> Patricia a -> Patricia a -> Patricia a
binAny (# Prefix, Patricia a, Patricia a #)
uB Patricia a
tB Patricia a
lA) Patricia a
rA
| Bool
otherwise -> Patricia a
no
unionL :: Patricia a -> Patricia a -> Patricia a
unionL :: forall a. Patricia a -> Patricia a -> Patricia a
unionL =
(forall x y. S x y a a -> Prefix -> x -> y -> Patricia a)
-> Patricia a -> Patricia a -> Patricia a
forall a.
(forall x y. S x y a a -> Prefix -> x -> y -> Patricia a)
-> Patricia a -> Patricia a -> Patricia a
union_ ((forall x y. S x y a a -> Prefix -> x -> y -> Patricia a)
-> Patricia a -> Patricia a -> Patricia a)
-> (forall x y. S x y a a -> Prefix -> x -> y -> Patricia a)
-> Patricia a
-> Patricia a
-> Patricia a
forall a b. (a -> b) -> a -> b
$ \S x y a a
s Prefix
k x
a y
b ->
let !(# a
c #) = case S x y a a
s of
S x y a a
L -> (# x
a #)
S x y a a
R -> (# y
b #)
in Prefix -> a -> Patricia a
forall a. Prefix -> a -> Patricia a
Tip Prefix
k a
c
unionWith'
:: (a -> a -> a)
-> Patricia a
-> Patricia a
-> Patricia a
unionWith' :: forall a. (a -> a -> a) -> Patricia a -> Patricia a -> Patricia a
unionWith' a -> a -> a
f =
(forall x y. S x y a a -> Prefix -> x -> y -> Patricia a)
-> Patricia a -> Patricia a -> Patricia a
forall a.
(forall x y. S x y a a -> Prefix -> x -> y -> Patricia a)
-> Patricia a -> Patricia a -> Patricia a
union_ ((forall x y. S x y a a -> Prefix -> x -> y -> Patricia a)
-> Patricia a -> Patricia a -> Patricia a)
-> (forall x y. S x y a a -> Prefix -> x -> y -> Patricia a)
-> Patricia a
-> Patricia a
-> Patricia a
forall a b. (a -> b) -> a -> b
$ \S x y a a
s Prefix
k x
a y
b ->
Prefix -> a -> Patricia a
forall a. Prefix -> a -> Patricia a
Tip Prefix
k (a -> Patricia a) -> a -> Patricia a
forall a b. (a -> b) -> a -> b
$! case S x y a a
s of
S x y a a
L -> a -> a -> a
f a
x
a a
y
b
S x y a a
R -> a -> a -> a
f a
y
b a
x
a
unionWithKey'
:: (Word -> a -> a -> a)
-> Patricia a
-> Patricia a
-> Patricia a
unionWithKey' :: forall a.
(Prefix -> a -> a -> a) -> Patricia a -> Patricia a -> Patricia a
unionWithKey' Prefix -> a -> a -> a
f =
(forall x y. S x y a a -> Prefix -> x -> y -> Patricia a)
-> Patricia a -> Patricia a -> Patricia a
forall a.
(forall x y. S x y a a -> Prefix -> x -> y -> Patricia a)
-> Patricia a -> Patricia a -> Patricia a
union_ ((forall x y. S x y a a -> Prefix -> x -> y -> Patricia a)
-> Patricia a -> Patricia a -> Patricia a)
-> (forall x y. S x y a a -> Prefix -> x -> y -> Patricia a)
-> Patricia a
-> Patricia a
-> Patricia a
forall a b. (a -> b) -> a -> b
$ \S x y a a
s Prefix
k x
a y
b ->
Prefix -> a -> Patricia a
forall a. Prefix -> a -> Patricia a
Tip Prefix
k (a -> Patricia a) -> a -> Patricia a
forall a b. (a -> b) -> a -> b
$! case S x y a a
s of
S x y a a
L -> Prefix -> a -> a -> a
f Prefix
k a
x
a a
y
b
S x y a a
R -> Prefix -> a -> a -> a
f Prefix
k a
y
b a
x
a
{-# INLINE union_ #-}
union_
:: (forall x y. S x y a a -> Key -> x -> y -> Patricia a)
-> Patricia a
-> Patricia a
-> Patricia a
union_ :: forall a.
(forall x y. S x y a a -> Prefix -> x -> y -> Patricia a)
-> Patricia a -> Patricia a -> Patricia a
union_ forall x y. S x y a a -> Prefix -> x -> y -> Patricia a
f = S a a a a -> Patricia a -> Patricia a -> Patricia a
anyAny S a a a a
forall a b. S a b a b
L
where
anyAny :: S a a a a -> Patricia a -> Patricia a -> Patricia a
anyAny S a a a a
s Patricia a
tA Patricia a
tB =
case Patricia a
tA of
Bin Prefix
pA Patricia a
lA Patricia a
rA -> S a a a a
-> (# Prefix, Patricia a, Patricia a #)
-> Patricia a
-> Patricia a
-> Patricia a
binAny S a a a a
s (# Prefix
pA, Patricia a
lA, Patricia a
rA #) Patricia a
tA Patricia a
tB
Tip Prefix
kA a
a -> S a a a a
-> (# Prefix, a #) -> Patricia a -> Patricia a -> Patricia a
tipAny S a a a a
s (# Prefix
kA, a
a #) Patricia a
tA Patricia a
tB
Patricia a
Nil -> Patricia a
tB
tipAny :: S a a a a
-> (# Prefix, a #) -> Patricia a -> Patricia a -> Patricia a
tipAny S a a a a
s uA :: (# Prefix, a #)
uA@(# Prefix
kA, a
a #) Patricia a
tA Patricia a
tB =
case Patricia a
tB of
Bin Prefix
pB Patricia a
lB Patricia a
rB -> S a a a a
-> (# Prefix, a #)
-> Patricia a
-> (# Prefix, Patricia a, Patricia a #)
-> Patricia a
-> Patricia a
tipBin S a a a a
s (# Prefix, a #)
uA Patricia a
tA (# Prefix
pB, Patricia a
lB, Patricia a
rB #) Patricia a
tB
Tip Prefix
kB a
b
| Prefix
kA Prefix -> Prefix -> Bool
forall a. Eq a => a -> a -> Bool
== Prefix
kB -> S a a a a -> Prefix -> a -> a -> Patricia a
forall x y. S x y a a -> Prefix -> x -> y -> Patricia a
f S a a a a
s Prefix
kA a
a a
b
| Bool
otherwise -> Prefix -> Patricia a -> Prefix -> Patricia a -> Patricia a
forall a.
Prefix -> Patricia a -> Prefix -> Patricia a -> Patricia a
join Prefix
kA Patricia a
tA Prefix
kB Patricia a
tB
Patricia a
Nil -> Patricia a
tA
binAny :: S a a a a
-> (# Prefix, Patricia a, Patricia a #)
-> Patricia a
-> Patricia a
-> Patricia a
binAny S a a a a
s (# Prefix, Patricia a, Patricia a #)
uA Patricia a
tA Patricia a
tB =
case Patricia a
tB of
Bin Prefix
pB Patricia a
lB Patricia a
rB -> S a a a a
-> (# Prefix, Patricia a, Patricia a #)
-> Patricia a
-> (# Prefix, Patricia a, Patricia a #)
-> Patricia a
-> Patricia a
binBin S a a a a
s (# Prefix, Patricia a, Patricia a #)
uA Patricia a
tA (# Prefix
pB, Patricia a
lB, Patricia a
rB #) Patricia a
tB
Tip Prefix
kB a
b ->
let !(# S a a a a
s' #) = S a a a a -> (# S a a a a #)
forall a b x y. S a b x y -> (# S b a x y #)
other S a a a a
s
in S a a a a
-> (# Prefix, a #)
-> Patricia a
-> (# Prefix, Patricia a, Patricia a #)
-> Patricia a
-> Patricia a
tipBin S a a a a
s' (# Prefix
kB, a
b #) Patricia a
tB (# Prefix, Patricia a, Patricia a #)
uA Patricia a
tA
Patricia a
Nil -> Patricia a
tA
tipBin :: S a a a a
-> (# Prefix, a #)
-> Patricia a
-> (# Prefix, Patricia a, Patricia a #)
-> Patricia a
-> Patricia a
tipBin S a a a a
s uA :: (# Prefix, a #)
uA@(# Prefix
kA, a
_ #) Patricia a
tA (# Prefix
pB, Patricia a
lB, Patricia a
rB #) Patricia a
tB
| Prefix -> Prefix -> Bool
beyond Prefix
pB Prefix
kA = Prefix -> Patricia a -> Prefix -> Patricia a -> Patricia a
forall a.
Prefix -> Patricia a -> Prefix -> Patricia a -> Patricia a
join Prefix
kA Patricia a
tA Prefix
pB Patricia a
tB
| Prefix
kA Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
pB = Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
pB (S a a a a
-> (# Prefix, a #) -> Patricia a -> Patricia a -> Patricia a
tipAny S a a a a
s (# Prefix, a #)
uA Patricia a
tA Patricia a
lB) Patricia a
rB
| Bool
otherwise = Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
pB Patricia a
lB (S a a a a
-> (# Prefix, a #) -> Patricia a -> Patricia a -> Patricia a
tipAny S a a a a
s (# Prefix, a #)
uA Patricia a
tA Patricia a
rB)
binBin :: S a a a a
-> (# Prefix, Patricia a, Patricia a #)
-> Patricia a
-> (# Prefix, Patricia a, Patricia a #)
-> Patricia a
-> Patricia a
binBin S a a a a
s uA :: (# Prefix, Patricia a, Patricia a #)
uA@(# Prefix
pA, Patricia a
lA, Patricia a
rA #) Patricia a
tA uB :: (# Prefix, Patricia a, Patricia a #)
uB@(# Prefix
pB, Patricia a
lB, Patricia a
rB #) Patricia a
tB =
let {-# NOINLINE no #-}
no :: Patricia a
no = Prefix -> Patricia a -> Prefix -> Patricia a -> Patricia a
forall a.
Prefix -> Patricia a -> Prefix -> Patricia a -> Patricia a
join Prefix
pA Patricia a
tA Prefix
pB Patricia a
tB
in case Prefix -> Prefix -> Ordering
forall a. Ord a => a -> a -> Ordering
Prelude.compare Prefix
pA Prefix
pB of
Ordering
EQ -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
pA (S a a a a -> Patricia a -> Patricia a -> Patricia a
anyAny S a a a a
s Patricia a
lA Patricia a
lB) (S a a a a -> Patricia a -> Patricia a -> Patricia a
anyAny S a a a a
s Patricia a
rA Patricia a
rB)
Ordering
LT | Prefix
pB Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
pA -> let !(# S a a a a
s' #) = S a a a a -> (# S a a a a #)
forall a b x y. S a b x y -> (# S b a x y #)
other S a a a a
s
in Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
pA Patricia a
lA (S a a a a
-> (# Prefix, Patricia a, Patricia a #)
-> Patricia a
-> Patricia a
-> Patricia a
binAny S a a a a
s' (# Prefix, Patricia a, Patricia a #)
uB Patricia a
tB Patricia a
rA)
| Prefix
pA Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
pB -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
pB (S a a a a
-> (# Prefix, Patricia a, Patricia a #)
-> Patricia a
-> Patricia a
-> Patricia a
binAny S a a a a
s (# Prefix, Patricia a, Patricia a #)
uA Patricia a
tA Patricia a
lB) Patricia a
rB
| Bool
otherwise -> Patricia a
no
Ordering
GT | Prefix
pA Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
pB -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
pB Patricia a
lB (S a a a a
-> (# Prefix, Patricia a, Patricia a #)
-> Patricia a
-> Patricia a
-> Patricia a
binAny S a a a a
s (# Prefix, Patricia a, Patricia a #)
uA Patricia a
tA Patricia a
rB)
| Prefix
pB Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
pA -> let !(# S a a a a
s' #) = S a a a a -> (# S a a a a #)
forall a b x y. S a b x y -> (# S b a x y #)
other S a a a a
s
in Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
pA (S a a a a
-> (# Prefix, Patricia a, Patricia a #)
-> Patricia a
-> Patricia a
-> Patricia a
binAny S a a a a
s' (# Prefix, Patricia a, Patricia a #)
uB Patricia a
tB Patricia a
lA) Patricia a
rA
| Bool
otherwise -> Patricia a
no
difference :: Patricia a -> Patricia b -> Patricia a
difference :: forall a b. Patricia a -> Patricia b -> Patricia a
difference =
(forall x y. S x y a b -> Prefix -> x -> y -> Patricia a)
-> Patricia a -> Patricia b -> Patricia a
forall a b.
(forall x y. S x y a b -> Prefix -> x -> y -> Patricia a)
-> Patricia a -> Patricia b -> Patricia a
difference_ ((forall x y. S x y a b -> Prefix -> x -> y -> Patricia a)
-> Patricia a -> Patricia b -> Patricia a)
-> (forall x y. S x y a b -> Prefix -> x -> y -> Patricia a)
-> Patricia a
-> Patricia b
-> Patricia a
forall a b. (a -> b) -> a -> b
$ \S x y a b
_ Prefix
_ x
_ y
_ ->
Patricia a
forall a. Patricia a
Nil
differenceWith
:: (a -> b -> Maybe a)
-> Patricia a
-> Patricia b
-> Patricia a
differenceWith :: forall a b.
(a -> b -> Maybe a) -> Patricia a -> Patricia b -> Patricia a
differenceWith a -> b -> Maybe a
f =
(forall x y. S x y a b -> Prefix -> x -> y -> Patricia a)
-> Patricia a -> Patricia b -> Patricia a
forall a b.
(forall x y. S x y a b -> Prefix -> x -> y -> Patricia a)
-> Patricia a -> Patricia b -> Patricia a
difference_ ((forall x y. S x y a b -> Prefix -> x -> y -> Patricia a)
-> Patricia a -> Patricia b -> Patricia a)
-> (forall x y. S x y a b -> Prefix -> x -> y -> Patricia a)
-> Patricia a
-> Patricia b
-> Patricia a
forall a b. (a -> b) -> a -> b
$ \S x y a b
s Prefix
k x
a y
b ->
Prefix -> Maybe a -> Patricia a
forall a. Prefix -> Maybe a -> Patricia a
retip Prefix
k (Maybe a -> Patricia a) -> Maybe a -> Patricia a
forall a b. (a -> b) -> a -> b
$ case S x y a b
s of
S x y a b
L -> a -> b -> Maybe a
f a
x
a b
y
b
S x y a b
R -> a -> b -> Maybe a
f a
y
b b
x
a
differenceWithKey
:: (Word -> a -> b -> Maybe a)
-> Patricia a
-> Patricia b
-> Patricia a
differenceWithKey :: forall a b.
(Prefix -> a -> b -> Maybe a)
-> Patricia a -> Patricia b -> Patricia a
differenceWithKey Prefix -> a -> b -> Maybe a
f =
(forall x y. S x y a b -> Prefix -> x -> y -> Patricia a)
-> Patricia a -> Patricia b -> Patricia a
forall a b.
(forall x y. S x y a b -> Prefix -> x -> y -> Patricia a)
-> Patricia a -> Patricia b -> Patricia a
difference_ ((forall x y. S x y a b -> Prefix -> x -> y -> Patricia a)
-> Patricia a -> Patricia b -> Patricia a)
-> (forall x y. S x y a b -> Prefix -> x -> y -> Patricia a)
-> Patricia a
-> Patricia b
-> Patricia a
forall a b. (a -> b) -> a -> b
$ \S x y a b
s Prefix
k x
a y
b ->
Prefix -> Maybe a -> Patricia a
forall a. Prefix -> Maybe a -> Patricia a
retip Prefix
k (Maybe a -> Patricia a) -> Maybe a -> Patricia a
forall a b. (a -> b) -> a -> b
$ case S x y a b
s of
S x y a b
L -> Prefix -> a -> b -> Maybe a
f Prefix
k a
x
a b
y
b
S x y a b
R -> Prefix -> a -> b -> Maybe a
f Prefix
k a
y
b b
x
a
{-# INLINE difference_ #-}
difference_
:: (forall x y. S x y a b -> Key -> x -> y -> Patricia a)
-> Patricia a
-> Patricia b
-> Patricia a
difference_ :: forall a b.
(forall x y. S x y a b -> Prefix -> x -> y -> Patricia a)
-> Patricia a -> Patricia b -> Patricia a
difference_ (forall x y. S x y a b -> Prefix -> x -> y -> Patricia a
f :: forall n o. S n o x y -> Key -> n -> o -> Patricia x) = S a b a b -> Patricia a -> Patricia b -> Patricia a
forall a b. S a b a b -> Patricia a -> Patricia b -> Patricia a
anyAny S a b a b
forall a b. S a b a b
L
where
anyAny
:: forall a b. S a b x y -> Patricia a -> Patricia b -> Patricia x
anyAny :: forall a b. S a b a b -> Patricia a -> Patricia b -> Patricia a
anyAny S a b a b
s Patricia a
tA Patricia b
tB =
case Patricia a
tA of
Bin Prefix
pA Patricia a
lA Patricia a
rA -> S a b a b -> UBin a -> Patricia a -> Patricia b -> Patricia a
forall a b.
S a b a b -> UBin a -> Patricia a -> Patricia b -> Patricia a
binAny S a b a b
s (# Prefix
pA, Patricia a
lA, Patricia a
rA #) Patricia a
tA Patricia b
tB
Tip Prefix
kA a
a -> S a b a b -> UTip a -> Patricia a -> Patricia b -> Patricia a
forall a b.
S a b a b -> UTip a -> Patricia a -> Patricia b -> Patricia a
tipAny S a b a b
s (# Prefix
kA, a
a #) Patricia a
tA Patricia b
tB
Patricia a
Nil -> case S a b a b
s of
S a b a b
L -> Patricia a
Patricia a
tA
S a b a b
R -> Patricia a
Patricia b
tB
tipAny
:: forall a b. S a b x y -> UTip a -> Patricia a -> Patricia b -> Patricia x
tipAny :: forall a b.
S a b a b -> UTip a -> Patricia a -> Patricia b -> Patricia a
tipAny S a b a b
s uA :: UTip a
uA@(# Prefix
kA, a
a #) Patricia a
tA Patricia b
tB =
case Patricia b
tB of
Bin Prefix
pB Patricia b
lB Patricia b
rB -> S a b a b
-> UTip a -> Patricia a -> UBin b -> Patricia b -> Patricia a
forall a b.
S a b a b
-> UTip a -> Patricia a -> UBin b -> Patricia b -> Patricia a
tipBin S a b a b
s UTip a
uA Patricia a
tA (# Prefix
pB, Patricia b
lB, Patricia b
rB #) Patricia b
tB
Tip Prefix
kB b
b
| Prefix
kA Prefix -> Prefix -> Bool
forall a. Eq a => a -> a -> Bool
== Prefix
kB -> S a b a b -> Prefix -> a -> b -> Patricia a
forall x y. S x y a b -> Prefix -> x -> y -> Patricia a
f S a b a b
s Prefix
kA a
a b
b
| Bool
otherwise -> case S a b a b
s of
S a b a b
L -> Patricia a
Patricia a
tA
S a b a b
R -> Patricia a
Patricia b
tB
Patricia b
Nil -> case S a b a b
s of
S a b a b
L -> Patricia a
Patricia a
tA
S a b a b
R -> Patricia a
Patricia b
tB
binAny
:: forall a b. S a b x y -> UBin a -> Patricia a -> Patricia b -> Patricia x
binAny :: forall a b.
S a b a b -> UBin a -> Patricia a -> Patricia b -> Patricia a
binAny S a b a b
s UBin a
uA Patricia a
tA Patricia b
tB =
case Patricia b
tB of
Bin Prefix
pB Patricia b
lB Patricia b
rB -> S a b a b
-> UBin a -> Patricia a -> UBin b -> Patricia b -> Patricia a
forall a b.
S a b a b
-> UBin a -> Patricia a -> UBin b -> Patricia b -> Patricia a
binBin S a b a b
s UBin a
uA Patricia a
tA (# Prefix
pB, Patricia b
lB, Patricia b
rB #) Patricia b
tB
Tip Prefix
kB b
b -> let !(# S b a a b
s' #) = S a b a b -> (# S b a a b #)
forall a b x y. S a b x y -> (# S b a x y #)
other S a b a b
s
in S b a a b
-> UTip b -> Patricia b -> UBin a -> Patricia a -> Patricia a
forall a b.
S a b a b
-> UTip a -> Patricia a -> UBin b -> Patricia b -> Patricia a
tipBin S b a a b
s' (# Prefix
kB, b
b #) Patricia b
tB UBin a
uA Patricia a
tA
Patricia b
Nil -> case S a b a b
s of
S a b a b
L -> Patricia a
Patricia a
tA
S a b a b
R -> Patricia a
Patricia b
tB
tipBin
:: forall a b. S a b x y -> UTip a -> Patricia a -> UBin b -> Patricia b -> Patricia x
tipBin :: forall a b.
S a b a b
-> UTip a -> Patricia a -> UBin b -> Patricia b -> Patricia a
tipBin S a b a b
s uA :: UTip a
uA@(# Prefix
kA, a
_ #) Patricia a
tA (# Prefix
pB, Patricia b
lB, Patricia b
rB #) Patricia b
tB
| Prefix -> Prefix -> Bool
beyond Prefix
pB Prefix
kA = case S a b a b
s of
S a b a b
L -> Patricia a
Patricia a
tA
S a b a b
R -> Patricia a
Patricia b
tB
| Prefix
kA Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
pB = case S a b a b
s of
S a b a b
L -> S a b a b -> UTip a -> Patricia a -> Patricia b -> Patricia a
forall a b.
S a b a b -> UTip a -> Patricia a -> Patricia b -> Patricia a
tipAny S a b a b
s UTip a
uA Patricia a
tA Patricia b
lB
S a b a b
R -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinL Prefix
pB (S a b a b -> UTip a -> Patricia a -> Patricia b -> Patricia a
forall a b.
S a b a b -> UTip a -> Patricia a -> Patricia b -> Patricia a
tipAny S a b a b
s UTip a
uA Patricia a
tA Patricia b
lB) Patricia a
Patricia b
rB
| Bool
otherwise = case S a b a b
s of
S a b a b
L -> S a b a b -> UTip a -> Patricia a -> Patricia b -> Patricia a
forall a b.
S a b a b -> UTip a -> Patricia a -> Patricia b -> Patricia a
tipAny S a b a b
s UTip a
uA Patricia a
tA Patricia b
rB
S a b a b
R -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinR Prefix
pB Patricia a
Patricia b
lB (S a b a b -> UTip a -> Patricia a -> Patricia b -> Patricia a
forall a b.
S a b a b -> UTip a -> Patricia a -> Patricia b -> Patricia a
tipAny S a b a b
s UTip a
uA Patricia a
tA Patricia b
rB)
binBin
:: forall a b. S a b x y -> UBin a -> Patricia a -> UBin b -> Patricia b -> Patricia x
binBin :: forall a b.
S a b a b
-> UBin a -> Patricia a -> UBin b -> Patricia b -> Patricia a
binBin S a b a b
s uA :: UBin a
uA@(# Prefix
pA, Patricia a
lA, Patricia a
rA #) Patricia a
tA uB :: UBin b
uB@(# Prefix
pB, Patricia b
lB, Patricia b
rB #) Patricia b
tB =
let {-# NOINLINE no #-}
no :: Patricia a
no = case S a b a b
s of
S a b a b
L -> Patricia a
Patricia a
tA
S a b a b
R -> Patricia a
Patricia b
tB
in case Prefix -> Prefix -> Ordering
forall a. Ord a => a -> a -> Ordering
Prelude.compare Prefix
pA Prefix
pB of
Ordering
EQ -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebin Prefix
pA (S a b a b -> Patricia a -> Patricia b -> Patricia a
forall a b. S a b a b -> Patricia a -> Patricia b -> Patricia a
anyAny S a b a b
s Patricia a
lA Patricia b
lB) (S a b a b -> Patricia a -> Patricia b -> Patricia a
forall a b. S a b a b -> Patricia a -> Patricia b -> Patricia a
anyAny S a b a b
s Patricia a
rA Patricia b
rB)
Ordering
LT | Prefix
pB Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
pA -> case S a b a b
s of
S a b a b
L -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinR Prefix
pA Patricia a
Patricia a
lA (S b a a b -> UBin b -> Patricia b -> Patricia a -> Patricia a
forall a b.
S a b a b -> UBin a -> Patricia a -> Patricia b -> Patricia a
binAny S b a a b
forall a b. S a b b a
R UBin b
UBin b
uB Patricia b
Patricia b
tB Patricia a
Patricia a
rA)
S a b a b
R -> S a b a b -> UBin a -> Patricia a -> Patricia b -> Patricia a
forall a b.
S a b a b -> UBin a -> Patricia a -> Patricia b -> Patricia a
binAny S a b a b
forall a b. S a b a b
L UBin a
UBin b
uB Patricia a
Patricia b
tB Patricia b
Patricia a
rA
| Prefix
pA Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
pB -> case S a b a b
s of
S a b a b
L -> S a b a b -> UBin a -> Patricia a -> Patricia b -> Patricia a
forall a b.
S a b a b -> UBin a -> Patricia a -> Patricia b -> Patricia a
binAny S a b a b
s UBin a
uA Patricia a
tA Patricia b
lB
S a b a b
R -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinL Prefix
pB (S a b a b -> UBin a -> Patricia a -> Patricia b -> Patricia a
forall a b.
S a b a b -> UBin a -> Patricia a -> Patricia b -> Patricia a
binAny S a b a b
s UBin a
uA Patricia a
tA Patricia b
lB) Patricia a
Patricia b
rB
| Bool
otherwise -> Patricia a
no
Ordering
GT | Prefix
pA Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
pB -> case S a b a b
s of
S a b a b
L -> S a b a b -> UBin a -> Patricia a -> Patricia b -> Patricia a
forall a b.
S a b a b -> UBin a -> Patricia a -> Patricia b -> Patricia a
binAny S a b a b
s UBin a
uA Patricia a
tA Patricia b
rB
S a b a b
R -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinR Prefix
pB Patricia a
Patricia b
lB (S a b a b -> UBin a -> Patricia a -> Patricia b -> Patricia a
forall a b.
S a b a b -> UBin a -> Patricia a -> Patricia b -> Patricia a
binAny S a b a b
s UBin a
uA Patricia a
tA Patricia b
rB)
| Prefix
pB Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
pA -> case S a b a b
s of
S a b a b
L -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinL Prefix
pA (S b a a b -> UBin b -> Patricia b -> Patricia a -> Patricia a
forall a b.
S a b a b -> UBin a -> Patricia a -> Patricia b -> Patricia a
binAny S b a a b
forall a b. S a b b a
R UBin b
UBin b
uB Patricia b
Patricia b
tB Patricia a
Patricia a
lA) Patricia a
Patricia a
rA
S a b a b
R -> S a b a b -> UBin a -> Patricia a -> Patricia b -> Patricia a
forall a b.
S a b a b -> UBin a -> Patricia a -> Patricia b -> Patricia a
binAny S a b a b
forall a b. S a b a b
L UBin a
UBin b
uB Patricia a
Patricia b
tB Patricia b
Patricia a
lA
| Bool
otherwise -> Patricia a
no
compare :: (a -> b -> Bool) -> Patricia a -> Patricia b -> PartialOrdering
compare :: forall a b.
(a -> b -> Bool) -> Patricia a -> Patricia b -> PartialOrdering
compare (a -> b -> Bool
f :: x -> y -> Bool) = S a b a b -> Patricia a -> Patricia b -> PartialOrdering
forall a b.
S a b a b -> Patricia a -> Patricia b -> PartialOrdering
anyAny S a b a b
forall a b. S a b a b
L
where
anyAny
:: forall a b. S a b x y -> Patricia a -> Patricia b -> PartialOrdering
anyAny :: forall a b.
S a b a b -> Patricia a -> Patricia b -> PartialOrdering
anyAny S a b a b
s Patricia a
tA Patricia b
tB =
case Patricia a
tA of
Bin Prefix
pA Patricia a
lA Patricia a
rA -> S a b a b -> UBin a -> Patricia a -> Patricia b -> PartialOrdering
forall a b.
S a b a b -> UBin a -> Patricia a -> Patricia b -> PartialOrdering
binAny S a b a b
s (# Prefix
pA, Patricia a
lA, Patricia a
rA #) Patricia a
tA Patricia b
tB
Tip Prefix
kA a
a -> S a b a b -> UTip a -> Patricia a -> Patricia b -> PartialOrdering
forall a b.
S a b a b -> UTip a -> Patricia a -> Patricia b -> PartialOrdering
tipAny S a b a b
s (# Prefix
kA, a
a #) Patricia a
tA Patricia b
tB
Patricia a
Nil -> case Patricia b
tB of
Patricia b
Nil -> PartialOrdering
Equal
Patricia b
_ -> PartialOrdering
Subset
tipAny
:: forall a b. S a b x y -> UTip a -> Patricia a -> Patricia b -> PartialOrdering
tipAny :: forall a b.
S a b a b -> UTip a -> Patricia a -> Patricia b -> PartialOrdering
tipAny S a b a b
s uA :: UTip a
uA@(# Prefix
kA, a
a #) Patricia a
tA Patricia b
tB =
case Patricia b
tB of
Bin Prefix
pB Patricia b
lB Patricia b
rB -> S a b a b -> UTip a -> Patricia a -> UBin b -> PartialOrdering
forall a b.
S a b a b -> UTip a -> Patricia a -> UBin b -> PartialOrdering
tipBin S a b a b
s UTip a
uA Patricia a
tA (# Prefix
pB, Patricia b
lB, Patricia b
rB #)
Tip Prefix
kB b
b
| Prefix
kA Prefix -> Prefix -> Bool
forall a. Eq a => a -> a -> Bool
== Prefix
kB -> let eq :: Bool
eq = case S a b a b
s of
S a b a b
L -> a -> b -> Bool
f a
a
a b
b
b
S a b a b
R -> a -> b -> Bool
f a
b
b b
a
a
in if Bool
eq
then PartialOrdering
Equal
else PartialOrdering
Incomparable
| Bool
otherwise -> PartialOrdering
Incomparable
Patricia b
Nil -> PartialOrdering
Superset
binAny
:: forall a b. S a b x y -> UBin a -> Patricia a -> Patricia b -> PartialOrdering
binAny :: forall a b.
S a b a b -> UBin a -> Patricia a -> Patricia b -> PartialOrdering
binAny S a b a b
s UBin a
uA Patricia a
tA Patricia b
tB =
case Patricia b
tB of
Bin Prefix
pB Patricia b
lB Patricia b
rB -> S a b a b
-> UBin a -> Patricia a -> UBin b -> Patricia b -> PartialOrdering
forall a b.
S a b a b
-> UBin a -> Patricia a -> UBin b -> Patricia b -> PartialOrdering
binBin S a b a b
s UBin a
uA Patricia a
tA (# Prefix
pB, Patricia b
lB, Patricia b
rB #) Patricia b
tB
Tip Prefix
kB b
b -> let !(# S b a a b
s' #) = S a b a b -> (# S b a a b #)
forall a b x y. S a b x y -> (# S b a x y #)
other S a b a b
s
in S b a a b -> UTip b -> Patricia b -> UBin a -> PartialOrdering
forall a b.
S a b a b -> UTip a -> Patricia a -> UBin b -> PartialOrdering
tipBin S b a a b
s' (# Prefix
kB, b
b #) Patricia b
tB UBin a
uA
Patricia b
Nil -> PartialOrdering
Superset
tipBin
:: forall a b. S a b x y -> UTip a -> Patricia a -> UBin b -> PartialOrdering
tipBin :: forall a b.
S a b a b -> UTip a -> Patricia a -> UBin b -> PartialOrdering
tipBin S a b a b
s uA :: UTip a
uA@(# Prefix
kA, a
_ #) Patricia a
tA (# Prefix
pB, Patricia b
lB, Patricia b
rB #) =
if Prefix -> Prefix -> Bool
beyond Prefix
pB Prefix
kA
then PartialOrdering
Incomparable
else S a b a b -> PartialOrdering -> PartialOrdering
forall x y a b. S x y a b -> PartialOrdering -> PartialOrdering
limit S a b a b
s (PartialOrdering -> PartialOrdering)
-> (Patricia b -> PartialOrdering) -> Patricia b -> PartialOrdering
forall b c a. (b -> c) -> (a -> b) -> a -> c
. S a b a b -> UTip a -> Patricia a -> Patricia b -> PartialOrdering
forall a b.
S a b a b -> UTip a -> Patricia a -> Patricia b -> PartialOrdering
tipAny S a b a b
s UTip a
uA Patricia a
tA (Patricia b -> PartialOrdering) -> Patricia b -> PartialOrdering
forall a b. (a -> b) -> a -> b
$ if Prefix
kA Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
pB
then Patricia b
lB
else Patricia b
rB
binBin
:: forall a b. S a b x y -> UBin a -> Patricia a -> UBin b -> Patricia b -> PartialOrdering
binBin :: forall a b.
S a b a b
-> UBin a -> Patricia a -> UBin b -> Patricia b -> PartialOrdering
binBin S a b a b
s uA :: UBin a
uA@(# Prefix
pA, Patricia a
lA, Patricia a
rA #) Patricia a
tA uB :: UBin b
uB@(# Prefix
pB, Patricia b
lB, Patricia b
rB #) Patricia b
tB =
case Prefix -> Prefix -> Ordering
forall a. Ord a => a -> a -> Ordering
Prelude.compare Prefix
pA Prefix
pB of
Ordering
EQ -> PartialOrdering -> PartialOrdering -> PartialOrdering
order (S a b a b -> Patricia a -> Patricia b -> PartialOrdering
forall a b.
S a b a b -> Patricia a -> Patricia b -> PartialOrdering
anyAny S a b a b
s Patricia a
lA Patricia b
lB) (S a b a b -> Patricia a -> Patricia b -> PartialOrdering
forall a b.
S a b a b -> Patricia a -> Patricia b -> PartialOrdering
anyAny S a b a b
s Patricia a
rA Patricia b
rB)
Ordering
LT | Prefix
pB Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
pA -> let !(# S b a a b
s' #) = S a b a b -> (# S b a a b #)
forall a b x y. S a b x y -> (# S b a x y #)
other S a b a b
s
in S b a a b -> PartialOrdering -> PartialOrdering
forall x y a b. S x y a b -> PartialOrdering -> PartialOrdering
limit S b a a b
s' (PartialOrdering -> PartialOrdering)
-> PartialOrdering -> PartialOrdering
forall a b. (a -> b) -> a -> b
$ S b a a b -> UBin b -> Patricia b -> Patricia a -> PartialOrdering
forall a b.
S a b a b -> UBin a -> Patricia a -> Patricia b -> PartialOrdering
binAny S b a a b
s' UBin b
uB Patricia b
tB Patricia a
rA
| Prefix
pA Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
pB -> S a b a b -> PartialOrdering -> PartialOrdering
forall x y a b. S x y a b -> PartialOrdering -> PartialOrdering
limit S a b a b
s (PartialOrdering -> PartialOrdering)
-> PartialOrdering -> PartialOrdering
forall a b. (a -> b) -> a -> b
$ S a b a b -> UBin a -> Patricia a -> Patricia b -> PartialOrdering
forall a b.
S a b a b -> UBin a -> Patricia a -> Patricia b -> PartialOrdering
binAny S a b a b
s UBin a
uA Patricia a
tA Patricia b
lB
| Bool
otherwise -> PartialOrdering
Incomparable
Ordering
GT | Prefix
pA Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
pB -> S a b a b -> PartialOrdering -> PartialOrdering
forall x y a b. S x y a b -> PartialOrdering -> PartialOrdering
limit S a b a b
s (PartialOrdering -> PartialOrdering)
-> PartialOrdering -> PartialOrdering
forall a b. (a -> b) -> a -> b
$ S a b a b -> UBin a -> Patricia a -> Patricia b -> PartialOrdering
forall a b.
S a b a b -> UBin a -> Patricia a -> Patricia b -> PartialOrdering
binAny S a b a b
s UBin a
uA Patricia a
tA Patricia b
rB
| Prefix
pB Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
pA -> let !(# S b a a b
s' #) = S a b a b -> (# S b a a b #)
forall a b x y. S a b x y -> (# S b a x y #)
other S a b a b
s
in S b a a b -> PartialOrdering -> PartialOrdering
forall x y a b. S x y a b -> PartialOrdering -> PartialOrdering
limit S b a a b
s' (PartialOrdering -> PartialOrdering)
-> PartialOrdering -> PartialOrdering
forall a b. (a -> b) -> a -> b
$ S b a a b -> UBin b -> Patricia b -> Patricia a -> PartialOrdering
forall a b.
S a b a b -> UBin a -> Patricia a -> Patricia b -> PartialOrdering
binAny S b a a b
s' UBin b
uB Patricia b
tB Patricia a
lA
| Bool
otherwise -> PartialOrdering
Incomparable
disjoint :: Patricia a -> Patricia b -> Bool
disjoint :: forall a b. Patricia a -> Patricia b -> Bool
disjoint = Patricia a -> Patricia b -> Bool
forall a b. Patricia a -> Patricia b -> Bool
anyAny
where
anyAny :: Patricia a -> Patricia a -> Bool
anyAny Patricia a
tA Patricia a
tB =
case Patricia a
tA of
Bin Prefix
pA Patricia a
lA Patricia a
rA -> UBin a -> Patricia a -> Patricia a -> Bool
forall a b. UBin a -> Patricia a -> Patricia b -> Bool
binAny (# Prefix
pA, Patricia a
lA, Patricia a
rA #) Patricia a
tA Patricia a
tB
Tip Prefix
kA a
_ -> Prefix -> Patricia a -> Patricia a -> Bool
forall {t} {a}. Prefix -> t -> Patricia a -> Bool
tipAny Prefix
kA Patricia a
tA Patricia a
tB
Patricia a
Nil -> Bool
True
tipAny :: Prefix -> t -> Patricia a -> Bool
tipAny Prefix
kA t
tA Patricia a
tB =
case Patricia a
tB of
Bin Prefix
pB Patricia a
lB Patricia a
rB -> Prefix -> t -> (# Prefix, Patricia a, Patricia a #) -> Bool
tipBin Prefix
kA t
tA (# Prefix
pB, Patricia a
lB, Patricia a
rB #)
Tip Prefix
kB a
_ -> Prefix
kA Prefix -> Prefix -> Bool
forall a. Eq a => a -> a -> Bool
/= Prefix
kB
Patricia a
Nil -> Bool
True
binAny :: forall a b. UBin a -> Patricia a -> Patricia b -> Bool
binAny :: forall a b. UBin a -> Patricia a -> Patricia b -> Bool
binAny UBin a
uA Patricia a
tA Patricia b
tB =
case Patricia b
tB of
Bin Prefix
pB Patricia b
lB Patricia b
rB -> UBin a
-> Patricia a
-> (# Prefix, Patricia b, Patricia b #)
-> Patricia b
-> Bool
forall {b} {a}.
(# Prefix, Patricia b, Patricia b #)
-> Patricia b
-> (# Prefix, Patricia a, Patricia a #)
-> Patricia a
-> Bool
binBin UBin a
uA Patricia a
tA (# Prefix
pB, Patricia b
lB, Patricia b
rB #) Patricia b
tB
Tip Prefix
kB b
_ -> Prefix -> Patricia b -> UBin a -> Bool
forall {t} {a}.
Prefix -> t -> (# Prefix, Patricia a, Patricia a #) -> Bool
tipBin Prefix
kB Patricia b
tB UBin a
uA
Patricia b
Nil -> Bool
True
tipBin :: Prefix -> t -> (# Prefix, Patricia a, Patricia a #) -> Bool
tipBin Prefix
kA t
tA (# Prefix
pB, Patricia a
lB, Patricia a
rB #)
| Prefix -> Prefix -> Bool
beyond Prefix
pB Prefix
kA = Bool
True
| Bool
otherwise = Prefix -> t -> Patricia a -> Bool
tipAny Prefix
kA t
tA (Patricia a -> Bool) -> Patricia a -> Bool
forall a b. (a -> b) -> a -> b
$ if Prefix
kA Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
pB
then Patricia a
lB
else Patricia a
rB
binBin :: (# Prefix, Patricia b, Patricia b #)
-> Patricia b
-> (# Prefix, Patricia a, Patricia a #)
-> Patricia a
-> Bool
binBin uA :: (# Prefix, Patricia b, Patricia b #)
uA@(# Prefix
pA, Patricia b
lA, Patricia b
rA #) Patricia b
tA uB :: (# Prefix, Patricia a, Patricia a #)
uB@(# Prefix
pB, Patricia a
lB, Patricia a
rB #) Patricia a
tB =
case Prefix -> Prefix -> Ordering
forall a. Ord a => a -> a -> Ordering
Prelude.compare Prefix
pA Prefix
pB of
Ordering
EQ -> Patricia b -> Patricia a -> Bool
forall a b. Patricia a -> Patricia b -> Bool
anyAny Patricia b
lA Patricia a
lB Bool -> Bool -> Bool
&& Patricia b -> Patricia a -> Bool
forall a b. Patricia a -> Patricia b -> Bool
anyAny Patricia b
rA Patricia a
rB
Ordering
LT | Prefix
pB Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
pA -> (# Prefix, Patricia a, Patricia a #)
-> Patricia a -> Patricia b -> Bool
forall a b. UBin a -> Patricia a -> Patricia b -> Bool
binAny (# Prefix, Patricia a, Patricia a #)
uB Patricia a
tB Patricia b
rA
| Prefix
pA Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
pB -> (# Prefix, Patricia b, Patricia b #)
-> Patricia b -> Patricia a -> Bool
forall a b. UBin a -> Patricia a -> Patricia b -> Bool
binAny (# Prefix, Patricia b, Patricia b #)
uA Patricia b
tA Patricia a
lB
| Bool
otherwise -> Bool
True
Ordering
GT | Prefix
pA Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
pB -> (# Prefix, Patricia b, Patricia b #)
-> Patricia b -> Patricia a -> Bool
forall a b. UBin a -> Patricia a -> Patricia b -> Bool
binAny (# Prefix, Patricia b, Patricia b #)
uA Patricia b
tA Patricia a
rB
| Prefix
pB Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
pA -> (# Prefix, Patricia a, Patricia a #)
-> Patricia a -> Patricia b -> Bool
forall a b. UBin a -> Patricia a -> Patricia b -> Bool
binAny (# Prefix, Patricia a, Patricia a #)
uB Patricia a
tB Patricia b
lA
| Bool
otherwise -> Bool
True
intersection :: Patricia a -> Patricia a -> Patricia a
intersection :: forall a. Patricia a -> Patricia a -> Patricia a
intersection = Patricia a -> Patricia a -> Patricia a
forall a. Patricia a -> Patricia a -> Patricia a
anyAny
where
anyAny :: Patricia a -> Patricia a -> Patricia a
anyAny Patricia a
tA Patricia a
tB =
case Patricia a
tA of
Bin Prefix
pA Patricia a
lA Patricia a
rA -> (# Prefix, Patricia a, Patricia a #)
-> Patricia a -> Patricia a -> Patricia a
binAny (# Prefix
pA, Patricia a
lA, Patricia a
rA #) Patricia a
tA Patricia a
tB
Tip Prefix
kA a
_ -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall {a} {a}. Prefix -> Patricia a -> Patricia a -> Patricia a
tipAny Prefix
kA Patricia a
tA Patricia a
tB
Patricia a
Nil -> Patricia a
forall a. Patricia a
Nil
tipAny :: Prefix -> Patricia a -> Patricia a -> Patricia a
tipAny Prefix
kA Patricia a
tA Patricia a
tB =
case Patricia a
tB of
Bin Prefix
pB Patricia a
lB Patricia a
rB -> Prefix
-> Patricia a -> (# Prefix, Patricia a, Patricia a #) -> Patricia a
tipBin Prefix
kA Patricia a
tA (# Prefix
pB, Patricia a
lB, Patricia a
rB #)
Tip Prefix
kB a
_
| Prefix
kA Prefix -> Prefix -> Bool
forall a. Eq a => a -> a -> Bool
== Prefix
kB -> Patricia a
tA
| Bool
otherwise -> Patricia a
forall a. Patricia a
Nil
Patricia a
Nil -> Patricia a
forall a. Patricia a
Nil
binAny :: (# Prefix, Patricia a, Patricia a #)
-> Patricia a -> Patricia a -> Patricia a
binAny (# Prefix, Patricia a, Patricia a #)
uA Patricia a
tA Patricia a
tB =
case Patricia a
tB of
Bin Prefix
pB Patricia a
lB Patricia a
rB -> (# Prefix, Patricia a, Patricia a #)
-> Patricia a
-> (# Prefix, Patricia a, Patricia a #)
-> Patricia a
-> Patricia a
binBin (# Prefix, Patricia a, Patricia a #)
uA Patricia a
tA (# Prefix
pB, Patricia a
lB, Patricia a
rB #) Patricia a
tB
Tip Prefix
kB a
_ -> Prefix
-> Patricia a -> (# Prefix, Patricia a, Patricia a #) -> Patricia a
forall {a} {a}.
Prefix
-> Patricia a -> (# Prefix, Patricia a, Patricia a #) -> Patricia a
tipBin Prefix
kB Patricia a
tB (# Prefix, Patricia a, Patricia a #)
uA
Patricia a
Nil -> Patricia a
forall a. Patricia a
Nil
tipBin :: Prefix
-> Patricia a -> (# Prefix, Patricia a, Patricia a #) -> Patricia a
tipBin Prefix
kA Patricia a
tA (# Prefix
pB, Patricia a
lB, Patricia a
rB #)
| Prefix -> Prefix -> Bool
beyond Prefix
pB Prefix
kA = Patricia a
forall a. Patricia a
Nil
| Bool
otherwise = Prefix -> Patricia a -> Patricia a -> Patricia a
tipAny Prefix
kA Patricia a
tA (Patricia a -> Patricia a) -> Patricia a -> Patricia a
forall a b. (a -> b) -> a -> b
$ if Prefix
kA Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
pB
then Patricia a
lB
else Patricia a
rB
binBin :: (# Prefix, Patricia a, Patricia a #)
-> Patricia a
-> (# Prefix, Patricia a, Patricia a #)
-> Patricia a
-> Patricia a
binBin uA :: (# Prefix, Patricia a, Patricia a #)
uA@(# Prefix
pA, Patricia a
lA, Patricia a
rA #) Patricia a
tA uB :: (# Prefix, Patricia a, Patricia a #)
uB@(# Prefix
pB, Patricia a
lB, Patricia a
rB #) Patricia a
tB =
case Prefix -> Prefix -> Ordering
forall a. Ord a => a -> a -> Ordering
Prelude.compare Prefix
pA Prefix
pB of
Ordering
EQ -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebin Prefix
pA (Patricia a -> Patricia a -> Patricia a
anyAny Patricia a
lA Patricia a
lB) (Patricia a -> Patricia a -> Patricia a
anyAny Patricia a
rA Patricia a
rB)
Ordering
LT | Prefix
pB Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
pA -> (# Prefix, Patricia a, Patricia a #)
-> Patricia a -> Patricia a -> Patricia a
binAny (# Prefix, Patricia a, Patricia a #)
uB Patricia a
tB Patricia a
rA
| Prefix
pA Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
pB -> (# Prefix, Patricia a, Patricia a #)
-> Patricia a -> Patricia a -> Patricia a
binAny (# Prefix, Patricia a, Patricia a #)
uA Patricia a
tA Patricia a
lB
| Bool
otherwise -> Patricia a
forall a. Patricia a
Nil
Ordering
GT | Prefix
pA Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
pB -> (# Prefix, Patricia a, Patricia a #)
-> Patricia a -> Patricia a -> Patricia a
binAny (# Prefix, Patricia a, Patricia a #)
uA Patricia a
tA Patricia a
rB
| Prefix
pB Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
pA -> (# Prefix, Patricia a, Patricia a #)
-> Patricia a -> Patricia a -> Patricia a
binAny (# Prefix, Patricia a, Patricia a #)
uB Patricia a
tB Patricia a
lA
| Bool
otherwise -> Patricia a
forall a. Patricia a
Nil
intersectionL :: Patricia a -> Patricia b -> Patricia a
intersectionL :: forall a b. Patricia a -> Patricia b -> Patricia a
intersectionL =
(forall x y. S x y a b -> Prefix -> x -> y -> Patricia a)
-> Patricia a -> Patricia b -> Patricia a
forall a b c.
(forall x y. S x y a b -> Prefix -> x -> y -> Patricia c)
-> Patricia a -> Patricia b -> Patricia c
intersection_ ((forall x y. S x y a b -> Prefix -> x -> y -> Patricia a)
-> Patricia a -> Patricia b -> Patricia a)
-> (forall x y. S x y a b -> Prefix -> x -> y -> Patricia a)
-> Patricia a
-> Patricia b
-> Patricia a
forall a b. (a -> b) -> a -> b
$ \S x y a b
s Prefix
k x
a y
b ->
let !(# a
c #) = case S x y a b
s of
S x y a b
L -> (# x
a #)
S x y a b
R -> (# y
b #)
in Prefix -> a -> Patricia a
forall a. Prefix -> a -> Patricia a
Tip Prefix
k a
c
intersectionWith'
:: (a -> b -> c)
-> Patricia a
-> Patricia b
-> Patricia c
intersectionWith' :: forall a b c.
(a -> b -> c) -> Patricia a -> Patricia b -> Patricia c
intersectionWith' a -> b -> c
f =
(forall x y. S x y a b -> Prefix -> x -> y -> Patricia c)
-> Patricia a -> Patricia b -> Patricia c
forall a b c.
(forall x y. S x y a b -> Prefix -> x -> y -> Patricia c)
-> Patricia a -> Patricia b -> Patricia c
intersection_ ((forall x y. S x y a b -> Prefix -> x -> y -> Patricia c)
-> Patricia a -> Patricia b -> Patricia c)
-> (forall x y. S x y a b -> Prefix -> x -> y -> Patricia c)
-> Patricia a
-> Patricia b
-> Patricia c
forall a b. (a -> b) -> a -> b
$ \S x y a b
s Prefix
k x
a y
b ->
Prefix -> c -> Patricia c
forall a. Prefix -> a -> Patricia a
Tip Prefix
k (c -> Patricia c) -> c -> Patricia c
forall a b. (a -> b) -> a -> b
$! case S x y a b
s of
S x y a b
L -> a -> b -> c
f a
x
a b
y
b
S x y a b
R -> a -> b -> c
f a
y
b b
x
a
intersectionWithKey'
:: (Word -> a -> b -> c)
-> Patricia a
-> Patricia b
-> Patricia c
intersectionWithKey' :: forall a b c.
(Prefix -> a -> b -> c) -> Patricia a -> Patricia b -> Patricia c
intersectionWithKey' Prefix -> a -> b -> c
f =
(forall x y. S x y a b -> Prefix -> x -> y -> Patricia c)
-> Patricia a -> Patricia b -> Patricia c
forall a b c.
(forall x y. S x y a b -> Prefix -> x -> y -> Patricia c)
-> Patricia a -> Patricia b -> Patricia c
intersection_ ((forall x y. S x y a b -> Prefix -> x -> y -> Patricia c)
-> Patricia a -> Patricia b -> Patricia c)
-> (forall x y. S x y a b -> Prefix -> x -> y -> Patricia c)
-> Patricia a
-> Patricia b
-> Patricia c
forall a b. (a -> b) -> a -> b
$ \S x y a b
s Prefix
k x
a y
b ->
Prefix -> c -> Patricia c
forall a. Prefix -> a -> Patricia a
Tip Prefix
k (c -> Patricia c) -> c -> Patricia c
forall a b. (a -> b) -> a -> b
$! case S x y a b
s of
S x y a b
L -> Prefix -> a -> b -> c
f Prefix
k a
x
a b
y
b
S x y a b
R -> Prefix -> a -> b -> c
f Prefix
k a
y
b b
x
a
{-# INLINE intersection_ #-}
intersection_
:: (forall x y. S x y a b -> Key -> x -> y -> Patricia c)
-> Patricia a
-> Patricia b
-> Patricia c
intersection_ :: forall a b c.
(forall x y. S x y a b -> Prefix -> x -> y -> Patricia c)
-> Patricia a -> Patricia b -> Patricia c
intersection_ (forall x y. S x y a b -> Prefix -> x -> y -> Patricia c
f :: forall n o. S n o x y -> Word -> n -> o -> Patricia c) =
S a b a b -> Patricia a -> Patricia b -> Patricia c
forall a b. S a b a b -> Patricia a -> Patricia b -> Patricia c
anyAny S a b a b
forall a b. S a b a b
L
where
anyAny
:: forall a b. S a b x y -> Patricia a -> Patricia b -> Patricia c
anyAny :: forall a b. S a b a b -> Patricia a -> Patricia b -> Patricia c
anyAny S a b a b
s Patricia a
tA Patricia b
tB =
case Patricia a
tA of
Bin Prefix
pA Patricia a
lA Patricia a
rA -> S a b a b -> UBin a -> Patricia a -> Patricia b -> Patricia c
forall a b.
S a b a b -> UBin a -> Patricia a -> Patricia b -> Patricia c
binAny S a b a b
s (# Prefix
pA, Patricia a
lA, Patricia a
rA #) Patricia a
tA Patricia b
tB
Tip Prefix
kA a
a -> S a b a b -> UTip a -> Patricia a -> Patricia b -> Patricia c
forall a b.
S a b a b -> UTip a -> Patricia a -> Patricia b -> Patricia c
tipAny S a b a b
s (# Prefix
kA, a
a #) Patricia a
tA Patricia b
tB
Patricia a
Nil -> Patricia c
forall a. Patricia a
Nil
tipAny
:: forall a b. S a b x y -> UTip a -> Patricia a -> Patricia b -> Patricia c
tipAny :: forall a b.
S a b a b -> UTip a -> Patricia a -> Patricia b -> Patricia c
tipAny S a b a b
s uA :: UTip a
uA@(# Prefix
kA, a
a #) Patricia a
tA Patricia b
tB =
case Patricia b
tB of
Bin Prefix
pB Patricia b
lB Patricia b
rB -> S a b a b -> UTip a -> Patricia a -> UBin b -> Patricia c
forall a b.
S a b a b -> UTip a -> Patricia a -> UBin b -> Patricia c
tipBin S a b a b
s UTip a
uA Patricia a
tA (# Prefix
pB, Patricia b
lB, Patricia b
rB #)
Tip Prefix
kB b
b
| Prefix
kA Prefix -> Prefix -> Bool
forall a. Eq a => a -> a -> Bool
== Prefix
kB -> S a b a b -> Prefix -> a -> b -> Patricia c
forall x y. S x y a b -> Prefix -> x -> y -> Patricia c
f S a b a b
s Prefix
kA a
a b
b
| Bool
otherwise -> Patricia c
forall a. Patricia a
Nil
Patricia b
Nil -> Patricia c
forall a. Patricia a
Nil
binAny
:: forall a b. S a b x y -> UBin a -> Patricia a -> Patricia b -> Patricia c
binAny :: forall a b.
S a b a b -> UBin a -> Patricia a -> Patricia b -> Patricia c
binAny S a b a b
s UBin a
uA Patricia a
tA Patricia b
tB =
case Patricia b
tB of
Bin Prefix
pB Patricia b
lB Patricia b
rB -> S a b a b
-> UBin a -> Patricia a -> UBin b -> Patricia b -> Patricia c
forall a b.
S a b a b
-> UBin a -> Patricia a -> UBin b -> Patricia b -> Patricia c
binBin S a b a b
s UBin a
uA Patricia a
tA (# Prefix
pB, Patricia b
lB, Patricia b
rB #) Patricia b
tB
Tip Prefix
kB b
b -> let !(# S b a a b
s' #) = S a b a b -> (# S b a a b #)
forall a b x y. S a b x y -> (# S b a x y #)
other S a b a b
s
in S b a a b -> UTip b -> Patricia b -> UBin a -> Patricia c
forall a b.
S a b a b -> UTip a -> Patricia a -> UBin b -> Patricia c
tipBin S b a a b
s' (# Prefix
kB, b
b #) Patricia b
tB UBin a
uA
Patricia b
Nil -> Patricia c
forall a. Patricia a
Nil
tipBin
:: forall a b. S a b x y -> UTip a -> Patricia a -> UBin b -> Patricia c
tipBin :: forall a b.
S a b a b -> UTip a -> Patricia a -> UBin b -> Patricia c
tipBin S a b a b
s uA :: UTip a
uA@(# Prefix
kA, a
_ #) Patricia a
tA (# Prefix
pB, Patricia b
lB, Patricia b
rB #)
| Prefix -> Prefix -> Bool
beyond Prefix
pB Prefix
kA = Patricia c
forall a. Patricia a
Nil
| Bool
otherwise = S a b a b -> UTip a -> Patricia a -> Patricia b -> Patricia c
forall a b.
S a b a b -> UTip a -> Patricia a -> Patricia b -> Patricia c
tipAny S a b a b
s UTip a
uA Patricia a
tA (Patricia b -> Patricia c) -> Patricia b -> Patricia c
forall a b. (a -> b) -> a -> b
$ if Prefix
kA Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
pB
then Patricia b
lB
else Patricia b
rB
binBin
:: forall a b. S a b x y -> UBin a -> Patricia a -> UBin b -> Patricia b -> Patricia c
binBin :: forall a b.
S a b a b
-> UBin a -> Patricia a -> UBin b -> Patricia b -> Patricia c
binBin S a b a b
s uA :: UBin a
uA@(# Prefix
pA, Patricia a
lA, Patricia a
rA #) Patricia a
tA uB :: UBin b
uB@(# Prefix
pB, Patricia b
lB, Patricia b
rB #) Patricia b
tB =
case Prefix -> Prefix -> Ordering
forall a. Ord a => a -> a -> Ordering
Prelude.compare Prefix
pA Prefix
pB of
Ordering
EQ -> Prefix -> Patricia c -> Patricia c -> Patricia c
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebin Prefix
pA (S a b a b -> Patricia a -> Patricia b -> Patricia c
forall a b. S a b a b -> Patricia a -> Patricia b -> Patricia c
anyAny S a b a b
s Patricia a
lA Patricia b
lB) (S a b a b -> Patricia a -> Patricia b -> Patricia c
forall a b. S a b a b -> Patricia a -> Patricia b -> Patricia c
anyAny S a b a b
s Patricia a
rA Patricia b
rB)
Ordering
LT | Prefix
pB Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
pA -> let !(# S b a a b
s' #) = S a b a b -> (# S b a a b #)
forall a b x y. S a b x y -> (# S b a x y #)
other S a b a b
s
in S b a a b -> UBin b -> Patricia b -> Patricia a -> Patricia c
forall a b.
S a b a b -> UBin a -> Patricia a -> Patricia b -> Patricia c
binAny S b a a b
s' UBin b
uB Patricia b
tB Patricia a
rA
| Prefix
pA Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
pB -> S a b a b -> UBin a -> Patricia a -> Patricia b -> Patricia c
forall a b.
S a b a b -> UBin a -> Patricia a -> Patricia b -> Patricia c
binAny S a b a b
s UBin a
uA Patricia a
tA Patricia b
lB
| Bool
otherwise -> Patricia c
forall a. Patricia a
Nil
Ordering
GT | Prefix
pA Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
pB -> S a b a b -> UBin a -> Patricia a -> Patricia b -> Patricia c
forall a b.
S a b a b -> UBin a -> Patricia a -> Patricia b -> Patricia c
binAny S a b a b
s UBin a
uA Patricia a
tA Patricia b
rB
| Prefix
pB Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
pA -> let !(# S b a a b
s' #) = S a b a b -> (# S b a a b #)
forall a b x y. S a b x y -> (# S b a x y #)
other S a b a b
s
in S b a a b -> UBin b -> Patricia b -> Patricia a -> Patricia c
forall a b.
S a b a b -> UBin a -> Patricia a -> Patricia b -> Patricia c
binAny S b a a b
s' UBin b
uB Patricia b
tB Patricia a
lA
| Bool
otherwise -> Patricia c
forall a. Patricia a
Nil
{-# INLINE merge #-}
merge
:: (Key -> a -> b -> Patricia c)
-> (Key -> a -> Patricia c)
-> (Prefix -> Patricia a -> Patricia a -> Patricia c)
-> (Key -> b -> Patricia c)
-> (Prefix -> Patricia b -> Patricia b -> Patricia c)
-> Patricia a
-> Patricia b
-> Patricia c
merge :: forall a b c.
(Prefix -> a -> b -> Patricia c)
-> (Prefix -> a -> Patricia c)
-> (Prefix -> Patricia a -> Patricia a -> Patricia c)
-> (Prefix -> b -> Patricia c)
-> (Prefix -> Patricia b -> Patricia b -> Patricia c)
-> Patricia a
-> Patricia b
-> Patricia c
merge (Prefix -> a -> b -> Patricia c
f :: Key -> x -> y -> Patricia c) Prefix -> a -> Patricia c
oneX Prefix -> Patricia a -> Patricia a -> Patricia c
treeX Prefix -> b -> Patricia c
oneY Prefix -> Patricia b -> Patricia b -> Patricia c
treeY = S a b a b -> Patricia a -> Patricia b -> Patricia c
forall a b. S a b a b -> Patricia a -> Patricia b -> Patricia c
anyAny S a b a b
forall a b. S a b a b
L
where
{-# INLINE side #-}
side :: (Prefix -> t -> Patricia a)
-> (Prefix -> Patricia t -> Patricia t -> Patricia a)
-> Patricia t
-> Patricia a
side Prefix -> t -> Patricia a
one Prefix -> Patricia t -> Patricia t -> Patricia a
tree Patricia t
t =
case Patricia t
t of
Bin Prefix
p Patricia t
l Patricia t
r -> Prefix -> Patricia t -> Patricia t -> Patricia a
tree Prefix
p Patricia t
l Patricia t
r
Tip Prefix
k t
a -> Prefix -> t -> Patricia a
one Prefix
k t
a
Patricia t
Nil -> Patricia a
forall a. Patricia a
Nil
sideX :: Patricia a -> Patricia c
sideX = (Prefix -> a -> Patricia c)
-> (Prefix -> Patricia a -> Patricia a -> Patricia c)
-> Patricia a
-> Patricia c
forall {t} {a}.
(Prefix -> t -> Patricia a)
-> (Prefix -> Patricia t -> Patricia t -> Patricia a)
-> Patricia t
-> Patricia a
side Prefix -> a -> Patricia c
oneX Prefix -> Patricia a -> Patricia a -> Patricia c
treeX
sideY :: Patricia b -> Patricia c
sideY = (Prefix -> b -> Patricia c)
-> (Prefix -> Patricia b -> Patricia b -> Patricia c)
-> Patricia b
-> Patricia c
forall {t} {a}.
(Prefix -> t -> Patricia a)
-> (Prefix -> Patricia t -> Patricia t -> Patricia a)
-> Patricia t
-> Patricia a
side Prefix -> b -> Patricia c
oneY Prefix -> Patricia b -> Patricia b -> Patricia c
treeY
sideA :: forall a b. S a b x y -> Patricia a -> Patricia c
sideA :: forall a b. S a b a b -> Patricia a -> Patricia c
sideA S a b a b
s Patricia a
tA = case S a b a b
s of
S a b a b
L -> Patricia a -> Patricia c
sideX Patricia a
Patricia a
tA
S a b a b
R -> Patricia b -> Patricia c
sideY Patricia b
Patricia a
tA
sideB :: forall a b. S a b x y -> Patricia b -> Patricia c
sideB :: forall a b. S a b a b -> Patricia b -> Patricia c
sideB S a b a b
s Patricia b
tB = case S a b a b
s of
S a b a b
L -> Patricia b -> Patricia c
sideY Patricia b
Patricia b
tB
S a b a b
R -> Patricia a -> Patricia c
sideX Patricia a
Patricia b
tB
anyAny
:: forall a b. S a b x y -> Patricia a -> Patricia b -> Patricia c
anyAny :: forall a b. S a b a b -> Patricia a -> Patricia b -> Patricia c
anyAny S a b a b
s Patricia a
tA Patricia b
tB =
case Patricia a
tA of
Bin Prefix
pA Patricia a
lA Patricia a
rA -> S a b a b -> UBin a -> Patricia a -> Patricia b -> Patricia c
forall a b.
S a b a b -> UBin a -> Patricia a -> Patricia b -> Patricia c
binAny S a b a b
s (# Prefix
pA, Patricia a
lA, Patricia a
rA #) Patricia a
tA Patricia b
tB
Tip Prefix
kA a
a -> S a b a b -> UTip a -> Patricia a -> Patricia b -> Patricia c
forall a b.
S a b a b -> UTip a -> Patricia a -> Patricia b -> Patricia c
tipAny S a b a b
s (# Prefix
kA, a
a #) Patricia a
tA Patricia b
tB
Patricia a
Nil -> S a b a b -> Patricia b -> Patricia c
forall a b. S a b a b -> Patricia b -> Patricia c
sideB S a b a b
s Patricia b
tB
tipAny
:: forall a b. S a b x y -> UTip a -> Patricia a -> Patricia b -> Patricia c
tipAny :: forall a b.
S a b a b -> UTip a -> Patricia a -> Patricia b -> Patricia c
tipAny S a b a b
s uA :: UTip a
uA@(# Prefix
kA, a
a #) Patricia a
tA Patricia b
tB =
case Patricia b
tB of
Bin Prefix
pB Patricia b
lB Patricia b
rB -> S a b a b -> UTip a -> Patricia a -> UBin b -> Patricia c
forall a b.
S a b a b -> UTip a -> Patricia a -> UBin b -> Patricia c
tipBin S a b a b
s UTip a
uA Patricia a
tA (# Prefix
pB, Patricia b
lB, Patricia b
rB #)
Tip Prefix
kB b
b
| Prefix
kA Prefix -> Prefix -> Bool
forall a. Eq a => a -> a -> Bool
== Prefix
kB -> case S a b a b
s of
S a b a b
L -> Prefix -> a -> b -> Patricia c
f Prefix
kA a
a
a b
b
b
S a b a b
R -> Prefix -> a -> b -> Patricia c
f Prefix
kA a
b
b b
a
a
| Bool
otherwise -> case S a b a b
s of
S a b a b
L -> Prefix -> Patricia c -> Prefix -> Patricia c -> Patricia c
forall a.
Prefix -> Patricia a -> Prefix -> Patricia a -> Patricia a
safeJoin Prefix
kA (Prefix -> a -> Patricia c
oneX Prefix
kA a
a
a) Prefix
kB (Patricia b -> Patricia c
sideY Patricia b
Patricia b
tB)
S a b a b
R -> Prefix -> Patricia c -> Prefix -> Patricia c -> Patricia c
forall a.
Prefix -> Patricia a -> Prefix -> Patricia a -> Patricia a
safeJoin Prefix
kA (Prefix -> b -> Patricia c
oneY Prefix
kA b
a
a) Prefix
kB (Patricia a -> Patricia c
sideX Patricia a
Patricia b
tB)
Patricia b
Nil -> S a b a b -> Patricia a -> Patricia c
forall a b. S a b a b -> Patricia a -> Patricia c
sideA S a b a b
s Patricia a
tA
binAny
:: forall a b. S a b x y -> UBin a -> Patricia a -> Patricia b -> Patricia c
binAny :: forall a b.
S a b a b -> UBin a -> Patricia a -> Patricia b -> Patricia c
binAny S a b a b
s UBin a
uA Patricia a
tA Patricia b
tB =
case Patricia b
tB of
Bin Prefix
pB Patricia b
lB Patricia b
rB -> S a b a b
-> UBin a -> Patricia a -> UBin b -> Patricia b -> Patricia c
forall a b.
S a b a b
-> UBin a -> Patricia a -> UBin b -> Patricia b -> Patricia c
binBin S a b a b
s UBin a
uA Patricia a
tA (# Prefix
pB, Patricia b
lB, Patricia b
rB #) Patricia b
tB
Tip Prefix
kB b
b -> let !(# S b a a b
s' #) = S a b a b -> (# S b a a b #)
forall a b x y. S a b x y -> (# S b a x y #)
other S a b a b
s
in S b a a b -> UTip b -> Patricia b -> UBin a -> Patricia c
forall a b.
S a b a b -> UTip a -> Patricia a -> UBin b -> Patricia c
tipBin S b a a b
s' (# Prefix
kB, b
b #) Patricia b
tB UBin a
uA
Patricia b
Nil -> S a b a b -> Patricia a -> Patricia c
forall a b. S a b a b -> Patricia a -> Patricia c
sideA S a b a b
s Patricia a
tA
tipBin
:: forall a b. S a b x y -> UTip a -> Patricia a -> UBin b -> Patricia c
tipBin :: forall a b.
S a b a b -> UTip a -> Patricia a -> UBin b -> Patricia c
tipBin S a b a b
s uA :: UTip a
uA@(# Prefix
kA, a
a #) Patricia a
tA (# Prefix
pB, Patricia b
lB, Patricia b
rB #)
| Prefix -> Prefix -> Bool
beyond Prefix
pB Prefix
kA = case S a b a b
s of
S a b a b
L -> Prefix -> Patricia c -> Prefix -> Patricia c -> Patricia c
forall a.
Prefix -> Patricia a -> Prefix -> Patricia a -> Patricia a
safeJoin Prefix
kA (Prefix -> a -> Patricia c
oneX Prefix
kA a
a
a) Prefix
pB (Prefix -> Patricia b -> Patricia b -> Patricia c
treeY Prefix
pB Patricia b
Patricia b
lB Patricia b
Patricia b
rB)
S a b a b
R -> Prefix -> Patricia c -> Prefix -> Patricia c -> Patricia c
forall a.
Prefix -> Patricia a -> Prefix -> Patricia a -> Patricia a
safeJoin Prefix
kA (Prefix -> b -> Patricia c
oneY Prefix
kA b
a
a) Prefix
pB (Prefix -> Patricia a -> Patricia a -> Patricia c
treeX Prefix
pB Patricia a
Patricia b
lB Patricia a
Patricia b
rB)
| Prefix
kA Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
pB = Prefix -> Patricia c -> Patricia c -> Patricia c
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebin Prefix
pB (S a b a b -> UTip a -> Patricia a -> Patricia b -> Patricia c
forall a b.
S a b a b -> UTip a -> Patricia a -> Patricia b -> Patricia c
tipAny S a b a b
s UTip a
uA Patricia a
tA Patricia b
lB) (S a b a b -> Patricia b -> Patricia c
forall a b. S a b a b -> Patricia b -> Patricia c
sideB S a b a b
s Patricia b
rB)
| Bool
otherwise = Prefix -> Patricia c -> Patricia c -> Patricia c
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebin Prefix
pB (S a b a b -> Patricia b -> Patricia c
forall a b. S a b a b -> Patricia b -> Patricia c
sideB S a b a b
s Patricia b
lB) (S a b a b -> UTip a -> Patricia a -> Patricia b -> Patricia c
forall a b.
S a b a b -> UTip a -> Patricia a -> Patricia b -> Patricia c
tipAny S a b a b
s UTip a
uA Patricia a
tA Patricia b
rB)
binBin
:: forall a b. S a b x y -> UBin a -> Patricia a -> UBin b -> Patricia b -> Patricia c
binBin :: forall a b.
S a b a b
-> UBin a -> Patricia a -> UBin b -> Patricia b -> Patricia c
binBin S a b a b
s uA :: UBin a
uA@(# Prefix
pA, Patricia a
lA, Patricia a
rA #) Patricia a
tA uB :: UBin b
uB@(# Prefix
pB, Patricia b
lB, Patricia b
rB #) Patricia b
tB =
let {-# NOINLINE no #-}
no :: Patricia c
no = case S a b a b
s of
S a b a b
L -> Prefix -> Patricia c -> Prefix -> Patricia c -> Patricia c
forall a.
Prefix -> Patricia a -> Prefix -> Patricia a -> Patricia a
safeJoin Prefix
pA (Prefix -> Patricia a -> Patricia a -> Patricia c
treeX Prefix
pA Patricia a
Patricia a
lA Patricia a
Patricia a
rA) Prefix
pB (Prefix -> Patricia b -> Patricia b -> Patricia c
treeY Prefix
pB Patricia b
Patricia b
lB Patricia b
Patricia b
rB)
S a b a b
R -> Prefix -> Patricia c -> Prefix -> Patricia c -> Patricia c
forall a.
Prefix -> Patricia a -> Prefix -> Patricia a -> Patricia a
safeJoin Prefix
pA (Prefix -> Patricia b -> Patricia b -> Patricia c
treeY Prefix
pA Patricia b
Patricia a
lA Patricia b
Patricia a
rA) Prefix
pB (Prefix -> Patricia a -> Patricia a -> Patricia c
treeX Prefix
pB Patricia a
Patricia b
lB Patricia a
Patricia b
rB)
in case Prefix -> Prefix -> Ordering
forall a. Ord a => a -> a -> Ordering
Prelude.compare Prefix
pA Prefix
pB of
Ordering
EQ -> Prefix -> Patricia c -> Patricia c -> Patricia c
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebin Prefix
pA (S a b a b -> Patricia a -> Patricia b -> Patricia c
forall a b. S a b a b -> Patricia a -> Patricia b -> Patricia c
anyAny S a b a b
s Patricia a
lA Patricia b
lB) (S a b a b -> Patricia a -> Patricia b -> Patricia c
forall a b. S a b a b -> Patricia a -> Patricia b -> Patricia c
anyAny S a b a b
s Patricia a
rA Patricia b
rB)
Ordering
LT | Prefix
pB Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
pA -> let !(# S b a a b
s' #) = S a b a b -> (# S b a a b #)
forall a b x y. S a b x y -> (# S b a x y #)
other S a b a b
s
in Prefix -> Patricia c -> Patricia c -> Patricia c
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebin Prefix
pA (S a b a b -> Patricia a -> Patricia c
forall a b. S a b a b -> Patricia a -> Patricia c
sideA S a b a b
s Patricia a
lA) (S b a a b -> UBin b -> Patricia b -> Patricia a -> Patricia c
forall a b.
S a b a b -> UBin a -> Patricia a -> Patricia b -> Patricia c
binAny S b a a b
s' UBin b
uB Patricia b
tB Patricia a
rA)
| Prefix
pA Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
pB -> Prefix -> Patricia c -> Patricia c -> Patricia c
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebin Prefix
pB (S a b a b -> UBin a -> Patricia a -> Patricia b -> Patricia c
forall a b.
S a b a b -> UBin a -> Patricia a -> Patricia b -> Patricia c
binAny S a b a b
s UBin a
uA Patricia a
tA Patricia b
lB) (S a b a b -> Patricia b -> Patricia c
forall a b. S a b a b -> Patricia b -> Patricia c
sideB S a b a b
s Patricia b
rB)
| Bool
otherwise -> Patricia c
no
Ordering
GT | Prefix
pA Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
pB -> Prefix -> Patricia c -> Patricia c -> Patricia c
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebin Prefix
pB (S a b a b -> Patricia b -> Patricia c
forall a b. S a b a b -> Patricia b -> Patricia c
sideB S a b a b
s Patricia b
lB) (S a b a b -> UBin a -> Patricia a -> Patricia b -> Patricia c
forall a b.
S a b a b -> UBin a -> Patricia a -> Patricia b -> Patricia c
binAny S a b a b
s UBin a
uA Patricia a
tA Patricia b
rB)
| Prefix
pB Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
pA -> let !(# S b a a b
s' #) = S a b a b -> (# S b a a b #)
forall a b x y. S a b x y -> (# S b a x y #)
other S a b a b
s
in Prefix -> Patricia c -> Patricia c -> Patricia c
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebin Prefix
pA (S b a a b -> UBin b -> Patricia b -> Patricia a -> Patricia c
forall a b.
S a b a b -> UBin a -> Patricia a -> Patricia b -> Patricia c
binAny S b a a b
s' UBin b
uB Patricia b
tB Patricia a
lA) (S a b a b -> Patricia a -> Patricia c
forall a b. S a b a b -> Patricia a -> Patricia c
sideA S a b a b
s Patricia a
rA)
| Bool
otherwise -> Patricia c
no
lookup :: Word -> Patricia a -> Maybe a
lookup :: forall a. Prefix -> Patricia a -> Maybe a
lookup !Prefix
w = Patricia a -> Maybe a
go
where
go :: Patricia a -> Maybe a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r
| Prefix -> Prefix -> Bool
beyond Prefix
p Prefix
w -> Maybe a
forall a. Maybe a
Nothing
| Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
p -> Patricia a -> Maybe a
go Patricia a
l
| Bool
otherwise -> Patricia a -> Maybe a
go Patricia a
r
Tip Prefix
k a
a
| Prefix
k Prefix -> Prefix -> Bool
forall a. Eq a => a -> a -> Bool
== Prefix
w -> a -> Maybe a
forall a. a -> Maybe a
Just a
a
| Bool
otherwise -> Maybe a
forall a. Maybe a
Nothing
Patricia a
Nil -> Maybe a
forall a. Maybe a
Nothing
find :: a -> Word -> Patricia a -> a
find :: forall a. a -> Prefix -> Patricia a -> a
find a
d !Prefix
w = Patricia a -> a
go
where
go :: Patricia a -> a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r
| Prefix -> Prefix -> Bool
beyond Prefix
p Prefix
w -> a
d
| Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
p -> Patricia a -> a
go Patricia a
l
| Bool
otherwise -> Patricia a -> a
go Patricia a
r
Tip Prefix
k a
a
| Prefix
k Prefix -> Prefix -> Bool
forall a. Eq a => a -> a -> Bool
== Prefix
w -> a
a
| Bool
otherwise -> a
d
Patricia a
Nil -> a
d
member :: Word -> Patricia a -> Bool
member :: forall a. Prefix -> Patricia a -> Bool
member !Prefix
w = Patricia a -> Bool
go
where
go :: Patricia a -> Bool
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r
| Prefix -> Prefix -> Bool
beyond Prefix
p Prefix
w -> Bool
False
| Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
p -> Patricia a -> Bool
go Patricia a
l
| Bool
otherwise -> Patricia a -> Bool
go Patricia a
r
Tip Prefix
k a
_ -> Prefix
k Prefix -> Prefix -> Bool
forall a. Eq a => a -> a -> Bool
== Prefix
w
Patricia a
Nil -> Bool
False
takeOne :: Word -> Patricia a -> Patricia a
takeOne :: forall a. Prefix -> Patricia a -> Patricia a
takeOne !Prefix
w = Patricia a -> Patricia a
go
where
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r
| Prefix -> Prefix -> Bool
beyond Prefix
p Prefix
w -> Patricia a
forall a. Patricia a
Nil
| Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
p -> Patricia a -> Patricia a
go Patricia a
l
| Bool
otherwise -> Patricia a -> Patricia a
go Patricia a
r
Tip Prefix
k a
_
| Prefix
k Prefix -> Prefix -> Bool
forall a. Eq a => a -> a -> Bool
== Prefix
w -> Patricia a
t
| Bool
otherwise -> Patricia a
forall a. Patricia a
Nil
Patricia a
Nil -> Patricia a
forall a. Patricia a
Nil
dirtyLookup :: Word -> Patricia a -> Maybe a
dirtyLookup :: forall a. Prefix -> Patricia a -> Maybe a
dirtyLookup !Prefix
w = Patricia a -> Maybe a
go
where
go :: Patricia a -> Maybe a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r
| Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
p -> Patricia a -> Maybe a
go Patricia a
l
| Bool
otherwise -> Patricia a -> Maybe a
go Patricia a
r
Tip Prefix
k a
a
| Prefix
k Prefix -> Prefix -> Bool
forall a. Eq a => a -> a -> Bool
== Prefix
w -> a -> Maybe a
forall a. a -> Maybe a
Just a
a
| Bool
otherwise -> Maybe a
forall a. Maybe a
Nothing
Patricia a
Nil -> Maybe a
forall a. Maybe a
Nothing
dirtyFind :: a -> Word -> Patricia a -> a
dirtyFind :: forall a. a -> Prefix -> Patricia a -> a
dirtyFind a
d !Prefix
w = Patricia a -> a
go
where
go :: Patricia a -> a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r
| Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
p -> Patricia a -> a
go Patricia a
l
| Bool
otherwise -> Patricia a -> a
go Patricia a
r
Tip Prefix
k a
a
| Prefix
k Prefix -> Prefix -> Bool
forall a. Eq a => a -> a -> Bool
== Prefix
w -> a
a
| Bool
otherwise -> a
d
Patricia a
Nil -> a
d
dirtyMember :: Word -> Patricia a -> Bool
dirtyMember :: forall a. Prefix -> Patricia a -> Bool
dirtyMember !Prefix
w = Patricia a -> Bool
go
where
go :: Patricia a -> Bool
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r
| Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
p -> Patricia a -> Bool
go Patricia a
l
| Bool
otherwise -> Patricia a -> Bool
go Patricia a
r
Tip Prefix
k a
_ -> Prefix
k Prefix -> Prefix -> Bool
forall a. Eq a => a -> a -> Bool
== Prefix
w
Patricia a
Nil -> Bool
False
insert :: Word -> a -> Patricia a -> Patricia a
insert :: forall a. Prefix -> a -> Patricia a -> Patricia a
insert !Prefix
w a
a = Patricia a -> Patricia a
go
where
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r
| Prefix -> Prefix -> Bool
beyond Prefix
p Prefix
w -> Prefix -> Patricia a -> Prefix -> Patricia a -> Patricia a
forall a.
Prefix -> Patricia a -> Prefix -> Patricia a -> Patricia a
join Prefix
w (Prefix -> a -> Patricia a
forall a. Prefix -> a -> Patricia a
Tip Prefix
w a
a) Prefix
p Patricia a
t
| Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
p -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p (Patricia a -> Patricia a
go Patricia a
l) Patricia a
r
| Bool
otherwise -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p Patricia a
l (Patricia a -> Patricia a
go Patricia a
r)
Tip Prefix
k a
_
| Prefix
k Prefix -> Prefix -> Bool
forall a. Eq a => a -> a -> Bool
== Prefix
w -> Prefix -> a -> Patricia a
forall a. Prefix -> a -> Patricia a
Tip Prefix
k a
a
| Bool
otherwise -> Prefix -> Patricia a -> Prefix -> Patricia a -> Patricia a
forall a.
Prefix -> Patricia a -> Prefix -> Patricia a -> Patricia a
join Prefix
w (Prefix -> a -> Patricia a
forall a. Prefix -> a -> Patricia a
Tip Prefix
w a
a) Prefix
k Patricia a
t
Patricia a
Nil -> Prefix -> a -> Patricia a
forall a. Prefix -> a -> Patricia a
Tip Prefix
w a
a
insertWith :: (a -> a) -> Word -> a -> Patricia a -> Patricia a
insertWith :: forall a. (a -> a) -> Prefix -> a -> Patricia a -> Patricia a
insertWith a -> a
f !Prefix
w a
b = Patricia a -> Patricia a
go
where
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r
| Prefix -> Prefix -> Bool
beyond Prefix
p Prefix
w -> Prefix -> Patricia a -> Prefix -> Patricia a -> Patricia a
forall a.
Prefix -> Patricia a -> Prefix -> Patricia a -> Patricia a
join Prefix
w (Prefix -> a -> Patricia a
forall a. Prefix -> a -> Patricia a
Tip Prefix
w a
b) Prefix
p Patricia a
t
| Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
p -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p (Patricia a -> Patricia a
go Patricia a
l) Patricia a
r
| Bool
otherwise -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p Patricia a
l (Patricia a -> Patricia a
go Patricia a
r)
Tip Prefix
k a
a
| Prefix
k Prefix -> Prefix -> Bool
forall a. Eq a => a -> a -> Bool
== Prefix
w -> Prefix -> a -> Patricia a
forall a. Prefix -> a -> Patricia a
Tip Prefix
k (a -> a
f a
a)
| Bool
otherwise -> Prefix -> Patricia a -> Prefix -> Patricia a -> Patricia a
forall a.
Prefix -> Patricia a -> Prefix -> Patricia a -> Patricia a
join Prefix
w (Prefix -> a -> Patricia a
forall a. Prefix -> a -> Patricia a
Tip Prefix
w a
b) Prefix
k Patricia a
t
Patricia a
Nil -> Prefix -> a -> Patricia a
forall a. Prefix -> a -> Patricia a
Tip Prefix
w a
b
insertWith' :: (a -> a) -> Word -> a -> Patricia a -> Patricia a
insertWith' :: forall a. (a -> a) -> Prefix -> a -> Patricia a -> Patricia a
insertWith' a -> a
f !Prefix
w a
b = Patricia a -> Patricia a
go
where
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r
| Prefix -> Prefix -> Bool
beyond Prefix
p Prefix
w -> Prefix -> Patricia a -> Prefix -> Patricia a -> Patricia a
forall a.
Prefix -> Patricia a -> Prefix -> Patricia a -> Patricia a
join Prefix
w (a
b a -> Patricia a -> Patricia a
forall a b. a -> b -> b
`seq` Prefix -> a -> Patricia a
forall a. Prefix -> a -> Patricia a
Tip Prefix
w a
b) Prefix
p Patricia a
t
| Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
p -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p (Patricia a -> Patricia a
go Patricia a
l) Patricia a
r
| Bool
otherwise -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p Patricia a
l (Patricia a -> Patricia a
go Patricia a
r)
Tip Prefix
k a
a
| Prefix
k Prefix -> Prefix -> Bool
forall a. Eq a => a -> a -> Bool
== Prefix
w -> Prefix -> a -> Patricia a
forall a. Prefix -> a -> Patricia a
Tip Prefix
k (a -> Patricia a) -> a -> Patricia a
forall a b. (a -> b) -> a -> b
$! a -> a
f a
a
| Bool
otherwise -> Prefix -> Patricia a -> Prefix -> Patricia a -> Patricia a
forall a.
Prefix -> Patricia a -> Prefix -> Patricia a -> Patricia a
join Prefix
w (a
b a -> Patricia a -> Patricia a
forall a b. a -> b -> b
`seq` Prefix -> a -> Patricia a
forall a. Prefix -> a -> Patricia a
Tip Prefix
w a
b) Prefix
k Patricia a
t
Patricia a
Nil -> Prefix -> a -> Patricia a
forall a. Prefix -> a -> Patricia a
Tip Prefix
w a
b
adjust :: (a -> a) -> Word -> Patricia a -> Patricia a
adjust :: forall a. (a -> a) -> Prefix -> Patricia a -> Patricia a
adjust a -> a
f !Prefix
w = Patricia a -> Patricia a
go
where
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r
| Prefix -> Prefix -> Bool
beyond Prefix
p Prefix
w -> Patricia a
t
| Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
p -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p (Patricia a -> Patricia a
go Patricia a
l) Patricia a
r
| Bool
otherwise -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p Patricia a
l (Patricia a -> Patricia a
go Patricia a
r)
Tip Prefix
k a
a
| Prefix
k Prefix -> Prefix -> Bool
forall a. Eq a => a -> a -> Bool
== Prefix
w -> Prefix -> a -> Patricia a
forall a. Prefix -> a -> Patricia a
Tip Prefix
k (a -> a
f a
a)
| Bool
otherwise -> Patricia a
t
Patricia a
Nil -> Patricia a
forall a. Patricia a
Nil
adjust' :: (a -> a) -> Word -> Patricia a -> Patricia a
adjust' :: forall a. (a -> a) -> Prefix -> Patricia a -> Patricia a
adjust' a -> a
f !Prefix
w = Patricia a -> Patricia a
go
where
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r
| Prefix -> Prefix -> Bool
beyond Prefix
p Prefix
w -> Patricia a
t
| Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
p -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p (Patricia a -> Patricia a
go Patricia a
l) Patricia a
r
| Bool
otherwise -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p Patricia a
l (Patricia a -> Patricia a
go Patricia a
r)
Tip Prefix
k a
a
| Prefix
k Prefix -> Prefix -> Bool
forall a. Eq a => a -> a -> Bool
== Prefix
w -> Prefix -> a -> Patricia a
forall a. Prefix -> a -> Patricia a
Tip Prefix
k (a -> Patricia a) -> a -> Patricia a
forall a b. (a -> b) -> a -> b
$! a -> a
f a
a
| Bool
otherwise -> Patricia a
t
Patricia a
Nil -> Patricia a
forall a. Patricia a
Nil
delete :: Word -> Patricia a -> Patricia a
delete :: forall a. Prefix -> Patricia a -> Patricia a
delete !Prefix
w = Patricia a -> Patricia a
go
where
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r
| Prefix -> Prefix -> Bool
beyond Prefix
p Prefix
w -> Patricia a
t
| Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
p -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinL Prefix
p (Patricia a -> Patricia a
go Patricia a
l) Patricia a
r
| Bool
otherwise -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinR Prefix
p Patricia a
l (Patricia a -> Patricia a
go Patricia a
r)
Tip Prefix
k a
_
| Prefix
k Prefix -> Prefix -> Bool
forall a. Eq a => a -> a -> Bool
== Prefix
w -> Patricia a
forall a. Patricia a
Nil
| Bool
otherwise -> Patricia a
t
Patricia a
Nil -> Patricia a
forall a. Patricia a
Nil
update :: (a -> Maybe a) -> Word -> Patricia a -> Patricia a
update :: forall a. (a -> Maybe a) -> Prefix -> Patricia a -> Patricia a
update a -> Maybe a
f !Prefix
w = Patricia a -> Patricia a
go
where
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r
| Prefix -> Prefix -> Bool
beyond Prefix
p Prefix
w -> Patricia a
t
| Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
p -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinL Prefix
p (Patricia a -> Patricia a
go Patricia a
l) Patricia a
r
| Bool
otherwise -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinR Prefix
p Patricia a
l (Patricia a -> Patricia a
go Patricia a
r)
Tip Prefix
k a
a
| Prefix
k Prefix -> Prefix -> Bool
forall a. Eq a => a -> a -> Bool
== Prefix
w -> Prefix -> Maybe a -> Patricia a
forall a. Prefix -> Maybe a -> Patricia a
retip Prefix
k (a -> Maybe a
f a
a)
| Bool
otherwise -> Patricia a
t
Patricia a
Nil -> Patricia a
forall a. Patricia a
Nil
alter :: (Maybe a -> Maybe a) -> Word -> Patricia a -> Patricia a
alter :: forall a.
(Maybe a -> Maybe a) -> Prefix -> Patricia a -> Patricia a
alter Maybe a -> Maybe a
f !Prefix
w = Patricia a -> Patricia a
go
where
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r
| Prefix -> Prefix -> Bool
beyond Prefix
p Prefix
w -> case Maybe a -> Maybe a
f Maybe a
forall a. Maybe a
Nothing of
Just a
b -> Prefix -> Patricia a -> Prefix -> Patricia a -> Patricia a
forall a.
Prefix -> Patricia a -> Prefix -> Patricia a -> Patricia a
join Prefix
p Patricia a
t Prefix
w (Prefix -> a -> Patricia a
forall a. Prefix -> a -> Patricia a
Tip Prefix
w a
b)
Maybe a
Nothing -> Patricia a
t
| Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
p -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinL Prefix
p (Patricia a -> Patricia a
go Patricia a
l) Patricia a
r
| Bool
otherwise -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinR Prefix
p Patricia a
l (Patricia a -> Patricia a
go Patricia a
r)
Tip Prefix
k a
a
| Prefix
k Prefix -> Prefix -> Bool
forall a. Eq a => a -> a -> Bool
== Prefix
w -> case Maybe a -> Maybe a
f (a -> Maybe a
forall a. a -> Maybe a
Just a
a) of
Just a
b -> Prefix -> a -> Patricia a
forall a. Prefix -> a -> Patricia a
Tip Prefix
k a
b
Maybe a
Nothing -> Patricia a
forall a. Patricia a
Nil
| Bool
otherwise -> case Maybe a -> Maybe a
f Maybe a
forall a. Maybe a
Nothing of
Just a
b -> Prefix -> Patricia a -> Prefix -> Patricia a -> Patricia a
forall a.
Prefix -> Patricia a -> Prefix -> Patricia a -> Patricia a
join Prefix
k Patricia a
t Prefix
w (Prefix -> a -> Patricia a
forall a. Prefix -> a -> Patricia a
Tip Prefix
w a
b)
Maybe a
Nothing -> Patricia a
t
Patricia a
Nil -> case Maybe a -> Maybe a
f Maybe a
forall a. Maybe a
Nothing of
Just a
b -> Prefix -> a -> Patricia a
forall a. Prefix -> a -> Patricia a
Tip Prefix
w a
b
Maybe a
Nothing -> Patricia a
forall a. Patricia a
Nil
lookupL :: Word -> Patricia a -> Maybe (Lookup a)
lookupL :: forall a. Prefix -> Patricia a -> Maybe (Lookup a)
lookupL !Prefix
w = Patricia a -> Maybe (Lookup a)
go
where
go :: Patricia a -> Maybe (Lookup a)
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r ->
if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
p
then if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
p
then Patricia a -> Maybe (Lookup a)
go Patricia a
l
else Maybe (Lookup a)
forall a. Maybe a
Nothing
else Lookup a -> Maybe (Lookup a)
forall a. a -> Maybe a
Just (Lookup a -> Maybe (Lookup a)) -> Lookup a -> Maybe (Lookup a)
forall a b. (a -> b) -> a -> b
$! if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
p
then case Patricia a -> Maybe (Lookup a)
go Patricia a
r of
Just Lookup a
x -> Lookup a
x
Maybe (Lookup a)
Nothing -> Patricia a -> Lookup a
forall a. Patricia a -> Lookup a
unsafeLookupMaxWithKey Patricia a
l
else Patricia a -> Lookup a
forall a. Patricia a -> Lookup a
unsafeLookupMaxWithKey Patricia a
r
Tip Prefix
k a
a
| Prefix
k Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix
w -> Lookup a -> Maybe (Lookup a)
forall a. a -> Maybe a
Just (Lookup a -> Maybe (Lookup a)) -> Lookup a -> Maybe (Lookup a)
forall a b. (a -> b) -> a -> b
$! Prefix -> a -> Lookup a
forall a. Prefix -> a -> Lookup a
Lookup Prefix
k a
a
| Bool
otherwise -> Maybe (Lookup a)
forall a. Maybe a
Nothing
Patricia a
Nil -> Maybe (Lookup a)
forall a. Maybe a
Nothing
lookupR :: Word -> Patricia a -> Maybe (Lookup a)
lookupR :: forall a. Prefix -> Patricia a -> Maybe (Lookup a)
lookupR !Prefix
w = Patricia a -> Maybe (Lookup a)
go
where
go :: Patricia a -> Maybe (Lookup a)
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r ->
if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
p
then Lookup a -> Maybe (Lookup a)
forall a. a -> Maybe a
Just (Lookup a -> Maybe (Lookup a)) -> Lookup a -> Maybe (Lookup a)
forall a b. (a -> b) -> a -> b
$! if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
p
then case Patricia a -> Maybe (Lookup a)
go Patricia a
l of
Just Lookup a
x -> Lookup a
x
Maybe (Lookup a)
Nothing -> Patricia a -> Lookup a
forall a. Patricia a -> Lookup a
unsafeLookupMinWithKey Patricia a
r
else Patricia a -> Lookup a
forall a. Patricia a -> Lookup a
unsafeLookupMinWithKey Patricia a
l
else if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
p
then Patricia a -> Maybe (Lookup a)
go Patricia a
r
else Maybe (Lookup a)
forall a. Maybe a
Nothing
Tip Prefix
k a
a
| Prefix
k Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix
w -> Lookup a -> Maybe (Lookup a)
forall a. a -> Maybe a
Just (Lookup a -> Maybe (Lookup a)) -> Lookup a -> Maybe (Lookup a)
forall a b. (a -> b) -> a -> b
$! Prefix -> a -> Lookup a
forall a. Prefix -> a -> Lookup a
Lookup Prefix
k a
a
| Bool
otherwise -> Maybe (Lookup a)
forall a. Maybe a
Nothing
Patricia a
Nil -> Maybe (Lookup a)
forall a. Maybe a
Nothing
adjustL :: (a -> a) -> Word -> Patricia a -> Patricia a
adjustL :: forall a. (a -> a) -> Prefix -> Patricia a -> Patricia a
adjustL a -> a
f !Prefix
w = Patricia a -> Patricia a
go
where
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r ->
if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
p
then if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
p
then Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p (Patricia a -> Patricia a
go Patricia a
l) Patricia a
r
else Patricia a
t
else Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p ((a -> a) -> Patricia a -> Patricia a
forall a b. (a -> b) -> Patricia a -> Patricia b
Data.Patricia.Word.Strict.Internal.map a -> a
f Patricia a
l) (Patricia a -> Patricia a) -> Patricia a -> Patricia a
forall a b. (a -> b) -> a -> b
$
if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
p
then Patricia a -> Patricia a
go Patricia a
r
else (a -> a) -> Patricia a -> Patricia a
forall a b. (a -> b) -> Patricia a -> Patricia b
Data.Patricia.Word.Strict.Internal.map a -> a
f Patricia a
r
Tip Prefix
k a
a
| Prefix
k Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix
w -> Prefix -> a -> Patricia a
forall a. Prefix -> a -> Patricia a
Tip Prefix
k (a -> a
f a
a)
| Bool
otherwise -> Patricia a
t
Patricia a
Nil -> Patricia a
forall a. Patricia a
Nil
adjustL' :: (a -> a) -> Word -> Patricia a -> Patricia a
adjustL' :: forall a. (a -> a) -> Prefix -> Patricia a -> Patricia a
adjustL' a -> a
f !Prefix
w = Patricia a -> Patricia a
go
where
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r ->
if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
p
then if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
p
then Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p (Patricia a -> Patricia a
go Patricia a
l) Patricia a
r
else Patricia a
t
else Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p ((a -> a) -> Patricia a -> Patricia a
forall a b. (a -> b) -> Patricia a -> Patricia b
map' a -> a
f Patricia a
l) (Patricia a -> Patricia a) -> Patricia a -> Patricia a
forall a b. (a -> b) -> a -> b
$
if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
p
then Patricia a -> Patricia a
go Patricia a
r
else (a -> a) -> Patricia a -> Patricia a
forall a b. (a -> b) -> Patricia a -> Patricia b
map' a -> a
f Patricia a
r
Tip Prefix
k a
a
| Prefix
k Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix
w -> Prefix -> a -> Patricia a
forall a. Prefix -> a -> Patricia a
Tip Prefix
k (a -> Patricia a) -> a -> Patricia a
forall a b. (a -> b) -> a -> b
$! a -> a
f a
a
| Bool
otherwise -> Patricia a
t
Patricia a
Nil -> Patricia a
forall a. Patricia a
Nil
adjustLWithKey :: (Word -> a -> a) -> Word -> Patricia a -> Patricia a
adjustLWithKey :: forall a. (Prefix -> a -> a) -> Prefix -> Patricia a -> Patricia a
adjustLWithKey Prefix -> a -> a
f !Prefix
w = Patricia a -> Patricia a
go
where
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r ->
if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
p
then if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
p
then Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p (Patricia a -> Patricia a
go Patricia a
l) Patricia a
r
else Patricia a
t
else Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p ((Prefix -> a -> a) -> Patricia a -> Patricia a
forall a b. (Prefix -> a -> b) -> Patricia a -> Patricia b
mapWithKey Prefix -> a -> a
f Patricia a
l) (Patricia a -> Patricia a) -> Patricia a -> Patricia a
forall a b. (a -> b) -> a -> b
$
if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
p
then Patricia a -> Patricia a
go Patricia a
r
else (Prefix -> a -> a) -> Patricia a -> Patricia a
forall a b. (Prefix -> a -> b) -> Patricia a -> Patricia b
mapWithKey Prefix -> a -> a
f Patricia a
r
Tip Prefix
k a
a
| Prefix
k Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix
w -> Prefix -> a -> Patricia a
forall a. Prefix -> a -> Patricia a
Tip Prefix
k (Prefix -> a -> a
f Prefix
k a
a)
| Bool
otherwise -> Patricia a
t
Patricia a
Nil -> Patricia a
forall a. Patricia a
Nil
adjustLWithKey' :: (Word -> a -> a) -> Word -> Patricia a -> Patricia a
adjustLWithKey' :: forall a. (Prefix -> a -> a) -> Prefix -> Patricia a -> Patricia a
adjustLWithKey' Prefix -> a -> a
f !Prefix
w = Patricia a -> Patricia a
go
where
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r ->
if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
p
then if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
p
then Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p (Patricia a -> Patricia a
go Patricia a
l) Patricia a
r
else Patricia a
t
else Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p ((Prefix -> a -> a) -> Patricia a -> Patricia a
forall a b. (Prefix -> a -> b) -> Patricia a -> Patricia b
mapWithKey' Prefix -> a -> a
f Patricia a
l) (Patricia a -> Patricia a) -> Patricia a -> Patricia a
forall a b. (a -> b) -> a -> b
$
if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
p
then Patricia a -> Patricia a
go Patricia a
r
else (Prefix -> a -> a) -> Patricia a -> Patricia a
forall a b. (Prefix -> a -> b) -> Patricia a -> Patricia b
mapWithKey' Prefix -> a -> a
f Patricia a
r
Tip Prefix
k a
a
| Prefix
k Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix
w -> Prefix -> a -> Patricia a
forall a. Prefix -> a -> Patricia a
Tip Prefix
k (a -> Patricia a) -> a -> Patricia a
forall a b. (a -> b) -> a -> b
$! Prefix -> a -> a
f Prefix
k a
a
| Bool
otherwise -> Patricia a
t
Patricia a
Nil -> Patricia a
forall a. Patricia a
Nil
deleteL :: Word -> Patricia a -> Patricia a
deleteL :: forall a. Prefix -> Patricia a -> Patricia a
deleteL !Prefix
w = Patricia a -> Patricia a
go
where
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r ->
if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
p
then if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
p
then Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinL Prefix
p (Patricia a -> Patricia a
go Patricia a
l) Patricia a
r
else Patricia a
t
else if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
p
then Patricia a -> Patricia a
go Patricia a
r
else Patricia a
forall a. Patricia a
Nil
Tip Prefix
k a
_
| Prefix
k Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix
w -> Patricia a
forall a. Patricia a
Nil
| Bool
otherwise -> Patricia a
t
Patricia a
Nil -> Patricia a
forall a. Patricia a
Nil
updateL :: (a -> Maybe a) -> Word -> Patricia a -> Patricia a
updateL :: forall a. (a -> Maybe a) -> Prefix -> Patricia a -> Patricia a
updateL a -> Maybe a
f !Prefix
w = Patricia a -> Patricia a
go
where
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r ->
if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
p
then if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
p
then Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinL Prefix
p (Patricia a -> Patricia a
go Patricia a
l) Patricia a
r
else Patricia a
t
else Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebin Prefix
p ((a -> Maybe a) -> Patricia a -> Patricia a
forall a b. (a -> Maybe b) -> Patricia a -> Patricia b
mapMaybe a -> Maybe a
f Patricia a
l) (Patricia a -> Patricia a) -> Patricia a -> Patricia a
forall a b. (a -> b) -> a -> b
$
if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
p
then Patricia a -> Patricia a
go Patricia a
r
else (a -> Maybe a) -> Patricia a -> Patricia a
forall a b. (a -> Maybe b) -> Patricia a -> Patricia b
mapMaybe a -> Maybe a
f Patricia a
r
Tip Prefix
k a
a
| Prefix
k Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix
w -> Prefix -> Maybe a -> Patricia a
forall a. Prefix -> Maybe a -> Patricia a
retip Prefix
k (a -> Maybe a
f a
a)
| Bool
otherwise -> Patricia a
t
Patricia a
Nil -> Patricia a
forall a. Patricia a
Nil
updateLWithKey :: (Word -> a -> Maybe a) -> Word -> Patricia a -> Patricia a
updateLWithKey :: forall a.
(Prefix -> a -> Maybe a) -> Prefix -> Patricia a -> Patricia a
updateLWithKey Prefix -> a -> Maybe a
f !Prefix
w = Patricia a -> Patricia a
go
where
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r ->
if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
p
then if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
p
then Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinL Prefix
p (Patricia a -> Patricia a
go Patricia a
l) Patricia a
r
else Patricia a
t
else Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebin Prefix
p ((Prefix -> a -> Maybe a) -> Patricia a -> Patricia a
forall a b. (Prefix -> a -> Maybe b) -> Patricia a -> Patricia b
mapMaybeWithKey Prefix -> a -> Maybe a
f Patricia a
l) (Patricia a -> Patricia a) -> Patricia a -> Patricia a
forall a b. (a -> b) -> a -> b
$
if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
p
then Patricia a -> Patricia a
go Patricia a
r
else (Prefix -> a -> Maybe a) -> Patricia a -> Patricia a
forall a b. (Prefix -> a -> Maybe b) -> Patricia a -> Patricia b
mapMaybeWithKey Prefix -> a -> Maybe a
f Patricia a
r
Tip Prefix
k a
a
| Prefix
k Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix
w -> Prefix -> Maybe a -> Patricia a
forall a. Prefix -> Maybe a -> Patricia a
retip Prefix
k (Prefix -> a -> Maybe a
f Prefix
k a
a)
| Bool
otherwise -> Patricia a
t
Patricia a
Nil -> Patricia a
forall a. Patricia a
Nil
takeL :: Word -> Patricia a -> Patricia a
takeL :: forall a. Prefix -> Patricia a -> Patricia a
takeL !Prefix
w = Patricia a -> Patricia a
go
where
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r ->
if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
p
then if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
p
then Patricia a -> Patricia a
go Patricia a
l
else Patricia a
forall a. Patricia a
Nil
else if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
p
then Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinR Prefix
p Patricia a
l (Patricia a -> Patricia a
go Patricia a
r)
else Patricia a
t
Tip Prefix
k a
_
| Prefix
k Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix
w -> Patricia a
t
| Bool
otherwise -> Patricia a
forall a. Patricia a
Nil
Patricia a
Nil -> Patricia a
forall a. Patricia a
Nil
adjustR :: (a -> a) -> Word -> Patricia a -> Patricia a
adjustR :: forall a. (a -> a) -> Prefix -> Patricia a -> Patricia a
adjustR a -> a
f !Prefix
w = Patricia a -> Patricia a
go
where
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r ->
if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
p
then let l' :: Patricia a
l' = if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
p
then Patricia a -> Patricia a
go Patricia a
l
else (a -> a) -> Patricia a -> Patricia a
forall a b. (a -> b) -> Patricia a -> Patricia b
Data.Patricia.Word.Strict.Internal.map a -> a
f Patricia a
l
in Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p Patricia a
l' ((a -> a) -> Patricia a -> Patricia a
forall a b. (a -> b) -> Patricia a -> Patricia b
Data.Patricia.Word.Strict.Internal.map a -> a
f Patricia a
r)
else if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
p
then Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p Patricia a
l (Patricia a -> Patricia a
go Patricia a
r)
else Patricia a
t
Tip Prefix
k a
a
| Prefix
k Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix
w -> Prefix -> a -> Patricia a
forall a. Prefix -> a -> Patricia a
Tip Prefix
k (a -> a
f a
a)
| Bool
otherwise -> Patricia a
t
Patricia a
Nil -> Patricia a
forall a. Patricia a
Nil
adjustR' :: (a -> a) -> Word -> Patricia a -> Patricia a
adjustR' :: forall a. (a -> a) -> Prefix -> Patricia a -> Patricia a
adjustR' a -> a
f !Prefix
w = Patricia a -> Patricia a
go
where
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r ->
if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
p
then let l' :: Patricia a
l' = if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
p
then Patricia a -> Patricia a
go Patricia a
l
else (a -> a) -> Patricia a -> Patricia a
forall a b. (a -> b) -> Patricia a -> Patricia b
map' a -> a
f Patricia a
l
in Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p Patricia a
l' ((a -> a) -> Patricia a -> Patricia a
forall a b. (a -> b) -> Patricia a -> Patricia b
map' a -> a
f Patricia a
r)
else if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
p
then Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p Patricia a
l (Patricia a -> Patricia a
go Patricia a
r)
else Patricia a
t
Tip Prefix
k a
a
| Prefix
k Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix
w -> Prefix -> a -> Patricia a
forall a. Prefix -> a -> Patricia a
Tip Prefix
k (a -> Patricia a) -> a -> Patricia a
forall a b. (a -> b) -> a -> b
$! a -> a
f a
a
| Bool
otherwise -> Patricia a
t
Patricia a
Nil -> Patricia a
forall a. Patricia a
Nil
adjustRWithKey :: (Word -> a -> a) -> Word -> Patricia a -> Patricia a
adjustRWithKey :: forall a. (Prefix -> a -> a) -> Prefix -> Patricia a -> Patricia a
adjustRWithKey Prefix -> a -> a
f !Prefix
w = Patricia a -> Patricia a
go
where
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r ->
if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
p
then let l' :: Patricia a
l' = if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
p
then Patricia a -> Patricia a
go Patricia a
l
else (Prefix -> a -> a) -> Patricia a -> Patricia a
forall a b. (Prefix -> a -> b) -> Patricia a -> Patricia b
mapWithKey Prefix -> a -> a
f Patricia a
l
in Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p Patricia a
l' ((Prefix -> a -> a) -> Patricia a -> Patricia a
forall a b. (Prefix -> a -> b) -> Patricia a -> Patricia b
mapWithKey Prefix -> a -> a
f Patricia a
r)
else if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
p
then Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p Patricia a
l (Patricia a -> Patricia a
go Patricia a
r)
else Patricia a
t
Tip Prefix
k a
a
| Prefix
k Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix
w -> Prefix -> a -> Patricia a
forall a. Prefix -> a -> Patricia a
Tip Prefix
k (Prefix -> a -> a
f Prefix
k a
a)
| Bool
otherwise -> Patricia a
t
Patricia a
Nil -> Patricia a
forall a. Patricia a
Nil
adjustRWithKey' :: (Word -> a -> a) -> Word -> Patricia a -> Patricia a
adjustRWithKey' :: forall a. (Prefix -> a -> a) -> Prefix -> Patricia a -> Patricia a
adjustRWithKey' Prefix -> a -> a
f !Prefix
w = Patricia a -> Patricia a
go
where
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r ->
if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
p
then let l' :: Patricia a
l' = if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
p
then Patricia a -> Patricia a
go Patricia a
l
else (Prefix -> a -> a) -> Patricia a -> Patricia a
forall a b. (Prefix -> a -> b) -> Patricia a -> Patricia b
mapWithKey' Prefix -> a -> a
f Patricia a
l
in Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p Patricia a
l' ((Prefix -> a -> a) -> Patricia a -> Patricia a
forall a b. (Prefix -> a -> b) -> Patricia a -> Patricia b
mapWithKey' Prefix -> a -> a
f Patricia a
r)
else if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
p
then Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p Patricia a
l (Patricia a -> Patricia a
go Patricia a
r)
else Patricia a
t
Tip Prefix
k a
a
| Prefix
k Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix
w -> Prefix -> a -> Patricia a
forall a. Prefix -> a -> Patricia a
Tip Prefix
k (a -> Patricia a) -> a -> Patricia a
forall a b. (a -> b) -> a -> b
$! Prefix -> a -> a
f Prefix
k a
a
| Bool
otherwise -> Patricia a
t
Patricia a
Nil -> Patricia a
forall a. Patricia a
Nil
deleteR :: Word -> Patricia a -> Patricia a
deleteR :: forall a. Prefix -> Patricia a -> Patricia a
deleteR !Prefix
w = Patricia a -> Patricia a
go
where
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r ->
if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
p
then if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
p
then Patricia a -> Patricia a
go Patricia a
l
else Patricia a
forall a. Patricia a
Nil
else if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
p
then Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinR Prefix
p Patricia a
l (Patricia a -> Patricia a
go Patricia a
r)
else Patricia a
t
Tip Prefix
k a
_
| Prefix
k Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix
w -> Patricia a
forall a. Patricia a
Nil
| Bool
otherwise -> Patricia a
t
Patricia a
Nil -> Patricia a
forall a. Patricia a
Nil
updateR :: (a -> Maybe a) -> Word -> Patricia a -> Patricia a
updateR :: forall a. (a -> Maybe a) -> Prefix -> Patricia a -> Patricia a
updateR a -> Maybe a
f !Prefix
w = Patricia a -> Patricia a
go
where
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r ->
if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
p
then let l' :: Patricia a
l' = if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
p
then Patricia a -> Patricia a
go Patricia a
l
else (a -> Maybe a) -> Patricia a -> Patricia a
forall a b. (a -> Maybe b) -> Patricia a -> Patricia b
mapMaybe a -> Maybe a
f Patricia a
l
in Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebin Prefix
p Patricia a
l' ((a -> Maybe a) -> Patricia a -> Patricia a
forall a b. (a -> Maybe b) -> Patricia a -> Patricia b
mapMaybe a -> Maybe a
f Patricia a
r)
else if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
p
then Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinR Prefix
p Patricia a
l (Patricia a -> Patricia a
go Patricia a
r)
else Patricia a
t
Tip Prefix
k a
a
| Prefix
k Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix
w -> Prefix -> Maybe a -> Patricia a
forall a. Prefix -> Maybe a -> Patricia a
retip Prefix
k (a -> Maybe a
f a
a)
| Bool
otherwise -> Patricia a
t
Patricia a
Nil -> Patricia a
forall a. Patricia a
Nil
updateRWithKey :: (Word -> a -> Maybe a) -> Word -> Patricia a -> Patricia a
updateRWithKey :: forall a.
(Prefix -> a -> Maybe a) -> Prefix -> Patricia a -> Patricia a
updateRWithKey Prefix -> a -> Maybe a
f !Prefix
w = Patricia a -> Patricia a
go
where
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r ->
if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
p
then let l' :: Patricia a
l' = if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
p
then Patricia a -> Patricia a
go Patricia a
l
else (Prefix -> a -> Maybe a) -> Patricia a -> Patricia a
forall a b. (Prefix -> a -> Maybe b) -> Patricia a -> Patricia b
mapMaybeWithKey Prefix -> a -> Maybe a
f Patricia a
l
in Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebin Prefix
p Patricia a
l' ((Prefix -> a -> Maybe a) -> Patricia a -> Patricia a
forall a b. (Prefix -> a -> Maybe b) -> Patricia a -> Patricia b
mapMaybeWithKey Prefix -> a -> Maybe a
f Patricia a
r)
else if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
p
then Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinR Prefix
p Patricia a
l (Patricia a -> Patricia a
go Patricia a
r)
else Patricia a
t
Tip Prefix
k a
a
| Prefix
k Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix
w -> Prefix -> Maybe a -> Patricia a
forall a. Prefix -> Maybe a -> Patricia a
retip Prefix
k (Prefix -> a -> Maybe a
f Prefix
k a
a)
| Bool
otherwise -> Patricia a
t
Patricia a
Nil -> Patricia a
forall a. Patricia a
Nil
takeR :: Word -> Patricia a -> Patricia a
takeR :: forall a. Prefix -> Patricia a -> Patricia a
takeR !Prefix
w = Patricia a -> Patricia a
go
where
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r ->
if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
p
then if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
p
then Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinL Prefix
p (Patricia a -> Patricia a
go Patricia a
l) Patricia a
r
else Patricia a
t
else if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
p
then Patricia a -> Patricia a
go Patricia a
r
else Patricia a
forall a. Patricia a
Nil
Tip Prefix
k a
_
| Prefix
k Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix
w -> Patricia a
t
| Bool
otherwise -> Patricia a
forall a. Patricia a
Nil
Patricia a
Nil -> Patricia a
forall a. Patricia a
Nil
adjustRange :: (a -> a) -> Range -> Patricia a -> Patricia a
adjustRange :: forall a. (a -> a) -> Range -> Patricia a -> Patricia a
adjustRange a -> a
f (UnsafeRange Prefix
kL Prefix
kR)
| Prefix
kL Prefix -> Prefix -> Bool
forall a. Eq a => a -> a -> Bool
== Prefix
kR = (a -> a) -> Prefix -> Patricia a -> Patricia a
forall a. (a -> a) -> Prefix -> Patricia a -> Patricia a
adjust a -> a
f Prefix
kL
| Bool
otherwise = (a -> a) -> Prefix -> Prefix -> Patricia a -> Patricia a
forall a. (a -> a) -> Prefix -> Prefix -> Patricia a -> Patricia a
unsafeAdjustRange a -> a
f Prefix
kL Prefix
kR
unsafeAdjustRange
:: (a -> a)
-> Word
-> Word
-> Patricia a
-> Patricia a
unsafeAdjustRange :: forall a. (a -> a) -> Prefix -> Prefix -> Patricia a -> Patricia a
unsafeAdjustRange a -> a
f !Prefix
wL !Prefix
wR = Patricia a -> Patricia a
go
where
!mM :: Prefix
mM = Prefix -> Prefix -> Prefix
branchingBit Prefix
wL Prefix
wR
!pM :: Prefix
pM = Prefix -> Prefix -> Prefix
mask Prefix
wL Prefix
mM Prefix -> Prefix -> Prefix
forall a. Bits a => a -> a -> a
.|. Prefix
mM
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r ->
case Prefix -> Prefix -> Ordering
forall a. Ord a => a -> a -> Ordering
Prelude.compare Prefix
p Prefix
pM of
Ordering
EQ -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p ((a -> a) -> Prefix -> Patricia a -> Patricia a
forall a. (a -> a) -> Prefix -> Patricia a -> Patricia a
adjustR a -> a
f Prefix
wL Patricia a
l) ((a -> a) -> Prefix -> Patricia a -> Patricia a
forall a. (a -> a) -> Prefix -> Patricia a -> Patricia a
adjustL a -> a
f Prefix
wR Patricia a
r)
Ordering
LT | Prefix
pM Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
p -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p Patricia a
l (Patricia a -> Patricia a
go Patricia a
r)
| Prefix
p Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
pM -> if Prefix
wL Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
p
then Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p
((a -> a) -> Prefix -> Patricia a -> Patricia a
forall a. (a -> a) -> Prefix -> Patricia a -> Patricia a
adjustR a -> a
f Prefix
wL Patricia a
l)
((a -> a) -> Patricia a -> Patricia a
forall a b. (a -> b) -> Patricia a -> Patricia b
Data.Patricia.Word.Strict.Internal.map a -> a
f Patricia a
r)
else Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p Patricia a
l ((a -> a) -> Prefix -> Patricia a -> Patricia a
forall a. (a -> a) -> Prefix -> Patricia a -> Patricia a
adjustR a -> a
f Prefix
wL Patricia a
r)
| Bool
otherwise -> Patricia a
t
Ordering
GT | Prefix
p Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
pM -> if Prefix
wR Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix
p
then Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p
((a -> a) -> Patricia a -> Patricia a
forall a b. (a -> b) -> Patricia a -> Patricia b
Data.Patricia.Word.Strict.Internal.map a -> a
f Patricia a
l)
((a -> a) -> Prefix -> Patricia a -> Patricia a
forall a. (a -> a) -> Prefix -> Patricia a -> Patricia a
adjustL a -> a
f Prefix
wR Patricia a
r)
else Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p ((a -> a) -> Prefix -> Patricia a -> Patricia a
forall a. (a -> a) -> Prefix -> Patricia a -> Patricia a
adjustL a -> a
f Prefix
wR Patricia a
l) Patricia a
r
| Prefix
pM Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
p -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p (Patricia a -> Patricia a
go Patricia a
l) Patricia a
r
| Bool
otherwise -> Patricia a
t
Tip Prefix
k a
a
| Prefix
k Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix
wL Bool -> Bool -> Bool
&& Prefix
k Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix
wR -> Prefix -> a -> Patricia a
forall a. Prefix -> a -> Patricia a
Tip Prefix
k (a -> a
f a
a)
| Bool
otherwise -> Patricia a
t
Patricia a
Nil -> Patricia a
forall a. Patricia a
Nil
adjustRange' :: (a -> a) -> Range -> Patricia a -> Patricia a
adjustRange' :: forall a. (a -> a) -> Range -> Patricia a -> Patricia a
adjustRange' a -> a
f (UnsafeRange Prefix
kL Prefix
kR)
| Prefix
kL Prefix -> Prefix -> Bool
forall a. Eq a => a -> a -> Bool
== Prefix
kR = (a -> a) -> Prefix -> Patricia a -> Patricia a
forall a. (a -> a) -> Prefix -> Patricia a -> Patricia a
adjust' a -> a
f Prefix
kL
| Bool
otherwise = (a -> a) -> Prefix -> Prefix -> Patricia a -> Patricia a
forall a. (a -> a) -> Prefix -> Prefix -> Patricia a -> Patricia a
unsafeAdjustRange' a -> a
f Prefix
kL Prefix
kR
unsafeAdjustRange'
:: (a -> a)
-> Word
-> Word
-> Patricia a
-> Patricia a
unsafeAdjustRange' :: forall a. (a -> a) -> Prefix -> Prefix -> Patricia a -> Patricia a
unsafeAdjustRange' a -> a
f !Prefix
wL !Prefix
wR = Patricia a -> Patricia a
go
where
!mM :: Prefix
mM = Prefix -> Prefix -> Prefix
branchingBit Prefix
wL Prefix
wR
!pM :: Prefix
pM = Prefix -> Prefix -> Prefix
mask Prefix
wL Prefix
mM Prefix -> Prefix -> Prefix
forall a. Bits a => a -> a -> a
.|. Prefix
mM
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r ->
case Prefix -> Prefix -> Ordering
forall a. Ord a => a -> a -> Ordering
Prelude.compare Prefix
p Prefix
pM of
Ordering
EQ -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p ((a -> a) -> Prefix -> Patricia a -> Patricia a
forall a. (a -> a) -> Prefix -> Patricia a -> Patricia a
adjustR' a -> a
f Prefix
wL Patricia a
l) ((a -> a) -> Prefix -> Patricia a -> Patricia a
forall a. (a -> a) -> Prefix -> Patricia a -> Patricia a
adjustL' a -> a
f Prefix
wR Patricia a
r)
Ordering
LT | Prefix
pM Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
p -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p Patricia a
l (Patricia a -> Patricia a
go Patricia a
r)
| Prefix
p Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
pM -> if Prefix
wL Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
p
then Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p ((a -> a) -> Prefix -> Patricia a -> Patricia a
forall a. (a -> a) -> Prefix -> Patricia a -> Patricia a
adjustR' a -> a
f Prefix
wL Patricia a
l) ((a -> a) -> Patricia a -> Patricia a
forall a b. (a -> b) -> Patricia a -> Patricia b
map' a -> a
f Patricia a
r)
else Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p Patricia a
l ((a -> a) -> Prefix -> Patricia a -> Patricia a
forall a. (a -> a) -> Prefix -> Patricia a -> Patricia a
adjustR' a -> a
f Prefix
wL Patricia a
r)
| Bool
otherwise -> Patricia a
t
Ordering
GT | Prefix
p Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
pM -> if Prefix
wR Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix
p
then Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p ((a -> a) -> Patricia a -> Patricia a
forall a b. (a -> b) -> Patricia a -> Patricia b
map' a -> a
f Patricia a
l) ((a -> a) -> Prefix -> Patricia a -> Patricia a
forall a. (a -> a) -> Prefix -> Patricia a -> Patricia a
adjustL' a -> a
f Prefix
wR Patricia a
r)
else Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p ((a -> a) -> Prefix -> Patricia a -> Patricia a
forall a. (a -> a) -> Prefix -> Patricia a -> Patricia a
adjustL' a -> a
f Prefix
wR Patricia a
l) Patricia a
r
| Prefix
pM Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
p -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p (Patricia a -> Patricia a
go Patricia a
l) Patricia a
r
| Bool
otherwise -> Patricia a
t
Tip Prefix
k a
a
| Prefix
k Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix
wL Bool -> Bool -> Bool
&& Prefix
k Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix
wR -> Prefix -> a -> Patricia a
forall a. Prefix -> a -> Patricia a
Tip Prefix
k (a -> Patricia a) -> a -> Patricia a
forall a b. (a -> b) -> a -> b
$! a -> a
f a
a
| Bool
otherwise -> Patricia a
t
Patricia a
Nil -> Patricia a
forall a. Patricia a
Nil
adjustRangeWithKey :: (Word -> a -> a) -> Range -> Patricia a -> Patricia a
adjustRangeWithKey :: forall a. (Prefix -> a -> a) -> Range -> Patricia a -> Patricia a
adjustRangeWithKey Prefix -> a -> a
f (UnsafeRange Prefix
kL Prefix
kR)
| Prefix
kL Prefix -> Prefix -> Bool
forall a. Eq a => a -> a -> Bool
== Prefix
kR = (a -> a) -> Prefix -> Patricia a -> Patricia a
forall a. (a -> a) -> Prefix -> Patricia a -> Patricia a
adjust (Prefix -> a -> a
f Prefix
kL) Prefix
kL
| Bool
otherwise = (Prefix -> a -> a) -> Prefix -> Prefix -> Patricia a -> Patricia a
forall a.
(Prefix -> a -> a) -> Prefix -> Prefix -> Patricia a -> Patricia a
unsafeAdjustRangeWithKey Prefix -> a -> a
f Prefix
kL Prefix
kR
unsafeAdjustRangeWithKey
:: (Word -> a -> a)
-> Word
-> Word
-> Patricia a
-> Patricia a
unsafeAdjustRangeWithKey :: forall a.
(Prefix -> a -> a) -> Prefix -> Prefix -> Patricia a -> Patricia a
unsafeAdjustRangeWithKey Prefix -> a -> a
f !Prefix
wL !Prefix
wR = Patricia a -> Patricia a
go
where
!mM :: Prefix
mM = Prefix -> Prefix -> Prefix
branchingBit Prefix
wL Prefix
wR
!pM :: Prefix
pM = Prefix -> Prefix -> Prefix
mask Prefix
wL Prefix
mM Prefix -> Prefix -> Prefix
forall a. Bits a => a -> a -> a
.|. Prefix
mM
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r ->
case Prefix -> Prefix -> Ordering
forall a. Ord a => a -> a -> Ordering
Prelude.compare Prefix
p Prefix
pM of
Ordering
EQ -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p ((Prefix -> a -> a) -> Prefix -> Patricia a -> Patricia a
forall a. (Prefix -> a -> a) -> Prefix -> Patricia a -> Patricia a
adjustRWithKey Prefix -> a -> a
f Prefix
wL Patricia a
l) ((Prefix -> a -> a) -> Prefix -> Patricia a -> Patricia a
forall a. (Prefix -> a -> a) -> Prefix -> Patricia a -> Patricia a
adjustLWithKey Prefix -> a -> a
f Prefix
wR Patricia a
r)
Ordering
LT | Prefix
pM Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
p -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p Patricia a
l (Patricia a -> Patricia a
go Patricia a
r)
| Prefix
p Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
pM -> if Prefix
wL Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
p
then Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p ((Prefix -> a -> a) -> Prefix -> Patricia a -> Patricia a
forall a. (Prefix -> a -> a) -> Prefix -> Patricia a -> Patricia a
adjustRWithKey Prefix -> a -> a
f Prefix
wL Patricia a
l) ((Prefix -> a -> a) -> Patricia a -> Patricia a
forall a b. (Prefix -> a -> b) -> Patricia a -> Patricia b
mapWithKey Prefix -> a -> a
f Patricia a
r)
else Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p Patricia a
l ((Prefix -> a -> a) -> Prefix -> Patricia a -> Patricia a
forall a. (Prefix -> a -> a) -> Prefix -> Patricia a -> Patricia a
adjustRWithKey Prefix -> a -> a
f Prefix
wL Patricia a
r)
| Bool
otherwise -> Patricia a
t
Ordering
GT | Prefix
p Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
pM -> if Prefix
wR Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix
p
then Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p ((Prefix -> a -> a) -> Patricia a -> Patricia a
forall a b. (Prefix -> a -> b) -> Patricia a -> Patricia b
mapWithKey Prefix -> a -> a
f Patricia a
l) ((Prefix -> a -> a) -> Prefix -> Patricia a -> Patricia a
forall a. (Prefix -> a -> a) -> Prefix -> Patricia a -> Patricia a
adjustLWithKey Prefix -> a -> a
f Prefix
wR Patricia a
r)
else Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p ((Prefix -> a -> a) -> Prefix -> Patricia a -> Patricia a
forall a. (Prefix -> a -> a) -> Prefix -> Patricia a -> Patricia a
adjustLWithKey Prefix -> a -> a
f Prefix
wR Patricia a
l) Patricia a
r
| Prefix
pM Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
p -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p (Patricia a -> Patricia a
go Patricia a
l) Patricia a
r
| Bool
otherwise -> Patricia a
t
Tip Prefix
k a
a
| Prefix
k Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix
wL Bool -> Bool -> Bool
&& Prefix
k Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix
wR -> Prefix -> a -> Patricia a
forall a. Prefix -> a -> Patricia a
Tip Prefix
k (Prefix -> a -> a
f Prefix
k a
a)
| Bool
otherwise -> Patricia a
t
Patricia a
Nil -> Patricia a
forall a. Patricia a
Nil
adjustRangeWithKey' :: (Word -> a -> a) -> Range -> Patricia a -> Patricia a
adjustRangeWithKey' :: forall a. (Prefix -> a -> a) -> Range -> Patricia a -> Patricia a
adjustRangeWithKey' Prefix -> a -> a
f (UnsafeRange Prefix
kL Prefix
kR)
| Prefix
kL Prefix -> Prefix -> Bool
forall a. Eq a => a -> a -> Bool
== Prefix
kR = (a -> a) -> Prefix -> Patricia a -> Patricia a
forall a. (a -> a) -> Prefix -> Patricia a -> Patricia a
adjust' (Prefix -> a -> a
f Prefix
kL) Prefix
kL
| Bool
otherwise = (Prefix -> a -> a) -> Prefix -> Prefix -> Patricia a -> Patricia a
forall a.
(Prefix -> a -> a) -> Prefix -> Prefix -> Patricia a -> Patricia a
unsafeAdjustRangeWithKey' Prefix -> a -> a
f Prefix
kL Prefix
kR
unsafeAdjustRangeWithKey'
:: (Word -> a -> a)
-> Word
-> Word
-> Patricia a
-> Patricia a
unsafeAdjustRangeWithKey' :: forall a.
(Prefix -> a -> a) -> Prefix -> Prefix -> Patricia a -> Patricia a
unsafeAdjustRangeWithKey' Prefix -> a -> a
f !Prefix
wL !Prefix
wR = Patricia a -> Patricia a
go
where
!mM :: Prefix
mM = Prefix -> Prefix -> Prefix
branchingBit Prefix
wL Prefix
wR
!pM :: Prefix
pM = Prefix -> Prefix -> Prefix
mask Prefix
wL Prefix
mM Prefix -> Prefix -> Prefix
forall a. Bits a => a -> a -> a
.|. Prefix
mM
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r ->
case Prefix -> Prefix -> Ordering
forall a. Ord a => a -> a -> Ordering
Prelude.compare Prefix
p Prefix
pM of
Ordering
EQ -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p ((Prefix -> a -> a) -> Prefix -> Patricia a -> Patricia a
forall a. (Prefix -> a -> a) -> Prefix -> Patricia a -> Patricia a
adjustRWithKey' Prefix -> a -> a
f Prefix
wL Patricia a
l) ((Prefix -> a -> a) -> Prefix -> Patricia a -> Patricia a
forall a. (Prefix -> a -> a) -> Prefix -> Patricia a -> Patricia a
adjustLWithKey' Prefix -> a -> a
f Prefix
wR Patricia a
r)
Ordering
LT | Prefix
pM Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
p -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p Patricia a
l (Patricia a -> Patricia a
go Patricia a
r)
| Prefix
p Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
pM -> if Prefix
wL Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
p
then Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p ((Prefix -> a -> a) -> Prefix -> Patricia a -> Patricia a
forall a. (Prefix -> a -> a) -> Prefix -> Patricia a -> Patricia a
adjustRWithKey' Prefix -> a -> a
f Prefix
wL Patricia a
l) ((Prefix -> a -> a) -> Patricia a -> Patricia a
forall a b. (Prefix -> a -> b) -> Patricia a -> Patricia b
mapWithKey' Prefix -> a -> a
f Patricia a
r)
else Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p Patricia a
l ((Prefix -> a -> a) -> Prefix -> Patricia a -> Patricia a
forall a. (Prefix -> a -> a) -> Prefix -> Patricia a -> Patricia a
adjustRWithKey' Prefix -> a -> a
f Prefix
wL Patricia a
r)
| Bool
otherwise -> Patricia a
t
Ordering
GT | Prefix
p Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
pM -> if Prefix
wR Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix
p
then Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p ((Prefix -> a -> a) -> Patricia a -> Patricia a
forall a b. (Prefix -> a -> b) -> Patricia a -> Patricia b
mapWithKey' Prefix -> a -> a
f Patricia a
l) ((Prefix -> a -> a) -> Prefix -> Patricia a -> Patricia a
forall a. (Prefix -> a -> a) -> Prefix -> Patricia a -> Patricia a
adjustLWithKey' Prefix -> a -> a
f Prefix
wR Patricia a
r)
else Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p ((Prefix -> a -> a) -> Prefix -> Patricia a -> Patricia a
forall a. (Prefix -> a -> a) -> Prefix -> Patricia a -> Patricia a
adjustLWithKey' Prefix -> a -> a
f Prefix
wR Patricia a
l) Patricia a
r
| Prefix
pM Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
p -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p (Patricia a -> Patricia a
go Patricia a
l) Patricia a
r
| Bool
otherwise -> Patricia a
t
Tip Prefix
k a
a
| Prefix
k Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix
wL Bool -> Bool -> Bool
&& Prefix
k Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix
wR -> Prefix -> a -> Patricia a
forall a. Prefix -> a -> Patricia a
Tip Prefix
k (a -> Patricia a) -> a -> Patricia a
forall a b. (a -> b) -> a -> b
$! Prefix -> a -> a
f Prefix
k a
a
| Bool
otherwise -> Patricia a
t
Patricia a
Nil -> Patricia a
forall a. Patricia a
Nil
deleteRange :: Range -> Patricia a -> Patricia a
deleteRange :: forall a. Range -> Patricia a -> Patricia a
deleteRange (UnsafeRange Prefix
kL Prefix
kR)
| Prefix
kL Prefix -> Prefix -> Bool
forall a. Eq a => a -> a -> Bool
== Prefix
kR = Prefix -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a
delete Prefix
kL
| Bool
otherwise = Prefix -> Prefix -> Patricia a -> Patricia a
forall a. Prefix -> Prefix -> Patricia a -> Patricia a
unsafeDeleteRange Prefix
kL Prefix
kR
unsafeDeleteRange
:: Word
-> Word
-> Patricia a
-> Patricia a
unsafeDeleteRange :: forall a. Prefix -> Prefix -> Patricia a -> Patricia a
unsafeDeleteRange !Prefix
wL !Prefix
wR = Patricia a -> Patricia a
go
where
!mM :: Prefix
mM = Prefix -> Prefix -> Prefix
branchingBit Prefix
wL Prefix
wR
!pM :: Prefix
pM = Prefix -> Prefix -> Prefix
mask Prefix
wL Prefix
mM Prefix -> Prefix -> Prefix
forall a. Bits a => a -> a -> a
.|. Prefix
mM
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r ->
case Prefix -> Prefix -> Ordering
forall a. Ord a => a -> a -> Ordering
Prelude.compare Prefix
p Prefix
pM of
Ordering
EQ -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebin Prefix
p (Prefix -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a
deleteR Prefix
wL Patricia a
l) (Prefix -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a
deleteL Prefix
wR Patricia a
r)
Ordering
LT | Prefix
pM Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
p -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinR Prefix
p Patricia a
l (Patricia a -> Patricia a
go Patricia a
r)
| Prefix
p Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
pM -> if Prefix
wL Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
p
then Prefix -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a
deleteR Prefix
wL Patricia a
l
else Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinR Prefix
p Patricia a
l (Prefix -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a
deleteR Prefix
wL Patricia a
r)
| Bool
otherwise -> Patricia a
t
Ordering
GT | Prefix
p Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
pM -> if Prefix
wR Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix
p
then Prefix -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a
deleteL Prefix
wR Patricia a
r
else Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinL Prefix
p (Prefix -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a
deleteL Prefix
wR Patricia a
l) Patricia a
r
| Prefix
pM Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
p -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinL Prefix
p (Patricia a -> Patricia a
go Patricia a
l) Patricia a
r
| Bool
otherwise -> Patricia a
t
Tip Prefix
k a
_
| Prefix
k Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix
wL Bool -> Bool -> Bool
&& Prefix
k Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix
wR -> Patricia a
forall a. Patricia a
Nil
| Bool
otherwise -> Patricia a
t
Patricia a
Nil -> Patricia a
forall a. Patricia a
Nil
updateRange :: (a -> Maybe a) -> Range -> Patricia a -> Patricia a
updateRange :: forall a. (a -> Maybe a) -> Range -> Patricia a -> Patricia a
updateRange a -> Maybe a
f (UnsafeRange Prefix
kL Prefix
kR)
| Prefix
kL Prefix -> Prefix -> Bool
forall a. Eq a => a -> a -> Bool
== Prefix
kR = (a -> Maybe a) -> Prefix -> Patricia a -> Patricia a
forall a. (a -> Maybe a) -> Prefix -> Patricia a -> Patricia a
update a -> Maybe a
f Prefix
kL
| Bool
otherwise = (a -> Maybe a) -> Prefix -> Prefix -> Patricia a -> Patricia a
forall a.
(a -> Maybe a) -> Prefix -> Prefix -> Patricia a -> Patricia a
unsafeUpdateRange a -> Maybe a
f Prefix
kL Prefix
kR
unsafeUpdateRange
:: (a -> Maybe a)
-> Word
-> Word
-> Patricia a
-> Patricia a
unsafeUpdateRange :: forall a.
(a -> Maybe a) -> Prefix -> Prefix -> Patricia a -> Patricia a
unsafeUpdateRange a -> Maybe a
f !Prefix
wL !Prefix
wR = Patricia a -> Patricia a
go
where
!mM :: Prefix
mM = Prefix -> Prefix -> Prefix
branchingBit Prefix
wL Prefix
wR
!pM :: Prefix
pM = Prefix -> Prefix -> Prefix
mask Prefix
wL Prefix
mM Prefix -> Prefix -> Prefix
forall a. Bits a => a -> a -> a
.|. Prefix
mM
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r ->
case Prefix -> Prefix -> Ordering
forall a. Ord a => a -> a -> Ordering
Prelude.compare Prefix
p Prefix
pM of
Ordering
EQ -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebin Prefix
p ((a -> Maybe a) -> Prefix -> Patricia a -> Patricia a
forall a. (a -> Maybe a) -> Prefix -> Patricia a -> Patricia a
updateR a -> Maybe a
f Prefix
wL Patricia a
l) ((a -> Maybe a) -> Prefix -> Patricia a -> Patricia a
forall a. (a -> Maybe a) -> Prefix -> Patricia a -> Patricia a
updateL a -> Maybe a
f Prefix
wR Patricia a
r)
Ordering
LT | Prefix
pM Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
p -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinR Prefix
p Patricia a
l (Patricia a -> Patricia a
go Patricia a
r)
| Prefix
p Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
pM -> if Prefix
wL Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
p
then Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinL Prefix
p ((a -> Maybe a) -> Prefix -> Patricia a -> Patricia a
forall a. (a -> Maybe a) -> Prefix -> Patricia a -> Patricia a
updateR a -> Maybe a
f Prefix
wL Patricia a
l) ((a -> Maybe a) -> Patricia a -> Patricia a
forall a b. (a -> Maybe b) -> Patricia a -> Patricia b
mapMaybe a -> Maybe a
f Patricia a
r)
else Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinR Prefix
p Patricia a
l ((a -> Maybe a) -> Prefix -> Patricia a -> Patricia a
forall a. (a -> Maybe a) -> Prefix -> Patricia a -> Patricia a
updateR a -> Maybe a
f Prefix
wL Patricia a
r)
| Bool
otherwise -> Patricia a
t
Ordering
GT | Prefix
p Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
pM -> if Prefix
wR Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix
p
then Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinR Prefix
p ((a -> Maybe a) -> Patricia a -> Patricia a
forall a b. (a -> Maybe b) -> Patricia a -> Patricia b
mapMaybe a -> Maybe a
f Patricia a
l) ((a -> Maybe a) -> Prefix -> Patricia a -> Patricia a
forall a. (a -> Maybe a) -> Prefix -> Patricia a -> Patricia a
updateL a -> Maybe a
f Prefix
wR Patricia a
r)
else Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinL Prefix
p ((a -> Maybe a) -> Prefix -> Patricia a -> Patricia a
forall a. (a -> Maybe a) -> Prefix -> Patricia a -> Patricia a
updateL a -> Maybe a
f Prefix
wR Patricia a
l) Patricia a
r
| Prefix
pM Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
p -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinL Prefix
p (Patricia a -> Patricia a
go Patricia a
l) Patricia a
r
| Bool
otherwise -> Patricia a
t
Tip Prefix
k a
a
| Prefix
k Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix
wL Bool -> Bool -> Bool
&& Prefix
k Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix
wR -> Prefix -> Maybe a -> Patricia a
forall a. Prefix -> Maybe a -> Patricia a
retip Prefix
k (a -> Maybe a
f a
a)
| Bool
otherwise -> Patricia a
t
Patricia a
Nil -> Patricia a
forall a. Patricia a
Nil
updateRangeWithKey :: (Word -> a -> Maybe a) -> Range -> Patricia a -> Patricia a
updateRangeWithKey :: forall a.
(Prefix -> a -> Maybe a) -> Range -> Patricia a -> Patricia a
updateRangeWithKey Prefix -> a -> Maybe a
f (UnsafeRange Prefix
kL Prefix
kR)
| Prefix
kL Prefix -> Prefix -> Bool
forall a. Eq a => a -> a -> Bool
== Prefix
kR = (a -> Maybe a) -> Prefix -> Patricia a -> Patricia a
forall a. (a -> Maybe a) -> Prefix -> Patricia a -> Patricia a
update (Prefix -> a -> Maybe a
f Prefix
kL) Prefix
kL
| Bool
otherwise = (Prefix -> a -> Maybe a)
-> Prefix -> Prefix -> Patricia a -> Patricia a
forall a.
(Prefix -> a -> Maybe a)
-> Prefix -> Prefix -> Patricia a -> Patricia a
unsafeUpdateRangeWithKey Prefix -> a -> Maybe a
f Prefix
kL Prefix
kR
unsafeUpdateRangeWithKey
:: (Word -> a -> Maybe a)
-> Word
-> Word
-> Patricia a
-> Patricia a
unsafeUpdateRangeWithKey :: forall a.
(Prefix -> a -> Maybe a)
-> Prefix -> Prefix -> Patricia a -> Patricia a
unsafeUpdateRangeWithKey Prefix -> a -> Maybe a
f !Prefix
wL !Prefix
wR = Patricia a -> Patricia a
go
where
!mM :: Prefix
mM = Prefix -> Prefix -> Prefix
branchingBit Prefix
wL Prefix
wR
!pM :: Prefix
pM = Prefix -> Prefix -> Prefix
mask Prefix
wL Prefix
mM Prefix -> Prefix -> Prefix
forall a. Bits a => a -> a -> a
.|. Prefix
mM
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r ->
case Prefix -> Prefix -> Ordering
forall a. Ord a => a -> a -> Ordering
Prelude.compare Prefix
p Prefix
pM of
Ordering
EQ -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebin Prefix
p ((Prefix -> a -> Maybe a) -> Prefix -> Patricia a -> Patricia a
forall a.
(Prefix -> a -> Maybe a) -> Prefix -> Patricia a -> Patricia a
updateRWithKey Prefix -> a -> Maybe a
f Prefix
wL Patricia a
l) ((Prefix -> a -> Maybe a) -> Prefix -> Patricia a -> Patricia a
forall a.
(Prefix -> a -> Maybe a) -> Prefix -> Patricia a -> Patricia a
updateLWithKey Prefix -> a -> Maybe a
f Prefix
wR Patricia a
r)
Ordering
LT | Prefix
pM Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
p -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinR Prefix
p Patricia a
l (Patricia a -> Patricia a
go Patricia a
r)
| Prefix
p Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
pM -> if Prefix
wL Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
p
then Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinL Prefix
p ((Prefix -> a -> Maybe a) -> Prefix -> Patricia a -> Patricia a
forall a.
(Prefix -> a -> Maybe a) -> Prefix -> Patricia a -> Patricia a
updateRWithKey Prefix -> a -> Maybe a
f Prefix
wL Patricia a
l)
((Prefix -> a -> Maybe a) -> Patricia a -> Patricia a
forall a b. (Prefix -> a -> Maybe b) -> Patricia a -> Patricia b
mapMaybeWithKey Prefix -> a -> Maybe a
f Patricia a
r)
else Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinR Prefix
p Patricia a
l ((Prefix -> a -> Maybe a) -> Prefix -> Patricia a -> Patricia a
forall a.
(Prefix -> a -> Maybe a) -> Prefix -> Patricia a -> Patricia a
updateRWithKey Prefix -> a -> Maybe a
f Prefix
wL Patricia a
r)
| Bool
otherwise -> Patricia a
t
Ordering
GT | Prefix
p Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
pM -> if Prefix
wR Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix
p
then Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinR Prefix
p ((Prefix -> a -> Maybe a) -> Patricia a -> Patricia a
forall a b. (Prefix -> a -> Maybe b) -> Patricia a -> Patricia b
mapMaybeWithKey Prefix -> a -> Maybe a
f Patricia a
l)
((Prefix -> a -> Maybe a) -> Prefix -> Patricia a -> Patricia a
forall a.
(Prefix -> a -> Maybe a) -> Prefix -> Patricia a -> Patricia a
updateLWithKey Prefix -> a -> Maybe a
f Prefix
wR Patricia a
r)
else Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinL Prefix
p ((Prefix -> a -> Maybe a) -> Prefix -> Patricia a -> Patricia a
forall a.
(Prefix -> a -> Maybe a) -> Prefix -> Patricia a -> Patricia a
updateLWithKey Prefix -> a -> Maybe a
f Prefix
wR Patricia a
l) Patricia a
r
| Prefix
pM Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
p -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinL Prefix
p (Patricia a -> Patricia a
go Patricia a
l) Patricia a
r
| Bool
otherwise -> Patricia a
t
Tip Prefix
k a
a
| Prefix
k Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix
wL Bool -> Bool -> Bool
&& Prefix
k Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix
wR -> Prefix -> Maybe a -> Patricia a
forall a. Prefix -> Maybe a -> Patricia a
retip Prefix
k (Prefix -> a -> Maybe a
f Prefix
k a
a)
| Bool
otherwise -> Patricia a
t
Patricia a
Nil -> Patricia a
forall a. Patricia a
Nil
takeRange :: Range -> Patricia a -> Patricia a
takeRange :: forall a. Range -> Patricia a -> Patricia a
takeRange (UnsafeRange Prefix
kL Prefix
kR)
| Prefix
kL Prefix -> Prefix -> Bool
forall a. Eq a => a -> a -> Bool
== Prefix
kR = Prefix -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a
takeOne Prefix
kL
| Bool
otherwise = Prefix -> Prefix -> Patricia a -> Patricia a
forall a. Prefix -> Prefix -> Patricia a -> Patricia a
unsafeTakeRange Prefix
kL Prefix
kR
unsafeTakeRange
:: Word
-> Word
-> Patricia a
-> Patricia a
unsafeTakeRange :: forall a. Prefix -> Prefix -> Patricia a -> Patricia a
unsafeTakeRange !Prefix
wL !Prefix
wR = Patricia a -> Patricia a
go
where
!mM :: Prefix
mM = Prefix -> Prefix -> Prefix
branchingBit Prefix
wL Prefix
wR
!pM :: Prefix
pM = Prefix -> Prefix -> Prefix
mask Prefix
wL Prefix
mM Prefix -> Prefix -> Prefix
forall a. Bits a => a -> a -> a
.|. Prefix
mM
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r ->
case Prefix -> Prefix -> Ordering
forall a. Ord a => a -> a -> Ordering
Prelude.compare Prefix
p Prefix
pM of
Ordering
EQ -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebin Prefix
p (Prefix -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a
takeR Prefix
wL Patricia a
l) (Prefix -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a
takeL Prefix
wR Patricia a
r)
Ordering
LT | Prefix
pM Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
p -> Patricia a -> Patricia a
go Patricia a
r
| Prefix
p Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
pM -> if Prefix
wL Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
p
then Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinL Prefix
p (Prefix -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a
takeR Prefix
wL Patricia a
l) Patricia a
r
else Prefix -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a
takeR Prefix
wL Patricia a
r
| Bool
otherwise -> Patricia a
forall a. Patricia a
Nil
Ordering
GT | Prefix
p Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
pM -> if Prefix
wR Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix
p
then Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinR Prefix
p Patricia a
l (Prefix -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a
takeL Prefix
wR Patricia a
r)
else Prefix -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a
takeL Prefix
wR Patricia a
l
| Prefix
pM Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
p -> Patricia a -> Patricia a
go Patricia a
l
| Bool
otherwise -> Patricia a
forall a. Patricia a
Nil
Tip Prefix
k a
_
| Prefix
k Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix
wL Bool -> Bool -> Bool
&& Prefix
k Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix
wR -> Patricia a
t
| Bool
otherwise -> Patricia a
forall a. Patricia a
Nil
Patricia a
Nil -> Patricia a
forall a. Patricia a
Nil
data Split l r = Split !(Patricia l) !(Patricia r)
deriving Int -> Split l r -> ShowS
[Split l r] -> ShowS
Split l r -> String
(Int -> Split l r -> ShowS)
-> (Split l r -> String)
-> ([Split l r] -> ShowS)
-> Show (Split l r)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall l r. (Show l, Show r) => Int -> Split l r -> ShowS
forall l r. (Show l, Show r) => [Split l r] -> ShowS
forall l r. (Show l, Show r) => Split l r -> String
$cshowsPrec :: forall l r. (Show l, Show r) => Int -> Split l r -> ShowS
showsPrec :: Int -> Split l r -> ShowS
$cshow :: forall l r. (Show l, Show r) => Split l r -> String
show :: Split l r -> String
$cshowList :: forall l r. (Show l, Show r) => [Split l r] -> ShowS
showList :: [Split l r] -> ShowS
Show
splitL :: Word -> Patricia a -> Split a a
splitL :: forall a. Prefix -> Patricia a -> Split a a
splitL !Prefix
w = \Patricia a
t ->
case Patricia a -> (# Patricia a, Patricia a #)
go Patricia a
t of
(# !Patricia a
l, !Patricia a
r #) -> Patricia a -> Patricia a -> Split a a
forall l r. Patricia l -> Patricia r -> Split l r
Split Patricia a
l Patricia a
r
where
go :: Patricia a -> (# Patricia a, Patricia a #)
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r ->
if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
p
then if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
p
then let !(# !Patricia a
ll, !Patricia a
lr #) = Patricia a -> (# Patricia a, Patricia a #)
go Patricia a
l
in (# Patricia a
ll, Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinL Prefix
p Patricia a
lr Patricia a
r #)
else (# Patricia a
forall a. Patricia a
Nil, Patricia a
t #)
else if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
p
then let !(# !Patricia a
rl, !Patricia a
rr #) = Patricia a -> (# Patricia a, Patricia a #)
go Patricia a
r
in (# Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinR Prefix
p Patricia a
l Patricia a
rl, Patricia a
rr #)
else (# Patricia a
t, Patricia a
forall a. Patricia a
Nil #)
Tip Prefix
k a
_
| Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix
k -> (# Patricia a
t, Patricia a
forall a. Patricia a
Nil #)
| Bool
otherwise -> (# Patricia a
forall a. Patricia a
Nil, Patricia a
t #)
Patricia a
Nil -> (# Patricia a
forall a. Patricia a
Nil, Patricia a
forall a. Patricia a
Nil #)
splitR :: Word -> Patricia a -> Split a a
splitR :: forall a. Prefix -> Patricia a -> Split a a
splitR !Prefix
w = \Patricia a
t ->
case Patricia a -> (# Patricia a, Patricia a #)
go Patricia a
t of
(# !Patricia a
l, !Patricia a
r #) -> Patricia a -> Patricia a -> Split a a
forall l r. Patricia l -> Patricia r -> Split l r
Split Patricia a
l Patricia a
r
where
go :: Patricia a -> (# Patricia a, Patricia a #)
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r ->
if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
p
then if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
p
then let !(# !Patricia a
ll, !Patricia a
lr #) = Patricia a -> (# Patricia a, Patricia a #)
go Patricia a
l
in (# Patricia a
ll, Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinL Prefix
p Patricia a
lr Patricia a
r #)
else (# Patricia a
forall a. Patricia a
Nil, Patricia a
t #)
else if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
p
then let !(# !Patricia a
rl, !Patricia a
rr #) = Patricia a -> (# Patricia a, Patricia a #)
go Patricia a
r
in (# Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinR Prefix
p Patricia a
l Patricia a
rl, Patricia a
rr #)
else (# Patricia a
t, Patricia a
forall a. Patricia a
Nil #)
Tip Prefix
k a
_
| Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
> Prefix
k -> (# Patricia a
t, Patricia a
forall a. Patricia a
Nil #)
| Bool
otherwise -> (# Patricia a
forall a. Patricia a
Nil, Patricia a
t #)
Patricia a
Nil -> (# Patricia a
forall a. Patricia a
Nil, Patricia a
forall a. Patricia a
Nil #)
data SplitLookup l x r = SplitLookup !(Patricia l) !(Maybe x) !(Patricia r)
deriving Int -> SplitLookup l x r -> ShowS
[SplitLookup l x r] -> ShowS
SplitLookup l x r -> String
(Int -> SplitLookup l x r -> ShowS)
-> (SplitLookup l x r -> String)
-> ([SplitLookup l x r] -> ShowS)
-> Show (SplitLookup l x r)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall l x r.
(Show l, Show x, Show r) =>
Int -> SplitLookup l x r -> ShowS
forall l x r.
(Show l, Show x, Show r) =>
[SplitLookup l x r] -> ShowS
forall l x r.
(Show l, Show x, Show r) =>
SplitLookup l x r -> String
$cshowsPrec :: forall l x r.
(Show l, Show x, Show r) =>
Int -> SplitLookup l x r -> ShowS
showsPrec :: Int -> SplitLookup l x r -> ShowS
$cshow :: forall l x r.
(Show l, Show x, Show r) =>
SplitLookup l x r -> String
show :: SplitLookup l x r -> String
$cshowList :: forall l x r.
(Show l, Show x, Show r) =>
[SplitLookup l x r] -> ShowS
showList :: [SplitLookup l x r] -> ShowS
Show
splitLookup :: Word -> Patricia a -> SplitLookup a a a
splitLookup :: forall a. Prefix -> Patricia a -> SplitLookup a a a
splitLookup !Prefix
w = \Patricia a
t ->
case Patricia a -> (# Patricia a, Maybe a, Patricia a #)
go Patricia a
t of
(# !Patricia a
l, !Maybe a
mx, !Patricia a
r #) -> Patricia a -> Maybe a -> Patricia a -> SplitLookup a a a
forall l x r.
Patricia l -> Maybe x -> Patricia r -> SplitLookup l x r
SplitLookup Patricia a
l Maybe a
mx Patricia a
r
where
go :: Patricia a -> (# Patricia a, Maybe a, Patricia a #)
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r ->
if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
< Prefix
p
then if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
>= Prefix -> Prefix
lower Prefix
p
then let !(# !Patricia a
ll, !Maybe a
mx, !Patricia a
lr #) = Patricia a -> (# Patricia a, Maybe a, Patricia a #)
go Patricia a
l
in (# Patricia a
ll, Maybe a
mx, Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinL Prefix
p Patricia a
lr Patricia a
r #)
else (# Patricia a
forall a. Patricia a
Nil, Maybe a
forall a. Maybe a
Nothing, Patricia a
t #)
else if Prefix
w Prefix -> Prefix -> Bool
forall a. Ord a => a -> a -> Bool
<= Prefix -> Prefix
upper Prefix
p
then let !(# !Patricia a
rl, !Maybe a
mx, !Patricia a
rr #) = Patricia a -> (# Patricia a, Maybe a, Patricia a #)
go Patricia a
r
in (# Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinR Prefix
p Patricia a
l Patricia a
rl, Maybe a
mx, Patricia a
rr #)
else (# Patricia a
t, Maybe a
forall a. Maybe a
Nothing, Patricia a
forall a. Patricia a
Nil #)
Tip Prefix
k a
a ->
case Prefix
w Prefix -> Prefix -> Ordering
forall a. Ord a => a -> a -> Ordering
`Prelude.compare` Prefix
k of
Ordering
EQ -> (# Patricia a
forall a. Patricia a
Nil, a -> Maybe a
forall a. a -> Maybe a
Just a
a , Patricia a
forall a. Patricia a
Nil #)
Ordering
GT -> (# Patricia a
t , Maybe a
forall a. Maybe a
Nothing, Patricia a
forall a. Patricia a
Nil #)
Ordering
LT -> (# Patricia a
forall a. Patricia a
Nil, Maybe a
forall a. Maybe a
Nothing, Patricia a
t #)
Patricia a
Nil -> (# Patricia a
forall a. Patricia a
Nil, Maybe a
forall a. Maybe a
Nothing, Patricia a
forall a. Patricia a
Nil #)
filter :: (a -> Bool) -> Patricia a -> Patricia a
filter :: forall a. (a -> Bool) -> Patricia a -> Patricia a
filter a -> Bool
f = Patricia a -> Patricia a
go
where
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebin Prefix
p (Patricia a -> Patricia a
go Patricia a
l) (Patricia a -> Patricia a
go Patricia a
r)
Tip Prefix
_ a
a
| a -> Bool
f a
a -> Patricia a
t
| Bool
otherwise -> Patricia a
forall a. Patricia a
Nil
Patricia a
Nil -> Patricia a
forall a. Patricia a
Nil
filterWithKey :: (Word -> a -> Bool) -> Patricia a -> Patricia a
filterWithKey :: forall a. (Prefix -> a -> Bool) -> Patricia a -> Patricia a
filterWithKey Prefix -> a -> Bool
f = Patricia a -> Patricia a
go
where
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebin Prefix
p (Patricia a -> Patricia a
go Patricia a
l) (Patricia a -> Patricia a
go Patricia a
r)
Tip Prefix
k a
a
| Prefix -> a -> Bool
f Prefix
k a
a -> Patricia a
t
| Bool
otherwise -> Patricia a
forall a. Patricia a
Nil
Patricia a
Nil -> Patricia a
forall a. Patricia a
Nil
mapMaybe :: (a -> Maybe b) -> Patricia a -> Patricia b
mapMaybe :: forall a b. (a -> Maybe b) -> Patricia a -> Patricia b
mapMaybe a -> Maybe b
f = Patricia a -> Patricia b
go
where
go :: Patricia a -> Patricia b
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r -> Prefix -> Patricia b -> Patricia b -> Patricia b
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebin Prefix
p (Patricia a -> Patricia b
go Patricia a
l) (Patricia a -> Patricia b
go Patricia a
r)
Tip Prefix
k a
a ->
case a -> Maybe b
f a
a of
Just b
b -> Prefix -> b -> Patricia b
forall a. Prefix -> a -> Patricia a
Tip Prefix
k b
b
Maybe b
Nothing -> Patricia b
forall a. Patricia a
Nil
Patricia a
Nil -> Patricia b
forall a. Patricia a
Nil
mapMaybeWithKey :: (Word -> a -> Maybe b) -> Patricia a -> Patricia b
mapMaybeWithKey :: forall a b. (Prefix -> a -> Maybe b) -> Patricia a -> Patricia b
mapMaybeWithKey Prefix -> a -> Maybe b
f = Patricia a -> Patricia b
go
where
go :: Patricia a -> Patricia b
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r -> Prefix -> Patricia b -> Patricia b -> Patricia b
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebin Prefix
p (Patricia a -> Patricia b
go Patricia a
l) (Patricia a -> Patricia b
go Patricia a
r)
Tip Prefix
k a
a ->
case Prefix -> a -> Maybe b
f Prefix
k a
a of
Just b
b -> Prefix -> b -> Patricia b
forall a. Prefix -> a -> Patricia a
Tip Prefix
k b
b
Maybe b
Nothing -> Patricia b
forall a. Patricia a
Nil
Patricia a
Nil -> Patricia b
forall a. Patricia a
Nil
partition :: (a -> Bool) -> Patricia a -> Split a a
partition :: forall a. (a -> Bool) -> Patricia a -> Split a a
partition a -> Bool
f = \Patricia a
t ->
case Patricia a -> (# Patricia a, Patricia a #)
go Patricia a
t of
(# !Patricia a
l, !Patricia a
r #) -> Patricia a -> Patricia a -> Split a a
forall l r. Patricia l -> Patricia r -> Split l r
Split Patricia a
l Patricia a
r
where
go :: Patricia a -> (# Patricia a, Patricia a #)
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r ->
let !(# !Patricia a
ll, !Patricia a
lr #) = Patricia a -> (# Patricia a, Patricia a #)
go Patricia a
l
!(# !Patricia a
rl, !Patricia a
rr #) = Patricia a -> (# Patricia a, Patricia a #)
go Patricia a
r
in (# Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebin Prefix
p Patricia a
ll Patricia a
rl, Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebin Prefix
p Patricia a
lr Patricia a
rr #)
Tip Prefix
_ a
a
| a -> Bool
f a
a -> (# Patricia a
t, Patricia a
forall a. Patricia a
Nil #)
| Bool
otherwise -> (# Patricia a
forall a. Patricia a
Nil, Patricia a
t #)
Patricia a
Nil -> (# Patricia a
forall a. Patricia a
Nil, Patricia a
forall a. Patricia a
Nil #)
partitionWithKey :: (Word -> a -> Bool) -> Patricia a -> Split a a
partitionWithKey :: forall a. (Prefix -> a -> Bool) -> Patricia a -> Split a a
partitionWithKey Prefix -> a -> Bool
f = \Patricia a
t ->
case Patricia a -> (# Patricia a, Patricia a #)
go Patricia a
t of
(# !Patricia a
l, !Patricia a
r #) -> Patricia a -> Patricia a -> Split a a
forall l r. Patricia l -> Patricia r -> Split l r
Split Patricia a
l Patricia a
r
where
go :: Patricia a -> (# Patricia a, Patricia a #)
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r ->
let !(# !Patricia a
ll, !Patricia a
lr #) = Patricia a -> (# Patricia a, Patricia a #)
go Patricia a
l
!(# !Patricia a
rl, !Patricia a
rr #) = Patricia a -> (# Patricia a, Patricia a #)
go Patricia a
r
in (# Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebin Prefix
p Patricia a
ll Patricia a
rl, Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebin Prefix
p Patricia a
lr Patricia a
rr #)
Tip Prefix
k a
a
| Prefix -> a -> Bool
f Prefix
k a
a -> (# Patricia a
t, Patricia a
forall a. Patricia a
Nil #)
| Bool
otherwise -> (# Patricia a
forall a. Patricia a
Nil, Patricia a
t #)
Patricia a
Nil -> (# Patricia a
forall a. Patricia a
Nil, Patricia a
forall a. Patricia a
Nil #)
mapEither :: (a -> Either b c) -> Patricia a -> Split b c
mapEither :: forall a b c. (a -> Either b c) -> Patricia a -> Split b c
mapEither a -> Either b c
f = \Patricia a
t ->
case Patricia a -> (# Patricia b, Patricia c #)
go Patricia a
t of
(# !Patricia b
l, !Patricia c
r #) -> Patricia b -> Patricia c -> Split b c
forall l r. Patricia l -> Patricia r -> Split l r
Split Patricia b
l Patricia c
r
where
go :: Patricia a -> (# Patricia b, Patricia c #)
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r ->
let !(# !Patricia b
ll, !Patricia c
lr #) = Patricia a -> (# Patricia b, Patricia c #)
go Patricia a
l
!(# !Patricia b
rl, !Patricia c
rr #) = Patricia a -> (# Patricia b, Patricia c #)
go Patricia a
r
in (# Prefix -> Patricia b -> Patricia b -> Patricia b
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebin Prefix
p Patricia b
ll Patricia b
rl, Prefix -> Patricia c -> Patricia c -> Patricia c
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebin Prefix
p Patricia c
lr Patricia c
rr #)
Tip Prefix
k a
a ->
case a -> Either b c
f a
a of
Left b
b -> (# Prefix -> b -> Patricia b
forall a. Prefix -> a -> Patricia a
Tip Prefix
k b
b, Patricia c
forall a. Patricia a
Nil #)
Right c
c -> (# Patricia b
forall a. Patricia a
Nil, Prefix -> c -> Patricia c
forall a. Prefix -> a -> Patricia a
Tip Prefix
k c
c #)
Patricia a
Nil -> (# Patricia b
forall a. Patricia a
Nil, Patricia c
forall a. Patricia a
Nil #)
mapEitherWithKey :: (Word -> a -> Either b c) -> Patricia a -> Split b c
mapEitherWithKey :: forall a b c.
(Prefix -> a -> Either b c) -> Patricia a -> Split b c
mapEitherWithKey Prefix -> a -> Either b c
f = \Patricia a
t ->
case Patricia a -> (# Patricia b, Patricia c #)
go Patricia a
t of
(# !Patricia b
l, !Patricia c
r #) -> Patricia b -> Patricia c -> Split b c
forall l r. Patricia l -> Patricia r -> Split l r
Split Patricia b
l Patricia c
r
where
go :: Patricia a -> (# Patricia b, Patricia c #)
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r ->
let !(# !Patricia b
ll, !Patricia c
lr #) = Patricia a -> (# Patricia b, Patricia c #)
go Patricia a
l
!(# !Patricia b
rl, !Patricia c
rr #) = Patricia a -> (# Patricia b, Patricia c #)
go Patricia a
r
in (# Prefix -> Patricia b -> Patricia b -> Patricia b
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebin Prefix
p Patricia b
ll Patricia b
rl, Prefix -> Patricia c -> Patricia c -> Patricia c
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebin Prefix
p Patricia c
lr Patricia c
rr #)
Tip Prefix
k a
a ->
case Prefix -> a -> Either b c
f Prefix
k a
a of
Left b
b -> (# Prefix -> b -> Patricia b
forall a. Prefix -> a -> Patricia a
Tip Prefix
k b
b, Patricia c
forall a. Patricia a
Nil #)
Right c
c -> (# Patricia b
forall a. Patricia a
Nil, Prefix -> c -> Patricia c
forall a. Prefix -> a -> Patricia a
Tip Prefix
k c
c #)
Patricia a
Nil -> (# Patricia b
forall a. Patricia a
Nil, Patricia c
forall a. Patricia a
Nil #)
moduleLoc :: String
moduleLoc :: String
moduleLoc = String
"Patricia.Word.Strict"
lookupMin :: Patricia a -> Maybe a
lookupMin :: forall a. Patricia a -> Maybe a
lookupMin Patricia a
Nil = Maybe a
forall a. Maybe a
Nothing
lookupMin Patricia a
t = let !(# a
a #) = Patricia a -> (# a #)
forall a. Patricia a -> (# a #)
unsafeLookupMin Patricia a
t
in a -> Maybe a
forall a. a -> Maybe a
Just a
a
unsafeLookupMin :: Patricia a -> (# a #)
unsafeLookupMin :: forall a. Patricia a -> (# a #)
unsafeLookupMin Patricia a
t =
case Patricia a
t of
Bin Prefix
_ Patricia a
l Patricia a
_ -> Patricia a -> (# a #)
forall a. Patricia a -> (# a #)
unsafeLookupMin Patricia a
l
Tip Prefix
_ a
a -> (# a
a #)
Patricia a
Nil -> MalformedTree -> (# a #)
forall a e. Exception e => e -> a
throw (MalformedTree -> (# a #)) -> MalformedTree -> (# a #)
forall a b. (a -> b) -> a -> b
$ String -> String -> MalformedTree
MalformedTree String
moduleLoc String
"lookupMin"
lookupMinWithKey :: Patricia a -> Maybe (Lookup a)
lookupMinWithKey :: forall a. Patricia a -> Maybe (Lookup a)
lookupMinWithKey Patricia a
Nil = Maybe (Lookup a)
forall a. Maybe a
Nothing
lookupMinWithKey Patricia a
t = Lookup a -> Maybe (Lookup a)
forall a. a -> Maybe a
Just (Lookup a -> Maybe (Lookup a)) -> Lookup a -> Maybe (Lookup a)
forall a b. (a -> b) -> a -> b
$! Patricia a -> Lookup a
forall a. Patricia a -> Lookup a
unsafeLookupMinWithKey Patricia a
t
unsafeLookupMinWithKey :: Patricia a -> Lookup a
unsafeLookupMinWithKey :: forall a. Patricia a -> Lookup a
unsafeLookupMinWithKey Patricia a
t =
case Patricia a
t of
Bin Prefix
_ Patricia a
l Patricia a
_ -> Patricia a -> Lookup a
forall a. Patricia a -> Lookup a
unsafeLookupMinWithKey Patricia a
l
Tip Prefix
k a
a -> Prefix -> a -> Lookup a
forall a. Prefix -> a -> Lookup a
Lookup Prefix
k a
a
Patricia a
Nil -> MalformedTree -> Lookup a
forall a e. Exception e => e -> a
throw (MalformedTree -> Lookup a) -> MalformedTree -> Lookup a
forall a b. (a -> b) -> a -> b
$ String -> String -> MalformedTree
MalformedTree String
moduleLoc String
"lookupMinWithKey"
lookupMax :: Patricia a -> Maybe a
lookupMax :: forall a. Patricia a -> Maybe a
lookupMax Patricia a
Nil = Maybe a
forall a. Maybe a
Nothing
lookupMax Patricia a
t = let !(# a
a #) = Patricia a -> (# a #)
forall a. Patricia a -> (# a #)
unsafeLookupMax Patricia a
t
in a -> Maybe a
forall a. a -> Maybe a
Just a
a
unsafeLookupMax :: Patricia a -> (# a #)
unsafeLookupMax :: forall a. Patricia a -> (# a #)
unsafeLookupMax Patricia a
t =
case Patricia a
t of
Bin Prefix
_ Patricia a
_ Patricia a
r -> Patricia a -> (# a #)
forall a. Patricia a -> (# a #)
unsafeLookupMax Patricia a
r
Tip Prefix
_ a
a -> (# a
a #)
Patricia a
Nil -> MalformedTree -> (# a #)
forall a e. Exception e => e -> a
throw (MalformedTree -> (# a #)) -> MalformedTree -> (# a #)
forall a b. (a -> b) -> a -> b
$ String -> String -> MalformedTree
MalformedTree String
moduleLoc String
"lookupMax"
lookupMaxWithKey :: Patricia a -> Maybe (Lookup a)
lookupMaxWithKey :: forall a. Patricia a -> Maybe (Lookup a)
lookupMaxWithKey Patricia a
Nil = Maybe (Lookup a)
forall a. Maybe a
Nothing
lookupMaxWithKey Patricia a
t = Lookup a -> Maybe (Lookup a)
forall a. a -> Maybe a
Just (Lookup a -> Maybe (Lookup a)) -> Lookup a -> Maybe (Lookup a)
forall a b. (a -> b) -> a -> b
$! Patricia a -> Lookup a
forall a. Patricia a -> Lookup a
unsafeLookupMaxWithKey Patricia a
t
unsafeLookupMaxWithKey :: Patricia a -> Lookup a
unsafeLookupMaxWithKey :: forall a. Patricia a -> Lookup a
unsafeLookupMaxWithKey Patricia a
t =
case Patricia a
t of
Bin Prefix
_ Patricia a
_ Patricia a
r -> Patricia a -> Lookup a
forall a. Patricia a -> Lookup a
unsafeLookupMaxWithKey Patricia a
r
Tip Prefix
k a
a -> Prefix -> a -> Lookup a
forall a. Prefix -> a -> Lookup a
Lookup Prefix
k a
a
Patricia a
Nil -> MalformedTree -> Lookup a
forall a e. Exception e => e -> a
throw (MalformedTree -> Lookup a) -> MalformedTree -> Lookup a
forall a b. (a -> b) -> a -> b
$ String -> String -> MalformedTree
MalformedTree String
moduleLoc String
"lookupMaxWithKey"
deleteMin :: Patricia a -> Patricia a
deleteMin :: forall a. Patricia a -> Patricia a
deleteMin = Patricia a -> Patricia a
forall a. Patricia a -> Patricia a
go
where
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinL Prefix
p (Patricia a -> Patricia a
go Patricia a
l) Patricia a
r
Patricia a
_ -> Patricia a
forall a. Patricia a
Nil
deleteMax :: Patricia a -> Patricia a
deleteMax :: forall a. Patricia a -> Patricia a
deleteMax = Patricia a -> Patricia a
forall a. Patricia a -> Patricia a
go
where
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinR Prefix
p Patricia a
l (Patricia a -> Patricia a
go Patricia a
r)
Patricia a
_ -> Patricia a
forall a. Patricia a
Nil
adjustMin :: (a -> a) -> Patricia a -> Patricia a
adjustMin :: forall a. (a -> a) -> Patricia a -> Patricia a
adjustMin a -> a
f = Patricia a -> Patricia a
go
where
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p (Patricia a -> Patricia a
go Patricia a
l) Patricia a
r
Tip Prefix
k a
a -> Prefix -> a -> Patricia a
forall a. Prefix -> a -> Patricia a
Tip Prefix
k (a -> a
f a
a)
Patricia a
Nil -> Patricia a
forall a. Patricia a
Nil
adjustMin' :: (a -> a) -> Patricia a -> Patricia a
adjustMin' :: forall a. (a -> a) -> Patricia a -> Patricia a
adjustMin' a -> a
f = Patricia a -> Patricia a
go
where
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p (Patricia a -> Patricia a
go Patricia a
l) Patricia a
r
Tip Prefix
k a
a -> Prefix -> a -> Patricia a
forall a. Prefix -> a -> Patricia a
Tip Prefix
k (a -> Patricia a) -> a -> Patricia a
forall a b. (a -> b) -> a -> b
$! a -> a
f a
a
Patricia a
Nil -> Patricia a
forall a. Patricia a
Nil
adjustMinWithKey :: (Word -> a -> a) -> Patricia a -> Patricia a
adjustMinWithKey :: forall a. (Prefix -> a -> a) -> Patricia a -> Patricia a
adjustMinWithKey Prefix -> a -> a
f = Patricia a -> Patricia a
go
where
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p (Patricia a -> Patricia a
go Patricia a
l) Patricia a
r
Tip Prefix
k a
a -> Prefix -> a -> Patricia a
forall a. Prefix -> a -> Patricia a
Tip Prefix
k (Prefix -> a -> a
f Prefix
k a
a)
Patricia a
Nil -> Patricia a
forall a. Patricia a
Nil
adjustMinWithKey' :: (Word -> a -> a) -> Patricia a -> Patricia a
adjustMinWithKey' :: forall a. (Prefix -> a -> a) -> Patricia a -> Patricia a
adjustMinWithKey' Prefix -> a -> a
f = Patricia a -> Patricia a
go
where
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p (Patricia a -> Patricia a
go Patricia a
l) Patricia a
r
Tip Prefix
k a
a -> Prefix -> a -> Patricia a
forall a. Prefix -> a -> Patricia a
Tip Prefix
k (a -> Patricia a) -> a -> Patricia a
forall a b. (a -> b) -> a -> b
$! Prefix -> a -> a
f Prefix
k a
a
Patricia a
Nil -> Patricia a
forall a. Patricia a
Nil
adjustMax :: (a -> a) -> Patricia a -> Patricia a
adjustMax :: forall a. (a -> a) -> Patricia a -> Patricia a
adjustMax a -> a
f = Patricia a -> Patricia a
go
where
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p Patricia a
l (Patricia a -> Patricia a
go Patricia a
r)
Tip Prefix
k a
a -> Prefix -> a -> Patricia a
forall a. Prefix -> a -> Patricia a
Tip Prefix
k (a -> a
f a
a)
Patricia a
Nil -> Patricia a
forall a. Patricia a
Nil
adjustMax' :: (a -> a) -> Patricia a -> Patricia a
adjustMax' :: forall a. (a -> a) -> Patricia a -> Patricia a
adjustMax' a -> a
f = Patricia a -> Patricia a
go
where
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p Patricia a
l (Patricia a -> Patricia a
go Patricia a
r)
Tip Prefix
k a
a -> Prefix -> a -> Patricia a
forall a. Prefix -> a -> Patricia a
Tip Prefix
k (a -> Patricia a) -> a -> Patricia a
forall a b. (a -> b) -> a -> b
$! a -> a
f a
a
Patricia a
Nil -> Patricia a
forall a. Patricia a
Nil
adjustMaxWithKey :: (Word -> a -> a) -> Patricia a -> Patricia a
adjustMaxWithKey :: forall a. (Prefix -> a -> a) -> Patricia a -> Patricia a
adjustMaxWithKey Prefix -> a -> a
f = Patricia a -> Patricia a
go
where
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p Patricia a
l (Patricia a -> Patricia a
go Patricia a
r)
Tip Prefix
k a
a -> Prefix -> a -> Patricia a
forall a. Prefix -> a -> Patricia a
Tip Prefix
k (Prefix -> a -> a
f Prefix
k a
a)
Patricia a
Nil -> Patricia a
forall a. Patricia a
Nil
adjustMaxWithKey' :: (Word -> a -> a) -> Patricia a -> Patricia a
adjustMaxWithKey' :: forall a. (Prefix -> a -> a) -> Patricia a -> Patricia a
adjustMaxWithKey' Prefix -> a -> a
f = Patricia a -> Patricia a
go
where
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
Bin Prefix
p Patricia a
l (Patricia a -> Patricia a
go Patricia a
r)
Tip Prefix
k a
a -> Prefix -> a -> Patricia a
forall a. Prefix -> a -> Patricia a
Tip Prefix
k (a -> Patricia a) -> a -> Patricia a
forall a b. (a -> b) -> a -> b
$! Prefix -> a -> a
f Prefix
k a
a
Patricia a
Nil -> Patricia a
forall a. Patricia a
Nil
updateMin :: (a -> Maybe a) -> Patricia a -> Patricia a
updateMin :: forall a. (a -> Maybe a) -> Patricia a -> Patricia a
updateMin a -> Maybe a
f = Patricia a -> Patricia a
go
where
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinL Prefix
p (Patricia a -> Patricia a
go Patricia a
l) Patricia a
r
Tip Prefix
k a
a -> Prefix -> Maybe a -> Patricia a
forall a. Prefix -> Maybe a -> Patricia a
retip Prefix
k (a -> Maybe a
f a
a)
Patricia a
Nil -> Patricia a
forall a. Patricia a
Nil
updateMinWithKey :: (Word -> a -> Maybe a) -> Patricia a -> Patricia a
updateMinWithKey :: forall a. (Prefix -> a -> Maybe a) -> Patricia a -> Patricia a
updateMinWithKey Prefix -> a -> Maybe a
f = Patricia a -> Patricia a
go
where
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinL Prefix
p (Patricia a -> Patricia a
go Patricia a
l) Patricia a
r
Tip Prefix
k a
a -> Prefix -> Maybe a -> Patricia a
forall a. Prefix -> Maybe a -> Patricia a
retip Prefix
k (Prefix -> a -> Maybe a
f Prefix
k a
a)
Patricia a
Nil -> Patricia a
forall a. Patricia a
Nil
updateMax :: (a -> Maybe a) -> Patricia a -> Patricia a
updateMax :: forall a. (a -> Maybe a) -> Patricia a -> Patricia a
updateMax a -> Maybe a
f = Patricia a -> Patricia a
go
where
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinR Prefix
p Patricia a
l (Patricia a -> Patricia a
go Patricia a
r)
Tip Prefix
k a
a -> Prefix -> Maybe a -> Patricia a
forall a. Prefix -> Maybe a -> Patricia a
retip Prefix
k (a -> Maybe a
f a
a)
Patricia a
Nil -> Patricia a
forall a. Patricia a
Nil
updateMaxWithKey :: (Word -> a -> Maybe a) -> Patricia a -> Patricia a
updateMaxWithKey :: forall a. (Prefix -> a -> Maybe a) -> Patricia a -> Patricia a
updateMaxWithKey Prefix -> a -> Maybe a
f = Patricia a -> Patricia a
go
where
go :: Patricia a -> Patricia a
go Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r -> Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinR Prefix
p Patricia a
l (Patricia a -> Patricia a
go Patricia a
r)
Tip Prefix
k a
a -> Prefix -> Maybe a -> Patricia a
forall a. Prefix -> Maybe a -> Patricia a
retip Prefix
k (Prefix -> a -> Maybe a
f Prefix
k a
a)
Patricia a
Nil -> Patricia a
forall a. Patricia a
Nil
minView :: Patricia a -> Maybe (ViewL a)
minView :: forall a. Patricia a -> Maybe (ViewL a)
minView Patricia a
Nil = Maybe (ViewL a)
forall a. Maybe a
Nothing
minView Patricia a
t = ViewL a -> Maybe (ViewL a)
forall a. a -> Maybe a
Just (ViewL a -> Maybe (ViewL a)) -> ViewL a -> Maybe (ViewL a)
forall a b. (a -> b) -> a -> b
$! Patricia a -> ViewL a
forall a. Patricia a -> ViewL a
unsafeMinView Patricia a
t
data ViewL a = ViewL {-# UNPACK #-} !(Lookup a) !(Patricia a)
deriving Int -> ViewL a -> ShowS
[ViewL a] -> ShowS
ViewL a -> String
(Int -> ViewL a -> ShowS)
-> (ViewL a -> String) -> ([ViewL a] -> ShowS) -> Show (ViewL a)
forall a. Show a => Int -> ViewL a -> ShowS
forall a. Show a => [ViewL a] -> ShowS
forall a. Show a => ViewL a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: forall a. Show a => Int -> ViewL a -> ShowS
showsPrec :: Int -> ViewL a -> ShowS
$cshow :: forall a. Show a => ViewL a -> String
show :: ViewL a -> String
$cshowList :: forall a. Show a => [ViewL a] -> ShowS
showList :: [ViewL a] -> ShowS
Show
unsafeMinView :: Patricia a -> ViewL a
unsafeMinView :: forall a. Patricia a -> ViewL a
unsafeMinView Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r ->
let !(ViewL Lookup a
a Patricia a
l0) = Patricia a -> ViewL a
forall a. Patricia a -> ViewL a
unsafeMinView Patricia a
l
in Lookup a -> Patricia a -> ViewL a
forall a. Lookup a -> Patricia a -> ViewL a
ViewL Lookup a
a (Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinL Prefix
p Patricia a
l0 Patricia a
r)
Tip Prefix
k a
a -> Lookup a -> Patricia a -> ViewL a
forall a. Lookup a -> Patricia a -> ViewL a
ViewL (Prefix -> a -> Lookup a
forall a. Prefix -> a -> Lookup a
Lookup Prefix
k a
a) Patricia a
forall a. Patricia a
Nil
Patricia a
Nil -> MalformedTree -> ViewL a
forall a e. Exception e => e -> a
throw (MalformedTree -> ViewL a) -> MalformedTree -> ViewL a
forall a b. (a -> b) -> a -> b
$ String -> String -> MalformedTree
MalformedTree String
moduleLoc String
"minView"
maxView :: Patricia a -> Maybe (ViewR a)
maxView :: forall a. Patricia a -> Maybe (ViewR a)
maxView Patricia a
Nil = Maybe (ViewR a)
forall a. Maybe a
Nothing
maxView Patricia a
t = ViewR a -> Maybe (ViewR a)
forall a. a -> Maybe a
Just (ViewR a -> Maybe (ViewR a)) -> ViewR a -> Maybe (ViewR a)
forall a b. (a -> b) -> a -> b
$! Patricia a -> ViewR a
forall a. Patricia a -> ViewR a
unsafeMaxView Patricia a
t
data ViewR a = ViewR !(Patricia a) {-# UNPACK #-} !(Lookup a)
deriving Int -> ViewR a -> ShowS
[ViewR a] -> ShowS
ViewR a -> String
(Int -> ViewR a -> ShowS)
-> (ViewR a -> String) -> ([ViewR a] -> ShowS) -> Show (ViewR a)
forall a. Show a => Int -> ViewR a -> ShowS
forall a. Show a => [ViewR a] -> ShowS
forall a. Show a => ViewR a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: forall a. Show a => Int -> ViewR a -> ShowS
showsPrec :: Int -> ViewR a -> ShowS
$cshow :: forall a. Show a => ViewR a -> String
show :: ViewR a -> String
$cshowList :: forall a. Show a => [ViewR a] -> ShowS
showList :: [ViewR a] -> ShowS
Show
unsafeMaxView :: Patricia a -> ViewR a
unsafeMaxView :: forall a. Patricia a -> ViewR a
unsafeMaxView Patricia a
t =
case Patricia a
t of
Bin Prefix
p Patricia a
l Patricia a
r ->
let !(ViewR Patricia a
r0 Lookup a
a) = Patricia a -> ViewR a
forall a. Patricia a -> ViewR a
unsafeMaxView Patricia a
r
in Patricia a -> Lookup a -> ViewR a
forall a. Patricia a -> Lookup a -> ViewR a
ViewR (Prefix -> Patricia a -> Patricia a -> Patricia a
forall a. Prefix -> Patricia a -> Patricia a -> Patricia a
rebinR Prefix
p Patricia a
l Patricia a
r0) Lookup a
a
Tip Prefix
k a
a -> Patricia a -> Lookup a -> ViewR a
forall a. Patricia a -> Lookup a -> ViewR a
ViewR Patricia a
forall a. Patricia a
Nil (Prefix -> a -> Lookup a
forall a. Prefix -> a -> Lookup a
Lookup Prefix
k a
a)
Patricia a
Nil -> MalformedTree -> ViewR a
forall a e. Exception e => e -> a
throw (MalformedTree -> ViewR a) -> MalformedTree -> ViewR a
forall a b. (a -> b) -> a -> b
$ String -> String -> MalformedTree
MalformedTree String
moduleLoc String
"maxView"