{-# LANGUAGE BangPatterns        #-}
{-# 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           Data.List.NonEmpty         (NonEmpty(..))
import           Data.Maybe
import           Data.Set                   (Set)
import           Data.Set.NonEmpty.Internal
import           Data.These
import           Prelude hiding             (Foldable(..), filter, map, take, drop, splitAt)
import qualified Data.Foldable              as F
import qualified Data.List.NonEmpty         as NE
import qualified Data.Semigroup.Foldable    as F1
import qualified Data.Set                   as S

-- | /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 $bIsNonEmpty :: forall a. NESet a -> Set a
$mIsNonEmpty :: forall {r} {a}. Set a -> (NESet a -> r) -> ((# #) -> r) -> r
IsNonEmpty n <- (nonEmptySet->Just n)
  where
    IsNonEmpty NESet a
n = 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 $bIsEmpty :: forall a. Set a
$mIsEmpty :: forall {r} {a}. Set a -> ((# #) -> r) -> ((# #) -> r) -> r
IsEmpty <- (S.null->True)
  where
    IsEmpty = 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 = forall r a. r -> (NESet a -> r) -> Set a -> r
withNonEmpty forall {a}. a
e forall a. a -> a
id
  where
    e :: a
e = 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 = forall r a. r -> (NESet a -> r) -> Set a -> r
withNonEmpty (forall a. a -> NESet a
singleton a
x) (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 = 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 = forall r a. r -> (NESet a -> r) -> Set a -> r
withNonEmpty (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) = forall a. a -> Set a -> NESet a
NESet a
x0 forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. a -> Set a -> Set a
insertMaxSet a
x 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 = forall a. NonEmpty a -> NESet a
fromDistinctAscList forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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) = forall a. a -> Set a -> NESet a
insertSetMin a
x
                              forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. [a] -> Set a
S.fromDistinctAscList
                              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 = forall a. NonEmpty a -> NESet a
fromDistinctDescList forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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) = forall a. a -> Set a -> NESet a
insertSetMax a
x
                               forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. [a] -> Set a
S.fromDistinctDescList
                               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 forall a. Set a -> Maybe (NESet a)
nonEmptySet Set (NESet a)
p1 of
    -- s0 was empty originally
    Maybe (NESet (NESet a))
Nothing -> forall a. a -> NESet a
singleton (forall a. a -> NESet a
singleton a
x)
    -- s1 was not empty originally
    Just NESet (NESet a)
p2 -> forall a b. (a -> b) -> NESet a -> NESet b
mapMonotonic (forall a. a -> Set a -> NESet a
insertSetMin a
x) NESet (Set a)
p0
       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) = forall a. Set a -> NESet a
forSure forall a b. (a -> b) -> a -> b
$ forall a. Set a -> Set (Set a)
powerSetSet Set a
s0
    p1 :: Set (NESet a)
    p1 :: Set (NESet a)
p1 = forall a b. (a -> b) -> Set a -> Set b
S.mapMonotonic 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 = forall r a. r -> (NESet a -> r) -> Set a -> r
withNonEmpty (forall a. [Char] -> a
errorWithoutStackTrace [Char]
"NESet.powerSet: internal error")
                        forall a. a -> a
id
{-# INLINABLE 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 forall a. Ord a => a -> a -> Ordering
compare a
x a
x0 of
    Ordering
LT -> forall a. a -> Set a -> NESet a
NESet a
x  forall a b. (a -> b) -> a -> b
$ forall a. NESet a -> Set a
toSet NESet a
n
    Ordering
EQ -> forall a. a -> Set a -> NESet a
NESet a
x  Set a
s
    Ordering
GT -> forall a. a -> Set a -> NESet a
NESet a
x0 forall a b. (a -> b) -> a -> b
$ 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 forall a. Ord a => a -> a -> Ordering
compare a
x a
x0 of
    Ordering
LT -> forall a. NESet a -> Set a
toSet NESet a
n
    Ordering
EQ -> Set a
s
    Ordering
GT -> forall a. a -> Set a -> Set a
insertMinSet a
x0 forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Ord a => a -> Set a -> Set a
S.delete a
x 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 forall a. Ord a => a -> a -> Ordering
compare a
x a
x0 of
    Ordering
LT -> Bool
False
    Ordering
EQ -> Bool
True
    Ordering
GT -> 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 forall a. Ord a => a -> a -> Ordering
compare a
x a
x0 of
    Ordering
LT -> Bool
True
    Ordering
EQ -> Bool
False
    Ordering
GT -> 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 forall a. Ord a => a -> a -> Ordering
compare a
x a
x0 of
    Ordering
LT -> forall a. Maybe a
Nothing
    Ordering
EQ -> forall a. Maybe a
Nothing
    Ordering
GT -> forall a. Ord a => a -> Set a -> Maybe a
S.lookupLT a
x Set a
s forall (f :: * -> *) a. Alternative f => f a -> f a -> f 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 forall a. Ord a => a -> a -> Ordering
compare a
x a
x0 of
    Ordering
LT -> forall a. a -> Maybe a
Just a
x0
    Ordering
EQ -> forall a. Set a -> Maybe a
S.lookupMin Set a
s
    Ordering
GT -> 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 forall a. Ord a => a -> a -> Ordering
compare a
x a
x0 of
    Ordering
LT -> forall a. Maybe a
Nothing
    Ordering
EQ -> forall a. a -> Maybe a
Just a
x0
    Ordering
GT -> forall a. Ord a => a -> Set a -> Maybe a
S.lookupLE a
x Set a
s forall (f :: * -> *) a. Alternative f => f a -> f a -> f 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 forall a. Ord a => a -> a -> Ordering
compare a
x a
x0 of
    Ordering
LT -> forall a. a -> Maybe a
Just a
x0
    Ordering
EQ -> forall a. a -> Maybe a
Just a
x0
    Ordering
GT -> 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) (forall a. NESet a -> Set a
toSet->Set a
s1) = a
x forall a. Ord a => a -> Set a -> Bool
`S.member` Set a
s1
                                   Bool -> Bool -> Bool
&& Set a
s0 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 = forall a. Set a -> Int
S.size (forall a. NESet a -> Set a
nesSet NESet a
s0) forall a. Ord a => a -> a -> Bool
< forall a. Set a -> Int
S.size (forall a. NESet a -> Set a
nesSet NESet a
s1)
                      Bool -> Bool -> Bool
&& NESet a
s0 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 forall a. Ord a => a -> a -> Ordering
compare a
x1 a
x2 of
    -- x1 is not in n2
    Ordering
LT -> Set a
s1 forall a. Ord a => Set a -> Set a -> Bool
`disjointSet` 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 -> forall a. NESet a -> Set a
toSet NESet a
n1 forall a. Ord a => Set a -> Set a -> Bool
`disjointSet` 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 forall a. Ord a => a -> a -> Ordering
compare a
x1 a
x2 of
    -- x1 is not in n2, so cannot be deleted
    Ordering
LT -> forall a. a -> Set a -> Set a
insertMinSet a
x1 forall a b. (a -> b) -> a -> b
$ Set a
s1 forall a. Ord a => Set a -> Set a -> Set a
`S.difference` forall a. NESet a -> Set a
toSet NESet a
n2
    -- x2 deletes x1, and only x1
    Ordering
EQ -> Set a
s1 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 -> forall a. NESet a -> Set a
toSet NESet a
n1 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
(\\) = 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 forall a. Ord a => a -> a -> Ordering
compare a
x1 a
x2 of
    -- x1 is not in n2
    Ordering
LT -> Set a
s1 forall a. Ord a => Set a -> Set a -> Set a
`S.intersection` forall a. NESet a -> Set a
toSet NESet a
n2
    -- x1 and x2 are a part of the result
    Ordering
EQ -> forall a. a -> Set a -> Set a
insertMinSet a
x1 forall a b. (a -> b) -> a -> b
$ Set a
s1 forall a. Ord a => Set a -> Set a -> Set a
`S.intersection` Set a
s2
    -- x2 is not in n1
    Ordering
GT -> forall a. NESet a -> Set a
toSet NESet a
n1 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 = forall a. MergeNESet a -> NESet a
getMergeNESet
                       forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (t :: * -> *) m a.
(Foldable1 t, Semigroup m) =>
(a -> m) -> t a -> m
F1.foldMap1 (\a
x -> forall a. NESet a -> MergeNESet a
MergeNESet forall a b. (a -> b) -> a -> b
$ forall a b. (a -> b) -> NESet a -> NESet b
mapMonotonic (a
x,) NESet b
n2)
                       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 = forall a. a -> Set a -> NESet a
NESet (forall a b. a -> Either a b
Left a
x1)
                                       (Set a
s1 forall a b. Set a -> Set b -> Set (Either a b)
`disjointUnionSet` 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       = forall a. a -> Set a -> Set a
insertMinSet a
x forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. (a -> Bool) -> Set a -> Set a
S.filter a -> Bool
f forall a b. (a -> b) -> a -> b
$ Set a
s1
    | Bool
otherwise = 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       = forall a. a -> Set a -> Set a
insertMinSet a
x forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. (a -> Bool) -> Set a -> Set a
S.takeWhileAntitone a -> Bool
f forall a b. (a -> b) -> a -> b
$ Set a
s
    | Bool
otherwise = 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       = forall a. (a -> Bool) -> Set a -> Set a
S.dropWhileAntitone a -> Bool
f Set a
s
    | Bool
otherwise = 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 (forall a. Set a -> Maybe (NESet a)
nonEmptySet Set a
s1, forall a. Set a -> Maybe (NESet a)
nonEmptySet Set a
s2) of
        (Maybe (NESet a)
Nothing, Maybe (NESet a)
Nothing) -> forall a b. a -> These a b
This  NESet a
n
        (Just NESet a
_ , Maybe (NESet a)
Nothing) -> forall a b. a -> These a b
This  NESet a
n
        (Maybe (NESet a)
Nothing, Just NESet a
n2) -> forall a b. a -> b -> These a b
These (forall a. a -> NESet a
singleton a
x)       NESet a
n2
        (Just NESet a
_ , Just NESet a
n2) -> forall a b. a -> b -> These a b
These (forall a. a -> Set a -> NESet a
insertSetMin a
x Set a
s1) NESet a
n2
    | Bool
otherwise = forall a b. b -> These a b
That NESet a
n
  where
    (Set a
s1, Set a
s2) = forall a. (a -> Bool) -> Set a -> (Set a, Set a)
S.spanAntitone a -> Bool
f Set a
s0
{-# INLINABLE 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 (forall a. Set a -> Maybe (NESet a)
nonEmptySet Set a
s1, 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       -> forall a b. a -> These a b
This  NESet a
n
      | Bool
otherwise -> forall a b. b -> These a b
That                      NESet a
n
    (Just NESet a
n1, Maybe (NESet a)
Nothing)
      | a -> Bool
f a
x       -> forall a b. a -> These a b
This  NESet a
n
      | Bool
otherwise -> forall a b. a -> b -> These a b
These NESet a
n1                  (forall a. a -> NESet a
singleton a
x)
    (Maybe (NESet a)
Nothing, Just NESet a
n2)
      | a -> Bool
f a
x       -> forall a b. a -> b -> These a b
These (forall a. a -> NESet a
singleton a
x)       NESet a
n2
      | Bool
otherwise -> forall a b. b -> These a b
That                      NESet a
n
    (Just NESet a
n1, Just NESet a
n2)
      | a -> Bool
f a
x       -> forall a b. a -> b -> These a b
These (forall a. a -> Set a -> NESet a
insertSetMin a
x Set a
s1) NESet a
n2
      | Bool
otherwise -> forall a b. a -> b -> These a b
These NESet a
n1                  (forall a. a -> Set a -> NESet a
insertSetMin a
x Set a
s2)
  where
    (Set a
s1, Set a
s2) = forall a. (a -> Bool) -> Set a -> (Set a, Set a)
S.partition a -> Bool
f Set a
s0
{-# INLINABLE 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 forall a. Ord a => a -> a -> Ordering
compare a
x a
x0 of
    Ordering
LT -> forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$ forall a b. b -> These a b
That NESet a
n
    Ordering
EQ -> forall a b. b -> These a b
That forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall a. Set a -> Maybe (NESet a)
nonEmptySet Set a
s0
    Ordering
GT -> case (forall a. Set a -> Maybe (NESet a)
nonEmptySet Set a
s1, forall a. Set a -> Maybe (NESet a)
nonEmptySet Set a
s2) of
      (Maybe (NESet a)
Nothing, Maybe (NESet a)
Nothing) -> forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$ forall a b. a -> These a b
This  (forall a. a -> NESet a
singleton a
x0)
      (Just NESet a
_ , Maybe (NESet a)
Nothing) -> forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$ forall a b. a -> These a b
This  (forall a. a -> Set a -> NESet a
insertSetMin a
x0 Set a
s1)
      (Maybe (NESet a)
Nothing, Just NESet a
n2) -> forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$ forall a b. a -> b -> These a b
These (forall a. a -> NESet a
singleton a
x0)       NESet a
n2
      (Just NESet a
_ , Just NESet a
n2) -> forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$ forall a b. a -> b -> These a b
These (forall a. a -> Set a -> NESet a
insertSetMin a
x0 Set a
s1) NESet a
n2
  where
    (Set a
s1, Set a
s2) = forall a. Ord a => a -> Set a -> (Set a, Set a)
S.split a
x Set a
s0
{-# INLINABLE 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 forall a. Ord a => a -> a -> Ordering
compare a
x a
x0 of
    Ordering
LT -> (Bool
False, forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$ forall a b. b -> These a b
That NESet a
n)
    Ordering
EQ -> (Bool
True , forall a b. b -> These a b
That forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall a. Set a -> Maybe (NESet a)
nonEmptySet Set a
s0)
    Ordering
GT -> (Bool
mem  ,) forall a b. (a -> b) -> a -> b
$ case (forall a. Set a -> Maybe (NESet a)
nonEmptySet Set a
s1, forall a. Set a -> Maybe (NESet a)
nonEmptySet Set a
s2) of
      (Maybe (NESet a)
Nothing, Maybe (NESet a)
Nothing) -> forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$ forall a b. a -> These a b
This  (forall a. a -> NESet a
singleton a
x0)
      (Just NESet a
_ , Maybe (NESet a)
Nothing) -> forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$ forall a b. a -> These a b
This  (forall a. a -> Set a -> NESet a
insertSetMin a
x0 Set a
s1)
      (Maybe (NESet a)
Nothing, Just NESet a
n2) -> forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$ forall a b. a -> b -> These a b
These (forall a. a -> NESet a
singleton a
x0)       NESet a
n2
      (Just NESet a
_ , Just NESet a
n2) -> forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$ forall a b. a -> b -> These a b
These (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) = forall a. Ord a => a -> Set a -> (Set a, Bool, Set a)
S.splitMember a
x Set a
s0
{-# INLINABLE 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) = forall a. a -> NESet a
singleton a
x
                     forall a. a -> [a] -> NonEmpty a
:| forall a b. (a -> Maybe b) -> [a] -> [b]
mapMaybe forall a. Set a -> Maybe (NESet a)
nonEmptySet (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 forall a. Ord a => a -> a -> Ordering
compare a
x a
x0 of
    Ordering
LT -> forall a. Maybe a
Nothing
    Ordering
EQ -> forall a. a -> Maybe a
Just Int
0
    Ordering
GT -> (forall a. Num a => a -> a -> a
+ Int
1) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> 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 = forall a. a -> Maybe a -> a
fromMaybe forall {a}. a
e forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Ord a => a -> NESet a -> Maybe Int
lookupIndex a
k
  where
    e :: a
e = 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) = forall a. Int -> Set a -> a
S.elemAt (Int
i 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) = forall a. a -> Set a -> Set a
insertMinSet a
x forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Int -> Set a -> Set a
S.deleteAt (Int
i forall a. Num a => a -> a -> a
- Int
1) forall a b. (a -> b) -> a -> b
$ Set a
s
{-# INLINABLE 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
_) = forall a. Set a
S.empty
take Int
i (NESet a
x Set a
s) = forall a. a -> Set a -> Set a
insertMinSet a
x forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Int -> Set a -> Set a
S.take (Int
i forall a. Num a => a -> a -> a
- Int
1) forall a b. (a -> b) -> a -> b
$ Set a
s
{-# INLINABLE 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           = forall a. NESet a -> Set a
toSet NESet a
n
drop Int
n (NESet a
_ Set a
s) = forall a. Int -> Set a -> Set a
S.drop (Int
n forall a. Num a => a -> a -> a
- Int
1) Set a
s
{-# INLINABLE 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              = 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 (forall a. Set a -> Maybe (NESet a)
nonEmptySet Set a
s1, forall a. Set a -> Maybe (NESet a)
nonEmptySet Set a
s2) of
    (Maybe (NESet a)
Nothing, Maybe (NESet a)
Nothing) -> forall a b. a -> These a b
This  (forall a. a -> NESet a
singleton a
x)
    (Just NESet a
_ , Maybe (NESet a)
Nothing) -> forall a b. a -> These a b
This  NESet a
n
    (Maybe (NESet a)
Nothing, Just NESet a
n2) -> forall a b. a -> b -> These a b
These (forall a. a -> NESet a
singleton a
x)       NESet a
n2
    (Just NESet a
_ , Just NESet a
n2) -> forall a b. a -> b -> These a b
These (forall a. a -> Set a -> NESet a
insertSetMin a
x Set a
s1) NESet a
n2
  where
    (Set a
s1, Set a
s2) = forall a. Int -> Set a -> (Set a, Set a)
S.splitAt (Int
i forall a. Num a => a -> a -> a
- Int
1) Set a
s0
{-# INLINABLE 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) = forall a. Ord a => NonEmpty a -> NESet a
fromList
                   forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b
f a
x0 forall a. a -> [a] -> NonEmpty a
:|)
                   forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (a -> b -> b) -> b -> Set a -> b
S.foldr (\a
x [b]
xs -> a -> b
f a
x forall a. a -> [a] -> [a]
: [b]
xs) []
                   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) = forall a. a -> Set a -> NESet a
NESet (a -> b
f a
x) (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 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 = 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) = 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) = forall a. a -> Maybe a -> a
fromMaybe a
x forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Set a -> Maybe a
S.lookupMax 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 forall a. Set a -> Maybe (a, Set a)
S.maxView Set a
s of
    Maybe (a, Set a)
Nothing      -> forall a. Set a
S.empty
    Just (a
_, Set a
s') -> 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) = forall b a. b -> (a -> b) -> Maybe a -> b
maybe (a
x, forall a. Set a
S.empty) (forall (p :: * -> * -> *) b c a.
Bifunctor p =>
(b -> c) -> p a b -> p a c
second (forall a. a -> Set a -> Set a
insertMinSet a
x))
                          forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Set a -> Maybe (a, Set a)
S.maxView
                          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 = 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 = 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) = forall a b. (a -> b -> a) -> a -> Set b -> a
S.foldl' (forall a b c. (a -> b -> c) -> b -> a -> c
flip forall a. a -> NonEmpty a -> NonEmpty a
(NE.<|)) (a
x 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

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