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

    -- |
    -- Module      : Data.Set.NonEmpty
    -- Copyright   : (c) Justin Le 2018
    -- License     : BSD3
    --
    -- Maintainer  : justin@jle.im
    -- Stability   : experimental
    -- Portability : non-portable
    --
    -- = Non-Empty Finite Sets
    --
    -- The @'NESet' e@ type represents a non-empty set of elements of type @e@.
    -- Most operations require that @e@ be an instance of the 'Ord' class.
    -- A 'NESet' is strict in its elements.
    --
    -- See documentation for 'NESet' for information on how to convert and
    -- manipulate such non-empty set.
    --
    -- This module essentially re-imports the API of "Data.Set" and its 'Set'
    -- 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).  All typeclass constraints are identical to their "Data.Set"
    -- counterparts.
    --
    -- Because 'NESet' is implemented using 'Set', all of the caveats of using
    -- 'Set' 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, 'Set' is returned instead.
    --
    -- Some functions ('partition', 'spanAntitone', '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.Set" functions:
    --
    -- > import qualified Data.Set.NonEmpty as NES
    module Data.Set.NonEmpty (
      -- * Non-Empty Set Type
      NESet,

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

      -- * Construction
      singleton,
      fromList,
      fromAscList,
      fromDescList,
      fromDistinctAscList,
      fromDistinctDescList,
      powerSet,

      -- * Insertion
      insert,

      -- * Deletion
      delete,

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

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

      -- * Filter
      filter,
      takeWhileAntitone,
      dropWhileAntitone,
      spanAntitone,
      partition,
      split,
      splitMember,
      splitRoot,

      -- * Indexed
      lookupIndex,
      findIndex,
      elemAt,
      deleteAt,
      take,
      drop,
      splitAt,

      -- * Map
      map,
      mapMonotonic,

      -- * Folds
      foldr,
      foldl,
      F.foldr1,
      F.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 qualified Data.Foldable as F
    import Data.List.NonEmpty (NonEmpty (..))
    import qualified Data.List.NonEmpty as NE
    import Data.Maybe
    import qualified Data.Semigroup.Foldable as F1
    import Data.Set (Set)
    import qualified Data.Set as S
    import Data.Set.NonEmpty.Internal
    import Data.These
    import Prelude hiding (Foldable (..), drop, filter, map, splitAt, take)

    -- | /O(1)/ match, /O(log n)/ usage of contents. The 'IsNonEmpty' and
    -- 'IsEmpty' patterns allow you to treat a 'Set' as if it were either
    -- a @'IsNonEmpty' n@ (where @n@ is a 'NESet') or an 'IsEmpty'.
    --
    -- For example, you can pattern match on a 'Set':
    --
    -- @
    -- myFunc :: 'Set' X -> Y
    -- myFunc ('IsNonEmpty' n) =  -- here, the user provided a non-empty set, and @n@ is the 'NESet'
    -- myFunc 'IsEmpty'        =  -- here, the user provided an empty set
    -- @
    --
    -- Matching on @'IsNonEmpty' n@ means that the original 'Set' was /not/
    -- empty, and you have a verified-non-empty 'NESet' @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 'NESet' back into a 'Set', obscuring its non-emptiness (see 'toSet').
    pattern IsNonEmpty :: NESet a -> Set a
    pattern $mIsNonEmpty :: forall {r} {a}. Set a -> (NESet a -> r) -> ((# #) -> r) -> r
    $bIsNonEmpty :: forall a. NESet a -> Set a
    IsNonEmpty n <- (nonEmptySet -> Just n)
      where
        IsNonEmpty NESet a
    n = NESet a -> Set a
    forall a. NESet a -> Set a
    toSet NESet a
    n

    -- | /O(1)/. The 'IsNonEmpty' and 'IsEmpty' patterns allow you to treat
    -- a 'Set' as if it were either a @'IsNonEmpty' n@ (where @n@ is
    -- a 'NESet') or an 'IsEmpty'.
    --
    -- Matching on 'IsEmpty' means that the original 'Set' 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.Set.empty'.
    --
    -- See 'IsNonEmpty' for more information.
    pattern IsEmpty :: Set a
    pattern $mIsEmpty :: forall {r} {a}. Set a -> ((# #) -> r) -> ((# #) -> r) -> r
    $bIsEmpty :: forall a. Set a
    IsEmpty <- (S.null -> True)
      where
        IsEmpty = Set a
    forall a. Set a
    S.empty

    {-# COMPLETE IsNonEmpty, IsEmpty #-}

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

    -- | /O(log n)/. Convert a 'Set' into an 'NESet' 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.Set.fromList [5, 3]) == fromList (3 :| [4, 5])
    -- > insertSet 4 Data.Set.empty == singleton 4 "c"
    insertSet :: Ord a => a -> Set a -> NESet a
    insertSet :: forall a. Ord a => a -> Set a -> NESet a
    insertSet a
    x = NESet a -> (NESet a -> NESet a) -> Set a -> NESet a
    forall r a. r -> (NESet a -> r) -> Set a -> r
    withNonEmpty (a -> NESet a
    forall a. a -> NESet a
    singleton a
    x) (a -> NESet a -> NESet a
    forall a. Ord a => a -> NESet a -> NESet a
    insert a
    x)
    {-# INLINE insertSet #-}

    -- | /O(1)/ Convert a 'Set' into an 'NESet' 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.Set.fromList [5, 3]) == fromList (2 :| [3, 5])
    -- > valid (insertSetMin 2 (Data.Set.fromList [5, 3])) == True
    -- > valid (insertSetMin 7 (Data.Set.fromList [5, 3])) == False
    -- > valid (insertSetMin 3 (Data.Set.fromList [5, 3])) == False
    insertSetMin :: a -> Set a -> NESet a
    insertSetMin :: forall a. a -> Set a -> NESet a
    insertSetMin = a -> Set a -> NESet a
    forall a. a -> Set a -> NESet a
    NESet
    {-# INLINE insertSetMin #-}

    -- | /O(log n)/ Convert a 'Set' into an 'NESet' 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./
    --
    -- While this has the same asymptotics as 'insertSet', it saves a constant
    -- factor for key comparison (so may be helpful if comparison is expensive)
    -- and also does not require an 'Ord' instance for the key type.
    --
    -- > insertSetMin 7 (Data.Set.fromList [5, 3]) == fromList (3 :| [5, 7])
    -- > valid (insertSetMin 7 (Data.Set.fromList [5, 3])) == True
    -- > valid (insertSetMin 2 (Data.Set.fromList [5, 3])) == False
    -- > valid (insertSetMin 5 (Data.Set.fromList [5, 3])) == False
    insertSetMax :: a -> Set a -> NESet a
    insertSetMax :: forall a. a -> Set a -> NESet a
    insertSetMax a
    x = NESet a -> (NESet a -> NESet a) -> Set a -> NESet a
    forall r a. r -> (NESet a -> r) -> Set a -> r
    withNonEmpty (a -> NESet a
    forall a. a -> NESet a
    singleton a
    x) NESet a -> NESet a
    go
      where
        go :: NESet a -> NESet a
    go (NESet a
    x0 Set a
    s0) = a -> Set a -> NESet a
    forall a. a -> Set a -> NESet a
    NESet a
    x0 (Set a -> NESet a) -> (Set a -> Set a) -> Set a -> NESet a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . a -> Set a -> Set a
    forall a. a -> Set a -> Set a
    insertMaxSet a
    x (Set a -> NESet a) -> Set a -> NESet a
    forall a b. (a -> b) -> a -> b
    $ Set a
    s0
    {-# INLINE insertSetMax #-}

    -- | /O(n)/. Build a set from an ascending list in linear time.  /The
    -- precondition (input list is ascending) is not checked./
    fromAscList :: Eq a => NonEmpty a -> NESet a
    fromAscList :: forall a. Eq a => NonEmpty a -> NESet a
    fromAscList = NonEmpty a -> NESet a
    forall a. NonEmpty a -> NESet a
    fromDistinctAscList (NonEmpty a -> NESet a)
    -> (NonEmpty a -> NonEmpty a) -> NonEmpty a -> NESet a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NonEmpty a -> NonEmpty a
    forall a. Eq a => NonEmpty a -> NonEmpty a
    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 a -> NESet a
    fromDistinctAscList :: forall a. NonEmpty a -> NESet a
    fromDistinctAscList (a
    x :| [a]
    xs) =
      a -> Set a -> NESet a
    forall a. a -> Set a -> NESet a
    insertSetMin a
    x
        (Set a -> NESet a) -> ([a] -> Set a) -> [a] -> NESet a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . [a] -> Set a
    forall a. [a] -> Set a
    S.fromDistinctAscList
        ([a] -> NESet a) -> [a] -> NESet a
    forall a b. (a -> b) -> a -> b
    $ [a]
    xs
    {-# INLINE fromDistinctAscList #-}

    -- | /O(n)/. Build a set from a descending list in linear time.
    -- /The precondition (input list is descending) is not checked./
    fromDescList :: Eq a => NonEmpty a -> NESet a
    fromDescList :: forall a. Eq a => NonEmpty a -> NESet a
    fromDescList = NonEmpty a -> NESet a
    forall a. NonEmpty a -> NESet a
    fromDistinctDescList (NonEmpty a -> NESet a)
    -> (NonEmpty a -> NonEmpty a) -> NonEmpty a -> NESet a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NonEmpty a -> NonEmpty a
    forall a. Eq a => NonEmpty a -> NonEmpty a
    combineEq
    {-# INLINE fromDescList #-}

    -- | /O(n)/. Build a set from a descending list of distinct elements in linear time.
    -- /The precondition (input list is strictly descending) is not checked./
    fromDistinctDescList :: NonEmpty a -> NESet a
    fromDistinctDescList :: forall a. NonEmpty a -> NESet a
    fromDistinctDescList (a
    x :| [a]
    xs) =
      a -> Set a -> NESet a
    forall a. a -> Set a -> NESet a
    insertSetMax a
    x
        (Set a -> NESet a) -> ([a] -> Set a) -> [a] -> NESet a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . [a] -> Set a
    forall a. [a] -> Set a
    S.fromDistinctDescList
        ([a] -> NESet a) -> [a] -> NESet a
    forall a b. (a -> b) -> a -> b
    $ [a]
    xs
    {-# INLINE fromDistinctDescList #-}

    -- | Calculate the power set of a non-empty: the set of all its (non-empty)
    -- subsets.
    --
    -- @
    -- t ``member`` powerSet s == t ``isSubsetOf`` s
    -- @
    --
    -- Example:
    --
    -- @
    -- powerSet (fromList (1 :| [2,3])) =
    --   fromList (singleton 1 :| [ singleton 2
    --                            , singleton 3
    --                            , fromList (1 :| [2])
    --                            , fromList (1 :| [3])
    --                            , fromList (2 :| [3])
    --                            , fromList (1 :| [2,3])
    --                            ]
    --            )
    -- @
    --
    -- We know that the result is non-empty because the result will always at
    -- least contain the original set.
    powerSet ::
      forall a.
      () =>
      NESet a ->
      NESet (NESet a)
    powerSet :: forall a. NESet a -> NESet (NESet a)
    powerSet (NESet a
    x Set a
    s0) = case Set (NESet a) -> Maybe (NESet (NESet a))
    forall a. Set a -> Maybe (NESet a)
    nonEmptySet Set (NESet a)
    p1 of
      -- s0 was empty originally
      Maybe (NESet (NESet a))
    Nothing -> NESet a -> NESet (NESet a)
    forall a. a -> NESet a
    singleton (a -> NESet a
    forall a. a -> NESet a
    singleton a
    x)
      -- s1 was not empty originally
      Just NESet (NESet a)
    p2 ->
        (Set a -> NESet a) -> NESet (Set a) -> NESet (NESet a)
    forall a b. (a -> b) -> NESet a -> NESet b
    mapMonotonic (a -> Set a -> NESet a
    forall a. a -> Set a -> NESet a
    insertSetMin a
    x) NESet (Set a)
    p0
          NESet (NESet a) -> NESet (NESet a) -> NESet (NESet a)
    forall a. NESet a -> NESet a -> NESet a
    `merge` NESet (NESet a)
    p2
      where
        -- powerset should never be empty
        p0 :: NESet (Set a)
        p0 :: NESet (Set a)
    p0@(NESet Set a
    _ Set (Set a)
    p0s) = Set (Set a) -> NESet (Set a)
    forall a. Set a -> NESet a
    forSure (Set (Set a) -> NESet (Set a)) -> Set (Set a) -> NESet (Set a)
    forall a b. (a -> b) -> a -> b
    $ Set a -> Set (Set a)
    forall a. Set a -> Set (Set a)
    S.powerSet Set a
    s0
        p1 :: Set (NESet a)
        p1 :: Set (NESet a)
    p1 = (Set a -> NESet a) -> Set (Set a) -> Set (NESet a)
    forall a b. (a -> b) -> Set a -> Set b
    S.mapMonotonic Set a -> NESet a
    forall a. Set a -> NESet a
    forSure Set (Set a)
    p0s -- only minimal element is empty, so the rest aren't
        forSure :: Set a -> NESet a
    forSure =
          NESet a -> (NESet a -> NESet a) -> Set a -> NESet a
    forall r a. r -> (NESet a -> r) -> Set a -> r
    withNonEmpty
            ([Char] -> NESet a
    forall a. [Char] -> a
    errorWithoutStackTrace [Char]
    "NESet.powerSet: internal error")
            NESet a -> NESet a
    forall a. a -> a
    id
    {-# INLINEABLE powerSet #-}

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

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

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

    -- | /O(log n)/. Is the element not in the set?
    notMember :: Ord a => a -> NESet a -> Bool
    notMember :: forall a. Ord a => a -> NESet a -> Bool
    notMember a
    x (NESet a
    x0 Set a
    s) = case a -> a -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare a
    x a
    x0 of
      Ordering
    LT -> Bool
    True
      Ordering
    EQ -> Bool
    False
      Ordering
    GT -> a -> Set a -> Bool
    forall a. Ord a => a -> Set a -> Bool
    S.notMember a
    x Set a
    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 :: Ord a => a -> NESet a -> Maybe a
    lookupLT :: forall a. Ord a => a -> NESet a -> Maybe a
    lookupLT a
    x (NESet a
    x0 Set a
    s) = case a -> a -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare a
    x a
    x0 of
      Ordering
    LT -> Maybe a
    forall a. Maybe a
    Nothing
      Ordering
    EQ -> Maybe a
    forall a. Maybe a
    Nothing
      Ordering
    GT -> a -> Set a -> Maybe a
    forall a. Ord a => a -> Set a -> Maybe a
    S.lookupLT a
    x Set a
    s Maybe a -> Maybe a -> Maybe a
    forall a. Maybe a -> Maybe a -> Maybe a
    forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
    <|> a -> Maybe a
    forall a. a -> Maybe a
    Just a
    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 :: Ord a => a -> NESet a -> Maybe a
    lookupGT :: forall a. Ord a => a -> NESet a -> Maybe a
    lookupGT a
    x (NESet a
    x0 Set a
    s) = case a -> a -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare a
    x a
    x0 of
      Ordering
    LT -> a -> Maybe a
    forall a. a -> Maybe a
    Just a
    x0
      Ordering
    EQ -> Set a -> Maybe a
    forall a. Set a -> Maybe a
    S.lookupMin Set a
    s
      Ordering
    GT -> a -> Set a -> Maybe a
    forall a. Ord a => a -> Set a -> Maybe a
    S.lookupGT a
    x Set a
    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 :: Ord a => a -> NESet a -> Maybe a
    lookupLE :: forall a. Ord a => a -> NESet a -> Maybe a
    lookupLE a
    x (NESet a
    x0 Set a
    s) = case a -> a -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare a
    x a
    x0 of
      Ordering
    LT -> Maybe a
    forall a. Maybe a
    Nothing
      Ordering
    EQ -> a -> Maybe a
    forall a. a -> Maybe a
    Just a
    x0
      Ordering
    GT -> a -> Set a -> Maybe a
    forall a. Ord a => a -> Set a -> Maybe a
    S.lookupLE a
    x Set a
    s Maybe a -> Maybe a -> Maybe a
    forall a. Maybe a -> Maybe a -> Maybe a
    forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
    <|> a -> Maybe a
    forall a. a -> Maybe a
    Just a
    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 :: Ord a => a -> NESet a -> Maybe a
    lookupGE :: forall a. Ord a => a -> NESet a -> Maybe a
    lookupGE a
    x (NESet a
    x0 Set a
    s) = case a -> a -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare a
    x a
    x0 of
      Ordering
    LT -> a -> Maybe a
    forall a. a -> Maybe a
    Just a
    x0
      Ordering
    EQ -> a -> Maybe a
    forall a. a -> Maybe a
    Just a
    x0
      Ordering
    GT -> a -> Set a -> Maybe a
    forall a. Ord a => a -> Set a -> Maybe a
    S.lookupGE a
    x Set a
    s
    {-# INLINE lookupGE #-}

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

    -- | /O(n+m)/. Is this a proper subset? (ie. a subset but not equal).
    isProperSubsetOf ::
      Ord a =>
      NESet a ->
      NESet a ->
      Bool
    isProperSubsetOf :: forall a. Ord a => NESet a -> NESet a -> Bool
    isProperSubsetOf NESet a
    s0 NESet a
    s1 =
      Set a -> Int
    forall a. Set a -> Int
    S.size (NESet a -> Set a
    forall a. NESet a -> Set a
    nesSet NESet a
    s0) Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    < Set a -> Int
    forall a. Set a -> Int
    S.size (NESet a -> Set a
    forall a. NESet a -> Set a
    nesSet NESet a
    s1)
        Bool -> Bool -> Bool
    && NESet a
    s0 NESet a -> NESet a -> Bool
    forall a. Ord a => NESet a -> NESet a -> Bool
    `isSubsetOf` NESet a
    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 ::
      Ord a =>
      NESet a ->
      NESet a ->
      Bool
    disjoint :: forall a. Ord a => NESet a -> NESet a -> Bool
    disjoint n1 :: NESet a
    n1@(NESet a
    x1 Set a
    s1) n2 :: NESet a
    n2@(NESet a
    x2 Set a
    s2) = case a -> a -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare a
    x1 a
    x2 of
      -- x1 is not in n2
      Ordering
    LT -> Set a
    s1 Set a -> Set a -> Bool
    forall a. Ord a => Set a -> Set a -> Bool
    `S.disjoint` NESet a -> Set a
    forall a. NESet a -> Set a
    toSet NESet a
    n2
      -- k1 and k2 are a part of the result
      Ordering
    EQ -> Bool
    False
      -- k2 is not in n1
      Ordering
    GT -> NESet a -> Set a
    forall a. NESet a -> Set a
    toSet NESet a
    n1 Set a -> Set a -> Bool
    forall a. Ord a => Set a -> Set a -> Bool
    `S.disjoint` Set a
    s2
    {-# INLINE disjoint #-}

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

    -- | Same as 'difference'.
    (\\) ::
      Ord a =>
      NESet a ->
      NESet a ->
      Set a
    \\ :: forall a. Ord a => NESet a -> NESet a -> Set a
    (\\) = NESet a -> NESet a -> Set a
    forall a. Ord a => NESet a -> NESet a -> Set a
    difference
    {-# INLINE (\\) #-}

    -- | /O(m*log(n\/m + 1)), m <= n/. The intersection of two sets.
    --
    -- Returns a potentially empty set ('Set'), because the two sets might have
    -- an empty intersection.
    --
    -- Elements of the result come from the first set, so for example
    --
    -- > import qualified Data.Set.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 ::
      Ord a =>
      NESet a ->
      NESet a ->
      Set a
    intersection :: forall a. Ord a => NESet a -> NESet a -> Set a
    intersection n1 :: NESet a
    n1@(NESet a
    x1 Set a
    s1) n2 :: NESet a
    n2@(NESet a
    x2 Set a
    s2) = case a -> a -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare a
    x1 a
    x2 of
      -- x1 is not in n2
      Ordering
    LT -> Set a
    s1 Set a -> Set a -> Set a
    forall a. Ord a => Set a -> Set a -> Set a
    `S.intersection` NESet a -> Set a
    forall a. NESet a -> Set a
    toSet NESet a
    n2
      -- x1 and x2 are a part of the result
      Ordering
    EQ -> a -> Set a -> Set a
    forall a. a -> Set a -> Set a
    insertMinSet a
    x1 (Set a -> Set a) -> Set a -> Set a
    forall a b. (a -> b) -> a -> b
    $ Set a
    s1 Set a -> Set a -> Set a
    forall a. Ord a => Set a -> Set a -> Set a
    `S.intersection` Set a
    s2
      -- x2 is not in n1
      Ordering
    GT -> NESet a -> Set a
    forall a. NESet a -> Set a
    toSet NESet a
    n1 Set a -> Set a -> Set a
    forall a. Ord a => Set a -> Set a -> Set a
    `S.intersection` Set a
    s2
    {-# INLINE intersection #-}

    -- | Calculate the Cartesian product of two sets.
    --
    -- @
    -- cartesianProduct xs ys = fromList $ liftA2 (,) (toList xs) (toList ys)
    -- @
    --
    -- Example:
    --
    -- @
    -- cartesianProduct (fromList (1:|[2])) (fromList (\'a\':|[\'b\'])) =
    --   fromList ((1,\'a\') :| [(1,\'b\'), (2,\'a\'), (2,\'b\')])
    -- @
    cartesianProduct ::
      NESet a ->
      NESet b ->
      NESet (a, b)
    cartesianProduct :: forall a b. NESet a -> NESet b -> NESet (a, b)
    cartesianProduct NESet a
    n1 NESet b
    n2 =
      MergeNESet (a, b) -> NESet (a, b)
    forall a. MergeNESet a -> NESet a
    getMergeNESet
        (MergeNESet (a, b) -> NESet (a, b))
    -> (NESet a -> MergeNESet (a, b)) -> NESet a -> NESet (a, b)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> MergeNESet (a, b)) -> NESet a -> MergeNESet (a, b)
    forall m a. Semigroup m => (a -> m) -> NESet a -> m
    forall (t :: * -> *) m a.
    (Foldable1 t, Semigroup m) =>
    (a -> m) -> t a -> m
    F1.foldMap1 (\a
    x -> NESet (a, b) -> MergeNESet (a, b)
    forall a. NESet a -> MergeNESet a
    MergeNESet (NESet (a, b) -> MergeNESet (a, b))
    -> NESet (a, b) -> MergeNESet (a, b)
    forall a b. (a -> b) -> a -> b
    $ (b -> (a, b)) -> NESet b -> NESet (a, b)
    forall a b. (a -> b) -> NESet a -> NESet b
    mapMonotonic (a
    x,) NESet b
    n2)
        (NESet a -> NESet (a, b)) -> NESet a -> NESet (a, b)
    forall a b. (a -> b) -> a -> b
    $ NESet a
    n1
    {-# INLINE cartesianProduct #-}

    -- | Calculate the disjoint union of two sets.
    --
    -- @ disjointUnion xs ys = map Left xs ``union`` map Right ys @
    --
    -- Example:
    --
    -- @
    -- disjointUnion (fromList (1:|[2])) (fromList ("hi":|["bye"])) =
    --   fromList (Left 1 :| [Left 2, Right "hi", Right "bye"])
    -- @
    disjointUnion ::
      NESet a ->
      NESet b ->
      NESet (Either a b)
    disjointUnion :: forall a b. NESet a -> NESet b -> NESet (Either a b)
    disjointUnion (NESet a
    x1 Set a
    s1) NESet b
    n2 =
      Either a b -> Set (Either a b) -> NESet (Either a b)
    forall a. a -> Set a -> NESet a
    NESet
        (a -> Either a b
    forall a b. a -> Either a b
    Left a
    x1)
        (Set a
    s1 Set a -> Set b -> Set (Either a b)
    forall a b. Set a -> Set b -> Set (Either a b)
    `S.disjointUnion` NESet b -> Set b
    forall a. NESet a -> Set a
    toSet NESet b
    n2)
    {-# INLINE disjointUnion #-}

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

    -- | /O(log n)/. Take while a predicate on the elements holds.  The user is
    -- responsible for ensuring that for all elements @j@ and @k@ in the set,
    -- @j \< k ==\> p j \>= p k@. See note at 'spanAntitone'.
    --
    -- Returns a potentially empty set ('Set') because the predicate might fail
    -- on the first input.
    --
    -- @
    -- takeWhileAntitone p = Data.Set.fromDistinctAscList . Data.List.NonEmpty.takeWhile p . 'toList'
    -- takeWhileAntitone p = 'filter' p
    -- @
    takeWhileAntitone ::
      (a -> Bool) ->
      NESet a ->
      Set a
    takeWhileAntitone :: forall a. (a -> Bool) -> NESet a -> Set a
    takeWhileAntitone a -> Bool
    f (NESet a
    x Set a
    s)
      | a -> Bool
    f a
    x = a -> Set a -> Set a
    forall a. a -> Set a -> Set a
    insertMinSet a
    x (Set a -> Set a) -> (Set a -> Set a) -> Set a -> Set a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> Bool) -> Set a -> Set a
    forall a. (a -> Bool) -> Set a -> Set a
    S.takeWhileAntitone a -> Bool
    f (Set a -> Set a) -> Set a -> Set a
    forall a b. (a -> b) -> a -> b
    $ Set a
    s
      | Bool
    otherwise = Set a
    forall a. Set a
    S.empty
    {-# INLINE takeWhileAntitone #-}

    -- | /O(log n)/. Drop while a predicate on the elements holds.  The user is
    -- responsible for ensuring that for all elements @j@ and @k@ in the set,
    -- @j \< k ==\> p j \>= p k@. See note at 'spanAntitone'.
    --
    -- Returns a potentially empty set ('Set') because the predicate might be
    -- true for all items.
    --
    -- @
    -- dropWhileAntitone p = Data.Set.fromDistinctAscList . Data.List.NonEmpty.dropWhile p . 'toList'
    -- dropWhileAntitone p = 'filter' (not . p)
    -- @
    dropWhileAntitone ::
      (a -> Bool) ->
      NESet a ->
      Set a
    dropWhileAntitone :: forall a. (a -> Bool) -> NESet a -> Set a
    dropWhileAntitone a -> Bool
    f n :: NESet a
    n@(NESet a
    x Set a
    s)
      | a -> Bool
    f a
    x = (a -> Bool) -> Set a -> Set a
    forall a. (a -> Bool) -> Set a -> Set a
    S.dropWhileAntitone a -> Bool
    f Set a
    s
      | Bool
    otherwise = NESet a -> Set a
    forall a. NESet a -> Set a
    toSet NESet a
    n
    {-# INLINE dropWhileAntitone #-}

    -- | /O(log n)/. Divide a set at the point where a predicate on the
    -- elements stops holding.  The user is responsible for ensuring that for
    -- all elements @j@ and @k@ in the set, @j \< k ==\> p j \>= p k@.
    --
    -- Returns a 'These' with potentially two non-empty sets:
    --
    -- *   @'This' n1@ means that the predicate never failed for any item,
    --     returning the original set
    -- *   @'That' n2@ means that the predicate failed for the first item,
    --     returning the original set
    -- *   @'These' n1 n2@ gives @n1@ (the set up to the point where the
    --     predicate stops holding) and @n2@ (the set starting from
    --     the point where the predicate stops holding)
    --
    -- @
    -- spanAntitone p xs = partition p xs
    -- @
    --
    -- Note: if @p@ is not actually antitone, then @spanAntitone@ will split the set
    -- at some /unspecified/ point where the predicate switches from holding to not
    -- holding (where the predicate is seen to hold before the first element and to fail
    -- after the last element).
    spanAntitone ::
      (a -> Bool) ->
      NESet a ->
      These (NESet a) (NESet a)
    spanAntitone :: forall a. (a -> Bool) -> NESet a -> These (NESet a) (NESet a)
    spanAntitone a -> Bool
    f n :: NESet a
    n@(NESet a
    x Set a
    s0)
      | a -> Bool
    f a
    x = case (Set a -> Maybe (NESet a)
    forall a. Set a -> Maybe (NESet a)
    nonEmptySet Set a
    s1, Set a -> Maybe (NESet a)
    forall a. Set a -> Maybe (NESet a)
    nonEmptySet Set a
    s2) of
          (Maybe (NESet a)
    Nothing, Maybe (NESet a)
    Nothing) -> NESet a -> These (NESet a) (NESet a)
    forall a b. a -> These a b
    This NESet a
    n
          (Just NESet a
    _, Maybe (NESet a)
    Nothing) -> NESet a -> These (NESet a) (NESet a)
    forall a b. a -> These a b
    This NESet a
    n
          (Maybe (NESet a)
    Nothing, Just NESet a
    n2) -> NESet a -> NESet a -> These (NESet a) (NESet a)
    forall a b. a -> b -> These a b
    These (a -> NESet a
    forall a. a -> NESet a
    singleton a
    x) NESet a
    n2
          (Just NESet a
    _, Just NESet a
    n2) -> NESet a -> NESet a -> These (NESet a) (NESet a)
    forall a b. a -> b -> These a b
    These (a -> Set a -> NESet a
    forall a. a -> Set a -> NESet a
    insertSetMin a
    x Set a
    s1) NESet a
    n2
      | Bool
    otherwise = NESet a -> These (NESet a) (NESet a)
    forall a b. b -> These a b
    That NESet a
    n
      where
        (Set a
    s1, Set a
    s2) = (a -> Bool) -> Set a -> (Set a, Set a)
    forall a. (a -> Bool) -> Set a -> (Set a, Set a)
    S.spanAntitone a -> Bool
    f Set a
    s0
    {-# INLINEABLE spanAntitone #-}

    -- | /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 ::
      (a -> Bool) ->
      NESet a ->
      These (NESet a) (NESet a)
    partition :: forall a. (a -> Bool) -> NESet a -> These (NESet a) (NESet a)
    partition a -> Bool
    f n :: NESet a
    n@(NESet a
    x Set a
    s0) = case (Set a -> Maybe (NESet a)
    forall a. Set a -> Maybe (NESet a)
    nonEmptySet Set a
    s1, Set a -> Maybe (NESet a)
    forall a. Set a -> Maybe (NESet a)
    nonEmptySet Set a
    s2) of
      (Maybe (NESet a)
    Nothing, Maybe (NESet a)
    Nothing)
        | a -> Bool
    f a
    x -> NESet a -> These (NESet a) (NESet a)
    forall a b. a -> These a b
    This NESet a
    n
        | Bool
    otherwise -> NESet a -> These (NESet a) (NESet a)
    forall a b. b -> These a b
    That NESet a
    n
      (Just NESet a
    n1, Maybe (NESet a)
    Nothing)
        | a -> Bool
    f a
    x -> NESet a -> These (NESet a) (NESet a)
    forall a b. a -> These a b
    This NESet a
    n
        | Bool
    otherwise -> NESet a -> NESet a -> These (NESet a) (NESet a)
    forall a b. a -> b -> These a b
    These NESet a
    n1 (a -> NESet a
    forall a. a -> NESet a
    singleton a
    x)
      (Maybe (NESet a)
    Nothing, Just NESet a
    n2)
        | a -> Bool
    f a
    x -> NESet a -> NESet a -> These (NESet a) (NESet a)
    forall a b. a -> b -> These a b
    These (a -> NESet a
    forall a. a -> NESet a
    singleton a
    x) NESet a
    n2
        | Bool
    otherwise -> NESet a -> These (NESet a) (NESet a)
    forall a b. b -> These a b
    That NESet a
    n
      (Just NESet a
    n1, Just NESet a
    n2)
        | a -> Bool
    f a
    x -> NESet a -> NESet a -> These (NESet a) (NESet a)
    forall a b. a -> b -> These a b
    These (a -> Set a -> NESet a
    forall a. a -> Set a -> NESet a
    insertSetMin a
    x Set a
    s1) NESet a
    n2
        | Bool
    otherwise -> NESet a -> NESet a -> These (NESet a) (NESet a)
    forall a b. a -> b -> These a b
    These NESet a
    n1 (a -> Set a -> NESet a
    forall a. a -> Set a -> NESet a
    insertSetMin a
    x Set a
    s2)
      where
        (Set a
    s1, Set a
    s2) = (a -> Bool) -> Set a -> (Set a, Set a)
    forall a. (a -> Bool) -> Set a -> (Set a, Set a)
    S.partition a -> Bool
    f Set a
    s0
    {-# INLINEABLE partition #-}

    -- | /O(log n)/. The expression (@'split' x set@) is potentially a 'These'
    -- containing up to two 'NESet'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 ::
      Ord a =>
      a ->
      NESet a ->
      Maybe (These (NESet a) (NESet a))
    split :: forall a.
    Ord a =>
    a -> NESet a -> Maybe (These (NESet a) (NESet a))
    split a
    x n :: NESet a
    n@(NESet a
    x0 Set a
    s0) = case a -> a -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare a
    x a
    x0 of
      Ordering
    LT -> These (NESet a) (NESet a) -> Maybe (These (NESet a) (NESet a))
    forall a. a -> Maybe a
    Just (These (NESet a) (NESet a) -> Maybe (These (NESet a) (NESet a)))
    -> These (NESet a) (NESet a) -> Maybe (These (NESet a) (NESet a))
    forall a b. (a -> b) -> a -> b
    $ NESet a -> These (NESet a) (NESet a)
    forall a b. b -> These a b
    That NESet a
    n
      Ordering
    EQ -> NESet a -> These (NESet a) (NESet a)
    forall a b. b -> These a b
    That (NESet a -> These (NESet a) (NESet a))
    -> Maybe (NESet a) -> Maybe (These (NESet a) (NESet a))
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> Set a -> Maybe (NESet a)
    forall a. Set a -> Maybe (NESet a)
    nonEmptySet Set a
    s0
      Ordering
    GT -> case (Set a -> Maybe (NESet a)
    forall a. Set a -> Maybe (NESet a)
    nonEmptySet Set a
    s1, Set a -> Maybe (NESet a)
    forall a. Set a -> Maybe (NESet a)
    nonEmptySet Set a
    s2) of
        (Maybe (NESet a)
    Nothing, Maybe (NESet a)
    Nothing) -> These (NESet a) (NESet a) -> Maybe (These (NESet a) (NESet a))
    forall a. a -> Maybe a
    Just (These (NESet a) (NESet a) -> Maybe (These (NESet a) (NESet a)))
    -> These (NESet a) (NESet a) -> Maybe (These (NESet a) (NESet a))
    forall a b. (a -> b) -> a -> b
    $ NESet a -> These (NESet a) (NESet a)
    forall a b. a -> These a b
    This (a -> NESet a
    forall a. a -> NESet a
    singleton a
    x0)
        (Just NESet a
    _, Maybe (NESet a)
    Nothing) -> These (NESet a) (NESet a) -> Maybe (These (NESet a) (NESet a))
    forall a. a -> Maybe a
    Just (These (NESet a) (NESet a) -> Maybe (These (NESet a) (NESet a)))
    -> These (NESet a) (NESet a) -> Maybe (These (NESet a) (NESet a))
    forall a b. (a -> b) -> a -> b
    $ NESet a -> These (NESet a) (NESet a)
    forall a b. a -> These a b
    This (a -> Set a -> NESet a
    forall a. a -> Set a -> NESet a
    insertSetMin a
    x0 Set a
    s1)
        (Maybe (NESet a)
    Nothing, Just NESet a
    n2) -> These (NESet a) (NESet a) -> Maybe (These (NESet a) (NESet a))
    forall a. a -> Maybe a
    Just (These (NESet a) (NESet a) -> Maybe (These (NESet a) (NESet a)))
    -> These (NESet a) (NESet a) -> Maybe (These (NESet a) (NESet a))
    forall a b. (a -> b) -> a -> b
    $ NESet a -> NESet a -> These (NESet a) (NESet a)
    forall a b. a -> b -> These a b
    These (a -> NESet a
    forall a. a -> NESet a
    singleton a
    x0) NESet a
    n2
        (Just NESet a
    _, Just NESet a
    n2) -> These (NESet a) (NESet a) -> Maybe (These (NESet a) (NESet a))
    forall a. a -> Maybe a
    Just (These (NESet a) (NESet a) -> Maybe (These (NESet a) (NESet a)))
    -> These (NESet a) (NESet a) -> Maybe (These (NESet a) (NESet a))
    forall a b. (a -> b) -> a -> b
    $ NESet a -> NESet a -> These (NESet a) (NESet a)
    forall a b. a -> b -> These a b
    These (a -> Set a -> NESet a
    forall a. a -> Set a -> NESet a
    insertSetMin a
    x0 Set a
    s1) NESet a
    n2
      where
        (Set a
    s1, Set a
    s2) = a -> Set a -> (Set a, Set a)
    forall a. Ord a => a -> Set a -> (Set a, Set a)
    S.split a
    x Set a
    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 ::
      Ord a =>
      a ->
      NESet a ->
      (Bool, Maybe (These (NESet a) (NESet a)))
    splitMember :: forall a.
    Ord a =>
    a -> NESet a -> (Bool, Maybe (These (NESet a) (NESet a)))
    splitMember a
    x n :: NESet a
    n@(NESet a
    x0 Set a
    s0) = case a -> a -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare a
    x a
    x0 of
      Ordering
    LT -> (Bool
    False, These (NESet a) (NESet a) -> Maybe (These (NESet a) (NESet a))
    forall a. a -> Maybe a
    Just (These (NESet a) (NESet a) -> Maybe (These (NESet a) (NESet a)))
    -> These (NESet a) (NESet a) -> Maybe (These (NESet a) (NESet a))
    forall a b. (a -> b) -> a -> b
    $ NESet a -> These (NESet a) (NESet a)
    forall a b. b -> These a b
    That NESet a
    n)
      Ordering
    EQ -> (Bool
    True, NESet a -> These (NESet a) (NESet a)
    forall a b. b -> These a b
    That (NESet a -> These (NESet a) (NESet a))
    -> Maybe (NESet a) -> Maybe (These (NESet a) (NESet a))
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> Set a -> Maybe (NESet a)
    forall a. Set a -> Maybe (NESet a)
    nonEmptySet Set a
    s0)
      Ordering
    GT -> (Bool
    mem,) (Maybe (These (NESet a) (NESet a))
     -> (Bool, Maybe (These (NESet a) (NESet a))))
    -> Maybe (These (NESet a) (NESet a))
    -> (Bool, Maybe (These (NESet a) (NESet a)))
    forall a b. (a -> b) -> a -> b
    $ case (Set a -> Maybe (NESet a)
    forall a. Set a -> Maybe (NESet a)
    nonEmptySet Set a
    s1, Set a -> Maybe (NESet a)
    forall a. Set a -> Maybe (NESet a)
    nonEmptySet Set a
    s2) of
        (Maybe (NESet a)
    Nothing, Maybe (NESet a)
    Nothing) -> These (NESet a) (NESet a) -> Maybe (These (NESet a) (NESet a))
    forall a. a -> Maybe a
    Just (These (NESet a) (NESet a) -> Maybe (These (NESet a) (NESet a)))
    -> These (NESet a) (NESet a) -> Maybe (These (NESet a) (NESet a))
    forall a b. (a -> b) -> a -> b
    $ NESet a -> These (NESet a) (NESet a)
    forall a b. a -> These a b
    This (a -> NESet a
    forall a. a -> NESet a
    singleton a
    x0)
        (Just NESet a
    _, Maybe (NESet a)
    Nothing) -> These (NESet a) (NESet a) -> Maybe (These (NESet a) (NESet a))
    forall a. a -> Maybe a
    Just (These (NESet a) (NESet a) -> Maybe (These (NESet a) (NESet a)))
    -> These (NESet a) (NESet a) -> Maybe (These (NESet a) (NESet a))
    forall a b. (a -> b) -> a -> b
    $ NESet a -> These (NESet a) (NESet a)
    forall a b. a -> These a b
    This (a -> Set a -> NESet a
    forall a. a -> Set a -> NESet a
    insertSetMin a
    x0 Set a
    s1)
        (Maybe (NESet a)
    Nothing, Just NESet a
    n2) -> These (NESet a) (NESet a) -> Maybe (These (NESet a) (NESet a))
    forall a. a -> Maybe a
    Just (These (NESet a) (NESet a) -> Maybe (These (NESet a) (NESet a)))
    -> These (NESet a) (NESet a) -> Maybe (These (NESet a) (NESet a))
    forall a b. (a -> b) -> a -> b
    $ NESet a -> NESet a -> These (NESet a) (NESet a)
    forall a b. a -> b -> These a b
    These (a -> NESet a
    forall a. a -> NESet a
    singleton a
    x0) NESet a
    n2
        (Just NESet a
    _, Just NESet a
    n2) -> These (NESet a) (NESet a) -> Maybe (These (NESet a) (NESet a))
    forall a. a -> Maybe a
    Just (These (NESet a) (NESet a) -> Maybe (These (NESet a) (NESet a)))
    -> These (NESet a) (NESet a) -> Maybe (These (NESet a) (NESet a))
    forall a b. (a -> b) -> a -> b
    $ NESet a -> NESet a -> These (NESet a) (NESet a)
    forall a b. a -> b -> These a b
    These (a -> Set a -> NESet a
    forall a. a -> Set a -> NESet a
    insertSetMin a
    x0 Set a
    s1) NESet a
    n2
      where
        (Set a
    s1, Bool
    mem, Set a
    s2) = a -> Set a -> (Set a, Bool, Set a)
    forall a. Ord a => a -> Set a -> (Set a, Bool, Set a)
    S.splitMember a
    x Set a
    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 ::
      NESet a ->
      NonEmpty (NESet a)
    splitRoot :: forall a. NESet a -> NonEmpty (NESet a)
    splitRoot (NESet a
    x Set a
    s) =
      a -> NESet a
    forall a. a -> NESet a
    singleton a
    x
        NESet a -> [NESet a] -> NonEmpty (NESet a)
    forall a. a -> [a] -> NonEmpty a
    :| (Set a -> Maybe (NESet a)) -> [Set a] -> [NESet a]
    forall a b. (a -> Maybe b) -> [a] -> [b]
    mapMaybe Set a -> Maybe (NESet a)
    forall a. Set a -> Maybe (NESet a)
    nonEmptySet (Set a -> [Set a]
    forall a. Set a -> [Set a]
    S.splitRoot Set a
    s)
    {-# INLINE splitRoot #-}

    -- | /O(log n)/. Lookup the /index/ of an element, which is its zero-based
    -- index in the sorted sequence of elements. The index is a number from /0/
    -- up to, but not including, the 'size' of the set.
    --
    -- > isJust   (lookupIndex 2 (fromList (5:|[3]))) == False
    -- > fromJust (lookupIndex 3 (fromList (5:|[3]))) == 0
    -- > fromJust (lookupIndex 5 (fromList (5:|[3]))) == 1
    -- > isJust   (lookupIndex 6 (fromList (5:|[3]))) == False
    lookupIndex ::
      Ord a =>
      a ->
      NESet a ->
      Maybe Int
    lookupIndex :: forall a. Ord a => a -> NESet a -> Maybe Int
    lookupIndex a
    x (NESet a
    x0 Set a
    s) = case a -> a -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare a
    x a
    x0 of
      Ordering
    LT -> Maybe Int
    forall a. Maybe a
    Nothing
      Ordering
    EQ -> Int -> Maybe Int
    forall a. a -> Maybe a
    Just Int
    0
      Ordering
    GT -> (Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + Int
    1) (Int -> Int) -> Maybe Int -> Maybe Int
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> a -> Set a -> Maybe Int
    forall a. Ord a => a -> Set a -> Maybe Int
    S.lookupIndex a
    x Set a
    s
    {-# INLINE lookupIndex #-}

    -- | /O(log n)/. Return the /index/ of an element, which is its zero-based
    -- index in the sorted sequence of elements. The index is a number from /0/
    -- up to, but not including, the 'size' of the set. Calls 'error' when the
    -- element is not a 'member' of the set.
    --
    -- > findIndex 2 (fromList (5:|[3]))    Error: element is not in the set
    -- > findIndex 3 (fromList (5:|[3])) == 0
    -- > findIndex 5 (fromList (5:|[3])) == 1
    -- > findIndex 6 (fromList (5:|[3]))    Error: element is not in the set
    findIndex ::
      Ord a =>
      a ->
      NESet a ->
      Int
    findIndex :: forall a. Ord a => a -> NESet a -> Int
    findIndex a
    k = Int -> Maybe Int -> Int
    forall a. a -> Maybe a -> a
    fromMaybe Int
    forall {a}. a
    e (Maybe Int -> Int) -> (NESet a -> Maybe Int) -> NESet a -> Int
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . a -> NESet a -> Maybe Int
    forall a. Ord a => a -> NESet a -> Maybe Int
    lookupIndex a
    k
      where
        e :: a
    e = [Char] -> a
    forall a. HasCallStack => [Char] -> a
    error [Char]
    "NESet.findIndex: element is not in the set"
    {-# INLINE findIndex #-}

    -- | /O(log n)/. Retrieve an element by its /index/, i.e. by its zero-based
    -- index in the sorted sequence of elements. If the /index/ is out of range
    -- (less than zero, greater or equal to 'size' of the set), 'error' is
    -- called.
    --
    -- > elemAt 0 (fromList (5:|[3])) == 3
    -- > elemAt 1 (fromList (5:|[3])) == 5
    -- > elemAt 2 (fromList (5:|[3]))    Error: index out of range
    elemAt ::
      Int ->
      NESet a ->
      a
    elemAt :: forall a. Int -> NESet a -> a
    elemAt Int
    0 (NESet a
    x Set a
    _) = a
    x
    elemAt Int
    i (NESet a
    _ Set a
    s) = Int -> Set a -> a
    forall a. Int -> Set a -> a
    S.elemAt (Int
    i Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1) Set a
    s
    {-# INLINE elemAt #-}

    -- | /O(log n)/. Delete the element at /index/, i.e. by its zero-based
    -- index in the sorted sequence of elements. If the /index/ is out of range
    -- (less than zero, greater or equal to 'size' of the set), 'error' is
    -- called.
    --
    -- Returns a potentially empty set ('Set'), because this could potentailly
    -- delete the final element in a singleton set.
    --
    -- > deleteAt 0    (fromList (5:|[3])) == singleton 5
    -- > deleteAt 1    (fromList (5:|[3])) == singleton 3
    -- > deleteAt 2    (fromList (5:|[3]))    Error: index out of range
    -- > deleteAt (-1) (fromList (5:|[3]))    Error: index out of range
    deleteAt ::
      Int ->
      NESet a ->
      Set a
    deleteAt :: forall a. Int -> NESet a -> Set a
    deleteAt Int
    0 (NESet a
    _ Set a
    s) = Set a
    s
    deleteAt Int
    i (NESet a
    x Set a
    s) = a -> Set a -> Set a
    forall a. a -> Set a -> Set a
    insertMinSet a
    x (Set a -> Set a) -> (Set a -> Set a) -> Set a -> Set a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Int -> Set a -> Set a
    forall a. Int -> Set a -> Set a
    S.deleteAt (Int
    i Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1) (Set a -> Set a) -> Set a -> Set a
    forall a b. (a -> b) -> a -> b
    $ Set a
    s
    {-# INLINEABLE deleteAt #-}

    -- | Take a given number of elements in order, beginning
    -- with the smallest ones.
    --
    -- Returns a potentailly empty set ('Set'), which can only happen when
    -- calling @take 0@.
    --
    -- @
    -- take n = Data.Set.fromDistinctAscList . Data.List.NonEmpty.take n . 'toAscList'
    -- @
    take ::
      Int ->
      NESet a ->
      Set a
    take :: forall a. Int -> NESet a -> Set a
    take Int
    0 (NESet a
    _ Set a
    _) = Set a
    forall a. Set a
    S.empty
    take Int
    i (NESet a
    x Set a
    s) = a -> Set a -> Set a
    forall a. a -> Set a -> Set a
    insertMinSet a
    x (Set a -> Set a) -> (Set a -> Set a) -> Set a -> Set a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Int -> Set a -> Set a
    forall a. Int -> Set a -> Set a
    S.take (Int
    i Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1) (Set a -> Set a) -> Set a -> Set a
    forall a b. (a -> b) -> a -> b
    $ Set a
    s
    {-# INLINEABLE take #-}

    -- | Drop a given number of elements in order, beginning
    -- with the smallest ones.
    --
    -- Returns a potentailly empty set ('Set'), in the case that 'drop' is
    -- called with a number equal to or greater the number of items in the set,
    -- and we drop every item.
    --
    -- @
    -- drop n = Data.Set.fromDistinctAscList . Data.List.NonEmpty.drop n . 'toAscList'
    -- @
    drop ::
      Int ->
      NESet a ->
      Set a
    drop :: forall a. Int -> NESet a -> Set a
    drop Int
    0 NESet a
    n = NESet a -> Set a
    forall a. NESet a -> Set a
    toSet NESet a
    n
    drop Int
    n (NESet a
    _ Set a
    s) = Int -> Set a -> Set a
    forall a. Int -> Set a -> Set a
    S.drop (Int
    n Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1) Set a
    s
    {-# INLINEABLE drop #-}

    -- | /O(log n)/. Split a set at a particular index @i@.
    --
    -- *   @'This' n1@ means that there are less than @i@ items in the set, and
    --     @n1@ is the original set.
    -- *   @'That' n2@ means @i@ was 0; we dropped 0 items, so @n2@ is the
    --     original set.
    -- *   @'These' n1 n2@ gives @n1@ (taking @i@ items from the original set)
    --     and @n2@ (dropping @i@ items from the original set))
    splitAt ::
      Int ->
      NESet a ->
      These (NESet a) (NESet a)
    splitAt :: forall a. Int -> NESet a -> These (NESet a) (NESet a)
    splitAt Int
    0 NESet a
    n = NESet a -> These (NESet a) (NESet a)
    forall a b. b -> These a b
    That NESet a
    n
    splitAt Int
    i n :: NESet a
    n@(NESet a
    x Set a
    s0) = case (Set a -> Maybe (NESet a)
    forall a. Set a -> Maybe (NESet a)
    nonEmptySet Set a
    s1, Set a -> Maybe (NESet a)
    forall a. Set a -> Maybe (NESet a)
    nonEmptySet Set a
    s2) of
      (Maybe (NESet a)
    Nothing, Maybe (NESet a)
    Nothing) -> NESet a -> These (NESet a) (NESet a)
    forall a b. a -> These a b
    This (a -> NESet a
    forall a. a -> NESet a
    singleton a
    x)
      (Just NESet a
    _, Maybe (NESet a)
    Nothing) -> NESet a -> These (NESet a) (NESet a)
    forall a b. a -> These a b
    This NESet a
    n
      (Maybe (NESet a)
    Nothing, Just NESet a
    n2) -> NESet a -> NESet a -> These (NESet a) (NESet a)
    forall a b. a -> b -> These a b
    These (a -> NESet a
    forall a. a -> NESet a
    singleton a
    x) NESet a
    n2
      (Just NESet a
    _, Just NESet a
    n2) -> NESet a -> NESet a -> These (NESet a) (NESet a)
    forall a b. a -> b -> These a b
    These (a -> Set a -> NESet a
    forall a. a -> Set a -> NESet a
    insertSetMin a
    x Set a
    s1) NESet a
    n2
      where
        (Set a
    s1, Set a
    s2) = Int -> Set a -> (Set a, Set a)
    forall a. Int -> Set a -> (Set a, Set a)
    S.splitAt (Int
    i Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1) Set a
    s0
    {-# INLINEABLE splitAt #-}

    -- | /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 ::
      Ord b =>
      (a -> b) ->
      NESet a ->
      NESet b
    map :: forall b a. Ord b => (a -> b) -> NESet a -> NESet b
    map a -> b
    f (NESet a
    x0 Set a
    s) =
      NonEmpty b -> NESet b
    forall a. Ord a => NonEmpty a -> NESet a
    fromList
        (NonEmpty b -> NESet b)
    -> (Set a -> NonEmpty b) -> Set a -> NESet b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> b
    f a
    x0 b -> [b] -> NonEmpty b
    forall a. a -> [a] -> NonEmpty a
    :|)
        ([b] -> NonEmpty b) -> (Set a -> [b]) -> Set a -> NonEmpty b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> [b] -> [b]) -> [b] -> Set a -> [b]
    forall a b. (a -> b -> b) -> b -> Set a -> b
    S.foldr (\a
    x [b]
    xs -> a -> b
    f a
    x b -> [b] -> [b]
    forall a. a -> [a] -> [a]
    : [b]
    xs) []
        (Set a -> NESet b) -> Set a -> NESet b
    forall a b. (a -> b) -> a -> b
    $ Set a
    s
    {-# INLINE map #-}

    -- | /O(n)/.
    -- @'mapMonotonic' f s == 'map' f s@, but works only when @f@ is strictly
    -- increasing.  /The precondition is not checked./ Semi-formally, we have:
    --
    -- > and [x < y ==> f x < f y | x <- ls, y <- ls]
    -- >                     ==> mapMonotonic f s == map f s
    -- >     where ls = Data.Foldable.toList s
    mapMonotonic ::
      (a -> b) ->
      NESet a ->
      NESet b
    mapMonotonic :: forall a b. (a -> b) -> NESet a -> NESet b
    mapMonotonic a -> b
    f (NESet a
    x Set a
    s) = b -> Set b -> NESet b
    forall a. a -> Set a -> NESet a
    NESet (a -> b
    f a
    x) ((a -> b) -> Set a -> Set b
    forall a b. (a -> b) -> Set a -> Set b
    S.mapMonotonic a -> b
    f Set a
    s)
    {-# INLINE mapMonotonic #-}

    -- | /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' :: (a -> a -> a) -> NESet a -> a
    foldr1' :: forall a. (a -> a -> a) -> NESet a -> a
    foldr1' a -> a -> a
    f (NESet a
    x Set a
    s) = case Set a -> Maybe (a, Set a)
    forall a. Set a -> Maybe (a, Set a)
    S.maxView Set a
    s of
      Maybe (a, Set a)
    Nothing -> a
    x
      Just (a
    y, Set a
    s') -> let !z :: a
    z = (a -> a -> a) -> a -> Set a -> a
    forall a b. (a -> b -> b) -> b -> Set a -> b
    S.foldr' a -> a -> a
    f a
    y Set a
    s' in a
    x a -> a -> a
    `f` a
    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' :: (a -> a -> a) -> NESet a -> a
    foldl1' :: forall a. (a -> a -> a) -> NESet a -> a
    foldl1' a -> a -> a
    f (NESet a
    x Set a
    s) = (a -> a -> a) -> a -> Set a -> a
    forall a b. (a -> b -> a) -> a -> Set b -> a
    S.foldl' a -> a -> a
    f a
    x Set a
    s
    {-# INLINE foldl1' #-}

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

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

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

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

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

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

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

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

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

    -- ---------------------------
    -- Combining functions
    -- ---------------------------
    --
    -- Code comes from "Data.Set.Internal" from containers, modified slightly
    -- to work with NonEmpty
    --
    -- Copyright   :  (c) Daan Leijen 2002

    {- ORMOLU_DISABLE -}
    combineEq :: Eq a => NonEmpty a -> NonEmpty a
    combineEq :: forall a. Eq a => NonEmpty a -> NonEmpty a
    combineEq (a
    x :| [a]
    xs) = a -> [a] -> NonEmpty a
    forall {t}. Eq t => t -> [t] -> NonEmpty t
    go a
    x [a]
    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)
    #if MIN_VERSION_containers(0,8,0)
          | z == y = go y ys
    #else
          | t
    z t -> t -> Bool
    forall a. Eq a => a -> a -> Bool
    == t
    y = t -> [t] -> NonEmpty t
    go t
    z [t]
    ys
    #endif
          | 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
    {- ORMOLU_ENABLE -}