{-# OPTIONS_GHC -Wunused-imports #-}
module Agda.Utils.SmallSet
( SmallSet()
, SmallSetElement
, Ix
, (\\)
, complement
, delete
, difference
, elems
, empty
, fromList, fromAscList, fromDistinctAscList
, insert
, intersection
, member
, notMember
, null
, singleton
, toList, toAscList
, total
, union
) where
import Prelude hiding (null)
import Control.DeepSeq
import Data.Word (Word64)
import Data.List (foldl')
import Data.Bits hiding (complement)
import qualified Data.Bits as Bits
import Data.Ix
import qualified Agda.Utils.Null as Null
class (Bounded a, Ix a) => SmallSetElement a where
newtype SmallSet a = SmallSet { forall a. SmallSet a -> Word64
theSmallSet :: Word64 }
deriving (SmallSet a -> SmallSet a -> Bool
forall a. SmallSet a -> SmallSet a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: SmallSet a -> SmallSet a -> Bool
$c/= :: forall a. SmallSet a -> SmallSet a -> Bool
== :: SmallSet a -> SmallSet a -> Bool
$c== :: forall a. SmallSet a -> SmallSet a -> Bool
Eq, SmallSet a -> SmallSet a -> Bool
SmallSet a -> SmallSet a -> Ordering
SmallSet a -> SmallSet a -> SmallSet a
forall a. Eq (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. SmallSet a -> SmallSet a -> Bool
forall a. SmallSet a -> SmallSet a -> Ordering
forall a. SmallSet a -> SmallSet a -> SmallSet a
min :: SmallSet a -> SmallSet a -> SmallSet a
$cmin :: forall a. SmallSet a -> SmallSet a -> SmallSet a
max :: SmallSet a -> SmallSet a -> SmallSet a
$cmax :: forall a. SmallSet a -> SmallSet a -> SmallSet a
>= :: SmallSet a -> SmallSet a -> Bool
$c>= :: forall a. SmallSet a -> SmallSet a -> Bool
> :: SmallSet a -> SmallSet a -> Bool
$c> :: forall a. SmallSet a -> SmallSet a -> Bool
<= :: SmallSet a -> SmallSet a -> Bool
$c<= :: forall a. SmallSet a -> SmallSet a -> Bool
< :: SmallSet a -> SmallSet a -> Bool
$c< :: forall a. SmallSet a -> SmallSet a -> Bool
compare :: SmallSet a -> SmallSet a -> Ordering
$ccompare :: forall a. SmallSet a -> SmallSet a -> Ordering
Ord, Int -> SmallSet a -> ShowS
forall a. Int -> SmallSet a -> ShowS
forall a. [SmallSet a] -> ShowS
forall a. SmallSet a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [SmallSet a] -> ShowS
$cshowList :: forall a. [SmallSet a] -> ShowS
show :: SmallSet a -> String
$cshow :: forall a. SmallSet a -> String
showsPrec :: Int -> SmallSet a -> ShowS
$cshowsPrec :: forall a. Int -> SmallSet a -> ShowS
Show, SmallSet a -> ()
forall a. SmallSet a -> ()
forall a. (a -> ()) -> NFData a
rnf :: SmallSet a -> ()
$crnf :: forall a. SmallSet a -> ()
NFData)
instance SmallSetElement a => Null.Null (SmallSet a) where
empty :: SmallSet a
empty = forall a. SmallSetElement a => SmallSet a
empty
null :: SmallSet a -> Bool
null = forall a. SmallSetElement a => SmallSet a -> Bool
null
instance SmallSetElement a => Semigroup (SmallSet a) where
<> :: SmallSet a -> SmallSet a -> SmallSet a
(<>) = forall a.
SmallSetElement a =>
SmallSet a -> SmallSet a -> SmallSet a
union
instance SmallSetElement a => Monoid (SmallSet a) where
mempty :: SmallSet a
mempty = forall a. SmallSetElement a => SmallSet a
empty
null :: SmallSetElement a => SmallSet a -> Bool
null :: forall a. SmallSetElement a => SmallSet a -> Bool
null SmallSet a
s = forall a. SmallSet a -> Word64
theSmallSet SmallSet a
s forall a. Eq a => a -> a -> Bool
== Word64
0
member :: SmallSetElement a => a -> SmallSet a -> Bool
member :: forall a. SmallSetElement a => a -> SmallSet a -> Bool
member a
a SmallSet a
s = forall a. SmallSet a -> Word64
theSmallSet SmallSet a
s forall a. Bits a => a -> Int -> Bool
`testBit` forall a. SmallSetElement a => a -> Int
idx a
a
notMember :: SmallSetElement a => a -> SmallSet a -> Bool
notMember :: forall a. SmallSetElement a => a -> SmallSet a -> Bool
notMember a
a = Bool -> Bool
not forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. SmallSetElement a => a -> SmallSet a -> Bool
member a
a
empty :: SmallSetElement a => SmallSet a
empty :: forall a. SmallSetElement a => SmallSet a
empty = forall a. Word64 -> SmallSet a
SmallSet Word64
0
total :: forall a. SmallSetElement a => SmallSet a
total :: forall a. SmallSetElement a => SmallSet a
total = forall a. Word64 -> SmallSet a
SmallSet forall a b. (a -> b) -> a -> b
$ forall a. Bits a => a -> a
Bits.complement Word64
0
singleton :: SmallSetElement a => a -> SmallSet a
singleton :: forall a. SmallSetElement a => a -> SmallSet a
singleton a
a = forall a. Word64 -> SmallSet a
SmallSet forall a b. (a -> b) -> a -> b
$ forall a. Bits a => Int -> a
bit (forall a. SmallSetElement a => a -> Int
idx a
a)
insert :: SmallSetElement a => a -> SmallSet a -> SmallSet a
insert :: forall a. SmallSetElement a => a -> SmallSet a -> SmallSet a
insert a
a SmallSet a
s = forall a. Word64 -> SmallSet a
SmallSet forall a b. (a -> b) -> a -> b
$ forall a. SmallSet a -> Word64
theSmallSet SmallSet a
s forall a. Bits a => a -> Int -> a
`setBit` forall a. SmallSetElement a => a -> Int
idx a
a
delete :: SmallSetElement a => a -> SmallSet a -> SmallSet a
delete :: forall a. SmallSetElement a => a -> SmallSet a -> SmallSet a
delete a
a SmallSet a
s = forall a. Word64 -> SmallSet a
SmallSet forall a b. (a -> b) -> a -> b
$ forall a. SmallSet a -> Word64
theSmallSet SmallSet a
s forall a. Bits a => a -> Int -> a
`clearBit` forall a. SmallSetElement a => a -> Int
idx a
a
complement :: SmallSetElement a => SmallSet a -> SmallSet a
complement :: forall a. SmallSetElement a => SmallSet a -> SmallSet a
complement = forall a. Word64 -> SmallSet a
SmallSet forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Bits a => a -> a
Bits.complement forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. SmallSet a -> Word64
theSmallSet
difference, (\\) :: SmallSetElement a => SmallSet a -> SmallSet a -> SmallSet a
difference :: forall a.
SmallSetElement a =>
SmallSet a -> SmallSet a -> SmallSet a
difference SmallSet a
s SmallSet a
t = forall a. Word64 -> SmallSet a
SmallSet forall a b. (a -> b) -> a -> b
$ forall a. SmallSet a -> Word64
theSmallSet SmallSet a
s forall a. Bits a => a -> a -> a
.&. forall a. Bits a => a -> a
Bits.complement (forall a. SmallSet a -> Word64
theSmallSet SmallSet a
t)
\\ :: forall a.
SmallSetElement a =>
SmallSet a -> SmallSet a -> SmallSet a
(\\) = forall a.
SmallSetElement a =>
SmallSet a -> SmallSet a -> SmallSet a
difference
intersection :: SmallSetElement a => SmallSet a -> SmallSet a -> SmallSet a
intersection :: forall a.
SmallSetElement a =>
SmallSet a -> SmallSet a -> SmallSet a
intersection SmallSet a
s SmallSet a
t = forall a. Word64 -> SmallSet a
SmallSet forall a b. (a -> b) -> a -> b
$ forall a. SmallSet a -> Word64
theSmallSet SmallSet a
s forall a. Bits a => a -> a -> a
.&. forall a. SmallSet a -> Word64
theSmallSet SmallSet a
t
union :: SmallSetElement a => SmallSet a -> SmallSet a -> SmallSet a
union :: forall a.
SmallSetElement a =>
SmallSet a -> SmallSet a -> SmallSet a
union SmallSet a
s SmallSet a
t = forall a. Word64 -> SmallSet a
SmallSet forall a b. (a -> b) -> a -> b
$ forall a. SmallSet a -> Word64
theSmallSet SmallSet a
s forall a. Bits a => a -> a -> a
.|. forall a. SmallSet a -> Word64
theSmallSet SmallSet a
t
elems, toList, toAscList :: SmallSetElement a => SmallSet a -> [a]
elems :: forall a. SmallSetElement a => SmallSet a -> [a]
elems SmallSet a
s = forall a. (a -> Bool) -> [a] -> [a]
filter (\a
i -> forall a. SmallSet a -> Word64
theSmallSet SmallSet a
s forall a. Bits a => a -> Int -> Bool
`testBit` forall a. SmallSetElement a => a -> Int
idx a
i) (forall a. Ix a => (a, a) -> [a]
range forall a. SmallSetElement a => (a, a)
bounds)
toList :: forall a. SmallSetElement a => SmallSet a -> [a]
toList = forall a. SmallSetElement a => SmallSet a -> [a]
elems
toAscList :: forall a. SmallSetElement a => SmallSet a -> [a]
toAscList = forall a. SmallSetElement a => SmallSet a -> [a]
elems
fromList, fromAscList, fromDistinctAscList :: SmallSetElement a => [a] -> SmallSet a
fromList :: forall a. SmallSetElement a => [a] -> SmallSet a
fromList = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (forall a b c. (a -> b -> c) -> b -> a -> c
flip forall a. SmallSetElement a => a -> SmallSet a -> SmallSet a
insert) forall a. SmallSetElement a => SmallSet a
empty
fromAscList :: forall a. SmallSetElement a => [a] -> SmallSet a
fromAscList = forall a. SmallSetElement a => [a] -> SmallSet a
fromList
fromDistinctAscList :: forall a. SmallSetElement a => [a] -> SmallSet a
fromDistinctAscList = forall a. SmallSetElement a => [a] -> SmallSet a
fromList
bounds :: SmallSetElement a => (a, a)
bounds :: forall a. SmallSetElement a => (a, a)
bounds = (forall a. Bounded a => a
minBound, forall a. Bounded a => a
maxBound)
idx :: SmallSetElement a => a -> Int
idx :: forall a. SmallSetElement a => a -> Int
idx a
a = forall a. Ix a => (a, a) -> a -> Int
index forall a. SmallSetElement a => (a, a)
bounds a
a