{-# LANGUAGE BangPatterns #-}

-- 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
k x :: 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 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 Tip              = 0
size (Bin sz :: Size
sz _ _ _ _) = 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 _ Tip = Maybe a
forall a. Maybe a
Nothing
    go !t
k (Bin _ kx :: t
kx x :: a
x l :: Map t a
l r :: Map t a
r) = case t -> t -> Ordering
forall a. Ord a => a -> a -> Ordering
compare t
k t
kx of
      LT -> t -> Map t a -> Maybe a
go t
k Map t a
l
      GT -> t -> Map t a -> Maybe a
go t
k Map t a
r
      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 x :: a
x Tip = k -> a -> Map k a
forall k a. k -> a -> Map k a
singleton k
kx a
x
    go !k
kx x :: a
x (Bin sz :: Size
sz ky :: k
ky y :: a
y l :: Map k a
l r :: Map k a
r) =
        case k -> k -> Ordering
forall a. Ord a => a -> a -> Ordering
compare k
kx k
ky of
            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
            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)
            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
k x :: a
x l :: Map k a
l r :: Map k a
r = case Map k a
r of
  Tip -> case Map k a
l of
           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 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 _ _ _ Tip 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 2 k
k a
x Map k a
l Map k a
forall k a. Map k a
Tip
           (Bin _ lk :: k
lk lx :: a
lx Tip (Bin _ lrk :: k
lrk lrx :: 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 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 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 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 _ lk :: k
lk lx :: a
lx ll :: Map k a
ll@(Bin _ _ _ _ _) 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 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 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 ls :: Size
ls lk :: k
lk lx :: a
lx ll :: Map k a
ll@(Bin lls :: Size
lls _ _ _ _) lr :: Map k a
lr@(Bin lrs :: Size
lrs lrk :: k
lrk lrx :: a
lrx lrl :: Map k a
lrl lrr :: 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 (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 (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 (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 (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 (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 rs :: Size
rs _ _ _ _) -> case Map k a
l of
           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 (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 ls :: Size
ls lk :: k
lk lx :: a
lx ll :: Map k a
ll lr :: 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 lls :: Size
lls _ _ _ _, Bin lrs :: Size
lrs lrk :: k
lrk lrx :: a
lrx lrl :: Map k a
lrl lrr :: 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 (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 (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 (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 (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 (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)
                   (_, _) -> [Char] -> Map k a
forall a. HasCallStack => [Char] -> a
error "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 (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
k x :: a
x l :: Map k a
l r :: Map k a
r = case Map k a
l of
  Tip -> case Map k a
r of
           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 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 _ _ _ Tip 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 2 k
k a
x Map k a
forall k a. Map k a
Tip Map k a
r
           (Bin _ rk :: k
rk rx :: a
rx Tip rr :: Map k a
rr@(Bin _ _ _ _ _)) -> 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 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 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 _ rk :: k
rk rx :: a
rx (Bin _ rlk :: k
rlk rlx :: a
rlx _ _) 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 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 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 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 rs :: Size
rs rk :: k
rk rx :: a
rx rl :: Map k a
rl@(Bin rls :: Size
rls rlk :: k
rlk rlx :: a
rlx rll :: Map k a
rll rlr :: Map k a
rlr) rr :: Map k a
rr@(Bin rrs :: Size
rrs _ _ _ _))
             | 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 (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 (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 (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 (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 (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 ls :: Size
ls _ _ _ _) -> case Map k a
r of
           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 (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 rs :: Size
rs rk :: k
rk rx :: a
rx rl :: Map k a
rl rr :: 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 rls :: Size
rls rlk :: k
rlk rlx :: a
rlx rll :: Map k a
rll rlr :: Map k a
rlr, Bin rrs :: Size
rrs _ _ _ _)
                     | 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 (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 (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 (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 (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 (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)
                   (_, _) -> [Char] -> Map k a
forall a. HasCallStack => [Char] -> a
error "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 (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 = 3
ratio :: Size
ratio = 2