-- |
--   Module      :  Data.Edison.Coll.UnbalancedSet
--   Copyright   :  Copyright (c) 1998-1999, 2008 Chris Okasaki
--   License     :  MIT; see COPYRIGHT file for terms and conditions
--
--   Maintainer  :  robdockins AT fastmail DOT fm
--   Stability   :  stable
--   Portability :  GHC, Hugs (MPTC and FD)
--
--   Sets implemented as unbalanced binary search trees.

module Data.Edison.Coll.UnbalancedSet (
    -- * Set type
    Set, -- instance of Coll/CollX, OrdColl/OrdCollX, Set/SetX, OrdSet/OrdSetX

    -- * CollX operations
    empty,singleton,fromSeq,insert,insertSeq,union,unionSeq,delete,deleteAll,
    deleteSeq,null,size,member,count,strict,structuralInvariant,

    -- * Coll operations
    toSeq,lookup,lookupM,lookupAll,lookupWithDefault,fold,fold',
    fold1,fold1',filter,partition,strictWith,

    -- * OrdCollX operations
    deleteMin,deleteMax,unsafeInsertMin,unsafeInsertMax,unsafeFromOrdSeq,
    unsafeAppend,filterLT,filterLE,filterGT,filterGE,partitionLT_GE,
    partitionLE_GT,partitionLT_GT,

    -- * OrdColl operations
    minView,minElem,maxView,maxElem,foldr,foldr',foldl,foldl',
    foldr1,foldr1',foldl1,foldl1',toOrdSeq,unsafeMapMonotonic,

    -- * SetX operations
    intersection,difference,symmetricDifference,properSubset,subset,

    -- * Set operations
    fromSeqWith,insertWith,insertSeqWith,unionl,unionr,unionWith,
    unionSeqWith,intersectionWith,

    -- * Documentation
    moduleName
) where

import Prelude hiding (null,foldr,foldl,foldr1,foldl1,foldl',lookup,filter)
import qualified Prelude
import qualified Control.Monad.Fail as Fail
import qualified Data.Edison.Coll as C
import qualified Data.Edison.Seq as S
import Data.Edison.Coll.Defaults
import Data.Monoid
import Data.Semigroup as SG
import Test.QuickCheck

-- signatures for exported functions
moduleName :: String
empty      :: Set a
singleton  :: a -> Set a
fromSeq    :: (Ord a,S.Sequence seq) => seq a -> Set a
insert     :: Ord a => a -> Set a -> Set a
insertSeq  :: (Ord a,S.Sequence seq) => seq a -> Set a -> Set a
union      :: Ord a => Set a -> Set a -> Set a
unionSeq   :: (Ord a,S.Sequence seq) => seq (Set a) -> Set a
delete     :: Ord a => a -> Set a -> Set a
deleteAll  :: Ord a => a -> Set a -> Set a
deleteSeq  :: (Ord a,S.Sequence seq) => seq a -> Set a -> Set a
null       :: Set a -> Bool
size       :: Set a -> Int
member     :: Ord a => a -> Set a -> Bool
count      :: Ord a => a -> Set a -> Int
strict     :: Set a -> Set a

toSeq      :: (Ord a,S.Sequence seq) => Set a -> seq a
lookup     :: Ord a => a -> Set a -> a
lookupM    :: (Ord a, Fail.MonadFail m) => a -> Set a -> m a
lookupAll  :: (Ord a,S.Sequence seq) => a -> Set a -> seq a
lookupWithDefault :: Ord a => a -> a -> Set a -> a
fold       :: (a -> b -> b) -> b -> Set a -> b
fold1      :: (a -> a -> a) -> Set a -> a
fold'      :: (a -> b -> b) -> b -> Set a -> b
fold1'     :: (a -> a -> a) -> Set a -> a
filter     :: Ord a => (a -> Bool) -> Set a -> Set a
partition  :: Ord a => (a -> Bool) -> Set a -> (Set a, Set a)
strictWith :: (a -> b) -> Set a -> Set a

deleteMin        :: Ord a => Set a -> Set a
deleteMax        :: Ord a => Set a -> Set a
unsafeInsertMin  :: Ord a => a -> Set a -> Set a
unsafeInsertMax  :: Ord a => a -> Set a -> Set a
unsafeFromOrdSeq :: (Ord a,S.Sequence seq) => seq a -> Set a
unsafeAppend     :: Ord a => Set a -> Set a -> Set a
filterLT         :: Ord a => a -> Set a -> Set a
filterLE         :: Ord a => a -> Set a -> Set a
filterGT         :: Ord a => a -> Set a -> Set a
filterGE         :: Ord a => a -> Set a -> Set a
partitionLT_GE   :: Ord a => a -> Set a -> (Set a, Set a)
partitionLE_GT   :: Ord a => a -> Set a -> (Set a, Set a)
partitionLT_GT   :: Ord a => a -> Set a -> (Set a, Set a)

minView       :: (Fail.MonadFail m) => Set a -> m (a, Set a)
minElem       :: Set a -> a
maxView       :: (Fail.MonadFail m) => Set a -> m (a, Set a)
maxElem       :: Set a -> a
foldr         :: (a -> b -> b) -> b -> Set a -> b
foldl         :: (b -> a -> b) -> b -> Set a -> b
foldr1        :: (a -> a -> a) -> Set a -> a
foldl1        :: (a -> a -> a) -> Set a -> a
foldr'        :: (a -> b -> b) -> b -> Set a -> b
foldl'        :: (b -> a -> b) -> b -> Set a -> b
foldr1'       :: (a -> a -> a) -> Set a -> a
foldl1'       :: (a -> a -> a) -> Set a -> a
toOrdSeq      :: (Ord a,S.Sequence seq) => Set a -> seq a

intersection  :: Ord a => Set a -> Set a -> Set a
difference    :: Ord a => Set a -> Set a -> Set a
symmetricDifference :: Ord a => Set a -> Set a -> Set a
properSubset  :: Ord a => Set a -> Set a -> Bool
subset        :: Ord a => Set a -> Set a -> Bool

fromSeqWith   :: (Ord a,S.Sequence seq) => (a -> a -> a) -> seq a -> Set a
insertWith    :: Ord a => (a -> a -> a) -> a -> Set a -> Set a
insertSeqWith :: (Ord a,S.Sequence seq) => (a -> a -> a) -> seq a -> Set a -> Set a
unionl       :: Ord a => Set a -> Set a -> Set a
unionr       :: Ord a => Set a -> Set a -> Set a
unionWith    :: Ord a => (a -> a -> a) -> Set a -> Set a -> Set a
unionSeqWith :: (Ord a,S.Sequence seq) => (a -> a -> a) -> seq (Set a) -> Set a
intersectionWith :: Ord a => (a -> a -> a) -> Set a -> Set a -> Set a
unsafeMapMonotonic :: Ord a => (a -> a) -> Set a -> Set a

moduleName :: String
moduleName = String
"Data.Edison.Coll.UnbalancedSet"

data Set a = E | T (Set a) a (Set a)

-- invariants:
--   * Binary Search Tree order
structuralInvariant :: Ord a => Set a -> Bool
structuralInvariant :: forall a. Ord a => Set a -> Bool
structuralInvariant Set a
t = Maybe a -> Maybe a -> Set a -> Bool
forall {a}. Ord a => Maybe a -> Maybe a -> Set a -> Bool
bounded Maybe a
forall a. Maybe a
Nothing Maybe a
forall a. Maybe a
Nothing Set a
t
   where bounded :: Maybe a -> Maybe a -> Set a -> Bool
bounded Maybe a
_ Maybe a
_ Set a
E = Bool
True
         bounded Maybe a
lo Maybe a
hi (T Set a
l a
x Set a
r)  = Maybe a -> a -> Bool
forall {a}. Ord a => Maybe a -> a -> Bool
cmp_l Maybe a
lo a
x
                                 Bool -> Bool -> Bool
&& a -> Maybe a -> Bool
forall {a}. Ord a => a -> Maybe a -> Bool
cmp_r a
x Maybe a
hi
                                 Bool -> Bool -> Bool
&& Maybe a -> Maybe a -> Set a -> Bool
bounded Maybe a
lo (a -> Maybe a
forall a. a -> Maybe a
Just a
x) Set a
l
                                 Bool -> Bool -> Bool
&& Maybe a -> Maybe a -> Set a -> Bool
bounded (a -> Maybe a
forall a. a -> Maybe a
Just a
x) Maybe a
hi Set a
r

         cmp_l :: Maybe a -> a -> Bool
cmp_l Maybe a
Nothing  a
_ = Bool
True
         cmp_l (Just a
x) a
y = a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
y

         cmp_r :: a -> Maybe a -> Bool
cmp_r a
_ Maybe a
Nothing  = Bool
True
         cmp_r a
x (Just a
y) = a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
y



empty :: forall a. Set a
empty = Set a
forall a. Set a
E
singleton :: forall a. a -> Set a
singleton a
x = Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
T Set a
forall a. Set a
E a
x Set a
forall a. Set a
E

insertWith :: forall a. Ord a => (a -> a -> a) -> a -> Set a -> Set a
insertWith a -> a -> a
c a
x = Set a -> Set a
ins
  where ins :: Set a -> Set a
ins Set a
E = Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
T Set a
forall a. Set a
E a
x Set a
forall a. Set a
E
        ins (T Set a
a a
y Set a
b) =
          case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
x a
y of
            Ordering
LT -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
T (Set a -> Set a
ins Set a
a) a
y Set a
b
            Ordering
EQ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
T Set a
a (a -> a -> a
c a
x a
y) Set a
b
            Ordering
GT -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
T Set a
a a
y (Set a -> Set a
ins Set a
b)

delete :: forall a. Ord a => a -> Set a -> Set a
delete a
_ Set a
E = Set a
forall a. Set a
E
delete a
x (T Set a
a a
y Set a
b) =
  case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
x a
y of
    Ordering
LT -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
T (a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
delete a
x Set a
a) a
y Set a
b
    Ordering
EQ -> Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
unsafeAppend Set a
a Set a
b
    Ordering
GT -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
T Set a
a a
y (a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
delete a
x Set a
b)

null :: forall a. Set a -> Bool
null Set a
E = Bool
True
null (T Set a
_ a
_ Set a
_) = Bool
False

size :: forall a. Set a -> Int
size Set a
t = Set a -> Int -> Int
forall {t} {a}. Num t => Set a -> t -> t
sz Set a
t Int
0
  where sz :: Set a -> t -> t
sz Set a
E t
i = t
i
        sz (T Set a
a a
_ Set a
b) t
i = Set a -> t -> t
sz Set a
a (Set a -> t -> t
sz Set a
b (t
it -> t -> t
forall a. Num a => a -> a -> a
+t
1))

member :: forall a. Ord a => a -> Set a -> Bool
member a
_ Set a
E = Bool
False
member a
x (T Set a
a a
y Set a
b) =
  case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
x a
y of
    Ordering
LT -> a -> Set a -> Bool
forall a. Ord a => a -> Set a -> Bool
member a
x Set a
a
    Ordering
EQ -> Bool
True
    Ordering
GT -> a -> Set a -> Bool
forall a. Ord a => a -> Set a -> Bool
member a
x Set a
b

lookupM :: forall a (m :: * -> *). (Ord a, MonadFail m) => a -> Set a -> m a
lookupM a
_ Set a
E = String -> m a
forall a. String -> m a
forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"UnbalancedSet.lookupM: XXX"
lookupM a
x (T Set a
a a
y Set a
b) =
  case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
x a
y of
    Ordering
LT -> a -> Set a -> m a
forall a (m :: * -> *). (Ord a, MonadFail m) => a -> Set a -> m a
lookupM a
x Set a
a
    Ordering
EQ -> a -> m a
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return a
y
    Ordering
GT -> a -> Set a -> m a
forall a (m :: * -> *). (Ord a, MonadFail m) => a -> Set a -> m a
lookupM a
x Set a
b

fold :: forall a b. (a -> b -> b) -> b -> Set a -> b
fold a -> b -> b
_ b
e Set a
E = b
e
fold a -> b -> b
f b
e (T Set a
a a
x Set a
b) = a -> b -> b
f a
x ((a -> b -> b) -> b -> Set a -> b
forall a b. (a -> b -> b) -> b -> Set a -> b
fold a -> b -> b
f ((a -> b -> b) -> b -> Set a -> b
forall a b. (a -> b -> b) -> b -> Set a -> b
fold a -> b -> b
f b
e Set a
a) Set a
b)

fold' :: forall a b. (a -> b -> b) -> b -> Set a -> b
fold' a -> b -> b
_ b
e Set a
E = b
e
fold' a -> b -> b
f b
e (T Set a
a a
x Set a
b) = b
e b -> b -> b
forall a b. a -> b -> b
`seq` a -> b -> b
f a
x (b -> b) -> b -> b
forall a b. (a -> b) -> a -> b
$! ((a -> b -> b) -> b -> Set a -> b
forall a b. (a -> b -> b) -> b -> Set a -> b
fold' a -> b -> b
f ((a -> b -> b) -> b -> Set a -> b
forall a b. (a -> b -> b) -> b -> Set a -> b
fold' a -> b -> b
f b
e Set a
a) Set a
b)

fold1 :: forall a. (a -> a -> a) -> Set a -> a
fold1 a -> a -> a
_ Set a
E = String -> a
forall a. HasCallStack => String -> a
error String
"UnbalancedSet.fold1: empty collection"
fold1 a -> a -> a
f (T Set a
a a
x Set a
b) = (a -> a -> a) -> a -> Set a -> a
forall a b. (a -> b -> b) -> b -> Set a -> b
fold a -> a -> a
f ((a -> a -> a) -> a -> Set a -> a
forall a b. (a -> b -> b) -> b -> Set a -> b
fold a -> a -> a
f a
x Set a
a) Set a
b

fold1' :: forall a. (a -> a -> a) -> Set a -> a
fold1' a -> a -> a
_ Set a
E = String -> a
forall a. HasCallStack => String -> a
error String
"UnbalancedSet.fold1': empty collection"
fold1' a -> a -> a
f (T Set a
a a
x Set a
b) = (a -> a -> a) -> a -> Set a -> a
forall a b. (a -> b -> b) -> b -> Set a -> b
fold' a -> a -> a
f ((a -> a -> a) -> a -> Set a -> a
forall a b. (a -> b -> b) -> b -> Set a -> b
fold' a -> a -> a
f a
x Set a
a) Set a
b

deleteMin :: forall a. Ord a => Set a -> Set a
deleteMin Set a
E = Set a
forall a. Set a
E
deleteMin (T Set a
E a
_ Set a
b) = Set a
b
deleteMin (T Set a
a a
x Set a
b) = Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
T (Set a -> Set a
forall a. Ord a => Set a -> Set a
deleteMin Set a
a) a
x Set a
b

deleteMax :: forall a. Ord a => Set a -> Set a
deleteMax Set a
E = Set a
forall a. Set a
E
deleteMax (T Set a
a a
_ Set a
E) = Set a
a
deleteMax (T Set a
a a
x Set a
b) = Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
T Set a
a a
x (Set a -> Set a
forall a. Ord a => Set a -> Set a
deleteMax Set a
b)

unsafeInsertMin :: forall a. Ord a => a -> Set a -> Set a
unsafeInsertMin a
x Set a
t = Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
T Set a
forall a. Set a
E a
x Set a
t
unsafeInsertMax :: forall a. Ord a => a -> Set a -> Set a
unsafeInsertMax a
x Set a
t = Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
T Set a
t a
x Set a
forall a. Set a
E

unsafeFromOrdSeq :: forall a (seq :: * -> *). (Ord a, Sequence seq) => seq a -> Set a
unsafeFromOrdSeq seq a
xs = (Set a, seq a) -> Set a
forall a b. (a, b) -> a
fst (seq a -> Int -> (Set a, seq a)
forall {a} {s :: * -> *} {a}.
(Integral a, Sequence s) =>
s a -> a -> (Set a, s a)
ins seq a
xs (seq a -> Int
forall a. seq a -> Int
forall (s :: * -> *) a. Sequence s => s a -> Int
S.size seq a
xs))
  where ins :: s a -> a -> (Set a, s a)
ins s a
ys a
0 = (Set a
forall a. Set a
E,s a
ys)
        ins s a
ys a
n = let m :: a
m = a
n a -> a -> a
forall a. Integral a => a -> a -> a
`div` a
2
                       (Set a
a,s a
ys') = s a -> a -> (Set a, s a)
ins s a
ys a
m
                       Just (a
y,s a
ys'') = s a -> Maybe (a, s a)
forall (s :: * -> *) (m :: * -> *) a.
(Sequence s, MonadFail m) =>
s a -> m (a, s a)
forall (m :: * -> *) a. MonadFail m => s a -> m (a, s a)
S.lview s a
ys'
                       (Set a
b,s a
ys''') = s a -> a -> (Set a, s a)
ins s a
ys'' (a
n a -> a -> a
forall a. Num a => a -> a -> a
- a
m a -> a -> a
forall a. Num a => a -> a -> a
- a
1)
                   in (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
T Set a
a a
y Set a
b,s a
ys''')

unsafeAppend :: forall a. Ord a => Set a -> Set a -> Set a
unsafeAppend Set a
a Set a
b = case Set a -> Maybe (a, Set a)
forall (m :: * -> *) a. MonadFail m => Set a -> m (a, Set a)
minView Set a
b of
                     Maybe (a, Set a)
Nothing -> Set a
a
                     Just (a
x,Set a
b') -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
T Set a
a a
x Set a
b'

filterLT :: forall a. Ord a => a -> Set a -> Set a
filterLT a
_ Set a
E = Set a
forall a. Set a
E
filterLT a
y (T Set a
a a
x Set a
b) =
  case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
x a
y of
    Ordering
LT -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
T Set a
a a
x (a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
filterLT a
y Set a
b)
    Ordering
EQ -> Set a
a
    Ordering
GT -> a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
filterLT a
y Set a
a

filterLE :: forall a. Ord a => a -> Set a -> Set a
filterLE a
_ Set a
E = Set a
forall a. Set a
E
filterLE a
y (T Set a
a a
x Set a
b) =
  case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
x a
y of
    Ordering
LT -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
T Set a
a a
x (a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
filterLE a
y Set a
b)
    Ordering
EQ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
T Set a
a a
x Set a
forall a. Set a
E
    Ordering
GT -> a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
filterLE a
y Set a
a

filterGT :: forall a. Ord a => a -> Set a -> Set a
filterGT a
_ Set a
E = Set a
forall a. Set a
E
filterGT a
y (T Set a
a a
x Set a
b) =
  case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
x a
y of
    Ordering
LT -> a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
filterGT a
y Set a
b
    Ordering
EQ -> Set a
b
    Ordering
GT -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
T (a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
filterGT a
y Set a
a) a
x Set a
b

filterGE :: forall a. Ord a => a -> Set a -> Set a
filterGE a
_ Set a
E = Set a
forall a. Set a
E
filterGE a
y (T Set a
a a
x Set a
b) =
  case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
x a
y of
    Ordering
LT -> a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
filterGE a
y Set a
b
    Ordering
EQ -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
T Set a
forall a. Set a
E a
x Set a
b
    Ordering
GT -> Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
T (a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
filterGE a
y Set a
a) a
x Set a
b

partitionLT_GE :: forall a. Ord a => a -> Set a -> (Set a, Set a)
partitionLT_GE a
_ Set a
E = (Set a
forall a. Set a
E,Set a
forall a. Set a
E)
partitionLT_GE a
y (T Set a
a a
x Set a
b) =
  case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
x a
y of
    Ordering
LT -> (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
T Set a
a a
x Set a
b0,Set a
b1)
          where (Set a
b0,Set a
b1) = a -> Set a -> (Set a, Set a)
forall a. Ord a => a -> Set a -> (Set a, Set a)
partitionLT_GE a
y Set a
b
    Ordering
EQ -> (Set a
a,Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
T Set a
forall a. Set a
E a
x Set a
b)
    Ordering
GT -> (Set a
a0,Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
T Set a
a1 a
x Set a
b)
          where (Set a
a0,Set a
a1) = a -> Set a -> (Set a, Set a)
forall a. Ord a => a -> Set a -> (Set a, Set a)
partitionLT_GE a
y Set a
a

partitionLE_GT :: forall a. Ord a => a -> Set a -> (Set a, Set a)
partitionLE_GT a
_ Set a
E = (Set a
forall a. Set a
E,Set a
forall a. Set a
E)
partitionLE_GT a
y (T Set a
a a
x Set a
b) =
  case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
x a
y of
    Ordering
LT -> (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
T Set a
a a
x Set a
b0,Set a
b1)
          where (Set a
b0,Set a
b1) = a -> Set a -> (Set a, Set a)
forall a. Ord a => a -> Set a -> (Set a, Set a)
partitionLE_GT a
y Set a
b
    Ordering
EQ -> (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
T Set a
a a
x Set a
forall a. Set a
E,Set a
b)
    Ordering
GT -> (Set a
a0,Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
T Set a
a1 a
x Set a
b)
          where (Set a
a0,Set a
a1) = a -> Set a -> (Set a, Set a)
forall a. Ord a => a -> Set a -> (Set a, Set a)
partitionLE_GT a
y Set a
a

partitionLT_GT :: forall a. Ord a => a -> Set a -> (Set a, Set a)
partitionLT_GT a
_ Set a
E = (Set a
forall a. Set a
E,Set a
forall a. Set a
E)
partitionLT_GT a
y (T Set a
a a
x Set a
b) =
  case a -> a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare a
x a
y of
    Ordering
LT -> (Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
T Set a
a a
x Set a
b0,Set a
b1)
          where (Set a
b0,Set a
b1) = a -> Set a -> (Set a, Set a)
forall a. Ord a => a -> Set a -> (Set a, Set a)
partitionLT_GT a
y Set a
b
    Ordering
EQ -> (Set a
a,Set a
b)
    Ordering
GT -> (Set a
a0,Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
T Set a
a1 a
x Set a
b)
          where (Set a
a0,Set a
a1) = a -> Set a -> (Set a, Set a)
forall a. Ord a => a -> Set a -> (Set a, Set a)
partitionLT_GT a
y Set a
a

minView :: forall (m :: * -> *) a. MonadFail m => Set a -> m (a, Set a)
minView Set a
E = String -> m (a, Set a)
forall a. String -> m a
forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"UnbalancedSet.minView: empty collection"
minView (T Set a
E a
x Set a
b) = (a, Set a) -> m (a, Set a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (a
x, Set a
b)
minView (T Set a
a a
x Set a
b) = (a, Set a) -> m (a, Set a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (a
y, Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
T Set a
a' a
x Set a
b)
  where Just (a
y,Set a
a') = Set a -> Maybe (a, Set a)
forall (m :: * -> *) a. MonadFail m => Set a -> m (a, Set a)
minView Set a
a

minElem :: forall a. Set a -> a
minElem Set a
E = String -> a
forall a. HasCallStack => String -> a
error String
"UnbalancedSet.minElem: empty collection"
minElem (T Set a
E a
x Set a
_) = a
x
minElem (T Set a
a a
_ Set a
_) = Set a -> a
forall a. Set a -> a
minElem Set a
a

maxView :: forall (m :: * -> *) a. MonadFail m => Set a -> m (a, Set a)
maxView Set a
E = String -> m (a, Set a)
forall a. String -> m a
forall (m :: * -> *) a. MonadFail m => String -> m a
fail String
"UnbalancedSet.maxView: empty collection"
maxView (T Set a
a a
x Set a
E) = (a, Set a) -> m (a, Set a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (a
x, Set a
a)
maxView (T Set a
a a
x Set a
b) = (a, Set a) -> m (a, Set a)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (a
y, Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
T Set a
a a
x Set a
b')
  where Just (a
y, Set a
b') = Set a -> Maybe (a, Set a)
forall (m :: * -> *) a. MonadFail m => Set a -> m (a, Set a)
maxView Set a
b

maxElem :: forall a. Set a -> a
maxElem Set a
E = String -> a
forall a. HasCallStack => String -> a
error String
"UnbalancedSet.maxElem: empty collection"
maxElem (T Set a
_ a
x Set a
E) = a
x
maxElem (T Set a
_ a
_ Set a
b) = Set a -> a
forall a. Set a -> a
maxElem Set a
b

foldr :: forall a b. (a -> b -> b) -> b -> Set a -> b
foldr a -> b -> b
_ b
e Set a
E = b
e
foldr a -> b -> b
f b
e (T Set a
a a
x Set a
b) = (a -> b -> b) -> b -> Set a -> b
forall a b. (a -> b -> b) -> b -> Set a -> b
foldr a -> b -> b
f (a -> b -> b
f a
x ((a -> b -> b) -> b -> Set a -> b
forall a b. (a -> b -> b) -> b -> Set a -> b
foldr a -> b -> b
f b
e Set a
b)) Set a
a

foldr' :: forall a b. (a -> b -> b) -> b -> Set a -> b
foldr' a -> b -> b
_ b
e Set a
E = b
e
foldr' a -> b -> b
f b
e (T Set a
a a
x Set a
b) = b
e b -> b -> b
forall a b. a -> b -> b
`seq` (a -> b -> b) -> b -> Set a -> b
forall a b. (a -> b -> b) -> b -> Set a -> b
foldr' a -> b -> b
f (a -> b -> b
f a
x (b -> b) -> b -> b
forall a b. (a -> b) -> a -> b
$! ((a -> b -> b) -> b -> Set a -> b
forall a b. (a -> b -> b) -> b -> Set a -> b
foldr' a -> b -> b
f b
e Set a
b)) Set a
a

foldl :: forall b a. (b -> a -> b) -> b -> Set a -> b
foldl b -> a -> b
_ b
e Set a
E = b
e
foldl b -> a -> b
f b
e (T Set a
a a
x Set a
b) = (b -> a -> b) -> b -> Set a -> b
forall b a. (b -> a -> b) -> b -> Set a -> b
foldl b -> a -> b
f (b -> a -> b
f ((b -> a -> b) -> b -> Set a -> b
forall b a. (b -> a -> b) -> b -> Set a -> b
foldl b -> a -> b
f b
e Set a
a) a
x) Set a
b

foldl' :: forall b a. (b -> a -> b) -> b -> Set a -> b
foldl' b -> a -> b
_ b
e Set a
E = b
e
foldl' b -> a -> b
f b
e (T Set a
a a
x Set a
b) = b
e b -> b -> b
forall a b. a -> b -> b
`seq` (b -> a -> b) -> b -> Set a -> b
forall b a. (b -> a -> b) -> b -> Set a -> b
foldl' b -> a -> b
f ((b -> a -> b
f (b -> a -> b) -> b -> a -> b
forall a b. (a -> b) -> a -> b
$! ((b -> a -> b) -> b -> Set a -> b
forall b a. (b -> a -> b) -> b -> Set a -> b
foldl' b -> a -> b
f b
e Set a
a)) a
x) Set a
b

foldr1 :: forall a. (a -> a -> a) -> Set a -> a
foldr1 a -> a -> a
_ Set a
E = String -> a
forall a. HasCallStack => String -> a
error String
"UnbalancedSet.foldr1: empty collection"
foldr1 a -> a -> a
f (T Set a
a a
x Set a
E) = (a -> a -> a) -> a -> Set a -> a
forall a b. (a -> b -> b) -> b -> Set a -> b
foldr a -> a -> a
f a
x Set a
a
foldr1 a -> a -> a
f (T Set a
a a
x Set a
b) = (a -> a -> a) -> a -> Set a -> a
forall a b. (a -> b -> b) -> b -> Set a -> b
foldr a -> a -> a
f (a -> a -> a
f a
x ((a -> a -> a) -> Set a -> a
forall a. (a -> a -> a) -> Set a -> a
foldr1 a -> a -> a
f Set a
b)) Set a
a

foldr1' :: forall a. (a -> a -> a) -> Set a -> a
foldr1' a -> a -> a
_ Set a
E = String -> a
forall a. HasCallStack => String -> a
error String
"UnbalancedSet.foldr1': empty collection"
foldr1' a -> a -> a
f (T Set a
a a
x Set a
E) = (a -> a -> a) -> a -> Set a -> a
forall a b. (a -> b -> b) -> b -> Set a -> b
foldr' a -> a -> a
f a
x Set a
a
foldr1' a -> a -> a
f (T Set a
a a
x Set a
b) = (a -> a -> a) -> a -> Set a -> a
forall a b. (a -> b -> b) -> b -> Set a -> b
foldr' a -> a -> a
f (a -> a -> a
f a
x (a -> a) -> a -> a
forall a b. (a -> b) -> a -> b
$! ((a -> a -> a) -> Set a -> a
forall a. (a -> a -> a) -> Set a -> a
foldr1' a -> a -> a
f Set a
b)) Set a
a

foldl1 :: forall a. (a -> a -> a) -> Set a -> a
foldl1 a -> a -> a
_ Set a
E = String -> a
forall a. HasCallStack => String -> a
error String
"UnbalancedSet.foldl1: empty collection"
foldl1 a -> a -> a
f (T Set a
E a
x Set a
b) = (a -> a -> a) -> a -> Set a -> a
forall b a. (b -> a -> b) -> b -> Set a -> b
foldl a -> a -> a
f a
x Set a
b
foldl1 a -> a -> a
f (T Set a
a a
x Set a
b) = (a -> a -> a) -> a -> Set a -> a
forall b a. (b -> a -> b) -> b -> Set a -> b
foldl a -> a -> a
f (a -> a -> a
f ((a -> a -> a) -> Set a -> a
forall a. (a -> a -> a) -> Set a -> a
foldl1 a -> a -> a
f Set a
a) a
x) Set a
b

foldl1' :: forall a. (a -> a -> a) -> Set a -> a
foldl1' a -> a -> a
_ Set a
E = String -> a
forall a. HasCallStack => String -> a
error String
"UnbalancedSet.foldl1': empty collection"
foldl1' a -> a -> a
f (T Set a
E a
x Set a
b) = (a -> a -> a) -> a -> Set a -> a
forall b a. (b -> a -> b) -> b -> Set a -> b
foldl' a -> a -> a
f a
x Set a
b
foldl1' a -> a -> a
f (T Set a
a a
x Set a
b) = (a -> a -> a) -> a -> Set a -> a
forall b a. (b -> a -> b) -> b -> Set a -> b
foldl' a -> a -> a
f ((a -> a -> a
f (a -> a -> a) -> a -> a -> a
forall a b. (a -> b) -> a -> b
$! ((a -> a -> a) -> Set a -> a
forall a. (a -> a -> a) -> Set a -> a
foldl1' a -> a -> a
f Set a
a)) a
x) Set a
b

unsafeMapMonotonic :: forall a. Ord a => (a -> a) -> Set a -> Set a
unsafeMapMonotonic a -> a
_ Set a
E = Set a
forall a. Set a
E
unsafeMapMonotonic a -> a
f (T Set a
a a
x Set a
b) =
    Set a -> a -> Set a -> Set a
forall a. Set a -> a -> Set a -> Set a
T ((a -> a) -> Set a -> Set a
forall a. Ord a => (a -> a) -> Set a -> Set a
unsafeMapMonotonic a -> a
f Set a
a) (a -> a
f a
x) ((a -> a) -> Set a -> Set a
forall a. Ord a => (a -> a) -> Set a -> Set a
unsafeMapMonotonic a -> a
f Set a
b)

strict :: forall a. Set a -> Set a
strict s :: Set a
s@Set a
E = Set a
s
strict s :: Set a
s@(T Set a
l a
_ Set a
r) = Set a -> Set a
forall a. Set a -> Set a
strict Set a
l Set a -> Set a -> Set a
forall a b. a -> b -> b
`seq` Set a -> Set a
forall a. Set a -> Set a
strict Set a
r Set a -> Set a -> Set a
forall a b. a -> b -> b
`seq` Set a
s

strictWith :: forall a b. (a -> b) -> Set a -> Set a
strictWith a -> b
_ s :: Set a
s@Set a
E = Set a
s
strictWith a -> b
f s :: Set a
s@(T Set a
l a
x Set a
r) = a -> b
f a
x b -> Set a -> Set a
forall a b. a -> b -> b
`seq` (a -> b) -> Set a -> Set a
forall a b. (a -> b) -> Set a -> Set a
strictWith a -> b
f Set a
l Set a -> Set a -> Set a
forall a b. a -> b -> b
`seq` (a -> b) -> Set a -> Set a
forall a b. (a -> b) -> Set a -> Set a
strictWith a -> b
f Set a
r Set a -> Set a -> Set a
forall a b. a -> b -> b
`seq` Set a
s

-- the remaining functions all use default definitions

fromSeq :: forall a (seq :: * -> *). (Ord a, Sequence seq) => seq a -> Set a
fromSeq = seq a -> Set a
forall c a (seq :: * -> *). (CollX c a, Sequence seq) => seq a -> c
fromSeqUsingUnionSeq
insert :: forall a. Ord a => a -> Set a -> Set a
insert = a -> Set a -> Set a
forall c a. Set c a => a -> c -> c
insertUsingInsertWith
insertSeq :: forall a (seq :: * -> *).
(Ord a, Sequence seq) =>
seq a -> Set a -> Set a
insertSeq = seq a -> Set a -> Set a
forall c a (seq :: * -> *).
(CollX c a, Sequence seq) =>
seq a -> c -> c
insertSeqUsingUnion
union :: forall a. Ord a => Set a -> Set a -> Set a
union = Set a -> Set a -> Set a
forall c a. Set c a => c -> c -> c
unionUsingUnionWith
unionSeq :: forall a (seq :: * -> *).
(Ord a, Sequence seq) =>
seq (Set a) -> Set a
unionSeq = seq (Set a) -> Set a
forall c a (seq :: * -> *). (CollX c a, Sequence seq) => seq c -> c
unionSeqUsingReduce
deleteAll :: forall a. Ord a => a -> Set a -> Set a
deleteAll = a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
delete
deleteSeq :: forall a (seq :: * -> *).
(Ord a, Sequence seq) =>
seq a -> Set a -> Set a
deleteSeq = seq a -> Set a -> Set a
forall c a (seq :: * -> *).
(CollX c a, Sequence seq) =>
seq a -> c -> c
deleteSeqUsingDelete
count :: forall a. Ord a => a -> Set a -> Int
count = a -> Set a -> Int
forall c a. SetX c a => a -> c -> Int
countUsingMember

toSeq :: forall a (seq :: * -> *). (Ord a, Sequence seq) => Set a -> seq a
toSeq = Set a -> seq a
forall c a (seq :: * -> *). (Coll c a, Sequence seq) => c -> seq a
toSeqUsingFold
lookup :: forall a. Ord a => a -> Set a -> a
lookup = a -> Set a -> a
forall c a. Coll c a => a -> c -> a
lookupUsingLookupM
lookupAll :: forall a (seq :: * -> *).
(Ord a, Sequence seq) =>
a -> Set a -> seq a
lookupAll = a -> Set a -> seq a
forall c a (seq :: * -> *).
(Set c a, Sequence seq) =>
a -> c -> seq a
lookupAllUsingLookupM
lookupWithDefault :: forall a. Ord a => a -> a -> Set a -> a
lookupWithDefault = a -> a -> Set a -> a
forall c a. Coll c a => a -> a -> c -> a
lookupWithDefaultUsingLookupM
filter :: forall a. Ord a => (a -> Bool) -> Set a -> Set a
filter = (a -> Bool) -> Set a -> Set a
forall c a. OrdColl c a => (a -> Bool) -> c -> c
filterUsingOrdLists
partition :: forall a. Ord a => (a -> Bool) -> Set a -> (Set a, Set a)
partition = (a -> Bool) -> Set a -> (Set a, Set a)
forall c a. OrdColl c a => (a -> Bool) -> c -> (c, c)
partitionUsingOrdLists
toOrdSeq :: forall a (seq :: * -> *). (Ord a, Sequence seq) => Set a -> seq a
toOrdSeq = Set a -> seq a
forall c a (seq :: * -> *).
(OrdColl c a, Sequence seq) =>
c -> seq a
toOrdSeqUsingFoldr

intersection :: forall a. Ord a => Set a -> Set a -> Set a
intersection = Set a -> Set a -> Set a
forall c a. Set c a => c -> c -> c
intersectionUsingIntersectionWith
difference :: forall a. Ord a => Set a -> Set a -> Set a
difference = Set a -> Set a -> Set a
forall c a. OrdSet c a => c -> c -> c
differenceUsingOrdLists
symmetricDifference :: forall a. Ord a => Set a -> Set a -> Set a
symmetricDifference = Set a -> Set a -> Set a
forall c a. SetX c a => c -> c -> c
symmetricDifferenceUsingDifference
properSubset :: forall a. Ord a => Set a -> Set a -> Bool
properSubset = Set a -> Set a -> Bool
forall c a. OrdSet c a => c -> c -> Bool
properSubsetUsingOrdLists
subset :: forall a. Ord a => Set a -> Set a -> Bool
subset = Set a -> Set a -> Bool
forall c a. OrdSet c a => c -> c -> Bool
subsetUsingOrdLists
fromSeqWith :: forall a (seq :: * -> *).
(Ord a, Sequence seq) =>
(a -> a -> a) -> seq a -> Set a
fromSeqWith = (a -> a -> a) -> seq a -> Set a
forall c a (seq :: * -> *).
(Set c a, Sequence seq) =>
(a -> a -> a) -> seq a -> c
fromSeqWithUsingInsertWith
insertSeqWith :: forall a (seq :: * -> *).
(Ord a, Sequence seq) =>
(a -> a -> a) -> seq a -> Set a -> Set a
insertSeqWith = (a -> a -> a) -> seq a -> Set a -> Set a
forall c a (seq :: * -> *).
(Set c a, Sequence seq) =>
(a -> a -> a) -> seq a -> c -> c
insertSeqWithUsingInsertWith
unionl :: forall a. Ord a => Set a -> Set a -> Set a
unionl = Set a -> Set a -> Set a
forall c a. Set c a => c -> c -> c
unionlUsingUnionWith
unionr :: forall a. Ord a => Set a -> Set a -> Set a
unionr = Set a -> Set a -> Set a
forall c a. Set c a => c -> c -> c
unionrUsingUnionWith
unionWith :: forall a. Ord a => (a -> a -> a) -> Set a -> Set a -> Set a
unionWith = (a -> a -> a) -> Set a -> Set a -> Set a
forall c a. OrdSet c a => (a -> a -> a) -> c -> c -> c
unionWithUsingOrdLists
unionSeqWith :: forall a (seq :: * -> *).
(Ord a, Sequence seq) =>
(a -> a -> a) -> seq (Set a) -> Set a
unionSeqWith = (a -> a -> a) -> seq (Set a) -> Set a
forall c a (seq :: * -> *).
(Set c a, Sequence seq) =>
(a -> a -> a) -> seq c -> c
unionSeqWithUsingReducer
intersectionWith :: forall a. Ord a => (a -> a -> a) -> Set a -> Set a -> Set a
intersectionWith = (a -> a -> a) -> Set a -> Set a -> Set a
forall c a. OrdSet c a => (a -> a -> a) -> c -> c -> c
intersectionWithUsingOrdLists

-- instance declarations

instance Ord a => C.CollX (Set a) a where
  {singleton :: a -> Set a
singleton = a -> Set a
forall a. a -> Set a
singleton; fromSeq :: forall (seq :: * -> *). Sequence seq => seq a -> Set a
fromSeq = seq a -> Set a
forall a (seq :: * -> *). (Ord a, Sequence seq) => seq a -> Set a
fromSeq; insert :: a -> Set a -> Set a
insert = a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
insert;
   insertSeq :: forall (seq :: * -> *). Sequence seq => seq a -> Set a -> Set a
insertSeq = seq a -> Set a -> Set a
forall a (seq :: * -> *).
(Ord a, Sequence seq) =>
seq a -> Set a -> Set a
insertSeq; unionSeq :: forall (seq :: * -> *). Sequence seq => seq (Set a) -> Set a
unionSeq = seq (Set a) -> Set a
forall a (seq :: * -> *).
(Ord a, Sequence seq) =>
seq (Set a) -> Set a
unionSeq;
   delete :: a -> Set a -> Set a
delete = a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
delete; deleteAll :: a -> Set a -> Set a
deleteAll = a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
deleteAll; deleteSeq :: forall (seq :: * -> *). Sequence seq => seq a -> Set a -> Set a
deleteSeq = seq a -> Set a -> Set a
forall a (seq :: * -> *).
(Ord a, Sequence seq) =>
seq a -> Set a -> Set a
deleteSeq;
   null :: Set a -> Bool
null = Set a -> Bool
forall a. Set a -> Bool
null; size :: Set a -> Int
size = Set a -> Int
forall a. Set a -> Int
size; member :: a -> Set a -> Bool
member = a -> Set a -> Bool
forall a. Ord a => a -> Set a -> Bool
member; count :: a -> Set a -> Int
count = a -> Set a -> Int
forall a. Ord a => a -> Set a -> Int
count;
   strict :: Set a -> Set a
strict = Set a -> Set a
forall a. Set a -> Set a
strict;
   structuralInvariant :: Set a -> Bool
structuralInvariant = Set a -> Bool
forall a. Ord a => Set a -> Bool
structuralInvariant; instanceName :: Set a -> String
instanceName Set a
_ = String
moduleName}

instance Ord a => C.OrdCollX (Set a) a where
  {deleteMin :: Set a -> Set a
deleteMin = Set a -> Set a
forall a. Ord a => Set a -> Set a
deleteMin; deleteMax :: Set a -> Set a
deleteMax = Set a -> Set a
forall a. Ord a => Set a -> Set a
deleteMax;
   unsafeInsertMin :: a -> Set a -> Set a
unsafeInsertMin = a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
unsafeInsertMin; unsafeInsertMax :: a -> Set a -> Set a
unsafeInsertMax = a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
unsafeInsertMax;
   unsafeFromOrdSeq :: forall (seq :: * -> *). Sequence seq => seq a -> Set a
unsafeFromOrdSeq = seq a -> Set a
forall a (seq :: * -> *). (Ord a, Sequence seq) => seq a -> Set a
unsafeFromOrdSeq; unsafeAppend :: Set a -> Set a -> Set a
unsafeAppend = Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
unsafeAppend;
   filterLT :: a -> Set a -> Set a
filterLT = a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
filterLT; filterLE :: a -> Set a -> Set a
filterLE = a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
filterLE; filterGT :: a -> Set a -> Set a
filterGT = a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
filterGT;
   filterGE :: a -> Set a -> Set a
filterGE = a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
filterGE; partitionLT_GE :: a -> Set a -> (Set a, Set a)
partitionLT_GE = a -> Set a -> (Set a, Set a)
forall a. Ord a => a -> Set a -> (Set a, Set a)
partitionLT_GE;
   partitionLE_GT :: a -> Set a -> (Set a, Set a)
partitionLE_GT = a -> Set a -> (Set a, Set a)
forall a. Ord a => a -> Set a -> (Set a, Set a)
partitionLE_GT; partitionLT_GT :: a -> Set a -> (Set a, Set a)
partitionLT_GT = a -> Set a -> (Set a, Set a)
forall a. Ord a => a -> Set a -> (Set a, Set a)
partitionLT_GT}

instance Ord a => C.Coll (Set a) a where
  {toSeq :: forall (seq :: * -> *). Sequence seq => Set a -> seq a
toSeq = Set a -> seq a
forall a (seq :: * -> *). (Ord a, Sequence seq) => Set a -> seq a
toSeq; lookup :: a -> Set a -> a
lookup = a -> Set a -> a
forall a. Ord a => a -> Set a -> a
lookup; lookupM :: forall (m :: * -> *). MonadFail m => a -> Set a -> m a
lookupM = a -> Set a -> m a
forall a (m :: * -> *). (Ord a, MonadFail m) => a -> Set a -> m a
lookupM;
   lookupAll :: forall (seq :: * -> *). Sequence seq => a -> Set a -> seq a
lookupAll = a -> Set a -> seq a
forall a (seq :: * -> *).
(Ord a, Sequence seq) =>
a -> Set a -> seq a
lookupAll; lookupWithDefault :: a -> a -> Set a -> a
lookupWithDefault = a -> a -> Set a -> a
forall a. Ord a => a -> a -> Set a -> a
lookupWithDefault;
   fold :: forall b. (a -> b -> b) -> b -> Set a -> b
fold = (a -> b -> b) -> b -> Set a -> b
forall a b. (a -> b -> b) -> b -> Set a -> b
fold; fold' :: forall b. (a -> b -> b) -> b -> Set a -> b
fold' = (a -> b -> b) -> b -> Set a -> b
forall a b. (a -> b -> b) -> b -> Set a -> b
fold'; fold1 :: (a -> a -> a) -> Set a -> a
fold1 = (a -> a -> a) -> Set a -> a
forall a. (a -> a -> a) -> Set a -> a
fold1; fold1' :: (a -> a -> a) -> Set a -> a
fold1' = (a -> a -> a) -> Set a -> a
forall a. (a -> a -> a) -> Set a -> a
fold1';
   filter :: (a -> Bool) -> Set a -> Set a
filter = (a -> Bool) -> Set a -> Set a
forall a. Ord a => (a -> Bool) -> Set a -> Set a
filter; partition :: (a -> Bool) -> Set a -> (Set a, Set a)
partition = (a -> Bool) -> Set a -> (Set a, Set a)
forall a. Ord a => (a -> Bool) -> Set a -> (Set a, Set a)
partition; strictWith :: forall b. (a -> b) -> Set a -> Set a
strictWith = (a -> b) -> Set a -> Set a
forall a b. (a -> b) -> Set a -> Set a
strictWith}

instance Ord a => C.OrdColl (Set a) a where
  {minView :: forall (m :: * -> *). MonadFail m => Set a -> m (a, Set a)
minView = Set a -> m (a, Set a)
forall (m :: * -> *) a. MonadFail m => Set a -> m (a, Set a)
minView; minElem :: Set a -> a
minElem = Set a -> a
forall a. Set a -> a
minElem; maxView :: forall (m :: * -> *). MonadFail m => Set a -> m (a, Set a)
maxView = Set a -> m (a, Set a)
forall (m :: * -> *) a. MonadFail m => Set a -> m (a, Set a)
maxView;
   maxElem :: Set a -> a
maxElem = Set a -> a
forall a. Set a -> a
maxElem; foldr :: forall b. (a -> b -> b) -> b -> Set a -> b
foldr = (a -> b -> b) -> b -> Set a -> b
forall a b. (a -> b -> b) -> b -> Set a -> b
foldr; foldr' :: forall b. (a -> b -> b) -> b -> Set a -> b
foldr' = (a -> b -> b) -> b -> Set a -> b
forall a b. (a -> b -> b) -> b -> Set a -> b
foldr';
   foldl :: forall b. (b -> a -> b) -> b -> Set a -> b
foldl = (b -> a -> b) -> b -> Set a -> b
forall b a. (b -> a -> b) -> b -> Set a -> b
foldl; foldl' :: forall b. (b -> a -> b) -> b -> Set a -> b
foldl' = (b -> a -> b) -> b -> Set a -> b
forall b a. (b -> a -> b) -> b -> Set a -> b
foldl'; foldr1 :: (a -> a -> a) -> Set a -> a
foldr1 = (a -> a -> a) -> Set a -> a
forall a. (a -> a -> a) -> Set a -> a
foldr1; foldr1' :: (a -> a -> a) -> Set a -> a
foldr1' = (a -> a -> a) -> Set a -> a
forall a. (a -> a -> a) -> Set a -> a
foldr1';
   foldl1 :: (a -> a -> a) -> Set a -> a
foldl1 = (a -> a -> a) -> Set a -> a
forall a. (a -> a -> a) -> Set a -> a
foldl1; foldl1' :: (a -> a -> a) -> Set a -> a
foldl1' = (a -> a -> a) -> Set a -> a
forall a. (a -> a -> a) -> Set a -> a
foldl1'; toOrdSeq :: forall (seq :: * -> *). Sequence seq => Set a -> seq a
toOrdSeq = Set a -> seq a
forall a (seq :: * -> *). (Ord a, Sequence seq) => Set a -> seq a
toOrdSeq;
   unsafeMapMonotonic :: (a -> a) -> Set a -> Set a
unsafeMapMonotonic = (a -> a) -> Set a -> Set a
forall a. Ord a => (a -> a) -> Set a -> Set a
unsafeMapMonotonic}

instance Ord a => C.SetX (Set a) a where
  {intersection :: Set a -> Set a -> Set a
intersection = Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
intersection; difference :: Set a -> Set a -> Set a
difference = Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
difference;
   symmetricDifference :: Set a -> Set a -> Set a
symmetricDifference = Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
symmetricDifference;
   properSubset :: Set a -> Set a -> Bool
properSubset = Set a -> Set a -> Bool
forall a. Ord a => Set a -> Set a -> Bool
properSubset; subset :: Set a -> Set a -> Bool
subset = Set a -> Set a -> Bool
forall a. Ord a => Set a -> Set a -> Bool
subset}

instance Ord a => C.Set (Set a) a where
  {fromSeqWith :: forall (seq :: * -> *).
Sequence seq =>
(a -> a -> a) -> seq a -> Set a
fromSeqWith = (a -> a -> a) -> seq a -> Set a
forall a (seq :: * -> *).
(Ord a, Sequence seq) =>
(a -> a -> a) -> seq a -> Set a
fromSeqWith; insertWith :: (a -> a -> a) -> a -> Set a -> Set a
insertWith = (a -> a -> a) -> a -> Set a -> Set a
forall a. Ord a => (a -> a -> a) -> a -> Set a -> Set a
insertWith;
   insertSeqWith :: forall (seq :: * -> *).
Sequence seq =>
(a -> a -> a) -> seq a -> Set a -> Set a
insertSeqWith = (a -> a -> a) -> seq a -> Set a -> Set a
forall a (seq :: * -> *).
(Ord a, Sequence seq) =>
(a -> a -> a) -> seq a -> Set a -> Set a
insertSeqWith; unionl :: Set a -> Set a -> Set a
unionl = Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
unionl; unionr :: Set a -> Set a -> Set a
unionr = Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
unionr;
   unionWith :: (a -> a -> a) -> Set a -> Set a -> Set a
unionWith = (a -> a -> a) -> Set a -> Set a -> Set a
forall a. Ord a => (a -> a -> a) -> Set a -> Set a -> Set a
unionWith; unionSeqWith :: forall (seq :: * -> *).
Sequence seq =>
(a -> a -> a) -> seq (Set a) -> Set a
unionSeqWith = (a -> a -> a) -> seq (Set a) -> Set a
forall a (seq :: * -> *).
(Ord a, Sequence seq) =>
(a -> a -> a) -> seq (Set a) -> Set a
unionSeqWith;
   intersectionWith :: (a -> a -> a) -> Set a -> Set a -> Set a
intersectionWith = (a -> a -> a) -> Set a -> Set a -> Set a
forall a. Ord a => (a -> a -> a) -> Set a -> Set a -> Set a
intersectionWith}

instance Ord a => C.OrdSetX (Set a) a

instance Ord a => C.OrdSet (Set a) a


instance Ord a => Eq (Set a) where
  Set a
xs == :: Set a -> Set a -> Bool
== Set a
ys = Set a -> [a]
forall c a. OrdColl c a => c -> [a]
C.toOrdList Set a
xs [a] -> [a] -> Bool
forall a. Eq a => a -> a -> Bool
== Set a -> [a]
forall c a. OrdColl c a => c -> [a]
C.toOrdList Set a
ys

instance (Ord a, Show a) => Show (Set a) where
   showsPrec :: Int -> Set a -> ShowS
showsPrec = Int -> Set a -> ShowS
forall c a. (Coll c a, Show a) => Int -> c -> ShowS
showsPrecUsingToList

instance (Ord a, Read a) => Read (Set a) where
   readsPrec :: Int -> ReadS (Set a)
readsPrec = Int -> ReadS (Set a)
forall c a. (Coll c a, Read a) => Int -> ReadS c
readsPrecUsingFromList


instance (Ord a, Arbitrary a) => Arbitrary (Set a) where
  arbitrary :: Gen (Set a)
arbitrary = do ([a]
xs::[a]) <- Gen [a]
forall a. Arbitrary a => Gen a
arbitrary
                 Set a -> Gen (Set a)
forall a. a -> Gen a
forall (m :: * -> *) a. Monad m => a -> m a
return ((a -> Set a -> Set a) -> Set a -> [a] -> Set a
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Prelude.foldr a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
insert Set a
forall a. Set a
empty [a]
xs)

instance (Ord a, CoArbitrary a) => CoArbitrary (Set a) where
  coarbitrary :: forall b. Set a -> Gen b -> Gen b
coarbitrary Set a
E = Integer -> Gen b -> Gen b
forall n a. Integral n => n -> Gen a -> Gen a
variant Integer
0
  coarbitrary (T Set a
a a
x Set a
b) =
    Integer -> Gen b -> Gen b
forall n a. Integral n => n -> Gen a -> Gen a
variant Integer
1 (Gen b -> Gen b) -> (Gen b -> Gen b) -> Gen b -> Gen b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Set a -> Gen b -> Gen b
forall a b. CoArbitrary a => a -> Gen b -> Gen b
forall b. Set a -> Gen b -> Gen b
coarbitrary Set a
a (Gen b -> Gen b) -> (Gen b -> Gen b) -> Gen b -> Gen b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Gen b -> Gen b
forall b. a -> Gen b -> Gen b
forall a b. CoArbitrary a => a -> Gen b -> Gen b
coarbitrary a
x (Gen b -> Gen b) -> (Gen b -> Gen b) -> Gen b -> Gen b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Set a -> Gen b -> Gen b
forall a b. CoArbitrary a => a -> Gen b -> Gen b
forall b. Set a -> Gen b -> Gen b
coarbitrary Set a
b

instance (Ord a) => Semigroup (Set a) where
  <> :: Set a -> Set a -> Set a
(<>) = Set a -> Set a -> Set a
forall a. Ord a => Set a -> Set a -> Set a
union

instance (Ord a) => Monoid (Set a) where
    mempty :: Set a
mempty  = Set a
forall a. Set a
empty
    mappend :: Set a -> Set a -> Set a
mappend = Set a -> Set a -> Set a
forall a. Semigroup a => a -> a -> a
(SG.<>)
    mconcat :: [Set a] -> Set a
mconcat = [Set a] -> Set a
forall a (seq :: * -> *).
(Ord a, Sequence seq) =>
seq (Set a) -> Set a
unionSeq

instance (Ord a) => Ord (Set a) where
    compare :: Set a -> Set a -> Ordering
compare = Set a -> Set a -> Ordering
forall c a. OrdColl c a => c -> c -> Ordering
compareUsingToOrdList