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
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
showList :: [IntLikeSet x] -> ShowS
$cshowList :: forall x. [IntLikeSet x] -> ShowS
show :: IntLikeSet x -> String
$cshow :: forall x. IntLikeSet x -> String
showsPrec :: Int -> IntLikeSet x -> ShowS
$cshowsPrec :: forall x. Int -> IntLikeSet x -> ShowS
Show)
  deriving newtype (IntLikeSet x -> IntLikeSet x -> Bool
forall x. IntLikeSet x -> IntLikeSet x -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: 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
Eq, IntLikeSet x -> ()
forall x. IntLikeSet x -> ()
forall a. (a -> ()) -> NFData a
rnf :: IntLikeSet x -> ()
$crnf :: forall x. IntLikeSet x -> ()
NFData, NonEmpty (IntLikeSet x) -> IntLikeSet x
IntLikeSet x -> IntLikeSet x -> 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
stimes :: forall b. Integral b => b -> IntLikeSet x -> IntLikeSet x
$cstimes :: forall x b. Integral b => b -> IntLikeSet x -> IntLikeSet x
sconcat :: NonEmpty (IntLikeSet x) -> IntLikeSet x
$csconcat :: forall x. NonEmpty (IntLikeSet x) -> IntLikeSet x
<> :: IntLikeSet x -> IntLikeSet x -> IntLikeSet x
$c<> :: forall x. IntLikeSet x -> IntLikeSet x -> IntLikeSet x
Semigroup, 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
mconcat :: [IntLikeSet x] -> IntLikeSet x
$cmconcat :: forall x. [IntLikeSet x] -> IntLikeSet x
mappend :: IntLikeSet x -> IntLikeSet x -> IntLikeSet x
$cmappend :: forall x. IntLikeSet x -> IntLikeSet x -> IntLikeSet x
mempty :: IntLikeSet x
$cmempty :: forall x. IntLikeSet x
Monoid)

empty :: IntLikeSet x
empty :: forall x. IntLikeSet x
empty = 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 = forall x. IntSet -> IntLikeSet x
IntLikeSet forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> IntSet
IntSet.singleton forall b c a. (b -> c) -> (a -> b) -> a -> c
. coerce :: 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 = forall x. IntSet -> IntLikeSet x
IntLikeSet forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Int] -> IntSet
IntSet.fromList forall b c a. (b -> c) -> (a -> b) -> a -> c
. coerce :: 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 forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall x. IntLikeSet x -> IntSet
unIntLikeSet
{-# INLINE size #-}

null :: IntLikeSet x -> Bool
null :: forall x. IntLikeSet x -> Bool
null = IntSet -> Bool
IntSet.null forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 (coerce :: forall a b. Coercible a b => a -> b
coerce x
x) forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 = coerce :: forall a b. Coercible a b => a -> b
coerce forall b c a. (b -> c) -> (a -> b) -> a -> c
. IntSet -> [Int]
IntSet.toList forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 = forall x. IntSet -> IntLikeSet x
IntLikeSet forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> IntSet -> IntSet
IntSet.insert (coerce :: forall a b. Coercible a b => a -> b
coerce x
x) forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 = forall x. IntSet -> IntLikeSet x
IntLikeSet forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> IntSet -> IntSet
IntSet.delete (coerce :: forall a b. Coercible a b => a -> b
coerce x
x) forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 (forall x. IntLikeSet x -> IntSet
unIntLikeSet IntLikeSet x
xs) (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 = forall x. IntSet -> IntLikeSet x
IntLikeSet (IntSet -> IntSet -> IntSet
IntSet.intersection (forall x. IntLikeSet x -> IntSet
unIntLikeSet IntLikeSet x
xs) (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 = forall x. IntSet -> IntLikeSet x
IntLikeSet (IntSet -> IntSet -> IntSet
IntSet.difference (forall x. IntLikeSet x -> IntSet
unIntLikeSet IntLikeSet x
xs) (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 = forall x. IntSet -> IntLikeSet x
IntLikeSet (IntSet -> IntSet -> IntSet
IntSet.union (forall x. IntLikeSet x -> IntSet
unIntLikeSet IntLikeSet x
xs) (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 = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' forall x. IntLikeSet x -> IntLikeSet x -> IntLikeSet x
union forall x. IntLikeSet x
empty
{-# INLINE unions #-}

findMin :: Coercible x Int => IntLikeSet x -> x
findMin :: forall x. Coercible x Int => IntLikeSet x -> x
findMin = coerce :: forall a b. Coercible a b => a -> b
coerce forall b c a. (b -> c) -> (a -> b) -> a -> c
. IntSet -> Int
IntSet.findMin forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 = coerce :: forall a b. Coercible a b => a -> b
coerce forall b c a. (b -> c) -> (a -> b) -> a -> c
. IntSet -> Maybe (Int, IntSet)
IntSet.minView forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 (forall x. IntLikeSet x -> IntSet
unIntLikeSet IntLikeSet x
a) (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 = forall x. IntSet -> IntLikeSet x
IntLikeSet forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int -> Int) -> IntSet -> IntSet
IntSet.map (coerce :: forall a b. Coercible a b => a -> b
coerce x -> y
f) forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 = forall x. IntSet -> IntLikeSet x
IntLikeSet forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int -> Bool) -> IntSet -> IntSet
IntSet.filter (coerce :: forall a b. Coercible a b => a -> b
coerce x -> Bool
f) forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 = coerce :: forall a b. Coercible a b => a -> b
coerce forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (f :: * -> *).
Functor f =>
(Bool -> f Bool) -> Int -> IntSet -> f IntSet
IntSet.alterF (\Bool
b -> (Bool -> b
f Bool
b, Bool
True)) (coerce :: forall a b. Coercible a b => a -> b
coerce x
x) forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 = 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 = forall {b}. [b] -> [(b, b)]
go1 forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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) forall a. a -> [a] -> [a]
: b -> [b] -> [b] -> [(b, b)]
go2 b
x [b]
vl' [b]
vs