{-# 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



-- | Convenience synonym.
type StrictPatricia = Patricia

-- | Spine-strict PATRICIA tree.
data Patricia a = Bin
                    {-# UNPACK #-} !Prefix
                    !(Patricia a)          -- ^ Masked bit is @0@.
                    !(Patricia a)          -- ^ Masked bit is @1@.

                | Tip
                    {-# UNPACK #-} !Key
                    a

                | Nil -- ^ Invariant: only allowed as the root of the tree.
                  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


-- | Uses 'Data.Patricia.Word.Strict.map'.
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 #-}
-- | Knowing that the prefices of two non-'Nil' trees disagree, construct a 'Bin'.
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 #-}
-- | Knowing that the prefices of two trees disagree, construct a 'Bin'.
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 #-}
-- | Reconstruct a 'Bin' knowing that either of the sides may now be a 'Nil'.
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 #-}
-- | Reconstruct a 'Bin' knowing that the left side may now be a 'Nil'.
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 #-}
-- | Reconstruct a 'Bin' knowing that the right side may now be a 'Nil'.
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 #-}
-- | Reconstruct a 'Tip' knowing that the value may not be there anymore.
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



-- | \(\mathcal{O}(1)\).
--   Check if the tree is empty.
null :: Patricia a -> Bool
null :: forall a. Patricia a -> Bool
null Patricia a
Nil = Bool
True
null Patricia a
_   = Bool
False

-- | \(\mathcal{O}(n)\).
--   Calculate the number of elements stored in the tree.
--   The returned number is guaranteed to be non-negative.
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



-- | \(\mathcal{O}(n)\).
--   Apply a function to every value in the tree.
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

-- | \(\mathcal{O}(n)\).
--   Apply a function to every value in the tree.
--
--   New values are evaluated to WHNF.
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

-- | \(\mathcal{O}(n)\).
--   Apply a function to every value in the tree.
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

-- | \(\mathcal{O}(n)\).
--   Apply a function to every value in the tree.
--
--   New values are evaluated to WHNF.
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



-- | \(\mathcal{O}(n_R)\).
--   Fold the tree left-to-right.
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

-- | \(\mathcal{O}(n_R)\).
--   Fold the tree left-to-right.
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



-- | \(\mathcal{O}(n)\).
--   Fold the tree left-to-right with a strict accumulator.
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

-- | \(\mathcal{O}(n)\).
--   Fold the tree left-to-right with a strict accumulator.
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



-- | \(\mathcal{O}(n_L)\).
--   Fold the tree right-to-left.
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

-- | \(\mathcal{O}(n_L)\).
--   Fold the tree right-to-left.
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

-- | \(\mathcal{O}(n)\).
--   Fold the tree right-to-left with a strict accumulator.
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

-- | \(\mathcal{O}(n)\).
--   Fold the tree right-to-left with a strict accumulator.
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



-- | \(\mathcal{O}(n_M)\).
--   Map each element in the tree to a monoid and combine the results.
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

-- | \(\mathcal{O}(n_M)\).
--   Map each element in the tree to a monoid and combine the results.
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



-- | \(\mathcal{O}(n)\).
--   Map each element in the tree to an action, evaluate these actions
--   left-to-right and collect the results.
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

-- | \(\mathcal{O}(n)\).
--   Map each element in the tree to an action, evaluate these actions
--   left-to-right and collect the results.
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 #)



-- | \(\mathcal{O}(n_A + n_B)\).
--   Unbiased union of two trees.
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



-- | \(\mathcal{O}(n_A + n_B)\).
--   Left-biased union of two trees.
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

-- | \(\mathcal{O}(n_A + n_B)\).
--   Union of two trees with a combining function.
--
--   New values are evaluated to WHNF.
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

-- | \(\mathcal{O}(n_A + n_B)\).
--   Union of two trees with a combining function.
--
--   New values are evaluated to WHNF.
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



-- | \(\mathcal{O}(n_A + n_B)\).
--   Difference of two trees.
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

-- | \(\mathcal{O}(n_A + n_B)\).
--   Difference of two trees with a combining function.
--
--   The 'Maybe' is evaluated to WHNF.
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

-- | \(\mathcal{O}(n_A + n_B)\).
--   Difference of two trees with a combining function.
--
--   The 'Maybe' is evaluated to WHNF.
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



-- | \(\mathcal{O}(n_A + n_B)\).
--   Compare two trees with respect to set inclusion,
--   using the given equality function for intersecting keys.
--   If any intersecting keys hold unequal values, the trees are 'Incomparable'.
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



-- | \(\mathcal{O}(n_A + n_B)\).
--   Determine whether two trees' key sets are disjoint.
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



-- | \(\mathcal{O}(n_A + n_B)\).
--   Unbiased intersection of two trees.
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



-- | \(\mathcal{O}(n_A + n_B)\).
--   Left-biased intersection of two trees.
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

-- | \(\mathcal{O}(n_A + n_B)\).
--   Intersection of two trees with a combining function.
--
--   New values are evaluated to WHNF.
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

-- | \(\mathcal{O}(n_A + n_B)\).
--   Intersection of two trees with a combining function.
--
--   New values are evaluated to WHNF.
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 #-}
-- | \(\mathcal{O}(n_A + n_B)\).
--   General merge of two trees.
--
--   Collision and single value functions __must__ return either
--   'Tip' with the respective key, or 'Nil'.
--
--   Subtree argument functions may return any tree, however the shape of said tree
--   __must__ be compatible with the prefix passed to the function.
--
--   Resulting 'Patricia' trees in argument functions are evaluated to WHNF.
--
--   This functions inlines when all argument functions are provided.
merge
  :: (Key -> a -> b -> Patricia c)                      -- ^ Single value collision
  -> (Key -> a -> Patricia c)                           -- ^ Single left value
  -> (Prefix -> Patricia a -> Patricia a -> Patricia c) -- ^ Left subtree
  -> (Key -> b -> Patricia c)                           -- ^ Single right value
  -> (Prefix -> Patricia b -> Patricia b -> Patricia c) -- ^ Right subtree
  -> 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



-- | \(\mathcal{O}(\min(n,W))\).
--   Look up the value at a key in the tree.
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

-- | \(\mathcal{O}(\min(n,W))\).
--   Look up the value at a key in the tree, falling back to the given default value
--   if it does not exist.
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

-- | \(\mathcal{O}(\min(n,W))\).
--   Check whether the value exists at a key in the tree.
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

-- 'lookup' that doesn't allocate a 'Maybe'.
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



-- | \(\mathcal{O}(\min(n,W))\).
--   Look up the value at a key in the tree.
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

-- | \(\mathcal{O}(\min(n,W))\).
--   Look up the value at a key in the tree, falling back to the default value
--   if it does not exist.
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

-- | \(\mathcal{O}(\min(n,W))\).
--   Check whether the value exists at a key in the tree.
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



-- | \(\mathcal{O}(\min(n,W))\).
--   Insert a new value in the tree at the given key.
--   If a value already exists at that key, it is replaced.
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



-- | \(\mathcal{O}(\min(n,W))\).
--   Insert a new value in the tree at the given key.
--   If a value already exists at that key, the function is used instead.
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

-- | \(\mathcal{O}(\min(n,W))\).
--   Insert a new value in the tree at the given key.
--   If a value already exists at that key, the function is used instead.
--
--   New value is evaluted to WHNF.
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



-- | \(\mathcal{O}(\min(n,W))\).
--   Apply a function to a value in the tree at the given key.
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

-- | \(\mathcal{O}(\min(n,W))\).
--   Apply a function to a value in the tree at the given key.
--
--   New value is evaluated to WHNF.
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



-- | \(\mathcal{O}(\min(n,W))\).
--   Delete a value in the tree at the given key.
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

-- | \(\mathcal{O}(\min(n,W))\).
--   Update or delete a value in the tree at the given key.
--
--   The 'Maybe' is evaluated to WHNF.
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



-- | \(\mathcal{O}(\min(n,W))\).
--   Insert, update or delete a value in the tree at the given key.
--
--   The resulting 'Maybe' is evaluated to WHNF.
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



-- | \(\mathcal{O}(\min(n,W))\).
--   Look up a value at a largest key smaller than or equal to the given key.
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

-- | \(\mathcal{O}(\min(n,W))\).
--   Look up a value at a smallest key greater than or equal to the given key.
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



-- | \(\mathcal{O}(\min(n,W) + n_L)\).
--   Apply a function to every value for which the key is smaller than
--   or equal to the given one.
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

-- | \(\mathcal{O}(\min(n,W) + n_L)\).
--   Apply a function to every value for which the key is smaller than
--   or equal to the given one.
--
--   New value is evaluated to WHNF.
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

-- | \(\mathcal{O}(\min(n,W) + n_L)\).
--   Apply a function to every value for which the key is smaller than
--   or equal to the given one.
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

-- | \(\mathcal{O}(\min(n,W) + n_L)\).
--   Apply a function to every value for which the key is smaller than
--   or equal to the given one.
--
--   New value is evaluated to WHNF.
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


-- | \(\mathcal{O}(\min(n,W))\).
--   Delete values for which keys are smaller than or equal to the given one.
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


-- | \(\mathcal{O}(\min(n,W) + n_L)\).
--   Update every value for which the key is smaller than or equal to the given one.
--
--   The 'Maybe' is evaluated to WHNF.
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

-- | \(\mathcal{O}(\min(n,W) + n_L)\).
--   Update every value for which the key is smaller than or equal to the given one.
--
--   The 'Maybe' is evaluated to WHNF.
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


-- | \(\mathcal{O}(\min(n,W))\).
--   Take values for which keys are smaller than or equal to the given one.
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



-- | \(\mathcal{O}(\min(n,W) + n_R)\).
--   Apply a function to every value for which the key is greater than
--   or equal to the given one.
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

-- | \(\mathcal{O}(\min(n,W) + n_R)\).
--   Apply a function to every value for which the key is greater than
--   or equal to the given one.
--
--   New value is evaluated to WHNF.
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

-- | \(\mathcal{O}(\min(n,W) + n_R)\).
--   Apply a function to every value for which the key is greater than
--   or equal to the given one.
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

-- | \(\mathcal{O}(\min(n,W) + n_R)\).
--   Apply a function to every value for which the key is greater than
--   or equal to the given one.
--
--   New value is evaluated to WHNF.
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


-- | \(\mathcal{O}(\min(n,W))\).
--   Delete values for which keys are greater than or equal to the given one.
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


-- | \(\mathcal{O}(\min(n,W) + n_R)\).
--   Update every value for which the key is greater than or equal to the given one.
--
--   The 'Maybe' is evaluated to WHNF.
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

-- | \(\mathcal{O}(\min(n,W) + n_R)\).
--   Update every value for which the key is greater than or equal to the given one.
--
--   The 'Maybe' is evaluated to WHNF.
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


-- | \(\mathcal{O}(\min(n,W))\).
--   Take values for which keys are greater than or equal to the given one.
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



-- | \(\mathcal{O}(\min(n,W) + n_I)\).
--   Apply a function to every value for which the key is in the given range.
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

-- | \(\mathcal{O}(\min(n,W) + n_I)\).
--   Apply a function to every value for which the key is in the given range.
--
--   \(k_R\) __must__ be greater than \(k_L\).
unsafeAdjustRange
  :: (a -> a)
  -> Word     -- ^ \(k_L\)
  -> Word     -- ^ \(k_R\)
  -> 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

-- | \(\mathcal{O}(\min(n,W) + n_I)\).
--   Apply a function to every value for which the key is in the given range.
--
--   New value is evaluated to WHNF.
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

-- | \(\mathcal{O}(\min(n,W) + n_I)\).
--   Apply a function to every value for which the key is in the given range.
--
--   New value is evaluated to WHNF.
--
--   \(k_R\) __must__ be greater than \(k_L\).
unsafeAdjustRange'
  :: (a -> a)
  -> Word     -- ^ \(k_L\)
  -> Word     -- ^ \(k_R\)
  -> 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

-- | \(\mathcal{O}(\min(n,W) + n_I)\).
--   Apply a function to every value for which the key is in the given range.
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

-- | \(\mathcal{O}(\min(n,W) + n_I)\).
--   Apply a function to every value for which the key is in the given range.
--
--   \(k_R\) __must__ be greater than \(k_L\).
unsafeAdjustRangeWithKey
  :: (Word -> a -> a)
  -> Word             -- ^ \(k_L\)
  -> Word             -- ^ \(k_R\)
  -> 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

-- | \(\mathcal{O}(\min(n,W) + n_I)\).
--   Apply a function to every value for which the key is in the given range.
--
--   New value is evaluated to WHNF.
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

-- | \(\mathcal{O}(\min(n,W) + n_I)\).
--   Apply a function to every value for which the key is in the given range.
--
--   New value is evaluated to WHNF.
--
--   \(k_R\) __must__ be greater than \(k_L\).
unsafeAdjustRangeWithKey'
  :: (Word -> a -> a)
  -> Word             -- ^ \(k_L\)
  -> Word             -- ^ \(k_R\)
  -> 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


-- | \(\mathcal{O}(\min(n,W))\).
--   Delete values for which keys are in the given range.
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

-- | \(\mathcal{O}(\min(n,W))\).
--   Delete values for which keys are in the given range.
--
--   \(k_R\) __must__ be greater than \(k_L\).
unsafeDeleteRange
  :: Word         -- ^ \(k_L\)
  -> Word         -- ^ \(k_R\)
  -> 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


-- | \(\mathcal{O}(\min(n,W) + n_I)\).
--   Update every value for which the key is in the given range.
--
--   The 'Maybe' is evaluated to WHNF.
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

-- | \(\mathcal{O}(\min(n,W) + n_I)\).
--   Update every value for which the key is in the given range.
--
--   The 'Maybe' is evaluated to WHNF.
--
--   \(k_R\) __must__ be greater than \(k_L\).
unsafeUpdateRange
  :: (a -> Maybe a)
  -> Word           -- ^ \(k_L\)
  -> Word           -- ^ \(k_R\)
  -> 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

-- | \(\mathcal{O}(\min(n,W) + n_I)\).
--   Update every value for which the key is in the given range.
--
--   The 'Maybe' is evaluated to WHNF.
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

-- | \(\mathcal{O}(\min(n,W) + n_I)\).
--   Update every value for which the key is in the given range.
--
--   The 'Maybe' is evaluated to WHNF.
--
--   \(k_R\) __must__ be greater than \(k_L\).
unsafeUpdateRangeWithKey
  :: (Word -> a -> Maybe a)
  -> Word                   -- ^ \(k_L\)
  -> Word                   -- ^ \(k_R\)
  -> 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



-- | \(\mathcal{O}(\min(n,W))\).
--   Take values for which keys are in the given range.
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

-- | \(\mathcal{O}(\min(n,W))\).
--   Take values for which keys are in the given range.
--
--   \(k_R\) __must__ be greater than \(k_L\).
unsafeTakeRange
  :: Word       -- ^ \(k_L\)
  -> Word       -- ^ \(k_R\)
  -> 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



-- | Result of a tree split.
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

-- | \(\mathcal{O}(\min(n,W))\).
--   Split the tree into two, such that
--   values with keys smaller than or equal to the given one are on the left,
--   and values with keys greater than the given one are on the right.
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 #)

-- | \(\mathcal{O}(\min(n,W))\).
--   Split the tree into two, such that
--   values with keys smaller than the given one are on the left,
--   and values with keys greater than or equal to the given one are on the right.
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 #)



-- | Result of a tree split with a lookup.
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

-- | \(\mathcal{O}(\min(n,W))\).
--   Split the tree into two, such that
--   values with keys smaller than the given one are on the left,
--   values with keys greater than the given one are on the right,
--   and the value at the given key is returned separately.
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 #)



-- | \(\mathcal{O}(n)\).
--   Filter values that satisfy the value predicate.
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

-- | \(\mathcal{O}(n)\).
--   Filter values that satisfy the value predicate.
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



-- | \(\mathcal{O}(n)\).
--   Apply a function to every value in the tree and create one out of 'Just' values.
--
--   The 'Maybe' is evaluated to WHNF.
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

-- | \(\mathcal{O}(n)\).
--   Apply a function to every value in the tree
--   and create a tree out of 'Just' results.
--
--   The 'Maybe' is evaluated to WHNF.
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



-- | \(\mathcal{O}(n)\).
--   Split the tree into two, such that values that satisfy the predicate
--   are on the left and values that do not are on the right.
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 #)

-- | \(\mathcal{O}(n)\).
--   Split the tree into two, such that values that satisfy the predicate
--   are on the left and values that do not are on the right.
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 #)


-- | \(\mathcal{O}(n)\).
--   Apply a function to every value in the tree and create two trees,
--   one out of 'Left' results and one out of 'Right' ones.
--
--   The 'Either' is evaluated to WHNF.
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 #)

-- | \(\mathcal{O}(n)\).
--   Apply a function to every value in the tree and create two trees,
--   one out of 'Left' results and one out of 'Right' ones.
--
--   The 'Either' is evaluated to WHNF.
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"



-- | \(\mathcal{O}(\min(n,W))\).
--   Look up a value at the leftmost key in the tree.
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

-- | \(\mathcal{O}(\min(n,W))\).
--   Look up a value at the leftmost key in the tree.
--
--   Throws 'MalformedTree' if the tree is empty.
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"


-- | \(\mathcal{O}(\min(n,W))\).
--   Look up a value at the leftmost key in the tree.
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

-- | \(\mathcal{O}(\min(n,W))\).
--   Look up a value at the leftmost key in the tree.
--
--   Throws 'MalformedTree' if the tree is empty.
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"



-- | \(\mathcal{O}(\min(n,W))\).
--   Look up a value at the rightmost key in the tree.
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

-- | \(\mathcal{O}(\min(n,W))\).
--   Look up a value at the rightmost key in the tree.
--
--   Throws 'MalformedTree' if the tree is empty.
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"


-- | \(\mathcal{O}(\min(n,W))\).
--   Look up a value at the rightmost key in the tree.
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

-- | \(\mathcal{O}(\min(n,W))\).
--   Look up a value at the rightmost key in the tree.
--
--   Throws 'MalformedTree' if the tree is empty.
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"



-- | \(\mathcal{O}(\min(n,W))\).
--   Delete a value at the leftmost key in the tree.
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

-- | \(\mathcal{O}(\min(n,W))\).
--   Delete a value at the rightmost key in the tree.
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



-- | \(\mathcal{O}(\min(n,W))\).
--   Update a value at the leftmost key in the tree.
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

-- | \(\mathcal{O}(\min(n,W))\).
--   Update a value at the leftmost key in the tree.
--
--   New value is evaluated to WHNF.
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


-- | \(\mathcal{O}(\min(n,W))\).
--   Update a value at the leftmost key in the tree.
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

-- | \(\mathcal{O}(\min(n,W))\).
--   Update a value at the leftmost key in the tree.
--
--   New value is evaluated to WHNF.
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


-- | \(\mathcal{O}(\min(n,W))\).
--   Update a value at the rightmost key in the tree.
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

-- | \(\mathcal{O}(\min(n,W))\).
--   Update a value at the rightmost key in the tree.
--
--   New value is evaluated to WHNF.
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

-- | \(\mathcal{O}(\min(n,W))\).
--   Update a value at the rightmost key in the tree.
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

-- | \(\mathcal{O}(\min(n,W))\).
--   Update a value at the rightmost key in the tree.
--
--   New value is evaluated to WHNF.
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



-- | \(\mathcal{O}(\min(n,W))\).
--   Update or delete a value at the leftmost key in the tree.
--
--   The 'Maybe' is evaluated to WHNF.
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

-- | \(\mathcal{O}(\min(n,W))\).
--   Update or delete a value at the leftmost key in the tree.
--
--   The 'Maybe' is evaluated to WHNF.
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


-- | \(\mathcal{O}(\min(n,W))\).
--   Update or delete a value at the rightmost key in the tree.
--
--   The 'Maybe' is evaluated to WHNF.
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

-- | \(\mathcal{O}(\min(n,W))\).
--   Update or delete a value at the rightmost key in the tree.
--
--   The 'Maybe' is evaluated to WHNF.
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



-- | \(\mathcal{O}(\min(n,W))\).
--   Look up the leftmost value and return it alongside the tree without it.
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

-- | The leftmost value with its key and the rest of the tree.
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

-- | \(\mathcal{O}(\min(n,W))\).
--   Look up the leftmost value and return it alongside the tree without it.
--
--   Throws 'MalformedTree' if the tree is empty.
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"



-- | \(\mathcal{O}(\min(n,W))\).
--   Look up the rightmost value and return it alongside the tree without it.
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

-- | The rightmost value with its key and the rest of the tree.
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

-- | \(\mathcal{O}(\min(n,W))\).
--   Look up the rightmost value and return it alongside the tree without it.
--
--   Throws 'MalformedTree' if the tree is empty.
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"