    {-# 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 GHC.Internal.TH.Lib.Map
        ( Map
        , empty
        , insert
        , GHC.Internal.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 :: forall k a. Map k a
    empty = Map k a
    forall k a. Map k a
    Tip
    {-# INLINE empty #-}

    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
    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 :: forall k a. 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 :: 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
      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 :: 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
      where
        go :: 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) =
            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 :: 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 = 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 :: 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 = 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