    {-# LANGUAGE CPP #-}
    {-# LANGUAGE BangPatterns #-}
    #if !defined(TESTING) && defined(__GLASGOW_HASKELL__)
    {-# LANGUAGE Trustworthy #-}
    #endif

    {-# OPTIONS_HADDOCK not-home #-}

    -----------------------------------------------------------------------------
    -- |
    -- Copyright   :  (c) Daan Leijen 2002
    -- License     :  BSD-style
    --
    -- = WARNING
    --
    -- This module is considered __internal__.
    --
    -- The Package Versioning Policy __does not apply__.
    --
    -- This contents of this module may change __in any way whatsoever__
    -- and __without any warning__ between minor versions of this package.
    --
    -- Authors importing this module are expected to track development
    -- closely.
    --
    -- = Description
    --
    -- An efficient implementation of sets.
    --
    -- These modules are intended to be imported qualified, to avoid name
    -- clashes with Prelude functions, e.g.
    --
    -- >  import Data.Set (Set)
    -- >  import qualified Data.Set as Set
    --
    -- The implementation of 'Set' is based on /size balanced/ binary trees (or
    -- trees of /bounded balance/) as described by:
    --
    --    * Stephen Adams, \"/Efficient sets: a balancing act/\",
    --      Journal of Functional Programming 3(4):553-562, October 1993,
    --      <http://www.swiss.ai.mit.edu/~adams/BB/>.
    --    * J. Nievergelt and E.M. Reingold,
    --      \"/Binary search trees of bounded balance/\",
    --      SIAM journal of computing 2(1), March 1973.
    --
    --  Bounds for 'union', 'intersection', and 'difference' are as given
    --  by
    --
    --    * Guy Blelloch, Daniel Ferizovic, and Yihan Sun,
    --      \"/Just Join for Parallel Ordered Sets/\",
    --      <https://arxiv.org/abs/1602.02120v3>.
    --
    -- Note that the implementation is /left-biased/ -- the elements of a
    -- first argument are always preferred to the second, for example in
    -- 'union' or 'insert'.  Of course, left-biasing can only be observed
    -- when equality is an equivalence relation instead of structural
    -- equality.
    --
    -- /Warning/: The size of the set must not exceed @maxBound::Int@. Violation of
    -- this condition is not detected and if the size limit is exceeded, the
    -- behavior of the set is completely undefined.
    --
    -- @since 0.5.9
    -----------------------------------------------------------------------------

    -- [Note: Using INLINABLE]
    -- ~~~~~~~~~~~~~~~~~~~~~~~
    -- It is crucial to the performance that the functions specialize on the Ord
    -- type when possible. GHC 7.0 and higher does this by itself when it sees th
    -- unfolding of a function -- that is why all public functions are marked
    -- INLINABLE (that exposes the unfolding).

    -- [Note: Using INLINE]
    -- ~~~~~~~~~~~~~~~~~~~~
    -- For other compilers and GHC pre 7.0, we mark some of the functions INLINE.
    -- We mark the functions that just navigate down the tree (lookup, insert,
    -- delete and similar). That navigation code gets inlined and thus specialized
    -- when possible. There is a price to pay -- code growth. The code INLINED is
    -- therefore only the tree navigation, all the real work (rebalancing) is not
    -- INLINED by using a NOINLINE.
    --
    -- All methods marked INLINE have to be nonrecursive -- a 'go' function doing
    -- the real work is provided.

    -- [Note: Type of local 'go' function]
    -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    -- If the local 'go' function uses an Ord class, it sometimes heap-allocates
    -- the Ord dictionary when the 'go' function does not have explicit type.
    -- In that case we give 'go' explicit type. But this slightly decrease
    -- performance, as the resulting 'go' function can float out to top level.

    -- [Note: Local 'go' functions and capturing]
    -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    -- As opposed to IntSet, when 'go' function captures an argument, increased
    -- heap-allocation can occur: sometimes in a polymorphic function, the 'go'
    -- floats out of its enclosing function and then it heap-allocates the
    -- dictionary and the argument. Maybe it floats out too late and strictness
    -- analyzer cannot see that these could be passed on stack.

    -- [Note: Order of constructors]
    -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    -- The order of constructors of Set matters when considering performance.
    -- Currently in GHC 7.0, when type has 2 constructors, a forward conditional
    -- jump is made when successfully matching second constructor. Successful match
    -- of first constructor results in the forward jump not taken.
    -- On GHC 7.0, reordering constructors from Tip | Bin to Bin | Tip
    -- improves the benchmark by up to 10% on x86.

    module Data.Set.Private (
                -- * Set type
                  Set(..)       -- instance Eq,Ord,Show,Read,Data,Typeable
                , Size
                , insertBy'
                , empty
                ) where

    import Prelude hiding (filter,foldl,foldr,null,map,take,drop,splitAt)
    import Control.Monad (join)

    #if __GLASGOW_HASKELL__
    import GHC.Exts ( lazy )
    #endif

    {--------------------------------------------------------------------
      Sets are size balanced trees
    --------------------------------------------------------------------}
    -- | A set of values @a@.

    -- See Note: Order of constructors
    data Set a = Bin {-# UNPACK #-} !Size !a !(Set a) !(Set a) | Tip

    type Size     = Int

    {--------------------------------------------------------------------
      Query
    --------------------------------------------------------------------}
    -- | /O(1)/. The number of elements in the set.
    size :: Set a -> Int
    size :: forall a. Set a -> Int
    size Set a
    Tip = Int
    0
    size (Bin Int
    sz a
    _ Set a
    _ Set a
    _) = Int
    sz

    {--------------------------------------------------------------------
      Construction
    --------------------------------------------------------------------}
    -- | /O(1)/. The empty set.
    empty :: Set a
    empty :: forall a. Set a
    empty = Set a
    forall a. Set a
    Tip

    -- | /O(1)/. Create a singleton set.
    singleton :: a -> Set a
    singleton :: forall a. a -> Set a
    singleton a
    x = Int -> a -> Set a -> Set a -> Set a
    forall a. Int -> a -> Set a -> Set a -> Set a
    Bin Int
    1 a
    x Set a
    forall a. Set a
    Tip Set a
    forall a. Set a
    Tip

    {--------------------------------------------------------------------
      Insertion, Deletion
    --------------------------------------------------------------------}
    -- | /O(log n)/. Insert an element in a set.
    -- If the set already contains an element equal to the given value,
    -- it is replaced with the new value.

    -- See Note: Type of local 'go' function
    -- See Note: Avoiding worker/wrapper (in Data.Map.Internal)
    insertBy' :: (a -> a -> Ordering) -> a -> Set a -> Maybe (Set a)
    insertBy' :: forall a. (a -> a -> Ordering) -> a -> Set a -> Maybe (Set a)
    insertBy' a -> a -> Ordering
    compare = (a -> a -> Set a -> Maybe (Set a)) -> a -> Set a -> Maybe (Set a)
    forall (m :: * -> *) a. Monad m => m (m a) -> m a
    join a -> a -> Set a -> Maybe (Set a)
    go
      where
        go :: a -> a -> Set a -> Maybe (Set a)
    go a
    orig !a
    _ Set a
    Tip = Set a -> Maybe (Set a)
    forall a. a -> Maybe a
    Just (Set a -> Maybe (Set a)) -> Set a -> Maybe (Set a)
    forall a b. (a -> b) -> a -> b
    $! a -> Set a
    forall a. a -> Set a
    singleton (a -> a
    forall a. a -> a
    lazy a
    orig)
        go a
    orig !a
    x (Bin Int
    _ a
    y Set a
    l Set a
    r) = case a -> a -> Ordering
    compare a
    x a
    y of
            Ordering
    LT -> (\ !Set a
    l' -> a -> Set a -> Set a -> Set a
    forall a. a -> Set a -> Set a -> Set a
    balanceL a
    y Set a
    l' Set a
    r) (Set a -> Set a) -> Maybe (Set a) -> Maybe (Set a)
    forall a b. (a -> b) -> Maybe a -> Maybe b
    <$!> a -> a -> Set a -> Maybe (Set a)
    go a
    orig a
    x Set a
    l
            Ordering
    GT -> (\ !Set a
    r' -> a -> Set a -> Set a -> Set a
    forall a. a -> Set a -> Set a -> Set a
    balanceR a
    y Set a
    l Set a
    r') (Set a -> Set a) -> Maybe (Set a) -> Maybe (Set a)
    forall a b. (a -> b) -> Maybe a -> Maybe b
    <$!> a -> a -> Set a -> Maybe (Set a)
    go a
    orig a
    x Set a
    r
            Ordering
    EQ -> Maybe (Set a)
    forall a. Maybe a
    Nothing
    #if __GLASGOW_HASKELL__
    {-# INLINABLE insertBy' #-}
    #else
    {-# INLINE insertBy' #-}
    #endif

    infixl 4 <$!>
    (<$!>) :: (a -> b) -> Maybe a -> Maybe b
    <$!> :: forall a b. (a -> b) -> Maybe a -> Maybe b
    (<$!>) a -> b
    f = \ case
        Maybe a
    Nothing -> Maybe b
    forall a. Maybe a
    Nothing
        Just a
    a -> b -> Maybe b
    forall a. a -> Maybe a
    Just (b -> Maybe b) -> b -> Maybe b
    forall a b. (a -> b) -> a -> b
    $! a -> b
    f a
    a

    #ifndef __GLASGOW_HASKELL__
    lazy :: a -> a
    lazy a = a
    #endif

    {--------------------------------------------------------------------
      [balance x l r] balances two trees with value x.
      The sizes of the trees should balance after decreasing the
      size of one of them. (a rotation).

      [delta] is the maximal relative difference between the sizes of
              two trees, it corresponds with the [w] in Adams' paper.
      [ratio] is the ratio between an outer and inner sibling of the
              heavier subtree in an unbalanced setting. It determines
              whether a double or single rotation should be performed
              to restore balance. It is correspondes with the inverse
              of $\alpha$ in Adam's article.

      Note that according to the Adam's paper:
      - [delta] should be larger than 4.646 with a [ratio] of 2.
      - [delta] should be larger than 3.745 with a [ratio] of 1.534.

      But the Adam's paper is errorneous:
      - it can be proved that for delta=2 and delta>=5 there does
        not exist any ratio that would work
      - delta=4.5 and ratio=2 does not work

      That leaves two reasonable variants, delta=3 and delta=4,
      both with ratio=2.

      - A lower [delta] leads to a more 'perfectly' balanced tree.
      - A higher [delta] performs less rebalancing.

      In the benchmarks, delta=3 is faster on insert operations,
      and delta=4 has slightly better deletes. As the insert speedup
      is larger, we currently use delta=3.

    --------------------------------------------------------------------}
    delta,ratio :: Int
    delta :: Int
    delta = Int
    3
    ratio :: Int
    ratio = Int
    2

    -- The balance function is equivalent to the following:
    --
    --   balance :: a -> Set a -> Set a -> Set a
    --   balance x l r
    --     | sizeL + sizeR <= 1   = Bin sizeX x l r
    --     | sizeR > delta*sizeL  = rotateL x l r
    --     | sizeL > delta*sizeR  = rotateR x l r
    --     | otherwise            = Bin sizeX x l r
    --     where
    --       sizeL = size l
    --       sizeR = size r
    --       sizeX = sizeL + sizeR + 1
    --
    --   rotateL :: a -> Set a -> Set a -> Set a
    --   rotateL x l r@(Bin _ _ ly ry) | size ly < ratio*size ry = singleL x l r
    --                                 | otherwise               = doubleL x l r
    --   rotateR :: a -> Set a -> Set a -> Set a
    --   rotateR x l@(Bin _ _ ly ry) r | size ry < ratio*size ly = singleR x l r
    --                                 | otherwise               = doubleR x l r
    --
    --   singleL, singleR :: a -> Set a -> Set a -> Set a
    --   singleL x1 t1 (Bin _ x2 t2 t3)  = bin x2 (bin x1 t1 t2) t3
    --   singleR x1 (Bin _ x2 t1 t2) t3  = bin x2 t1 (bin x1 t2 t3)
    --
    --   doubleL, doubleR :: a -> Set a -> Set a -> Set a
    --   doubleL x1 t1 (Bin _ x2 (Bin _ x3 t2 t3) t4) = bin x3 (bin x1 t1 t2) (bin x2 t3 t4)
    --   doubleR x1 (Bin _ x2 t1 (Bin _ x3 t2 t3)) t4 = bin x3 (bin x2 t1 t2) (bin x1 t3 t4)
    --
    -- It is only written in such a way that every node is pattern-matched only once.
    --
    -- Only balanceL and balanceR are needed at the moment, so balance is not here anymore.
    -- In case it is needed, it can be found in Data.Map.

    -- Functions balanceL and balanceR are specialised versions of balance.
    -- balanceL only checks whether the left subtree is too big,
    -- balanceR only checks whether the right subtree is too big.

    -- balanceL is called when left subtree might have been inserted to or when
    -- right subtree might have been deleted from.
    balanceL :: a -> Set a -> Set a -> Set a
    balanceL :: forall a. a -> Set a -> Set a -> Set a
    balanceL a
    x Set a
    l Set a
    r = case Set a
    r of
      Set a
    Tip -> case Set a
    l of
               Set a
    Tip -> Int -> a -> Set a -> Set a -> Set a
    forall a. Int -> a -> Set a -> Set a -> Set a
    Bin Int
    1 a
    x Set a
    forall a. Set a
    Tip Set a
    forall a. Set a
    Tip
               (Bin Int
    _ a
    _ Set a
    Tip Set a
    Tip) -> Int -> a -> Set a -> Set a -> Set a
    forall a. Int -> a -> Set a -> Set a -> Set a
    Bin Int
    2 a
    x Set a
    l Set a
    forall a. Set a
    Tip
               (Bin Int
    _ a
    lx Set a
    Tip (Bin Int
    _ a
    lrx Set a
    _ Set a
    _)) -> Int -> a -> Set a -> Set a -> Set a
    forall a. Int -> a -> Set a -> Set a -> Set a
    Bin Int
    3 a
    lrx (Int -> a -> Set a -> Set a -> Set a
    forall a. Int -> a -> Set a -> Set a -> Set a
    Bin Int
    1 a
    lx Set a
    forall a. Set a
    Tip Set a
    forall a. Set a
    Tip) (Int -> a -> Set a -> Set a -> Set a
    forall a. Int -> a -> Set a -> Set a -> Set a
    Bin Int
    1 a
    x Set a
    forall a. Set a
    Tip Set a
    forall a. Set a
    Tip)
               (Bin Int
    _ a
    lx ll :: Set a
    ll@(Bin Int
    _ a
    _ Set a
    _ Set a
    _) Set a
    Tip) -> Int -> a -> Set a -> Set a -> Set a
    forall a. Int -> a -> Set a -> Set a -> Set a
    Bin Int
    3 a
    lx Set a
    ll (Int -> a -> Set a -> Set a -> Set a
    forall a. Int -> a -> Set a -> Set a -> Set a
    Bin Int
    1 a
    x Set a
    forall a. Set a
    Tip Set a
    forall a. Set a
    Tip)
               (Bin Int
    ls a
    lx ll :: Set a
    ll@(Bin Int
    lls a
    _ Set a
    _ Set a
    _) lr :: Set a
    lr@(Bin Int
    lrs a
    lrx Set a
    lrl Set a
    lrr))
                 | Int
    lrs Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    < Int
    ratioInt -> Int -> Int
    forall a. Num a => a -> a -> a
    *Int
    lls -> Int -> a -> Set a -> Set a -> Set a
    forall a. Int -> a -> Set a -> Set a -> Set a
    Bin (Int
    1Int -> Int -> Int
    forall a. Num a => a -> a -> a
    +Int
    ls) a
    lx Set a
    ll (Int -> a -> Set a -> Set a -> Set a
    forall a. Int -> a -> Set a -> Set a -> Set a
    Bin (Int
    1Int -> Int -> Int
    forall a. Num a => a -> a -> a
    +Int
    lrs) a
    x Set a
    lr Set a
    forall a. Set a
    Tip)
                 | Bool
    otherwise -> Int -> a -> Set a -> Set a -> Set a
    forall a. Int -> a -> Set a -> Set a -> Set a
    Bin (Int
    1Int -> Int -> Int
    forall a. Num a => a -> a -> a
    +Int
    ls) a
    lrx (Int -> a -> Set a -> Set a -> Set a
    forall a. Int -> a -> Set a -> Set a -> Set a
    Bin (Int
    1Int -> Int -> Int
    forall a. Num a => a -> a -> a
    +Int
    llsInt -> Int -> Int
    forall a. Num a => a -> a -> a
    +Set a -> Int
    forall a. Set a -> Int
    size Set a
    lrl) a
    lx Set a
    ll Set a
    lrl) (Int -> a -> Set a -> Set a -> Set a
    forall a. Int -> a -> Set a -> Set a -> Set a
    Bin (Int
    1Int -> Int -> Int
    forall a. Num a => a -> a -> a
    +Set a -> Int
    forall a. Set a -> Int
    size Set a
    lrr) a
    x Set a
    lrr Set a
    forall a. Set a
    Tip)

      (Bin Int
    rs a
    _ Set a
    _ Set a
    _) -> case Set a
    l of
               Set a
    Tip -> Int -> a -> Set a -> Set a -> Set a
    forall a. Int -> a -> Set a -> Set a -> Set a
    Bin (Int
    1Int -> Int -> Int
    forall a. Num a => a -> a -> a
    +Int
    rs) a
    x Set a
    forall a. Set a
    Tip Set a
    r

               (Bin Int
    ls a
    lx Set a
    ll Set a
    lr)
                  | Int
    ls Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    > Int
    deltaInt -> Int -> Int
    forall a. Num a => a -> a -> a
    *Int
    rs  -> case (Set a
    ll, Set a
    lr) of
                       (Bin Int
    lls a
    _ Set a
    _ Set a
    _, Bin Int
    lrs a
    lrx Set a
    lrl Set a
    lrr)
                         | Int
    lrs Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    < Int
    ratioInt -> Int -> Int
    forall a. Num a => a -> a -> a
    *Int
    lls -> Int -> a -> Set a -> Set a -> Set a
    forall a. Int -> a -> Set a -> Set a -> Set a
    Bin (Int
    1Int -> Int -> Int
    forall a. Num a => a -> a -> a
    +Int
    lsInt -> Int -> Int
    forall a. Num a => a -> a -> a
    +Int
    rs) a
    lx Set a
    ll (Int -> a -> Set a -> Set a -> Set a
    forall a. Int -> a -> Set a -> Set a -> Set a
    Bin (Int
    1Int -> Int -> Int
    forall a. Num a => a -> a -> a
    +Int
    rsInt -> Int -> Int
    forall a. Num a => a -> a -> a
    +Int
    lrs) a
    x Set a
    lr Set a
    r)
                         | Bool
    otherwise -> Int -> a -> Set a -> Set a -> Set a
    forall a. Int -> a -> Set a -> Set a -> Set a
    Bin (Int
    1Int -> Int -> Int
    forall a. Num a => a -> a -> a
    +Int
    lsInt -> Int -> Int
    forall a. Num a => a -> a -> a
    +Int
    rs) a
    lrx (Int -> a -> Set a -> Set a -> Set a
    forall a. Int -> a -> Set a -> Set a -> Set a
    Bin (Int
    1Int -> Int -> Int
    forall a. Num a => a -> a -> a
    +Int
    llsInt -> Int -> Int
    forall a. Num a => a -> a -> a
    +Set a -> Int
    forall a. Set a -> Int
    size Set a
    lrl) a
    lx Set a
    ll Set a
    lrl) (Int -> a -> Set a -> Set a -> Set a
    forall a. Int -> a -> Set a -> Set a -> Set a
    Bin (Int
    1Int -> Int -> Int
    forall a. Num a => a -> a -> a
    +Int
    rsInt -> Int -> Int
    forall a. Num a => a -> a -> a
    +Set a -> Int
    forall a. Set a -> Int
    size Set a
    lrr) a
    x Set a
    lrr Set a
    r)
                       (Set a
    _, Set a
    _) -> [Char] -> Set a
    forall a. HasCallStack => [Char] -> a
    error [Char]
    "Failure in Data.Map.balanceL"
                  | Bool
    otherwise -> Int -> a -> Set a -> Set a -> Set a
    forall a. Int -> a -> Set a -> Set a -> Set a
    Bin (Int
    1Int -> Int -> Int
    forall a. Num a => a -> a -> a
    +Int
    lsInt -> Int -> Int
    forall a. Num a => a -> a -> a
    +Int
    rs) a
    x Set a
    l Set a
    r
    {-# NOINLINE balanceL #-}

    -- balanceR is called when right subtree might have been inserted to or when
    -- left subtree might have been deleted from.
    balanceR :: a -> Set a -> Set a -> Set a
    balanceR :: forall a. a -> Set a -> Set a -> Set a
    balanceR a
    x Set a
    l Set a
    r = case Set a
    l of
      Set a
    Tip -> case Set a
    r of
               Set a
    Tip -> Int -> a -> Set a -> Set a -> Set a
    forall a. Int -> a -> Set a -> Set a -> Set a
    Bin Int
    1 a
    x Set a
    forall a. Set a
    Tip Set a
    forall a. Set a
    Tip
               (Bin Int
    _ a
    _ Set a
    Tip Set a
    Tip) -> Int -> a -> Set a -> Set a -> Set a
    forall a. Int -> a -> Set a -> Set a -> Set a
    Bin Int
    2 a
    x Set a
    forall a. Set a
    Tip Set a
    r
               (Bin Int
    _ a
    rx Set a
    Tip rr :: Set a
    rr@(Bin Int
    _ a
    _ Set a
    _ Set a
    _)) -> Int -> a -> Set a -> Set a -> Set a
    forall a. Int -> a -> Set a -> Set a -> Set a
    Bin Int
    3 a
    rx (Int -> a -> Set a -> Set a -> Set a
    forall a. Int -> a -> Set a -> Set a -> Set a
    Bin Int
    1 a
    x Set a
    forall a. Set a
    Tip Set a
    forall a. Set a
    Tip) Set a
    rr
               (Bin Int
    _ a
    rx (Bin Int
    _ a
    rlx Set a
    _ Set a
    _) Set a
    Tip) -> Int -> a -> Set a -> Set a -> Set a
    forall a. Int -> a -> Set a -> Set a -> Set a
    Bin Int
    3 a
    rlx (Int -> a -> Set a -> Set a -> Set a
    forall a. Int -> a -> Set a -> Set a -> Set a
    Bin Int
    1 a
    x Set a
    forall a. Set a
    Tip Set a
    forall a. Set a
    Tip) (Int -> a -> Set a -> Set a -> Set a
    forall a. Int -> a -> Set a -> Set a -> Set a
    Bin Int
    1 a
    rx Set a
    forall a. Set a
    Tip Set a
    forall a. Set a
    Tip)
               (Bin Int
    rs a
    rx rl :: Set a
    rl@(Bin Int
    rls a
    rlx Set a
    rll Set a
    rlr) rr :: Set a
    rr@(Bin Int
    rrs a
    _ Set a
    _ Set a
    _))
                 | Int
    rls Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    < Int
    ratioInt -> Int -> Int
    forall a. Num a => a -> a -> a
    *Int
    rrs -> Int -> a -> Set a -> Set a -> Set a
    forall a. Int -> a -> Set a -> Set a -> Set a
    Bin (Int
    1Int -> Int -> Int
    forall a. Num a => a -> a -> a
    +Int
    rs) a
    rx (Int -> a -> Set a -> Set a -> Set a
    forall a. Int -> a -> Set a -> Set a -> Set a
    Bin (Int
    1Int -> Int -> Int
    forall a. Num a => a -> a -> a
    +Int
    rls) a
    x Set a
    forall a. Set a
    Tip Set a
    rl) Set a
    rr
                 | Bool
    otherwise -> Int -> a -> Set a -> Set a -> Set a
    forall a. Int -> a -> Set a -> Set a -> Set a
    Bin (Int
    1Int -> Int -> Int
    forall a. Num a => a -> a -> a
    +Int
    rs) a
    rlx (Int -> a -> Set a -> Set a -> Set a
    forall a. Int -> a -> Set a -> Set a -> Set a
    Bin (Int
    1Int -> Int -> Int
    forall a. Num a => a -> a -> a
    +Set a -> Int
    forall a. Set a -> Int
    size Set a
    rll) a
    x Set a
    forall a. Set a
    Tip Set a
    rll) (Int -> a -> Set a -> Set a -> Set a
    forall a. Int -> a -> Set a -> Set a -> Set a
    Bin (Int
    1Int -> Int -> Int
    forall a. Num a => a -> a -> a
    +Int
    rrsInt -> Int -> Int
    forall a. Num a => a -> a -> a
    +Set a -> Int
    forall a. Set a -> Int
    size Set a
    rlr) a
    rx Set a
    rlr Set a
    rr)

      (Bin Int
    ls a
    _ Set a
    _ Set a
    _) -> case Set a
    r of
               Set a
    Tip -> Int -> a -> Set a -> Set a -> Set a
    forall a. Int -> a -> Set a -> Set a -> Set a
    Bin (Int
    1Int -> Int -> Int
    forall a. Num a => a -> a -> a
    +Int
    ls) a
    x Set a
    l Set a
    forall a. Set a
    Tip

               (Bin Int
    rs a
    rx Set a
    rl Set a
    rr)
                  | Int
    rs Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    > Int
    deltaInt -> Int -> Int
    forall a. Num a => a -> a -> a
    *Int
    ls  -> case (Set a
    rl, Set a
    rr) of
                       (Bin Int
    rls a
    rlx Set a
    rll Set a
    rlr, Bin Int
    rrs a
    _ Set a
    _ Set a
    _)
                         | Int
    rls Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    < Int
    ratioInt -> Int -> Int
    forall a. Num a => a -> a -> a
    *Int
    rrs -> Int -> a -> Set a -> Set a -> Set a
    forall a. Int -> a -> Set a -> Set a -> Set a
    Bin (Int
    1Int -> Int -> Int
    forall a. Num a => a -> a -> a
    +Int
    lsInt -> Int -> Int
    forall a. Num a => a -> a -> a
    +Int
    rs) a
    rx (Int -> a -> Set a -> Set a -> Set a
    forall a. Int -> a -> Set a -> Set a -> Set a
    Bin (Int
    1Int -> Int -> Int
    forall a. Num a => a -> a -> a
    +Int
    lsInt -> Int -> Int
    forall a. Num a => a -> a -> a
    +Int
    rls) a
    x Set a
    l Set a
    rl) Set a
    rr
                         | Bool
    otherwise -> Int -> a -> Set a -> Set a -> Set a
    forall a. Int -> a -> Set a -> Set a -> Set a
    Bin (Int
    1Int -> Int -> Int
    forall a. Num a => a -> a -> a
    +Int
    lsInt -> Int -> Int
    forall a. Num a => a -> a -> a
    +Int
    rs) a
    rlx (Int -> a -> Set a -> Set a -> Set a
    forall a. Int -> a -> Set a -> Set a -> Set a
    Bin (Int
    1Int -> Int -> Int
    forall a. Num a => a -> a -> a
    +Int
    lsInt -> Int -> Int
    forall a. Num a => a -> a -> a
    +Set a -> Int
    forall a. Set a -> Int
    size Set a
    rll) a
    x Set a
    l Set a
    rll) (Int -> a -> Set a -> Set a -> Set a
    forall a. Int -> a -> Set a -> Set a -> Set a
    Bin (Int
    1Int -> Int -> Int
    forall a. Num a => a -> a -> a
    +Int
    rrsInt -> Int -> Int
    forall a. Num a => a -> a -> a
    +Set a -> Int
    forall a. Set a -> Int
    size Set a
    rlr) a
    rx Set a
    rlr Set a
    rr)
                       (Set a
    _, Set a
    _) -> [Char] -> Set a
    forall a. HasCallStack => [Char] -> a
    error [Char]
    "Failure in Data.Map.balanceR"
                  | Bool
    otherwise -> Int -> a -> Set a -> Set a -> Set a
    forall a. Int -> a -> Set a -> Set a -> Set a
    Bin (Int
    1Int -> Int -> Int
    forall a. Num a => a -> a -> a
    +Int
    lsInt -> Int -> Int
    forall a. Num a => a -> a -> a
    +Int
    rs) a
    x Set a
    l Set a
    r
    {-# NOINLINE balanceR #-}