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

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

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

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

  -- * Insertion
  insert,

  -- * Deletion
  delete,

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

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

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

  -- * Map
  map,

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

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

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

  -- * Conversion

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

  -- * Debugging
  valid,
) where

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

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

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

{-# COMPLETE IsNonEmpty, IsEmpty #-}

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

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

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

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

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

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

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

-- | /O(log n)/. Insert an element in a set.
-- If the set already contains an element equal to the given value,
-- it is replaced with the new value.
insert :: Key -> NEIntSet -> NEIntSet
insert :: Key -> NEIntSet -> NEIntSet
insert Key
x n :: NEIntSet
n@(NEIntSet Key
x0 IntSet
s) = case Key -> Key -> Ordering
forall a. Ord a => a -> a -> Ordering
compare Key
x Key
x0 of
  Ordering
LT -> Key -> IntSet -> NEIntSet
NEIntSet Key
x (IntSet -> NEIntSet) -> IntSet -> NEIntSet
forall a b. (a -> b) -> a -> b
$ NEIntSet -> IntSet
toSet NEIntSet
n
  Ordering
EQ -> Key -> IntSet -> NEIntSet
NEIntSet Key
x IntSet
s
  Ordering
GT -> Key -> IntSet -> NEIntSet
NEIntSet Key
x0 (IntSet -> NEIntSet) -> IntSet -> NEIntSet
forall a b. (a -> b) -> a -> b
$ Key -> IntSet -> IntSet
S.insert Key
x IntSet
s
{-# INLINE insert #-}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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