module IntLike.Set
  ( IntLikeSet (..)
  , empty
  , singleton
  , fromList
  , size
  , null
  , member
  , toList
  , insert
  , delete
  , isSubsetOf
  , intersection
  , difference
  , union
  , unions
  , findMin
  , minView
  , disjoint
  , map
  , filter
  , insertState
  , orderedPairs
  , unorderedPairs
  )
where

import Control.DeepSeq (NFData)
import Data.Coerce (Coercible, coerce)
import Data.Foldable (foldl')
import Data.IntSet (IntSet)
import qualified Data.IntSet as IntSet
import Prelude hiding (filter, map, null)

newtype IntLikeSet x = IntLikeSet {forall x. IntLikeSet x -> IntSet
unIntLikeSet :: IntSet}
  deriving stock (Int -> IntLikeSet x -> ShowS
[IntLikeSet x] -> ShowS
IntLikeSet x -> String
(Int -> IntLikeSet x -> ShowS)
-> (IntLikeSet x -> String)
-> ([IntLikeSet x] -> ShowS)
-> Show (IntLikeSet x)
forall x. Int -> IntLikeSet x -> ShowS
forall x. [IntLikeSet x] -> ShowS
forall x. IntLikeSet x -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: forall x. Int -> IntLikeSet x -> ShowS
showsPrec :: Int -> IntLikeSet x -> ShowS
$cshow :: forall x. IntLikeSet x -> String
show :: IntLikeSet x -> String
$cshowList :: forall x. [IntLikeSet x] -> ShowS
showList :: [IntLikeSet x] -> ShowS
Show)
  deriving newtype (IntLikeSet x -> IntLikeSet x -> Bool
(IntLikeSet x -> IntLikeSet x -> Bool)
-> (IntLikeSet x -> IntLikeSet x -> Bool) -> Eq (IntLikeSet x)
forall x. IntLikeSet x -> IntLikeSet x -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: forall x. IntLikeSet x -> IntLikeSet x -> Bool
== :: IntLikeSet x -> IntLikeSet x -> Bool
$c/= :: forall x. IntLikeSet x -> IntLikeSet x -> Bool
/= :: IntLikeSet x -> IntLikeSet x -> Bool
Eq, Eq (IntLikeSet x)
Eq (IntLikeSet x) =>
(IntLikeSet x -> IntLikeSet x -> Ordering)
-> (IntLikeSet x -> IntLikeSet x -> Bool)
-> (IntLikeSet x -> IntLikeSet x -> Bool)
-> (IntLikeSet x -> IntLikeSet x -> Bool)
-> (IntLikeSet x -> IntLikeSet x -> Bool)
-> (IntLikeSet x -> IntLikeSet x -> IntLikeSet x)
-> (IntLikeSet x -> IntLikeSet x -> IntLikeSet x)
-> Ord (IntLikeSet x)
IntLikeSet x -> IntLikeSet x -> Bool
IntLikeSet x -> IntLikeSet x -> Ordering
IntLikeSet x -> IntLikeSet x -> IntLikeSet x
forall x. Eq (IntLikeSet x)
forall a.
Eq a =>
(a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall x. IntLikeSet x -> IntLikeSet x -> Bool
forall x. IntLikeSet x -> IntLikeSet x -> Ordering
forall x. IntLikeSet x -> IntLikeSet x -> IntLikeSet x
$ccompare :: forall x. IntLikeSet x -> IntLikeSet x -> Ordering
compare :: IntLikeSet x -> IntLikeSet x -> Ordering
$c< :: forall x. IntLikeSet x -> IntLikeSet x -> Bool
< :: IntLikeSet x -> IntLikeSet x -> Bool
$c<= :: forall x. IntLikeSet x -> IntLikeSet x -> Bool
<= :: IntLikeSet x -> IntLikeSet x -> Bool
$c> :: forall x. IntLikeSet x -> IntLikeSet x -> Bool
> :: IntLikeSet x -> IntLikeSet x -> Bool
$c>= :: forall x. IntLikeSet x -> IntLikeSet x -> Bool
>= :: IntLikeSet x -> IntLikeSet x -> Bool
$cmax :: forall x. IntLikeSet x -> IntLikeSet x -> IntLikeSet x
max :: IntLikeSet x -> IntLikeSet x -> IntLikeSet x
$cmin :: forall x. IntLikeSet x -> IntLikeSet x -> IntLikeSet x
min :: IntLikeSet x -> IntLikeSet x -> IntLikeSet x
Ord, IntLikeSet x -> ()
(IntLikeSet x -> ()) -> NFData (IntLikeSet x)
forall x. IntLikeSet x -> ()
forall a. (a -> ()) -> NFData a
$crnf :: forall x. IntLikeSet x -> ()
rnf :: IntLikeSet x -> ()
NFData, NonEmpty (IntLikeSet x) -> IntLikeSet x
IntLikeSet x -> IntLikeSet x -> IntLikeSet x
(IntLikeSet x -> IntLikeSet x -> IntLikeSet x)
-> (NonEmpty (IntLikeSet x) -> IntLikeSet x)
-> (forall b. Integral b => b -> IntLikeSet x -> IntLikeSet x)
-> Semigroup (IntLikeSet x)
forall b. Integral b => b -> IntLikeSet x -> IntLikeSet x
forall x. NonEmpty (IntLikeSet x) -> IntLikeSet x
forall x. IntLikeSet x -> IntLikeSet x -> IntLikeSet x
forall a.
(a -> a -> a)
-> (NonEmpty a -> a)
-> (forall b. Integral b => b -> a -> a)
-> Semigroup a
forall x b. Integral b => b -> IntLikeSet x -> IntLikeSet x
$c<> :: forall x. IntLikeSet x -> IntLikeSet x -> IntLikeSet x
<> :: IntLikeSet x -> IntLikeSet x -> IntLikeSet x
$csconcat :: forall x. NonEmpty (IntLikeSet x) -> IntLikeSet x
sconcat :: NonEmpty (IntLikeSet x) -> IntLikeSet x
$cstimes :: forall x b. Integral b => b -> IntLikeSet x -> IntLikeSet x
stimes :: forall b. Integral b => b -> IntLikeSet x -> IntLikeSet x
Semigroup, Semigroup (IntLikeSet x)
IntLikeSet x
Semigroup (IntLikeSet x) =>
IntLikeSet x
-> (IntLikeSet x -> IntLikeSet x -> IntLikeSet x)
-> ([IntLikeSet x] -> IntLikeSet x)
-> Monoid (IntLikeSet x)
[IntLikeSet x] -> IntLikeSet x
IntLikeSet x -> IntLikeSet x -> IntLikeSet x
forall x. Semigroup (IntLikeSet x)
forall x. IntLikeSet x
forall a.
Semigroup a =>
a -> (a -> a -> a) -> ([a] -> a) -> Monoid a
forall x. [IntLikeSet x] -> IntLikeSet x
forall x. IntLikeSet x -> IntLikeSet x -> IntLikeSet x
$cmempty :: forall x. IntLikeSet x
mempty :: IntLikeSet x
$cmappend :: forall x. IntLikeSet x -> IntLikeSet x -> IntLikeSet x
mappend :: IntLikeSet x -> IntLikeSet x -> IntLikeSet x
$cmconcat :: forall x. [IntLikeSet x] -> IntLikeSet x
mconcat :: [IntLikeSet x] -> IntLikeSet x
Monoid)

empty :: IntLikeSet x
empty :: forall x. IntLikeSet x
empty = IntSet -> IntLikeSet x
forall x. IntSet -> IntLikeSet x
IntLikeSet IntSet
IntSet.empty
{-# INLINE empty #-}

singleton :: Coercible x Int => x -> IntLikeSet x
singleton :: forall x. Coercible x Int => x -> IntLikeSet x
singleton = IntSet -> IntLikeSet x
forall x. IntSet -> IntLikeSet x
IntLikeSet (IntSet -> IntLikeSet x) -> (x -> IntSet) -> x -> IntLikeSet x
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> IntSet
IntSet.singleton (Int -> IntSet) -> (x -> Int) -> x -> IntSet
forall b c a. (b -> c) -> (a -> b) -> a -> c
. x -> Int
forall a b. Coercible a b => a -> b
coerce
{-# INLINE singleton #-}

fromList :: Coercible x Int => [x] -> IntLikeSet x
fromList :: forall x. Coercible x Int => [x] -> IntLikeSet x
fromList = IntSet -> IntLikeSet x
forall x. IntSet -> IntLikeSet x
IntLikeSet (IntSet -> IntLikeSet x) -> ([x] -> IntSet) -> [x] -> IntLikeSet x
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Int] -> IntSet
IntSet.fromList ([Int] -> IntSet) -> ([x] -> [Int]) -> [x] -> IntSet
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [x] -> [Int]
forall a b. Coercible a b => a -> b
coerce
{-# INLINE fromList #-}

size :: IntLikeSet x -> Int
size :: forall x. IntLikeSet x -> Int
size = IntSet -> Int
IntSet.size (IntSet -> Int) -> (IntLikeSet x -> IntSet) -> IntLikeSet x -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. IntLikeSet x -> IntSet
forall x. IntLikeSet x -> IntSet
unIntLikeSet
{-# INLINE size #-}

null :: IntLikeSet x -> Bool
null :: forall x. IntLikeSet x -> Bool
null = IntSet -> Bool
IntSet.null (IntSet -> Bool)
-> (IntLikeSet x -> IntSet) -> IntLikeSet x -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. IntLikeSet x -> IntSet
forall x. IntLikeSet x -> IntSet
unIntLikeSet
{-# INLINE null #-}

member :: Coercible x Int => x -> IntLikeSet x -> Bool
member :: forall x. Coercible x Int => x -> IntLikeSet x -> Bool
member x
x = Int -> IntSet -> Bool
IntSet.member (x -> Int
forall a b. Coercible a b => a -> b
coerce x
x) (IntSet -> Bool)
-> (IntLikeSet x -> IntSet) -> IntLikeSet x -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. IntLikeSet x -> IntSet
forall x. IntLikeSet x -> IntSet
unIntLikeSet
{-# INLINE member #-}

toList :: Coercible x Int => IntLikeSet x -> [x]
toList :: forall x. Coercible x Int => IntLikeSet x -> [x]
toList = [Int] -> [x]
forall a b. Coercible a b => a -> b
coerce ([Int] -> [x]) -> (IntLikeSet x -> [Int]) -> IntLikeSet x -> [x]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. IntSet -> [Int]
IntSet.toList (IntSet -> [Int])
-> (IntLikeSet x -> IntSet) -> IntLikeSet x -> [Int]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. IntLikeSet x -> IntSet
forall x. IntLikeSet x -> IntSet
unIntLikeSet
{-# INLINE toList #-}

insert :: Coercible x Int => x -> IntLikeSet x -> IntLikeSet x
insert :: forall x. Coercible x Int => x -> IntLikeSet x -> IntLikeSet x
insert x
x = IntSet -> IntLikeSet x
forall x. IntSet -> IntLikeSet x
IntLikeSet (IntSet -> IntLikeSet x)
-> (IntLikeSet x -> IntSet) -> IntLikeSet x -> IntLikeSet x
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> IntSet -> IntSet
IntSet.insert (x -> Int
forall a b. Coercible a b => a -> b
coerce x
x) (IntSet -> IntSet)
-> (IntLikeSet x -> IntSet) -> IntLikeSet x -> IntSet
forall b c a. (b -> c) -> (a -> b) -> a -> c
. IntLikeSet x -> IntSet
forall x. IntLikeSet x -> IntSet
unIntLikeSet
{-# INLINE insert #-}

delete :: Coercible x Int => x -> IntLikeSet x -> IntLikeSet x
delete :: forall x. Coercible x Int => x -> IntLikeSet x -> IntLikeSet x
delete x
x = IntSet -> IntLikeSet x
forall x. IntSet -> IntLikeSet x
IntLikeSet (IntSet -> IntLikeSet x)
-> (IntLikeSet x -> IntSet) -> IntLikeSet x -> IntLikeSet x
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> IntSet -> IntSet
IntSet.delete (x -> Int
forall a b. Coercible a b => a -> b
coerce x
x) (IntSet -> IntSet)
-> (IntLikeSet x -> IntSet) -> IntLikeSet x -> IntSet
forall b c a. (b -> c) -> (a -> b) -> a -> c
. IntLikeSet x -> IntSet
forall x. IntLikeSet x -> IntSet
unIntLikeSet
{-# INLINE delete #-}

isSubsetOf :: IntLikeSet x -> IntLikeSet x -> Bool
isSubsetOf :: forall x. IntLikeSet x -> IntLikeSet x -> Bool
isSubsetOf IntLikeSet x
xs IntLikeSet x
ys = IntSet -> IntSet -> Bool
IntSet.isSubsetOf (IntLikeSet x -> IntSet
forall x. IntLikeSet x -> IntSet
unIntLikeSet IntLikeSet x
xs) (IntLikeSet x -> IntSet
forall x. IntLikeSet x -> IntSet
unIntLikeSet IntLikeSet x
ys)
{-# INLINE isSubsetOf #-}

intersection :: IntLikeSet x -> IntLikeSet x -> IntLikeSet x
intersection :: forall x. IntLikeSet x -> IntLikeSet x -> IntLikeSet x
intersection IntLikeSet x
xs IntLikeSet x
ys = IntSet -> IntLikeSet x
forall x. IntSet -> IntLikeSet x
IntLikeSet (IntSet -> IntSet -> IntSet
IntSet.intersection (IntLikeSet x -> IntSet
forall x. IntLikeSet x -> IntSet
unIntLikeSet IntLikeSet x
xs) (IntLikeSet x -> IntSet
forall x. IntLikeSet x -> IntSet
unIntLikeSet IntLikeSet x
ys))
{-# INLINE intersection #-}

difference :: IntLikeSet x -> IntLikeSet x -> IntLikeSet x
difference :: forall x. IntLikeSet x -> IntLikeSet x -> IntLikeSet x
difference IntLikeSet x
xs IntLikeSet x
ys = IntSet -> IntLikeSet x
forall x. IntSet -> IntLikeSet x
IntLikeSet (IntSet -> IntSet -> IntSet
IntSet.difference (IntLikeSet x -> IntSet
forall x. IntLikeSet x -> IntSet
unIntLikeSet IntLikeSet x
xs) (IntLikeSet x -> IntSet
forall x. IntLikeSet x -> IntSet
unIntLikeSet IntLikeSet x
ys))
{-# INLINE difference #-}

union :: IntLikeSet x -> IntLikeSet x -> IntLikeSet x
union :: forall x. IntLikeSet x -> IntLikeSet x -> IntLikeSet x
union IntLikeSet x
xs IntLikeSet x
ys = IntSet -> IntLikeSet x
forall x. IntSet -> IntLikeSet x
IntLikeSet (IntSet -> IntSet -> IntSet
IntSet.union (IntLikeSet x -> IntSet
forall x. IntLikeSet x -> IntSet
unIntLikeSet IntLikeSet x
xs) (IntLikeSet x -> IntSet
forall x. IntLikeSet x -> IntSet
unIntLikeSet IntLikeSet x
ys))
{-# INLINE union #-}

-- Copied here because coercion through f is difficult
unions :: Foldable f => f (IntLikeSet x) -> IntLikeSet x
unions :: forall (f :: * -> *) x.
Foldable f =>
f (IntLikeSet x) -> IntLikeSet x
unions = (IntLikeSet x -> IntLikeSet x -> IntLikeSet x)
-> IntLikeSet x -> f (IntLikeSet x) -> IntLikeSet x
forall b a. (b -> a -> b) -> b -> f a -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' IntLikeSet x -> IntLikeSet x -> IntLikeSet x
forall x. IntLikeSet x -> IntLikeSet x -> IntLikeSet x
union IntLikeSet x
forall x. IntLikeSet x
empty
{-# INLINE unions #-}

findMin :: Coercible x Int => IntLikeSet x -> x
findMin :: forall x. Coercible x Int => IntLikeSet x -> x
findMin = Int -> x
forall a b. Coercible a b => a -> b
coerce (Int -> x) -> (IntLikeSet x -> Int) -> IntLikeSet x -> x
forall b c a. (b -> c) -> (a -> b) -> a -> c
. IntSet -> Int
IntSet.findMin (IntSet -> Int) -> (IntLikeSet x -> IntSet) -> IntLikeSet x -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. IntLikeSet x -> IntSet
forall x. IntLikeSet x -> IntSet
unIntLikeSet
{-# INLINE findMin #-}

minView :: Coercible x Int => IntLikeSet x -> Maybe (x, IntLikeSet x)
minView :: forall x.
Coercible x Int =>
IntLikeSet x -> Maybe (x, IntLikeSet x)
minView = Maybe (Int, IntSet) -> Maybe (x, IntLikeSet x)
forall a b. Coercible a b => a -> b
coerce (Maybe (Int, IntSet) -> Maybe (x, IntLikeSet x))
-> (IntLikeSet x -> Maybe (Int, IntSet))
-> IntLikeSet x
-> Maybe (x, IntLikeSet x)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. IntSet -> Maybe (Int, IntSet)
IntSet.minView (IntSet -> Maybe (Int, IntSet))
-> (IntLikeSet x -> IntSet) -> IntLikeSet x -> Maybe (Int, IntSet)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. IntLikeSet x -> IntSet
forall x. IntLikeSet x -> IntSet
unIntLikeSet
{-# INLINE minView #-}

disjoint :: IntLikeSet x -> IntLikeSet x -> Bool
disjoint :: forall x. IntLikeSet x -> IntLikeSet x -> Bool
disjoint IntLikeSet x
a IntLikeSet x
b = IntSet -> IntSet -> Bool
IntSet.disjoint (IntLikeSet x -> IntSet
forall x. IntLikeSet x -> IntSet
unIntLikeSet IntLikeSet x
a) (IntLikeSet x -> IntSet
forall x. IntLikeSet x -> IntSet
unIntLikeSet IntLikeSet x
b)
{-# INLINE disjoint #-}

map :: (Coercible x Int, Coercible y Int) => (x -> y) -> IntLikeSet x -> IntLikeSet y
map :: forall x y.
(Coercible x Int, Coercible y Int) =>
(x -> y) -> IntLikeSet x -> IntLikeSet y
map x -> y
f = IntSet -> IntLikeSet y
forall x. IntSet -> IntLikeSet x
IntLikeSet (IntSet -> IntLikeSet y)
-> (IntLikeSet x -> IntSet) -> IntLikeSet x -> IntLikeSet y
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int -> Int) -> IntSet -> IntSet
IntSet.map ((x -> y) -> Int -> Int
forall a b. Coercible a b => a -> b
coerce x -> y
f) (IntSet -> IntSet)
-> (IntLikeSet x -> IntSet) -> IntLikeSet x -> IntSet
forall b c a. (b -> c) -> (a -> b) -> a -> c
. IntLikeSet x -> IntSet
forall x. IntLikeSet x -> IntSet
unIntLikeSet
{-# INLINE map #-}

filter :: (Coercible x Int) => (x -> Bool) -> IntLikeSet x -> IntLikeSet x
filter :: forall x.
Coercible x Int =>
(x -> Bool) -> IntLikeSet x -> IntLikeSet x
filter x -> Bool
f = IntSet -> IntLikeSet x
forall x. IntSet -> IntLikeSet x
IntLikeSet (IntSet -> IntLikeSet x)
-> (IntLikeSet x -> IntSet) -> IntLikeSet x -> IntLikeSet x
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int -> Bool) -> IntSet -> IntSet
IntSet.filter ((x -> Bool) -> Int -> Bool
forall a b. Coercible a b => a -> b
coerce x -> Bool
f) (IntSet -> IntSet)
-> (IntLikeSet x -> IntSet) -> IntLikeSet x -> IntSet
forall b c a. (b -> c) -> (a -> b) -> a -> c
. IntLikeSet x -> IntSet
forall x. IntLikeSet x -> IntSet
unIntLikeSet
{-# INLINE filter #-}

insertState :: Coercible x Int => (Bool -> b) -> x -> IntLikeSet x -> (b, IntLikeSet x)
insertState :: forall x b.
Coercible x Int =>
(Bool -> b) -> x -> IntLikeSet x -> (b, IntLikeSet x)
insertState Bool -> b
f x
x = (b, IntSet) -> (b, IntLikeSet x)
forall a b. Coercible a b => a -> b
coerce ((b, IntSet) -> (b, IntLikeSet x))
-> (IntLikeSet x -> (b, IntSet))
-> IntLikeSet x
-> (b, IntLikeSet x)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Bool -> (b, Bool)) -> Int -> IntSet -> (b, IntSet)
forall (f :: * -> *).
Functor f =>
(Bool -> f Bool) -> Int -> IntSet -> f IntSet
IntSet.alterF (\Bool
b -> (Bool -> b
f Bool
b, Bool
True)) (x -> Int
forall a b. Coercible a b => a -> b
coerce x
x) (IntSet -> (b, IntSet))
-> (IntLikeSet x -> IntSet) -> IntLikeSet x -> (b, IntSet)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. IntLikeSet x -> IntSet
forall x. IntLikeSet x -> IntSet
unIntLikeSet
{-# INLINE insertState #-}

orderedPairs :: Coercible x Int => IntLikeSet x -> [(x, x)]
orderedPairs :: forall x. Coercible x Int => IntLikeSet x -> [(x, x)]
orderedPairs IntLikeSet x
s = let vs :: [x]
vs = IntLikeSet x -> [x]
forall x. Coercible x Int => IntLikeSet x -> [x]
toList IntLikeSet x
s in [(x
x, x
y) | x
x <- [x]
vs, x
y <- [x]
vs]

unorderedPairs :: Coercible x Int => IntLikeSet x -> [(x, x)]
unorderedPairs :: forall x. Coercible x Int => IntLikeSet x -> [(x, x)]
unorderedPairs = [x] -> [(x, x)]
forall {b}. [b] -> [(b, b)]
go1 ([x] -> [(x, x)])
-> (IntLikeSet x -> [x]) -> IntLikeSet x -> [(x, x)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. IntLikeSet x -> [x]
forall x. Coercible x Int => IntLikeSet x -> [x]
toList
 where
  go1 :: [b] -> [(b, b)]
go1 [b]
vs =
    case [b]
vs of
      [] -> []
      b
x : [b]
xs -> b -> [b] -> [b] -> [(b, b)]
go2 b
x [b]
xs [b]
xs
  go2 :: b -> [b] -> [b] -> [(b, b)]
go2 b
x [b]
vl [b]
vs =
    case [b]
vl of
      [] -> [b] -> [(b, b)]
go1 [b]
vs
      b
y : [b]
vl' -> (b
x, b
y) (b, b) -> [(b, b)] -> [(b, b)]
forall a. a -> [a] -> [a]
: b -> [b] -> [b] -> [(b, b)]
go2 b
x [b]
vl' [b]
vs