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

module Language.Haskell.TH.Lib.Map
    ( Map
    , empty
    , insert
    , Language.Haskell.TH.Lib.Map.lookup
    ) where

import Prelude

data Map k a  = Bin {-# UNPACK #-} !Size !k a !(Map k a) !(Map k a)
              | Tip

type Size     = Int

empty :: Map k a
empty :: Map k a
empty = Map k a
forall k a. Map k a
Tip
{-# INLINE empty #-}

singleton :: k -> a -> Map k a
singleton :: 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
1 k
k a
x Map k a
forall k a. Map k a
Tip Map k a
forall k a. Map k a
Tip
{-# INLINE singleton #-}

size :: Map k a -> Int
size :: Map k a -> Size
size Map k a
Tip              = Size
0
size (Bin Size
sz k
_ a
_ Map k a
_ Map k a
_) = Size
sz
{-# INLINE size #-}

lookup :: Ord k => k -> Map k a -> Maybe a
lookup :: k -> Map k a -> Maybe a
lookup = k -> Map k a -> Maybe a
forall t a. Ord t => t -> Map t a -> Maybe a
go
  where
    go :: 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) = case t -> t -> Ordering
forall a. Ord a => a -> a -> Ordering
compare t
k t
kx of
      Ordering
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
{-# INLINABLE lookup #-}


insert :: Ord k => k -> a -> Map k a -> Map k a
insert :: 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
  where
    go :: Ord k => k -> a -> Map k a -> Map k a
    go :: 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) =
        case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
kx k
ky of
            Ordering
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
{-# INLINABLE insert #-}

balanceL :: k -> a -> Map k a -> Map k a -> Map k a
balanceL :: k -> a -> Map k a -> Map k a -> Map k a
balanceL k
k a
x Map k a
l Map k a
r = case Map k a
r of
  Map k a
Tip -> case Map k a
l of
           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
1 k
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
2 k
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
3 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
1 k
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
1 k
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
3 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
1 k
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
ratioSize -> 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
llsSize -> 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
_) -> case Map k a
l of
           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
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
deltaSize -> 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
ratioSize -> 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
lsSize -> 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
rsSize -> 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
lsSize -> 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
llsSize -> 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
rsSize -> 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
lsSize -> Size -> Size
forall a. Num a => a -> a -> a
+Size
rs) k
k a
x Map k a
l Map k a
r
{-# NOINLINE balanceL #-}

balanceR :: k -> a -> Map k a -> Map k a -> Map k a
balanceR :: k -> a -> Map k a -> Map k a -> Map k a
balanceR k
k a
x Map k a
l Map k a
r = case Map k a
l of
  Map k a
Tip -> case Map k a
r of
           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
1 k
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
2 k
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
3 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
1 k
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
3 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
1 k
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
1 k
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
ratioSize -> 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
rrsSize -> 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
_) -> case Map k a
r of
           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
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
deltaSize -> 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
ratioSize -> 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
lsSize -> 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
lsSize -> 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
lsSize -> 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
lsSize -> 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
rrsSize -> 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
lsSize -> Size -> Size
forall a. Num a => a -> a -> a
+Size
rs) k
k a
x Map k a
l Map k a
r
{-# NOINLINE balanceR #-}

delta,ratio :: Int
delta :: Size
delta = Size
3
ratio :: Size
ratio = Size
2