    {-# LANGUAGE BangPatterns #-}
    {-# LANGUAGE PatternSynonyms #-}
    {-# LANGUAGE TupleSections #-}
    {-# LANGUAGE ViewPatterns #-}

    -- |
    -- Module      : Data.IntSet.NonEmpty
    -- Copyright   : (c) Justin Le 2018
    -- License     : BSD3
    --
    -- Maintainer  : justin@jle.im
    -- Stability   : experimental
    -- Portability : non-portable
    --
    -- = Non-Empty Finite Integer Sets
    --
    -- The 'NEIntSet' type represents a non-empty set of integers.
    --
    -- See documentation for 'NEIntSet' for information on how to convert and
    -- manipulate such non-empty set.
    --
    -- This module essentially re-imports the API of "Data.IntSet" and its 'IntSet'
    -- type, along with semantics and asymptotics.  In most situations,
    -- asymptotics are different only by a constant factor.  In some
    -- situations, asmyptotics are even better (constant-time instead of
    -- log-time).
    --
    -- Because 'NEIntSet' is implemented using 'IntSet', all of the caveats of
    -- using 'IntSet' apply (such as the limitation of the maximum size of
    -- sets).
    --
    -- All functions take non-empty sets as inputs.  In situations where their
    -- results can be guarunteed to also be non-empty, they also return
    -- non-empty sets.  In situations where their results could potentially be
    -- empty, 'IntSet' is returned instead.
    --
    -- Some functions ('partition', 'split') have modified return types to
    -- account for possible configurations of non-emptiness.
    --
    -- This module is intended to be imported qualified, to avoid name clashes
    -- with "Prelude" and "Data.IntSet" functions:
    --
    -- > import qualified Data.IntSet.NonEmpty as NEIS
    --
    -- Note that all asmyptotics /O(f(n))/ in this module are actually
    -- /O(min(W, f(n)))/, where @W@ is the number of bits in an 'Int' (32 or
    -- 64).  That is, if @f(n)@ is greater than @W@, all operations are
    -- constant-time.
    module Data.IntSet.NonEmpty (
      -- * Non-Empty Set Type
      NEIntSet,
      Key,

      -- ** Conversions between empty and non-empty sets
      pattern IsNonEmpty,
      pattern IsEmpty,
      nonEmptySet,
      toSet,
      withNonEmpty,
      insertSet,
      insertSetMin,
      insertSetMax,
      unsafeFromSet,

      -- * Construction
      singleton,
      fromList,
      fromAscList,
      fromDistinctAscList,

      -- * Insertion
      insert,

      -- * Deletion
      delete,

      -- * Query
      member,
      notMember,
      lookupLT,
      lookupGT,
      lookupLE,
      lookupGE,
      size,
      isSubsetOf,
      isProperSubsetOf,
      disjoint,

      -- * Combine
      union,
      unions,
      difference,
      (\\),
      intersection,

      -- * Filter
      filter,
      partition,
      split,
      splitMember,
      splitRoot,

      -- * Map
      map,

      -- * Folds
      foldr,
      foldl,
      foldr1,
      foldl1,

      -- ** Strict folds
      foldr',
      foldl',
      foldr1',
      foldl1',

      -- * Min\/Max
      findMin,
      findMax,
      deleteMin,
      deleteMax,
      deleteFindMin,
      deleteFindMax,

      -- * Conversion

      -- ** List
      elems,
      toList,
      toAscList,
      toDescList,

      -- * Debugging
      valid,
    ) where

    import Control.Applicative
    import Data.Bifunctor
    import Data.IntSet (IntSet)
    import qualified Data.IntSet as S
    import Data.IntSet.NonEmpty.Internal
    import Data.List.NonEmpty (NonEmpty (..))
    import qualified Data.List.NonEmpty as NE
    import Data.Maybe
    import Data.These
    import Prelude hiding (Foldable (..), filter, map)

    -- | /O(1)/ match, /O(log n)/ usage of contents. The 'IsNonEmpty' and
    -- 'IsEmpty' patterns allow you to treat a 'IntSet' as if it were either
    -- a @'IsNonEmpty' n@ (where @n@ is a 'NEIntSet') or an 'IsEmpty'.
    --
    -- For example, you can pattern match on a 'IntSet':
    --
    -- @
    -- myFunc :: 'IntSet' X -> Y
    -- myFunc ('IsNonEmpty' n) =  -- here, the user provided a non-empty set, and @n@ is the 'NEIntSet'
    -- myFunc 'IsEmpty'        =  -- here, the user provided an empty set
    -- @
    --
    -- Matching on @'IsNonEmpty' n@ means that the original 'IntSet' was /not/
    -- empty, and you have a verified-non-empty 'NEIntSet' @n@ to use.
    --
    -- Note that patching on this pattern is /O(1)/.  However, using the
    -- contents requires a /O(log n)/ cost that is deferred until after the
    -- pattern is matched on (and is not incurred at all if the contents are
    -- never used).
    --
    -- A case statement handling both 'IsNonEmpty' and 'IsEmpty' provides
    -- complete coverage.
    --
    -- This is a bidirectional pattern, so you can use 'IsNonEmpty' to convert
    -- a 'NEIntSet' back into a 'IntSet', obscuring its non-emptiness (see 'toSet').
    pattern IsNonEmpty :: NEIntSet -> IntSet
    pattern $mIsNonEmpty :: forall {r}. IntSet -> (NEIntSet -> r) -> ((# #) -> r) -> r
    $bIsNonEmpty :: NEIntSet -> IntSet
    IsNonEmpty n <- (nonEmptySet -> Just n)
      where
        IsNonEmpty NEIntSet
    n = NEIntSet -> IntSet
    toSet NEIntSet
    n

    -- | /O(1)/. The 'IsNonEmpty' and 'IsEmpty' patterns allow you to treat
    -- a 'IntSet' as if it were either a @'IsNonEmpty' n@ (where @n@ is
    -- a 'NEIntSet') or an 'IsEmpty'.
    --
    -- Matching on 'IsEmpty' means that the original 'IntSet' was empty.
    --
    -- A case statement handling both 'IsNonEmpty' and 'IsEmpty' provides
    -- complete coverage.
    --
    -- This is a bidirectional pattern, so you can use 'IsEmpty' as an
    -- expression, and it will be interpreted as 'Data.IntSet.empty'.
    --
    -- See 'IsNonEmpty' for more information.
    pattern IsEmpty :: IntSet
    pattern $mIsEmpty :: forall {r}. IntSet -> ((# #) -> r) -> ((# #) -> r) -> r
    $bIsEmpty :: IntSet
    IsEmpty <- (S.null -> True)
      where
        IsEmpty = IntSet
    S.empty

    {-# COMPLETE IsNonEmpty, IsEmpty #-}

    -- | /O(log n)/. Convert a 'IntSet' into an 'NEIntSet' by adding a value.
    -- Because of this, we know that the set must have at least one
    -- element, and so therefore cannot be empty.
    --
    -- See 'insertSetMin' for a version that is constant-time if the new
    -- value is /strictly smaller than/ all values in the original set
    --
    -- > insertSet 4 (Data.IntSet.fromList [5, 3]) == fromList (3 :| [4, 5])
    -- > insertSet 4 Data.IntSet.empty == singleton 4 "c"
    insertSet :: Key -> IntSet -> NEIntSet
    insertSet :: Key -> IntSet -> NEIntSet
    insertSet Key
    x = NEIntSet -> (NEIntSet -> NEIntSet) -> IntSet -> NEIntSet
    forall r. r -> (NEIntSet -> r) -> IntSet -> r
    withNonEmpty (Key -> NEIntSet
    singleton Key
    x) (Key -> NEIntSet -> NEIntSet
    insert Key
    x)
    {-# INLINE insertSet #-}

    -- | /O(1)/ Convert a 'IntSet' into an 'NEIntSet' by adding a value where the
    -- value is /strictly less than/ all values in the input set  The values in
    -- the original map must all be /strictly greater than/ the new value.
    -- /The precondition is not checked./
    --
    -- > insertSetMin 2 (Data.IntSet.fromList [5, 3]) == fromList (2 :| [3, 5])
    -- > valid (insertSetMin 2 (Data.IntSet.fromList [5, 3])) == True
    -- > valid (insertSetMin 7 (Data.IntSet.fromList [5, 3])) == False
    -- > valid (insertSetMin 3 (Data.IntSet.fromList [5, 3])) == False
    insertSetMin :: Key -> IntSet -> NEIntSet
    insertSetMin :: Key -> IntSet -> NEIntSet
    insertSetMin = Key -> IntSet -> NEIntSet
    NEIntSet
    {-# INLINE insertSetMin #-}

    -- | /O(log n)/ Convert a 'IntSet' into an 'NEIntSet' by adding a value
    -- where the value is /strictly less than/ all values in the input set  The
    -- values in the original map must all be /strictly greater than/ the new
    -- value.  /The precondition is not checked./
    --
    -- At the current moment, this is identical simply 'insertSet'; however,
    -- it is left both for consistency and as a placeholder for a future
    -- version where optimizations are implemented to allow for a faster
    -- implementation.
    --
    -- > insertSetMin 7 (Data.IntSet.fromList [5, 3]) == fromList (3 :| [5, 7])

    -- these currently are all valid, but shouldn't be
    -- > valid (insertSetMin 7 (Data.IntSet.fromList [5, 3])) == True
    -- > valid (insertSetMin 2 (Data.IntSet.fromList [5, 3])) == False
    -- > valid (insertSetMin 5 (Data.IntSet.fromList [5, 3])) == False
    insertSetMax :: Key -> IntSet -> NEIntSet
    insertSetMax :: Key -> IntSet -> NEIntSet
    insertSetMax Key
    x = NEIntSet -> (NEIntSet -> NEIntSet) -> IntSet -> NEIntSet
    forall r. r -> (NEIntSet -> r) -> IntSet -> r
    withNonEmpty (Key -> NEIntSet
    singleton Key
    x) NEIntSet -> NEIntSet
    go
      where
        go :: NEIntSet -> NEIntSet
    go (NEIntSet Key
    x0 IntSet
    s0) = Key -> IntSet -> NEIntSet
    NEIntSet Key
    x0 (IntSet -> NEIntSet) -> (IntSet -> IntSet) -> IntSet -> NEIntSet
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Key -> IntSet -> IntSet
    insertMaxSet Key
    x (IntSet -> NEIntSet) -> IntSet -> NEIntSet
    forall a b. (a -> b) -> a -> b
    $ IntSet
    s0
    {-# INLINE insertSetMax #-}

    -- | /O(log n)/. Unsafe version of 'nonEmptySet'.  Coerces a 'IntSet'
    -- into an 'NEIntSet', but is undefined (throws a runtime exception when
    -- evaluation is attempted) for an empty 'IntSet'.
    unsafeFromSet ::
      IntSet ->
      NEIntSet
    unsafeFromSet :: IntSet -> NEIntSet
    unsafeFromSet = NEIntSet -> (NEIntSet -> NEIntSet) -> IntSet -> NEIntSet
    forall r. r -> (NEIntSet -> r) -> IntSet -> r
    withNonEmpty NEIntSet
    forall {a}. a
    e NEIntSet -> NEIntSet
    forall a. a -> a
    id
      where
        e :: a
    e = [Char] -> a
    forall a. [Char] -> a
    errorWithoutStackTrace [Char]
    "NEIntSet.unsafeFromSet: empty set"
    {-# INLINE unsafeFromSet #-}

    -- | /O(n)/. Build a set from an ascending list in linear time.  /The
    -- precondition (input list is ascending) is not checked./
    fromAscList :: NonEmpty Key -> NEIntSet
    fromAscList :: NonEmpty Key -> NEIntSet
    fromAscList = NonEmpty Key -> NEIntSet
    fromDistinctAscList (NonEmpty Key -> NEIntSet)
    -> (NonEmpty Key -> NonEmpty Key) -> NonEmpty Key -> NEIntSet
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NonEmpty Key -> NonEmpty Key
    combineEq
    {-# INLINE fromAscList #-}

    -- | /O(n)/. Build a set from an ascending list of distinct elements in linear time.
    -- /The precondition (input list is strictly ascending) is not checked./
    fromDistinctAscList :: NonEmpty Key -> NEIntSet
    fromDistinctAscList :: NonEmpty Key -> NEIntSet
    fromDistinctAscList (Key
    x :| [Key]
    xs) =
      Key -> IntSet -> NEIntSet
    insertSetMin Key
    x
        (IntSet -> NEIntSet) -> ([Key] -> IntSet) -> [Key] -> NEIntSet
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . [Key] -> IntSet
    S.fromDistinctAscList
        ([Key] -> NEIntSet) -> [Key] -> NEIntSet
    forall a b. (a -> b) -> a -> b
    $ [Key]
    xs
    {-# INLINE fromDistinctAscList #-}

    -- | /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.
    insert :: Key -> NEIntSet -> NEIntSet
    insert :: Key -> NEIntSet -> NEIntSet
    insert Key
    x n :: NEIntSet
    n@(NEIntSet Key
    x0 IntSet
    s) = case Key -> Key -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare Key
    x Key
    x0 of
      Ordering
    LT -> Key -> IntSet -> NEIntSet
    NEIntSet Key
    x (IntSet -> NEIntSet) -> IntSet -> NEIntSet
    forall a b. (a -> b) -> a -> b
    $ NEIntSet -> IntSet
    toSet NEIntSet
    n
      Ordering
    EQ -> Key -> IntSet -> NEIntSet
    NEIntSet Key
    x IntSet
    s
      Ordering
    GT -> Key -> IntSet -> NEIntSet
    NEIntSet Key
    x0 (IntSet -> NEIntSet) -> IntSet -> NEIntSet
    forall a b. (a -> b) -> a -> b
    $ Key -> IntSet -> IntSet
    S.insert Key
    x IntSet
    s
    {-# INLINE insert #-}

    -- | /O(log n)/. Delete an element from a set.
    delete :: Key -> NEIntSet -> IntSet
    delete :: Key -> NEIntSet -> IntSet
    delete Key
    x n :: NEIntSet
    n@(NEIntSet Key
    x0 IntSet
    s) = case Key -> Key -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare Key
    x Key
    x0 of
      Ordering
    LT -> NEIntSet -> IntSet
    toSet NEIntSet
    n
      Ordering
    EQ -> IntSet
    s
      Ordering
    GT -> Key -> IntSet -> IntSet
    insertMinSet Key
    x0 (IntSet -> IntSet) -> (IntSet -> IntSet) -> IntSet -> IntSet
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Key -> IntSet -> IntSet
    S.delete Key
    x (IntSet -> IntSet) -> IntSet -> IntSet
    forall a b. (a -> b) -> a -> b
    $ IntSet
    s
    {-# INLINE delete #-}

    -- | /O(log n)/. Is the element in the set?
    member :: Key -> NEIntSet -> Bool
    member :: Key -> NEIntSet -> Bool
    member Key
    x (NEIntSet Key
    x0 IntSet
    s) = case Key -> Key -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare Key
    x Key
    x0 of
      Ordering
    LT -> Bool
    False
      Ordering
    EQ -> Bool
    True
      Ordering
    GT -> Key -> IntSet -> Bool
    S.member Key
    x IntSet
    s
    {-# INLINE member #-}

    -- | /O(log n)/. Is the element not in the set?
    notMember :: Key -> NEIntSet -> Bool
    notMember :: Key -> NEIntSet -> Bool
    notMember Key
    x (NEIntSet Key
    x0 IntSet
    s) = case Key -> Key -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare Key
    x Key
    x0 of
      Ordering
    LT -> Bool
    True
      Ordering
    EQ -> Bool
    False
      Ordering
    GT -> Key -> IntSet -> Bool
    S.notMember Key
    x IntSet
    s
    {-# INLINE notMember #-}

    -- | /O(log n)/. Find largest element smaller than the given one.
    --
    -- > lookupLT 3 (fromList (3 :| [5])) == Nothing
    -- > lookupLT 5 (fromList (3 :| [5])) == Just 3
    lookupLT :: Key -> NEIntSet -> Maybe Key
    lookupLT :: Key -> NEIntSet -> Maybe Key
    lookupLT Key
    x (NEIntSet Key
    x0 IntSet
    s) = case Key -> Key -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare Key
    x Key
    x0 of
      Ordering
    LT -> Maybe Key
    forall a. Maybe a
    Nothing
      Ordering
    EQ -> Maybe Key
    forall a. Maybe a
    Nothing
      Ordering
    GT -> Key -> IntSet -> Maybe Key
    S.lookupLT Key
    x IntSet
    s Maybe Key -> Maybe Key -> Maybe Key
    forall a. Maybe a -> Maybe a -> Maybe a
    forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
    <|> Key -> Maybe Key
    forall a. a -> Maybe a
    Just Key
    x0
    {-# INLINE lookupLT #-}

    -- | /O(log n)/. Find smallest element greater than the given one.
    --
    -- > lookupLT 4 (fromList (3 :| [5])) == Just 5
    -- > lookupLT 5 (fromList (3 :| [5])) == Nothing
    lookupGT :: Key -> NEIntSet -> Maybe Key
    lookupGT :: Key -> NEIntSet -> Maybe Key
    lookupGT Key
    x (NEIntSet Key
    x0 IntSet
    s) = case Key -> Key -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare Key
    x Key
    x0 of
      Ordering
    LT -> Key -> Maybe Key
    forall a. a -> Maybe a
    Just Key
    x0
      Ordering
    EQ -> (Key, IntSet) -> Key
    forall a b. (a, b) -> a
    fst ((Key, IntSet) -> Key) -> Maybe (Key, IntSet) -> Maybe Key
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> IntSet -> Maybe (Key, IntSet)
    S.minView IntSet
    s
      Ordering
    GT -> Key -> IntSet -> Maybe Key
    S.lookupGT Key
    x IntSet
    s
    {-# INLINE lookupGT #-}

    -- | /O(log n)/. Find largest element smaller or equal to the given one.
    --
    -- > lookupLT 2 (fromList (3 :| [5])) == Nothing
    -- > lookupLT 4 (fromList (3 :| [5])) == Just 3
    -- > lookupLT 5 (fromList (3 :| [5])) == Just 5
    lookupLE :: Key -> NEIntSet -> Maybe Key
    lookupLE :: Key -> NEIntSet -> Maybe Key
    lookupLE Key
    x (NEIntSet Key
    x0 IntSet
    s) = case Key -> Key -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare Key
    x Key
    x0 of
      Ordering
    LT -> Maybe Key
    forall a. Maybe a
    Nothing
      Ordering
    EQ -> Key -> Maybe Key
    forall a. a -> Maybe a
    Just Key
    x0
      Ordering
    GT -> Key -> IntSet -> Maybe Key
    S.lookupLE Key
    x IntSet
    s Maybe Key -> Maybe Key -> Maybe Key
    forall a. Maybe a -> Maybe a -> Maybe a
    forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
    <|> Key -> Maybe Key
    forall a. a -> Maybe a
    Just Key
    x0
    {-# INLINE lookupLE #-}

    -- | /O(log n)/. Find smallest element greater or equal to the given one.
    --
    -- > lookupLT 3 (fromList (3 :| [5])) == Just 3
    -- > lookupLT 4 (fromList (3 :| [5])) == Just 5
    -- > lookupLT 6 (fromList (3 :| [5])) == Nothing
    lookupGE :: Key -> NEIntSet -> Maybe Key
    lookupGE :: Key -> NEIntSet -> Maybe Key
    lookupGE Key
    x (NEIntSet Key
    x0 IntSet
    s) = case Key -> Key -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare Key
    x Key
    x0 of
      Ordering
    LT -> Key -> Maybe Key
    forall a. a -> Maybe a
    Just Key
    x0
      Ordering
    EQ -> Key -> Maybe Key
    forall a. a -> Maybe a
    Just Key
    x0
      Ordering
    GT -> Key -> IntSet -> Maybe Key
    S.lookupGE Key
    x IntSet
    s
    {-# INLINE lookupGE #-}

    -- | /O(n)/. Fold the elements in the set using the given right-associative
    -- binary operator, such that @'foldr' f z == 'Prelude.foldr' f z . 'Data.IntSet.NonEmpty.toAscList'@.
    --
    -- For example,
    --
    -- > elemsList set = foldr (:) [] set
    foldr :: (Key -> b -> b) -> b -> NEIntSet -> b
    foldr :: forall b. (Key -> b -> b) -> b -> NEIntSet -> b
    foldr Key -> b -> b
    f b
    z (NEIntSet Key
    x IntSet
    s) = Key
    x Key -> b -> b
    `f` (Key -> b -> b) -> b -> IntSet -> b
    forall b. (Key -> b -> b) -> b -> IntSet -> b
    S.foldr Key -> b -> b
    f b
    z IntSet
    s
    {-# INLINE foldr #-}

    -- | /O(n)/. A strict version of 'foldr'. Each application of the operator is
    -- evaluated before using the result in the next application. This
    -- function is strict in the starting value.
    foldr' :: (Key -> b -> b) -> b -> NEIntSet -> b
    foldr' :: forall b. (Key -> b -> b) -> b -> NEIntSet -> b
    foldr' Key -> b -> b
    f b
    z (NEIntSet Key
    x IntSet
    s) = Key
    x Key -> b -> b
    `f` b
    y
      where
        !y :: b
    y = (Key -> b -> b) -> b -> IntSet -> b
    forall b. (Key -> b -> b) -> b -> IntSet -> b
    S.foldr' Key -> b -> b
    f b
    z IntSet
    s
    {-# INLINE foldr' #-}

    -- | /O(n)/. A version of 'foldr' that uses the value at the maximal value
    -- in the set as the starting value.
    --
    -- Note that, unlike 'Data.Foldable.foldr1' for 'IntSet', this function is
    -- total if the input function is total.
    foldr1 :: (Key -> Key -> Key) -> NEIntSet -> Key
    foldr1 :: (Key -> Key -> Key) -> NEIntSet -> Key
    foldr1 Key -> Key -> Key
    f (NEIntSet Key
    x IntSet
    s) =
      Key -> ((Key, IntSet) -> Key) -> Maybe (Key, IntSet) -> Key
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe Key
    x (Key -> Key -> Key
    f Key
    x (Key -> Key) -> ((Key, IntSet) -> Key) -> (Key, IntSet) -> Key
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Key -> IntSet -> Key) -> (Key, IntSet) -> Key
    forall a b c. (a -> b -> c) -> (a, b) -> c
    uncurry ((Key -> Key -> Key) -> Key -> IntSet -> Key
    forall b. (Key -> b -> b) -> b -> IntSet -> b
    S.foldr Key -> Key -> Key
    f))
        (Maybe (Key, IntSet) -> Key)
    -> (IntSet -> Maybe (Key, IntSet)) -> IntSet -> Key
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . IntSet -> Maybe (Key, IntSet)
    S.maxView
        (IntSet -> Key) -> IntSet -> Key
    forall a b. (a -> b) -> a -> b
    $ IntSet
    s
    {-# INLINE foldr1 #-}

    -- | /O(n)/. Fold the elements in the set using the given left-associative
    -- binary operator, such that @'foldl' f z == 'Prelude.foldl' f z . 'Data.IntSet.NonEmpty.toAscList'@.
    --
    -- For example,
    --
    -- > descElemsList set = foldl (flip (:)) [] set
    foldl :: (a -> Key -> a) -> a -> NEIntSet -> a
    foldl :: forall a. (a -> Key -> a) -> a -> NEIntSet -> a
    foldl a -> Key -> a
    f a
    z (NEIntSet Key
    x IntSet
    s) = (a -> Key -> a) -> a -> IntSet -> a
    forall a. (a -> Key -> a) -> a -> IntSet -> a
    S.foldl a -> Key -> a
    f (a -> Key -> a
    f a
    z Key
    x) IntSet
    s
    {-# INLINE foldl #-}

    -- | /O(n)/. A strict version of 'foldl'. Each application of the operator is
    -- evaluated before using the result in the next application. This
    -- function is strict in the starting value.
    foldl' :: (a -> Key -> a) -> a -> NEIntSet -> a
    foldl' :: forall a. (a -> Key -> a) -> a -> NEIntSet -> a
    foldl' a -> Key -> a
    f a
    z (NEIntSet Key
    x IntSet
    s) = (a -> Key -> a) -> a -> IntSet -> a
    forall a. (a -> Key -> a) -> a -> IntSet -> a
    S.foldl' a -> Key -> a
    f a
    y IntSet
    s
      where
        !y :: a
    y = a -> Key -> a
    f a
    z Key
    x
    {-# INLINE foldl' #-}

    -- | /O(n)/. A version of 'foldl' that uses the value at the minimal value
    -- in the set as the starting value.
    --
    -- Note that, unlike 'Data.Foldable.foldl1' for 'IntSet', this function is
    -- total if the input function is total.
    foldl1 :: (Key -> Key -> Key) -> NEIntSet -> Key
    foldl1 :: (Key -> Key -> Key) -> NEIntSet -> Key
    foldl1 Key -> Key -> Key
    f (NEIntSet Key
    x IntSet
    s) = (Key -> Key -> Key) -> Key -> IntSet -> Key
    forall a. (a -> Key -> a) -> a -> IntSet -> a
    S.foldl Key -> Key -> Key
    f Key
    x IntSet
    s
    {-# INLINE foldl1 #-}

    -- | /O(n)/. A strict version of 'foldr1'. Each application of the operator
    -- is evaluated before using the result in the next application. This
    -- function is strict in the starting value.
    foldr1' :: (Key -> Key -> Key) -> NEIntSet -> Key
    foldr1' :: (Key -> Key -> Key) -> NEIntSet -> Key
    foldr1' Key -> Key -> Key
    f (NEIntSet Key
    x IntSet
    s) = case IntSet -> Maybe (Key, IntSet)
    S.maxView IntSet
    s of
      Maybe (Key, IntSet)
    Nothing -> Key
    x
      Just (Key
    y, IntSet
    s') -> let !z :: Key
    z = (Key -> Key -> Key) -> Key -> IntSet -> Key
    forall b. (Key -> b -> b) -> b -> IntSet -> b
    S.foldr' Key -> Key -> Key
    f Key
    y IntSet
    s' in Key
    x Key -> Key -> Key
    `f` Key
    z
    {-# INLINE foldr1' #-}

    -- | /O(n)/. A strict version of 'foldl1'. Each application of the operator
    -- is evaluated before using the result in the next application. This
    -- function is strict in the starting value.
    foldl1' :: (Key -> Key -> Key) -> NEIntSet -> Key
    foldl1' :: (Key -> Key -> Key) -> NEIntSet -> Key
    foldl1' Key -> Key -> Key
    f (NEIntSet Key
    x IntSet
    s) = (Key -> Key -> Key) -> Key -> IntSet -> Key
    forall a. (a -> Key -> a) -> a -> IntSet -> a
    S.foldl' Key -> Key -> Key
    f Key
    x IntSet
    s
    {-# INLINE foldl1' #-}

    -- | /O(1)/. The number of elements in the set.  Guaranteed to be greater
    -- than zero.
    size :: NEIntSet -> Int
    size :: NEIntSet -> Key
    size (NEIntSet Key
    _ IntSet
    s) = Key
    1 Key -> Key -> Key
    forall a. Num a => a -> a -> a
    + IntSet -> Key
    S.size IntSet
    s
    {-# INLINE size #-}

    -- | /O(n+m)/. Is this a subset?
    -- @(s1 \`isSubsetOf\` s2)@ tells whether @s1@ is a subset of @s2@.
    isSubsetOf ::
      NEIntSet ->
      NEIntSet ->
      Bool
    isSubsetOf :: NEIntSet -> NEIntSet -> Bool
    isSubsetOf (NEIntSet Key
    x IntSet
    s0) (NEIntSet -> IntSet
    toSet -> IntSet
    s1) =
      Key
    x Key -> IntSet -> Bool
    `S.member` IntSet
    s1
        Bool -> Bool -> Bool
    && IntSet
    s0 IntSet -> IntSet -> Bool
    `S.isSubsetOf` IntSet
    s1
    {-# INLINE isSubsetOf #-}

    -- | /O(n+m)/. Is this a proper subset? (ie. a subset but not equal).
    isProperSubsetOf ::
      NEIntSet ->
      NEIntSet ->
      Bool
    isProperSubsetOf :: NEIntSet -> NEIntSet -> Bool
    isProperSubsetOf NEIntSet
    s0 NEIntSet
    s1 =
      IntSet -> Key
    S.size (NEIntSet -> IntSet
    neisIntSet NEIntSet
    s0) Key -> Key -> Bool
    forall a. Ord a => a -> a -> Bool
    < IntSet -> Key
    S.size (NEIntSet -> IntSet
    neisIntSet NEIntSet
    s1)
        Bool -> Bool -> Bool
    && NEIntSet
    s0 NEIntSet -> NEIntSet -> Bool
    `isSubsetOf` NEIntSet
    s1
    {-# INLINE isProperSubsetOf #-}

    -- | /O(n+m)/. Check whether two sets are disjoint (i.e. their intersection
    --   is empty).
    --
    -- > disjoint (fromList (2:|[4,6]))   (fromList (1:|[3]))     == True
    -- > disjoint (fromList (2:|[4,6,8])) (fromList (2:|[3,5,7])) == False
    -- > disjoint (fromList (1:|[2]))     (fromList (1:|[2,3,4])) == False
    disjoint ::
      NEIntSet ->
      NEIntSet ->
      Bool
    disjoint :: NEIntSet -> NEIntSet -> Bool
    disjoint n1 :: NEIntSet
    n1@(NEIntSet Key
    x1 IntSet
    s1) n2 :: NEIntSet
    n2@(NEIntSet Key
    x2 IntSet
    s2) = case Key -> Key -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare Key
    x1 Key
    x2 of
      -- x1 is not in n2
      Ordering
    LT -> IntSet
    s1 IntSet -> IntSet -> Bool
    `S.disjoint` NEIntSet -> IntSet
    toSet NEIntSet
    n2
      -- k1 and k2 are a part of the result
      Ordering
    EQ -> Bool
    False
      -- k2 is not in n1
      Ordering
    GT -> NEIntSet -> IntSet
    toSet NEIntSet
    n1 IntSet -> IntSet -> Bool
    `S.disjoint` IntSet
    s2
    {-# INLINE disjoint #-}

    -- | /O(m*log(n\/m + 1)), m <= n/. Difference of two sets.
    --
    -- Returns a potentially empty set ('IntSet') because the first set might be
    -- a subset of the second set, and therefore have all of its elements
    -- removed.
    difference ::
      NEIntSet ->
      NEIntSet ->
      IntSet
    difference :: NEIntSet -> NEIntSet -> IntSet
    difference n1 :: NEIntSet
    n1@(NEIntSet Key
    x1 IntSet
    s1) n2 :: NEIntSet
    n2@(NEIntSet Key
    x2 IntSet
    s2) = case Key -> Key -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare Key
    x1 Key
    x2 of
      -- x1 is not in n2, so cannot be deleted
      Ordering
    LT -> Key -> IntSet -> IntSet
    insertMinSet Key
    x1 (IntSet -> IntSet) -> IntSet -> IntSet
    forall a b. (a -> b) -> a -> b
    $ IntSet
    s1 IntSet -> IntSet -> IntSet
    `S.difference` NEIntSet -> IntSet
    toSet NEIntSet
    n2
      -- x2 deletes x1, and only x1
      Ordering
    EQ -> IntSet
    s1 IntSet -> IntSet -> IntSet
    `S.difference` IntSet
    s2
      -- x2 is not in n1, so cannot delete anything, so we can just difference n1 // s2.
      Ordering
    GT -> NEIntSet -> IntSet
    toSet NEIntSet
    n1 IntSet -> IntSet -> IntSet
    `S.difference` IntSet
    s2
    {-# INLINE difference #-}

    -- | Same as 'difference'.
    (\\) ::
      NEIntSet ->
      NEIntSet ->
      IntSet
    \\ :: NEIntSet -> NEIntSet -> IntSet
    (\\) = NEIntSet -> NEIntSet -> IntSet
    difference
    {-# INLINE (\\) #-}

    -- | /O(m*log(n\/m + 1)), m <= n/. The intersection of two sets.
    --
    -- Returns a potentially empty set ('IntSet'), because the two sets might have
    -- an empty intersection.
    --
    -- Elements of the result come from the first set, so for example
    --
    -- > import qualified Data.IntSet.NonEmpty as NES
    -- > data AB = A | B deriving Show
    -- > instance Ord AB where compare _ _ = EQ
    -- > instance Eq AB where _ == _ = True
    -- > main = print (NES.singleton A `NES.intersection` NES.singleton B,
    -- >               NES.singleton B `NES.intersection` NES.singleton A)
    --
    -- prints @(fromList (A:|[]),fromList (B:|[]))@.
    intersection ::
      NEIntSet ->
      NEIntSet ->
      IntSet
    intersection :: NEIntSet -> NEIntSet -> IntSet
    intersection n1 :: NEIntSet
    n1@(NEIntSet Key
    x1 IntSet
    s1) n2 :: NEIntSet
    n2@(NEIntSet Key
    x2 IntSet
    s2) = case Key -> Key -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare Key
    x1 Key
    x2 of
      -- x1 is not in n2
      Ordering
    LT -> IntSet
    s1 IntSet -> IntSet -> IntSet
    `S.intersection` NEIntSet -> IntSet
    toSet NEIntSet
    n2
      -- x1 and x2 are a part of the result
      Ordering
    EQ -> Key -> IntSet -> IntSet
    insertMinSet Key
    x1 (IntSet -> IntSet) -> IntSet -> IntSet
    forall a b. (a -> b) -> a -> b
    $ IntSet
    s1 IntSet -> IntSet -> IntSet
    `S.intersection` IntSet
    s2
      -- x2 is not in n1
      Ordering
    GT -> NEIntSet -> IntSet
    toSet NEIntSet
    n1 IntSet -> IntSet -> IntSet
    `S.intersection` IntSet
    s2
    {-# INLINE intersection #-}

    -- | /O(n)/. Filter all elements that satisfy the predicate.
    --
    -- Returns a potentially empty set ('IntSet') because the predicate might
    -- filter out all items in the original non-empty set.
    filter ::
      (Key -> Bool) ->
      NEIntSet ->
      IntSet
    filter :: (Key -> Bool) -> NEIntSet -> IntSet
    filter Key -> Bool
    f (NEIntSet Key
    x IntSet
    s1)
      | Key -> Bool
    f Key
    x = Key -> IntSet -> IntSet
    insertMinSet Key
    x (IntSet -> IntSet) -> (IntSet -> IntSet) -> IntSet -> IntSet
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Key -> Bool) -> IntSet -> IntSet
    S.filter Key -> Bool
    f (IntSet -> IntSet) -> IntSet -> IntSet
    forall a b. (a -> b) -> a -> b
    $ IntSet
    s1
      | Bool
    otherwise = (Key -> Bool) -> IntSet -> IntSet
    S.filter Key -> Bool
    f IntSet
    s1
    {-# INLINE filter #-}

    -- | /O(n)/. Partition the map according to a predicate.
    --
    -- Returns a 'These' with potentially two non-empty sets:
    --
    -- *   @'This' n1@ means that the predicate was true for all items.
    -- *   @'That' n2@ means that the predicate was false for all items.
    -- *   @'These' n1 n2@ gives @n1@ (all of the items that were true for the
    --     predicate) and @n2@ (all of the items that were false for the
    --     predicate).
    --
    -- See also 'split'.
    --
    -- > partition (> 3) (fromList (5 :| [3])) == These (singleton 5) (singleton 3)
    -- > partition (< 7) (fromList (5 :| [3])) == This  (fromList (3 :| [5]))
    -- > partition (> 7) (fromList (5 :| [3])) == That  (fromList (3 :| [5]))
    partition ::
      (Key -> Bool) ->
      NEIntSet ->
      These NEIntSet NEIntSet
    partition :: (Key -> Bool) -> NEIntSet -> These NEIntSet NEIntSet
    partition Key -> Bool
    f n :: NEIntSet
    n@(NEIntSet Key
    x IntSet
    s0) = case (IntSet -> Maybe NEIntSet
    nonEmptySet IntSet
    s1, IntSet -> Maybe NEIntSet
    nonEmptySet IntSet
    s2) of
      (Maybe NEIntSet
    Nothing, Maybe NEIntSet
    Nothing)
        | Key -> Bool
    f Key
    x -> NEIntSet -> These NEIntSet NEIntSet
    forall a b. a -> These a b
    This NEIntSet
    n
        | Bool
    otherwise -> NEIntSet -> These NEIntSet NEIntSet
    forall a b. b -> These a b
    That NEIntSet
    n
      (Just NEIntSet
    n1, Maybe NEIntSet
    Nothing)
        | Key -> Bool
    f Key
    x -> NEIntSet -> These NEIntSet NEIntSet
    forall a b. a -> These a b
    This NEIntSet
    n
        | Bool
    otherwise -> NEIntSet -> NEIntSet -> These NEIntSet NEIntSet
    forall a b. a -> b -> These a b
    These NEIntSet
    n1 (Key -> NEIntSet
    singleton Key
    x)
      (Maybe NEIntSet
    Nothing, Just NEIntSet
    n2)
        | Key -> Bool
    f Key
    x -> NEIntSet -> NEIntSet -> These NEIntSet NEIntSet
    forall a b. a -> b -> These a b
    These (Key -> NEIntSet
    singleton Key
    x) NEIntSet
    n2
        | Bool
    otherwise -> NEIntSet -> These NEIntSet NEIntSet
    forall a b. b -> These a b
    That NEIntSet
    n
      (Just NEIntSet
    n1, Just NEIntSet
    n2)
        | Key -> Bool
    f Key
    x -> NEIntSet -> NEIntSet -> These NEIntSet NEIntSet
    forall a b. a -> b -> These a b
    These (Key -> IntSet -> NEIntSet
    insertSetMin Key
    x IntSet
    s1) NEIntSet
    n2
        | Bool
    otherwise -> NEIntSet -> NEIntSet -> These NEIntSet NEIntSet
    forall a b. a -> b -> These a b
    These NEIntSet
    n1 (Key -> IntSet -> NEIntSet
    insertSetMin Key
    x IntSet
    s2)
      where
        (IntSet
    s1, IntSet
    s2) = (Key -> Bool) -> IntSet -> (IntSet, IntSet)
    S.partition Key -> Bool
    f IntSet
    s0
    {-# INLINEABLE partition #-}

    -- | /O(log n)/. The expression (@'split' x set@) is potentially a 'These'
    -- containing up to two 'NEIntSet's based on splitting the set into sets
    -- containing items before and after the value @x@.  It will never return
    -- a set that contains @x@ itself.
    --
    -- *   'Nothing' means that @x@ was the only value in the the original set,
    --     and so there are no items before or after it.
    -- *   @'Just' ('This' n1)@ means @x@ was larger than or equal to all items
    --     in the set, and @n1@ is the entire original set (minus @x@, if it
    --     was present)
    -- *   @'Just' ('That' n2)@ means @x@ was smaller than or equal to all
    --     items in the set, and @n2@ is the entire original set (minus @x@, if
    --     it was present)
    -- *   @'Just' ('These' n1 n2)@ gives @n1@ (the set of all values from the
    --     original set less than @x@) and @n2@ (the set of all values from the
    --     original set greater than @x@).
    --
    -- > split 2 (fromList (5 :| [3])) == Just (That  (fromList (3 :| [5]))      )
    -- > split 3 (fromList (5 :| [3])) == Just (That  (singleton 5)              )
    -- > split 4 (fromList (5 :| [3])) == Just (These (singleton 3) (singleton 5))
    -- > split 5 (fromList (5 :| [3])) == Just (This  (singleton 3)              )
    -- > split 6 (fromList (5 :| [3])) == Just (This  (fromList (3 :| [5]))      )
    -- > split 5 (singleton 5)         == Nothing
    split ::
      Key ->
      NEIntSet ->
      Maybe (These NEIntSet NEIntSet)
    split :: Key -> NEIntSet -> Maybe (These NEIntSet NEIntSet)
    split Key
    x n :: NEIntSet
    n@(NEIntSet Key
    x0 IntSet
    s0) = case Key -> Key -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare Key
    x Key
    x0 of
      Ordering
    LT -> These NEIntSet NEIntSet -> Maybe (These NEIntSet NEIntSet)
    forall a. a -> Maybe a
    Just (These NEIntSet NEIntSet -> Maybe (These NEIntSet NEIntSet))
    -> These NEIntSet NEIntSet -> Maybe (These NEIntSet NEIntSet)
    forall a b. (a -> b) -> a -> b
    $ NEIntSet -> These NEIntSet NEIntSet
    forall a b. b -> These a b
    That NEIntSet
    n
      Ordering
    EQ -> NEIntSet -> These NEIntSet NEIntSet
    forall a b. b -> These a b
    That (NEIntSet -> These NEIntSet NEIntSet)
    -> Maybe NEIntSet -> Maybe (These NEIntSet NEIntSet)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> IntSet -> Maybe NEIntSet
    nonEmptySet IntSet
    s0
      Ordering
    GT -> case (IntSet -> Maybe NEIntSet
    nonEmptySet IntSet
    s1, IntSet -> Maybe NEIntSet
    nonEmptySet IntSet
    s2) of
        (Maybe NEIntSet
    Nothing, Maybe NEIntSet
    Nothing) -> These NEIntSet NEIntSet -> Maybe (These NEIntSet NEIntSet)
    forall a. a -> Maybe a
    Just (These NEIntSet NEIntSet -> Maybe (These NEIntSet NEIntSet))
    -> These NEIntSet NEIntSet -> Maybe (These NEIntSet NEIntSet)
    forall a b. (a -> b) -> a -> b
    $ NEIntSet -> These NEIntSet NEIntSet
    forall a b. a -> These a b
    This (Key -> NEIntSet
    singleton Key
    x0)
        (Just NEIntSet
    _, Maybe NEIntSet
    Nothing) -> These NEIntSet NEIntSet -> Maybe (These NEIntSet NEIntSet)
    forall a. a -> Maybe a
    Just (These NEIntSet NEIntSet -> Maybe (These NEIntSet NEIntSet))
    -> These NEIntSet NEIntSet -> Maybe (These NEIntSet NEIntSet)
    forall a b. (a -> b) -> a -> b
    $ NEIntSet -> These NEIntSet NEIntSet
    forall a b. a -> These a b
    This (Key -> IntSet -> NEIntSet
    insertSetMin Key
    x0 IntSet
    s1)
        (Maybe NEIntSet
    Nothing, Just NEIntSet
    n2) -> These NEIntSet NEIntSet -> Maybe (These NEIntSet NEIntSet)
    forall a. a -> Maybe a
    Just (These NEIntSet NEIntSet -> Maybe (These NEIntSet NEIntSet))
    -> These NEIntSet NEIntSet -> Maybe (These NEIntSet NEIntSet)
    forall a b. (a -> b) -> a -> b
    $ NEIntSet -> NEIntSet -> These NEIntSet NEIntSet
    forall a b. a -> b -> These a b
    These (Key -> NEIntSet
    singleton Key
    x0) NEIntSet
    n2
        (Just NEIntSet
    _, Just NEIntSet
    n2) -> These NEIntSet NEIntSet -> Maybe (These NEIntSet NEIntSet)
    forall a. a -> Maybe a
    Just (These NEIntSet NEIntSet -> Maybe (These NEIntSet NEIntSet))
    -> These NEIntSet NEIntSet -> Maybe (These NEIntSet NEIntSet)
    forall a b. (a -> b) -> a -> b
    $ NEIntSet -> NEIntSet -> These NEIntSet NEIntSet
    forall a b. a -> b -> These a b
    These (Key -> IntSet -> NEIntSet
    insertSetMin Key
    x0 IntSet
    s1) NEIntSet
    n2
      where
        (IntSet
    s1, IntSet
    s2) = Key -> IntSet -> (IntSet, IntSet)
    S.split Key
    x IntSet
    s0
    {-# INLINEABLE split #-}

    -- | /O(log n)/. The expression (@'splitMember' x set@) splits a set just
    -- like 'split' but also returns @'member' x set@ (whether or not @x@ was
    -- in @set@)
    --
    -- > splitMember 2 (fromList (5 :| [3])) == (False, Just (That  (fromList (3 :| [5)]))))
    -- > splitMember 3 (fromList (5 :| [3])) == (True , Just (That  (singleton 5)))
    -- > splitMember 4 (fromList (5 :| [3])) == (False, Just (These (singleton 3) (singleton 5)))
    -- > splitMember 5 (fromList (5 :| [3])) == (True , Just (This  (singleton 3))
    -- > splitMember 6 (fromList (5 :| [3])) == (False, Just (This  (fromList (3 :| [5])))
    -- > splitMember 5 (singleton 5)         == (True , Nothing)
    splitMember ::
      Key ->
      NEIntSet ->
      (Bool, Maybe (These NEIntSet NEIntSet))
    splitMember :: Key -> NEIntSet -> (Bool, Maybe (These NEIntSet NEIntSet))
    splitMember Key
    x n :: NEIntSet
    n@(NEIntSet Key
    x0 IntSet
    s0) = case Key -> Key -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare Key
    x Key
    x0 of
      Ordering
    LT -> (Bool
    False, These NEIntSet NEIntSet -> Maybe (These NEIntSet NEIntSet)
    forall a. a -> Maybe a
    Just (These NEIntSet NEIntSet -> Maybe (These NEIntSet NEIntSet))
    -> These NEIntSet NEIntSet -> Maybe (These NEIntSet NEIntSet)
    forall a b. (a -> b) -> a -> b
    $ NEIntSet -> These NEIntSet NEIntSet
    forall a b. b -> These a b
    That NEIntSet
    n)
      Ordering
    EQ -> (Bool
    True, NEIntSet -> These NEIntSet NEIntSet
    forall a b. b -> These a b
    That (NEIntSet -> These NEIntSet NEIntSet)
    -> Maybe NEIntSet -> Maybe (These NEIntSet NEIntSet)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> IntSet -> Maybe NEIntSet
    nonEmptySet IntSet
    s0)
      Ordering
    GT -> (Bool
    mem,) (Maybe (These NEIntSet NEIntSet)
     -> (Bool, Maybe (These NEIntSet NEIntSet)))
    -> Maybe (These NEIntSet NEIntSet)
    -> (Bool, Maybe (These NEIntSet NEIntSet))
    forall a b. (a -> b) -> a -> b
    $ case (IntSet -> Maybe NEIntSet
    nonEmptySet IntSet
    s1, IntSet -> Maybe NEIntSet
    nonEmptySet IntSet
    s2) of
        (Maybe NEIntSet
    Nothing, Maybe NEIntSet
    Nothing) -> These NEIntSet NEIntSet -> Maybe (These NEIntSet NEIntSet)
    forall a. a -> Maybe a
    Just (These NEIntSet NEIntSet -> Maybe (These NEIntSet NEIntSet))
    -> These NEIntSet NEIntSet -> Maybe (These NEIntSet NEIntSet)
    forall a b. (a -> b) -> a -> b
    $ NEIntSet -> These NEIntSet NEIntSet
    forall a b. a -> These a b
    This (Key -> NEIntSet
    singleton Key
    x0)
        (Just NEIntSet
    _, Maybe NEIntSet
    Nothing) -> These NEIntSet NEIntSet -> Maybe (These NEIntSet NEIntSet)
    forall a. a -> Maybe a
    Just (These NEIntSet NEIntSet -> Maybe (These NEIntSet NEIntSet))
    -> These NEIntSet NEIntSet -> Maybe (These NEIntSet NEIntSet)
    forall a b. (a -> b) -> a -> b
    $ NEIntSet -> These NEIntSet NEIntSet
    forall a b. a -> These a b
    This (Key -> IntSet -> NEIntSet
    insertSetMin Key
    x0 IntSet
    s1)
        (Maybe NEIntSet
    Nothing, Just NEIntSet
    n2) -> These NEIntSet NEIntSet -> Maybe (These NEIntSet NEIntSet)
    forall a. a -> Maybe a
    Just (These NEIntSet NEIntSet -> Maybe (These NEIntSet NEIntSet))
    -> These NEIntSet NEIntSet -> Maybe (These NEIntSet NEIntSet)
    forall a b. (a -> b) -> a -> b
    $ NEIntSet -> NEIntSet -> These NEIntSet NEIntSet
    forall a b. a -> b -> These a b
    These (Key -> NEIntSet
    singleton Key
    x0) NEIntSet
    n2
        (Just NEIntSet
    _, Just NEIntSet
    n2) -> These NEIntSet NEIntSet -> Maybe (These NEIntSet NEIntSet)
    forall a. a -> Maybe a
    Just (These NEIntSet NEIntSet -> Maybe (These NEIntSet NEIntSet))
    -> These NEIntSet NEIntSet -> Maybe (These NEIntSet NEIntSet)
    forall a b. (a -> b) -> a -> b
    $ NEIntSet -> NEIntSet -> These NEIntSet NEIntSet
    forall a b. a -> b -> These a b
    These (Key -> IntSet -> NEIntSet
    insertSetMin Key
    x0 IntSet
    s1) NEIntSet
    n2
      where
        (IntSet
    s1, Bool
    mem, IntSet
    s2) = Key -> IntSet -> (IntSet, Bool, IntSet)
    S.splitMember Key
    x IntSet
    s0
    {-# INLINEABLE splitMember #-}

    -- | /O(1)/.  Decompose a set into pieces based on the structure of the underlying
    -- tree.  This function is useful for consuming a set in parallel.
    --
    -- No guarantee is made as to the sizes of the pieces; an internal, but
    -- deterministic process determines this.  However, it is guaranteed that
    -- the pieces returned will be in ascending order (all elements in the
    -- first subset less than all elements in the second, and so on).
    --
    --  Note that the current implementation does not return more than four
    --  subsets, but you should not depend on this behaviour because it can
    --  change in the future without notice.
    splitRoot ::
      NEIntSet ->
      NonEmpty NEIntSet
    splitRoot :: NEIntSet -> NonEmpty NEIntSet
    splitRoot (NEIntSet Key
    x IntSet
    s) =
      Key -> NEIntSet
    singleton Key
    x
        NEIntSet -> [NEIntSet] -> NonEmpty NEIntSet
    forall a. a -> [a] -> NonEmpty a
    :| (IntSet -> Maybe NEIntSet) -> [IntSet] -> [NEIntSet]
    forall a b. (a -> Maybe b) -> [a] -> [b]
    mapMaybe IntSet -> Maybe NEIntSet
    nonEmptySet (IntSet -> [IntSet]
    S.splitRoot IntSet
    s)
    {-# INLINE splitRoot #-}

    -- | /O(n*log n)/.
    -- @'map' f s@ is the set obtained by applying @f@ to each element of @s@.
    --
    -- It's worth noting that the size of the result may be smaller if,
    -- for some @(x,y)@, @x \/= y && f x == f y@
    map ::
      (Key -> Key) ->
      NEIntSet ->
      NEIntSet
    map :: (Key -> Key) -> NEIntSet -> NEIntSet
    map Key -> Key
    f (NEIntSet Key
    x0 IntSet
    s) =
      NonEmpty Key -> NEIntSet
    fromList
        (NonEmpty Key -> NEIntSet)
    -> (IntSet -> NonEmpty Key) -> IntSet -> NEIntSet
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Key -> Key
    f Key
    x0 Key -> [Key] -> NonEmpty Key
    forall a. a -> [a] -> NonEmpty a
    :|)
        ([Key] -> NonEmpty Key)
    -> (IntSet -> [Key]) -> IntSet -> NonEmpty Key
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Key -> [Key] -> [Key]) -> [Key] -> IntSet -> [Key]
    forall b. (Key -> b -> b) -> b -> IntSet -> b
    S.foldr (\Key
    x [Key]
    xs -> Key -> Key
    f Key
    x Key -> [Key] -> [Key]
    forall a. a -> [a] -> [a]
    : [Key]
    xs) []
        (IntSet -> NEIntSet) -> IntSet -> NEIntSet
    forall a b. (a -> b) -> a -> b
    $ IntSet
    s
    {-# INLINE map #-}

    -- | /O(1)/. The minimal element of a set.  Note that this is total, making
    -- 'Data.IntSet.lookupMin' obsolete.  It is constant-time, so has better
    -- asymptotics than @Data.IntSet.lookupMin@ and @Data.Map.findMin@ as well.
    --
    -- > findMin (fromList (5 :| [3])) == 3
    findMin :: NEIntSet -> Key
    findMin :: NEIntSet -> Key
    findMin (NEIntSet Key
    x IntSet
    _) = Key
    x
    {-# INLINE findMin #-}

    -- | /O(log n)/. The maximal key of a set  Note that this is total,
    -- making 'Data.IntSet.lookupMin' obsolete.
    --
    -- > findMax (fromList (5 :| [3])) == 5
    findMax :: NEIntSet -> Key
    findMax :: NEIntSet -> Key
    findMax (NEIntSet Key
    x IntSet
    s) = Key -> ((Key, IntSet) -> Key) -> Maybe (Key, IntSet) -> Key
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe Key
    x (Key, IntSet) -> Key
    forall a b. (a, b) -> a
    fst (Maybe (Key, IntSet) -> Key)
    -> (IntSet -> Maybe (Key, IntSet)) -> IntSet -> Key
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . IntSet -> Maybe (Key, IntSet)
    S.maxView (IntSet -> Key) -> IntSet -> Key
    forall a b. (a -> b) -> a -> b
    $ IntSet
    s
    {-# INLINE findMax #-}

    -- | /O(1)/. Delete the minimal element.  Returns a potentially empty set
    -- ('IntSet'), because we might delete the final item in a singleton set.  It
    -- is constant-time, so has better asymptotics than @Data.IntSet.deleteMin@.
    --
    -- > deleteMin (fromList (5 :| [3, 7])) == Data.IntSet.fromList [5, 7]
    -- > deleteMin (singleton 5) == Data.IntSet.empty
    deleteMin :: NEIntSet -> IntSet
    deleteMin :: NEIntSet -> IntSet
    deleteMin (NEIntSet Key
    _ IntSet
    s) = IntSet
    s
    {-# INLINE deleteMin #-}

    -- | /O(log n)/. Delete the maximal element.  Returns a potentially empty
    -- set ('IntSet'), because we might delete the final item in a singleton set.
    --
    -- > deleteMax (fromList (5 :| [3, 7])) == Data.IntSet.fromList [3, 5]
    -- > deleteMax (singleton 5) == Data.IntSet.empty
    deleteMax :: NEIntSet -> IntSet
    deleteMax :: NEIntSet -> IntSet
    deleteMax (NEIntSet Key
    x IntSet
    s) = case IntSet -> Maybe (Key, IntSet)
    S.maxView IntSet
    s of
      Maybe (Key, IntSet)
    Nothing -> IntSet
    S.empty
      Just (Key
    _, IntSet
    s') -> Key -> IntSet -> IntSet
    insertMinSet Key
    x IntSet
    s'
    {-# INLINE deleteMax #-}

    -- | /O(1)/. Delete and find the minimal element.  It is constant-time, so
    -- has better asymptotics that @Data.IntSet.minView@ for 'IntSet'.
    --
    -- Note that unlike @Data.IntSet.deleteFindMin@ for 'IntSet', this cannot ever
    -- fail, and so is a total function. However, the result 'IntSet' is
    -- potentially empty, since the original set might have contained just
    -- a single item.
    --
    -- > deleteFindMin (fromList (5 :| [3, 10])) == (3, Data.IntSet.fromList [5, 10])
    deleteFindMin :: NEIntSet -> (Key, IntSet)
    deleteFindMin :: NEIntSet -> (Key, IntSet)
    deleteFindMin (NEIntSet Key
    x IntSet
    s) = (Key
    x, IntSet
    s)
    {-# INLINE deleteFindMin #-}

    -- | /O(log n)/. Delete and find the minimal element.
    --
    -- Note that unlike @Data.IntSet.deleteFindMax@ for 'IntSet', this cannot ever
    -- fail, and so is a total function. However, the result 'IntSet' is
    -- potentially empty, since the original set might have contained just
    -- a single item.
    --
    -- > deleteFindMax (fromList (5 :| [3, 10])) == (10, Data.IntSet.fromList [3, 5])
    deleteFindMax :: NEIntSet -> (Key, IntSet)
    deleteFindMax :: NEIntSet -> (Key, IntSet)
    deleteFindMax (NEIntSet Key
    x IntSet
    s) =
      (Key, IntSet)
    -> ((Key, IntSet) -> (Key, IntSet))
    -> Maybe (Key, IntSet)
    -> (Key, IntSet)
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe (Key
    x, IntSet
    S.empty) ((IntSet -> IntSet) -> (Key, IntSet) -> (Key, IntSet)
    forall b c a. (b -> c) -> (a, b) -> (a, c)
    forall (p :: * -> * -> *) b c a.
    Bifunctor p =>
    (b -> c) -> p a b -> p a c
    second (Key -> IntSet -> IntSet
    insertMinSet Key
    x))
        (Maybe (Key, IntSet) -> (Key, IntSet))
    -> (IntSet -> Maybe (Key, IntSet)) -> IntSet -> (Key, IntSet)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . IntSet -> Maybe (Key, IntSet)
    S.maxView
        (IntSet -> (Key, IntSet)) -> IntSet -> (Key, IntSet)
    forall a b. (a -> b) -> a -> b
    $ IntSet
    s
    {-# INLINE deleteFindMax #-}

    -- | /O(n)/. An alias of 'toAscList'. The elements of a set in ascending
    -- order.
    elems :: NEIntSet -> NonEmpty Key
    elems :: NEIntSet -> NonEmpty Key
    elems = NEIntSet -> NonEmpty Key
    toList
    {-# INLINE elems #-}

    -- | /O(n)/. Convert the set to an ascending non-empty list of elements.
    toAscList :: NEIntSet -> NonEmpty Key
    toAscList :: NEIntSet -> NonEmpty Key
    toAscList = NEIntSet -> NonEmpty Key
    toList
    {-# INLINE toAscList #-}

    -- | /O(n)/. Convert the set to a descending non-empty list of elements.
    toDescList :: NEIntSet -> NonEmpty Key
    toDescList :: NEIntSet -> NonEmpty Key
    toDescList (NEIntSet Key
    x IntSet
    s) = (NonEmpty Key -> Key -> NonEmpty Key)
    -> NonEmpty Key -> IntSet -> NonEmpty Key
    forall a. (a -> Key -> a) -> a -> IntSet -> a
    S.foldl' ((Key -> NonEmpty Key -> NonEmpty Key)
    -> NonEmpty Key -> Key -> NonEmpty Key
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip Key -> NonEmpty Key -> NonEmpty Key
    forall a. a -> NonEmpty a -> NonEmpty a
    (NE.<|)) (Key
    x Key -> [Key] -> NonEmpty Key
    forall a. a -> [a] -> NonEmpty a
    :| []) IntSet
    s
    {-# INLINE toDescList #-}

    combineEq :: NonEmpty Key -> NonEmpty Key
    combineEq :: NonEmpty Key -> NonEmpty Key
    combineEq (Key
    x :| [Key]
    xs) = Key -> [Key] -> NonEmpty Key
    forall {t}. Eq t => t -> [t] -> NonEmpty t
    go Key
    x [Key]
    xs
      where
        go :: t -> [t] -> NonEmpty t
    go t
    z [] = t
    z t -> [t] -> NonEmpty t
    forall a. a -> [a] -> NonEmpty a
    :| []
        go t
    z (t
    y : [t]
    ys)
          | t
    z t -> t -> Bool
    forall a. Eq a => a -> a -> Bool
    == t
    y = t -> [t] -> NonEmpty t
    go t
    z [t]
    ys
          | Bool
    otherwise = t
    z t -> NonEmpty t -> NonEmpty t
    forall a. a -> NonEmpty a -> NonEmpty a
    NE.<| t -> [t] -> NonEmpty t
    go t
    y [t]
    ys