-- |
--   Module      :  Data.Edison.Assoc.TernaryTrie
--   Copyright   :  Copyright (c) 2002, 2008 Andrew Bromage
--   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 ternary search tries

module Data.Edison.Assoc.TernaryTrie (
    -- * Type of ternary search tries
    FM,

    -- * AssocX operations
    empty,singleton,fromSeq,insert,insertSeq,union,unionSeq,delete,deleteAll,
    deleteSeq,null,size,member,count,lookup,lookupM,lookupAll,
    lookupAndDelete,lookupAndDeleteM,lookupAndDeleteAll,
    lookupWithDefault,adjust,adjustAll,adjustOrInsert,adjustAllOrInsert,
    adjustOrDelete,adjustOrDeleteAll,strict,strictWith,
    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,

    -- * Other supported operations
    mergeVFM, mergeKVFM,

    -- * Documentation
    moduleName
) where

import Prelude hiding (null,map,lookup,foldr,foldl,foldr1,foldl1,foldl',filter)
import qualified Prelude
import qualified Data.Edison.Assoc as A
import Data.Edison.Prelude ( runFail_ )
import qualified Data.Edison.Seq as S
import qualified Data.List as L
import qualified Control.Monad.Fail as Fail
import Control.Monad
import Data.Monoid
import Data.Semigroup as SG
import Data.Maybe (isNothing)

import Data.Edison.Assoc.Defaults
import Test.QuickCheck (Arbitrary(..), CoArbitrary(..), Gen(), variant)


-- signatures for exported functions
moduleName    :: String
empty         :: Ord k => FM k a
singleton     :: Ord k => [k] -> a -> FM k a
fromSeq       :: (Ord k,S.Sequence seq) => seq ([k],a) -> FM k a
insert        :: Ord k => [k] -> a -> FM k a -> FM k a
insertSeq     :: (Ord k,S.Sequence seq) => seq ([k],a) -> FM k a -> FM k a
union         :: Ord k => FM k a -> FM k a -> FM k a
unionSeq      :: (Ord k,S.Sequence seq) => seq (FM k a) -> FM k a
delete        :: Ord k => [k] -> FM k a -> FM k a
deleteAll     :: Ord k => [k] -> FM k a -> FM k a
deleteSeq     :: (Ord k,S.Sequence seq) => seq [k] -> FM k a -> FM k a
null          :: Ord k => FM k a -> Bool
size          :: Ord k => FM k a -> Int
member        :: Ord k => [k] -> FM k a -> Bool
count         :: Ord k => [k] -> FM k a -> Int
lookup        :: Ord k => [k] -> FM k a -> a
lookupM       :: (Ord k, Fail.MonadFail rm) => [k] -> FM k a -> rm a
lookupAll     :: (Ord k,S.Sequence seq) => [k] -> FM k a -> seq a
lookupAndDelete    :: Ord k => [k] -> FM k a -> (a, FM k a)
lookupAndDeleteM   :: (Ord k, Fail.MonadFail rm) => [k] -> FM k a -> rm (a, FM k a)
lookupAndDeleteAll :: (Ord k, S.Sequence seq) => [k] -> FM k a -> (seq a,FM k a)
lookupWithDefault  :: Ord k => a -> [k] -> FM k a -> a
adjust        :: Ord k => (a -> a) -> [k] -> FM k a -> FM k a
adjustAll     :: Ord k => (a -> a) -> [k] -> FM k a -> FM k a
adjustOrInsert    :: Ord k => (a -> a) -> a -> [k] -> FM k a -> FM k a
adjustAllOrInsert :: Ord k => (a -> a) -> a -> [k] -> FM k a -> FM k a
adjustOrDelete    :: Ord k => (a -> Maybe a) -> [k] -> FM k a -> FM k a
adjustOrDeleteAll :: Ord k => (a -> Maybe a) -> [k] -> FM k a -> FM k a
strict            :: FM k a -> FM k a
strictWith        :: (a -> b) -> FM k a -> FM k a
map           :: Ord k => (a -> b) -> FM k a -> FM k b
fold          :: Ord k => (a -> b -> b) -> b -> FM k a -> b
fold1         :: Ord k => (a -> a -> a) -> FM k a -> a
fold'         :: Ord k => (a -> b -> b) -> b -> FM k a -> b
fold1'        :: Ord k => (a -> a -> a) -> FM k a -> a
filter        :: Ord k => (a -> Bool) -> FM k a -> FM k a
partition     :: Ord k => (a -> Bool) -> FM k a -> (FM k a, FM k a)
elements      :: (Ord k,S.Sequence seq) => FM k a -> seq a

fromSeqWith      :: (Ord k,S.Sequence seq) =>
                        (a -> a -> a) -> seq ([k],a) -> FM k a
fromSeqWithKey   :: (Ord k,S.Sequence seq) => ([k] -> a -> a -> a) -> seq ([k],a) -> FM k a
insertWith       :: Ord k => (a -> a -> a) -> [k] -> a -> FM k a -> FM k a
insertWithKey    :: Ord k => ([k] -> a -> a -> a) -> [k] -> a -> FM k a -> FM k a
insertSeqWith    :: (Ord k,S.Sequence seq) =>
                        (a -> a -> a) -> seq ([k],a) -> FM k a -> FM k a
insertSeqWithKey :: (Ord k,S.Sequence seq) =>
                        ([k] -> a -> a -> a) -> seq ([k],a) -> FM k a -> FM k a
unionl           :: Ord k => FM k a -> FM k a -> FM k a
unionr           :: Ord k => FM k a -> FM k a -> FM k a
unionWith        :: Ord k => (a -> a -> a) -> FM k a -> FM k a -> FM k a
unionSeqWith     :: (Ord k,S.Sequence seq) =>
                        (a -> a -> a) -> seq (FM k a) -> FM k a
intersectionWith :: Ord k => (a -> b -> c) -> FM k a -> FM k b -> FM k c
difference       :: Ord k => FM k a -> FM k b -> FM k a
properSubset     :: Ord k => FM k a -> FM k b -> Bool
subset           :: Ord k => FM k a -> FM k b -> Bool
properSubmapBy   :: Ord k => (a -> a -> Bool) -> FM k a -> FM k a -> Bool
submapBy         :: Ord k => (a -> a -> Bool) -> FM k a -> FM k a -> Bool
sameMapBy        :: Ord k => (a -> a -> Bool) -> FM k a -> FM k a -> Bool
properSubmap     :: (Ord k, Eq a) => FM k a -> FM k a -> Bool
submap           :: (Ord k, Eq a) => FM k a -> FM k a -> Bool
sameMap          :: (Ord k, Eq a) => FM k a -> FM k a -> Bool

toSeq            :: (Ord k,S.Sequence seq) => FM k a -> seq ([k],a)
keys             :: (Ord k,S.Sequence seq) => FM k a -> seq [k]
mapWithKey       :: Ord k => ([k] -> a -> b) -> FM k a -> FM k b
foldWithKey      :: Ord k => ([k] -> a -> b -> b) -> b -> FM k a -> b
foldWithKey'     :: Ord k => ([k] -> a -> b -> b) -> b -> FM k a -> b
filterWithKey    :: Ord k => ([k] -> a -> Bool) -> FM k a -> FM k a
partitionWithKey :: Ord k => ([k] -> a -> Bool) -> FM k a -> (FM k a, FM k a)
unionWithKey     :: Ord k => ([k] -> a -> a -> a) -> FM k a -> FM k a -> FM k a
unionSeqWithKey  :: (Ord k,S.Sequence seq) =>
                       ([k] -> a -> a -> a) -> seq (FM k a) -> FM k a
intersectionWithKey :: Ord k => ([k] -> a -> b -> c) -> FM k a -> FM k b -> FM k c

foldr          :: Ord k => (a -> b -> b) -> b -> FM k a -> b
foldr1         :: Ord k => (a -> a -> a) -> FM k a -> a
foldr'         :: Ord k => (a -> b -> b) -> b -> FM k a -> b
foldr1'        :: Ord k => (a -> a -> a) -> FM k a -> a

foldrWithKey   :: Ord k => ([k] -> a -> b -> b) -> b -> FM k a -> b
foldrWithKey'  :: Ord k => ([k] -> a -> b -> b) -> b -> FM k a -> b
foldlWithKey   :: Ord k => (b -> [k] -> a -> b) -> b -> FM k a -> b
foldlWithKey'  :: Ord k => (b -> [k] -> a -> b) -> b -> FM k a -> b
toOrdSeq       :: (Ord k,S.Sequence seq) => FM k a -> seq ([k],a)

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


data FM k a
  = FM !(Maybe a) !(FMB k a)

data FMB k v
  = E
  | I !Int !k !(Maybe v) !(FMB k v) !(FMB' k v) !(FMB k v)

newtype FMB' k v
  = FMB' (FMB k v)

balance :: Int
balance :: Int
balance = Int
6

sizeFMB :: FMB k v -> Int
sizeFMB :: forall k v. FMB k v -> Int
sizeFMB FMB k v
E = Int
0
sizeFMB (I Int
size k
_ Maybe v
_ FMB k v
_ FMB' k v
_ FMB k v
_) = Int
size

mkFMB :: k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkFMB :: forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkFMB k
k Maybe v
v FMB k v
l FMB' k v
m FMB k v
r
  = Int -> k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
forall k v.
Int -> k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
I (Int
1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ FMB k v -> Int
forall k v. FMB k v -> Int
sizeFMB FMB k v
l Int -> Int -> Int
forall a. Num a => a -> a -> a
+ FMB k v -> Int
forall k v. FMB k v -> Int
sizeFMB FMB k v
r) k
k Maybe v
v FMB k v
l FMB' k v
m FMB k v
r

lookupFMB :: (Ord k) => [k] -> FMB k v -> Maybe v
lookupFMB :: forall k v. Ord k => [k] -> FMB k v -> Maybe v
lookupFMB []        FMB k v
_
  = Maybe v
forall a. Maybe a
Nothing
lookupFMB (k
_:[k]
_) FMB k v
E
  = Maybe v
forall a. Maybe a
Nothing
lookupFMB nk :: [k]
nk@(k
x:[k]
xs) (I Int
_ k
k Maybe v
v FMB k v
l (FMB' FMB k v
fmbm) FMB k v
r)
  = case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
x k
k of
        Ordering
LT -> [k] -> FMB k v -> Maybe v
forall k v. Ord k => [k] -> FMB k v -> Maybe v
lookupFMB [k]
nk FMB k v
l
        Ordering
GT -> [k] -> FMB k v -> Maybe v
forall k v. Ord k => [k] -> FMB k v -> Maybe v
lookupFMB [k]
nk FMB k v
r
        Ordering
EQ -> if [k] -> Bool
forall a. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
L.null [k]
xs then Maybe v
v else [k] -> FMB k v -> Maybe v
forall k v. Ord k => [k] -> FMB k v -> Maybe v
lookupFMB [k]
xs FMB k v
fmbm

listToFMB :: [k] -> (Maybe v -> Maybe v) -> FMB k v
listToFMB :: forall k v. [k] -> (Maybe v -> Maybe v) -> FMB k v
listToFMB [k
x]    Maybe v -> Maybe v
fv = k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkFMB k
x (Maybe v -> Maybe v
fv Maybe v
forall a. Maybe a
Nothing) FMB k v
forall k v. FMB k v
E (FMB k v -> FMB' k v
forall k v. FMB k v -> FMB' k v
FMB' FMB k v
forall k v. FMB k v
E)                 FMB k v
forall k v. FMB k v
E
listToFMB (k
x:[k]
xs) Maybe v -> Maybe v
fv = k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkFMB k
x Maybe v
forall a. Maybe a
Nothing      FMB k v
forall k v. FMB k v
E (FMB k v -> FMB' k v
forall k v. FMB k v -> FMB' k v
FMB' (FMB k v -> FMB' k v) -> FMB k v -> FMB' k v
forall a b. (a -> b) -> a -> b
$ [k] -> (Maybe v -> Maybe v) -> FMB k v
forall k v. [k] -> (Maybe v -> Maybe v) -> FMB k v
listToFMB [k]
xs Maybe v -> Maybe v
fv) FMB k v
forall k v. FMB k v
E
listToFMB [k]
_ Maybe v -> Maybe v
_ = String -> FMB k v
forall a. HasCallStack => String -> a
error String
"TernaryTrie.listToFMB: bug!"

addToFMB :: (Ord k) => [k] -> (Maybe v -> Maybe v) -> FMB k v -> FMB k v
addToFMB :: forall k v.
Ord k =>
[k] -> (Maybe v -> Maybe v) -> FMB k v -> FMB k v
addToFMB [k]
xs Maybe v -> Maybe v
combiner FMB k v
E
  = [k] -> (Maybe v -> Maybe v) -> FMB k v
forall k v. [k] -> (Maybe v -> Maybe v) -> FMB k v
listToFMB [k]
xs Maybe v -> Maybe v
combiner
addToFMB nk :: [k]
nk@(k
x:[k]
xs) Maybe v -> Maybe v
combiner (I Int
size k
k Maybe v
v FMB k v
l m :: FMB' k v
m@(FMB' FMB k v
fmbm) FMB k v
r)
  = case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
x k
k of
        Ordering
LT -> k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkBalancedFMB k
k Maybe v
v ([k] -> (Maybe v -> Maybe v) -> FMB k v -> FMB k v
forall k v.
Ord k =>
[k] -> (Maybe v -> Maybe v) -> FMB k v -> FMB k v
addToFMB [k]
nk Maybe v -> Maybe v
combiner FMB k v
l) FMB' k v
m FMB k v
r
        Ordering
GT -> k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkBalancedFMB k
k Maybe v
v FMB k v
l FMB' k v
m ([k] -> (Maybe v -> Maybe v) -> FMB k v -> FMB k v
forall k v.
Ord k =>
[k] -> (Maybe v -> Maybe v) -> FMB k v -> FMB k v
addToFMB [k]
nk Maybe v -> Maybe v
combiner FMB k v
r)
        Ordering
EQ -> case [k]
xs of
                [] -> Int -> k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
forall k v.
Int -> k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
I Int
size k
k (Maybe v -> Maybe v
combiner Maybe v
v) FMB k v
l FMB' k v
m FMB k v
r
                [k]
_  -> Int -> k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
forall k v.
Int -> k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
I Int
size k
k Maybe v
v FMB k v
l (FMB k v -> FMB' k v
forall k v. FMB k v -> FMB' k v
FMB' (FMB k v -> FMB' k v) -> FMB k v -> FMB' k v
forall a b. (a -> b) -> a -> b
$ [k] -> (Maybe v -> Maybe v) -> FMB k v -> FMB k v
forall k v.
Ord k =>
[k] -> (Maybe v -> Maybe v) -> FMB k v -> FMB k v
addToFMB [k]
xs Maybe v -> Maybe v
combiner FMB k v
fmbm) FMB k v
r
addToFMB [k]
_ Maybe v -> Maybe v
_ FMB k v
_ = String -> FMB k v
forall a. HasCallStack => String -> a
error String
"TernaryTrie.addToFMB: bug!"

addToFM :: (Ord k) => [k] -> (Maybe v -> Maybe v) -> FM k v -> FM k v
addToFM :: forall k v.
Ord k =>
[k] -> (Maybe v -> Maybe v) -> FM k v -> FM k v
addToFM [] Maybe v -> Maybe v
combiner (FM Maybe v
n FMB k v
fmb)
  = Maybe v -> FMB k v -> FM k v
forall k a. Maybe a -> FMB k a -> FM k a
FM (Maybe v -> Maybe v
combiner Maybe v
n) FMB k v
fmb
addToFM [k]
xs Maybe v -> Maybe v
combiner (FM Maybe v
n FMB k v
fmb)
  = Maybe v -> FMB k v -> FM k v
forall k a. Maybe a -> FMB k a -> FM k a
FM Maybe v
n ([k] -> (Maybe v -> Maybe v) -> FMB k v -> FMB k v
forall k v.
Ord k =>
[k] -> (Maybe v -> Maybe v) -> FMB k v -> FMB k v
addToFMB [k]
xs Maybe v -> Maybe v
combiner FMB k v
fmb)

lookupAndDelFromFMB :: (Ord k) => z -> (v -> FMB k v -> z) -> [k] -> FMB k v -> z
lookupAndDelFromFMB :: forall k z v.
Ord k =>
z -> (v -> FMB k v -> z) -> [k] -> FMB k v -> z
lookupAndDelFromFMB z
onFail v -> FMB k v -> z
_ [k]
_ FMB k v
E = z
onFail
lookupAndDelFromFMB z
onFail v -> FMB k v -> z
cont nk :: [k]
nk@(k
x:[k]
xs) (I Int
size k
k Maybe v
v FMB k v
l m :: FMB' k v
m@(FMB' FMB k v
fmbm) FMB k v
r)
  = case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
x k
k of
        Ordering
LT -> z -> (v -> FMB k v -> z) -> [k] -> FMB k v -> z
forall k z v.
Ord k =>
z -> (v -> FMB k v -> z) -> [k] -> FMB k v -> z
lookupAndDelFromFMB z
onFail (\v
w FMB k v
l' -> v -> FMB k v -> z
cont v
w (k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkBalancedFMB k
k Maybe v
v FMB k v
l' FMB' k v
m FMB k v
r)) [k]
nk FMB k v
l
        Ordering
GT -> z -> (v -> FMB k v -> z) -> [k] -> FMB k v -> z
forall k z v.
Ord k =>
z -> (v -> FMB k v -> z) -> [k] -> FMB k v -> z
lookupAndDelFromFMB z
onFail (\v
w FMB k v
r' -> v -> FMB k v -> z
cont v
w (k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkBalancedFMB k
k Maybe v
v FMB k v
l FMB' k v
m FMB k v
r')) [k]
nk FMB k v
r
        Ordering
EQ -> case [k]
xs of
                [] -> case Maybe v
v of
                        Maybe v
Nothing -> z
onFail
                        Just v
w  -> case FMB k v
fmbm of
                                      FMB k v
E -> v -> FMB k v -> z
cont v
w (FMB k v -> FMB k v -> FMB k v
forall k v. FMB k v -> FMB k v -> FMB k v
appendFMB FMB k v
l FMB k v
r)
                                      FMB k v
_ -> v -> FMB k v -> z
cont v
w (Int -> k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
forall k v.
Int -> k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
I Int
size k
k Maybe v
forall a. Maybe a
Nothing FMB k v
l FMB' k v
m FMB k v
r)
                [k]
_  -> z -> (v -> FMB k v -> z) -> [k] -> FMB k v -> z
forall k z v.
Ord k =>
z -> (v -> FMB k v -> z) -> [k] -> FMB k v -> z
lookupAndDelFromFMB z
onFail (\v
w FMB k v
m' -> v -> FMB k v -> z
cont v
w (Int -> k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
forall k v.
Int -> k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
I Int
size k
k Maybe v
v FMB k v
l (FMB k v -> FMB' k v
forall k v. FMB k v -> FMB' k v
FMB' FMB k v
m') FMB k v
r)) [k]
xs FMB k v
fmbm
lookupAndDelFromFMB z
_ v -> FMB k v -> z
_ [k]
_ FMB k v
_ = String -> z
forall a. HasCallStack => String -> a
error String
"TernaryTrie.lookupAndDelFromFMB: bug!"

lookupAndDelFromFM :: (Ord k) => z -> (v -> FM k v -> z) -> [k] -> FM k v -> z
lookupAndDelFromFM :: forall k z v.
Ord k =>
z -> (v -> FM k v -> z) -> [k] -> FM k v -> z
lookupAndDelFromFM z
onFail v -> FM k v -> z
_ [] (FM Maybe v
Nothing FMB k v
_)  = z
onFail
lookupAndDelFromFM z
_ v -> FM k v -> z
cont [] (FM (Just v
v) FMB k v
fmb) = v -> FM k v -> z
cont v
v (Maybe v -> FMB k v -> FM k v
forall k a. Maybe a -> FMB k a -> FM k a
FM Maybe v
forall a. Maybe a
Nothing FMB k v
fmb)
lookupAndDelFromFM z
onFail v -> FM k v -> z
cont [k]
xs (FM Maybe v
n FMB k v
fmb) =
   z -> (v -> FMB k v -> z) -> [k] -> FMB k v -> z
forall k z v.
Ord k =>
z -> (v -> FMB k v -> z) -> [k] -> FMB k v -> z
lookupAndDelFromFMB z
onFail (\v
w FMB k v
fmb' -> v -> FM k v -> z
cont v
w (Maybe v -> FMB k v -> FM k v
forall k a. Maybe a -> FMB k a -> FM k a
FM Maybe v
n FMB k v
fmb')) [k]
xs FMB k v
fmb


delFromFMB :: (Ord k) => [k] -> FMB k v -> FMB k v
delFromFMB :: forall k v. Ord k => [k] -> FMB k v -> FMB k v
delFromFMB [k]
_ FMB k v
E
  = FMB k v
forall k v. FMB k v
E
delFromFMB nk :: [k]
nk@(k
x:[k]
xs) (I Int
size k
k Maybe v
v FMB k v
l m :: FMB' k v
m@(FMB' FMB k v
fmbm) FMB k v
r)
  = case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
x k
k of
        Ordering
LT -> k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkBalancedFMB k
k Maybe v
v ([k] -> FMB k v -> FMB k v
forall k v. Ord k => [k] -> FMB k v -> FMB k v
delFromFMB [k]
nk FMB k v
l) FMB' k v
m FMB k v
r
        Ordering
GT -> k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkBalancedFMB k
k Maybe v
v FMB k v
l FMB' k v
m ([k] -> FMB k v -> FMB k v
forall k v. Ord k => [k] -> FMB k v -> FMB k v
delFromFMB [k]
nk FMB k v
r)
        Ordering
EQ -> case [k]
xs of
                [] -> case FMB k v
fmbm of
                        FMB k v
E -> FMB k v -> FMB k v -> FMB k v
forall k v. FMB k v -> FMB k v -> FMB k v
appendFMB FMB k v
l FMB k v
r
                        FMB k v
_ -> Int -> k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
forall k v.
Int -> k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
I Int
size k
k Maybe v
forall a. Maybe a
Nothing FMB k v
l FMB' k v
m FMB k v
r
                [k]
_  -> Int -> k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
forall k v.
Int -> k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
I Int
size k
k Maybe v
v FMB k v
l (FMB k v -> FMB' k v
forall k v. FMB k v -> FMB' k v
FMB' (FMB k v -> FMB' k v) -> FMB k v -> FMB' k v
forall a b. (a -> b) -> a -> b
$ [k] -> FMB k v -> FMB k v
forall k v. Ord k => [k] -> FMB k v -> FMB k v
delFromFMB [k]
xs FMB k v
fmbm) FMB k v
r
delFromFMB [k]
_ FMB k v
_ = String -> FMB k v
forall a. HasCallStack => String -> a
error String
"TernaryTrie.delFromFMB: bug!"


delFromFM :: (Ord k) => [k] -> FM k v -> FM k v
delFromFM :: forall k v. Ord k => [k] -> FM k v -> FM k v
delFromFM [] (FM Maybe v
_ FMB k v
fmb)
  = Maybe v -> FMB k v -> FM k v
forall k a. Maybe a -> FMB k a -> FM k a
FM Maybe v
forall a. Maybe a
Nothing FMB k v
fmb
delFromFM [k]
xs (FM Maybe v
n FMB k v
fmb)
  = Maybe v -> FMB k v -> FM k v
forall k a. Maybe a -> FMB k a -> FM k a
FM Maybe v
n ([k] -> FMB k v -> FMB k v
forall k v. Ord k => [k] -> FMB k v -> FMB k v
delFromFMB [k]
xs FMB k v
fmb)


mkBalancedFMB :: k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkBalancedFMB :: forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkBalancedFMB k
k Maybe v
v FMB k v
l FMB' k v
m FMB k v
r
  | Int
size_l Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
size_r Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
2
    = k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkFMB k
k Maybe v
v FMB k v
l FMB' k v
m FMB k v
r
  | Int
size_r Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
balance Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
size_l        -- Right tree too big
    = case FMB k v
r of
        I Int
_ k
_ Maybe v
_ FMB k v
rl FMB' k v
_ FMB k v
rr
            | FMB k v -> Int
forall k v. FMB k v -> Int
sizeFMB FMB k v
rl Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
2 Int -> Int -> Int
forall a. Num a => a -> a -> a
* FMB k v -> Int
forall k v. FMB k v -> Int
sizeFMB FMB k v
rr
                -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
single_L FMB k v
l FMB' k v
m FMB k v
r
            | Bool
otherwise
                -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
double_L FMB k v
l FMB' k v
m FMB k v
r
        FMB k v
_ -> String -> FMB k v
forall a. HasCallStack => String -> a
error String
"TernaryTrie.mkBalancedFMB: bug!"

  | Int
size_l Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
balance Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
size_r   -- Left tree too big
    = case FMB k v
l of
        I Int
_ k
_ Maybe v
_ FMB k v
ll FMB' k v
_ FMB k v
lr
            | FMB k v -> Int
forall k v. FMB k v -> Int
sizeFMB FMB k v
lr Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
2 Int -> Int -> Int
forall a. Num a => a -> a -> a
* FMB k v -> Int
forall k v. FMB k v -> Int
sizeFMB FMB k v
ll
                -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
single_R FMB k v
l FMB' k v
m FMB k v
r
            | Bool
otherwise
                -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
double_R FMB k v
l FMB' k v
m FMB k v
r
        FMB k v
_ -> String -> FMB k v
forall a. HasCallStack => String -> a
error String
"TernaryTrie.mkBalancedFMB: bug!"

  | Bool
otherwise                           -- No imbalance
    = k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkFMB k
k Maybe v
v FMB k v
l FMB' k v
m FMB k v
r
  where
        size_l :: Int
size_l   = FMB k v -> Int
forall k v. FMB k v -> Int
sizeFMB FMB k v
l
        size_r :: Int
size_r   = FMB k v -> Int
forall k v. FMB k v -> Int
sizeFMB FMB k v
r

        single_L :: FMB k v -> FMB' k v -> FMB k v -> FMB k v
single_L FMB k v
l FMB' k v
m (I Int
_ k
k_r Maybe v
v_r FMB k v
rl FMB' k v
rm FMB k v
rr)
          = k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkFMB k
k_r Maybe v
v_r (k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkFMB k
k Maybe v
v FMB k v
l FMB' k v
m FMB k v
rl) FMB' k v
rm FMB k v
rr
        single_L FMB k v
_ FMB' k v
_ FMB k v
_ = String -> FMB k v
forall a. HasCallStack => String -> a
error String
"TernaryTrie:mkBalancedFMB: bug!"

        double_L :: FMB k v -> FMB' k v -> FMB k v -> FMB k v
double_L FMB k v
l FMB' k v
m (I Int
_ k
k_r Maybe v
v_r (I Int
_ k
k_rl Maybe v
v_rl FMB k v
rll FMB' k v
rlm FMB k v
rlr) FMB' k v
rm FMB k v
rr)
          = k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkFMB k
k_rl Maybe v
v_rl (k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkFMB k
k Maybe v
v FMB k v
l FMB' k v
m FMB k v
rll) FMB' k v
rlm (k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkFMB k
k_r Maybe v
v_r FMB k v
rlr FMB' k v
rm FMB k v
rr)
        double_L FMB k v
_ FMB' k v
_ FMB k v
_ = String -> FMB k v
forall a. HasCallStack => String -> a
error String
"TernaryTrie:mkBalancedFMB: bug!"

        single_R :: FMB k v -> FMB' k v -> FMB k v -> FMB k v
single_R (I Int
_ k
k_l Maybe v
v_l FMB k v
ll FMB' k v
lm FMB k v
lr) FMB' k v
m FMB k v
r
          = k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkFMB k
k_l Maybe v
v_l FMB k v
ll FMB' k v
lm (k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkFMB k
k Maybe v
v FMB k v
lr FMB' k v
m FMB k v
r)
        single_R FMB k v
_ FMB' k v
_ FMB k v
_ = String -> FMB k v
forall a. HasCallStack => String -> a
error String
"TernaryTrie:mkBalancedFMB: bug!"

        double_R :: FMB k v -> FMB' k v -> FMB k v -> FMB k v
double_R (I Int
_ k
k_l Maybe v
v_l FMB k v
ll FMB' k v
lm (I Int
_ k
k_lr Maybe v
v_lr FMB k v
lrl FMB' k v
lrm FMB k v
lrr)) FMB' k v
m FMB k v
r
          = k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkFMB k
k_lr Maybe v
v_lr (k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkFMB k
k_l Maybe v
v_l FMB k v
ll FMB' k v
lm FMB k v
lrl) FMB' k v
lrm (k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkFMB k
k Maybe v
v FMB k v
lrr FMB' k v
m FMB k v
r)
        double_R FMB k v
_ FMB' k v
_ FMB k v
_ = String -> FMB k v
forall a. HasCallStack => String -> a
error String
"TernaryTrie:mkBalancedFMB: bug!"


mkVBalancedFMB :: k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkVBalancedFMB :: forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkVBalancedFMB k
k Maybe v
v FMB k v
E FMB' k v
m FMB k v
E
  = k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkFMB k
k Maybe v
v FMB k v
forall k v. FMB k v
E FMB' k v
m FMB k v
forall k v. FMB k v
E
mkVBalancedFMB k
k Maybe v
v l :: FMB k v
l@FMB k v
E FMB' k v
m (I Int
_ k
kr Maybe v
vr FMB k v
rl FMB' k v
rm FMB k v
rr)
  = k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkBalancedFMB k
kr Maybe v
vr (k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkVBalancedFMB k
k Maybe v
v FMB k v
l FMB' k v
m FMB k v
rl) FMB' k v
rm FMB k v
rr
mkVBalancedFMB k
k Maybe v
v (I Int
_ k
kl Maybe v
vl FMB k v
ll FMB' k v
lm FMB k v
lr) FMB' k v
m r :: FMB k v
r@FMB k v
E
  = k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkBalancedFMB k
kl Maybe v
vl FMB k v
ll FMB' k v
lm (k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkVBalancedFMB k
k Maybe v
v FMB k v
lr FMB' k v
m FMB k v
r)
mkVBalancedFMB k
k Maybe v
v l :: FMB k v
l@(I Int
_ k
kl Maybe v
vl FMB k v
ll FMB' k v
lm FMB k v
lr) FMB' k v
m r :: FMB k v
r@(I Int
_ k
kr Maybe v
vr FMB k v
rl FMB' k v
rm FMB k v
rr)
  | Int
balance Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
size_l Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
size_r
    = k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkBalancedFMB k
kr Maybe v
vr (k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkVBalancedFMB k
k Maybe v
v FMB k v
l FMB' k v
m FMB k v
rl) FMB' k v
rm FMB k v
rr
  | Int
balance Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
size_r Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
size_l
    = k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkBalancedFMB k
kl Maybe v
vl FMB k v
ll FMB' k v
lm (k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkVBalancedFMB k
k Maybe v
v FMB k v
lr FMB' k v
m FMB k v
r)
  | Bool
otherwise
    = k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkFMB k
k Maybe v
v FMB k v
l FMB' k v
m FMB k v
r
  where
        size_l :: Int
size_l = FMB k v -> Int
forall k v. FMB k v -> Int
sizeFMB FMB k v
l
        size_r :: Int
size_r = FMB k v -> Int
forall k v. FMB k v -> Int
sizeFMB FMB k v
r

    -- Constraint: All keys in the first FMB are less than
    -- that in the second FMB.
appendFMB :: FMB k v -> FMB k v -> FMB k v
appendFMB :: forall k v. FMB k v -> FMB k v -> FMB k v
appendFMB FMB k v
E FMB k v
m2 = FMB k v
m2
appendFMB FMB k v
m1 FMB k v
E = FMB k v
m1
appendFMB fmb1 :: FMB k v
fmb1@(I Int
size1 k
k1 Maybe v
v1 FMB k v
l1 FMB' k v
m1 FMB k v
r1) fmb2 :: FMB k v
fmb2@(I Int
size2 k
k2 Maybe v
v2 FMB k v
l2 FMB' k v
m2 FMB k v
r2)
  | Int
size1 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
size2
    = k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkVBalancedFMB k
k1 Maybe v
v1 FMB k v
l1 FMB' k v
m1 (FMB k v -> FMB k v -> FMB k v
forall k v. FMB k v -> FMB k v -> FMB k v
appendFMB FMB k v
r1 FMB k v
fmb2)
  | Bool
otherwise
    = k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkVBalancedFMB k
k2 Maybe v
v2 (FMB k v -> FMB k v -> FMB k v
forall k v. FMB k v -> FMB k v -> FMB k v
appendFMB FMB k v
fmb1 FMB k v
l2) FMB' k v
m2 FMB k v
r2

mapVFM :: (Maybe a -> Maybe b) -> FM k a -> FM k b
mapVFM :: forall a b k. (Maybe a -> Maybe b) -> FM k a -> FM k b
mapVFM Maybe a -> Maybe b
f (FM Maybe a
n FMB k a
fmb)
  = Maybe b -> FMB k b -> FM k b
forall k a. Maybe a -> FMB k a -> FM k a
FM (Maybe a -> Maybe b
f Maybe a
n) ((Maybe a -> Maybe b) -> FMB k a -> FMB k b
forall a b k. (Maybe a -> Maybe b) -> FMB k a -> FMB k b
mapVFMB Maybe a -> Maybe b
f FMB k a
fmb)

mapVFMB :: (Maybe a -> Maybe b) -> FMB k a -> FMB k b
mapVFMB :: forall a b k. (Maybe a -> Maybe b) -> FMB k a -> FMB k b
mapVFMB Maybe a -> Maybe b
f FMB k a
m
  = FMB k a -> FMB k b
forall {k}. FMB k a -> FMB k b
mapVFMB' FMB k a
m
  where
        mapVFMB' :: FMB k a -> FMB k b
mapVFMB' FMB k a
E = FMB k b
forall k v. FMB k v
E
        mapVFMB' (I Int
_ k
k Maybe a
v FMB k a
l (FMB' FMB k a
m) FMB k a
r)
          = case (FMB k a -> FMB k b
mapVFMB' FMB k a
m, Maybe a -> Maybe b
f Maybe a
v) of
                (FMB k b
E,Maybe b
Nothing) -> FMB k b -> FMB k b -> FMB k b
forall k v. FMB k v -> FMB k v -> FMB k v
appendFMB (FMB k a -> FMB k b
mapVFMB' FMB k a
l) (FMB k a -> FMB k b
mapVFMB' FMB k a
r)
                (FMB k b
m',Maybe b
v')     -> k -> Maybe b -> FMB k b -> FMB' k b -> FMB k b -> FMB k b
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkVBalancedFMB k
k Maybe b
v'
                                    (FMB k a -> FMB k b
mapVFMB' FMB k a
l) (FMB k b -> FMB' k b
forall k v. FMB k v -> FMB' k v
FMB' FMB k b
m') (FMB k a -> FMB k b
mapVFMB' FMB k a
r)

mapKVFM :: ([k] -> Maybe a -> Maybe b) -> FM k a -> FM k b
mapKVFM :: forall k a b. ([k] -> Maybe a -> Maybe b) -> FM k a -> FM k b
mapKVFM [k] -> Maybe a -> Maybe b
f (FM Maybe a
n FMB k a
fmb)
  = Maybe b -> FMB k b -> FM k b
forall k a. Maybe a -> FMB k a -> FM k a
FM ([k] -> Maybe a -> Maybe b
f [] Maybe a
n) ([k] -> FMB k a -> FMB k b
mapKVFMB [] FMB k a
fmb)
  where
        mapKVFMB :: [k] -> FMB k a -> FMB k b
mapKVFMB [k]
_ FMB k a
E = FMB k b
forall k v. FMB k v
E
        mapKVFMB [k]
ks (I Int
_ k
k Maybe a
v FMB k a
l (FMB' FMB k a
m) FMB k a
r)
          = k -> Maybe b -> FMB k b -> FMB' k b -> FMB k b -> FMB k b
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkVBalancedFMB k
k ([k] -> Maybe a -> Maybe b
f ([k] -> [k]
forall a. [a] -> [a]
reverse (k
kk -> [k] -> [k]
forall a. a -> [a] -> [a]
:[k]
ks)) Maybe a
v)
              ([k] -> FMB k a -> FMB k b
mapKVFMB [k]
ks FMB k a
l)
              (FMB k b -> FMB' k b
forall k v. FMB k v -> FMB' k v
FMB' ([k] -> FMB k a -> FMB k b
mapKVFMB (k
kk -> [k] -> [k]
forall a. a -> [a] -> [a]
:[k]
ks) FMB k a
m))
              ([k] -> FMB k a -> FMB k b
mapKVFMB [k]
ks FMB k a
r)

nullFMB :: FMB k v -> Bool
nullFMB :: forall k v. FMB k v -> Bool
nullFMB FMB k v
E = Bool
True
nullFMB (I Int
_ k
_ Maybe v
v FMB k v
l (FMB' FMB k v
m) FMB k v
r)
  = case Maybe v
v of
      Just v
_  -> Bool
False
      Maybe v
Nothing -> FMB k v -> Bool
forall k v. FMB k v -> Bool
nullFMB FMB k v
l Bool -> Bool -> Bool
&& FMB k v -> Bool
forall k v. FMB k v -> Bool
nullFMB FMB k v
m Bool -> Bool -> Bool
&& FMB k v -> Bool
forall k v. FMB k v -> Bool
nullFMB FMB k v
r

nullFM :: FM k v -> Bool
nullFM :: forall k v. FM k v -> Bool
nullFM (FM (Just v
_) FMB k v
_)  = Bool
False
nullFM (FM Maybe v
Nothing FMB k v
fmb) = FMB k v -> Bool
forall k v. FMB k v -> Bool
nullFMB FMB k v
fmb

data FMBCtx k v
  = T
  | L !k !(Maybe v) !(FMBCtx k v) !(FMB' k v) !(FMB k v)
  | R !k !(Maybe v) !(FMB k v) !(FMB' k v) !(FMBCtx k v)

splayFMB :: (Ord k) => k -> FMB k a -> (Maybe a, FMB k a, FMB' k a, FMB k a)
splayFMB :: forall k a.
Ord k =>
k -> FMB k a -> (Maybe a, FMB k a, FMB' k a, FMB k a)
splayFMB k
key FMB k a
fmb
  = FMBCtx k a -> FMB k a -> (Maybe a, FMB k a, FMB' k a, FMB k a)
forall {v}.
FMBCtx k v -> FMB k v -> (Maybe v, FMB k v, FMB' k v, FMB k v)
splaydown FMBCtx k a
forall k v. FMBCtx k v
T FMB k a
fmb
  where
    splaydown :: FMBCtx k v -> FMB k v -> (Maybe v, FMB k v, FMB' k v, FMB k v)
splaydown FMBCtx k v
ctx FMB k v
E
      = FMBCtx k v
-> Maybe v
-> FMB k v
-> FMB' k v
-> FMB k v
-> (Maybe v, FMB k v, FMB' k v, FMB k v)
forall {k} {v} {p} {p}.
FMBCtx k v
-> p -> FMB k v -> p -> FMB k v -> (p, FMB k v, p, FMB k v)
splayup FMBCtx k v
ctx Maybe v
forall a. Maybe a
Nothing FMB k v
forall k v. FMB k v
E (FMB k v -> FMB' k v
forall k v. FMB k v -> FMB' k v
FMB' FMB k v
forall k v. FMB k v
E) FMB k v
forall k v. FMB k v
E
    splaydown FMBCtx k v
ctx (I Int
_ k
k Maybe v
v FMB k v
l FMB' k v
m FMB k v
r)
      = case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
key k
k of
            Ordering
LT -> FMBCtx k v -> FMB k v -> (Maybe v, FMB k v, FMB' k v, FMB k v)
splaydown (k -> Maybe v -> FMBCtx k v -> FMB' k v -> FMB k v -> FMBCtx k v
forall k v.
k -> Maybe v -> FMBCtx k v -> FMB' k v -> FMB k v -> FMBCtx k v
L k
k Maybe v
v FMBCtx k v
ctx FMB' k v
m FMB k v
r) FMB k v
l
            Ordering
GT -> FMBCtx k v -> FMB k v -> (Maybe v, FMB k v, FMB' k v, FMB k v)
splaydown (k -> Maybe v -> FMB k v -> FMB' k v -> FMBCtx k v -> FMBCtx k v
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMBCtx k v -> FMBCtx k v
R k
k Maybe v
v FMB k v
l FMB' k v
m FMBCtx k v
ctx) FMB k v
r
            Ordering
EQ -> FMBCtx k v
-> Maybe v
-> FMB k v
-> FMB' k v
-> FMB k v
-> (Maybe v, FMB k v, FMB' k v, FMB k v)
forall {k} {v} {p} {p}.
FMBCtx k v
-> p -> FMB k v -> p -> FMB k v -> (p, FMB k v, p, FMB k v)
splayup FMBCtx k v
ctx Maybe v
v FMB k v
l FMB' k v
m FMB k v
r

    splayup :: FMBCtx k v
-> p -> FMB k v -> p -> FMB k v -> (p, FMB k v, p, FMB k v)
splayup FMBCtx k v
ctx p
v FMB k v
l p
m FMB k v
r
      = FMBCtx k v -> FMB k v -> FMB k v -> (p, FMB k v, p, FMB k v)
forall {k} {v}.
FMBCtx k v -> FMB k v -> FMB k v -> (p, FMB k v, p, FMB k v)
splayup' FMBCtx k v
ctx FMB k v
l FMB k v
r
      where
          splayup' :: FMBCtx k v -> FMB k v -> FMB k v -> (p, FMB k v, p, FMB k v)
splayup' FMBCtx k v
T FMB k v
l FMB k v
r
            = (p
v, FMB k v
l, p
m, FMB k v
r)
          splayup' (L k
ck Maybe v
cv FMBCtx k v
ctx FMB' k v
cm FMB k v
cr) FMB k v
tl FMB k v
tr
            = FMBCtx k v -> FMB k v -> FMB k v -> (p, FMB k v, p, FMB k v)
splayup' FMBCtx k v
ctx FMB k v
tl (k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkVBalancedFMB k
ck Maybe v
cv FMB k v
tr FMB' k v
cm FMB k v
cr)
          splayup' (R k
ck Maybe v
cv FMB k v
cl FMB' k v
cm FMBCtx k v
ctx) FMB k v
tl FMB k v
tr
            = FMBCtx k v -> FMB k v -> FMB k v -> (p, FMB k v, p, FMB k v)
splayup' FMBCtx k v
ctx (k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkVBalancedFMB k
ck Maybe v
cv FMB k v
cl FMB' k v
cm FMB k v
tl) FMB k v
tr

mergeVFMB :: (Ord k) => (Maybe a -> Maybe b -> Maybe c) ->
                FMB k a -> FMB k b -> FMB k c
mergeVFMB :: forall k a b c.
Ord k =>
(Maybe a -> Maybe b -> Maybe c) -> FMB k a -> FMB k b -> FMB k c
mergeVFMB Maybe a -> Maybe b -> Maybe c
f FMB k a
fmbx FMB k b
fmby
  = FMB k a -> FMB k b -> FMB k c
forall {k}. Ord k => FMB k a -> FMB k b -> FMB k c
mergeVFMB' FMB k a
fmbx FMB k b
fmby
  where
    mergeVFMB' :: FMB k a -> FMB k b -> FMB k c
mergeVFMB' FMB k a
E FMB k b
E
      = FMB k c
forall k v. FMB k v
E
    mergeVFMB' FMB k a
E fmby :: FMB k b
fmby@(I Int
_ k
_ Maybe b
_ FMB k b
_ (FMB' FMB k b
_) FMB k b
_)
      = (Maybe b -> Maybe c) -> FMB k b -> FMB k c
forall a b k. (Maybe a -> Maybe b) -> FMB k a -> FMB k b
mapVFMB (\Maybe b
v -> Maybe a -> Maybe b -> Maybe c
f Maybe a
forall a. Maybe a
Nothing Maybe b
v) FMB k b
fmby
    mergeVFMB' fmbx :: FMB k a
fmbx@(I Int
_ k
_ Maybe a
_ FMB k a
_ (FMB' FMB k a
_) FMB k a
_) FMB k b
E
      = (Maybe a -> Maybe c) -> FMB k a -> FMB k c
forall a b k. (Maybe a -> Maybe b) -> FMB k a -> FMB k b
mapVFMB (\Maybe a
v -> Maybe a -> Maybe b -> Maybe c
f Maybe a
v Maybe b
forall a. Maybe a
Nothing) FMB k a
fmbx
    mergeVFMB' fmbx :: FMB k a
fmbx@(I Int
sizex k
kx Maybe a
vx FMB k a
lx (FMB' FMB k a
mx) FMB k a
rx)
               fmby :: FMB k b
fmby@(I Int
sizey k
ky Maybe b
vy FMB k b
ly (FMB' FMB k b
my) FMB k b
ry)
      | Int
sizex Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
sizey
        = let (Maybe b
vy, FMB k b
ly, FMB' FMB k b
my, FMB k b
ry) = k -> FMB k b -> (Maybe b, FMB k b, FMB' k b, FMB k b)
forall k a.
Ord k =>
k -> FMB k a -> (Maybe a, FMB k a, FMB' k a, FMB k a)
splayFMB k
kx FMB k b
fmby
          in case (FMB k a -> FMB k b -> FMB k c
mergeVFMB' FMB k a
mx FMB k b
my, Maybe a -> Maybe b -> Maybe c
f Maybe a
vx Maybe b
vy) of
                (FMB k c
E,Maybe c
Nothing) -> FMB k c -> FMB k c -> FMB k c
forall k v. FMB k v -> FMB k v -> FMB k v
appendFMB (FMB k a -> FMB k b -> FMB k c
mergeVFMB' FMB k a
lx FMB k b
ly) (FMB k a -> FMB k b -> FMB k c
mergeVFMB' FMB k a
rx FMB k b
ry)
                (FMB k c
m',Maybe c
v)      -> k -> Maybe c -> FMB k c -> FMB' k c -> FMB k c -> FMB k c
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkVBalancedFMB k
kx Maybe c
v
                                   (FMB k a -> FMB k b -> FMB k c
mergeVFMB' FMB k a
lx FMB k b
ly)
                                   (FMB k c -> FMB' k c
forall k v. FMB k v -> FMB' k v
FMB' FMB k c
m')
                                   (FMB k a -> FMB k b -> FMB k c
mergeVFMB' FMB k a
rx FMB k b
ry)
      | Bool
otherwise
        = let (Maybe a
vx, FMB k a
lx, FMB' FMB k a
mx, FMB k a
rx) = k -> FMB k a -> (Maybe a, FMB k a, FMB' k a, FMB k a)
forall k a.
Ord k =>
k -> FMB k a -> (Maybe a, FMB k a, FMB' k a, FMB k a)
splayFMB k
ky FMB k a
fmbx
          in case (FMB k a -> FMB k b -> FMB k c
mergeVFMB' FMB k a
mx FMB k b
my, Maybe a -> Maybe b -> Maybe c
f Maybe a
vx Maybe b
vy) of
                (FMB k c
E,Maybe c
Nothing) -> FMB k c -> FMB k c -> FMB k c
forall k v. FMB k v -> FMB k v -> FMB k v
appendFMB (FMB k a -> FMB k b -> FMB k c
mergeVFMB' FMB k a
lx FMB k b
ly) (FMB k a -> FMB k b -> FMB k c
mergeVFMB' FMB k a
rx FMB k b
ry)
                (FMB k c
m',Maybe c
v)      -> k -> Maybe c -> FMB k c -> FMB' k c -> FMB k c -> FMB k c
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkVBalancedFMB k
ky Maybe c
v
                                   (FMB k a -> FMB k b -> FMB k c
mergeVFMB' FMB k a
lx FMB k b
ly)
                                   (FMB k c -> FMB' k c
forall k v. FMB k v -> FMB' k v
FMB' FMB k c
m')
                                   (FMB k a -> FMB k b -> FMB k c
mergeVFMB' FMB k a
rx FMB k b
ry)

mergeVFM :: (Ord k) => (Maybe a -> Maybe b -> Maybe c) ->
                FM k a -> FM k b -> FM k c
mergeVFM :: forall k a b c.
Ord k =>
(Maybe a -> Maybe b -> Maybe c) -> FM k a -> FM k b -> FM k c
mergeVFM Maybe a -> Maybe b -> Maybe c
f (FM Maybe a
vx FMB k a
fmbx) (FM Maybe b
vy FMB k b
fmby)
  = Maybe c -> FMB k c -> FM k c
forall k a. Maybe a -> FMB k a -> FM k a
FM (Maybe a -> Maybe b -> Maybe c
f Maybe a
vx Maybe b
vy) ((Maybe a -> Maybe b -> Maybe c) -> FMB k a -> FMB k b -> FMB k c
forall k a b c.
Ord k =>
(Maybe a -> Maybe b -> Maybe c) -> FMB k a -> FMB k b -> FMB k c
mergeVFMB Maybe a -> Maybe b -> Maybe c
f FMB k a
fmbx FMB k b
fmby)


mergeKVFMB :: (Ord k) => ([k] -> Maybe a -> Maybe b -> Maybe c) ->
                FMB k a -> FMB k b -> FMB k c
mergeKVFMB :: forall k a b c.
Ord k =>
([k] -> Maybe a -> Maybe b -> Maybe c)
-> FMB k a -> FMB k b -> FMB k c
mergeKVFMB [k] -> Maybe a -> Maybe b -> Maybe c
f FMB k a
fmbx FMB k b
fmby
  = [k] -> FMB k a -> FMB k b -> FMB k c
mergeKVFMB' [] FMB k a
fmbx FMB k b
fmby
  where
    mergeKVFMB' :: [k] -> FMB k a -> FMB k b -> FMB k c
mergeKVFMB' [k]
_ FMB k a
E FMB k b
E
      = FMB k c
forall k v. FMB k v
E
    mergeKVFMB' [k]
ks FMB k a
E FMB k b
fmby
      = ([k] -> Maybe b -> Maybe c) -> [k] -> FMB k b -> FMB k c
forall {k} {v} {v}.
([k] -> Maybe v -> Maybe v) -> [k] -> FMB k v -> FMB k v
mergeKVFMBs (\[k]
k Maybe b
v -> [k] -> Maybe a -> Maybe b -> Maybe c
f [k]
k Maybe a
forall a. Maybe a
Nothing Maybe b
v) [k]
ks FMB k b
fmby
    mergeKVFMB' [k]
ks FMB k a
fmbx FMB k b
E
      = ([k] -> Maybe a -> Maybe c) -> [k] -> FMB k a -> FMB k c
forall {k} {v} {v}.
([k] -> Maybe v -> Maybe v) -> [k] -> FMB k v -> FMB k v
mergeKVFMBs (\[k]
k Maybe a
v -> [k] -> Maybe a -> Maybe b -> Maybe c
f [k]
k Maybe a
v Maybe b
forall a. Maybe a
Nothing) [k]
ks FMB k a
fmbx
    mergeKVFMB' [k]
ks fmbx :: FMB k a
fmbx@(I Int
sizex k
kx Maybe a
vx FMB k a
lx (FMB' FMB k a
mx) FMB k a
rx)
                   fmby :: FMB k b
fmby@(I Int
sizey k
ky Maybe b
vy FMB k b
ly (FMB' FMB k b
my) FMB k b
ry)
      | Int
sizex Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
sizey
        = let (Maybe b
vy, FMB k b
ly, FMB' FMB k b
my, FMB k b
ry) = k -> FMB k b -> (Maybe b, FMB k b, FMB' k b, FMB k b)
forall k a.
Ord k =>
k -> FMB k a -> (Maybe a, FMB k a, FMB' k a, FMB k a)
splayFMB k
kx FMB k b
fmby
              ks' :: [k]
ks' = [k] -> [k]
forall a. [a] -> [a]
reverse (k
kxk -> [k] -> [k]
forall a. a -> [a] -> [a]
:[k]
ks)
          in case ([k] -> FMB k a -> FMB k b -> FMB k c
mergeKVFMB' [k]
ks' FMB k a
mx FMB k b
my, [k] -> Maybe a -> Maybe b -> Maybe c
f [k]
ks' Maybe a
vx Maybe b
vy) of
                (FMB k c
E,Maybe c
Nothing) -> FMB k c -> FMB k c -> FMB k c
forall k v. FMB k v -> FMB k v -> FMB k v
appendFMB
                                    ([k] -> FMB k a -> FMB k b -> FMB k c
mergeKVFMB' [k]
ks FMB k a
lx FMB k b
ly)
                                    ([k] -> FMB k a -> FMB k b -> FMB k c
mergeKVFMB' [k]
ks FMB k a
rx FMB k b
ry)
                (FMB k c
m',Maybe c
v)      -> k -> Maybe c -> FMB k c -> FMB' k c -> FMB k c -> FMB k c
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkVBalancedFMB k
kx Maybe c
v
                                    ([k] -> FMB k a -> FMB k b -> FMB k c
mergeKVFMB' [k]
ks FMB k a
lx FMB k b
ly)
                                    (FMB k c -> FMB' k c
forall k v. FMB k v -> FMB' k v
FMB' FMB k c
m')
                                    ([k] -> FMB k a -> FMB k b -> FMB k c
mergeKVFMB' [k]
ks FMB k a
rx FMB k b
ry)
      | Bool
otherwise
        = let (Maybe a
vx, FMB k a
lx, FMB' FMB k a
mx, FMB k a
rx) = k -> FMB k a -> (Maybe a, FMB k a, FMB' k a, FMB k a)
forall k a.
Ord k =>
k -> FMB k a -> (Maybe a, FMB k a, FMB' k a, FMB k a)
splayFMB k
ky FMB k a
fmbx
              ks' :: [k]
ks' = [k] -> [k]
forall a. [a] -> [a]
reverse (k
kyk -> [k] -> [k]
forall a. a -> [a] -> [a]
:[k]
ks)
          in case ([k] -> FMB k a -> FMB k b -> FMB k c
mergeKVFMB' [k]
ks' FMB k a
mx FMB k b
my, [k] -> Maybe a -> Maybe b -> Maybe c
f [k]
ks' Maybe a
vx Maybe b
vy) of
                (FMB k c
E,Maybe c
Nothing) -> FMB k c -> FMB k c -> FMB k c
forall k v. FMB k v -> FMB k v -> FMB k v
appendFMB
                                    ([k] -> FMB k a -> FMB k b -> FMB k c
mergeKVFMB' [k]
ks FMB k a
lx FMB k b
ly)
                                    ([k] -> FMB k a -> FMB k b -> FMB k c
mergeKVFMB' [k]
ks FMB k a
rx FMB k b
ry)
                (FMB k c
m',Maybe c
v)      -> k -> Maybe c -> FMB k c -> FMB' k c -> FMB k c -> FMB k c
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkVBalancedFMB k
ky Maybe c
v
                                    ([k] -> FMB k a -> FMB k b -> FMB k c
mergeKVFMB' [k]
ks FMB k a
lx FMB k b
ly)
                                    (FMB k c -> FMB' k c
forall k v. FMB k v -> FMB' k v
FMB' FMB k c
m')
                                    ([k] -> FMB k a -> FMB k b -> FMB k c
mergeKVFMB' [k]
ks FMB k a
rx FMB k b
ry)

    mergeKVFMBs :: ([k] -> Maybe v -> Maybe v) -> [k] -> FMB k v -> FMB k v
mergeKVFMBs [k] -> Maybe v -> Maybe v
f [k]
ks FMB k v
fmb
      = [k] -> FMB k v -> FMB k v
mergeKVFMBs' [k]
ks FMB k v
fmb
      where
          mergeKVFMBs' :: [k] -> FMB k v -> FMB k v
mergeKVFMBs' [k]
_ FMB k v
E
            = FMB k v
forall k v. FMB k v
E
          mergeKVFMBs' [k]
ks (I Int
_ k
k Maybe v
v FMB k v
l (FMB' FMB k v
m) FMB k v
r)
            = case ([k] -> FMB k v -> FMB k v
mergeKVFMBs' (k
kk -> [k] -> [k]
forall a. a -> [a] -> [a]
:[k]
ks) FMB k v
m, [k] -> Maybe v -> Maybe v
f ([k] -> [k]
forall a. [a] -> [a]
reverse (k
kk -> [k] -> [k]
forall a. a -> [a] -> [a]
:[k]
ks)) Maybe v
v) of
                (FMB k v
E, Maybe v
Nothing) -> FMB k v -> FMB k v -> FMB k v
forall k v. FMB k v -> FMB k v -> FMB k v
appendFMB
                                    ([k] -> FMB k v -> FMB k v
mergeKVFMBs' [k]
ks FMB k v
l)
                                    ([k] -> FMB k v -> FMB k v
mergeKVFMBs' [k]
ks FMB k v
r)
                (FMB k v
m,Maybe v
v)        -> k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkVBalancedFMB k
k Maybe v
v
                                    ([k] -> FMB k v -> FMB k v
mergeKVFMBs' [k]
ks FMB k v
l)
                                    (FMB k v -> FMB' k v
forall k v. FMB k v -> FMB' k v
FMB' FMB k v
m)
                                    ([k] -> FMB k v -> FMB k v
mergeKVFMBs' [k]
ks FMB k v
r)

mergeKVFM :: (Ord k) => ([k] -> Maybe a -> Maybe b -> Maybe c) ->
                FM k a -> FM k b -> FM k c
mergeKVFM :: forall k a b c.
Ord k =>
([k] -> Maybe a -> Maybe b -> Maybe c)
-> FM k a -> FM k b -> FM k c
mergeKVFM [k] -> Maybe a -> Maybe b -> Maybe c
f (FM Maybe a
vx FMB k a
fmbx) (FM Maybe b
vy FMB k b
fmby)
  = Maybe c -> FMB k c -> FM k c
forall k a. Maybe a -> FMB k a -> FM k a
FM ([k] -> Maybe a -> Maybe b -> Maybe c
f [] Maybe a
vx Maybe b
vy) (([k] -> Maybe a -> Maybe b -> Maybe c)
-> FMB k a -> FMB k b -> FMB k c
forall k a b c.
Ord k =>
([k] -> Maybe a -> Maybe b -> Maybe c)
-> FMB k a -> FMB k b -> FMB k c
mergeKVFMB [k] -> Maybe a -> Maybe b -> Maybe c
f FMB k a
fmbx FMB k b
fmby)


-- The public interface.
--

-- AssocX

empty :: forall k a. Ord k => FM k a
empty = Maybe a -> FMB k a -> FM k a
forall k a. Maybe a -> FMB k a -> FM k a
FM Maybe a
forall a. Maybe a
Nothing FMB k a
forall k v. FMB k v
E

singleton :: forall k a. Ord k => [k] -> a -> FM k a
singleton [] a
v = Maybe a -> FMB k a -> FM k a
forall k a. Maybe a -> FMB k a -> FM k a
FM (a -> Maybe a
forall a. a -> Maybe a
Just a
v) FMB k a
forall k v. FMB k v
E
singleton [k]
xs a
v = Maybe a -> FMB k a -> FM k a
forall k a. Maybe a -> FMB k a -> FM k a
FM Maybe a
forall a. Maybe a
Nothing ([k] -> (Maybe a -> Maybe a) -> FMB k a
forall k v. [k] -> (Maybe v -> Maybe v) -> FMB k v
listToFMB [k]
xs (\Maybe a
_ -> a -> Maybe a
forall a. a -> Maybe a
Just a
v))

fromSeq :: forall k (seq :: * -> *) a.
(Ord k, Sequence seq) =>
seq ([k], a) -> FM k a
fromSeq = seq ([k], a) -> FM k a
forall (m :: * -> *) k (seq :: * -> *) a.
(AssocX m k, Sequence seq) =>
seq (k, a) -> m a
fromSeqUsingInsertSeq

insert :: forall k a. Ord k => [k] -> a -> FM k a -> FM k a
insert [k]
k a
v FM k a
fm = [k] -> (Maybe a -> Maybe a) -> FM k a -> FM k a
forall k v.
Ord k =>
[k] -> (Maybe v -> Maybe v) -> FM k v -> FM k v
addToFM [k]
k (\Maybe a
_ -> a -> Maybe a
forall a. a -> Maybe a
Just a
v) FM k a
fm

insertSeq :: forall k (seq :: * -> *) a.
(Ord k, Sequence seq) =>
seq ([k], a) -> FM k a -> FM k a
insertSeq = seq ([k], a) -> FM k a -> FM k a
forall (m :: * -> *) k (seq :: * -> *) a.
(AssocX m k, Sequence seq) =>
seq (k, a) -> m a -> m a
insertSeqUsingFoldr

union :: forall k a. Ord k => FM k a -> FM k a -> FM k a
union = (Maybe a -> Maybe a -> Maybe a) -> FM k a -> FM k a -> FM k a
forall k a b c.
Ord k =>
(Maybe a -> Maybe b -> Maybe c) -> FM k a -> FM k b -> FM k c
mergeVFM Maybe a -> Maybe a -> Maybe a
forall a. Maybe a -> Maybe a -> Maybe a
forall (m :: * -> *) a. MonadPlus m => m a -> m a -> m a
mplus

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

delete :: forall k v. Ord k => [k] -> FM k v -> FM k v
delete [k]
k FM k a
fm = [k] -> FM k a -> FM k a
forall k v. Ord k => [k] -> FM k v -> FM k v
delFromFM [k]
k FM k a
fm

deleteAll :: forall k v. Ord k => [k] -> FM k v -> FM k v
deleteAll = [k] -> FM k a -> FM k a
forall k v. Ord k => [k] -> FM k v -> FM k v
delete

deleteSeq :: forall k (seq :: * -> *) a.
(Ord k, Sequence seq) =>
seq [k] -> FM k a -> FM k a
deleteSeq = seq [k] -> FM k a -> FM k a
forall (m :: * -> *) k (seq :: * -> *) a.
(AssocX m k, Sequence seq) =>
seq k -> m a -> m a
deleteSeqUsingFoldr

null :: forall k a. Ord k => FM k a -> Bool
null = FM k a -> Bool
forall k v. FM k v -> Bool
nullFM

size :: forall k a. Ord k => FM k a -> Int
size (FM Maybe a
k FMB k a
fmb)
    | Maybe a -> Bool
forall a. Maybe a -> Bool
isNothing Maybe a
k = FMB k a -> Int -> Int
forall {a} {k} {v}. Num a => FMB k v -> a -> a
fmb_size FMB k a
fmb Int
0
    | Bool
otherwise   = FMB k a -> Int -> Int
forall {a} {k} {v}. Num a => FMB k v -> a -> a
fmb_size FMB k a
fmb Int
1
    where fmb_size :: FMB k v -> a -> a
fmb_size FMB k v
E a
k = a
k
          fmb_size (I Int
_ k
_ Maybe v
Nothing FMB k v
l (FMB' FMB k v
m) FMB k v
r) a
k = FMB k v -> a -> a
fmb_size FMB k v
l (a -> a) -> a -> a
forall a b. (a -> b) -> a -> b
$ FMB k v -> a -> a
fmb_size FMB k v
m (a -> a) -> a -> a
forall a b. (a -> b) -> a -> b
$ FMB k v -> a -> a
fmb_size FMB k v
r a
k
          fmb_size (I Int
_ k
_ Maybe v
_ FMB k v
l (FMB' FMB k v
m) FMB k v
r ) a
k      = FMB k v -> a -> a
fmb_size FMB k v
l (a -> a) -> a -> a
forall a b. (a -> b) -> a -> b
$ FMB k v -> a -> a
fmb_size FMB k v
m (a -> a) -> a -> a
forall a b. (a -> b) -> a -> b
$ FMB k v -> a -> a
fmb_size FMB k v
r (a -> a) -> a -> a
forall a b. (a -> b) -> a -> b
$! a
ka -> a -> a
forall a. Num a => a -> a -> a
+a
1


member :: forall k a. Ord k => [k] -> FM k a -> Bool
member = [k] -> FM k a -> Bool
forall (m :: * -> *) k a. AssocX m k => k -> m a -> Bool
memberUsingLookupM

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

lookup :: forall k a. Ord k => [k] -> FM k a -> a
lookup [k]
m FM k a
k = Fail a -> a
forall a. Fail a -> a
runFail_ ([k] -> FM k a -> Fail a
forall k (rm :: * -> *) a.
(Ord k, MonadFail rm) =>
[k] -> FM k a -> rm a
lookupM [k]
m FM k a
k)

lookupM :: forall k (rm :: * -> *) a.
(Ord k, MonadFail rm) =>
[k] -> FM k a -> rm a
lookupM [] (FM Maybe a
Nothing FMB k a
_)
  = String -> rm a
forall a. String -> rm a
forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"TernaryTrie.lookup: lookup failed"
lookupM [] (FM (Just a
v) FMB k a
_)
  = a -> rm a
forall a. a -> rm a
forall (m :: * -> *) a. Monad m => a -> m a
return a
v
lookupM [k]
xs (FM Maybe a
_ FMB k a
fmb)
  = case  [k] -> FMB k a -> Maybe a
forall k v. Ord k => [k] -> FMB k v -> Maybe v
lookupFMB [k]
xs FMB k a
fmb  of
        Maybe a
Nothing -> String -> rm a
forall a. String -> rm a
forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"TernaryTrie.lookup: lookup failed"
        Just a
v  -> a -> rm a
forall a. a -> rm a
forall (m :: * -> *) a. Monad m => a -> m a
return a
v

lookupAll :: forall k (seq :: * -> *) a.
(Ord k, Sequence seq) =>
[k] -> FM k a -> seq a
lookupAll = [k] -> FM k a -> seq a
forall (m :: * -> *) k (seq :: * -> *) a.
(AssocX m k, Sequence seq) =>
k -> m a -> seq a
lookupAllUsingLookupM

lookupAndDelete :: forall k a. Ord k => [k] -> FM k a -> (a, FM k a)
lookupAndDelete =
    (a, FM k a)
-> (a -> FM k a -> (a, FM k a)) -> [k] -> FM k a -> (a, FM k a)
forall k z v.
Ord k =>
z -> (v -> FM k v -> z) -> [k] -> FM k v -> z
lookupAndDelFromFM
      (String -> (a, FM k a)
forall a. HasCallStack => String -> a
error String
"TernaryTrie.lookupAndDelete: lookup failed")
      (,)

lookupAndDeleteM :: forall k (rm :: * -> *) a.
(Ord k, MonadFail rm) =>
[k] -> FM k a -> rm (a, FM k a)
lookupAndDeleteM =
    rm (a, FM k a)
-> (a -> FM k a -> rm (a, FM k a))
-> [k]
-> FM k a
-> rm (a, FM k a)
forall k z v.
Ord k =>
z -> (v -> FM k v -> z) -> [k] -> FM k v -> z
lookupAndDelFromFM
      (String -> rm (a, FM k a)
forall a. String -> rm a
forall (m :: * -> *) a. MonadFail m => String -> m a
fail  String
"TernaryTrie.lookupAndDeleteM: lookup failed")
      (\a
w FM k a
m -> (a, FM k a) -> rm (a, FM k a)
forall a. a -> rm a
forall (m :: * -> *) a. Monad m => a -> m a
return (a
w,FM k a
m))

lookupAndDeleteAll :: forall k (seq :: * -> *) a.
(Ord k, Sequence seq) =>
[k] -> FM k a -> (seq a, FM k a)
lookupAndDeleteAll [k]
k FM k a
m =
    (seq a, FM k a)
-> (a -> FM k a -> (seq a, FM k a))
-> [k]
-> FM k a
-> (seq a, FM k a)
forall k z v.
Ord k =>
z -> (v -> FM k v -> z) -> [k] -> FM k v -> z
lookupAndDelFromFM
      (seq a
forall (s :: * -> *) a. Sequence s => s a
S.empty,FM k a
m)
      (\a
w FM k a
m' -> (a -> seq a
forall (s :: * -> *) a. Sequence s => a -> s a
S.singleton a
w,FM k a
m'))
      [k]
k FM k a
m

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

adjust :: forall k a. Ord k => (a -> a) -> [k] -> FM k a -> FM k a
adjust a -> a
f [k]
k
  = [k] -> (Maybe a -> Maybe a) -> FM k a -> FM k a
forall k v.
Ord k =>
[k] -> (Maybe v -> Maybe v) -> FM k v -> FM k v
addToFM [k]
k (\Maybe a
mv -> case Maybe a
mv of
                        Maybe a
Nothing -> Maybe a
mv
                        Just a
v  -> a -> Maybe a
forall a. a -> Maybe a
Just (a -> a
f a
v))

adjustAll :: forall k a. Ord k => (a -> a) -> [k] -> FM k a -> FM k a
adjustAll = (a -> a) -> [k] -> FM k a -> FM k a
forall k a. Ord k => (a -> a) -> [k] -> FM k a -> FM k a
adjust

adjustOrInsert :: forall k a. Ord k => (a -> a) -> a -> [k] -> FM k a -> FM k a
adjustOrInsert a -> a
f a
z [k]
k
  = [k] -> (Maybe a -> Maybe a) -> FM k a -> FM k a
forall k v.
Ord k =>
[k] -> (Maybe v -> Maybe v) -> FM k v -> FM k v
addToFM [k]
k (\Maybe a
mv -> case Maybe a
mv of
                        Maybe a
Nothing -> a -> Maybe a
forall a. a -> Maybe a
Just a
z
                        Just a
v  -> a -> Maybe a
forall a. a -> Maybe a
Just (a -> a
f a
v))

adjustAllOrInsert :: forall k a. Ord k => (a -> a) -> a -> [k] -> FM k a -> FM k a
adjustAllOrInsert = (a -> a) -> a -> [k] -> FM k a -> FM k a
forall k a. Ord k => (a -> a) -> a -> [k] -> FM k a -> FM k a
adjustOrInsert

adjustOrDelete :: forall k a. Ord k => (a -> Maybe a) -> [k] -> FM k a -> FM k a
adjustOrDelete a -> Maybe a
f [k]
k
  = [k] -> (Maybe a -> Maybe a) -> FM k a -> FM k a
forall k v.
Ord k =>
[k] -> (Maybe v -> Maybe v) -> FM k v -> FM k v
addToFM [k]
k (\Maybe a
mv -> case Maybe a
mv of
                        Maybe a
Nothing -> Maybe a
mv
                        Just a
v  -> a -> Maybe a
f a
v)

adjustOrDeleteAll :: forall k a. Ord k => (a -> Maybe a) -> [k] -> FM k a -> FM k a
adjustOrDeleteAll = (a -> Maybe a) -> [k] -> FM k a -> FM k a
forall k a. Ord k => (a -> Maybe a) -> [k] -> FM k a -> FM k a
adjustOrDelete

map :: forall k a b. Ord k => (a -> b) -> FM k a -> FM k b
map a -> b
f
  = (Maybe a -> Maybe b) -> FM k a -> FM k b
forall a b k. (Maybe a -> Maybe b) -> FM k a -> FM k b
mapVFM (\Maybe a
mv -> case Maybe a
mv of
                        Maybe a
Nothing -> Maybe b
forall a. Maybe a
Nothing
                        Just a
v  -> b -> Maybe b
forall a. a -> Maybe a
Just (a -> b
f a
v))

fold :: forall k a b. Ord k => (a -> b -> b) -> b -> FM k a -> b
fold = (a -> b -> b) -> b -> FM k a -> b
forall k a b. Ord k => (a -> b -> b) -> b -> FM k a -> b
foldr
fold' :: forall k a b. Ord k => (a -> b -> b) -> b -> FM k a -> b
fold' = (a -> b -> b) -> b -> FM k a -> b
forall k a b. Ord k => (a -> b -> b) -> b -> FM k a -> b
foldr'

foldr :: forall k a b. Ord k => (a -> b -> b) -> b -> FM k a -> b
foldr a -> b -> b
op b
z (FM Maybe a
n FMB k a
fmb)
  = Maybe a -> b -> b
foldMV Maybe a
n (b -> b) -> (b -> b) -> b -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FMB k a -> b -> b
forall {k}. FMB k a -> b -> b
foldFMB FMB k a
fmb (b -> b) -> b -> b
forall a b. (a -> b) -> a -> b
$ b
z
  where
    foldMV :: Maybe a -> b -> b
foldMV Maybe a
Nothing  = b -> b
forall a. a -> a
id
    foldMV (Just a
v) = a -> b -> b
op a
v

    foldFMB :: FMB k a -> b -> b
foldFMB FMB k a
E
      = b -> b
forall a. a -> a
id
    foldFMB (I Int
_ k
_ Maybe a
v FMB k a
l (FMB' FMB k a
m) FMB k a
r)
      = FMB k a -> b -> b
foldFMB FMB k a
l (b -> b) -> (b -> b) -> b -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Maybe a -> b -> b
foldMV Maybe a
v (b -> b) -> (b -> b) -> b -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FMB k a -> b -> b
foldFMB FMB k a
m (b -> b) -> (b -> b) -> b -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FMB k a -> b -> b
foldFMB FMB k a
r

foldrWithKey :: forall k a b. Ord k => ([k] -> a -> b -> b) -> b -> FM k a -> b
foldrWithKey [k] -> a -> b -> b
f b
z (FM Maybe a
n FMB k a
fmb)
  = [k] -> Maybe a -> b -> b
foldMV [] Maybe a
n (b -> b) -> (b -> b) -> b -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ([k] -> [k]) -> FMB k a -> b -> b
forall {a}. ([a] -> [k]) -> FMB a a -> b -> b
foldFMB [k] -> [k]
forall a. a -> a
id FMB k a
fmb (b -> b) -> b -> b
forall a b. (a -> b) -> a -> b
$ b
z
  where
     foldMV :: [k] -> Maybe a -> b -> b
foldMV [k]
_ Maybe a
Nothing  = b -> b
forall a. a -> a
id
     foldMV [k]
ks (Just a
v) = [k] -> a -> b -> b
f [k]
ks a
v

     foldFMB :: ([a] -> [k]) -> FMB a a -> b -> b
foldFMB [a] -> [k]
_ FMB a a
E = b -> b
forall a. a -> a
id
     foldFMB [a] -> [k]
kf (I Int
_ a
k Maybe a
mv FMB a a
l (FMB' FMB a a
m) FMB a a
r)
       = ([a] -> [k]) -> FMB a a -> b -> b
foldFMB [a] -> [k]
kf FMB a a
l (b -> b) -> (b -> b) -> b -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [k] -> Maybe a -> b -> b
foldMV ([a] -> [k]
kf [a
k]) Maybe a
mv (b -> b) -> (b -> b) -> b -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ([a] -> [k]) -> FMB a a -> b -> b
foldFMB ([a] -> [k]
kf ([a] -> [k]) -> ([a] -> [a]) -> [a] -> [k]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a
ka -> [a] -> [a]
forall a. a -> [a] -> [a]
:)) FMB a a
m (b -> b) -> (b -> b) -> b -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ([a] -> [k]) -> FMB a a -> b -> b
foldFMB [a] -> [k]
kf FMB a a
r

foldlWithKey :: forall k b a. Ord k => (b -> [k] -> a -> b) -> b -> FM k a -> b
foldlWithKey b -> [k] -> a -> b
f b
z (FM Maybe a
n FMB k a
fmb)
  = ([k] -> [k]) -> FMB k a -> b -> b
forall {a}. ([a] -> [k]) -> FMB a a -> b -> b
foldFMB [k] -> [k]
forall a. a -> a
id FMB k a
fmb (b -> b) -> (b -> b) -> b -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [k] -> Maybe a -> b -> b
foldMV [] Maybe a
n (b -> b) -> b -> b
forall a b. (a -> b) -> a -> b
$ b
z
  where
     g :: [k] -> a -> b -> b
g [k]
k a
x b
a = b -> [k] -> a -> b
f b
a [k]
k a
x

     foldMV :: [k] -> Maybe a -> b -> b
foldMV [k]
_ Maybe a
Nothing  = b -> b
forall a. a -> a
id
     foldMV [k]
ks (Just a
v) = [k] -> a -> b -> b
g [k]
ks a
v

     foldFMB :: ([a] -> [k]) -> FMB a a -> b -> b
foldFMB [a] -> [k]
_ FMB a a
E = b -> b
forall a. a -> a
id
     foldFMB [a] -> [k]
kf (I Int
_ a
k Maybe a
mv FMB a a
l (FMB' FMB a a
m) FMB a a
r)
       = ([a] -> [k]) -> FMB a a -> b -> b
foldFMB [a] -> [k]
kf FMB a a
r (b -> b) -> (b -> b) -> b -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ([a] -> [k]) -> FMB a a -> b -> b
foldFMB ([a] -> [k]
kf ([a] -> [k]) -> ([a] -> [a]) -> [a] -> [k]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a
ka -> [a] -> [a]
forall a. a -> [a] -> [a]
:)) FMB a a
m (b -> b) -> (b -> b) -> b -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [k] -> Maybe a -> b -> b
foldMV ([a] -> [k]
kf [a
k]) Maybe a
mv (b -> b) -> (b -> b) -> b -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ([a] -> [k]) -> FMB a a -> b -> b
foldFMB [a] -> [k]
kf FMB a a
l

foldrWithKey' :: forall k a b. Ord k => ([k] -> a -> b -> b) -> b -> FM k a -> b
foldrWithKey' = ([k] -> a -> b -> b) -> b -> FM k a -> b
forall k a b. Ord k => ([k] -> a -> b -> b) -> b -> FM k a -> b
foldrWithKey
foldlWithKey' :: forall k b a. Ord k => (b -> [k] -> a -> b) -> b -> FM k a -> b
foldlWithKey' = (b -> [k] -> a -> b) -> b -> FM k a -> b
forall k b a. Ord k => (b -> [k] -> a -> b) -> b -> FM k a -> b
foldlWithKey

foldl :: (a -> b -> a) -> a -> FM t b -> a
foldl :: forall a b t. (a -> b -> a) -> a -> FM t b -> a
foldl a -> b -> a
op a
z (FM Maybe b
n FMB t b
fmb)
  = FMB t b -> a -> a
forall {k}. FMB k b -> a -> a
foldFMB FMB t b
fmb (a -> a) -> (a -> a) -> a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Maybe b -> a -> a
foldMV Maybe b
n (a -> a) -> a -> a
forall a b. (a -> b) -> a -> b
$ a
z
  where
    foldMV :: Maybe b -> a -> a
foldMV Maybe b
Nothing  = a -> a
forall a. a -> a
id
    foldMV (Just b
v) = ((a -> b -> a) -> b -> a -> a
forall a b c. (a -> b -> c) -> b -> a -> c
flip a -> b -> a
op) b
v

    foldFMB :: FMB k b -> a -> a
foldFMB FMB k b
E = a -> a
forall a. a -> a
id
    foldFMB (I Int
_ k
_ Maybe b
v FMB k b
l (FMB' FMB k b
m) FMB k b
r)
      = FMB k b -> a -> a
foldFMB FMB k b
r (a -> a) -> (a -> a) -> a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FMB k b -> a -> a
foldFMB FMB k b
m (a -> a) -> (a -> a) -> a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Maybe b -> a -> a
foldMV Maybe b
v (a -> a) -> (a -> a) -> a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FMB k b -> a -> a
foldFMB FMB k b
l


-- FIXME, understand this code to strictify it
foldr' :: forall k a b. Ord k => (a -> b -> b) -> b -> FM k a -> b
foldr' = (a -> b -> b) -> b -> FM k a -> b
forall k a b. Ord k => (a -> b -> b) -> b -> FM k a -> b
foldr
foldl' :: (a -> b -> a) -> a -> FM t b -> a
foldl' :: forall a b t. (a -> b -> a) -> a -> FM t b -> a
foldl' = (a -> b -> a) -> a -> FM t b -> a
forall a b t. (a -> b -> a) -> a -> FM t b -> a
foldl

foldr1 :: forall k a. Ord k => (a -> a -> a) -> FM k a -> a
foldr1 a -> a -> a
f FM k a
fm =
  case FM k a -> Maybe (a, FM k a)
forall (m :: * -> *) k a. MonadFail m => FM k a -> m (a, FM k a)
maxView FM k a
fm of
     Just (a
z,FM k a
fm') -> (a -> a -> a) -> a -> FM k a -> a
forall k a b. Ord k => (a -> b -> b) -> b -> FM k a -> b
foldr a -> a -> a
f a
z FM k a
fm'
     Maybe (a, FM k a)
Nothing      -> String -> a
forall a. HasCallStack => String -> a
error (String -> a) -> String -> a
forall a b. (a -> b) -> a -> b
$ String
moduleNameString -> String -> String
forall a. [a] -> [a] -> [a]
++String
".foldr1: empty map"

foldl1 :: (b -> b -> b) -> FM k b -> b
foldl1 :: forall b k. (b -> b -> b) -> FM k b -> b
foldl1 b -> b -> b
f FM k b
fm =
  case FM k b -> Maybe (b, FM k b)
forall (m :: * -> *) k a. MonadFail m => FM k a -> m (a, FM k a)
minView FM k b
fm of
     Just (b
z,FM k b
fm') -> (b -> b -> b) -> b -> FM k b -> b
forall a b t. (a -> b -> a) -> a -> FM t b -> a
foldl b -> b -> b
f b
z FM k b
fm'
     Maybe (b, FM k b)
Nothing      -> String -> b
forall a. HasCallStack => String -> a
error (String -> b) -> String -> b
forall a b. (a -> b) -> a -> b
$ String
moduleNameString -> String -> String
forall a. [a] -> [a] -> [a]
++String
".foldl1: empty map"


basecase :: Maybe t1 -> (t1 -> t) -> t -> t
basecase :: forall t1 t. Maybe t1 -> (t1 -> t) -> t -> t
basecase Maybe t1
Nothing  = \t1 -> t
_ t
n -> t
n
basecase (Just t1
x) = \t1 -> t
j t
_ -> t1 -> t
j t1
x

comb ::                                (t1 -> t1 -> t1)
                                    -> ((t1 -> t2) -> t2 -> t3)
                                    -> ((t1 -> t) -> t -> t2)
                                    -> (t1 -> t)
                                    -> t
                                    -> t3
comb :: forall t1 t2 t3 t.
(t1 -> t1 -> t1)
-> ((t1 -> t2) -> t2 -> t3)
-> ((t1 -> t) -> t -> t2)
-> (t1 -> t)
-> t
-> t3
comb t1 -> t1 -> t1
f (t1 -> t2) -> t2 -> t3
p1 (t1 -> t) -> t -> t2
p2
   = \t1 -> t
j t
n -> (t1 -> t2) -> t2 -> t3
p1 (\t1
x -> (t1 -> t) -> t -> t2
p2 (\t1
y -> t1 -> t
j (t1 -> t1 -> t1
f t1
x t1
y)) (t1 -> t
j t1
x)) ((t1 -> t) -> t -> t2
p2 t1 -> t
j t
n)

fold1 :: forall k a. Ord k => (a -> a -> a) -> FM k a -> a
fold1 a -> a -> a
f (FM Maybe a
mv FMB k a
fmb)
  = (a -> a -> a)
-> ((a -> a) -> a -> a)
-> ((a -> a) -> a -> a)
-> (a -> a)
-> a
-> a
forall t1 t2 t3 t.
(t1 -> t1 -> t1)
-> ((t1 -> t2) -> t2 -> t3)
-> ((t1 -> t) -> t -> t2)
-> (t1 -> t)
-> t
-> t3
comb a -> a -> a
f (Maybe a -> (a -> a) -> a -> a
forall t1 t. Maybe t1 -> (t1 -> t) -> t -> t
basecase Maybe a
mv) (FMB k a -> (a -> a) -> a -> a
forall {k} {t2}. FMB k a -> (a -> t2) -> t2 -> t2
fold1FMB FMB k a
fmb) a -> a
forall a. a -> a
id (String -> a
forall a. HasCallStack => String -> a
error (String -> a) -> String -> a
forall a b. (a -> b) -> a -> b
$ String
moduleNameString -> String -> String
forall a. [a] -> [a] -> [a]
++String
".fold1: empty map")
  where
      fold1FMB :: FMB k a -> (a -> t2) -> t2 -> t2
fold1FMB FMB k a
E
        = \a -> t2
_ t2
n -> t2
n
      fold1FMB (I Int
_ k
_ Maybe a
mv FMB k a
l (FMB' FMB k a
m) FMB k a
r)
        = (a -> a -> a)
-> ((a -> t2) -> t2 -> t2)
-> ((a -> t2) -> t2 -> t2)
-> (a -> t2)
-> t2
-> t2
forall t1 t2 t3 t.
(t1 -> t1 -> t1)
-> ((t1 -> t2) -> t2 -> t3)
-> ((t1 -> t) -> t -> t2)
-> (t1 -> t)
-> t
-> t3
comb a -> a -> a
f (Maybe a -> (a -> t2) -> t2 -> t2
forall t1 t. Maybe t1 -> (t1 -> t) -> t -> t
basecase Maybe a
mv) (((a -> t2) -> t2 -> t2) -> (a -> t2) -> t2 -> t2)
-> ((a -> t2) -> t2 -> t2) -> (a -> t2) -> t2 -> t2
forall a b. (a -> b) -> a -> b
$ (a -> a -> a)
-> ((a -> t2) -> t2 -> t2)
-> ((a -> t2) -> t2 -> t2)
-> (a -> t2)
-> t2
-> t2
forall t1 t2 t3 t.
(t1 -> t1 -> t1)
-> ((t1 -> t2) -> t2 -> t3)
-> ((t1 -> t) -> t -> t2)
-> (t1 -> t)
-> t
-> t3
comb a -> a -> a
f (FMB k a -> (a -> t2) -> t2 -> t2
fold1FMB FMB k a
l) (((a -> t2) -> t2 -> t2) -> (a -> t2) -> t2 -> t2)
-> ((a -> t2) -> t2 -> t2) -> (a -> t2) -> t2 -> t2
forall a b. (a -> b) -> a -> b
$ (a -> a -> a)
-> ((a -> t2) -> t2 -> t2)
-> ((a -> t2) -> t2 -> t2)
-> (a -> t2)
-> t2
-> t2
forall t1 t2 t3 t.
(t1 -> t1 -> t1)
-> ((t1 -> t2) -> t2 -> t3)
-> ((t1 -> t) -> t -> t2)
-> (t1 -> t)
-> t
-> t3
comb a -> a -> a
f (FMB k a -> (a -> t2) -> t2 -> t2
fold1FMB FMB k a
m) (((a -> t2) -> t2 -> t2) -> (a -> t2) -> t2 -> t2)
-> ((a -> t2) -> t2 -> t2) -> (a -> t2) -> t2 -> t2
forall a b. (a -> b) -> a -> b
$ (FMB k a -> (a -> t2) -> t2 -> t2
fold1FMB FMB k a
r)

fold1' :: forall k a. Ord k => (a -> a -> a) -> FM k a -> a
fold1' = (a -> a -> a) -> FM k a -> a
forall k a. Ord k => (a -> a -> a) -> FM k a -> a
fold1

{-
FIXME -- can these be somehow fixed to have the right order...

foldr1 f (FM v fmb)
  = comb f (basecase v) (fold1FMB fmb) id (error $ moduleName++".foldr1: empty map")
  where
      fold1FMB E
        = \j n -> n
      fold1FMB (I _ _ v l (FMB' m) r)
        = comb f (fold1FMB l) $ comb f (basecase v) $ comb f (fold1FMB m) $ (fold1FMB r)


foldl1 f (FM v fmb)
  = comb f (fold1FMB fmb) (basecase v) id (error $ moduleName++".foldl1: empty map")
  where
      fold1FMB E
        = \j n -> n
      fold1FMB (I _ _ v l (FMB' m) r)
        = comb f (fold1FMB r) $ comb f (fold1FMB m) $ comb f (basecase v) $ (fold1FMB l)
-}



-- FIXME, understand this code to strictify it
foldr1' :: forall k a. Ord k => (a -> a -> a) -> FM k a -> a
foldr1' = (a -> a -> a) -> FM k a -> a
forall k a. Ord k => (a -> a -> a) -> FM k a -> a
foldr1
foldl1' :: (b -> b -> b) -> FM k b -> b
foldl1' :: forall b k. (b -> b -> b) -> FM k b -> b
foldl1' = (b -> b -> b) -> FM k b -> b
forall b k. (b -> b -> b) -> FM k b -> b
foldl1


filter :: forall k a. Ord k => (a -> Bool) -> FM k a -> FM k a
filter a -> Bool
p = (Maybe a -> Maybe a) -> FM k a -> FM k a
forall a b k. (Maybe a -> Maybe b) -> FM k a -> FM k b
mapVFM (\Maybe a
mv -> case Maybe a
mv of
                            Maybe a
Nothing -> Maybe a
mv
                            Just a
v  -> if a -> Bool
p a
v then Maybe a
mv else Maybe a
forall a. Maybe a
Nothing)

partition :: forall k a. Ord k => (a -> Bool) -> FM k a -> (FM k a, FM k a)
partition = (a -> Bool) -> FM k a -> (FM k a, FM k a)
forall (m :: * -> *) k a.
AssocX m k =>
(a -> Bool) -> m a -> (m a, m a)
partitionUsingFilter

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

strict :: forall k a. FM k a -> FM k a
strict z :: FM k a
z@(FM Maybe a
_ FMB k a
fmb) = FMB k a -> FMB k a
forall {k} {v}. FMB k v -> FMB k v
strictFMB FMB k a
fmb FMB k a -> FM k a -> FM k a
forall a b. a -> b -> b
`seq` FM k a
z
 where strictFMB :: FMB k v -> FMB k v
strictFMB n :: FMB k v
n@FMB k v
E = FMB k v
n
       strictFMB n :: FMB k v
n@(I Int
_ k
_ Maybe v
_ FMB k v
l (FMB' FMB k v
m) FMB k v
r) =
           FMB k v -> FMB k v
strictFMB FMB k v
l FMB k v -> FMB k v -> FMB k v
forall a b. a -> b -> b
`seq` FMB k v -> FMB k v
strictFMB FMB k v
m FMB k v -> FMB k v -> FMB k v
forall a b. a -> b -> b
`seq` FMB k v -> FMB k v
strictFMB FMB k v
r FMB k v -> FMB k v -> FMB k v
forall a b. a -> b -> b
`seq` FMB k v
n

strictWith :: forall a b k. (a -> b) -> FM k a -> FM k a
strictWith a -> b
f z :: FM k a
z@(FM Maybe a
v FMB k a
fmb) = Maybe a -> Maybe a
f' Maybe a
v Maybe a -> FM k a -> FM k a
forall a b. a -> b -> b
`seq` FMB k a -> FMB k a
forall {k}. FMB k a -> FMB k a
strictWithFMB FMB k a
fmb FMB k a -> FM k a -> FM k a
forall a b. a -> b -> b
`seq` FM k a
z
   where f' :: Maybe a -> Maybe a
f' v :: Maybe a
v@Maybe a
Nothing  = Maybe a
v
         f' v :: Maybe a
v@(Just a
x) = a -> b
f a
x b -> Maybe a -> Maybe a
forall a b. a -> b -> b
`seq` Maybe a
v

         strictWithFMB :: FMB k a -> FMB k a
strictWithFMB n :: FMB k a
n@FMB k a
E = FMB k a
n
         strictWithFMB n :: FMB k a
n@(I Int
_ k
_ Maybe a
v FMB k a
l (FMB' FMB k a
m) FMB k a
r) =
           Maybe a -> Maybe a
f' Maybe a
v Maybe a -> FMB k a -> FMB k a
forall a b. a -> b -> b
`seq` FMB k a -> FMB k a
strictWithFMB FMB k a
l FMB k a -> FMB k a -> FMB k a
forall a b. a -> b -> b
`seq` FMB k a -> FMB k a
strictWithFMB FMB k a
m FMB k a -> FMB k a -> FMB k a
forall a b. a -> b -> b
`seq` FMB k a -> FMB k a
strictWithFMB FMB k a
r FMB k a -> FMB k a -> FMB k a
forall a b. a -> b -> b
`seq` FMB k a
n


-- FiniteMapX

fromSeqWith :: forall k (seq :: * -> *) a.
(Ord k, Sequence seq) =>
(a -> a -> a) -> seq ([k], a) -> FM k a
fromSeqWith = (a -> a -> a) -> seq ([k], a) -> FM k a
forall (m :: * -> *) k (seq :: * -> *) a.
(FiniteMapX m k, Sequence seq) =>
(a -> a -> a) -> seq (k, a) -> m a
fromSeqWithUsingInsertSeqWith

fromSeqWithKey :: forall k (seq :: * -> *) a.
(Ord k, Sequence seq) =>
([k] -> a -> a -> a) -> seq ([k], a) -> FM k a
fromSeqWithKey = ([k] -> a -> a -> a) -> seq ([k], a) -> FM k a
forall (m :: * -> *) k (seq :: * -> *) a.
(FiniteMapX m k, Sequence seq) =>
(k -> a -> a -> a) -> seq (k, a) -> m a
fromSeqWithKeyUsingInsertSeqWithKey

insertWith :: forall k a. Ord k => (a -> a -> a) -> [k] -> a -> FM k a -> FM k a
insertWith a -> a -> a
f [k]
k a
v
  = [k] -> (Maybe a -> Maybe a) -> FM k a -> FM k a
forall k v.
Ord k =>
[k] -> (Maybe v -> Maybe v) -> FM k v -> FM k v
addToFM [k]
k (\Maybe a
vem ->
      case Maybe a
vem of
          Maybe a
Nothing -> a -> Maybe a
forall a. a -> Maybe a
Just a
v
          Just a
ve -> a -> Maybe a
forall a. a -> Maybe a
Just (a -> a -> a
f a
ve a
v))

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

insertSeqWith :: forall k (seq :: * -> *) a.
(Ord k, Sequence seq) =>
(a -> a -> a) -> seq ([k], a) -> FM k a -> FM k a
insertSeqWith = (a -> a -> a) -> seq ([k], a) -> FM k a -> FM k a
forall (m :: * -> *) k (seq :: * -> *) a.
(FiniteMapX m k, Sequence seq) =>
(a -> a -> a) -> seq (k, a) -> m a -> m a
insertSeqWithUsingInsertWith

insertSeqWithKey :: forall k (seq :: * -> *) a.
(Ord k, Sequence seq) =>
([k] -> a -> a -> a) -> seq ([k], a) -> FM k a -> FM k a
insertSeqWithKey = ([k] -> a -> a -> a) -> seq ([k], a) -> FM k a -> FM k a
forall (m :: * -> *) k (seq :: * -> *) a.
(FiniteMapX m k, Sequence seq) =>
(k -> a -> a -> a) -> seq (k, a) -> m a -> m a
insertSeqWithKeyUsingInsertWithKey

unionl :: forall k a. Ord k => FM k a -> FM k a -> FM k a
unionl = FM k a -> FM k a -> FM k a
forall k a. Ord k => FM k a -> FM k a -> FM k a
union
unionr :: forall k a. Ord k => FM k a -> FM k a -> FM k a
unionr = (FM k a -> FM k a -> FM k a) -> FM k a -> FM k a -> FM k a
forall a b c. (a -> b -> c) -> b -> a -> c
flip FM k a -> FM k a -> FM k a
forall k a. Ord k => FM k a -> FM k a -> FM k a
union

unionWith :: forall k a. Ord k => (a -> a -> a) -> FM k a -> FM k a -> FM k a
unionWith a -> a -> a
f = ([k] -> a -> a -> a) -> FM k a -> FM k a -> FM k a
forall k a.
Ord k =>
([k] -> a -> a -> a) -> FM k a -> FM k a -> FM k a
unionWithKey ((a -> a -> a) -> [k] -> a -> a -> a
forall a b. a -> b -> a
const a -> a -> a
f)

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

intersectionWith :: forall k a b c.
Ord k =>
(a -> b -> c) -> FM k a -> FM k b -> FM k c
intersectionWith a -> b -> c
f = ([k] -> a -> b -> c) -> FM k a -> FM k b -> FM k c
forall k a b c.
Ord k =>
([k] -> a -> b -> c) -> FM k a -> FM k b -> FM k c
intersectionWithKey ((a -> b -> c) -> [k] -> a -> b -> c
forall a b. a -> b -> a
const a -> b -> c
f)

difference :: forall k a b. Ord k => FM k a -> FM k b -> FM k a
difference FM k a
mx FM k b
my
  = (Maybe a -> Maybe b -> Maybe a) -> FM k a -> FM k b -> FM k a
forall k a b c.
Ord k =>
(Maybe a -> Maybe b -> Maybe c) -> FM k a -> FM k b -> FM k c
mergeVFM (\Maybe a
v1 Maybe b
v2 -> case Maybe b
v2 of
              Maybe b
Nothing -> Maybe a
v1
              Just b
_  -> Maybe a
forall a. Maybe a
Nothing) FM k a
mx FM k b
my

properSubset :: forall k a b. Ord k => FM k a -> FM k b -> Bool
properSubset = FM k a -> FM k b -> Bool
forall (m :: * -> *) k a b. FiniteMapX m k => m a -> m b -> Bool
properSubsetUsingSubset

subset :: forall k a b. Ord k => FM k a -> FM k b -> Bool
subset (FM Maybe a
nx FMB k a
fmbx) (FM Maybe b
ny FMB k b
fmby)
  = Maybe a -> Maybe b -> Bool
forall {a} {a}. Maybe a -> Maybe a -> Bool
subsetEqM Maybe a
nx Maybe b
ny Bool -> Bool -> Bool
&& FMB k a -> FMB k b -> Bool
forall {k} {a} {a}. Ord k => FMB k a -> FMB k a -> Bool
subsetEqFMB FMB k a
fmbx FMB k b
fmby
  where
    subsetEqM :: Maybe a -> Maybe a -> Bool
subsetEqM Maybe a
Nothing Maybe a
_ = Bool
True
    subsetEqM (Just a
_) Maybe a
Nothing = Bool
False
    subsetEqM (Just a
_) (Just a
_) = Bool
True

    subsetEqFMB :: FMB k a -> FMB k a -> Bool
subsetEqFMB FMB k a
E FMB k a
_ = Bool
True
    subsetEqFMB fmbx :: FMB k a
fmbx@(I Int
_ k
_ Maybe a
_ FMB k a
_ FMB' k a
_ FMB k a
_) FMB k a
E
      = FMB k a -> Bool
forall k v. FMB k v -> Bool
nullFMB FMB k a
fmbx
    subsetEqFMB fmbx :: FMB k a
fmbx@(I Int
sizex k
kx Maybe a
vx FMB k a
lx (FMB' FMB k a
mx) FMB k a
rx)
            fmby :: FMB k a
fmby@(I Int
sizey k
ky Maybe a
vy FMB k a
ly (FMB' FMB k a
my) FMB k a
ry)
      | Int
sizex Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
sizey
        = let (Maybe a
vy, FMB k a
ly, FMB' FMB k a
my, FMB k a
ry) = k -> FMB k a -> (Maybe a, FMB k a, FMB' k a, FMB k a)
forall k a.
Ord k =>
k -> FMB k a -> (Maybe a, FMB k a, FMB' k a, FMB k a)
splayFMB k
kx FMB k a
fmby
          in    Maybe a -> Maybe a -> Bool
forall {a} {a}. Maybe a -> Maybe a -> Bool
subsetEqM Maybe a
vx Maybe a
vy
             Bool -> Bool -> Bool
&& FMB k a -> FMB k a -> Bool
subsetEqFMB FMB k a
lx FMB k a
ly
             Bool -> Bool -> Bool
&& FMB k a -> FMB k a -> Bool
subsetEqFMB FMB k a
mx FMB k a
my
             Bool -> Bool -> Bool
&& FMB k a -> FMB k a -> Bool
subsetEqFMB FMB k a
rx FMB k a
ry
      | Bool
otherwise
        = let (Maybe a
vx, FMB k a
lx, FMB' FMB k a
mx, FMB k a
rx) = k -> FMB k a -> (Maybe a, FMB k a, FMB' k a, FMB k a)
forall k a.
Ord k =>
k -> FMB k a -> (Maybe a, FMB k a, FMB' k a, FMB k a)
splayFMB k
ky FMB k a
fmbx
          in    Maybe a -> Maybe a -> Bool
forall {a} {a}. Maybe a -> Maybe a -> Bool
subsetEqM Maybe a
vx Maybe a
vy
             Bool -> Bool -> Bool
&& FMB k a -> FMB k a -> Bool
subsetEqFMB FMB k a
lx FMB k a
ly
             Bool -> Bool -> Bool
&& FMB k a -> FMB k a -> Bool
subsetEqFMB FMB k a
mx FMB k a
my
             Bool -> Bool -> Bool
&& FMB k a -> FMB k a -> Bool
subsetEqFMB FMB k a
rx FMB k a
ry


submapBy :: forall k a. Ord k => (a -> a -> Bool) -> FM k a -> FM k a -> Bool
submapBy = (a -> a -> Bool) -> FM k a -> FM k a -> Bool
forall (m :: * -> *) k a.
FiniteMap m k =>
(a -> a -> Bool) -> m a -> m a -> Bool
submapByUsingLookupM
properSubmapBy :: forall k a. Ord k => (a -> a -> Bool) -> FM k a -> FM k a -> Bool
properSubmapBy = (a -> a -> Bool) -> FM k a -> FM k a -> Bool
forall (m :: * -> *) k a.
FiniteMapX m k =>
(a -> a -> Bool) -> m a -> m a -> Bool
properSubmapByUsingSubmapBy
sameMapBy :: forall k a. Ord k => (a -> a -> Bool) -> FM k a -> FM k a -> Bool
sameMapBy = (a -> a -> Bool) -> FM k a -> FM k a -> Bool
forall (m :: * -> *) k a.
FiniteMapX m k =>
(a -> a -> Bool) -> m a -> m a -> Bool
sameMapByUsingSubmapBy
properSubmap :: forall k a. (Ord k, Eq a) => FM k a -> FM k a -> Bool
properSubmap = FM k a -> FM k a -> Bool
forall a (m :: * -> *) k.
(Eq a, FiniteMapX m k) =>
m a -> m a -> Bool
A.properSubmap
submap :: forall k a. (Ord k, Eq a) => FM k a -> FM k a -> Bool
submap = FM k a -> FM k a -> Bool
forall a (m :: * -> *) k.
(Eq a, FiniteMapX m k) =>
m a -> m a -> Bool
A.submap
sameMap :: forall k a. (Ord k, Eq a) => FM k a -> FM k a -> Bool
sameMap = FM k a -> FM k a -> Bool
forall a (m :: * -> *) k.
(Eq a, FiniteMapX m k) =>
m a -> m a -> Bool
A.sameMap

-- Assoc

toSeq :: forall k (seq :: * -> *) a.
(Ord k, Sequence seq) =>
FM k a -> seq ([k], a)
toSeq = FM k a -> seq ([k], a)
forall (m :: * -> *) k (seq :: * -> *) a.
(Assoc m k, Sequence seq) =>
m a -> seq (k, a)
toSeqUsingFoldWithKey

keys :: forall k (seq :: * -> *) a.
(Ord k, Sequence seq) =>
FM k a -> seq [k]
keys = FM k a -> seq [k]
forall (m :: * -> *) k (seq :: * -> *) a.
(Assoc m k, Sequence seq) =>
m a -> seq k
keysUsingFoldWithKey

mapWithKey :: forall k a b. Ord k => ([k] -> a -> b) -> FM k a -> FM k b
mapWithKey [k] -> a -> b
f
  = ([k] -> Maybe a -> Maybe b) -> FM k a -> FM k b
forall k a b. ([k] -> Maybe a -> Maybe b) -> FM k a -> FM k b
mapKVFM (\[k]
k Maybe a
mv -> case Maybe a
mv of
          Maybe a
Nothing -> Maybe b
forall a. Maybe a
Nothing
          Just a
v  -> b -> Maybe b
forall a. a -> Maybe a
Just ([k] -> a -> b
f [k]
k a
v))

foldWithKey :: forall k a b. Ord k => ([k] -> a -> b -> b) -> b -> FM k a -> b
foldWithKey [k] -> a -> b -> b
op b
r (FM Maybe a
n FMB k a
fmb)
  = [k] -> Maybe a -> b -> b
foldWithKeyB [] Maybe a
n (b -> b) -> (b -> b) -> b -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [k] -> FMB k a -> b -> b
foldWithKeyFM [] FMB k a
fmb (b -> b) -> b -> b
forall a b. (a -> b) -> a -> b
$ b
r
  where
      foldWithKeyB :: [k] -> Maybe a -> b -> b
foldWithKeyB [k]
_ Maybe a
Nothing = b -> b
forall a. a -> a
id
      foldWithKeyB [k]
k (Just a
v) = [k] -> a -> b -> b
op [k]
k a
v

      foldWithKeyFM :: [k] -> FMB k a -> b -> b
foldWithKeyFM [k]
_ FMB k a
E = b -> b
forall a. a -> a
id
      foldWithKeyFM [k]
ks (I Int
_ k
k Maybe a
v FMB k a
l (FMB' FMB k a
m) FMB k a
r)
        = [k] -> FMB k a -> b -> b
foldWithKeyFM [k]
ks FMB k a
l
        (b -> b) -> (b -> b) -> b -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [k] -> Maybe a -> b -> b
foldWithKeyB ([k] -> [k]
forall a. [a] -> [a]
reverse (k
kk -> [k] -> [k]
forall a. a -> [a] -> [a]
:[k]
ks)) Maybe a
v
        (b -> b) -> (b -> b) -> b -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [k] -> FMB k a -> b -> b
foldWithKeyFM (k
kk -> [k] -> [k]
forall a. a -> [a] -> [a]
:[k]
ks) FMB k a
m
        (b -> b) -> (b -> b) -> b -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [k] -> FMB k a -> b -> b
foldWithKeyFM [k]
ks FMB k a
r


-- FIXME, make this strict
foldWithKey' :: forall k a b. Ord k => ([k] -> a -> b -> b) -> b -> FM k a -> b
foldWithKey' = ([k] -> a -> b -> b) -> b -> FM k a -> b
forall k a b. Ord k => ([k] -> a -> b -> b) -> b -> FM k a -> b
foldWithKey


filterWithKey :: forall k a. Ord k => ([k] -> a -> Bool) -> FM k a -> FM k a
filterWithKey [k] -> a -> Bool
f
  = ([k] -> Maybe a -> Maybe a) -> FM k a -> FM k a
forall k a b. ([k] -> Maybe a -> Maybe b) -> FM k a -> FM k b
mapKVFM (\[k]
k Maybe a
mv -> case Maybe a
mv of
          Maybe a
Nothing -> Maybe a
mv
          Just a
v  -> if [k] -> a -> Bool
f [k]
k a
v then Maybe a
mv else Maybe a
forall a. Maybe a
Nothing)

partitionWithKey :: forall k a.
Ord k =>
([k] -> a -> Bool) -> FM k a -> (FM k a, FM k a)
partitionWithKey [k] -> a -> Bool
f FM k a
m
  = (([k] -> a -> Bool) -> FM k a -> FM k a
forall k a. Ord k => ([k] -> a -> Bool) -> FM k a -> FM k a
filterWithKey [k] -> a -> Bool
f FM k a
m, ([k] -> a -> Bool) -> FM k a -> FM k a
forall k a. Ord k => ([k] -> a -> Bool) -> FM k a -> FM k a
filterWithKey (\[k]
k a
v -> Bool -> Bool
not ([k] -> a -> Bool
f [k]
k a
v)) FM k a
m)

-- FiniteMap

unionWithKey :: forall k a.
Ord k =>
([k] -> a -> a -> a) -> FM k a -> FM k a -> FM k a
unionWithKey [k] -> a -> a -> a
f
  = ([k] -> Maybe a -> Maybe a -> Maybe a)
-> FM k a -> FM k a -> FM k a
forall k a b c.
Ord k =>
([k] -> Maybe a -> Maybe b -> Maybe c)
-> FM k a -> FM k b -> FM k c
mergeKVFM (\[k]
k Maybe a
v1m Maybe a
v2m ->
    case Maybe a
v1m of
        Maybe a
Nothing -> Maybe a
v2m
        Just a
v1 ->
            case Maybe a
v2m of
            Maybe a
Nothing -> Maybe a
v1m
            Just a
v2 -> a -> Maybe a
forall a. a -> Maybe a
Just ([k] -> a -> a -> a
f [k]
k a
v1 a
v2))

unionSeqWithKey :: forall k (seq :: * -> *) a.
(Ord k, Sequence seq) =>
([k] -> a -> a -> a) -> seq (FM k a) -> FM k a
unionSeqWithKey = ([k] -> a -> a -> a) -> seq (FM k a) -> FM k a
forall (m :: * -> *) k (seq :: * -> *) a.
(FiniteMap m k, Sequence seq) =>
(k -> a -> a -> a) -> seq (m a) -> m a
unionSeqWithKeyUsingReduce

intersectionWithKey :: forall k a b c.
Ord k =>
([k] -> a -> b -> c) -> FM k a -> FM k b -> FM k c
intersectionWithKey [k] -> a -> b -> c
f
  = ([k] -> Maybe a -> Maybe b -> Maybe c)
-> FM k a -> FM k b -> FM k c
forall k a b c.
Ord k =>
([k] -> Maybe a -> Maybe b -> Maybe c)
-> FM k a -> FM k b -> FM k c
mergeKVFM (\[k]
k Maybe a
v1m Maybe b
v2m ->
    case Maybe a
v1m of
        Maybe a
Nothing -> Maybe c
forall a. Maybe a
Nothing
        Just a
v1 ->
            case Maybe b
v2m of
            Maybe b
Nothing -> Maybe c
forall a. Maybe a
Nothing
            Just b
v2 -> c -> Maybe c
forall a. a -> Maybe a
Just ([k] -> a -> b -> c
f [k]
k a
v1 b
v2))

-- OrdAssocX

minViewFMB :: Fail.MonadFail m => FMB k a -> (FMB k a -> FM k a) -> m (a, FM k a)
minViewFMB :: forall (m :: * -> *) k a.
MonadFail m =>
FMB k a -> (FMB k a -> FM k a) -> m (a, FM k a)
minViewFMB FMB k a
E FMB k a -> FM k a
_ = String -> m (a, FM k a)
forall a. String -> m a
forall (m :: * -> *) a. MonadFail m => String -> m a
fail (String -> m (a, FM k a)) -> String -> m (a, FM k a)
forall a b. (a -> b) -> a -> b
$ String
moduleNameString -> String -> String
forall a. [a] -> [a] -> [a]
++String
".minView: empty map"
minViewFMB (I Int
i k
k (Just a
v) FMB k a
E FMB' k a
m FMB k a
r)        FMB k a -> FM k a
f = (a, FM k a) -> m (a, FM k a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (a
v, FMB k a -> FM k a
f (Int -> k -> Maybe a -> FMB k a -> FMB' k a -> FMB k a -> FMB k a
forall k v.
Int -> k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
I Int
i k
k Maybe a
forall a. Maybe a
Nothing FMB k a
forall k v. FMB k v
E FMB' k a
m FMB k a
r))
minViewFMB (I Int
_ k
_ Maybe a
Nothing  FMB k a
E (FMB' FMB k a
E) FMB k a
_) FMB k a -> FM k a
_ = String -> m (a, FM k a)
forall a. HasCallStack => String -> a
error (String -> m (a, FM k a)) -> String -> m (a, FM k a)
forall a b. (a -> b) -> a -> b
$ String
moduleNameString -> String -> String
forall a. [a] -> [a] -> [a]
++String
".minView: bug!"
minViewFMB (I Int
_ k
k Maybe a
Nothing  FMB k a
E (FMB' FMB k a
m) FMB k a
r) FMB k a -> FM k a
f = FMB k a -> (FMB k a -> FM k a) -> m (a, FM k a)
forall (m :: * -> *) k a.
MonadFail m =>
FMB k a -> (FMB k a -> FM k a) -> m (a, FM k a)
minViewFMB FMB k a
m (\FMB k a
m' -> FMB k a -> FM k a
f (k -> Maybe a -> FMB k a -> FMB' k a -> FMB k a -> FMB k a
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkVBalancedFMB k
k Maybe a
forall a. Maybe a
Nothing FMB k a
forall k v. FMB k v
E (FMB k a -> FMB' k a
forall k v. FMB k v -> FMB' k v
FMB' FMB k a
m') FMB k a
r))
minViewFMB (I Int
_ k
k Maybe a
mv FMB k a
l FMB' k a
m FMB k a
r)              FMB k a -> FM k a
f = FMB k a -> (FMB k a -> FM k a) -> m (a, FM k a)
forall (m :: * -> *) k a.
MonadFail m =>
FMB k a -> (FMB k a -> FM k a) -> m (a, FM k a)
minViewFMB FMB k a
l (\FMB k a
l' -> FMB k a -> FM k a
f (k -> Maybe a -> FMB k a -> FMB' k a -> FMB k a -> FMB k a
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkVBalancedFMB k
k Maybe a
mv FMB k a
l' FMB' k a
m FMB k a
r))

minView :: Fail.MonadFail m => FM k a -> m (a,FM k a)
minView :: forall (m :: * -> *) k a. MonadFail m => FM k a -> m (a, FM k a)
minView (FM (Just a
v) FMB k a
fmb) = (a, FM k a) -> m (a, FM k a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (a
v, Maybe a -> FMB k a -> FM k a
forall k a. Maybe a -> FMB k a -> FM k a
FM Maybe a
forall a. Maybe a
Nothing FMB k a
fmb)
minView (FM Maybe a
Nothing FMB k a
fmb)  = FMB k a -> (FMB k a -> FM k a) -> m (a, FM k a)
forall (m :: * -> *) k a.
MonadFail m =>
FMB k a -> (FMB k a -> FM k a) -> m (a, FM k a)
minViewFMB FMB k a
fmb (Maybe a -> FMB k a -> FM k a
forall k a. Maybe a -> FMB k a -> FM k a
FM Maybe a
forall a. Maybe a
Nothing)

minViewWithKeyFMB :: Fail.MonadFail m => FMB k a -> ([k] -> [k]) -> (FMB k a -> FM k a) -> m (([k],a),FM k a)
minViewWithKeyFMB :: forall (m :: * -> *) k a.
MonadFail m =>
FMB k a
-> ([k] -> [k]) -> (FMB k a -> FM k a) -> m (([k], a), FM k a)
minViewWithKeyFMB FMB k a
E [k] -> [k]
_ FMB k a -> FM k a
_ = String -> m (([k], a), FM k a)
forall a. String -> m a
forall (m :: * -> *) a. MonadFail m => String -> m a
fail (String -> m (([k], a), FM k a)) -> String -> m (([k], a), FM k a)
forall a b. (a -> b) -> a -> b
$ String
moduleNameString -> String -> String
forall a. [a] -> [a] -> [a]
++String
".minView: empty map"
minViewWithKeyFMB (I Int
i k
k (Just a
v) FMB k a
E FMB' k a
m FMB k a
r)        [k] -> [k]
kf FMB k a -> FM k a
f = (([k], a), FM k a) -> m (([k], a), FM k a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (([k] -> [k]
kf [k
k],a
v),FMB k a -> FM k a
f (Int -> k -> Maybe a -> FMB k a -> FMB' k a -> FMB k a -> FMB k a
forall k v.
Int -> k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
I Int
i k
k Maybe a
forall a. Maybe a
Nothing FMB k a
forall k v. FMB k v
E FMB' k a
m FMB k a
r))
minViewWithKeyFMB (I Int
_ k
_ Maybe a
Nothing  FMB k a
E (FMB' FMB k a
E) FMB k a
_) [k] -> [k]
_ FMB k a -> FM k a
_ = String -> m (([k], a), FM k a)
forall a. HasCallStack => String -> a
error (String -> m (([k], a), FM k a)) -> String -> m (([k], a), FM k a)
forall a b. (a -> b) -> a -> b
$ String
moduleNameString -> String -> String
forall a. [a] -> [a] -> [a]
++String
".minViewWithKey: bug!"
minViewWithKeyFMB (I Int
_ k
k Maybe a
Nothing  FMB k a
E (FMB' FMB k a
m) FMB k a
r) [k] -> [k]
kf FMB k a -> FM k a
f = FMB k a
-> ([k] -> [k]) -> (FMB k a -> FM k a) -> m (([k], a), FM k a)
forall (m :: * -> *) k a.
MonadFail m =>
FMB k a
-> ([k] -> [k]) -> (FMB k a -> FM k a) -> m (([k], a), FM k a)
minViewWithKeyFMB FMB k a
m ([k] -> [k]
kf ([k] -> [k]) -> ([k] -> [k]) -> [k] -> [k]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k
kk -> [k] -> [k]
forall a. a -> [a] -> [a]
:))
                                                        (\FMB k a
m' -> FMB k a -> FM k a
f (k -> Maybe a -> FMB k a -> FMB' k a -> FMB k a -> FMB k a
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkVBalancedFMB k
k Maybe a
forall a. Maybe a
Nothing FMB k a
forall k v. FMB k v
E (FMB k a -> FMB' k a
forall k v. FMB k v -> FMB' k v
FMB' FMB k a
m') FMB k a
r))
minViewWithKeyFMB (I Int
_ k
k Maybe a
mv FMB k a
l FMB' k a
m FMB k a
r)              [k] -> [k]
kf FMB k a -> FM k a
f = FMB k a
-> ([k] -> [k]) -> (FMB k a -> FM k a) -> m (([k], a), FM k a)
forall (m :: * -> *) k a.
MonadFail m =>
FMB k a
-> ([k] -> [k]) -> (FMB k a -> FM k a) -> m (([k], a), FM k a)
minViewWithKeyFMB FMB k a
l [k] -> [k]
kf
                                                        (\FMB k a
l' -> FMB k a -> FM k a
f (k -> Maybe a -> FMB k a -> FMB' k a -> FMB k a -> FMB k a
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkVBalancedFMB k
k Maybe a
mv FMB k a
l' FMB' k a
m FMB k a
r))

minViewWithKey :: Fail.MonadFail m => FM k a -> m (([k],a),FM k a)
minViewWithKey :: forall (m :: * -> *) k a.
MonadFail m =>
FM k a -> m (([k], a), FM k a)
minViewWithKey (FM (Just a
v) FMB k a
fmb) = (([k], a), FM k a) -> m (([k], a), FM k a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (([],a
v),Maybe a -> FMB k a -> FM k a
forall k a. Maybe a -> FMB k a -> FM k a
FM Maybe a
forall a. Maybe a
Nothing FMB k a
fmb)
minViewWithKey (FM Maybe a
Nothing FMB k a
fmb)  = FMB k a
-> ([k] -> [k]) -> (FMB k a -> FM k a) -> m (([k], a), FM k a)
forall (m :: * -> *) k a.
MonadFail m =>
FMB k a
-> ([k] -> [k]) -> (FMB k a -> FM k a) -> m (([k], a), FM k a)
minViewWithKeyFMB FMB k a
fmb [k] -> [k]
forall a. a -> a
id (Maybe a -> FMB k a -> FM k a
forall k a. Maybe a -> FMB k a -> FM k a
FM Maybe a
forall a. Maybe a
Nothing)


minElemFMB :: FMB k a -> a
minElemFMB :: forall k a. FMB k a -> a
minElemFMB FMB k a
E = String -> a
forall a. HasCallStack => String -> a
error (String -> a) -> String -> a
forall a b. (a -> b) -> a -> b
$ String
moduleNameString -> String -> String
forall a. [a] -> [a] -> [a]
++String
".minElem: empty map"
minElemFMB (I Int
_ k
_ (Just a
v) FMB k a
E FMB' k a
_ FMB k a
_)        = a
v
minElemFMB (I Int
_ k
_ Maybe a
Nothing  FMB k a
E (FMB' FMB k a
m) FMB k a
_) = FMB k a -> a
forall k a. FMB k a -> a
minElemFMB FMB k a
m
minElemFMB (I Int
_ k
_ Maybe a
_ FMB k a
l FMB' k a
_ FMB k a
_)              = FMB k a -> a
forall k a. FMB k a -> a
minElemFMB FMB k a
l

minElem :: FM t1 t -> t
minElem :: forall t1 t. FM t1 t -> t
minElem (FM (Just t
v) FMB t1 t
_) = t
v
minElem (FM Maybe t
Nothing  FMB t1 t
fmb) = FMB t1 t -> t
forall k a. FMB k a -> a
minElemFMB FMB t1 t
fmb


minElemWithKeyFMB :: ([k] -> [k]) -> FMB k a -> ([k],a)
minElemWithKeyFMB :: forall k a. ([k] -> [k]) -> FMB k a -> ([k], a)
minElemWithKeyFMB [k] -> [k]
_ FMB k a
E = String -> ([k], a)
forall a. HasCallStack => String -> a
error (String -> ([k], a)) -> String -> ([k], a)
forall a b. (a -> b) -> a -> b
$ String
moduleNameString -> String -> String
forall a. [a] -> [a] -> [a]
++String
".minElemWithKey: empty map"
minElemWithKeyFMB [k] -> [k]
kf (I Int
_ k
k (Just a
v) FMB k a
E FMB' k a
_ FMB k a
_)        = ([k] -> [k]
kf [k
k],a
v)
minElemWithKeyFMB [k] -> [k]
kf (I Int
_ k
k Maybe a
Nothing  FMB k a
E (FMB' FMB k a
m) FMB k a
_) = ([k] -> [k]) -> FMB k a -> ([k], a)
forall k a. ([k] -> [k]) -> FMB k a -> ([k], a)
minElemWithKeyFMB ([k] -> [k]
kf ([k] -> [k]) -> ([k] -> [k]) -> [k] -> [k]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k
kk -> [k] -> [k]
forall a. a -> [a] -> [a]
:)) FMB k a
m
minElemWithKeyFMB [k] -> [k]
kf (I Int
_ k
_ Maybe a
_ FMB k a
l FMB' k a
_ FMB k a
_)              = ([k] -> [k]) -> FMB k a -> ([k], a)
forall k a. ([k] -> [k]) -> FMB k a -> ([k], a)
minElemWithKeyFMB [k] -> [k]
kf FMB k a
l

minElemWithKey :: FM k a -> ([k],a)
minElemWithKey :: forall k a. FM k a -> ([k], a)
minElemWithKey (FM (Just a
v) FMB k a
_) = ([],a
v)
minElemWithKey (FM Maybe a
Nothing  FMB k a
fmb) = ([k] -> [k]) -> FMB k a -> ([k], a)
forall k a. ([k] -> [k]) -> FMB k a -> ([k], a)
minElemWithKeyFMB [k] -> [k]
forall a. a -> a
id FMB k a
fmb

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

unsafeInsertMin :: Ord k => [k] -> a -> FM k a -> FM k a
unsafeInsertMin :: forall k a. Ord k => [k] -> a -> FM k a -> FM k a
unsafeInsertMin = [k] -> a -> FM k a -> FM k a
forall k a. Ord k => [k] -> a -> FM k a -> FM k a
insert

maxViewFMB :: Fail.MonadFail m => FMB k a -> (FMB k a -> FM k a) -> m (a, FM k a)
maxViewFMB :: forall (m :: * -> *) k a.
MonadFail m =>
FMB k a -> (FMB k a -> FM k a) -> m (a, FM k a)
maxViewFMB (I Int
_ k
_ (Just a
v) FMB k a
l (FMB' FMB k a
E) FMB k a
E) FMB k a -> FM k a
f = (a, FM k a) -> m (a, FM k a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (a
v, FMB k a -> FM k a
f FMB k a
l)
--maxViewFMB (I i k (Just v) l (FMB' E) E) f = return (v, f (I i k Nothing l (FMB' E) E))
maxViewFMB (I Int
_ k
_ Maybe a
Nothing  FMB k a
_ (FMB' FMB k a
E) FMB k a
E) FMB k a -> FM k a
_ = String -> m (a, FM k a)
forall a. HasCallStack => String -> a
error (String -> m (a, FM k a)) -> String -> m (a, FM k a)
forall a b. (a -> b) -> a -> b
$ String
moduleNameString -> String -> String
forall a. [a] -> [a] -> [a]
++String
".maxView: bug!"
maxViewFMB (I Int
i k
k Maybe a
mv FMB k a
l (FMB' FMB k a
m) FMB k a
E)       FMB k a -> FM k a
f = FMB k a -> (FMB k a -> FM k a) -> m (a, FM k a)
forall (m :: * -> *) k a.
MonadFail m =>
FMB k a -> (FMB k a -> FM k a) -> m (a, FM k a)
maxViewFMB FMB k a
m (\FMB k a
m' -> FMB k a -> FM k a
f (Int -> k -> Maybe a -> FMB k a -> FMB' k a -> FMB k a -> FMB k a
forall k v.
Int -> k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
I Int
i k
k Maybe a
mv FMB k a
l (FMB k a -> FMB' k a
forall k v. FMB k v -> FMB' k v
FMB' FMB k a
m') FMB k a
forall k v. FMB k v
E))
maxViewFMB (I Int
_ k
k Maybe a
mv FMB k a
l FMB' k a
m FMB k a
r)              FMB k a -> FM k a
f = FMB k a -> (FMB k a -> FM k a) -> m (a, FM k a)
forall (m :: * -> *) k a.
MonadFail m =>
FMB k a -> (FMB k a -> FM k a) -> m (a, FM k a)
maxViewFMB FMB k a
r (\FMB k a
r' -> FMB k a -> FM k a
f (k -> Maybe a -> FMB k a -> FMB' k a -> FMB k a -> FMB k a
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkVBalancedFMB k
k Maybe a
mv FMB k a
l FMB' k a
m FMB k a
r'))
maxViewFMB FMB k a
E                             FMB k a -> FM k a
_ = String -> m (a, FM k a)
forall a. HasCallStack => String -> a
error (String -> m (a, FM k a)) -> String -> m (a, FM k a)
forall a b. (a -> b) -> a -> b
$ String
moduleNameString -> String -> String
forall a. [a] -> [a] -> [a]
++String
".maxView: bug!"

maxView :: Fail.MonadFail m => FM k a -> m (a, FM k a)
maxView :: forall (m :: * -> *) k a. MonadFail m => FM k a -> m (a, FM k a)
maxView (FM Maybe a
Nothing FMB k a
E)  = String -> m (a, FM k a)
forall a. String -> m a
forall (m :: * -> *) a. MonadFail m => String -> m a
fail (String -> m (a, FM k a)) -> String -> m (a, FM k a)
forall a b. (a -> b) -> a -> b
$ String
moduleNameString -> String -> String
forall a. [a] -> [a] -> [a]
++String
".maxView: empty map"
maxView (FM (Just a
v) FMB k a
E) = (a, FM k a) -> m (a, FM k a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (a
v,Maybe a -> FMB k a -> FM k a
forall k a. Maybe a -> FMB k a -> FM k a
FM Maybe a
forall a. Maybe a
Nothing FMB k a
forall k v. FMB k v
E)
maxView (FM Maybe a
mv FMB k a
fmb)     = FMB k a -> (FMB k a -> FM k a) -> m (a, FM k a)
forall (m :: * -> *) k a.
MonadFail m =>
FMB k a -> (FMB k a -> FM k a) -> m (a, FM k a)
maxViewFMB FMB k a
fmb (Maybe a -> FMB k a -> FM k a
forall k a. Maybe a -> FMB k a -> FM k a
FM Maybe a
mv)


maxViewWithKeyFMB :: Monad m => FMB k a -> ([k] -> [k]) -> (FMB k a -> FM k a) -> m (([k],a),FM k a)
maxViewWithKeyFMB :: forall (m :: * -> *) k a.
Monad m =>
FMB k a
-> ([k] -> [k]) -> (FMB k a -> FM k a) -> m (([k], a), FM k a)
maxViewWithKeyFMB (I Int
_ k
k (Just a
v) FMB k a
l (FMB' FMB k a
E) FMB k a
E) [k] -> [k]
kf FMB k a -> FM k a
f = (([k], a), FM k a) -> m (([k], a), FM k a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (([k] -> [k]
kf [k
k],a
v),FMB k a -> FM k a
f FMB k a
l)
maxViewWithKeyFMB (I Int
_ k
_ Maybe a
Nothing  FMB k a
_ (FMB' FMB k a
E) FMB k a
E) [k] -> [k]
_ FMB k a -> FM k a
_ = String -> m (([k], a), FM k a)
forall a. HasCallStack => String -> a
error (String -> m (([k], a), FM k a)) -> String -> m (([k], a), FM k a)
forall a b. (a -> b) -> a -> b
$ String
moduleNameString -> String -> String
forall a. [a] -> [a] -> [a]
++String
".maxViewWithKey: bug!"
maxViewWithKeyFMB (I Int
i k
k Maybe a
mv FMB k a
l (FMB' FMB k a
m) FMB k a
E)       [k] -> [k]
kf FMB k a -> FM k a
f = FMB k a
-> ([k] -> [k]) -> (FMB k a -> FM k a) -> m (([k], a), FM k a)
forall (m :: * -> *) k a.
Monad m =>
FMB k a
-> ([k] -> [k]) -> (FMB k a -> FM k a) -> m (([k], a), FM k a)
maxViewWithKeyFMB FMB k a
m ([k] -> [k]
kf ([k] -> [k]) -> ([k] -> [k]) -> [k] -> [k]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k
kk -> [k] -> [k]
forall a. a -> [a] -> [a]
:))
                                                        (\FMB k a
m' -> FMB k a -> FM k a
f (Int -> k -> Maybe a -> FMB k a -> FMB' k a -> FMB k a -> FMB k a
forall k v.
Int -> k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
I Int
i k
k Maybe a
mv FMB k a
l (FMB k a -> FMB' k a
forall k v. FMB k v -> FMB' k v
FMB' FMB k a
m') FMB k a
forall k v. FMB k v
E))
maxViewWithKeyFMB (I Int
_ k
k Maybe a
mv FMB k a
l FMB' k a
m FMB k a
r)              [k] -> [k]
kf FMB k a -> FM k a
f = FMB k a
-> ([k] -> [k]) -> (FMB k a -> FM k a) -> m (([k], a), FM k a)
forall (m :: * -> *) k a.
Monad m =>
FMB k a
-> ([k] -> [k]) -> (FMB k a -> FM k a) -> m (([k], a), FM k a)
maxViewWithKeyFMB FMB k a
r [k] -> [k]
kf
                                                        (\FMB k a
r' -> FMB k a -> FM k a
f (k -> Maybe a -> FMB k a -> FMB' k a -> FMB k a -> FMB k a
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkVBalancedFMB k
k Maybe a
mv FMB k a
l FMB' k a
m FMB k a
r'))
maxViewWithKeyFMB FMB k a
E                             [k] -> [k]
_ FMB k a -> FM k a
_ = String -> m (([k], a), FM k a)
forall a. HasCallStack => String -> a
error (String -> m (([k], a), FM k a)) -> String -> m (([k], a), FM k a)
forall a b. (a -> b) -> a -> b
$ String
moduleNameString -> String -> String
forall a. [a] -> [a] -> [a]
++String
".maxViewWithKey: bug!"


maxViewWithKey :: Fail.MonadFail m => FM k a -> m (([k],a), FM k a)
maxViewWithKey :: forall (m :: * -> *) k a.
MonadFail m =>
FM k a -> m (([k], a), FM k a)
maxViewWithKey (FM Maybe a
Nothing FMB k a
E)  = String -> m (([k], a), FM k a)
forall a. String -> m a
forall (m :: * -> *) a. MonadFail m => String -> m a
fail (String -> m (([k], a), FM k a)) -> String -> m (([k], a), FM k a)
forall a b. (a -> b) -> a -> b
$ String
moduleNameString -> String -> String
forall a. [a] -> [a] -> [a]
++String
".maxViewWithKey: empty map"
maxViewWithKey (FM (Just a
v) FMB k a
E) = (([k], a), FM k a) -> m (([k], a), FM k a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (([],a
v),Maybe a -> FMB k a -> FM k a
forall k a. Maybe a -> FMB k a -> FM k a
FM Maybe a
forall a. Maybe a
Nothing FMB k a
forall k v. FMB k v
E)
maxViewWithKey (FM Maybe a
mv FMB k a
fmb)     = FMB k a
-> ([k] -> [k]) -> (FMB k a -> FM k a) -> m (([k], a), FM k a)
forall (m :: * -> *) k a.
Monad m =>
FMB k a
-> ([k] -> [k]) -> (FMB k a -> FM k a) -> m (([k], a), FM k a)
maxViewWithKeyFMB FMB k a
fmb [k] -> [k]
forall a. a -> a
id (Maybe a -> FMB k a -> FM k a
forall k a. Maybe a -> FMB k a -> FM k a
FM Maybe a
mv)



maxElemFMB :: FMB k a -> a
maxElemFMB :: forall k a. FMB k a -> a
maxElemFMB (I Int
_ k
_ (Just a
v) FMB k a
_ (FMB' FMB k a
E) FMB k a
E) = a
v
maxElemFMB (I Int
_ k
_ Maybe a
Nothing  FMB k a
_ (FMB' FMB k a
E) FMB k a
E) = String -> a
forall a. HasCallStack => String -> a
error (String -> a) -> String -> a
forall a b. (a -> b) -> a -> b
$ String
moduleNameString -> String -> String
forall a. [a] -> [a] -> [a]
++String
".maxElem: bug!"
maxElemFMB (I Int
_ k
_ Maybe a
_ FMB k a
_ (FMB' FMB k a
m) FMB k a
E)       = FMB k a -> a
forall k a. FMB k a -> a
maxElemFMB FMB k a
m
maxElemFMB (I Int
_ k
_ Maybe a
_ FMB k a
_ FMB' k a
_ FMB k a
r)              = FMB k a -> a
forall k a. FMB k a -> a
maxElemFMB FMB k a
r
maxElemFMB FMB k a
E                             = String -> a
forall a. HasCallStack => String -> a
error (String -> a) -> String -> a
forall a b. (a -> b) -> a -> b
$ String
moduleNameString -> String -> String
forall a. [a] -> [a] -> [a]
++String
".maxElem: bug!"

maxElem :: FM k a -> a
maxElem :: forall t1 t. FM t1 t -> t
maxElem (FM (Just a
v) FMB k a
E) = a
v
maxElem (FM Maybe a
Nothing  FMB k a
E) = String -> a
forall a. HasCallStack => String -> a
error (String -> a) -> String -> a
forall a b. (a -> b) -> a -> b
$ String
moduleNameString -> String -> String
forall a. [a] -> [a] -> [a]
++String
".maxElem: empty map"
maxElem (FM Maybe a
_ FMB k a
fmb)      = FMB k a -> a
forall k a. FMB k a -> a
maxElemFMB FMB k a
fmb

maxElemWithKeyFMB :: FMB k a -> ([k] -> [k]) -> ([k],a)
maxElemWithKeyFMB :: forall k a. FMB k a -> ([k] -> [k]) -> ([k], a)
maxElemWithKeyFMB (I Int
_ k
k (Just a
v) FMB k a
_ (FMB' FMB k a
E) FMB k a
E) [k] -> [k]
kf = ([k] -> [k]
kf [k
k],a
v)
maxElemWithKeyFMB (I Int
_ k
_ Maybe a
Nothing  FMB k a
_ (FMB' FMB k a
E) FMB k a
E) [k] -> [k]
_ = String -> ([k], a)
forall a. HasCallStack => String -> a
error (String -> ([k], a)) -> String -> ([k], a)
forall a b. (a -> b) -> a -> b
$ String
moduleNameString -> String -> String
forall a. [a] -> [a] -> [a]
++String
".maxElemWithKey: bug!"
maxElemWithKeyFMB (I Int
_ k
k Maybe a
_ FMB k a
_ (FMB' FMB k a
m) FMB k a
E)       [k] -> [k]
kf = FMB k a -> ([k] -> [k]) -> ([k], a)
forall k a. FMB k a -> ([k] -> [k]) -> ([k], a)
maxElemWithKeyFMB FMB k a
m ([k] -> [k]
kf ([k] -> [k]) -> ([k] -> [k]) -> [k] -> [k]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k
kk -> [k] -> [k]
forall a. a -> [a] -> [a]
:))
maxElemWithKeyFMB (I Int
_ k
_ Maybe a
_ FMB k a
_ FMB' k a
_ FMB k a
r)              [k] -> [k]
kf = FMB k a -> ([k] -> [k]) -> ([k], a)
forall k a. FMB k a -> ([k] -> [k]) -> ([k], a)
maxElemWithKeyFMB FMB k a
r [k] -> [k]
kf
maxElemWithKeyFMB FMB k a
E                             [k] -> [k]
_ = String -> ([k], a)
forall a. HasCallStack => String -> a
error (String -> ([k], a)) -> String -> ([k], a)
forall a b. (a -> b) -> a -> b
$ String
moduleNameString -> String -> String
forall a. [a] -> [a] -> [a]
++String
".maxElemWithKey: bug!"


maxElemWithKey :: FM k a -> ([k],a)
maxElemWithKey :: forall k a. FM k a -> ([k], a)
maxElemWithKey (FM (Just a
v) FMB k a
E) = ([],a
v)
maxElemWithKey (FM Maybe a
Nothing FMB k a
E)  = String -> ([k], a)
forall a. HasCallStack => String -> a
error (String -> ([k], a)) -> String -> ([k], a)
forall a b. (a -> b) -> a -> b
$ String
moduleNameString -> String -> String
forall a. [a] -> [a] -> [a]
++String
".maxElemWithKey: empty map"
maxElemWithKey (FM Maybe a
_ FMB k a
fmb)      = FMB k a -> ([k] -> [k]) -> ([k], a)
forall k a. FMB k a -> ([k] -> [k]) -> ([k], a)
maxElemWithKeyFMB FMB k a
fmb [k] -> [k]
forall a. a -> a
id


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

unsafeInsertMax :: Ord k => [k] -> a -> FM k a -> FM k a
unsafeInsertMax :: forall k a. Ord k => [k] -> a -> FM k a -> FM k a
unsafeInsertMax = [k] -> a -> FM k a -> FM k a
forall k a. Ord k => [k] -> a -> FM k a -> FM k a
insert

unsafeFromOrdSeq :: (Ord k,S.Sequence seq) => seq ([k],a) -> FM k a
unsafeFromOrdSeq :: forall k (seq :: * -> *) a.
(Ord k, Sequence seq) =>
seq ([k], a) -> FM k a
unsafeFromOrdSeq = seq ([k], a) -> FM k a
forall k (seq :: * -> *) a.
(Ord k, Sequence seq) =>
seq ([k], a) -> FM k a
fromSeq

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

-- FIXME this doesn't respect the structural invariant... why??
{-
unsafeAppend (FM (Just v) fmb1) (FM Nothing fmb2) = FM (Just v) (appendFMB fmb1 fmb2)
unsafeAppend (FM Nothing  fmb1) (FM mv fmb2)      = FM mv       (appendFMB fmb1 fmb2)
unsafeAppend (FM (Just _) _) (FM (Just _) _)      = error $ moduleName++".unsafeAppend: bug!"
-}

filterL_FMB :: Ord k => (k -> Maybe a -> FMB k a -> FMB k a) -> k -> [k] -> FMB k a -> FMB k a
filterL_FMB :: forall k a.
Ord k =>
(k -> Maybe a -> FMB k a -> FMB k a)
-> k -> [k] -> FMB k a -> FMB k a
filterL_FMB k -> Maybe a -> FMB k a -> FMB k a
_ k
_ [k]
_ FMB k a
E = FMB k a
forall k v. FMB k v
E
filterL_FMB k -> Maybe a -> FMB k a -> FMB k a
f k
k [k]
ks (I Int
_ k
key Maybe a
mv FMB k a
l (FMB' FMB k a
m) FMB k a
r)
    | k
key k -> k -> Bool
forall a. Ord a => a -> a -> Bool
< k
k   = k -> Maybe a -> FMB k a -> FMB' k a -> FMB k a -> FMB k a
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkVBalancedFMB k
key Maybe a
mv FMB k a
l (FMB k a -> FMB' k a
forall k v. FMB k v -> FMB' k v
FMB' FMB k a
m) ((k -> Maybe a -> FMB k a -> FMB k a)
-> k -> [k] -> FMB k a -> FMB k a
forall k a.
Ord k =>
(k -> Maybe a -> FMB k a -> FMB k a)
-> k -> [k] -> FMB k a -> FMB k a
filterL_FMB k -> Maybe a -> FMB k a -> FMB k a
f k
k [k]
ks FMB k a
r)
    | k
key k -> k -> Bool
forall a. Ord a => a -> a -> Bool
> k
k   = (k -> Maybe a -> FMB k a -> FMB k a)
-> k -> [k] -> FMB k a -> FMB k a
forall k a.
Ord k =>
(k -> Maybe a -> FMB k a -> FMB k a)
-> k -> [k] -> FMB k a -> FMB k a
filterL_FMB k -> Maybe a -> FMB k a -> FMB k a
f k
k [k]
ks FMB k a
l
    | Bool
otherwise = case [k]
ks of
                    []       -> k -> Maybe a -> FMB k a -> FMB k a
f k
k Maybe a
mv FMB k a
l
                    (k
k':[k]
ks') -> k -> Maybe a -> FMB k a -> FMB' k a -> FMB k a -> FMB k a
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkVBalancedFMB k
key Maybe a
mv FMB k a
l (FMB k a -> FMB' k a
forall k v. FMB k v -> FMB' k v
FMB' ((k -> Maybe a -> FMB k a -> FMB k a)
-> k -> [k] -> FMB k a -> FMB k a
forall k a.
Ord k =>
(k -> Maybe a -> FMB k a -> FMB k a)
-> k -> [k] -> FMB k a -> FMB k a
filterL_FMB k -> Maybe a -> FMB k a -> FMB k a
f k
k' [k]
ks' FMB k a
m)) FMB k a
forall k v. FMB k v
E

filterLT :: Ord k => [k] -> FM k a -> FM k a
filterLT :: forall k v. Ord k => [k] -> FM k v -> FM k v
filterLT [] FM k a
_               = Maybe a -> FMB k a -> FM k a
forall k a. Maybe a -> FMB k a -> FM k a
FM Maybe a
forall a. Maybe a
Nothing FMB k a
forall k v. FMB k v
E
filterLT (k
k:[k]
ks) (FM Maybe a
mv FMB k a
fmb) = Maybe a -> FMB k a -> FM k a
forall k a. Maybe a -> FMB k a -> FM k a
FM Maybe a
mv ((k -> Maybe a -> FMB k a -> FMB k a)
-> k -> [k] -> FMB k a -> FMB k a
forall k a.
Ord k =>
(k -> Maybe a -> FMB k a -> FMB k a)
-> k -> [k] -> FMB k a -> FMB k a
filterL_FMB (\k
_ Maybe a
_ FMB k a
l -> FMB k a
l) k
k [k]
ks FMB k a
fmb)

filterLE :: Ord k => [k] -> FM k a -> FM k a
filterLE :: forall k v. Ord k => [k] -> FM k v -> FM k v
filterLE [] (FM Maybe a
mv FMB k a
_)       = Maybe a -> FMB k a -> FM k a
forall k a. Maybe a -> FMB k a -> FM k a
FM Maybe a
mv FMB k a
forall k v. FMB k v
E
filterLE (k
k:[k]
ks) (FM Maybe a
mv FMB k a
fmb) = Maybe a -> FMB k a -> FM k a
forall k a. Maybe a -> FMB k a -> FM k a
FM Maybe a
mv ((k -> Maybe a -> FMB k a -> FMB k a)
-> k -> [k] -> FMB k a -> FMB k a
forall k a.
Ord k =>
(k -> Maybe a -> FMB k a -> FMB k a)
-> k -> [k] -> FMB k a -> FMB k a
filterL_FMB (\k
k Maybe a
mv FMB k a
l -> k -> Maybe a -> FMB k a -> FMB' k a -> FMB k a -> FMB k a
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkVBalancedFMB k
k Maybe a
mv FMB k a
l (FMB k a -> FMB' k a
forall k v. FMB k v -> FMB' k v
FMB' FMB k a
forall k v. FMB k v
E) FMB k a
forall k v. FMB k v
E) k
k [k]
ks FMB k a
fmb)



filterG_FMB :: Ord k => (k -> Maybe a -> FMB k a -> FMB k a -> FMB k a) -> k -> [k] -> FMB k a -> FMB k a
filterG_FMB :: forall k a.
Ord k =>
(k -> Maybe a -> FMB k a -> FMB k a -> FMB k a)
-> k -> [k] -> FMB k a -> FMB k a
filterG_FMB k -> Maybe a -> FMB k a -> FMB k a -> FMB k a
_ k
_ [k]
_ FMB k a
E = FMB k a
forall k v. FMB k v
E
filterG_FMB k -> Maybe a -> FMB k a -> FMB k a -> FMB k a
f k
k [k]
ks (I Int
_ k
key Maybe a
mv FMB k a
l (FMB' FMB k a
m) FMB k a
r)
    | k
key k -> k -> Bool
forall a. Ord a => a -> a -> Bool
< k
k   = (k -> Maybe a -> FMB k a -> FMB k a -> FMB k a)
-> k -> [k] -> FMB k a -> FMB k a
forall k a.
Ord k =>
(k -> Maybe a -> FMB k a -> FMB k a -> FMB k a)
-> k -> [k] -> FMB k a -> FMB k a
filterG_FMB k -> Maybe a -> FMB k a -> FMB k a -> FMB k a
f k
k [k]
ks FMB k a
r
    | k
key k -> k -> Bool
forall a. Ord a => a -> a -> Bool
> k
k   = k -> Maybe a -> FMB k a -> FMB' k a -> FMB k a -> FMB k a
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkVBalancedFMB k
key Maybe a
mv ((k -> Maybe a -> FMB k a -> FMB k a -> FMB k a)
-> k -> [k] -> FMB k a -> FMB k a
forall k a.
Ord k =>
(k -> Maybe a -> FMB k a -> FMB k a -> FMB k a)
-> k -> [k] -> FMB k a -> FMB k a
filterG_FMB k -> Maybe a -> FMB k a -> FMB k a -> FMB k a
f k
k [k]
ks FMB k a
l) (FMB k a -> FMB' k a
forall k v. FMB k v -> FMB' k v
FMB' FMB k a
m) FMB k a
r
    | Bool
otherwise = case [k]
ks of
                    []       -> k -> Maybe a -> FMB k a -> FMB k a -> FMB k a
f k
k Maybe a
mv FMB k a
m FMB k a
r
                    (k
k':[k]
ks') -> k -> Maybe a -> FMB k a -> FMB' k a -> FMB k a -> FMB k a
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkVBalancedFMB k
key Maybe a
forall a. Maybe a
Nothing FMB k a
forall k v. FMB k v
E (FMB k a -> FMB' k a
forall k v. FMB k v -> FMB' k v
FMB' ((k -> Maybe a -> FMB k a -> FMB k a -> FMB k a)
-> k -> [k] -> FMB k a -> FMB k a
forall k a.
Ord k =>
(k -> Maybe a -> FMB k a -> FMB k a -> FMB k a)
-> k -> [k] -> FMB k a -> FMB k a
filterG_FMB k -> Maybe a -> FMB k a -> FMB k a -> FMB k a
f k
k' [k]
ks' FMB k a
m)) FMB k a
r

filterGT :: Ord k => [k] -> FM k a -> FM k a
filterGT :: forall k v. Ord k => [k] -> FM k v -> FM k v
filterGT []     (FM Maybe a
_  FMB k a
fmb) = Maybe a -> FMB k a -> FM k a
forall k a. Maybe a -> FMB k a -> FM k a
FM Maybe a
forall a. Maybe a
Nothing FMB k a
fmb
filterGT (k
k:[k]
ks) (FM Maybe a
_ FMB k a
fmb) = Maybe a -> FMB k a -> FM k a
forall k a. Maybe a -> FMB k a -> FM k a
FM Maybe a
forall a. Maybe a
Nothing ((k -> Maybe a -> FMB k a -> FMB k a -> FMB k a)
-> k -> [k] -> FMB k a -> FMB k a
forall k a.
Ord k =>
(k -> Maybe a -> FMB k a -> FMB k a -> FMB k a)
-> k -> [k] -> FMB k a -> FMB k a
filterG_FMB (\k
k Maybe a
_ FMB k a
m FMB k a
r -> k -> Maybe a -> FMB k a -> FMB' k a -> FMB k a -> FMB k a
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkVBalancedFMB k
k Maybe a
forall a. Maybe a
Nothing FMB k a
forall k v. FMB k v
E (FMB k a -> FMB' k a
forall k v. FMB k v -> FMB' k v
FMB' FMB k a
m) FMB k a
r) k
k [k]
ks FMB k a
fmb)

filterGE :: Ord k => [k] -> FM k a -> FM k a
filterGE :: forall k v. Ord k => [k] -> FM k v -> FM k v
filterGE []     FM k a
fm          = FM k a
fm
filterGE (k
k:[k]
ks) (FM Maybe a
_ FMB k a
fmb) = Maybe a -> FMB k a -> FM k a
forall k a. Maybe a -> FMB k a -> FM k a
FM Maybe a
forall a. Maybe a
Nothing ((k -> Maybe a -> FMB k a -> FMB k a -> FMB k a)
-> k -> [k] -> FMB k a -> FMB k a
forall k a.
Ord k =>
(k -> Maybe a -> FMB k a -> FMB k a -> FMB k a)
-> k -> [k] -> FMB k a -> FMB k a
filterG_FMB (\k
k Maybe a
mv FMB k a
m FMB k a
r -> k -> Maybe a -> FMB k a -> FMB' k a -> FMB k a -> FMB k a
forall k v.
k -> Maybe v -> FMB k v -> FMB' k v -> FMB k v -> FMB k v
mkVBalancedFMB k
k Maybe a
mv FMB k a
forall k v. FMB k v
E (FMB k a -> FMB' k a
forall k v. FMB k v -> FMB' k v
FMB' FMB k a
m) FMB k a
r) k
k [k]
ks FMB k a
fmb)

--FIXME do better...
partitionLT_GE :: Ord k => [k] -> FM k a -> (FM k a,FM k a)
partitionLT_GE :: forall k a. Ord k => [k] -> FM k a -> (FM k a, FM k a)
partitionLT_GE [k]
ks FM k a
fm = ([k] -> FM k a -> FM k a
forall k v. Ord k => [k] -> FM k v -> FM k v
filterLT [k]
ks FM k a
fm, [k] -> FM k a -> FM k a
forall k v. Ord k => [k] -> FM k v -> FM k v
filterGE [k]
ks FM k a
fm)

partitionLE_GT :: Ord k => [k] -> FM k a -> (FM k a,FM k a)
partitionLE_GT :: forall k a. Ord k => [k] -> FM k a -> (FM k a, FM k a)
partitionLE_GT [k]
ks FM k a
fm = ([k] -> FM k a -> FM k a
forall k v. Ord k => [k] -> FM k v -> FM k v
filterLE [k]
ks FM k a
fm, [k] -> FM k a -> FM k a
forall k v. Ord k => [k] -> FM k v -> FM k v
filterGT [k]
ks FM k a
fm)

partitionLT_GT :: Ord k => [k] -> FM k a -> (FM k a,FM k a)
partitionLT_GT :: forall k a. Ord k => [k] -> FM k a -> (FM k a, FM k a)
partitionLT_GT [k]
ks FM k a
fm = ([k] -> FM k a -> FM k a
forall k v. Ord k => [k] -> FM k v -> FM k v
filterLT [k]
ks FM k a
fm, [k] -> FM k a -> FM k a
forall k v. Ord k => [k] -> FM k v -> FM k v
filterGT [k]
ks FM k a
fm)

toOrdSeq :: forall k (seq :: * -> *) a.
(Ord k, Sequence seq) =>
FM k a -> seq ([k], a)
toOrdSeq = FM k a -> seq ([k], a)
forall (m :: * -> *) k (seq :: * -> *) a.
(OrdAssoc m k, Sequence seq) =>
m a -> seq (k, a)
toOrdSeqUsingFoldrWithKey

-- instance declarations

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

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

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

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

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

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

instance Ord k => A.OrdFiniteMapX (FM k) [k]
instance Ord k => A.OrdFiniteMap (FM k) [k]


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

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

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

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

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

--
-- Test code follows
--

keyInvariantFMB :: Ord k => (k -> Bool) -> FMB k a -> Bool
keyInvariantFMB :: forall k a. Ord k => (k -> Bool) -> FMB k a -> Bool
keyInvariantFMB k -> Bool
_ FMB k a
E = Bool
True
keyInvariantFMB k -> Bool
p (I Int
_ k
k Maybe a
_ FMB k a
l FMB' k a
_ FMB k a
r)
  =    k -> Bool
p k
k
    Bool -> Bool -> Bool
&& (k -> Bool) -> FMB k a -> Bool
forall k a. Ord k => (k -> Bool) -> FMB k a -> Bool
keyInvariantFMB k -> Bool
p FMB k a
l
    Bool -> Bool -> Bool
&& (k -> Bool) -> FMB k a -> Bool
forall k a. Ord k => (k -> Bool) -> FMB k a -> Bool
keyInvariantFMB k -> Bool
p FMB k a
r

actualSizeFMB :: FMB k a -> Int
actualSizeFMB :: forall k v. FMB k v -> Int
actualSizeFMB FMB k a
E = Int
0
actualSizeFMB (I Int
_ k
_ Maybe a
_ FMB k a
l FMB' k a
_ FMB k a
r) = Int
1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ FMB k a -> Int
forall k v. FMB k v -> Int
actualSizeFMB FMB k a
l Int -> Int -> Int
forall a. Num a => a -> a -> a
+ FMB k a -> Int
forall k v. FMB k v -> Int
actualSizeFMB FMB k a
r

structuralInvariantFMB :: Ord k => FMB k a -> Bool
structuralInvariantFMB :: forall k a. Ord k => FMB k a -> Bool
structuralInvariantFMB FMB k a
E = Bool
True
structuralInvariantFMB fmb :: FMB k a
fmb@(I Int
size k
k Maybe a
_ FMB k a
l (FMB' FMB k a
m) FMB k a
r)
  =    FMB k a -> Bool
forall k a. Ord k => FMB k a -> Bool
structuralInvariantFMB FMB k a
l
    Bool -> Bool -> Bool
&& FMB k a -> Bool
forall k a. Ord k => FMB k a -> Bool
structuralInvariantFMB FMB k a
m
    Bool -> Bool -> Bool
&& FMB k a -> Bool
forall k a. Ord k => FMB k a -> Bool
structuralInvariantFMB FMB k a
r
    Bool -> Bool -> Bool
&& (k -> Bool) -> FMB k a -> Bool
forall k a. Ord k => (k -> Bool) -> FMB k a -> Bool
keyInvariantFMB (k -> k -> Bool
forall a. Ord a => a -> a -> Bool
<k
k) FMB k a
l
    Bool -> Bool -> Bool
&& (k -> Bool) -> FMB k a -> Bool
forall k a. Ord k => (k -> Bool) -> FMB k a -> Bool
keyInvariantFMB (k -> k -> Bool
forall a. Ord a => a -> a -> Bool
>k
k) FMB k a
r
    Bool -> Bool -> Bool
&& FMB k a -> Int
forall k v. FMB k v -> Int
actualSizeFMB FMB k a
fmb Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
size
    Bool -> Bool -> Bool
&& (Int
sizel Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
sizer Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
2
        Bool -> Bool -> Bool
|| (Int
sizel Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
balance Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
sizer Bool -> Bool -> Bool
&& Int
sizer Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
balance Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
sizel))
  where
      sizel :: Int
sizel = FMB k a -> Int
forall k v. FMB k v -> Int
sizeFMB FMB k a
l
      sizer :: Int
sizer = FMB k a -> Int
forall k v. FMB k v -> Int
sizeFMB FMB k a
r

structuralInvariant :: Ord k => FM k a -> Bool
structuralInvariant :: forall k a. Ord k => FM k a -> Bool
structuralInvariant (FM Maybe a
_ FMB k a
fmb) = FMB k a -> Bool
forall k a. Ord k => FMB k a -> Bool
structuralInvariantFMB FMB k a
fmb


instance (Ord k,Arbitrary k,Arbitrary a) => Arbitrary (FM k a) where
  arbitrary :: Gen (FM k a)
arbitrary = do ([([k], a)]
xs::[([k],a)]) <- Gen [([k], a)]
forall a. Arbitrary a => Gen a
arbitrary
                 FM k a -> Gen (FM k a)
forall a. a -> Gen a
forall (m :: * -> *) a. Monad m => a -> m a
return ((([k], a) -> FM k a -> FM k a) -> FM k a -> [([k], a)] -> FM k 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 (([k] -> a -> FM k a -> FM k a) -> ([k], a) -> FM k a -> FM k a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry [k] -> a -> FM k a -> FM k a
forall k a. Ord k => [k] -> a -> FM k a -> FM k a
insert) FM k a
forall k a. Ord k => FM k a
empty [([k], a)]
xs)

instance (Ord k,CoArbitrary k,CoArbitrary a) => CoArbitrary (FM k a) where
  coarbitrary :: forall b. FM k a -> Gen b -> Gen b
coarbitrary (FM Maybe a
x FMB k a
fmb) = Maybe a -> Gen b -> Gen b
forall t b. CoArbitrary t => Maybe t -> Gen b -> Gen b
coarbitrary_maybe Maybe a
x (Gen b -> Gen b) -> (Gen b -> Gen b) -> Gen b -> Gen b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FMB k a -> Gen b -> Gen b
forall t1 t a.
(CoArbitrary t1, CoArbitrary t) =>
FMB t t1 -> Gen a -> Gen a
coarbitrary_fmb FMB k a
fmb


coarbitrary_maybe :: (CoArbitrary t) => Maybe t  -> Test.QuickCheck.Gen b
                                                 -> Test.QuickCheck.Gen b
coarbitrary_maybe :: forall t b. CoArbitrary t => Maybe t -> Gen b -> Gen b
coarbitrary_maybe Maybe t
Nothing = Integer -> Gen b -> Gen b
forall n a. Integral n => n -> Gen a -> Gen a
variant Integer
0
coarbitrary_maybe (Just t
x) = 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
. t -> Gen b -> Gen b
forall b. t -> Gen b -> Gen b
forall a b. CoArbitrary a => a -> Gen b -> Gen b
coarbitrary t
x

coarbitrary_fmb :: (CoArbitrary t1, CoArbitrary t) => FMB t t1 -> Gen a -> Gen a
coarbitrary_fmb :: forall t1 t a.
(CoArbitrary t1, CoArbitrary t) =>
FMB t t1 -> Gen a -> Gen a
coarbitrary_fmb FMB t t1
E = Integer -> Gen a -> Gen a
forall n a. Integral n => n -> Gen a -> Gen a
variant Integer
0
coarbitrary_fmb (I Int
_ t
k Maybe t1
x FMB t t1
l (FMB' FMB t t1
m) FMB t t1
r) =
        Integer -> Gen a -> Gen a
forall n a. Integral n => n -> Gen a -> Gen a
variant Integer
1 (Gen a -> Gen a) -> (Gen a -> Gen a) -> Gen a -> Gen a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. t -> Gen a -> Gen a
forall b. t -> Gen b -> Gen b
forall a b. CoArbitrary a => a -> Gen b -> Gen b
coarbitrary t
k (Gen a -> Gen a) -> (Gen a -> Gen a) -> Gen a -> Gen a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Maybe t1 -> Gen a -> Gen a
forall t b. CoArbitrary t => Maybe t -> Gen b -> Gen b
coarbitrary_maybe Maybe t1
x (Gen a -> Gen a) -> (Gen a -> Gen a) -> Gen a -> Gen a
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
        FMB t t1 -> Gen a -> Gen a
forall t1 t a.
(CoArbitrary t1, CoArbitrary t) =>
FMB t t1 -> Gen a -> Gen a
coarbitrary_fmb FMB t t1
l (Gen a -> Gen a) -> (Gen a -> Gen a) -> Gen a -> Gen a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FMB t t1 -> Gen a -> Gen a
forall t1 t a.
(CoArbitrary t1, CoArbitrary t) =>
FMB t t1 -> Gen a -> Gen a
coarbitrary_fmb FMB t t1
m (Gen a -> Gen a) -> (Gen a -> Gen a) -> Gen a -> Gen a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. FMB t t1 -> Gen a -> Gen a
forall t1 t a.
(CoArbitrary t1, CoArbitrary t) =>
FMB t t1 -> Gen a -> Gen a
coarbitrary_fmb FMB t t1
r

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