{-# LANGUAGE BangPatterns #-}{-# LANGUAGE Safe #-}-- This is a non-exposed internal module---- The code in this module has been ripped from containers-0.5.5.1:Data.Map.Base [1] almost-- verbatimely to avoid a dependency of 'template-haskell' on the containers package.---- [1] see https://hackage.haskell.org/package/containers-0.5.5.1---- The original code is BSD-licensed and copyrighted by Daan Leijen, Andriy Palamarchuk, et al.moduleLanguage.Haskell.TH.Lib.Map(Map ,empty ,insert ,Language.Haskell.TH.Lib.Map.lookup )whereimportPrelude dataMap k a =Bin {-# UNPACK#-}!Size !k a !(Map k a )!(Map k a )|Tip typeSize =Int empty ::Map k a empty :: forall k a. Map k a
empty =Map k a
forall k a. Map k a
Tip {-# INLINEempty #-}singleton ::k ->a ->Map k a singleton :: forall k a. k -> a -> Map k a
singleton k
k a
x =Size -> k -> a -> Map k a -> Map k a -> Map k a
forall k a. Size -> k -> a -> Map k a -> Map k a -> Map k a
Bin Size
1k
k a
x Map k a
forall k a. Map k a
Tip Map k a
forall k a. Map k a
Tip {-# INLINEsingleton #-}size ::Map k a ->Int size :: forall k a. Map k a -> Size
size Map k a
Tip =Size
0size (Bin Size
sz k
_a
_Map k a
_Map k a
_)=Size
sz {-# INLINEsize #-}lookup ::Ord k =>k ->Map k a ->Maybe a lookup :: forall k a. Ord k => k -> Map k a -> Maybe a
lookup =k -> Map k a -> Maybe a
forall k a. Ord k => k -> Map k a -> Maybe a
go wherego :: t -> Map t a -> Maybe a
go t
_Map t a
Tip =Maybe a
forall a. Maybe a
Nothing go !t
k (Bin Size
_t
kx a
x Map t a
l Map t a
r )=caset -> t -> Ordering
forall a. Ord a => a -> a -> Ordering
compare t
k t
kx ofOrdering
LT ->t -> Map t a -> Maybe a
go t
k Map t a
l Ordering
GT ->t -> Map t a -> Maybe a
go t
k Map t a
r Ordering
EQ ->a -> Maybe a
forall a. a -> Maybe a
Just a
x {-# INLINABLElookup #-}insert ::Ord k =>k ->a ->Map k a ->Map k a insert :: forall k a. Ord k => k -> a -> Map k a -> Map k a
insert =k -> a -> Map k a -> Map k a
forall k a. Ord k => k -> a -> Map k a -> Map k a
go wherego ::Ord k =>k ->a ->Map k a ->Map k a go :: forall k a. Ord k => k -> a -> Map k a -> Map k a
go !k
kx a
x Map k a
Tip =k -> a -> Map k a
forall k a. k -> a -> Map k a
singleton k
kx a
x go !k
kx a
x (Bin Size
sz k
ky a
y Map k a
l Map k a
r )=casek -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
kx k
ky ofOrdering
LT ->k -> a -> Map k a -> Map k a -> Map k a
forall k a. k -> a -> Map k a -> Map k a -> Map k a
balanceL k
ky a
y (k -> a -> Map k a -> Map k a
forall k a. Ord k => k -> a -> Map k a -> Map k a
go k
kx a
x Map k a
l )Map k a
r Ordering
GT ->k -> a -> Map k a -> Map k a -> Map k a
forall k a. k -> a -> Map k a -> Map k a -> Map k a
balanceR k
ky a
y Map k a
l (k -> a -> Map k a -> Map k a
forall k a. Ord k => k -> a -> Map k a -> Map k a
go k
kx a
x Map k a
r )Ordering
EQ ->Size -> k -> a -> Map k a -> Map k a -> Map k a
forall k a. Size -> k -> a -> Map k a -> Map k a -> Map k a
Bin Size
sz k
kx a
x Map k a
l Map k a
r {-# INLINABLEinsert #-}balanceL ::k ->a ->Map k a ->Map k a ->Map k a balanceL :: forall k a. k -> a -> Map k a -> Map k a -> Map k a
balanceL k
k a
x Map k a
l Map k a
r =caseMap k a
r ofMap k a
Tip ->caseMap k a
l ofMap k a
Tip ->Size -> k -> a -> Map k a -> Map k a -> Map k a
forall k a. Size -> k -> a -> Map k a -> Map k a -> Map k a
Bin Size
1k
k a
x Map k a
forall k a. Map k a
Tip Map k a
forall k a. Map k a
Tip (Bin Size
_k
_a
_Map k a
Tip Map k a
Tip )->Size -> k -> a -> Map k a -> Map k a -> Map k a
forall k a. Size -> k -> a -> Map k a -> Map k a -> Map k a
Bin Size
2k
k a
x Map k a
l Map k a
forall k a. Map k a
Tip (Bin Size
_k
lk a
lx Map k a
Tip (Bin Size
_k
lrk a
lrx Map k a
_Map k a
_))->Size -> k -> a -> Map k a -> Map k a -> Map k a
forall k a. Size -> k -> a -> Map k a -> Map k a -> Map k a
Bin Size
3k
lrk a
lrx (Size -> k -> a -> Map k a -> Map k a -> Map k a
forall k a. Size -> k -> a -> Map k a -> Map k a -> Map k a
Bin Size
1k
lk a
lx Map k a
forall k a. Map k a
Tip Map k a
forall k a. Map k a
Tip )(Size -> k -> a -> Map k a -> Map k a -> Map k a
forall k a. Size -> k -> a -> Map k a -> Map k a -> Map k a
Bin Size
1k
k a
x Map k a
forall k a. Map k a
Tip Map k a
forall k a. Map k a
Tip )(Bin Size
_k
lk a
lx ll :: Map k a
ll @(Bin Size
_k
_a
_Map k a
_Map k a
_)Map k a
Tip )->Size -> k -> a -> Map k a -> Map k a -> Map k a
forall k a. Size -> k -> a -> Map k a -> Map k a -> Map k a
Bin Size
3k
lk a
lx Map k a
ll (Size -> k -> a -> Map k a -> Map k a -> Map k a
forall k a. Size -> k -> a -> Map k a -> Map k a -> Map k a
Bin Size
1k
k a
x Map k a
forall k a. Map k a
Tip Map k a
forall k a. Map k a
Tip )(Bin Size
ls k
lk a
lx ll :: Map k a
ll @(Bin Size
lls k
_a
_Map k a
_Map k a
_)lr :: Map k a
lr @(Bin Size
lrs k
lrk a
lrx Map k a
lrl Map k a
lrr ))|Size
lrs Size -> Size -> Bool
forall a. Ord a => a -> a -> Bool
< Size
ratio Size -> Size -> Size
forall a. Num a => a -> a -> a
* Size
lls ->Size -> k -> a -> Map k a -> Map k a -> Map k a
forall k a. Size -> k -> a -> Map k a -> Map k a -> Map k a
Bin (Size
1Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Size
ls )k
lk a
lx Map k a
ll (Size -> k -> a -> Map k a -> Map k a -> Map k a
forall k a. Size -> k -> a -> Map k a -> Map k a -> Map k a
Bin (Size
1Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Size
lrs )k
k a
x Map k a
lr Map k a
forall k a. Map k a
Tip )|Bool
otherwise ->Size -> k -> a -> Map k a -> Map k a -> Map k a
forall k a. Size -> k -> a -> Map k a -> Map k a -> Map k a
Bin (Size
1Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Size
ls )k
lrk a
lrx (Size -> k -> a -> Map k a -> Map k a -> Map k a
forall k a. Size -> k -> a -> Map k a -> Map k a -> Map k a
Bin (Size
1Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Size
lls Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Map k a -> Size
forall k a. Map k a -> Size
size Map k a
lrl )k
lk a
lx Map k a
ll Map k a
lrl )(Size -> k -> a -> Map k a -> Map k a -> Map k a
forall k a. Size -> k -> a -> Map k a -> Map k a -> Map k a
Bin (Size
1Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Map k a -> Size
forall k a. Map k a -> Size
size Map k a
lrr )k
k a
x Map k a
lrr Map k a
forall k a. Map k a
Tip )(Bin Size
rs k
_a
_Map k a
_Map k a
_)->caseMap k a
l ofMap k a
Tip ->Size -> k -> a -> Map k a -> Map k a -> Map k a
forall k a. Size -> k -> a -> Map k a -> Map k a -> Map k a
Bin (Size
1Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Size
rs )k
k a
x Map k a
forall k a. Map k a
Tip Map k a
r (Bin Size
ls k
lk a
lx Map k a
ll Map k a
lr )|Size
ls Size -> Size -> Bool
forall a. Ord a => a -> a -> Bool
> Size
delta Size -> Size -> Size
forall a. Num a => a -> a -> a
* Size
rs ->case(Map k a
ll ,Map k a
lr )of(Bin Size
lls k
_a
_Map k a
_Map k a
_,Bin Size
lrs k
lrk a
lrx Map k a
lrl Map k a
lrr )|Size
lrs Size -> Size -> Bool
forall a. Ord a => a -> a -> Bool
< Size
ratio Size -> Size -> Size
forall a. Num a => a -> a -> a
* Size
lls ->Size -> k -> a -> Map k a -> Map k a -> Map k a
forall k a. Size -> k -> a -> Map k a -> Map k a -> Map k a
Bin (Size
1Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Size
ls Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Size
rs )k
lk a
lx Map k a
ll (Size -> k -> a -> Map k a -> Map k a -> Map k a
forall k a. Size -> k -> a -> Map k a -> Map k a -> Map k a
Bin (Size
1Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Size
rs Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Size
lrs )k
k a
x Map k a
lr Map k a
r )|Bool
otherwise ->Size -> k -> a -> Map k a -> Map k a -> Map k a
forall k a. Size -> k -> a -> Map k a -> Map k a -> Map k a
Bin (Size
1Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Size
ls Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Size
rs )k
lrk a
lrx (Size -> k -> a -> Map k a -> Map k a -> Map k a
forall k a. Size -> k -> a -> Map k a -> Map k a -> Map k a
Bin (Size
1Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Size
lls Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Map k a -> Size
forall k a. Map k a -> Size
size Map k a
lrl )k
lk a
lx Map k a
ll Map k a
lrl )(Size -> k -> a -> Map k a -> Map k a -> Map k a
forall k a. Size -> k -> a -> Map k a -> Map k a -> Map k a
Bin (Size
1Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Size
rs Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Map k a -> Size
forall k a. Map k a -> Size
size Map k a
lrr )k
k a
x Map k a
lrr Map k a
r )(Map k a
_,Map k a
_)->[Char] -> Map k a
forall a. HasCallStack => [Char] -> a
error [Char]
"Failure in Data.Map.balanceL"|Bool
otherwise ->Size -> k -> a -> Map k a -> Map k a -> Map k a
forall k a. Size -> k -> a -> Map k a -> Map k a -> Map k a
Bin (Size
1Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Size
ls Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Size
rs )k
k a
x Map k a
l Map k a
r {-# NOINLINEbalanceL #-}balanceR ::k ->a ->Map k a ->Map k a ->Map k a balanceR :: forall k a. k -> a -> Map k a -> Map k a -> Map k a
balanceR k
k a
x Map k a
l Map k a
r =caseMap k a
l ofMap k a
Tip ->caseMap k a
r ofMap k a
Tip ->Size -> k -> a -> Map k a -> Map k a -> Map k a
forall k a. Size -> k -> a -> Map k a -> Map k a -> Map k a
Bin Size
1k
k a
x Map k a
forall k a. Map k a
Tip Map k a
forall k a. Map k a
Tip (Bin Size
_k
_a
_Map k a
Tip Map k a
Tip )->Size -> k -> a -> Map k a -> Map k a -> Map k a
forall k a. Size -> k -> a -> Map k a -> Map k a -> Map k a
Bin Size
2k
k a
x Map k a
forall k a. Map k a
Tip Map k a
r (Bin Size
_k
rk a
rx Map k a
Tip rr :: Map k a
rr @(Bin Size
_k
_a
_Map k a
_Map k a
_))->Size -> k -> a -> Map k a -> Map k a -> Map k a
forall k a. Size -> k -> a -> Map k a -> Map k a -> Map k a
Bin Size
3k
rk a
rx (Size -> k -> a -> Map k a -> Map k a -> Map k a
forall k a. Size -> k -> a -> Map k a -> Map k a -> Map k a
Bin Size
1k
k a
x Map k a
forall k a. Map k a
Tip Map k a
forall k a. Map k a
Tip )Map k a
rr (Bin Size
_k
rk a
rx (Bin Size
_k
rlk a
rlx Map k a
_Map k a
_)Map k a
Tip )->Size -> k -> a -> Map k a -> Map k a -> Map k a
forall k a. Size -> k -> a -> Map k a -> Map k a -> Map k a
Bin Size
3k
rlk a
rlx (Size -> k -> a -> Map k a -> Map k a -> Map k a
forall k a. Size -> k -> a -> Map k a -> Map k a -> Map k a
Bin Size
1k
k a
x Map k a
forall k a. Map k a
Tip Map k a
forall k a. Map k a
Tip )(Size -> k -> a -> Map k a -> Map k a -> Map k a
forall k a. Size -> k -> a -> Map k a -> Map k a -> Map k a
Bin Size
1k
rk a
rx Map k a
forall k a. Map k a
Tip Map k a
forall k a. Map k a
Tip )(Bin Size
rs k
rk a
rx rl :: Map k a
rl @(Bin Size
rls k
rlk a
rlx Map k a
rll Map k a
rlr )rr :: Map k a
rr @(Bin Size
rrs k
_a
_Map k a
_Map k a
_))|Size
rls Size -> Size -> Bool
forall a. Ord a => a -> a -> Bool
< Size
ratio Size -> Size -> Size
forall a. Num a => a -> a -> a
* Size
rrs ->Size -> k -> a -> Map k a -> Map k a -> Map k a
forall k a. Size -> k -> a -> Map k a -> Map k a -> Map k a
Bin (Size
1Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Size
rs )k
rk a
rx (Size -> k -> a -> Map k a -> Map k a -> Map k a
forall k a. Size -> k -> a -> Map k a -> Map k a -> Map k a
Bin (Size
1Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Size
rls )k
k a
x Map k a
forall k a. Map k a
Tip Map k a
rl )Map k a
rr |Bool
otherwise ->Size -> k -> a -> Map k a -> Map k a -> Map k a
forall k a. Size -> k -> a -> Map k a -> Map k a -> Map k a
Bin (Size
1Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Size
rs )k
rlk a
rlx (Size -> k -> a -> Map k a -> Map k a -> Map k a
forall k a. Size -> k -> a -> Map k a -> Map k a -> Map k a
Bin (Size
1Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Map k a -> Size
forall k a. Map k a -> Size
size Map k a
rll )k
k a
x Map k a
forall k a. Map k a
Tip Map k a
rll )(Size -> k -> a -> Map k a -> Map k a -> Map k a
forall k a. Size -> k -> a -> Map k a -> Map k a -> Map k a
Bin (Size
1Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Size
rrs Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Map k a -> Size
forall k a. Map k a -> Size
size Map k a
rlr )k
rk a
rx Map k a
rlr Map k a
rr )(Bin Size
ls k
_a
_Map k a
_Map k a
_)->caseMap k a
r ofMap k a
Tip ->Size -> k -> a -> Map k a -> Map k a -> Map k a
forall k a. Size -> k -> a -> Map k a -> Map k a -> Map k a
Bin (Size
1Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Size
ls )k
k a
x Map k a
l Map k a
forall k a. Map k a
Tip (Bin Size
rs k
rk a
rx Map k a
rl Map k a
rr )|Size
rs Size -> Size -> Bool
forall a. Ord a => a -> a -> Bool
> Size
delta Size -> Size -> Size
forall a. Num a => a -> a -> a
* Size
ls ->case(Map k a
rl ,Map k a
rr )of(Bin Size
rls k
rlk a
rlx Map k a
rll Map k a
rlr ,Bin Size
rrs k
_a
_Map k a
_Map k a
_)|Size
rls Size -> Size -> Bool
forall a. Ord a => a -> a -> Bool
< Size
ratio Size -> Size -> Size
forall a. Num a => a -> a -> a
* Size
rrs ->Size -> k -> a -> Map k a -> Map k a -> Map k a
forall k a. Size -> k -> a -> Map k a -> Map k a -> Map k a
Bin (Size
1Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Size
ls Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Size
rs )k
rk a
rx (Size -> k -> a -> Map k a -> Map k a -> Map k a
forall k a. Size -> k -> a -> Map k a -> Map k a -> Map k a
Bin (Size
1Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Size
ls Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Size
rls )k
k a
x Map k a
l Map k a
rl )Map k a
rr |Bool
otherwise ->Size -> k -> a -> Map k a -> Map k a -> Map k a
forall k a. Size -> k -> a -> Map k a -> Map k a -> Map k a
Bin (Size
1Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Size
ls Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Size
rs )k
rlk a
rlx (Size -> k -> a -> Map k a -> Map k a -> Map k a
forall k a. Size -> k -> a -> Map k a -> Map k a -> Map k a
Bin (Size
1Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Size
ls Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Map k a -> Size
forall k a. Map k a -> Size
size Map k a
rll )k
k a
x Map k a
l Map k a
rll )(Size -> k -> a -> Map k a -> Map k a -> Map k a
forall k a. Size -> k -> a -> Map k a -> Map k a -> Map k a
Bin (Size
1Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Size
rrs Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Map k a -> Size
forall k a. Map k a -> Size
size Map k a
rlr )k
rk a
rx Map k a
rlr Map k a
rr )(Map k a
_,Map k a
_)->[Char] -> Map k a
forall a. HasCallStack => [Char] -> a
error [Char]
"Failure in Data.Map.balanceR"|Bool
otherwise ->Size -> k -> a -> Map k a -> Map k a -> Map k a
forall k a. Size -> k -> a -> Map k a -> Map k a -> Map k a
Bin (Size
1Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Size
ls Size -> Size -> Size
forall a. Num a => a -> a -> a
+ Size
rs )k
k a
x Map k a
l Map k a
r {-# NOINLINEbalanceR #-}delta ,ratio ::Int delta :: Size
delta =Size
3ratio :: Size
ratio =Size
2