-- | Small sets represented as immutable bit arrays for fast membership checking.
--
-- Membership checking is O(1), but all other operations are O(n)
-- where n is the size of the element type.
-- The element type needs to implement 'Bounded' and 'Ix'.
--
-- Mimics the interface of 'Data.Set'.
--
-- Import as:
-- @
--    import qualified Agda.Utils.SmallSet as SmallSet
--    import Agda.Utils.SmallSet (SmallSet)
-- @

{-# LANGUAGE DeriveDataTypeable #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}

module Agda.Utils.SmallSet
  ( SmallSet()
  , Ix
  , (\\)
  , complement
  , delete
  , difference
  , elems
  , empty
  , fromList, fromAscList, fromDistinctAscList
  , insert
  , intersection
  , isSubsetOf
  , mapMemberShip
  , member
  , notMember
  , null
  , singleton
  , toList, toAscList
  , total
  , union
  , zipMemberShipWith
  ) where

import Prelude hiding (null)

import Data.Array.IArray (Ix, Array)
import qualified Data.Array.IArray as Array
import Data.Data (Data)

-- Note: we might want to use unboxed arrays, but they have no Data instance

-- | Let @n@ be the size of type @a@.
type SmallSetElement a = (Bounded a, Ix a)
newtype SmallSet a = SmallSet { SmallSet a -> Array a Bool
theSmallSet :: Array a Bool }
  deriving (SmallSet a -> SmallSet a -> Bool
(SmallSet a -> SmallSet a -> Bool)
-> (SmallSet a -> SmallSet a -> Bool) -> Eq (SmallSet a)
forall a. Ix a => SmallSet a -> SmallSet a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: SmallSet a -> SmallSet a -> Bool
$c/= :: forall a. Ix a => SmallSet a -> SmallSet a -> Bool
== :: SmallSet a -> SmallSet a -> Bool
$c== :: forall a. Ix a => SmallSet a -> SmallSet a -> Bool
Eq, Eq (SmallSet a)
Eq (SmallSet a)
-> (SmallSet a -> SmallSet a -> Ordering)
-> (SmallSet a -> SmallSet a -> Bool)
-> (SmallSet a -> SmallSet a -> Bool)
-> (SmallSet a -> SmallSet a -> Bool)
-> (SmallSet a -> SmallSet a -> Bool)
-> (SmallSet a -> SmallSet a -> SmallSet a)
-> (SmallSet a -> SmallSet a -> SmallSet a)
-> Ord (SmallSet a)
SmallSet a -> SmallSet a -> Bool
SmallSet a -> SmallSet a -> Ordering
SmallSet a -> SmallSet a -> SmallSet a
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 a. Ix a => Eq (SmallSet a)
forall a. Ix a => SmallSet a -> SmallSet a -> Bool
forall a. Ix a => SmallSet a -> SmallSet a -> Ordering
forall a. Ix a => SmallSet a -> SmallSet a -> SmallSet a
min :: SmallSet a -> SmallSet a -> SmallSet a
$cmin :: forall a. Ix a => SmallSet a -> SmallSet a -> SmallSet a
max :: SmallSet a -> SmallSet a -> SmallSet a
$cmax :: forall a. Ix a => SmallSet a -> SmallSet a -> SmallSet a
>= :: SmallSet a -> SmallSet a -> Bool
$c>= :: forall a. Ix a => SmallSet a -> SmallSet a -> Bool
> :: SmallSet a -> SmallSet a -> Bool
$c> :: forall a. Ix a => SmallSet a -> SmallSet a -> Bool
<= :: SmallSet a -> SmallSet a -> Bool
$c<= :: forall a. Ix a => SmallSet a -> SmallSet a -> Bool
< :: SmallSet a -> SmallSet a -> Bool
$c< :: forall a. Ix a => SmallSet a -> SmallSet a -> Bool
compare :: SmallSet a -> SmallSet a -> Ordering
$ccompare :: forall a. Ix a => SmallSet a -> SmallSet a -> Ordering
$cp1Ord :: forall a. Ix a => Eq (SmallSet a)
Ord, Int -> SmallSet a -> ShowS
[SmallSet a] -> ShowS
SmallSet a -> String
(Int -> SmallSet a -> ShowS)
-> (SmallSet a -> String)
-> ([SmallSet a] -> ShowS)
-> Show (SmallSet a)
forall a. (Ix a, Show a) => Int -> SmallSet a -> ShowS
forall a. (Ix a, Show a) => [SmallSet a] -> ShowS
forall a. (Ix a, Show a) => SmallSet a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [SmallSet a] -> ShowS
$cshowList :: forall a. (Ix a, Show a) => [SmallSet a] -> ShowS
show :: SmallSet a -> String
$cshow :: forall a. (Ix a, Show a) => SmallSet a -> String
showsPrec :: Int -> SmallSet a -> ShowS
$cshowsPrec :: forall a. (Ix a, Show a) => Int -> SmallSet a -> ShowS
Show, Typeable (SmallSet a)
DataType
Constr
Typeable (SmallSet a)
-> (forall (c :: * -> *).
    (forall d b. Data d => c (d -> b) -> d -> c b)
    -> (forall g. g -> c g) -> SmallSet a -> c (SmallSet a))
-> (forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c (SmallSet a))
-> (SmallSet a -> Constr)
-> (SmallSet a -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c (SmallSet a)))
-> (forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e))
    -> Maybe (c (SmallSet a)))
-> ((forall b. Data b => b -> b) -> SmallSet a -> SmallSet a)
-> (forall r r'.
    (r -> r' -> r)
    -> r -> (forall d. Data d => d -> r') -> SmallSet a -> r)
-> (forall r r'.
    (r' -> r -> r)
    -> r -> (forall d. Data d => d -> r') -> SmallSet a -> r)
-> (forall u. (forall d. Data d => d -> u) -> SmallSet a -> [u])
-> (forall u.
    Int -> (forall d. Data d => d -> u) -> SmallSet a -> u)
-> (forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d) -> SmallSet a -> m (SmallSet a))
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> SmallSet a -> m (SmallSet a))
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> SmallSet a -> m (SmallSet a))
-> Data (SmallSet a)
SmallSet a -> DataType
SmallSet a -> Constr
(forall d. Data d => c (t d)) -> Maybe (c (SmallSet a))
(forall b. Data b => b -> b) -> SmallSet a -> SmallSet a
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> SmallSet a -> c (SmallSet a)
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (SmallSet a)
forall a. (Data a, Ix a) => Typeable (SmallSet a)
forall a. (Data a, Ix a) => SmallSet a -> DataType
forall a. (Data a, Ix a) => SmallSet a -> Constr
forall a.
(Data a, Ix a) =>
(forall b. Data b => b -> b) -> SmallSet a -> SmallSet a
forall a u.
(Data a, Ix a) =>
Int -> (forall d. Data d => d -> u) -> SmallSet a -> u
forall a u.
(Data a, Ix a) =>
(forall d. Data d => d -> u) -> SmallSet a -> [u]
forall a r r'.
(Data a, Ix a) =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> SmallSet a -> r
forall a r r'.
(Data a, Ix a) =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> SmallSet a -> r
forall a (m :: * -> *).
(Data a, Ix a, Monad m) =>
(forall d. Data d => d -> m d) -> SmallSet a -> m (SmallSet a)
forall a (m :: * -> *).
(Data a, Ix a, MonadPlus m) =>
(forall d. Data d => d -> m d) -> SmallSet a -> m (SmallSet a)
forall a (c :: * -> *).
(Data a, Ix a) =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (SmallSet a)
forall a (c :: * -> *).
(Data a, Ix a) =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> SmallSet a -> c (SmallSet a)
forall a (t :: * -> *) (c :: * -> *).
(Data a, Ix a, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (SmallSet a))
forall a (t :: * -> * -> *) (c :: * -> *).
(Data a, Ix a, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (SmallSet a))
forall a.
Typeable a
-> (forall (c :: * -> *).
    (forall d b. Data d => c (d -> b) -> d -> c b)
    -> (forall g. g -> c g) -> a -> c a)
-> (forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c a)
-> (a -> Constr)
-> (a -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c a))
-> (forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c a))
-> ((forall b. Data b => b -> b) -> a -> a)
-> (forall r r'.
    (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall r r'.
    (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall u. (forall d. Data d => d -> u) -> a -> [u])
-> (forall u. Int -> (forall d. Data d => d -> u) -> a -> u)
-> (forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> Data a
forall u. Int -> (forall d. Data d => d -> u) -> SmallSet a -> u
forall u. (forall d. Data d => d -> u) -> SmallSet a -> [u]
forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> SmallSet a -> r
forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> SmallSet a -> r
forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> SmallSet a -> m (SmallSet a)
forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> SmallSet a -> m (SmallSet a)
forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (SmallSet a)
forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> SmallSet a -> c (SmallSet a)
forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c (SmallSet a))
forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (SmallSet a))
$cSmallSet :: Constr
$tSmallSet :: DataType
gmapMo :: (forall d. Data d => d -> m d) -> SmallSet a -> m (SmallSet a)
$cgmapMo :: forall a (m :: * -> *).
(Data a, Ix a, MonadPlus m) =>
(forall d. Data d => d -> m d) -> SmallSet a -> m (SmallSet a)
gmapMp :: (forall d. Data d => d -> m d) -> SmallSet a -> m (SmallSet a)
$cgmapMp :: forall a (m :: * -> *).
(Data a, Ix a, MonadPlus m) =>
(forall d. Data d => d -> m d) -> SmallSet a -> m (SmallSet a)
gmapM :: (forall d. Data d => d -> m d) -> SmallSet a -> m (SmallSet a)
$cgmapM :: forall a (m :: * -> *).
(Data a, Ix a, Monad m) =>
(forall d. Data d => d -> m d) -> SmallSet a -> m (SmallSet a)
gmapQi :: Int -> (forall d. Data d => d -> u) -> SmallSet a -> u
$cgmapQi :: forall a u.
(Data a, Ix a) =>
Int -> (forall d. Data d => d -> u) -> SmallSet a -> u
gmapQ :: (forall d. Data d => d -> u) -> SmallSet a -> [u]
$cgmapQ :: forall a u.
(Data a, Ix a) =>
(forall d. Data d => d -> u) -> SmallSet a -> [u]
gmapQr :: (r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> SmallSet a -> r
$cgmapQr :: forall a r r'.
(Data a, Ix a) =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> SmallSet a -> r
gmapQl :: (r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> SmallSet a -> r
$cgmapQl :: forall a r r'.
(Data a, Ix a) =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> SmallSet a -> r
gmapT :: (forall b. Data b => b -> b) -> SmallSet a -> SmallSet a
$cgmapT :: forall a.
(Data a, Ix a) =>
(forall b. Data b => b -> b) -> SmallSet a -> SmallSet a
dataCast2 :: (forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (SmallSet a))
$cdataCast2 :: forall a (t :: * -> * -> *) (c :: * -> *).
(Data a, Ix a, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (SmallSet a))
dataCast1 :: (forall d. Data d => c (t d)) -> Maybe (c (SmallSet a))
$cdataCast1 :: forall a (t :: * -> *) (c :: * -> *).
(Data a, Ix a, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (SmallSet a))
dataTypeOf :: SmallSet a -> DataType
$cdataTypeOf :: forall a. (Data a, Ix a) => SmallSet a -> DataType
toConstr :: SmallSet a -> Constr
$ctoConstr :: forall a. (Data a, Ix a) => SmallSet a -> Constr
gunfold :: (forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (SmallSet a)
$cgunfold :: forall a (c :: * -> *).
(Data a, Ix a) =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (SmallSet a)
gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> SmallSet a -> c (SmallSet a)
$cgfoldl :: forall a (c :: * -> *).
(Data a, Ix a) =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> SmallSet a -> c (SmallSet a)
$cp1Data :: forall a. (Data a, Ix a) => Typeable (SmallSet a)
Data)

-- * Query

-- | Time O(n)!
null :: SmallSetElement a => SmallSet a -> Bool
null :: SmallSet a -> Bool
null = (Bool -> Bool) -> [Bool] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all (Bool -> Bool -> Bool
forall a. Eq a => a -> a -> Bool
== Bool
False) ([Bool] -> Bool) -> (SmallSet a -> [Bool]) -> SmallSet a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Array a Bool -> [Bool]
forall (a :: * -> * -> *) e i. (IArray a e, Ix i) => a i e -> [e]
Array.elems (Array a Bool -> [Bool])
-> (SmallSet a -> Array a Bool) -> SmallSet a -> [Bool]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. SmallSet a -> Array a Bool
forall a. SmallSet a -> Array a Bool
theSmallSet

-- | Time O(1).
member :: SmallSetElement a => a -> SmallSet a -> Bool
member :: a -> SmallSet a -> Bool
member a
a SmallSet a
s = SmallSet a -> Array a Bool
forall a. SmallSet a -> Array a Bool
theSmallSet SmallSet a
s Array a Bool -> a -> Bool
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> i -> e
Array.! a
a

-- | @not . member a@.  Time O(1).
notMember :: SmallSetElement a => a -> SmallSet a -> Bool
notMember :: a -> SmallSet a -> Bool
notMember a
a = Bool -> Bool
not (Bool -> Bool) -> (SmallSet a -> Bool) -> SmallSet a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> SmallSet a -> Bool
forall a. SmallSetElement a => a -> SmallSet a -> Bool
member a
a

-- | Time O(n).
isSubsetOf ::  SmallSetElement a => SmallSet a -> SmallSet a -> Bool
isSubsetOf :: SmallSet a -> SmallSet a -> Bool
isSubsetOf SmallSet a
s SmallSet a
t = [Bool] -> Bool
forall (t :: * -> *). Foldable t => t Bool -> Bool
and ([Bool] -> Bool) -> [Bool] -> Bool
forall a b. (a -> b) -> a -> b
$ (Bool -> Bool -> Bool) -> SmallSet a -> SmallSet a -> [Bool]
forall a.
SmallSetElement a =>
(Bool -> Bool -> Bool) -> SmallSet a -> SmallSet a -> [Bool]
toBoolListZipWith Bool -> Bool -> Bool
implies SmallSet a
s SmallSet a
t
  where implies :: Bool -> Bool -> Bool
implies Bool
a Bool
b = if Bool
a then Bool
b else Bool
True

-- * Construction

-- | The empty set.  Time O(n).
empty :: SmallSetElement a => SmallSet a
empty :: SmallSet a
empty = [Bool] -> SmallSet a
forall a. SmallSetElement a => [Bool] -> SmallSet a
fromBoolList (Bool -> [Bool]
forall a. a -> [a]
repeat Bool
False)

-- | The full set.  Time O(n).
total :: SmallSetElement a => SmallSet a
total :: SmallSet a
total = [Bool] -> SmallSet a
forall a. SmallSetElement a => [Bool] -> SmallSet a
fromBoolList (Bool -> [Bool]
forall a. a -> [a]
repeat Bool
True)

-- | A singleton set.  Time O(n).
singleton :: SmallSetElement a => a -> SmallSet a
singleton :: a -> SmallSet a
singleton a
a = [a] -> SmallSet a
forall a. SmallSetElement a => [a] -> SmallSet a
fromList [a
a]

-- | Time O(n).
insert :: SmallSetElement a => a -> SmallSet a -> SmallSet a
insert :: a -> SmallSet a -> SmallSet a
insert a
a = [(a, Bool)] -> SmallSet a -> SmallSet a
forall a.
SmallSetElement a =>
[(a, Bool)] -> SmallSet a -> SmallSet a
update [(a
a,Bool
True)]

-- | Time O(n).
delete :: SmallSetElement a => a -> SmallSet a -> SmallSet a
delete :: a -> SmallSet a -> SmallSet a
delete a
a = [(a, Bool)] -> SmallSet a -> SmallSet a
forall a.
SmallSetElement a =>
[(a, Bool)] -> SmallSet a -> SmallSet a
update [(a
a,Bool
False)]

-- * Combine

-- | Time O(n).
complement :: SmallSetElement a => SmallSet a -> SmallSet a
complement :: SmallSet a -> SmallSet a
complement = (Bool -> Bool) -> SmallSet a -> SmallSet a
forall a.
SmallSetElement a =>
(Bool -> Bool) -> SmallSet a -> SmallSet a
mapMemberShip Bool -> Bool
not

-- | Time O(n).
difference, (\\) :: SmallSetElement a => SmallSet a -> SmallSet a -> SmallSet a
difference :: SmallSet a -> SmallSet a -> SmallSet a
difference = (Bool -> Bool -> Bool) -> SmallSet a -> SmallSet a -> SmallSet a
forall a.
SmallSetElement a =>
(Bool -> Bool -> Bool) -> SmallSet a -> SmallSet a -> SmallSet a
zipMemberShipWith ((Bool -> Bool -> Bool) -> SmallSet a -> SmallSet a -> SmallSet a)
-> (Bool -> Bool -> Bool) -> SmallSet a -> SmallSet a -> SmallSet a
forall a b. (a -> b) -> a -> b
$ \ Bool
b Bool
c -> Bool
b Bool -> Bool -> Bool
&& Bool -> Bool
not Bool
c
\\ :: SmallSet a -> SmallSet a -> SmallSet a
(\\)       = SmallSet a -> SmallSet a -> SmallSet a
forall a.
SmallSetElement a =>
SmallSet a -> SmallSet a -> SmallSet a
difference

-- | Time O(n).
intersection ::  SmallSetElement a => SmallSet a -> SmallSet a -> SmallSet a
intersection :: SmallSet a -> SmallSet a -> SmallSet a
intersection = (Bool -> Bool -> Bool) -> SmallSet a -> SmallSet a -> SmallSet a
forall a.
SmallSetElement a =>
(Bool -> Bool -> Bool) -> SmallSet a -> SmallSet a -> SmallSet a
zipMemberShipWith Bool -> Bool -> Bool
(&&)

-- | Time O(n).
union ::  SmallSetElement a => SmallSet a -> SmallSet a -> SmallSet a
union :: SmallSet a -> SmallSet a -> SmallSet a
union = (Bool -> Bool -> Bool) -> SmallSet a -> SmallSet a -> SmallSet a
forall a.
SmallSetElement a =>
(Bool -> Bool -> Bool) -> SmallSet a -> SmallSet a -> SmallSet a
zipMemberShipWith Bool -> Bool -> Bool
(||)

-- | Time O(n).
mapMemberShip :: SmallSetElement a => (Bool -> Bool) -> SmallSet a -> SmallSet a
mapMemberShip :: (Bool -> Bool) -> SmallSet a -> SmallSet a
mapMemberShip Bool -> Bool
f = Array a Bool -> SmallSet a
forall a. Array a Bool -> SmallSet a
SmallSet (Array a Bool -> SmallSet a)
-> (SmallSet a -> Array a Bool) -> SmallSet a -> SmallSet a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Bool -> Bool) -> Array a Bool -> Array a Bool
forall (a :: * -> * -> *) e' e i.
(IArray a e', IArray a e, Ix i) =>
(e' -> e) -> a i e' -> a i e
Array.amap Bool -> Bool
f (Array a Bool -> Array a Bool)
-> (SmallSet a -> Array a Bool) -> SmallSet a -> Array a Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. SmallSet a -> Array a Bool
forall a. SmallSet a -> Array a Bool
theSmallSet

-- | Time O(n).
zipMemberShipWith :: SmallSetElement a => (Bool -> Bool -> Bool) -> SmallSet a -> SmallSet a -> SmallSet a
zipMemberShipWith :: (Bool -> Bool -> Bool) -> SmallSet a -> SmallSet a -> SmallSet a
zipMemberShipWith Bool -> Bool -> Bool
f SmallSet a
s SmallSet a
t = [Bool] -> SmallSet a
forall a. SmallSetElement a => [Bool] -> SmallSet a
fromBoolList ([Bool] -> SmallSet a) -> [Bool] -> SmallSet a
forall a b. (a -> b) -> a -> b
$ (Bool -> Bool -> Bool) -> SmallSet a -> SmallSet a -> [Bool]
forall a.
SmallSetElement a =>
(Bool -> Bool -> Bool) -> SmallSet a -> SmallSet a -> [Bool]
toBoolListZipWith Bool -> Bool -> Bool
f SmallSet a
s SmallSet a
t

-- * Conversion

-- | Time O(n).
elems, toList, toAscList :: SmallSetElement a => SmallSet a -> [a]
elems :: SmallSet a -> [a]
elems     = ((a, Bool) -> a) -> [(a, Bool)] -> [a]
forall a b. (a -> b) -> [a] -> [b]
map (a, Bool) -> a
forall a b. (a, b) -> a
fst ([(a, Bool)] -> [a])
-> (SmallSet a -> [(a, Bool)]) -> SmallSet a -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((a, Bool) -> Bool) -> [(a, Bool)] -> [(a, Bool)]
forall a. (a -> Bool) -> [a] -> [a]
filter (a, Bool) -> Bool
forall a b. (a, b) -> b
snd ([(a, Bool)] -> [(a, Bool)])
-> (SmallSet a -> [(a, Bool)]) -> SmallSet a -> [(a, Bool)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Array a Bool -> [(a, Bool)]
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> [(i, e)]
Array.assocs (Array a Bool -> [(a, Bool)])
-> (SmallSet a -> Array a Bool) -> SmallSet a -> [(a, Bool)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. SmallSet a -> Array a Bool
forall a. SmallSet a -> Array a Bool
theSmallSet
toList :: SmallSet a -> [a]
toList    = SmallSet a -> [a]
forall a. SmallSetElement a => SmallSet a -> [a]
elems
toAscList :: SmallSet a -> [a]
toAscList = SmallSet a -> [a]
forall a. SmallSetElement a => SmallSet a -> [a]
elems

-- | Time O(n).
fromList, fromAscList, fromDistinctAscList :: SmallSetElement a => [a] -> SmallSet a
fromList :: [a] -> SmallSet a
fromList            = ([(a, Bool)] -> SmallSet a -> SmallSet a)
-> SmallSet a -> [(a, Bool)] -> SmallSet a
forall a b c. (a -> b -> c) -> b -> a -> c
flip [(a, Bool)] -> SmallSet a -> SmallSet a
forall a.
SmallSetElement a =>
[(a, Bool)] -> SmallSet a -> SmallSet a
update SmallSet a
forall a. SmallSetElement a => SmallSet a
empty ([(a, Bool)] -> SmallSet a)
-> ([a] -> [(a, Bool)]) -> [a] -> SmallSet a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> (a, Bool)) -> [a] -> [(a, Bool)]
forall a b. (a -> b) -> [a] -> [b]
map (,Bool
True)
fromAscList :: [a] -> SmallSet a
fromAscList         = [a] -> SmallSet a
forall a. SmallSetElement a => [a] -> SmallSet a
fromList
fromDistinctAscList :: [a] -> SmallSet a
fromDistinctAscList = [a] -> SmallSet a
forall a. SmallSetElement a => [a] -> SmallSet a
fromList

-- * Internal

-- | Time O(n).  Assumes @Bool@-vector of length @n@.
fromBoolList :: SmallSetElement a => [Bool] -> SmallSet a
fromBoolList :: [Bool] -> SmallSet a
fromBoolList = Array a Bool -> SmallSet a
forall a. Array a Bool -> SmallSet a
SmallSet (Array a Bool -> SmallSet a)
-> ([Bool] -> Array a Bool) -> [Bool] -> SmallSet a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a, a) -> [Bool] -> Array a Bool
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
(i, i) -> [e] -> a i e
Array.listArray (a
forall a. Bounded a => a
minBound, a
forall a. Bounded a => a
maxBound)

-- | Time O(n).  Produces @Bool@-vector of length @n@.
toBoolList :: SmallSetElement a => SmallSet a -> [Bool]
toBoolList :: SmallSet a -> [Bool]
toBoolList = Array a Bool -> [Bool]
forall (a :: * -> * -> *) e i. (IArray a e, Ix i) => a i e -> [e]
Array.elems (Array a Bool -> [Bool])
-> (SmallSet a -> Array a Bool) -> SmallSet a -> [Bool]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. SmallSet a -> Array a Bool
forall a. SmallSet a -> Array a Bool
theSmallSet

-- | Time O(n).  Produces @Bool@-vector of length @n@.
toBoolListZipWith :: SmallSetElement a => (Bool -> Bool -> Bool) -> SmallSet a -> SmallSet a -> [Bool]
toBoolListZipWith :: (Bool -> Bool -> Bool) -> SmallSet a -> SmallSet a -> [Bool]
toBoolListZipWith Bool -> Bool -> Bool
f SmallSet a
s SmallSet a
t = (Bool -> Bool -> Bool) -> [Bool] -> [Bool] -> [Bool]
forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith Bool -> Bool -> Bool
f (SmallSet a -> [Bool]
forall a. SmallSetElement a => SmallSet a -> [Bool]
toBoolList SmallSet a
s) (SmallSet a -> [Bool]
forall a. SmallSetElement a => SmallSet a -> [Bool]
toBoolList SmallSet a
t)

-- | Time O(n).  Bulk insert/delete.
update :: SmallSetElement a => [(a,Bool)] -> SmallSet a -> SmallSet a
update :: [(a, Bool)] -> SmallSet a -> SmallSet a
update [(a, Bool)]
u SmallSet a
s = Array a Bool -> SmallSet a
forall a. Array a Bool -> SmallSet a
SmallSet (Array a Bool -> SmallSet a) -> Array a Bool -> SmallSet a
forall a b. (a -> b) -> a -> b
$ SmallSet a -> Array a Bool
forall a. SmallSet a -> Array a Bool
theSmallSet SmallSet a
s Array a Bool -> [(a, Bool)] -> Array a Bool
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> [(i, e)] -> a i e
Array.// [(a, Bool)]
u