-- |
--   Module      :  Data.Edison.Assoc.PatriciaLoMap
--   Copyright   :  Copyright (c) 1998, 2008 Chris Okasaki
--   License     :  MIT; see COPYRIGHT file for terms and conditions
--
--   Maintainer  :  robdockins AT fastmail DOT fm
--   Stability   :  stable
--   Portability :  GHC, Hugs (MPTC and FD)
--
--   Finite maps implemented as little-endian Patricia trees.
--
--   /References:/
--
-- * Chris Okasaki and Any Gill.  \"Fast Mergeable Integer Maps\".
--   Workshop on ML, September 1998, pages 77-86.

module Data.Edison.Assoc.PatriciaLoMap (
    -- * Type of little-endian Patricia trees
    FM,

    -- * AssocX operations
    empty,singleton,fromSeq,insert,insertSeq,union,unionSeq,delete,deleteAll,
    deleteSeq,null,size,member,count,lookup,lookupM,lookupAll,
    lookupAndDelete,lookupAndDeleteM,lookupAndDeleteAll,strict,strictWith,
    lookupWithDefault,adjust,adjustAll,adjustOrInsert,adjustAllOrInsert,map,
    fold,fold',fold1,fold1',filter,partition,elements,structuralInvariant,

    -- * Assoc operations
    toSeq,keys,mapWithKey,foldWithKey,foldWithKey',filterWithKey,partitionWithKey,

    -- * FiniteMapX operations
    fromSeqWith,fromSeqWithKey,insertWith,insertWithKey,insertSeqWith,
    insertSeqWithKey,unionl,unionr,unionWith,unionSeqWith,intersectionWith,
    difference,properSubset,subset,properSubmapBy,submapBy,sameMapBy,
    properSubmap,submap,sameMap,

    -- * FiniteMap operations
    unionWithKey,unionSeqWithKey,intersectionWithKey,

    -- * OrdAssocX operations
    minView, minElem, deleteMin, unsafeInsertMin,
    maxView, maxElem, deleteMax, unsafeInsertMax,
    foldr, foldr', foldr1, foldr1', foldl, foldl', foldl1, foldl1',
    unsafeFromOrdSeq, unsafeAppend, filterLT, filterLE, filterGT, filterGE,
    partitionLT_GE, partitionLE_GT, partitionLT_GT,

    -- * OrdAssoc operations
    minViewWithKey, minElemWithKey, maxViewWithKey, maxElemWithKey,
    foldrWithKey, foldrWithKey', foldlWithKey, foldlWithKey',
    toOrdSeq,

    -- * Documentation
    moduleName
) where

import Prelude hiding (null,map,lookup,foldr,foldl,foldr1,foldl1,foldl',filter)
import qualified Prelude
import qualified Control.Monad.Fail as Fail
import Data.Monoid
import Data.Semigroup as SG
import qualified Data.Edison.Assoc as A
import Data.Edison.Prelude ( runFail_ )
import qualified Data.Edison.Seq as S
import qualified Data.Edison.Seq.ListSeq as L
import Data.Edison.Assoc.Defaults
import Data.Int
import Data.Bits
import Test.QuickCheck (Arbitrary(..), CoArbitrary(..), variant)

moduleName :: String
moduleName :: String
moduleName = String
"Data.Edison.Assoc.PatriciaLoMap"

data FM a
  = E
  | L Int a
  | B Int Int !(FM a) !(FM a)

-- Invariants:
-- * No B node has an E child
-- * first argument to B is a prefix
-- * second argument to B is the "branching bit" and is
--   always an exact power of two
-- * all bits in the prefix >= the branching bit are zeros
-- * valid prefix bits match all subnodes

structuralInvariant :: FM a -> Bool
structuralInvariant :: forall a. FM a -> Bool
structuralInvariant FM a
E = Bool
True
structuralInvariant (L Int
_ a
_) = Bool
True
structuralInvariant FM a
x = Int -> Int -> FM a -> Bool
forall a. Int -> Int -> FM a -> Bool
inv Int
0 Int
0 FM a
x

inv :: Int -> Int -> FM a -> Bool
inv :: forall a. Int -> Int -> FM a -> Bool
inv Int
_ Int
_ FM a
E = Bool
False
inv Int
pre Int
msk (L Int
k a
_) = Int
k Int -> Int -> Int
forall a. Bits a => a -> a -> a
.&. Int
msk Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
pre
inv Int
pre Int
msk (B Int
p Int
m FM a
t0 FM a
t1) =
    (Int
p Int -> Int -> Int
forall a. Bits a => a -> a -> a
.&. Int
msk Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
pre) Bool -> Bool -> Bool
&&
    (Int -> Int -> Int
bitcount Int
0 Int
m Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
1) Bool -> Bool -> Bool
&&
    (Int
p Int -> Int -> Int
forall a. Bits a => a -> a -> a
.&. (Int -> Int
forall a. Bits a => a -> a
complement (Int
m Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)) Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
0) Bool -> Bool -> Bool
&&
    Int -> Int -> FM a -> Bool
forall a. Int -> Int -> FM a -> Bool
inv Int
p0 Int
msk' FM a
t0 Bool -> Bool -> Bool
&&
    Int -> Int -> FM a -> Bool
forall a. Int -> Int -> FM a -> Bool
inv Int
p1 Int
msk' FM a
t1

  where p0 :: Int
p0 = Int
p
        p1 :: Int
p1 = Int
p Int -> Int -> Int
forall a. Bits a => a -> a -> a
.|. Int
m
        msk' :: Int
msk' = (Int
m Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
1) Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1

bitcount :: Int -> Int -> Int
bitcount :: Int -> Int -> Int
bitcount Int
a Int
0 = Int
a
bitcount Int
a Int
x = Int
a Int -> Int -> Int
forall a b. a -> b -> b
`seq` Int -> Int -> Int
bitcount (Int
aInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) (Int
x Int -> Int -> Int
forall a. Bits a => a -> a -> a
.&. (Int
xInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1))

-- auxiliary functions

makeB :: Int -> Int -> FM t -> FM t -> FM t
makeB :: forall t. Int -> Int -> FM t -> FM t -> FM t
makeB Int
_ Int
_ FM t
E FM t
t = FM t
t
makeB Int
_ Int
_ FM t
t FM t
E = FM t
t
makeB Int
p Int
m FM t
t0 FM t
t1 = Int -> Int -> FM t -> FM t -> FM t
forall t. Int -> Int -> FM t -> FM t -> FM t
B Int
p Int
m FM t
t0 FM t
t1

lmakeB :: Int -> Int -> FM t -> FM t -> FM t
lmakeB :: forall t. Int -> Int -> FM t -> FM t -> FM t
lmakeB Int
_ Int
_ FM t
E FM t
t = FM t
t
lmakeB Int
p Int
m FM t
t0 FM t
t1 = Int -> Int -> FM t -> FM t -> FM t
forall t. Int -> Int -> FM t -> FM t -> FM t
B Int
p Int
m FM t
t0 FM t
t1

rmakeB :: Int -> Int -> FM a -> FM a -> FM a
rmakeB :: forall t. Int -> Int -> FM t -> FM t -> FM t
rmakeB Int
_ Int
_ FM a
t FM a
E = FM a
t
rmakeB Int
p Int
m FM a
t0 FM a
t1 = Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
B Int
p Int
m FM a
t0 FM a
t1

lowestBit :: Word -> Word
lowestBit :: Word -> Word
lowestBit Word
x = Word
x Word -> Word -> Word
forall a. Bits a => a -> a -> a
.&. (-Word
x)

branchingBit :: Int -> Int -> Int
branchingBit :: Int -> Int -> Int
branchingBit Int
p0 Int
p1 =
  Word -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word -> Word
lowestBit (Int -> Word
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
p0 Word -> Word -> Word
forall a. Bits a => a -> a -> a
`xor` Int -> Word
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
p1))

mask :: Int -> Int -> Int
mask :: Int -> Int -> Int
mask Int
p Int
m = Word -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int -> Word
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
p Word -> Word -> Word
forall a. Bits a => a -> a -> a
.&. (Int -> Word
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
m Word -> Word -> Word
forall a. Num a => a -> a -> a
- (Word
1 :: Word)))

shorter :: Int -> Int -> Bool
shorter :: Int -> Int -> Bool
shorter Int
m Int
n = Int -> Word
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
m Word -> Word -> Bool
forall a. Ord a => a -> a -> Bool
< (Int -> Word
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
n :: Word)

zeroBit :: Int -> Int -> Bool
zeroBit :: Int -> Int -> Bool
zeroBit Int
p Int
m = (Int -> Word
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
p) Word -> Word -> Word
forall a. Bits a => a -> a -> a
.&. (Int -> Word
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
m) Word -> Word -> Bool
forall a. Eq a => a -> a -> Bool
== (Word
0 :: Word)

matchPrefix :: Int -> Int -> Int -> Bool
matchPrefix :: Int -> Int -> Int -> Bool
matchPrefix Int
k Int
p Int
m = Int -> Int -> Int
mask Int
k Int
m Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
p

join :: Int -> FM a -> Int -> FM a -> FM a
join :: forall a. Int -> FM a -> Int -> FM a -> FM a
join Int
p0 FM a
t0 Int
p1 FM a
t1 =
  let m :: Int
m = Int -> Int -> Int
branchingBit Int
p0 Int
p1
  in if Int -> Int -> Bool
zeroBit Int
p0 Int
m then Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
B (Int -> Int -> Int
mask Int
p0 Int
m) Int
m FM a
t0 FM a
t1
                     else Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
B (Int -> Int -> Int
mask Int
p0 Int
m) Int
m FM a
t1 FM a
t0

keepR :: forall t t1. t -> t1 -> t1
keepR :: forall t t1. t -> t1 -> t1
keepR t
_ t1
y = t1
y

-- end auxiliary functions

empty :: FM a
empty :: forall a. FM a
empty = FM a
forall a. FM a
E

singleton :: Int -> a -> FM a
singleton :: forall a. Int -> a -> FM a
singleton Int
k a
x = Int -> a -> FM a
forall a. Int -> a -> FM a
L Int
k a
x

fromSeq :: S.Sequence seq => seq (Int,a) -> FM a
fromSeq :: forall (seq :: * -> *) a. Sequence seq => seq (Int, a) -> FM a
fromSeq = (FM a -> (Int, a) -> FM a) -> FM a -> seq (Int, a) -> FM a
forall b a. (b -> a -> b) -> b -> seq a -> b
forall (s :: * -> *) b a.
Sequence s =>
(b -> a -> b) -> b -> s a -> b
S.foldl (\FM a
t (Int
k, a
x) -> Int -> a -> FM a -> FM a
forall a. Int -> a -> FM a -> FM a
insert Int
k a
x FM a
t) FM a
forall a. FM a
E

insert :: Int -> a -> FM a -> FM a
insert :: forall a. Int -> a -> FM a -> FM a
insert Int
k a
x FM a
E = Int -> a -> FM a
forall a. Int -> a -> FM a
L Int
k a
x
insert Int
k a
x t :: FM a
t@(L Int
j a
_) = if Int
j Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
k then Int -> a -> FM a
forall a. Int -> a -> FM a
L Int
k a
x else Int -> FM a -> Int -> FM a -> FM a
forall a. Int -> FM a -> Int -> FM a -> FM a
join Int
k (Int -> a -> FM a
forall a. Int -> a -> FM a
L Int
k a
x) Int
j FM a
t
insert Int
k a
x t :: FM a
t@(B Int
p Int
m FM a
t0 FM a
t1) =
    if Int -> Int -> Int -> Bool
matchPrefix Int
k Int
p Int
m then
      if Int -> Int -> Bool
zeroBit Int
k Int
m then Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
B Int
p Int
m (Int -> a -> FM a -> FM a
forall a. Int -> a -> FM a -> FM a
insert Int
k a
x FM a
t0) FM a
t1
                     else Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
B Int
p Int
m FM a
t0 (Int -> a -> FM a -> FM a
forall a. Int -> a -> FM a -> FM a
insert Int
k a
x FM a
t1)
    else Int -> FM a -> Int -> FM a -> FM a
forall a. Int -> FM a -> Int -> FM a -> FM a
join Int
k (Int -> a -> FM a
forall a. Int -> a -> FM a
L Int
k a
x) Int
p FM a
t

union :: FM a -> FM a -> FM a
union :: forall a. FM a -> FM a -> FM a
union s :: FM a
s@(B Int
p Int
m FM a
s0 FM a
s1) t :: FM a
t@(B Int
q Int
n FM a
t0 FM a
t1)
  | Int -> Int -> Bool
shorter Int
m Int
n = if Int -> Int -> Int -> Bool
matchPrefix Int
q Int
p Int
m then
                  if Int -> Int -> Bool
zeroBit Int
q Int
m then Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
B Int
p Int
m (FM a -> FM a -> FM a
forall a. FM a -> FM a -> FM a
union FM a
s0 FM a
t) FM a
s1
                                 else Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
B Int
p Int
m FM a
s0 (FM a -> FM a -> FM a
forall a. FM a -> FM a -> FM a
union FM a
s1 FM a
t)
                else Int -> FM a -> Int -> FM a -> FM a
forall a. Int -> FM a -> Int -> FM a -> FM a
join Int
p FM a
s Int
q FM a
t
  | Int -> Int -> Bool
shorter Int
n Int
m = if Int -> Int -> Int -> Bool
matchPrefix Int
p Int
q Int
n then
                  if Int -> Int -> Bool
zeroBit Int
p Int
n then Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
B Int
q Int
n (FM a -> FM a -> FM a
forall a. FM a -> FM a -> FM a
union FM a
s FM a
t0) FM a
t1
                                 else Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
B Int
q Int
n FM a
t0 (FM a -> FM a -> FM a
forall a. FM a -> FM a -> FM a
union FM a
s FM a
t1)
                else Int -> FM a -> Int -> FM a -> FM a
forall a. Int -> FM a -> Int -> FM a -> FM a
join Int
p FM a
s Int
q FM a
t
  | Bool
otherwise = if Int
p Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
q then Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
B Int
p Int
m (FM a -> FM a -> FM a
forall a. FM a -> FM a -> FM a
union FM a
s0 FM a
t0) (FM a -> FM a -> FM a
forall a. FM a -> FM a -> FM a
union FM a
s1 FM a
t1)
                else Int -> FM a -> Int -> FM a -> FM a
forall a. Int -> FM a -> Int -> FM a -> FM a
join Int
p FM a
s Int
q FM a
t
union s :: FM a
s@(B Int
p Int
m FM a
s0 FM a
s1) (L Int
k a
x) =
    if Int -> Int -> Int -> Bool
matchPrefix Int
k Int
p Int
m then
      if Int -> Int -> Bool
zeroBit Int
k Int
m then Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
B Int
p Int
m (Int -> a -> FM a -> FM a
forall a. Int -> a -> FM a -> FM a
insert Int
k a
x FM a
s0) FM a
s1
                     else Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
B Int
p Int
m FM a
s0 (Int -> a -> FM a -> FM a
forall a. Int -> a -> FM a -> FM a
insert Int
k a
x FM a
s1)
    else Int -> FM a -> Int -> FM a -> FM a
forall a. Int -> FM a -> Int -> FM a -> FM a
join Int
k (Int -> a -> FM a
forall a. Int -> a -> FM a
L Int
k a
x) Int
p FM a
s
union s :: FM a
s@(B Int
_ Int
_ FM a
_ FM a
_) FM a
E = FM a
s
union (L Int
k a
x) FM a
t = Int -> a -> FM a -> FM a
forall a. Int -> a -> FM a -> FM a
insert Int
k a
x FM a
t
union FM a
E FM a
t = FM a
t

delete :: Int -> FM a -> FM a
delete :: forall a. Int -> FM a -> FM a
delete Int
_ FM a
E = FM a
forall a. FM a
E
delete Int
k t :: FM a
t@(L Int
j a
_) = if Int
k Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
j then FM a
forall a. FM a
E else FM a
t
delete Int
k t :: FM a
t@(B Int
p Int
m FM a
t0 FM a
t1) =
    if Int -> Int -> Int -> Bool
matchPrefix Int
k Int
p Int
m then
      if Int -> Int -> Bool
zeroBit Int
k Int
m then Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
lmakeB Int
p Int
m (Int -> FM a -> FM a
forall a. Int -> FM a -> FM a
delete Int
k FM a
t0) FM a
t1
                     else Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
rmakeB Int
p Int
m FM a
t0 (Int -> FM a -> FM a
forall a. Int -> FM a -> FM a
delete Int
k FM a
t1)
    else FM a
t

null :: FM a -> Bool
null :: forall a. FM a -> Bool
null FM a
E = Bool
True
null FM a
_ = Bool
False

size :: FM a -> Int
size :: forall a. FM a -> Int
size FM a
E = Int
0
size (L Int
_ a
_) = Int
1
size (B Int
_ Int
_ FM a
t0 FM a
t1) = FM a -> Int
forall a. FM a -> Int
size FM a
t0 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ FM a -> Int
forall a. FM a -> Int
size FM a
t1

member :: Int -> FM a -> Bool
member :: forall a. Int -> FM a -> Bool
member Int
_ FM a
E = Bool
False
member Int
k (L Int
j a
_) = (Int
j Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
k)
member Int
k (B Int
_ Int
m FM a
t0 FM a
t1) = if Int -> Int -> Bool
zeroBit Int
k Int
m then Int -> FM a -> Bool
forall a. Int -> FM a -> Bool
member Int
k FM a
t0 else Int -> FM a -> Bool
forall a. Int -> FM a -> Bool
member Int
k FM a
t1

lookup :: Int -> FM a -> a
lookup :: forall a. Int -> FM a -> a
lookup Int
k FM a
m = Fail a -> a
forall a. Fail a -> a
runFail_ (Int -> FM a -> Fail a
forall (rm :: * -> *) a. MonadFail rm => Int -> FM a -> rm a
lookupM Int
k FM a
m)

lookupM :: (Fail.MonadFail rm) => Int -> FM a -> rm a
lookupM :: forall (rm :: * -> *) a. MonadFail rm => Int -> FM a -> rm a
lookupM Int
_ FM a
E = String -> rm a
forall a. String -> rm a
forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"PatriciaLoMap.lookup: lookup failed"
lookupM Int
k (L Int
j a
x)
  | Int
j Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
k    = a -> rm a
forall a. a -> rm a
forall (m :: * -> *) a. Monad m => a -> m a
return a
x
  | Bool
otherwise = String -> rm a
forall a. String -> rm a
forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"PatriciaLoMap.lookup: lookup failed"
lookupM Int
k (B Int
_ Int
m FM a
t0 FM a
t1) = if Int -> Int -> Bool
zeroBit Int
k Int
m then Int -> FM a -> rm a
forall (rm :: * -> *) a. MonadFail rm => Int -> FM a -> rm a
lookupM Int
k FM a
t0 else Int -> FM a -> rm a
forall (rm :: * -> *) a. MonadFail rm => Int -> FM a -> rm a
lookupM Int
k FM a
t1

doLookupAndDelete :: z -> (a -> FM a -> z) -> Int -> FM a -> z
doLookupAndDelete :: forall z a. z -> (a -> FM a -> z) -> Int -> FM a -> z
doLookupAndDelete z
onFail a -> FM a -> z
_ Int
_ FM a
E = z
onFail
doLookupAndDelete z
onFail a -> FM a -> z
cont Int
k (L Int
j a
x)
     | Int
j Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
k    = a -> FM a -> z
cont a
x FM a
forall a. FM a
E
     | Bool
otherwise = z
onFail
doLookupAndDelete z
onFail a -> FM a -> z
cont Int
k (B Int
p Int
m FM a
t0 FM a
t1)
     | Int -> Int -> Bool
zeroBit Int
k Int
m = z -> (a -> FM a -> z) -> Int -> FM a -> z
forall z a. z -> (a -> FM a -> z) -> Int -> FM a -> z
doLookupAndDelete z
onFail (\a
x FM a
t0' -> a -> FM a -> z
cont a
x (Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
makeB Int
p Int
m FM a
t0' FM a
t1)) Int
k FM a
t0
     | Bool
otherwise   = z -> (a -> FM a -> z) -> Int -> FM a -> z
forall z a. z -> (a -> FM a -> z) -> Int -> FM a -> z
doLookupAndDelete z
onFail (\a
x FM a
t1' -> a -> FM a -> z
cont a
x (Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
makeB Int
p Int
m FM a
t0 FM a
t1')) Int
k FM a
t1

lookupAndDelete :: Int -> FM a -> (a, FM a)
lookupAndDelete :: forall a. Int -> FM a -> (a, FM a)
lookupAndDelete        = (a, FM a) -> (a -> FM a -> (a, FM a)) -> Int -> FM a -> (a, FM a)
forall z a. z -> (a -> FM a -> z) -> Int -> FM a -> z
doLookupAndDelete
                           (String -> (a, FM a)
forall a. HasCallStack => String -> a
error String
"PatriciaLoMap.lookupAndDelete: lookup failed")
                           (,)

lookupAndDeleteM :: Fail.MonadFail m => Int -> FM a -> m (a, FM a)
lookupAndDeleteM :: forall (m :: * -> *) a. MonadFail m => Int -> FM a -> m (a, FM a)
lookupAndDeleteM       = m (a, FM a)
-> (a -> FM a -> m (a, FM a)) -> Int -> FM a -> m (a, FM a)
forall z a. z -> (a -> FM a -> z) -> Int -> FM a -> z
doLookupAndDelete
                           (String -> m (a, FM a)
forall a. String -> m a
forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"PatriciaLoMap.lookupAndDelete: lookup failed")
                           (\a
x FM a
m -> (a, FM a) -> m (a, FM a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (a
x,FM a
m))

lookupAndDeleteAll :: S.Sequence seq => Int -> FM a -> (seq a,FM a)
lookupAndDeleteAll :: forall (seq :: * -> *) a.
Sequence seq =>
Int -> FM a -> (seq a, FM a)
lookupAndDeleteAll Int
k FM a
m = (seq a, FM a)
-> (a -> FM a -> (seq a, FM a)) -> Int -> FM a -> (seq a, FM a)
forall z a. z -> (a -> FM a -> z) -> Int -> FM a -> z
doLookupAndDelete
                           (seq a
forall (s :: * -> *) a. Sequence s => s a
S.empty, FM a
m)
                           (\a
x FM a
m' -> (a -> seq a
forall (s :: * -> *) a. Sequence s => a -> s a
S.singleton a
x,FM a
m'))
                           Int
k FM a
m


adjust :: (a -> a) -> Int -> FM a -> FM a
adjust :: forall a. (a -> a) -> Int -> FM a -> FM a
adjust a -> a
_ Int
_ FM a
E = FM a
forall a. FM a
E
adjust a -> a
f Int
k t :: FM a
t@(L Int
j a
x) = if Int
k Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
j then Int -> a -> FM a
forall a. Int -> a -> FM a
L Int
k (a -> a
f a
x) else FM a
t
adjust a -> a
f Int
k t :: FM a
t@(B Int
p Int
m FM a
t0 FM a
t1) =
    if Int -> Int -> Int -> Bool
matchPrefix Int
k Int
p Int
m then
      if Int -> Int -> Bool
zeroBit Int
k Int
m then Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
B Int
p Int
m ((a -> a) -> Int -> FM a -> FM a
forall a. (a -> a) -> Int -> FM a -> FM a
adjust a -> a
f Int
k FM a
t0) FM a
t1
                     else Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
B Int
p Int
m FM a
t0 ((a -> a) -> Int -> FM a -> FM a
forall a. (a -> a) -> Int -> FM a -> FM a
adjust a -> a
f Int
k FM a
t1)
    else FM a
t

-- FIXME can we do better than this?
adjustOrInsert :: (a -> a) -> a -> Int -> FM a -> FM a
adjustOrInsert :: forall a. (a -> a) -> a -> Int -> FM a -> FM a
adjustOrInsert = (a -> a) -> a -> Int -> FM a -> FM a
forall (m :: * -> *) k a.
AssocX m k =>
(a -> a) -> a -> k -> m a -> m a
adjustOrInsertUsingMember

adjustAllOrInsert :: (a -> a) -> a -> Int -> FM a -> FM a
adjustAllOrInsert :: forall a. (a -> a) -> a -> Int -> FM a -> FM a
adjustAllOrInsert = (a -> a) -> a -> Int -> FM a -> FM a
forall (m :: * -> *) k a.
AssocX m k =>
(a -> a) -> a -> k -> m a -> m a
adjustOrInsertUsingMember

adjustOrDelete :: (a -> Maybe a) -> Int -> FM a -> FM a
adjustOrDelete :: forall a. (a -> Maybe a) -> Int -> FM a -> FM a
adjustOrDelete = (a -> Maybe a) -> Int -> FM a -> FM a
forall (m :: * -> *) k a.
AssocX m k =>
(a -> Maybe a) -> k -> m a -> m a
adjustOrDeleteDefault

adjustOrDeleteAll :: (a -> Maybe a) -> Int -> FM a -> FM a
adjustOrDeleteAll :: forall a. (a -> Maybe a) -> Int -> FM a -> FM a
adjustOrDeleteAll = (a -> Maybe a) -> Int -> FM a -> FM a
forall (m :: * -> *) k a.
AssocX m k =>
(a -> Maybe a) -> k -> m a -> m a
adjustOrDeleteDefault

map :: (a -> b) -> FM a -> FM b
map :: forall a b. (a -> b) -> FM a -> FM b
map a -> b
_ FM a
E = FM b
forall a. FM a
E
map a -> b
f (L Int
k a
x) = Int -> b -> FM b
forall a. Int -> a -> FM a
L Int
k (a -> b
f a
x)
map a -> b
f (B Int
p Int
m FM a
t0 FM a
t1) = Int -> Int -> FM b -> FM b -> FM b
forall t. Int -> Int -> FM t -> FM t -> FM t
B Int
p Int
m ((a -> b) -> FM a -> FM b
forall a b. (a -> b) -> FM a -> FM b
map a -> b
f FM a
t0) ((a -> b) -> FM a -> FM b
forall a b. (a -> b) -> FM a -> FM b
map a -> b
f FM a
t1)

fold :: (a -> b -> b) -> b -> FM a -> b
fold :: forall a b. (a -> b -> b) -> b -> FM a -> b
fold a -> b -> b
_ b
c FM a
E = b
c
fold a -> b -> b
f b
c (L Int
_ a
x) = a -> b -> b
f a
x b
c
fold a -> b -> b
f b
c (B Int
_ Int
_ FM a
t0 FM a
t1) = (a -> b -> b) -> b -> FM a -> b
forall a b. (a -> b -> b) -> b -> FM a -> b
fold a -> b -> b
f ((a -> b -> b) -> b -> FM a -> b
forall a b. (a -> b -> b) -> b -> FM a -> b
fold a -> b -> b
f b
c FM a
t1) FM a
t0

fold' :: (a -> b -> b) -> b -> FM a -> b
fold' :: forall a b. (a -> b -> b) -> b -> FM a -> b
fold' a -> b -> b
_ b
c FM a
E = b
c
fold' a -> b -> b
f b
c (L Int
_ a
x) = b
c b -> b -> b
forall a b. a -> b -> b
`seq` a -> b -> b
f a
x b
c
fold' a -> b -> b
f b
c (B Int
_ Int
_ FM a
t0 FM a
t1) = b
c b -> b -> b
forall a b. a -> b -> b
`seq` ((a -> b -> b) -> b -> FM a -> b
forall a b. (a -> b -> b) -> b -> FM a -> b
fold a -> b -> b
f (b -> FM a -> b) -> b -> FM a -> b
forall a b. (a -> b) -> a -> b
$! ((a -> b -> b) -> b -> FM a -> b
forall a b. (a -> b -> b) -> b -> FM a -> b
fold a -> b -> b
f b
c FM a
t1)) FM a
t0

fold1 :: (a -> a -> a) -> FM a -> a
fold1 :: forall a. (a -> a -> a) -> FM a -> a
fold1 a -> a -> a
_ FM a
E = String -> a
forall a. HasCallStack => String -> a
error String
"PatriciaLoMap.fold1: empty map"
fold1 a -> a -> a
_ (L Int
_ a
x) = a
x
fold1 a -> a -> a
f (B Int
_ Int
_ FM a
t0 FM a
t1) = a -> a -> a
f ((a -> a -> a) -> FM a -> a
forall a. (a -> a -> a) -> FM a -> a
fold1 a -> a -> a
f FM a
t0) ((a -> a -> a) -> FM a -> a
forall a. (a -> a -> a) -> FM a -> a
fold1 a -> a -> a
f FM a
t1)

fold1' :: (a -> a -> a) -> FM a -> a
fold1' :: forall a. (a -> a -> a) -> FM a -> a
fold1' a -> a -> a
_ FM a
E = String -> a
forall a. HasCallStack => String -> a
error String
"PatriciaLoMap.fold1: empty map"
fold1' a -> a -> a
_ (L Int
_ a
x) = a
x
fold1' a -> a -> a
f (B Int
_ Int
_ FM a
t0 FM a
t1) = a -> a -> a
f ((a -> a -> a) -> FM a -> a
forall a. (a -> a -> a) -> FM a -> a
fold1' a -> a -> a
f FM a
t0) (a -> a) -> a -> a
forall a b. (a -> b) -> a -> b
$! ((a -> a -> a) -> FM a -> a
forall a. (a -> a -> a) -> FM a -> a
fold1' a -> a -> a
f FM a
t1)

filter :: (a -> Bool) -> FM a -> FM a
filter :: forall a. (a -> Bool) -> FM a -> FM a
filter a -> Bool
_ FM a
E = FM a
forall a. FM a
E
filter a -> Bool
g t :: FM a
t@(L Int
_ a
x) = if a -> Bool
g a
x then FM a
t else FM a
forall a. FM a
E
filter a -> Bool
g (B Int
p Int
m FM a
t0 FM a
t1) = Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
makeB Int
p Int
m ((a -> Bool) -> FM a -> FM a
forall a. (a -> Bool) -> FM a -> FM a
filter a -> Bool
g FM a
t0) ((a -> Bool) -> FM a -> FM a
forall a. (a -> Bool) -> FM a -> FM a
filter a -> Bool
g FM a
t1)

partition :: (a -> Bool) -> FM a -> (FM a, FM a)
partition :: forall a. (a -> Bool) -> FM a -> (FM a, FM a)
partition a -> Bool
_ FM a
E = (FM a
forall a. FM a
E, FM a
forall a. FM a
E)
partition a -> Bool
g t :: FM a
t@(L Int
_ a
x) = if a -> Bool
g a
x then (FM a
t, FM a
forall a. FM a
E) else (FM a
forall a. FM a
E, FM a
t)
partition a -> Bool
g (B Int
p Int
m FM a
t0 FM a
t1) =
  let (FM a
t0',FM a
t0'') = (a -> Bool) -> FM a -> (FM a, FM a)
forall a. (a -> Bool) -> FM a -> (FM a, FM a)
partition a -> Bool
g FM a
t0
      (FM a
t1',FM a
t1'') = (a -> Bool) -> FM a -> (FM a, FM a)
forall a. (a -> Bool) -> FM a -> (FM a, FM a)
partition a -> Bool
g FM a
t1
  in (Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
makeB Int
p Int
m FM a
t0' FM a
t1', Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
makeB Int
p Int
m FM a
t0'' FM a
t1'')

fromSeqWith :: S.Sequence seq => (a -> a -> a) -> seq (Int,a) -> FM a
fromSeqWith :: forall (seq :: * -> *) a.
Sequence seq =>
(a -> a -> a) -> seq (Int, a) -> FM a
fromSeqWith a -> a -> a
f = (FM a -> (Int, a) -> FM a) -> FM a -> seq (Int, a) -> FM a
forall b a. (b -> a -> b) -> b -> seq a -> b
forall (s :: * -> *) b a.
Sequence s =>
(b -> a -> b) -> b -> s a -> b
S.foldl (\FM a
t (Int
k, a
x) -> (a -> a -> a) -> Int -> a -> FM a -> FM a
forall a. (a -> a -> a) -> Int -> a -> FM a -> FM a
insertWith a -> a -> a
f Int
k a
x FM a
t) FM a
forall a. FM a
E

insertWith :: (a -> a -> a) -> Int -> a -> FM a -> FM a
insertWith :: forall a. (a -> a -> a) -> Int -> a -> FM a -> FM a
insertWith a -> a -> a
_ Int
k a
x FM a
E = Int -> a -> FM a
forall a. Int -> a -> FM a
L Int
k a
x
insertWith a -> a -> a
f Int
k a
x t :: FM a
t@(L Int
j a
y) = if Int
j Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
k then Int -> a -> FM a
forall a. Int -> a -> FM a
L Int
k (a -> a -> a
f a
x a
y) else Int -> FM a -> Int -> FM a -> FM a
forall a. Int -> FM a -> Int -> FM a -> FM a
join Int
k (Int -> a -> FM a
forall a. Int -> a -> FM a
L Int
k a
x) Int
j FM a
t
insertWith a -> a -> a
f Int
k a
x t :: FM a
t@(B Int
p Int
m FM a
t0 FM a
t1) =
    if Int -> Int -> Int -> Bool
matchPrefix Int
k Int
p Int
m then
      if Int -> Int -> Bool
zeroBit Int
k Int
m then Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
B Int
p Int
m ((a -> a -> a) -> Int -> a -> FM a -> FM a
forall a. (a -> a -> a) -> Int -> a -> FM a -> FM a
insertWith a -> a -> a
f Int
k a
x FM a
t0) FM a
t1
                     else Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
B Int
p Int
m FM a
t0 ((a -> a -> a) -> Int -> a -> FM a -> FM a
forall a. (a -> a -> a) -> Int -> a -> FM a -> FM a
insertWith a -> a -> a
f Int
k a
x FM a
t1)
    else Int -> FM a -> Int -> FM a -> FM a
forall a. Int -> FM a -> Int -> FM a -> FM a
join Int
k (Int -> a -> FM a
forall a. Int -> a -> FM a
L Int
k a
x) Int
p FM a
t

unionl :: FM a -> FM a -> FM a
unionl :: forall a. FM a -> FM a -> FM a
unionl s :: FM a
s@(B Int
p Int
m FM a
s0 FM a
s1) t :: FM a
t@(B Int
q Int
n FM a
t0 FM a
t1)
  | Int -> Int -> Bool
shorter Int
m Int
n = if Int -> Int -> Int -> Bool
matchPrefix Int
q Int
p Int
m then
                  if Int -> Int -> Bool
zeroBit Int
q Int
m then Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
B Int
p Int
m (FM a -> FM a -> FM a
forall a. FM a -> FM a -> FM a
unionl FM a
s0 FM a
t) FM a
s1
                                 else Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
B Int
p Int
m FM a
s0 (FM a -> FM a -> FM a
forall a. FM a -> FM a -> FM a
unionl FM a
s1 FM a
t)
                else Int -> FM a -> Int -> FM a -> FM a
forall a. Int -> FM a -> Int -> FM a -> FM a
join Int
p FM a
s Int
q FM a
t
  | Int -> Int -> Bool
shorter Int
n Int
m = if Int -> Int -> Int -> Bool
matchPrefix Int
p Int
q Int
n then
                  if Int -> Int -> Bool
zeroBit Int
p Int
n then Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
B Int
q Int
n (FM a -> FM a -> FM a
forall a. FM a -> FM a -> FM a
unionl FM a
s FM a
t0) FM a
t1
                                 else Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
B Int
q Int
n FM a
t0 (FM a -> FM a -> FM a
forall a. FM a -> FM a -> FM a
unionl FM a
s FM a
t1)
                else Int -> FM a -> Int -> FM a -> FM a
forall a. Int -> FM a -> Int -> FM a -> FM a
join Int
p FM a
s Int
q FM a
t
  | Bool
otherwise = if Int
p Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
q then Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
B Int
p Int
m (FM a -> FM a -> FM a
forall a. FM a -> FM a -> FM a
unionl FM a
s0 FM a
t0) (FM a -> FM a -> FM a
forall a. FM a -> FM a -> FM a
unionl FM a
s1 FM a
t1)
                else Int -> FM a -> Int -> FM a -> FM a
forall a. Int -> FM a -> Int -> FM a -> FM a
join Int
p FM a
s Int
q FM a
t
unionl s :: FM a
s@(B Int
p Int
m FM a
s0 FM a
s1) (L Int
k a
x) =
    if Int -> Int -> Int -> Bool
matchPrefix Int
k Int
p Int
m then
      if Int -> Int -> Bool
zeroBit Int
k Int
m then Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
B Int
p Int
m ((a -> a -> a) -> Int -> a -> FM a -> FM a
forall a. (a -> a -> a) -> Int -> a -> FM a -> FM a
insertWith a -> a -> a
forall t t1. t -> t1 -> t1
keepR Int
k a
x FM a
s0) FM a
s1
                     else Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
B Int
p Int
m FM a
s0 ((a -> a -> a) -> Int -> a -> FM a -> FM a
forall a. (a -> a -> a) -> Int -> a -> FM a -> FM a
insertWith a -> a -> a
forall t t1. t -> t1 -> t1
keepR Int
k a
x FM a
s1)
    else Int -> FM a -> Int -> FM a -> FM a
forall a. Int -> FM a -> Int -> FM a -> FM a
join Int
k (Int -> a -> FM a
forall a. Int -> a -> FM a
L Int
k a
x) Int
p FM a
s
unionl s :: FM a
s@(B Int
_ Int
_ FM a
_ FM a
_) FM a
E = FM a
s
unionl (L Int
k a
x) FM a
t = Int -> a -> FM a -> FM a
forall a. Int -> a -> FM a -> FM a
insert Int
k a
x FM a
t
unionl FM a
E FM a
t = FM a
t

unionr :: FM a -> FM a -> FM a
unionr :: forall a. FM a -> FM a -> FM a
unionr s :: FM a
s@(B Int
p Int
m FM a
s0 FM a
s1) t :: FM a
t@(B Int
q Int
n FM a
t0 FM a
t1)
  | Int -> Int -> Bool
shorter Int
m Int
n = if Int -> Int -> Int -> Bool
matchPrefix Int
q Int
p Int
m then
                  if Int -> Int -> Bool
zeroBit Int
q Int
m then Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
B Int
p Int
m (FM a -> FM a -> FM a
forall a. FM a -> FM a -> FM a
unionr FM a
s0 FM a
t) FM a
s1
                                 else Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
B Int
p Int
m FM a
s0 (FM a -> FM a -> FM a
forall a. FM a -> FM a -> FM a
unionr FM a
s1 FM a
t)
                else Int -> FM a -> Int -> FM a -> FM a
forall a. Int -> FM a -> Int -> FM a -> FM a
join Int
p FM a
s Int
q FM a
t
  | Int -> Int -> Bool
shorter Int
n Int
m = if Int -> Int -> Int -> Bool
matchPrefix Int
p Int
q Int
n then
                  if Int -> Int -> Bool
zeroBit Int
p Int
n then Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
B Int
q Int
n (FM a -> FM a -> FM a
forall a. FM a -> FM a -> FM a
unionr FM a
s FM a
t0) FM a
t1
                                 else Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
B Int
q Int
n FM a
t0 (FM a -> FM a -> FM a
forall a. FM a -> FM a -> FM a
unionr FM a
s FM a
t1)
                else Int -> FM a -> Int -> FM a -> FM a
forall a. Int -> FM a -> Int -> FM a -> FM a
join Int
p FM a
s Int
q FM a
t
  | Bool
otherwise = if Int
p Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
q then Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
B Int
p Int
m (FM a -> FM a -> FM a
forall a. FM a -> FM a -> FM a
unionr FM a
s0 FM a
t0) (FM a -> FM a -> FM a
forall a. FM a -> FM a -> FM a
unionr FM a
s1 FM a
t1)
                else Int -> FM a -> Int -> FM a -> FM a
forall a. Int -> FM a -> Int -> FM a -> FM a
join Int
p FM a
s Int
q FM a
t
unionr s :: FM a
s@(B Int
p Int
m FM a
s0 FM a
s1) (L Int
k a
x) =
    if Int -> Int -> Int -> Bool
matchPrefix Int
k Int
p Int
m then
      if Int -> Int -> Bool
zeroBit Int
k Int
m then Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
B Int
p Int
m (Int -> a -> FM a -> FM a
forall a. Int -> a -> FM a -> FM a
insert Int
k a
x FM a
s0) FM a
s1
                     else Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
B Int
p Int
m FM a
s0 (Int -> a -> FM a -> FM a
forall a. Int -> a -> FM a -> FM a
insert Int
k a
x FM a
s1)
    else Int -> FM a -> Int -> FM a -> FM a
forall a. Int -> FM a -> Int -> FM a -> FM a
join Int
k (Int -> a -> FM a
forall a. Int -> a -> FM a
L Int
k a
x) Int
p FM a
s
unionr s :: FM a
s@(B Int
_ Int
_ FM a
_ FM a
_) FM a
E = FM a
s
unionr (L Int
k a
x) FM a
t = (a -> a -> a) -> Int -> a -> FM a -> FM a
forall a. (a -> a -> a) -> Int -> a -> FM a -> FM a
insertWith a -> a -> a
forall t t1. t -> t1 -> t1
keepR Int
k a
x FM a
t
unionr FM a
E FM a
t = FM a
t

unionWith :: (a -> a -> a) -> FM a -> FM a -> FM a
unionWith :: forall a. (a -> a -> a) -> FM a -> FM a -> FM a
unionWith a -> a -> a
f s :: FM a
s@(B Int
p Int
m FM a
s0 FM a
s1) t :: FM a
t@(B Int
q Int
n FM a
t0 FM a
t1)
  | Int -> Int -> Bool
shorter Int
m Int
n = if Int -> Int -> Int -> Bool
matchPrefix Int
q Int
p Int
m then
                  if Int -> Int -> Bool
zeroBit Int
q Int
m then Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
B Int
p Int
m ((a -> a -> a) -> FM a -> FM a -> FM a
forall a. (a -> a -> a) -> FM a -> FM a -> FM a
unionWith a -> a -> a
f FM a
s0 FM a
t) FM a
s1
                                 else Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
B Int
p Int
m FM a
s0 ((a -> a -> a) -> FM a -> FM a -> FM a
forall a. (a -> a -> a) -> FM a -> FM a -> FM a
unionWith a -> a -> a
f FM a
s1 FM a
t)
                else Int -> FM a -> Int -> FM a -> FM a
forall a. Int -> FM a -> Int -> FM a -> FM a
join Int
p FM a
s Int
q FM a
t
  | Int -> Int -> Bool
shorter Int
n Int
m = if Int -> Int -> Int -> Bool
matchPrefix Int
p Int
q Int
n then
                  if Int -> Int -> Bool
zeroBit Int
p Int
n then Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
B Int
q Int
n ((a -> a -> a) -> FM a -> FM a -> FM a
forall a. (a -> a -> a) -> FM a -> FM a -> FM a
unionWith a -> a -> a
f FM a
s FM a
t0) FM a
t1
                                 else Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
B Int
q Int
n FM a
t0 ((a -> a -> a) -> FM a -> FM a -> FM a
forall a. (a -> a -> a) -> FM a -> FM a -> FM a
unionWith a -> a -> a
f FM a
s FM a
t1)
                else Int -> FM a -> Int -> FM a -> FM a
forall a. Int -> FM a -> Int -> FM a -> FM a
join Int
p FM a
s Int
q FM a
t
  | Bool
otherwise = if Int
p Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
q then Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
B Int
p Int
m ((a -> a -> a) -> FM a -> FM a -> FM a
forall a. (a -> a -> a) -> FM a -> FM a -> FM a
unionWith a -> a -> a
f FM a
s0 FM a
t0) ((a -> a -> a) -> FM a -> FM a -> FM a
forall a. (a -> a -> a) -> FM a -> FM a -> FM a
unionWith a -> a -> a
f FM a
s1 FM a
t1)
                else Int -> FM a -> Int -> FM a -> FM a
forall a. Int -> FM a -> Int -> FM a -> FM a
join Int
p FM a
s Int
q FM a
t
unionWith a -> a -> a
f s :: FM a
s@(B Int
p Int
m FM a
s0 FM a
s1) (L Int
k a
x) =
    if Int -> Int -> Int -> Bool
matchPrefix Int
k Int
p Int
m then
      if Int -> Int -> Bool
zeroBit Int
k Int
m then Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
B Int
p Int
m ((a -> a -> a) -> Int -> a -> FM a -> FM a
forall a. (a -> a -> a) -> Int -> a -> FM a -> FM a
insertWith ((a -> a -> a) -> a -> a -> a
forall a b c. (a -> b -> c) -> b -> a -> c
flip a -> a -> a
f) Int
k a
x FM a
s0) FM a
s1
                     else Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
B Int
p Int
m FM a
s0 ((a -> a -> a) -> Int -> a -> FM a -> FM a
forall a. (a -> a -> a) -> Int -> a -> FM a -> FM a
insertWith ((a -> a -> a) -> a -> a -> a
forall a b c. (a -> b -> c) -> b -> a -> c
flip a -> a -> a
f) Int
k a
x FM a
s1)
    else Int -> FM a -> Int -> FM a -> FM a
forall a. Int -> FM a -> Int -> FM a -> FM a
join Int
k (Int -> a -> FM a
forall a. Int -> a -> FM a
L Int
k a
x) Int
p FM a
s
unionWith a -> a -> a
_ s :: FM a
s@(B Int
_ Int
_ FM a
_ FM a
_) FM a
E = FM a
s
unionWith a -> a -> a
f (L Int
k a
x) FM a
t = (a -> a -> a) -> Int -> a -> FM a -> FM a
forall a. (a -> a -> a) -> Int -> a -> FM a -> FM a
insertWith a -> a -> a
f Int
k a
x FM a
t
unionWith a -> a -> a
_ FM a
E FM a
t = FM a
t

intersectionWith :: (a -> b -> c) -> FM a -> FM b -> FM c
intersectionWith :: forall a b c. (a -> b -> c) -> FM a -> FM b -> FM c
intersectionWith a -> b -> c
f s :: FM a
s@(B Int
p Int
m FM a
s0 FM a
s1) t :: FM b
t@(B Int
q Int
n FM b
t0 FM b
t1)
  | Int -> Int -> Bool
shorter Int
m Int
n = if Int -> Int -> Int -> Bool
matchPrefix Int
q Int
p Int
m then
                  if Int -> Int -> Bool
zeroBit Int
q Int
m then (a -> b -> c) -> FM a -> FM b -> FM c
forall a b c. (a -> b -> c) -> FM a -> FM b -> FM c
intersectionWith a -> b -> c
f FM a
s0 FM b
t
                                 else (a -> b -> c) -> FM a -> FM b -> FM c
forall a b c. (a -> b -> c) -> FM a -> FM b -> FM c
intersectionWith a -> b -> c
f FM a
s1 FM b
t
                else FM c
forall a. FM a
E
  | Int -> Int -> Bool
shorter Int
n Int
m = if Int -> Int -> Int -> Bool
matchPrefix Int
p Int
q Int
n then
                  if Int -> Int -> Bool
zeroBit Int
p Int
n then (a -> b -> c) -> FM a -> FM b -> FM c
forall a b c. (a -> b -> c) -> FM a -> FM b -> FM c
intersectionWith a -> b -> c
f FM a
s FM b
t0
                                 else (a -> b -> c) -> FM a -> FM b -> FM c
forall a b c. (a -> b -> c) -> FM a -> FM b -> FM c
intersectionWith a -> b -> c
f FM a
s FM b
t1
                else FM c
forall a. FM a
E
  | Bool
otherwise = if Int
p Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
/= Int
q then FM c
forall a. FM a
E
                else Int -> Int -> FM c -> FM c -> FM c
forall t. Int -> Int -> FM t -> FM t -> FM t
makeB Int
p Int
m ((a -> b -> c) -> FM a -> FM b -> FM c
forall a b c. (a -> b -> c) -> FM a -> FM b -> FM c
intersectionWith a -> b -> c
f FM a
s0 FM b
t0) ((a -> b -> c) -> FM a -> FM b -> FM c
forall a b c. (a -> b -> c) -> FM a -> FM b -> FM c
intersectionWith a -> b -> c
f FM a
s1 FM b
t1)
intersectionWith a -> b -> c
f (B Int
_ Int
m FM a
s0 FM a
s1) (L Int
k b
y) =
    case Int -> FM a -> Maybe a
forall (rm :: * -> *) a. MonadFail rm => Int -> FM a -> rm a
lookupM Int
k (if Int -> Int -> Bool
zeroBit Int
k Int
m then FM a
s0 else FM a
s1) of
      Just a
x  -> Int -> c -> FM c
forall a. Int -> a -> FM a
L Int
k (a -> b -> c
f a
x b
y)
      Maybe a
Nothing -> FM c
forall a. FM a
E
intersectionWith a -> b -> c
_ (B Int
_ Int
_ FM a
_ FM a
_) FM b
E = FM c
forall a. FM a
E
intersectionWith a -> b -> c
f (L Int
k a
x) FM b
t =
    case Int -> FM b -> Maybe b
forall (rm :: * -> *) a. MonadFail rm => Int -> FM a -> rm a
lookupM Int
k FM b
t of
      Just b
y  -> Int -> c -> FM c
forall a. Int -> a -> FM a
L Int
k (a -> b -> c
f a
x b
y)
      Maybe b
Nothing -> FM c
forall a. FM a
E
intersectionWith a -> b -> c
_ FM a
E FM b
_ = FM c
forall a. FM a
E

difference :: FM a -> FM b -> FM a
difference :: forall a b. FM a -> FM b -> FM a
difference s :: FM a
s@(B Int
p Int
m FM a
s0 FM a
s1) t :: FM b
t@(B Int
q Int
n FM b
t0 FM b
t1)
  | Int -> Int -> Bool
shorter Int
m Int
n = if Int -> Int -> Int -> Bool
matchPrefix Int
q Int
p Int
m then
                  if Int -> Int -> Bool
zeroBit Int
q Int
m then Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
lmakeB Int
p Int
m (FM a -> FM b -> FM a
forall a b. FM a -> FM b -> FM a
difference FM a
s0 FM b
t) FM a
s1
                                 else Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
rmakeB Int
p Int
m FM a
s0 (FM a -> FM b -> FM a
forall a b. FM a -> FM b -> FM a
difference FM a
s1 FM b
t)
                else FM a
s
  | Int -> Int -> Bool
shorter Int
n Int
m = if Int -> Int -> Int -> Bool
matchPrefix Int
p Int
q Int
n then
                  if Int -> Int -> Bool
zeroBit Int
p Int
n then FM a -> FM b -> FM a
forall a b. FM a -> FM b -> FM a
difference FM a
s FM b
t0
                                 else FM a -> FM b -> FM a
forall a b. FM a -> FM b -> FM a
difference FM a
s FM b
t1
                else FM a
s
  | Bool
otherwise = if Int
p Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
/= Int
q then FM a
s
                else Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
makeB Int
p Int
m (FM a -> FM b -> FM a
forall a b. FM a -> FM b -> FM a
difference FM a
s0 FM b
t0) (FM a -> FM b -> FM a
forall a b. FM a -> FM b -> FM a
difference FM a
s1 FM b
t1)
difference s :: FM a
s@(B Int
p Int
m FM a
s0 FM a
s1) (L Int
k b
_) =
    if Int -> Int -> Int -> Bool
matchPrefix Int
k Int
p Int
m then
      if Int -> Int -> Bool
zeroBit Int
k Int
m then Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
lmakeB Int
p Int
m (Int -> FM a -> FM a
forall a. Int -> FM a -> FM a
delete Int
k FM a
s0) FM a
s1
                     else Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
rmakeB Int
p Int
m FM a
s0 (Int -> FM a -> FM a
forall a. Int -> FM a -> FM a
delete Int
k FM a
s1)
    else FM a
s
difference s :: FM a
s@(B Int
_ Int
_ FM a
_ FM a
_) FM b
E = FM a
s
difference s :: FM a
s@(L Int
k a
_) FM b
t = if Int -> FM b -> Bool
forall a. Int -> FM a -> Bool
member Int
k FM b
t then FM a
forall a. FM a
E else FM a
s
difference FM a
E FM b
_ = FM a
forall a. FM a
E

properSubset :: FM a -> FM b -> Bool
properSubset :: forall a b. FM a -> FM b -> Bool
properSubset FM a
s FM b
t = case FM a -> FM b -> Ordering
forall t t1. FM t -> FM t1 -> Ordering
subset' FM a
s FM b
t of {Ordering
LT -> Bool
True; Ordering
_ -> Bool
False}

subset' :: FM t -> FM t1 -> Ordering
subset' :: forall t t1. FM t -> FM t1 -> Ordering
subset' s :: FM t
s@(B Int
p Int
m FM t
s0 FM t
s1) (B Int
q Int
n FM t1
t0 FM t1
t1)
  | Int -> Int -> Bool
shorter Int
m Int
n = Ordering
GT
  | Int -> Int -> Bool
shorter Int
n Int
m = if Int -> Int -> Int -> Bool
matchPrefix Int
p Int
q Int
n then
                  if Int -> Int -> Bool
zeroBit Int
p Int
n then FM t -> FM t1 -> Ordering
forall t t1. FM t -> FM t1 -> Ordering
subset' FM t
s FM t1
t0 Ordering -> Ordering -> Ordering
forall a. Semigroup a => a -> a -> a
SG.<> Ordering
LT
                                 else FM t -> FM t1 -> Ordering
forall t t1. FM t -> FM t1 -> Ordering
subset' FM t
s FM t1
t1 Ordering -> Ordering -> Ordering
forall a. Semigroup a => a -> a -> a
SG.<> Ordering
LT
                else Ordering
GT
  | Bool
otherwise = if Int
p Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
q then case (FM t -> FM t1 -> Ordering
forall t t1. FM t -> FM t1 -> Ordering
subset' FM t
s0 FM t1
t0,FM t -> FM t1 -> Ordering
forall t t1. FM t -> FM t1 -> Ordering
subset' FM t
s1 FM t1
t1) of
                                  (Ordering
GT,Ordering
_)  -> Ordering
GT
                                  (Ordering
_,Ordering
GT)  -> Ordering
GT
                                  (Ordering
EQ,Ordering
EQ) -> Ordering
EQ
                                  (Ordering
_,Ordering
_)   -> Ordering
LT
                else Ordering
GT
subset' (B Int
_ Int
_ FM t
_ FM t
_) FM t1
_ = Ordering
GT
subset' (L Int
k t
_) (L Int
j t1
_) = if Int
k Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
j then Ordering
EQ else Ordering
GT
subset' (L Int
k t
_) FM t1
t = if Int -> FM t1 -> Bool
forall a. Int -> FM a -> Bool
member Int
k FM t1
t then Ordering
LT else Ordering
GT
subset' FM t
E FM t1
E = Ordering
EQ
subset' FM t
E FM t1
_ = Ordering
LT

subset :: FM a -> FM b -> Bool
subset :: forall a b. FM a -> FM b -> Bool
subset s :: FM a
s@(B Int
p Int
m FM a
s0 FM a
s1) (B Int
q Int
n FM b
t0 FM b
t1)
  | Int -> Int -> Bool
shorter Int
m Int
n = Bool
False
  | Int -> Int -> Bool
shorter Int
n Int
m = Int -> Int -> Int -> Bool
matchPrefix Int
p Int
q Int
n Bool -> Bool -> Bool
&& (if Int -> Int -> Bool
zeroBit Int
p Int
n then FM a -> FM b -> Bool
forall a b. FM a -> FM b -> Bool
subset FM a
s FM b
t0
                                                     else FM a -> FM b -> Bool
forall a b. FM a -> FM b -> Bool
subset FM a
s FM b
t1)
  | Bool
otherwise = (Int
p Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
q) Bool -> Bool -> Bool
&& FM a -> FM b -> Bool
forall a b. FM a -> FM b -> Bool
subset FM a
s0 FM b
t0 Bool -> Bool -> Bool
&& FM a -> FM b -> Bool
forall a b. FM a -> FM b -> Bool
subset FM a
s1 FM b
t1
subset (B Int
_ Int
_ FM a
_ FM a
_) FM b
_ = Bool
False
subset (L Int
k a
_) FM b
t = Int -> FM b -> Bool
forall a. Int -> FM a -> Bool
member Int
k FM b
t
subset FM a
E FM b
_ = Bool
True

properSubmapBy :: (a -> a -> Bool) -> FM a -> FM a -> Bool
properSubmapBy :: forall a. (a -> a -> Bool) -> FM a -> FM a -> Bool
properSubmapBy = (a -> a -> Bool) -> FM a -> FM a -> Bool
forall (m :: * -> *) k a.
FiniteMapX m k =>
(a -> a -> Bool) -> m a -> m a -> Bool
properSubmapByUsingSubmapBy

submapBy :: (a -> a -> Bool) -> FM a -> FM a -> Bool
submapBy :: forall a. (a -> a -> Bool) -> FM a -> FM a -> Bool
submapBy = (a -> a -> Bool) -> FM a -> FM a -> Bool
forall (m :: * -> *) k a.
FiniteMap m k =>
(a -> a -> Bool) -> m a -> m a -> Bool
submapByUsingLookupM

sameMapBy :: (a -> a -> Bool) -> FM a -> FM a -> Bool
sameMapBy :: forall a. (a -> a -> Bool) -> FM a -> FM a -> Bool
sameMapBy = (a -> a -> Bool) -> FM a -> FM a -> Bool
forall (m :: * -> *) k a.
FiniteMapX m k =>
(a -> a -> Bool) -> m a -> m a -> Bool
sameMapByUsingSubmapBy

properSubmap :: (Eq a) => FM a -> FM a -> Bool
properSubmap :: forall a. Eq a => FM a -> FM a -> Bool
properSubmap = FM a -> FM a -> Bool
forall a (m :: * -> *) k.
(Eq a, FiniteMapX m k) =>
m a -> m a -> Bool
A.properSubmap

submap :: (Eq a) => FM a -> FM a -> Bool
submap :: forall a. Eq a => FM a -> FM a -> Bool
submap = FM a -> FM a -> Bool
forall a (m :: * -> *) k.
(Eq a, FiniteMapX m k) =>
m a -> m a -> Bool
A.submap

sameMap :: (Eq a) => FM a -> FM a -> Bool
sameMap :: forall a. Eq a => FM a -> FM a -> Bool
sameMap = FM a -> FM a -> Bool
forall a (m :: * -> *) k.
(Eq a, FiniteMapX m k) =>
m a -> m a -> Bool
A.sameMap

mapWithKey :: (Int -> a -> b) -> FM a -> FM b
mapWithKey :: forall a b. (Int -> a -> b) -> FM a -> FM b
mapWithKey Int -> a -> b
_ FM a
E = FM b
forall a. FM a
E
mapWithKey Int -> a -> b
f (L Int
k a
x) = Int -> b -> FM b
forall a. Int -> a -> FM a
L Int
k (Int -> a -> b
f Int
k a
x)
mapWithKey Int -> a -> b
f (B Int
p Int
m FM a
t0 FM a
t1) = Int -> Int -> FM b -> FM b -> FM b
forall t. Int -> Int -> FM t -> FM t -> FM t
B Int
p Int
m ((Int -> a -> b) -> FM a -> FM b
forall a b. (Int -> a -> b) -> FM a -> FM b
mapWithKey Int -> a -> b
f FM a
t0) ((Int -> a -> b) -> FM a -> FM b
forall a b. (Int -> a -> b) -> FM a -> FM b
mapWithKey Int -> a -> b
f FM a
t1)

foldWithKey :: (Int -> a -> b -> b) -> b -> FM a -> b
foldWithKey :: forall a b. (Int -> a -> b -> b) -> b -> FM a -> b
foldWithKey Int -> a -> b -> b
_ b
c FM a
E = b
c
foldWithKey Int -> a -> b -> b
f b
c (L Int
k a
x) = Int -> a -> b -> b
f Int
k a
x b
c
foldWithKey Int -> a -> b -> b
f b
c (B Int
_ Int
_ FM a
t0 FM a
t1) = (Int -> a -> b -> b) -> b -> FM a -> b
forall a b. (Int -> a -> b -> b) -> b -> FM a -> b
foldWithKey Int -> a -> b -> b
f ((Int -> a -> b -> b) -> b -> FM a -> b
forall a b. (Int -> a -> b -> b) -> b -> FM a -> b
foldWithKey Int -> a -> b -> b
f b
c FM a
t1) FM a
t0

foldWithKey' :: (Int -> a -> b -> b) -> b -> FM a -> b
foldWithKey' :: forall a b. (Int -> a -> b -> b) -> b -> FM a -> b
foldWithKey' Int -> a -> b -> b
_ b
c FM a
E = b
c
foldWithKey' Int -> a -> b -> b
f b
c (L Int
k a
x) = b
c b -> b -> b
forall a b. a -> b -> b
`seq` Int -> a -> b -> b
f Int
k a
x b
c
foldWithKey' Int -> a -> b -> b
f b
c (B Int
_ Int
_ FM a
t0 FM a
t1) = b
c b -> b -> b
forall a b. a -> b -> b
`seq` ((Int -> a -> b -> b) -> b -> FM a -> b
forall a b. (Int -> a -> b -> b) -> b -> FM a -> b
foldWithKey Int -> a -> b -> b
f (b -> FM a -> b) -> b -> FM a -> b
forall a b. (a -> b) -> a -> b
$! ((Int -> a -> b -> b) -> b -> FM a -> b
forall a b. (Int -> a -> b -> b) -> b -> FM a -> b
foldWithKey Int -> a -> b -> b
f b
c FM a
t1)) FM a
t0


filterWithKey :: (Int -> a -> Bool) -> FM a -> FM a
filterWithKey :: forall a. (Int -> a -> Bool) -> FM a -> FM a
filterWithKey Int -> a -> Bool
_ FM a
E = FM a
forall a. FM a
E
filterWithKey Int -> a -> Bool
g t :: FM a
t@(L Int
k a
x) = if Int -> a -> Bool
g Int
k a
x then FM a
t else FM a
forall a. FM a
E
filterWithKey Int -> a -> Bool
g (B Int
p Int
m FM a
t0 FM a
t1) =
  Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
makeB Int
p Int
m ((Int -> a -> Bool) -> FM a -> FM a
forall a. (Int -> a -> Bool) -> FM a -> FM a
filterWithKey Int -> a -> Bool
g FM a
t0) ((Int -> a -> Bool) -> FM a -> FM a
forall a. (Int -> a -> Bool) -> FM a -> FM a
filterWithKey Int -> a -> Bool
g FM a
t1)

partitionWithKey :: (Int -> a -> Bool) -> FM a -> (FM a, FM a)
partitionWithKey :: forall a. (Int -> a -> Bool) -> FM a -> (FM a, FM a)
partitionWithKey Int -> a -> Bool
_ FM a
E = (FM a
forall a. FM a
E, FM a
forall a. FM a
E)
partitionWithKey Int -> a -> Bool
g t :: FM a
t@(L Int
k a
x) = if Int -> a -> Bool
g Int
k a
x then (FM a
t, FM a
forall a. FM a
E) else (FM a
forall a. FM a
E, FM a
t)
partitionWithKey Int -> a -> Bool
g (B Int
p Int
m FM a
t0 FM a
t1) =
  let (FM a
t0',FM a
t0'') = (Int -> a -> Bool) -> FM a -> (FM a, FM a)
forall a. (Int -> a -> Bool) -> FM a -> (FM a, FM a)
partitionWithKey Int -> a -> Bool
g FM a
t0
      (FM a
t1',FM a
t1'') = (Int -> a -> Bool) -> FM a -> (FM a, FM a)
forall a. (Int -> a -> Bool) -> FM a -> (FM a, FM a)
partitionWithKey Int -> a -> Bool
g FM a
t1
  in (Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
makeB Int
p Int
m FM a
t0' FM a
t1', Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
makeB Int
p Int
m FM a
t0'' FM a
t1'')

unionWithKey :: (Int -> a -> a -> a) -> FM a -> FM a -> FM a
unionWithKey :: forall a. (Int -> a -> a -> a) -> FM a -> FM a -> FM a
unionWithKey Int -> a -> a -> a
f s :: FM a
s@(B Int
p Int
m FM a
s0 FM a
s1) t :: FM a
t@(B Int
q Int
n FM a
t0 FM a
t1)
  | Int -> Int -> Bool
shorter Int
m Int
n = if Int -> Int -> Int -> Bool
matchPrefix Int
q Int
p Int
m then
                  if Int -> Int -> Bool
zeroBit Int
q Int
m then Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
B Int
p Int
m ((Int -> a -> a -> a) -> FM a -> FM a -> FM a
forall a. (Int -> a -> a -> a) -> FM a -> FM a -> FM a
unionWithKey Int -> a -> a -> a
f FM a
s0 FM a
t) FM a
s1
                                 else Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
B Int
p Int
m FM a
s0 ((Int -> a -> a -> a) -> FM a -> FM a -> FM a
forall a. (Int -> a -> a -> a) -> FM a -> FM a -> FM a
unionWithKey Int -> a -> a -> a
f FM a
s1 FM a
t)
                else Int -> FM a -> Int -> FM a -> FM a
forall a. Int -> FM a -> Int -> FM a -> FM a
join Int
p FM a
s Int
q FM a
t
  | Int -> Int -> Bool
shorter Int
n Int
m = if Int -> Int -> Int -> Bool
matchPrefix Int
p Int
q Int
n then
                  if Int -> Int -> Bool
zeroBit Int
p Int
n then Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
B Int
q Int
n ((Int -> a -> a -> a) -> FM a -> FM a -> FM a
forall a. (Int -> a -> a -> a) -> FM a -> FM a -> FM a
unionWithKey Int -> a -> a -> a
f FM a
s FM a
t0) FM a
t1
                                 else Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
B Int
q Int
n FM a
t0 ((Int -> a -> a -> a) -> FM a -> FM a -> FM a
forall a. (Int -> a -> a -> a) -> FM a -> FM a -> FM a
unionWithKey Int -> a -> a -> a
f FM a
s FM a
t1)
                else Int -> FM a -> Int -> FM a -> FM a
forall a. Int -> FM a -> Int -> FM a -> FM a
join Int
p FM a
s Int
q FM a
t
  | Bool
otherwise = if Int
p Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
q then Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
B Int
p Int
m ((Int -> a -> a -> a) -> FM a -> FM a -> FM a
forall a. (Int -> a -> a -> a) -> FM a -> FM a -> FM a
unionWithKey Int -> a -> a -> a
f FM a
s0 FM a
t0) ((Int -> a -> a -> a) -> FM a -> FM a -> FM a
forall a. (Int -> a -> a -> a) -> FM a -> FM a -> FM a
unionWithKey Int -> a -> a -> a
f FM a
s1 FM a
t1)
                else Int -> FM a -> Int -> FM a -> FM a
forall a. Int -> FM a -> Int -> FM a -> FM a
join Int
p FM a
s Int
q FM a
t
unionWithKey Int -> a -> a -> a
f s :: FM a
s@(B Int
p Int
m FM a
s0 FM a
s1) (L Int
k a
x) =
    if Int -> Int -> Int -> Bool
matchPrefix Int
k Int
p Int
m then
      if Int -> Int -> Bool
zeroBit Int
k Int
m then Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
B Int
p Int
m ((a -> a -> a) -> Int -> a -> FM a -> FM a
forall a. (a -> a -> a) -> Int -> a -> FM a -> FM a
insertWith ((a -> a -> a) -> a -> a -> a
forall a b c. (a -> b -> c) -> b -> a -> c
flip (Int -> a -> a -> a
f Int
k)) Int
k a
x FM a
s0) FM a
s1
                     else Int -> Int -> FM a -> FM a -> FM a
forall t. Int -> Int -> FM t -> FM t -> FM t
B Int
p Int
m FM a
s0 ((a -> a -> a) -> Int -> a -> FM a -> FM a
forall a. (a -> a -> a) -> Int -> a -> FM a -> FM a
insertWith ((a -> a -> a) -> a -> a -> a
forall a b c. (a -> b -> c) -> b -> a -> c
flip (Int -> a -> a -> a
f Int
k)) Int
k a
x FM a
s1)
    else Int -> FM a -> Int -> FM a -> FM a
forall a. Int -> FM a -> Int -> FM a -> FM a
join Int
k (Int -> a -> FM a
forall a. Int -> a -> FM a
L Int
k a
x) Int
p FM a
s
unionWithKey Int -> a -> a -> a
_ s :: FM a
s@(B Int
_ Int
_ FM a
_ FM a
_) FM a
E = FM a
s
unionWithKey Int -> a -> a -> a
f (L Int
k a
x) FM a
t = (a -> a -> a) -> Int -> a -> FM a -> FM a
forall a. (a -> a -> a) -> Int -> a -> FM a -> FM a
insertWith (Int -> a -> a -> a
f Int
k) Int
k a
x FM a
t
unionWithKey Int -> a -> a -> a
_ FM a
E FM a
t = FM a
t

intersectionWithKey :: (Int -> a -> b -> c) -> FM a -> FM b -> FM c
intersectionWithKey :: forall a b c. (Int -> a -> b -> c) -> FM a -> FM b -> FM c
intersectionWithKey Int -> a -> b -> c
f s :: FM a
s@(B Int
p Int
m FM a
s0 FM a
s1) t :: FM b
t@(B Int
q Int
n FM b
t0 FM b
t1)
  | Int -> Int -> Bool
shorter Int
m Int
n = if Int -> Int -> Int -> Bool
matchPrefix Int
q Int
p Int
m then
                  if Int -> Int -> Bool
zeroBit Int
q Int
m then (Int -> a -> b -> c) -> FM a -> FM b -> FM c
forall a b c. (Int -> a -> b -> c) -> FM a -> FM b -> FM c
intersectionWithKey Int -> a -> b -> c
f FM a
s0 FM b
t
                                 else (Int -> a -> b -> c) -> FM a -> FM b -> FM c
forall a b c. (Int -> a -> b -> c) -> FM a -> FM b -> FM c
intersectionWithKey Int -> a -> b -> c
f FM a
s1 FM b
t
                else FM c
forall a. FM a
E
  | Int -> Int -> Bool
shorter Int
n Int
m = if Int -> Int -> Int -> Bool
matchPrefix Int
p Int
q Int
n then
                  if Int -> Int -> Bool
zeroBit Int
p Int
n then (Int -> a -> b -> c) -> FM a -> FM b -> FM c
forall a b c. (Int -> a -> b -> c) -> FM a -> FM b -> FM c
intersectionWithKey Int -> a -> b -> c
f FM a
s FM b
t0
                                 else (Int -> a -> b -> c) -> FM a -> FM b -> FM c
forall a b c. (Int -> a -> b -> c) -> FM a -> FM b -> FM c
intersectionWithKey Int -> a -> b -> c
f FM a
s FM b
t1
                else FM c
forall a. FM a
E
  | Bool
otherwise = if Int
p Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
/= Int
q then FM c
forall a. FM a
E
                else Int -> Int -> FM c -> FM c -> FM c
forall t. Int -> Int -> FM t -> FM t -> FM t
makeB Int
p Int
m ((Int -> a -> b -> c) -> FM a -> FM b -> FM c
forall a b c. (Int -> a -> b -> c) -> FM a -> FM b -> FM c
intersectionWithKey Int -> a -> b -> c
f FM a
s0 FM b
t0) ((Int -> a -> b -> c) -> FM a -> FM b -> FM c
forall a b c. (Int -> a -> b -> c) -> FM a -> FM b -> FM c
intersectionWithKey Int -> a -> b -> c
f FM a
s1 FM b
t1)
intersectionWithKey Int -> a -> b -> c
f (B Int
_ Int
m FM a
s0 FM a
s1) (L Int
k b
y) =
    case Int -> FM a -> Maybe a
forall (rm :: * -> *) a. MonadFail rm => Int -> FM a -> rm a
lookupM Int
k (if Int -> Int -> Bool
zeroBit Int
k Int
m then FM a
s0 else FM a
s1) of
      Just a
x  -> Int -> c -> FM c
forall a. Int -> a -> FM a
L Int
k (Int -> a -> b -> c
f Int
k a
x b
y)
      Maybe a
Nothing -> FM c
forall a. FM a
E
intersectionWithKey Int -> a -> b -> c
_ (B Int
_ Int
_ FM a
_ FM a
_) FM b
E = FM c
forall a. FM a
E
intersectionWithKey Int -> a -> b -> c
f (L Int
k a
x) FM b
t =
    case Int -> FM b -> Maybe b
forall (rm :: * -> *) a. MonadFail rm => Int -> FM a -> rm a
lookupM Int
k FM b
t of
      Just b
y  -> Int -> c -> FM c
forall a. Int -> a -> FM a
L Int
k (Int -> a -> b -> c
f Int
k a
x b
y)
      Maybe b
Nothing -> FM c
forall a. FM a
E
intersectionWithKey Int -> a -> b -> c
_ FM a
E FM b
_ = FM c
forall a. FM a
E

-- Datastructure definition is strict in all submaps,
-- no forcing required
strict :: t -> t
strict :: forall t. t -> t
strict t
n = t
n

strictWith :: (t -> a) -> FM t -> FM t
strictWith :: forall t a. (t -> a) -> FM t -> FM t
strictWith t -> a
_ n :: FM t
n@FM t
E = FM t
n
strictWith t -> a
f n :: FM t
n@(L Int
_ t
x) = t -> a
f t
x a -> FM t -> FM t
forall a b. a -> b -> b
`seq` FM t
n
strictWith t -> a
f n :: FM t
n@(B Int
_ Int
_ FM t
m1 FM t
m2) = (t -> a) -> FM t -> FM t
forall t a. (t -> a) -> FM t -> FM t
strictWith t -> a
f FM t
m1 FM t -> FM t -> FM t
forall a b. a -> b -> b
`seq` (t -> a) -> FM t -> FM t
forall t a. (t -> a) -> FM t -> FM t
strictWith t -> a
f FM t
m2 FM t -> FM t -> FM t
forall a b. a -> b -> b
`seq` FM t
n


ordListFM :: FM a -> [(Int,a)]
ordListFM :: forall a. FM a -> [(Int, a)]
ordListFM FM a
E = []
ordListFM (L Int
k a
x) = [(Int
k,a
x)]
ordListFM (B Int
_ Int
_ FM a
t0 FM a
t1) = [(Int, a)] -> [(Int, a)] -> [(Int, a)]
forall {a} {b}. Ord a => [(a, b)] -> [(a, b)] -> [(a, b)]
merge (FM a -> [(Int, a)]
forall a. FM a -> [(Int, a)]
ordListFM FM a
t0) (FM a -> [(Int, a)]
forall a. FM a -> [(Int, a)]
ordListFM FM a
t1)
  where merge :: [(a, b)] -> [(a, b)] -> [(a, b)]
merge [] [(a, b)]
ys = [(a, b)]
ys
        merge [(a, b)]
xs [] = [(a, b)]
xs
        merge (x :: (a, b)
x@(a
k1,b
_):[(a, b)]
xs) (y :: (a, b)
y@(a
k2,b
_):[(a, b)]
ys) =
           case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
k1 a
k2 of
              Ordering
LT -> (a, b)
x (a, b) -> [(a, b)] -> [(a, b)]
forall a. a -> [a] -> [a]
: [(a, b)] -> [(a, b)] -> [(a, b)]
merge [(a, b)]
xs ((a, b)
y(a, b) -> [(a, b)] -> [(a, b)]
forall a. a -> [a] -> [a]
:[(a, b)]
ys)
              Ordering
GT -> (a, b)
y (a, b) -> [(a, b)] -> [(a, b)]
forall a. a -> [a] -> [a]
: [(a, b)] -> [(a, b)] -> [(a, b)]
merge ((a, b)
x(a, b) -> [(a, b)] -> [(a, b)]
forall a. a -> [a] -> [a]
:[(a, b)]
xs) [(a, b)]
ys
              Ordering
EQ -> String -> [(a, b)]
forall a. HasCallStack => String -> a
error String
"PatriciaLoMap: bug in ordListFM"

ordListFM_rev :: FM a -> [(Int,a)]
ordListFM_rev :: forall a. FM a -> [(Int, a)]
ordListFM_rev FM a
E = []
ordListFM_rev (L Int
k a
x) = [(Int
k,a
x)]
ordListFM_rev (B Int
_ Int
_ FM a
t0 FM a
t1) = [(Int, a)] -> [(Int, a)] -> [(Int, a)]
forall {a} {b}. Ord a => [(a, b)] -> [(a, b)] -> [(a, b)]
merge (FM a -> [(Int, a)]
forall a. FM a -> [(Int, a)]
ordListFM_rev FM a
t0) (FM a -> [(Int, a)]
forall a. FM a -> [(Int, a)]
ordListFM_rev FM a
t1)
  where merge :: [(a, b)] -> [(a, b)] -> [(a, b)]
merge [] [(a, b)]
ys = [(a, b)]
ys
        merge [(a, b)]
xs [] = [(a, b)]
xs
        merge (x :: (a, b)
x@(a
k1,b
_):[(a, b)]
xs) (y :: (a, b)
y@(a
k2,b
_):[(a, b)]
ys) =
         case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
k1 a
k2 of
            Ordering
LT -> (a, b)
y (a, b) -> [(a, b)] -> [(a, b)]
forall a. a -> [a] -> [a]
: [(a, b)] -> [(a, b)] -> [(a, b)]
merge ((a, b)
x(a, b) -> [(a, b)] -> [(a, b)]
forall a. a -> [a] -> [a]
:[(a, b)]
xs) [(a, b)]
ys
            Ordering
GT -> (a, b)
x (a, b) -> [(a, b)] -> [(a, b)]
forall a. a -> [a] -> [a]
: [(a, b)] -> [(a, b)] -> [(a, b)]
merge [(a, b)]
xs ((a, b)
y(a, b) -> [(a, b)] -> [(a, b)]
forall a. a -> [a] -> [a]
:[(a, b)]
ys)
            Ordering
EQ -> String -> [(a, b)]
forall a. HasCallStack => String -> a
error String
"PatriciaLoMap: bug in ordListFM_rev"

minView :: Fail.MonadFail m => FM a -> m (a, FM a)
minView :: forall (m :: * -> *) a. MonadFail m => FM a -> m (a, FM a)
minView FM a
fm =
   case FM a -> [(Int, a)]
forall a. FM a -> [(Int, a)]
ordListFM FM a
fm of
     [] -> String -> m (a, FM a)
forall a. String -> m a
forall (m :: * -> *) a. MonadFail m => String -> m a
fail (String -> m (a, FM a)) -> String -> m (a, FM a)
forall a b. (a -> b) -> a -> b
$ String
moduleNameString -> String -> String
forall a. [a] -> [a] -> [a]
++String
".minView: empty map"
     ((Int
k,a
x):[(Int, a)]
_) -> (a, FM a) -> m (a, FM a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (a
x,Int -> FM a -> FM a
forall a. Int -> FM a -> FM a
delete Int
k FM a
fm)

minViewWithKey :: Fail.MonadFail m => FM a -> m ((Int, a), FM a)
minViewWithKey :: forall (m :: * -> *) a. MonadFail m => FM a -> m ((Int, a), FM a)
minViewWithKey FM a
fm =
   case FM a -> [(Int, a)]
forall a. FM a -> [(Int, a)]
ordListFM FM a
fm of
     [] -> String -> m ((Int, a), FM a)
forall a. String -> m a
forall (m :: * -> *) a. MonadFail m => String -> m a
fail (String -> m ((Int, a), FM a)) -> String -> m ((Int, a), FM a)
forall a b. (a -> b) -> a -> b
$ String
moduleNameString -> String -> String
forall a. [a] -> [a] -> [a]
++String
".minViewWithKey: empty map"
     ((Int
k,a
x):[(Int, a)]
_) -> ((Int, a), FM a) -> m ((Int, a), FM a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return ((Int
k,a
x),Int -> FM a -> FM a
forall a. Int -> FM a -> FM a
delete Int
k FM a
fm)

maxView :: Fail.MonadFail m => FM a -> m (a, FM a)
maxView :: forall (m :: * -> *) a. MonadFail m => FM a -> m (a, FM a)
maxView FM a
fm =
  case FM a -> [(Int, a)]
forall a. FM a -> [(Int, a)]
ordListFM_rev FM a
fm of
     [] -> String -> m (a, FM a)
forall a. String -> m a
forall (m :: * -> *) a. MonadFail m => String -> m a
fail (String -> m (a, FM a)) -> String -> m (a, FM a)
forall a b. (a -> b) -> a -> b
$ String
moduleNameString -> String -> String
forall a. [a] -> [a] -> [a]
++String
".maxView: empty map"
     ((Int
k,a
x):[(Int, a)]
_) -> (a, FM a) -> m (a, FM a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (a
x,Int -> FM a -> FM a
forall a. Int -> FM a -> FM a
delete Int
k FM a
fm)

maxViewWithKey :: Fail.MonadFail m => FM a -> m ((Int, a), FM a)
maxViewWithKey :: forall (m :: * -> *) a. MonadFail m => FM a -> m ((Int, a), FM a)
maxViewWithKey FM a
fm =
   case FM a -> [(Int, a)]
forall a. FM a -> [(Int, a)]
ordListFM_rev FM a
fm of
     [] -> String -> m ((Int, a), FM a)
forall a. String -> m a
forall (m :: * -> *) a. MonadFail m => String -> m a
fail (String -> m ((Int, a), FM a)) -> String -> m ((Int, a), FM a)
forall a b. (a -> b) -> a -> b
$ String
moduleNameString -> String -> String
forall a. [a] -> [a] -> [a]
++String
".maxViewWithKey: empty map"
     ((Int
k,a
x):[(Int, a)]
_) -> ((Int, a), FM a) -> m ((Int, a), FM a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return ((Int
k,a
x),Int -> FM a -> FM a
forall a. Int -> FM a -> FM a
delete Int
k FM a
fm)

minElem :: FM a -> a
minElem :: forall a. FM a -> a
minElem = FM a -> a
forall (m :: * -> *) k a. OrdAssocX m k => m a -> a
minElemUsingMinView

minElemWithKey :: FM a -> (Int,a)
minElemWithKey :: forall a. FM a -> (Int, a)
minElemWithKey = FM a -> (Int, a)
forall (m :: * -> *) k a. OrdAssoc m k => m a -> (k, a)
minElemWithKeyUsingMinViewWithKey

deleteMin :: FM a -> FM a
deleteMin :: forall a. FM a -> FM a
deleteMin = FM a -> FM a
forall (m :: * -> *) k a. OrdAssocX m k => m a -> m a
deleteMinUsingMinView

unsafeInsertMin :: Int -> a -> FM a -> FM a
unsafeInsertMin :: forall a. Int -> a -> FM a -> FM a
unsafeInsertMin = Int -> a -> FM a -> FM a
forall a. Int -> a -> FM a -> FM a
insert

maxElem :: FM a -> a
maxElem :: forall a. FM a -> a
maxElem = FM a -> a
forall (m :: * -> *) k a. OrdAssocX m k => m a -> a
maxElemUsingMaxView

deleteMax :: FM a -> FM a
deleteMax :: forall a. FM a -> FM a
deleteMax = FM a -> FM a
forall (m :: * -> *) k a. OrdAssocX m k => m a -> m a
deleteMaxUsingMaxView

maxElemWithKey :: FM a -> (Int,a)
maxElemWithKey :: forall a. FM a -> (Int, a)
maxElemWithKey = FM a -> (Int, a)
forall (m :: * -> *) k a. OrdAssoc m k => m a -> (k, a)
maxElemWithKeyUsingMaxViewWithKey

unsafeInsertMax :: Int -> a -> FM a -> FM a
unsafeInsertMax :: forall a. Int -> a -> FM a -> FM a
unsafeInsertMax = Int -> a -> FM a -> FM a
forall a. Int -> a -> FM a -> FM a
insert

foldr :: (a -> b -> b) -> b -> FM a -> b
foldr :: forall a b. (a -> b -> b) -> b -> FM a -> b
foldr a -> b -> b
f b
z FM a
fm = (a -> b -> b) -> b -> [a] -> b
forall a b. (a -> b -> b) -> b -> [a] -> b
L.foldr a -> b -> b
f b
z ([a] -> b) -> (FM a -> [a]) -> FM a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Int, a) -> a) -> [(Int, a)] -> [a]
forall a b. (a -> b) -> [a] -> [b]
L.map (Int, a) -> a
forall a b. (a, b) -> b
snd ([(Int, a)] -> [a]) -> (FM a -> [(Int, a)]) -> FM a -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FM a -> [(Int, a)]
forall a. FM a -> [(Int, a)]
ordListFM (FM a -> b) -> FM a -> b
forall a b. (a -> b) -> a -> b
$ FM a
fm

foldr' :: (a -> b -> b) -> b -> FM a -> b
foldr' :: forall a b. (a -> b -> b) -> b -> FM a -> b
foldr' a -> b -> b
f b
z FM a
fm = (b -> a -> b) -> b -> [a] -> b
forall b a. (b -> a -> b) -> b -> [a] -> b
L.foldl' ((a -> b -> b) -> b -> a -> b
forall a b c. (a -> b -> c) -> b -> a -> c
flip a -> b -> b
f) b
z ([a] -> b) -> (FM a -> [a]) -> FM a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Int, a) -> a) -> [(Int, a)] -> [a]
forall a b. (a -> b) -> [a] -> [b]
L.map (Int, a) -> a
forall a b. (a, b) -> b
snd ([(Int, a)] -> [a]) -> (FM a -> [(Int, a)]) -> FM a -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FM a -> [(Int, a)]
forall a. FM a -> [(Int, a)]
ordListFM_rev (FM a -> b) -> FM a -> b
forall a b. (a -> b) -> a -> b
$ FM a
fm

foldr1 :: (a -> a -> a) -> FM a -> a
foldr1 :: forall a. (a -> a -> a) -> FM a -> a
foldr1 a -> a -> a
f FM a
fm = (a -> a -> a) -> [a] -> a
forall a. (a -> a -> a) -> [a] -> a
L.foldr1 a -> a -> a
f ([a] -> a) -> (FM a -> [a]) -> FM a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Int, a) -> a) -> [(Int, a)] -> [a]
forall a b. (a -> b) -> [a] -> [b]
L.map (Int, a) -> a
forall a b. (a, b) -> b
snd ([(Int, a)] -> [a]) -> (FM a -> [(Int, a)]) -> FM a -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FM a -> [(Int, a)]
forall a. FM a -> [(Int, a)]
ordListFM (FM a -> a) -> FM a -> a
forall a b. (a -> b) -> a -> b
$ FM a
fm

foldr1' :: (a -> a -> a) -> FM a -> a
foldr1' :: forall a. (a -> a -> a) -> FM a -> a
foldr1' a -> a -> a
f FM a
fm = (a -> a -> a) -> [a] -> a
forall a. (a -> a -> a) -> [a] -> a
L.foldl1' ((a -> a -> a) -> a -> a -> a
forall a b c. (a -> b -> c) -> b -> a -> c
flip a -> a -> a
f) ([a] -> a) -> (FM a -> [a]) -> FM a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Int, a) -> a) -> [(Int, a)] -> [a]
forall a b. (a -> b) -> [a] -> [b]
L.map (Int, a) -> a
forall a b. (a, b) -> b
snd ([(Int, a)] -> [a]) -> (FM a -> [(Int, a)]) -> FM a -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FM a -> [(Int, a)]
forall a. FM a -> [(Int, a)]
ordListFM_rev (FM a -> a) -> FM a -> a
forall a b. (a -> b) -> a -> b
$ FM a
fm

foldl :: (b -> a -> b) -> b -> FM a -> b
foldl :: forall b a. (b -> a -> b) -> b -> FM a -> b
foldl b -> a -> b
f b
z FM a
fm = (a -> b -> b) -> b -> [a] -> b
forall a b. (a -> b -> b) -> b -> [a] -> b
L.foldr ((b -> a -> b) -> a -> b -> b
forall a b c. (a -> b -> c) -> b -> a -> c
flip b -> a -> b
f) b
z ([a] -> b) -> (FM a -> [a]) -> FM a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Int, a) -> a) -> [(Int, a)] -> [a]
forall a b. (a -> b) -> [a] -> [b]
L.map (Int, a) -> a
forall a b. (a, b) -> b
snd ([(Int, a)] -> [a]) -> (FM a -> [(Int, a)]) -> FM a -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FM a -> [(Int, a)]
forall a. FM a -> [(Int, a)]
ordListFM_rev (FM a -> b) -> FM a -> b
forall a b. (a -> b) -> a -> b
$ FM a
fm

foldl' :: (b -> a -> b) -> b -> FM a -> b
foldl' :: forall b a. (b -> a -> b) -> b -> FM a -> b
foldl' b -> a -> b
f b
z FM a
fm = (b -> a -> b) -> b -> [a] -> b
forall b a. (b -> a -> b) -> b -> [a] -> b
L.foldl' b -> a -> b
f b
z ([a] -> b) -> (FM a -> [a]) -> FM a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Int, a) -> a) -> [(Int, a)] -> [a]
forall a b. (a -> b) -> [a] -> [b]
L.map (Int, a) -> a
forall a b. (a, b) -> b
snd ([(Int, a)] -> [a]) -> (FM a -> [(Int, a)]) -> FM a -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FM a -> [(Int, a)]
forall a. FM a -> [(Int, a)]
ordListFM (FM a -> b) -> FM a -> b
forall a b. (a -> b) -> a -> b
$ FM a
fm

foldl1 :: (a -> a -> a) -> FM a -> a
foldl1 :: forall a. (a -> a -> a) -> FM a -> a
foldl1 a -> a -> a
f FM a
fm = (a -> a -> a) -> [a] -> a
forall a. (a -> a -> a) -> [a] -> a
L.foldr1 ((a -> a -> a) -> a -> a -> a
forall a b c. (a -> b -> c) -> b -> a -> c
flip a -> a -> a
f) ([a] -> a) -> (FM a -> [a]) -> FM a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Int, a) -> a) -> [(Int, a)] -> [a]
forall a b. (a -> b) -> [a] -> [b]
L.map (Int, a) -> a
forall a b. (a, b) -> b
snd ([(Int, a)] -> [a]) -> (FM a -> [(Int, a)]) -> FM a -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FM a -> [(Int, a)]
forall a. FM a -> [(Int, a)]
ordListFM_rev (FM a -> a) -> FM a -> a
forall a b. (a -> b) -> a -> b
$ FM a
fm

foldl1' :: (a -> a -> a) -> FM a -> a
foldl1' :: forall a. (a -> a -> a) -> FM a -> a
foldl1' a -> a -> a
f FM a
fm = (a -> a -> a) -> [a] -> a
forall a. (a -> a -> a) -> [a] -> a
L.foldl1' a -> a -> a
f ([a] -> a) -> (FM a -> [a]) -> FM a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Int, a) -> a) -> [(Int, a)] -> [a]
forall a b. (a -> b) -> [a] -> [b]
L.map (Int, a) -> a
forall a b. (a, b) -> b
snd ([(Int, a)] -> [a]) -> (FM a -> [(Int, a)]) -> FM a -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FM a -> [(Int, a)]
forall a. FM a -> [(Int, a)]
ordListFM (FM a -> a) -> FM a -> a
forall a b. (a -> b) -> a -> b
$ FM a
fm

foldrWithKey :: (Int -> a -> b -> b) -> b -> FM a -> b
foldrWithKey :: forall a b. (Int -> a -> b -> b) -> b -> FM a -> b
foldrWithKey Int -> a -> b -> b
f b
z FM a
fm = ((Int, a) -> b -> b) -> b -> [(Int, a)] -> b
forall a b. (a -> b -> b) -> b -> [a] -> b
L.foldr ((Int -> a -> b -> b) -> (Int, a) -> b -> b
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry Int -> a -> b -> b
f) b
z ([(Int, a)] -> b) -> (FM a -> [(Int, a)]) -> FM a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FM a -> [(Int, a)]
forall a. FM a -> [(Int, a)]
ordListFM (FM a -> b) -> FM a -> b
forall a b. (a -> b) -> a -> b
$ FM a
fm

foldrWithKey' :: (Int -> a -> b -> b) -> b -> FM a -> b
foldrWithKey' :: forall a b. (Int -> a -> b -> b) -> b -> FM a -> b
foldrWithKey' Int -> a -> b -> b
f b
z FM a
fm = (b -> (Int, a) -> b) -> b -> [(Int, a)] -> b
forall b a. (b -> a -> b) -> b -> [a] -> b
L.foldl' (((Int, a) -> b -> b) -> b -> (Int, a) -> b
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((Int -> a -> b -> b) -> (Int, a) -> b -> b
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry Int -> a -> b -> b
f)) b
z ([(Int, a)] -> b) -> (FM a -> [(Int, a)]) -> FM a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FM a -> [(Int, a)]
forall a. FM a -> [(Int, a)]
ordListFM_rev (FM a -> b) -> FM a -> b
forall a b. (a -> b) -> a -> b
$ FM a
fm

foldlWithKey :: (b -> Int -> a -> b) -> b -> FM a -> b
foldlWithKey :: forall b a. (b -> Int -> a -> b) -> b -> FM a -> b
foldlWithKey b -> Int -> a -> b
f b
z FM a
fm = ((Int, a) -> b -> b) -> b -> [(Int, a)] -> b
forall a b. (a -> b -> b) -> b -> [a] -> b
L.foldr (\(Int
k,a
x) b
a -> b -> Int -> a -> b
f b
a Int
k a
x) b
z ([(Int, a)] -> b) -> (FM a -> [(Int, a)]) -> FM a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FM a -> [(Int, a)]
forall a. FM a -> [(Int, a)]
ordListFM_rev (FM a -> b) -> FM a -> b
forall a b. (a -> b) -> a -> b
$ FM a
fm

foldlWithKey' :: (b -> Int -> a -> b) -> b -> FM a -> b
foldlWithKey' :: forall b a. (b -> Int -> a -> b) -> b -> FM a -> b
foldlWithKey' b -> Int -> a -> b
f b
z FM a
fm = (b -> (Int, a) -> b) -> b -> [(Int, a)] -> b
forall b a. (b -> a -> b) -> b -> [a] -> b
L.foldl' (\b
a (Int
k,a
x) -> b -> Int -> a -> b
f b
a Int
k a
x) b
z ([(Int, a)] -> b) -> (FM a -> [(Int, a)]) -> FM a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FM a -> [(Int, a)]
forall a. FM a -> [(Int, a)]
ordListFM (FM a -> b) -> FM a -> b
forall a b. (a -> b) -> a -> b
$ FM a
fm


unsafeFromOrdSeq :: S.Sequence seq => seq (Int,a) -> FM a
unsafeFromOrdSeq :: forall (seq :: * -> *) a. Sequence seq => seq (Int, a) -> FM a
unsafeFromOrdSeq = seq (Int, a) -> FM a
forall (seq :: * -> *) a. Sequence seq => seq (Int, a) -> FM a
fromSeq

unsafeAppend :: FM a -> FM a -> FM a
unsafeAppend :: forall a. FM a -> FM a -> FM a
unsafeAppend = FM a -> FM a -> FM a
forall a. FM a -> FM a -> FM a
union

filterLT :: Int -> FM a -> FM a
filterLT :: forall a. Int -> FM a -> FM a
filterLT Int
k = (Int -> a -> Bool) -> FM a -> FM a
forall a. (Int -> a -> Bool) -> FM a -> FM a
filterWithKey (\Int
k' a
_ -> Int
k' Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
k)

filterLE :: Int -> FM a -> FM a
filterLE :: forall a. Int -> FM a -> FM a
filterLE Int
k = (Int -> a -> Bool) -> FM a -> FM a
forall a. (Int -> a -> Bool) -> FM a -> FM a
filterWithKey (\Int
k' a
_ -> Int
k' Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
k)

filterGT :: Int -> FM a -> FM a
filterGT :: forall a. Int -> FM a -> FM a
filterGT Int
k = (Int -> a -> Bool) -> FM a -> FM a
forall a. (Int -> a -> Bool) -> FM a -> FM a
filterWithKey (\Int
k' a
_ -> Int
k' Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
k)

filterGE :: Int -> FM a -> FM a
filterGE :: forall a. Int -> FM a -> FM a
filterGE Int
k = (Int -> a -> Bool) -> FM a -> FM a
forall a. (Int -> a -> Bool) -> FM a -> FM a
filterWithKey (\Int
k' a
_ -> Int
k' Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
k)

partitionLT_GE :: Int -> FM a -> (FM a, FM a)
partitionLT_GE :: forall a. Int -> FM a -> (FM a, FM a)
partitionLT_GE Int
k FM a
fm = (Int -> FM a -> FM a
forall a. Int -> FM a -> FM a
filterLT Int
k FM a
fm,Int -> FM a -> FM a
forall a. Int -> FM a -> FM a
filterGE Int
k FM a
fm)

partitionLE_GT :: Int -> FM a -> (FM a,FM a)
partitionLE_GT :: forall a. Int -> FM a -> (FM a, FM a)
partitionLE_GT Int
k FM a
fm = (Int -> FM a -> FM a
forall a. Int -> FM a -> FM a
filterLE Int
k FM a
fm,Int -> FM a -> FM a
forall a. Int -> FM a -> FM a
filterGT Int
k FM a
fm)

partitionLT_GT :: Int -> FM a -> (FM a,FM a)
partitionLT_GT :: forall a. Int -> FM a -> (FM a, FM a)
partitionLT_GT Int
k FM a
fm = (Int -> FM a -> FM a
forall a. Int -> FM a -> FM a
filterLT Int
k FM a
fm,Int -> FM a -> FM a
forall a. Int -> FM a -> FM a
filterGT Int
k FM a
fm)

toOrdSeq :: S.Sequence seq => FM a -> seq (Int,a)
toOrdSeq :: forall (seq :: * -> *) a. Sequence seq => FM a -> seq (Int, a)
toOrdSeq = ((Int, a) -> seq (Int, a) -> seq (Int, a))
-> seq (Int, a) -> [(Int, a)] -> seq (Int, a)
forall a b. (a -> b -> b) -> b -> [a] -> b
L.foldr (Int, a) -> seq (Int, a) -> seq (Int, a)
forall a. a -> seq a -> seq a
forall (s :: * -> *) a. Sequence s => a -> s a -> s a
S.lcons seq (Int, a)
forall (s :: * -> *) a. Sequence s => s a
S.empty ([(Int, a)] -> seq (Int, a))
-> (FM a -> [(Int, a)]) -> FM a -> seq (Int, a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FM a -> [(Int, a)]
forall a. FM a -> [(Int, a)]
ordListFM

-- defaults

insertSeq :: S.Sequence seq => seq (Int,a) -> FM a -> FM a
insertSeq :: forall (seq :: * -> *) a.
Sequence seq =>
seq (Int, a) -> FM a -> FM a
insertSeq = seq (Int, a) -> FM a -> FM a
forall (m :: * -> *) k (seq :: * -> *) a.
(AssocX m k, Sequence seq) =>
seq (k, a) -> m a -> m a
insertSeqUsingFoldr

unionSeq :: S.Sequence seq => seq (FM a) -> FM a
unionSeq :: forall (seq :: * -> *) a. Sequence seq => seq (FM a) -> FM a
unionSeq = seq (FM a) -> FM a
forall (m :: * -> *) k (seq :: * -> *) a.
(AssocX m k, Sequence seq) =>
seq (m a) -> m a
unionSeqUsingReduce

deleteAll :: Int -> FM a -> FM a
deleteAll :: forall a. Int -> FM a -> FM a
deleteAll = Int -> FM a -> FM a
forall a. Int -> FM a -> FM a
delete

deleteSeq :: S.Sequence seq => seq Int -> FM a -> FM a
deleteSeq :: forall (seq :: * -> *) a. Sequence seq => seq Int -> FM a -> FM a
deleteSeq = seq Int -> FM a -> FM a
forall (m :: * -> *) k (seq :: * -> *) a.
(AssocX m k, Sequence seq) =>
seq k -> m a -> m a
deleteSeqUsingFoldr

count :: Int -> FM a -> Int
count :: forall a. Int -> FM a -> Int
count = Int -> FM a -> Int
forall (m :: * -> *) k a. AssocX m k => k -> m a -> Int
countUsingMember

lookupAll :: S.Sequence seq => Int -> FM a -> seq a
lookupAll :: forall (seq :: * -> *) a. Sequence seq => Int -> FM a -> seq a
lookupAll = Int -> FM a -> seq a
forall (m :: * -> *) k (seq :: * -> *) a.
(AssocX m k, Sequence seq) =>
k -> m a -> seq a
lookupAllUsingLookupM

lookupWithDefault :: a -> Int -> FM a -> a
lookupWithDefault :: forall a. a -> Int -> FM a -> a
lookupWithDefault = a -> Int -> FM a -> a
forall (m :: * -> *) k a. AssocX m k => a -> k -> m a -> a
lookupWithDefaultUsingLookupM

elements :: S.Sequence seq => FM a -> seq a
elements :: forall (seq :: * -> *) a. Sequence seq => FM a -> seq a
elements = FM a -> seq a
forall (m :: * -> *) k (seq :: * -> *) a.
(AssocX m k, Sequence seq) =>
m a -> seq a
elementsUsingFold

fromSeqWithKey ::
    S.Sequence seq => (Int -> a -> a -> a) -> seq (Int,a) -> FM a
fromSeqWithKey :: forall (seq :: * -> *) a.
Sequence seq =>
(Int -> a -> a -> a) -> seq (Int, a) -> FM a
fromSeqWithKey = (Int -> a -> a -> a) -> seq (Int, a) -> FM a
forall (m :: * -> *) k (seq :: * -> *) a.
(FiniteMapX m k, Sequence seq) =>
(k -> a -> a -> a) -> seq (k, a) -> m a
fromSeqWithKeyUsingInsertSeqWithKey

insertWithKey :: (Int -> a -> a -> a) -> Int -> a -> FM a -> FM a
insertWithKey :: forall a. (Int -> a -> a -> a) -> Int -> a -> FM a -> FM a
insertWithKey = (Int -> a -> a -> a) -> Int -> a -> FM a -> FM a
forall (m :: * -> *) k a.
FiniteMapX m k =>
(k -> a -> a -> a) -> k -> a -> m a -> m a
insertWithKeyUsingInsertWith

insertSeqWith ::
    S.Sequence seq => (a -> a -> a) -> seq (Int,a) -> FM a -> FM a
insertSeqWith :: forall (seq :: * -> *) a.
Sequence seq =>
(a -> a -> a) -> seq (Int, a) -> FM a -> FM a
insertSeqWith = (a -> a -> a) -> seq (Int, a) -> FM a -> FM a
forall (m :: * -> *) k (seq :: * -> *) a.
(FiniteMapX m k, Sequence seq) =>
(a -> a -> a) -> seq (k, a) -> m a -> m a
insertSeqWithUsingInsertWith

insertSeqWithKey ::
    S.Sequence seq =>
      (Int -> a -> a -> a) -> seq (Int,a) -> FM a -> FM a
insertSeqWithKey :: forall (seq :: * -> *) a.
Sequence seq =>
(Int -> a -> a -> a) -> seq (Int, a) -> FM a -> FM a
insertSeqWithKey = (Int -> a -> a -> a) -> seq (Int, a) -> FM a -> FM a
forall (m :: * -> *) k (seq :: * -> *) a.
(FiniteMapX m k, Sequence seq) =>
(k -> a -> a -> a) -> seq (k, a) -> m a -> m a
insertSeqWithKeyUsingInsertWithKey

adjustAll :: (a -> a) -> Int -> FM a -> FM a
adjustAll :: forall a. (a -> a) -> Int -> FM a -> FM a
adjustAll = (a -> a) -> Int -> FM a -> FM a
forall a. (a -> a) -> Int -> FM a -> FM a
adjust

unionSeqWith :: S.Sequence seq => (a -> a -> a) -> seq (FM a) -> FM a
unionSeqWith :: forall (seq :: * -> *) a.
Sequence seq =>
(a -> a -> a) -> seq (FM a) -> FM a
unionSeqWith = (a -> a -> a) -> seq (FM a) -> FM a
forall (m :: * -> *) k (seq :: * -> *) a.
(FiniteMapX m k, Sequence seq) =>
(a -> a -> a) -> seq (m a) -> m a
unionSeqWithUsingReduce

toSeq :: S.Sequence seq => FM a -> seq (Int,a)
toSeq :: forall (seq :: * -> *) a. Sequence seq => FM a -> seq (Int, a)
toSeq = FM a -> seq (Int, a)
forall (m :: * -> *) k (seq :: * -> *) a.
(Assoc m k, Sequence seq) =>
m a -> seq (k, a)
toSeqUsingFoldWithKey

keys :: S.Sequence seq => FM a -> seq Int
keys :: forall (seq :: * -> *) a. Sequence seq => FM a -> seq Int
keys = FM a -> seq Int
forall (m :: * -> *) k (seq :: * -> *) a.
(Assoc m k, Sequence seq) =>
m a -> seq k
keysUsingFoldWithKey

unionSeqWithKey ::
    S.Sequence seq => (Int -> a -> a -> a) -> seq (FM a) -> FM a
unionSeqWithKey :: forall (seq :: * -> *) a.
Sequence seq =>
(Int -> a -> a -> a) -> seq (FM a) -> FM a
unionSeqWithKey = (Int -> a -> a -> a) -> seq (FM a) -> FM a
forall (m :: * -> *) k (seq :: * -> *) a.
(FiniteMap m k, Sequence seq) =>
(k -> a -> a -> a) -> seq (m a) -> m a
unionSeqWithKeyUsingReduce

-- instance declarations

instance A.AssocX FM Int where
  {empty :: forall a. FM a
empty = FM a
forall a. FM a
empty; singleton :: forall a. Int -> a -> FM a
singleton = Int -> a -> FM a
forall a. Int -> a -> FM a
singleton; fromSeq :: forall (seq :: * -> *) a. Sequence seq => seq (Int, a) -> FM a
fromSeq = seq (Int, a) -> FM a
forall (seq :: * -> *) a. Sequence seq => seq (Int, a) -> FM a
fromSeq; insert :: forall a. Int -> a -> FM a -> FM a
insert = Int -> a -> FM a -> FM a
forall a. Int -> a -> FM a -> FM a
insert;
   insertSeq :: forall (seq :: * -> *) a.
Sequence seq =>
seq (Int, a) -> FM a -> FM a
insertSeq = seq (Int, a) -> FM a -> FM a
forall (seq :: * -> *) a.
Sequence seq =>
seq (Int, a) -> FM a -> FM a
insertSeq; union :: forall a. FM a -> FM a -> FM a
union = FM a -> FM a -> FM a
forall a. FM a -> FM a -> FM a
union; unionSeq :: forall (seq :: * -> *) a. Sequence seq => seq (FM a) -> FM a
unionSeq = seq (FM a) -> FM a
forall (seq :: * -> *) a. Sequence seq => seq (FM a) -> FM a
unionSeq;
   delete :: forall a. Int -> FM a -> FM a
delete = Int -> FM a -> FM a
forall a. Int -> FM a -> FM a
delete; deleteAll :: forall a. Int -> FM a -> FM a
deleteAll = Int -> FM a -> FM a
forall a. Int -> FM a -> FM a
deleteAll; deleteSeq :: forall (seq :: * -> *) a. Sequence seq => seq Int -> FM a -> FM a
deleteSeq = seq Int -> FM a -> FM a
forall (seq :: * -> *) a. Sequence seq => seq Int -> FM a -> FM a
deleteSeq;
   null :: forall a. FM a -> Bool
null = FM a -> Bool
forall a. FM a -> Bool
null; size :: forall a. FM a -> Int
size = FM a -> Int
forall a. FM a -> Int
size; member :: forall a. Int -> FM a -> Bool
member = Int -> FM a -> Bool
forall a. Int -> FM a -> Bool
member; count :: forall a. Int -> FM a -> Int
count = Int -> FM a -> Int
forall a. Int -> FM a -> Int
count;
   lookup :: forall a. Int -> FM a -> a
lookup = Int -> FM a -> a
forall a. Int -> FM a -> a
lookup; lookupM :: forall (rm :: * -> *) a. MonadFail rm => Int -> FM a -> rm a
lookupM = Int -> FM a -> rm a
forall (rm :: * -> *) a. MonadFail rm => Int -> FM a -> rm a
lookupM; lookupAll :: forall (seq :: * -> *) a. Sequence seq => Int -> FM a -> seq a
lookupAll = Int -> FM a -> seq a
forall (seq :: * -> *) a. Sequence seq => Int -> FM a -> seq a
lookupAll;
   lookupAndDelete :: forall a. Int -> FM a -> (a, FM a)
lookupAndDelete = Int -> FM a -> (a, FM a)
forall a. Int -> FM a -> (a, FM a)
lookupAndDelete; lookupAndDeleteM :: forall (m :: * -> *) a. MonadFail m => Int -> FM a -> m (a, FM a)
lookupAndDeleteM = Int -> FM a -> rm (a, FM a)
forall (m :: * -> *) a. MonadFail m => Int -> FM a -> m (a, FM a)
lookupAndDeleteM;
   lookupAndDeleteAll :: forall (seq :: * -> *) a.
Sequence seq =>
Int -> FM a -> (seq a, FM a)
lookupAndDeleteAll = Int -> FM a -> (seq a, FM a)
forall (seq :: * -> *) a.
Sequence seq =>
Int -> FM a -> (seq a, FM a)
lookupAndDeleteAll;
   lookupWithDefault :: forall a. a -> Int -> FM a -> a
lookupWithDefault = a -> Int -> FM a -> a
forall a. a -> Int -> FM a -> a
lookupWithDefault; adjust :: forall a. (a -> a) -> Int -> FM a -> FM a
adjust = (a -> a) -> Int -> FM a -> FM a
forall a. (a -> a) -> Int -> FM a -> FM a
adjust;
   adjustAll :: forall a. (a -> a) -> Int -> FM a -> FM a
adjustAll = (a -> a) -> Int -> FM a -> FM a
forall a. (a -> a) -> Int -> FM a -> FM a
adjustAll; adjustOrInsert :: forall a. (a -> a) -> a -> Int -> FM a -> FM a
adjustOrInsert = (a -> a) -> a -> Int -> FM a -> FM a
forall a. (a -> a) -> a -> Int -> FM a -> FM a
adjustOrInsert;
   adjustAllOrInsert :: forall a. (a -> a) -> a -> Int -> FM a -> FM a
adjustAllOrInsert = (a -> a) -> a -> Int -> FM a -> FM a
forall a. (a -> a) -> a -> Int -> FM a -> FM a
adjustAllOrInsert;
   adjustOrDelete :: forall a. (a -> Maybe a) -> Int -> FM a -> FM a
adjustOrDelete = (a -> Maybe a) -> Int -> FM a -> FM a
forall a. (a -> Maybe a) -> Int -> FM a -> FM a
adjustOrDelete; adjustOrDeleteAll :: forall a. (a -> Maybe a) -> Int -> FM a -> FM a
adjustOrDeleteAll = (a -> Maybe a) -> Int -> FM a -> FM a
forall a. (a -> Maybe a) -> Int -> FM a -> FM a
adjustOrDeleteAll;
   fold :: forall a b. (a -> b -> b) -> b -> FM a -> b
fold = (a -> b -> b) -> b -> FM a -> b
forall a b. (a -> b -> b) -> b -> FM a -> b
fold; fold' :: forall a b. (a -> b -> b) -> b -> FM a -> b
fold' = (a -> b -> b) -> b -> FM a -> b
forall a b. (a -> b -> b) -> b -> FM a -> b
fold'; fold1 :: forall a. (a -> a -> a) -> FM a -> a
fold1 = (a -> a -> a) -> FM a -> a
forall a. (a -> a -> a) -> FM a -> a
fold1; fold1' :: forall a. (a -> a -> a) -> FM a -> a
fold1' = (a -> a -> a) -> FM a -> a
forall a. (a -> a -> a) -> FM a -> a
fold1';
   filter :: forall a. (a -> Bool) -> FM a -> FM a
filter = (a -> Bool) -> FM a -> FM a
forall a. (a -> Bool) -> FM a -> FM a
filter; partition :: forall a. (a -> Bool) -> FM a -> (FM a, FM a)
partition = (a -> Bool) -> FM a -> (FM a, FM a)
forall a. (a -> Bool) -> FM a -> (FM a, FM a)
partition; elements :: forall (seq :: * -> *) a. Sequence seq => FM a -> seq a
elements = FM a -> seq a
forall (seq :: * -> *) a. Sequence seq => FM a -> seq a
elements;
   strict :: forall a. FM a -> FM a
strict = FM a -> FM a
forall t. t -> t
strict; strictWith :: forall t a. (t -> a) -> FM t -> FM t
strictWith = (a -> b) -> FM a -> FM a
forall t a. (t -> a) -> FM t -> FM t
strictWith;
   structuralInvariant :: forall a. FM a -> Bool
structuralInvariant = FM a -> Bool
forall a. FM a -> Bool
structuralInvariant; instanceName :: forall a. FM a -> String
instanceName FM a
_ = String
moduleName}

instance A.Assoc FM Int where
  {toSeq :: forall (seq :: * -> *) a. Sequence seq => FM a -> seq (Int, a)
toSeq = FM a -> seq (Int, a)
forall (seq :: * -> *) a. Sequence seq => FM a -> seq (Int, a)
toSeq; keys :: forall (seq :: * -> *) a. Sequence seq => FM a -> seq Int
keys = FM a -> seq Int
forall (seq :: * -> *) a. Sequence seq => FM a -> seq Int
keys; mapWithKey :: forall a b. (Int -> a -> b) -> FM a -> FM b
mapWithKey = (Int -> a -> b) -> FM a -> FM b
forall a b. (Int -> a -> b) -> FM a -> FM b
mapWithKey;
   foldWithKey :: forall a b. (Int -> a -> b -> b) -> b -> FM a -> b
foldWithKey = (Int -> a -> b -> b) -> b -> FM a -> b
forall a b. (Int -> a -> b -> b) -> b -> FM a -> b
foldWithKey; foldWithKey' :: forall a b. (Int -> a -> b -> b) -> b -> FM a -> b
foldWithKey' = (Int -> a -> b -> b) -> b -> FM a -> b
forall a b. (Int -> a -> b -> b) -> b -> FM a -> b
foldWithKey';
   filterWithKey :: forall a. (Int -> a -> Bool) -> FM a -> FM a
filterWithKey = (Int -> a -> Bool) -> FM a -> FM a
forall a. (Int -> a -> Bool) -> FM a -> FM a
filterWithKey;
   partitionWithKey :: forall a. (Int -> a -> Bool) -> FM a -> (FM a, FM a)
partitionWithKey = (Int -> a -> Bool) -> FM a -> (FM a, FM a)
forall a. (Int -> a -> Bool) -> FM a -> (FM a, FM a)
partitionWithKey}

instance A.FiniteMapX FM Int where
  {fromSeqWith :: forall (seq :: * -> *) a.
Sequence seq =>
(a -> a -> a) -> seq (Int, a) -> FM a
fromSeqWith = (a -> a -> a) -> seq (Int, a) -> FM a
forall (seq :: * -> *) a.
Sequence seq =>
(a -> a -> a) -> seq (Int, a) -> FM a
fromSeqWith; fromSeqWithKey :: forall (seq :: * -> *) a.
Sequence seq =>
(Int -> a -> a -> a) -> seq (Int, a) -> FM a
fromSeqWithKey = (Int -> a -> a -> a) -> seq (Int, a) -> FM a
forall (seq :: * -> *) a.
Sequence seq =>
(Int -> a -> a -> a) -> seq (Int, a) -> FM a
fromSeqWithKey;
   insertWith :: forall a. (a -> a -> a) -> Int -> a -> FM a -> FM a
insertWith = (a -> a -> a) -> Int -> a -> FM a -> FM a
forall a. (a -> a -> a) -> Int -> a -> FM a -> FM a
insertWith; insertWithKey :: forall a. (Int -> a -> a -> a) -> Int -> a -> FM a -> FM a
insertWithKey = (Int -> a -> a -> a) -> Int -> a -> FM a -> FM a
forall a. (Int -> a -> a -> a) -> Int -> a -> FM a -> FM a
insertWithKey;
   insertSeqWith :: forall (seq :: * -> *) a.
Sequence seq =>
(a -> a -> a) -> seq (Int, a) -> FM a -> FM a
insertSeqWith = (a -> a -> a) -> seq (Int, a) -> FM a -> FM a
forall (seq :: * -> *) a.
Sequence seq =>
(a -> a -> a) -> seq (Int, a) -> FM a -> FM a
insertSeqWith; insertSeqWithKey :: forall (seq :: * -> *) a.
Sequence seq =>
(Int -> a -> a -> a) -> seq (Int, a) -> FM a -> FM a
insertSeqWithKey = (Int -> a -> a -> a) -> seq (Int, a) -> FM a -> FM a
forall (seq :: * -> *) a.
Sequence seq =>
(Int -> a -> a -> a) -> seq (Int, a) -> FM a -> FM a
insertSeqWithKey;
   unionl :: forall a. FM a -> FM a -> FM a
unionl = FM a -> FM a -> FM a
forall a. FM a -> FM a -> FM a
unionl; unionr :: forall a. FM a -> FM a -> FM a
unionr = FM a -> FM a -> FM a
forall a. FM a -> FM a -> FM a
unionr; unionWith :: forall a. (a -> a -> a) -> FM a -> FM a -> FM a
unionWith = (a -> a -> a) -> FM a -> FM a -> FM a
forall a. (a -> a -> a) -> FM a -> FM a -> FM a
unionWith;
   unionSeqWith :: forall (seq :: * -> *) a.
Sequence seq =>
(a -> a -> a) -> seq (FM a) -> FM a
unionSeqWith = (a -> a -> a) -> seq (FM a) -> FM a
forall (seq :: * -> *) a.
Sequence seq =>
(a -> a -> a) -> seq (FM a) -> FM a
unionSeqWith; intersectionWith :: forall a b c. (a -> b -> c) -> FM a -> FM b -> FM c
intersectionWith = (a -> b -> c) -> FM a -> FM b -> FM c
forall a b c. (a -> b -> c) -> FM a -> FM b -> FM c
intersectionWith;
   difference :: forall a b. FM a -> FM b -> FM a
difference = FM a -> FM b -> FM a
forall a b. FM a -> FM b -> FM a
difference; properSubset :: forall a b. FM a -> FM b -> Bool
properSubset = FM a -> FM b -> Bool
forall a b. FM a -> FM b -> Bool
properSubset; subset :: forall a b. FM a -> FM b -> Bool
subset = FM a -> FM b -> Bool
forall a b. FM a -> FM b -> Bool
subset;
   properSubmapBy :: forall a. (a -> a -> Bool) -> FM a -> FM a -> Bool
properSubmapBy = (a -> a -> Bool) -> FM a -> FM a -> Bool
forall a. (a -> a -> Bool) -> FM a -> FM a -> Bool
properSubmapBy; submapBy :: forall a. (a -> a -> Bool) -> FM a -> FM a -> Bool
submapBy = (a -> a -> Bool) -> FM a -> FM a -> Bool
forall a. (a -> a -> Bool) -> FM a -> FM a -> Bool
submapBy;
   sameMapBy :: forall a. (a -> a -> Bool) -> FM a -> FM a -> Bool
sameMapBy = (a -> a -> Bool) -> FM a -> FM a -> Bool
forall a. (a -> a -> Bool) -> FM a -> FM a -> Bool
sameMapBy}

instance A.FiniteMap FM Int where
  {unionWithKey :: forall a. (Int -> a -> a -> a) -> FM a -> FM a -> FM a
unionWithKey = (Int -> a -> a -> a) -> FM a -> FM a -> FM a
forall a. (Int -> a -> a -> a) -> FM a -> FM a -> FM a
unionWithKey; unionSeqWithKey :: forall (seq :: * -> *) a.
Sequence seq =>
(Int -> a -> a -> a) -> seq (FM a) -> FM a
unionSeqWithKey = (Int -> a -> a -> a) -> seq (FM a) -> FM a
forall (seq :: * -> *) a.
Sequence seq =>
(Int -> a -> a -> a) -> seq (FM a) -> FM a
unionSeqWithKey;
   intersectionWithKey :: forall a b c. (Int -> a -> b -> c) -> FM a -> FM b -> FM c
intersectionWithKey = (Int -> a -> b -> c) -> FM a -> FM b -> FM c
forall a b c. (Int -> a -> b -> c) -> FM a -> FM b -> FM c
intersectionWithKey}

instance A.OrdAssocX FM Int where
  {minView :: forall (m :: * -> *) a. MonadFail m => FM a -> m (a, FM a)
minView = FM a -> rm (a, FM a)
forall (m :: * -> *) a. MonadFail m => FM a -> m (a, FM a)
minView; minElem :: forall a. FM a -> a
minElem = FM a -> a
forall a. FM a -> a
minElem; deleteMin :: forall a. FM a -> FM a
deleteMin = FM a -> FM a
forall a. FM a -> FM a
deleteMin;
   unsafeInsertMin :: forall a. Int -> a -> FM a -> FM a
unsafeInsertMin = Int -> a -> FM a -> FM a
forall a. Int -> a -> FM a -> FM a
unsafeInsertMin; maxView :: forall (m :: * -> *) a. MonadFail m => FM a -> m (a, FM a)
maxView = FM a -> rm (a, FM a)
forall (m :: * -> *) a. MonadFail m => FM a -> m (a, FM a)
maxView; maxElem :: forall a. FM a -> a
maxElem = FM a -> a
forall a. FM a -> a
maxElem;
   deleteMax :: forall a. FM a -> FM a
deleteMax = FM a -> FM a
forall a. FM a -> FM a
deleteMax; unsafeInsertMax :: forall a. Int -> a -> FM a -> FM a
unsafeInsertMax = Int -> a -> FM a -> FM a
forall a. Int -> a -> FM a -> FM a
unsafeInsertMax;
   foldr :: forall a b. (a -> b -> b) -> b -> FM a -> b
foldr = (a -> b -> b) -> b -> FM a -> b
forall a b. (a -> b -> b) -> b -> FM a -> b
foldr; foldr' :: forall a b. (a -> b -> b) -> b -> FM a -> b
foldr' = (a -> b -> b) -> b -> FM a -> b
forall a b. (a -> b -> b) -> b -> FM a -> b
foldr'; foldl :: forall b a. (b -> a -> b) -> b -> FM a -> b
foldl = (b -> a -> b) -> b -> FM a -> b
forall b a. (b -> a -> b) -> b -> FM a -> b
foldl; foldl' :: forall b a. (b -> a -> b) -> b -> FM a -> b
foldl' = (b -> a -> b) -> b -> FM a -> b
forall b a. (b -> a -> b) -> b -> FM a -> b
foldl';
   foldr1 :: forall a. (a -> a -> a) -> FM a -> a
foldr1 = (a -> a -> a) -> FM a -> a
forall a. (a -> a -> a) -> FM a -> a
foldr1; foldr1' :: forall a. (a -> a -> a) -> FM a -> a
foldr1' = (a -> a -> a) -> FM a -> a
forall a. (a -> a -> a) -> FM a -> a
foldr1'; foldl1 :: forall a. (a -> a -> a) -> FM a -> a
foldl1 = (a -> a -> a) -> FM a -> a
forall a. (a -> a -> a) -> FM a -> a
foldl1; foldl1' :: forall a. (a -> a -> a) -> FM a -> a
foldl1' = (a -> a -> a) -> FM a -> a
forall a. (a -> a -> a) -> FM a -> a
foldl1';
   unsafeFromOrdSeq :: forall (seq :: * -> *) a. Sequence seq => seq (Int, a) -> FM a
unsafeFromOrdSeq = seq (Int, a) -> FM a
forall (seq :: * -> *) a. Sequence seq => seq (Int, a) -> FM a
unsafeFromOrdSeq; unsafeAppend :: forall a. FM a -> FM a -> FM a
unsafeAppend = FM a -> FM a -> FM a
forall a. FM a -> FM a -> FM a
unsafeAppend;
   filterLT :: forall a. Int -> FM a -> FM a
filterLT = Int -> FM a -> FM a
forall a. Int -> FM a -> FM a
filterLT; filterGT :: forall a. Int -> FM a -> FM a
filterGT = Int -> FM a -> FM a
forall a. Int -> FM a -> FM a
filterGT; filterLE :: forall a. Int -> FM a -> FM a
filterLE = Int -> FM a -> FM a
forall a. Int -> FM a -> FM a
filterLE;
   filterGE :: forall a. Int -> FM a -> FM a
filterGE = Int -> FM a -> FM a
forall a. Int -> FM a -> FM a
filterGE; partitionLT_GE :: forall a. Int -> FM a -> (FM a, FM a)
partitionLT_GE = Int -> FM a -> (FM a, FM a)
forall a. Int -> FM a -> (FM a, FM a)
partitionLT_GE;
   partitionLE_GT :: forall a. Int -> FM a -> (FM a, FM a)
partitionLE_GT = Int -> FM a -> (FM a, FM a)
forall a. Int -> FM a -> (FM a, FM a)
partitionLE_GT; partitionLT_GT :: forall a. Int -> FM a -> (FM a, FM a)
partitionLT_GT = Int -> FM a -> (FM a, FM a)
forall a. Int -> FM a -> (FM a, FM a)
partitionLT_GT}

instance A.OrdAssoc FM Int where
  {minViewWithKey :: forall (m :: * -> *) a. MonadFail m => FM a -> m ((Int, a), FM a)
minViewWithKey = FM a -> rm ((Int, a), FM a)
forall (m :: * -> *) a. MonadFail m => FM a -> m ((Int, a), FM a)
minViewWithKey; minElemWithKey :: forall a. FM a -> (Int, a)
minElemWithKey = FM a -> (Int, a)
forall a. FM a -> (Int, a)
minElemWithKey;
   maxViewWithKey :: forall (m :: * -> *) a. MonadFail m => FM a -> m ((Int, a), FM a)
maxViewWithKey = FM a -> rm ((Int, a), FM a)
forall (m :: * -> *) a. MonadFail m => FM a -> m ((Int, a), FM a)
maxViewWithKey; maxElemWithKey :: forall a. FM a -> (Int, a)
maxElemWithKey = FM a -> (Int, a)
forall a. FM a -> (Int, a)
maxElemWithKey;
   foldrWithKey :: forall a b. (Int -> a -> b -> b) -> b -> FM a -> b
foldrWithKey = (Int -> a -> b -> b) -> b -> FM a -> b
forall a b. (Int -> a -> b -> b) -> b -> FM a -> b
foldrWithKey; foldrWithKey' :: forall a b. (Int -> a -> b -> b) -> b -> FM a -> b
foldrWithKey' = (Int -> a -> b -> b) -> b -> FM a -> b
forall a b. (Int -> a -> b -> b) -> b -> FM a -> b
foldrWithKey';
   foldlWithKey :: forall b a. (b -> Int -> a -> b) -> b -> FM a -> b
foldlWithKey = (b -> Int -> a -> b) -> b -> FM a -> b
forall b a. (b -> Int -> a -> b) -> b -> FM a -> b
foldlWithKey; foldlWithKey' :: forall b a. (b -> Int -> a -> b) -> b -> FM a -> b
foldlWithKey' = (b -> Int -> a -> b) -> b -> FM a -> b
forall b a. (b -> Int -> a -> b) -> b -> FM a -> b
foldlWithKey';
   toOrdSeq :: forall (seq :: * -> *) a. Sequence seq => FM a -> seq (Int, a)
toOrdSeq = FM a -> seq (Int, a)
forall (seq :: * -> *) a. Sequence seq => FM a -> seq (Int, a)
toOrdSeq}

instance A.OrdFiniteMapX FM Int
instance A.OrdFiniteMap FM Int

instance Functor FM where
  fmap :: forall a b. (a -> b) -> FM a -> FM b
fmap = (a -> b) -> FM a -> FM b
forall a b. (a -> b) -> FM a -> FM b
map

instance (Show a) => Show (FM a) where
  showsPrec :: Int -> FM a -> String -> String
showsPrec = Int -> FM a -> String -> String
forall k a (m :: * -> *).
(Show k, Show a, Assoc m k) =>
Int -> m a -> String -> String
showsPrecUsingToList

instance (Read a) => Read (FM a) where
  readsPrec :: Int -> ReadS (FM a)
readsPrec = Int -> ReadS (FM a)
forall k a (m :: * -> *).
(Read k, Read a, AssocX m k) =>
Int -> ReadS (m a)
readsPrecUsingFromList

instance (Eq a) => Eq (FM a) where
  == :: FM a -> FM a -> Bool
(==) = FM a -> FM a -> Bool
forall a. Eq a => FM a -> FM a -> Bool
sameMap

instance (Ord a) => Ord (FM a) where
  compare :: FM a -> FM a -> Ordering
compare = FM a -> FM a -> Ordering
forall a (m :: * -> *) k.
(Ord a, OrdAssoc m k) =>
m a -> m a -> Ordering
compareUsingToOrdList

instance (Arbitrary a) => Arbitrary (FM a) where
   arbitrary :: Gen (FM a)
arbitrary = do ([(Int, a)]
xs::[(Int,a)]) <- Gen [(Int, a)]
forall a. Arbitrary a => Gen a
arbitrary
                  FM a -> Gen (FM a)
forall a. a -> Gen a
forall (m :: * -> *) a. Monad m => a -> m a
return (((Int, a) -> FM a -> FM a) -> FM a -> [(Int, a)] -> FM a
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Prelude.foldr ((Int -> a -> FM a -> FM a) -> (Int, a) -> FM a -> FM a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry Int -> a -> FM a -> FM a
forall a. Int -> a -> FM a -> FM a
insert) FM a
forall a. FM a
empty [(Int, a)]
xs)

instance (CoArbitrary a) => CoArbitrary (FM a) where
   coarbitrary :: forall b. FM a -> Gen b -> Gen b
coarbitrary FM a
E = Integer -> Gen b -> Gen b
forall n a. Integral n => n -> Gen a -> Gen a
variant Integer
0
   coarbitrary (L Int
i a
a) = Integer -> Gen b -> Gen b
forall n a. Integral n => n -> Gen a -> Gen a
variant Integer
1 (Gen b -> Gen b) -> (Gen b -> Gen b) -> Gen b -> Gen b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Gen b -> Gen b
forall b. Int -> Gen b -> Gen b
forall a b. CoArbitrary a => a -> Gen b -> Gen b
coarbitrary Int
i (Gen b -> Gen b) -> (Gen b -> Gen b) -> Gen b -> Gen b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Gen b -> Gen b
forall b. a -> Gen b -> Gen b
forall a b. CoArbitrary a => a -> Gen b -> Gen b
coarbitrary a
a
   coarbitrary (B Int
i Int
j FM a
m FM a
n) = Integer -> Gen b -> Gen b
forall n a. Integral n => n -> Gen a -> Gen a
variant Integer
2 (Gen b -> Gen b) -> (Gen b -> Gen b) -> Gen b -> Gen b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Gen b -> Gen b
forall b. Int -> Gen b -> Gen b
forall a b. CoArbitrary a => a -> Gen b -> Gen b
coarbitrary Int
i (Gen b -> Gen b) -> (Gen b -> Gen b) -> Gen b -> Gen b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Gen b -> Gen b
forall b. Int -> Gen b -> Gen b
forall a b. CoArbitrary a => a -> Gen b -> Gen b
coarbitrary Int
j
                           (Gen b -> Gen b) -> (Gen b -> Gen b) -> Gen b -> Gen b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FM a -> Gen b -> Gen b
forall a b. CoArbitrary a => a -> Gen b -> Gen b
forall b. FM a -> Gen b -> Gen b
coarbitrary FM a
m (Gen b -> Gen b) -> (Gen b -> Gen b) -> Gen b -> Gen b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FM a -> Gen b -> Gen b
forall a b. CoArbitrary a => a -> Gen b -> Gen b
forall b. FM a -> Gen b -> Gen b
coarbitrary FM a
n


instance Semigroup (FM a) where
   <> :: FM a -> FM a -> FM a
(<>) = FM a -> FM a -> FM a
forall a. FM a -> FM a -> FM a
union
instance Monoid (FM a) where
   mempty :: FM a
mempty  = FM a
forall a. FM a
empty
   mappend :: FM a -> FM a -> FM a
mappend = FM a -> FM a -> FM a
forall a. Semigroup a => a -> a -> a
(SG.<>)
   mconcat :: [FM a] -> FM a
mconcat = [FM a] -> FM a
forall (seq :: * -> *) a. Sequence seq => seq (FM a) -> FM a
unionSeq