{-# LANGUAGE CPP, DeriveDataTypeable #-}
#if __GLASGOW_HASKELL__ >= 708
{-# LANGUAGE RoleAnnotations #-}
{-# LANGUAGE TypeFamilies #-}
#endif
#if __GLASGOW_HASKELL__ >= 702
{-# LANGUAGE Trustworthy #-}
#endif
{-# OPTIONS_HADDOCK not-home #-}

------------------------------------------------------------------------
-- |
-- Module      :  Data.HashSet.Internal
-- Copyright   :  2011 Bryan O'Sullivan
-- License     :  BSD-style
-- Maintainer  :  johan.tibell@gmail.com
-- Portability :  portable
--
-- = WARNING
--
-- This module is considered __internal__.
--
-- The Package Versioning Policy __does not apply__.
--
-- The contents of this module may change __in any way whatsoever__
-- and __without any warning__ between minor versions of this package.
--
-- Authors importing this module are expected to track development
-- closely.
--
-- = Description
--
-- A set of /hashable/ values.  A set cannot contain duplicate items.
-- A 'HashSet' makes no guarantees as to the order of its elements.
--
-- The implementation is based on /hash array mapped tries/.  A
-- 'HashSet' is often faster than other tree-based set types,
-- especially when value comparison is expensive, as in the case of
-- strings.
--
-- Many operations have a average-case complexity of /O(log n)/.  The
-- implementation uses a large base (i.e. 16) so in practice these
-- operations are constant time.

module Data.HashSet.Internal
    (
      HashSet

    -- * Construction
    , empty
    , singleton

    -- * Basic interface
    , null
    , size
    , member
    , insert
    , delete
    , isSubsetOf

    -- * Transformations
    , map

    -- * Combine
    , union
    , unions

      -- * Difference and intersection
    , difference
    , intersection

    -- * Folds
    , foldr
    , foldr'
    , foldl
    , foldl'

    -- * Filter
    , filter

    -- * Conversions

    -- ** Lists
    , toList
    , fromList

    -- * HashMaps
    , toMap
    , fromMap

    -- Exported from Data.HashMap.{Strict, Lazy}
    , keysSet
    ) where

import Control.DeepSeq (NFData(..))
import Data.Data hiding (Typeable)
import Data.HashMap.Internal
  ( HashMap, foldMapWithKey, foldlWithKey, foldrWithKey
  , equalKeys, equalKeys1)
import Data.Hashable (Hashable(hashWithSalt))
#if __GLASGOW_HASKELL__ >= 711
import Data.Semigroup (Semigroup(..))
#elif __GLASGOW_HASKELL__ < 709
import Data.Monoid (Monoid(..))
#endif
import GHC.Exts (build)
import Prelude hiding (filter, foldr, foldl, map, null)
import qualified Data.Foldable as Foldable
import qualified Data.HashMap.Internal as H
import qualified Data.List as List
import Data.Typeable (Typeable)
import Text.Read

#if __GLASGOW_HASKELL__ >= 708
import qualified GHC.Exts as Exts
#endif

#if MIN_VERSION_base(4,9,0)
import Data.Functor.Classes
#endif

#if MIN_VERSION_hashable(1,2,5)
import qualified Data.Hashable.Lifted as H
#endif

#if MIN_VERSION_deepseq(1,4,3)
import qualified Control.DeepSeq as NF
#endif

import Data.Functor ((<$))

-- | A set of values.  A set cannot contain duplicate values.
newtype HashSet a = HashSet {
      HashSet a -> HashMap a ()
asMap :: HashMap a ()
    } deriving (Typeable)

#if __GLASGOW_HASKELL__ >= 708
type role HashSet nominal
#endif

instance (NFData a) => NFData (HashSet a) where
    rnf :: HashSet a -> ()
rnf = HashMap a () -> ()
forall a. NFData a => a -> ()
rnf (HashMap a () -> ())
-> (HashSet a -> HashMap a ()) -> HashSet a -> ()
forall b c a. (b -> c) -> (a -> b) -> a -> c
. HashSet a -> HashMap a ()
forall a. HashSet a -> HashMap a ()
asMap
    {-# INLINE rnf #-}

#if MIN_VERSION_deepseq(1,4,3)
-- | @since 0.2.14.0
instance NF.NFData1 HashSet where
    liftRnf :: (a -> ()) -> HashSet a -> ()
liftRnf a -> ()
rnf1 = (a -> ()) -> (() -> ()) -> HashMap a () -> ()
forall (p :: * -> * -> *) a b.
NFData2 p =>
(a -> ()) -> (b -> ()) -> p a b -> ()
NF.liftRnf2 a -> ()
rnf1 () -> ()
forall a. NFData a => a -> ()
rnf (HashMap a () -> ())
-> (HashSet a -> HashMap a ()) -> HashSet a -> ()
forall b c a. (b -> c) -> (a -> b) -> a -> c
. HashSet a -> HashMap a ()
forall a. HashSet a -> HashMap a ()
asMap
#endif

-- | Note that, in the presence of hash collisions, equal @HashSet@s may
-- behave differently, i.e. substitutivity may be violated:
--
-- >>> data D = A | B deriving (Eq, Show)
-- >>> instance Hashable D where hashWithSalt salt _d = salt
--
-- >>> x = fromList [A, B]
-- >>> y = fromList [B, A]
--
-- >>> x == y
-- True
-- >>> toList x
-- [A,B]
-- >>> toList y
-- [B,A]
--
-- In general, the lack of substitutivity can be observed with any function
-- that depends on the key ordering, such as folds and traversals.
instance (Eq a) => Eq (HashSet a) where
    HashSet HashMap a ()
a == :: HashSet a -> HashSet a -> Bool
== HashSet HashMap a ()
b = HashMap a () -> HashMap a () -> Bool
forall k v v'. Eq k => HashMap k v -> HashMap k v' -> Bool
equalKeys HashMap a ()
a HashMap a ()
b
    {-# INLINE (==) #-}

#if MIN_VERSION_base(4,9,0)
instance Eq1 HashSet where
    liftEq :: (a -> b -> Bool) -> HashSet a -> HashSet b -> Bool
liftEq a -> b -> Bool
eq (HashSet HashMap a ()
a) (HashSet HashMap b ()
b) = (a -> b -> Bool) -> HashMap a () -> HashMap b () -> Bool
forall k k' v v'.
(k -> k' -> Bool) -> HashMap k v -> HashMap k' v' -> Bool
equalKeys1 a -> b -> Bool
eq HashMap a ()
a HashMap b ()
b
#endif

instance (Ord a) => Ord (HashSet a) where
    compare :: HashSet a -> HashSet a -> Ordering
compare (HashSet HashMap a ()
a) (HashSet HashMap a ()
b) = HashMap a () -> HashMap a () -> Ordering
forall a. Ord a => a -> a -> Ordering
compare HashMap a ()
a HashMap a ()
b
    {-# INLINE compare #-}

#if MIN_VERSION_base(4,9,0)
instance Ord1 HashSet where
    liftCompare :: (a -> b -> Ordering) -> HashSet a -> HashSet b -> Ordering
liftCompare a -> b -> Ordering
c (HashSet HashMap a ()
a) (HashSet HashMap b ()
b) = (a -> b -> Ordering)
-> (() -> () -> Ordering)
-> HashMap a ()
-> HashMap b ()
-> Ordering
forall (f :: * -> * -> *) a b c d.
Ord2 f =>
(a -> b -> Ordering)
-> (c -> d -> Ordering) -> f a c -> f b d -> Ordering
liftCompare2 a -> b -> Ordering
c () -> () -> Ordering
forall a. Ord a => a -> a -> Ordering
compare HashMap a ()
a HashMap b ()
b
#endif

instance Foldable.Foldable HashSet where
    foldMap :: (a -> m) -> HashSet a -> m
foldMap a -> m
f = (a -> () -> m) -> HashMap a () -> m
forall m k v. Monoid m => (k -> v -> m) -> HashMap k v -> m
foldMapWithKey (\a
a ()
_ -> a -> m
f a
a) (HashMap a () -> m)
-> (HashSet a -> HashMap a ()) -> HashSet a -> m
forall b c a. (b -> c) -> (a -> b) -> a -> c
. HashSet a -> HashMap a ()
forall a. HashSet a -> HashMap a ()
asMap
    foldr :: (a -> b -> b) -> b -> HashSet a -> b
foldr = (a -> b -> b) -> b -> HashSet a -> b
forall a b. (a -> b -> b) -> b -> HashSet a -> b
foldr
    {-# INLINE foldr #-}
    foldl :: (b -> a -> b) -> b -> HashSet a -> b
foldl = (b -> a -> b) -> b -> HashSet a -> b
forall b a. (b -> a -> b) -> b -> HashSet a -> b
foldl
    {-# INLINE foldl #-}
    foldl' :: (b -> a -> b) -> b -> HashSet a -> b
foldl' = (b -> a -> b) -> b -> HashSet a -> b
forall b a. (b -> a -> b) -> b -> HashSet a -> b
foldl'
    {-# INLINE foldl' #-}
    foldr' :: (a -> b -> b) -> b -> HashSet a -> b
foldr' = (a -> b -> b) -> b -> HashSet a -> b
forall a b. (a -> b -> b) -> b -> HashSet a -> b
foldr'
    {-# INLINE foldr' #-}
#if MIN_VERSION_base(4,8,0)
    toList :: HashSet a -> [a]
toList = HashSet a -> [a]
forall a. HashSet a -> [a]
toList
    {-# INLINE toList #-}
    null :: HashSet a -> Bool
null = HashSet a -> Bool
forall a. HashSet a -> Bool
null
    {-# INLINE null #-}
    length :: HashSet a -> Int
length = HashSet a -> Int
forall a. HashSet a -> Int
size
    {-# INLINE length #-}
#endif

#if __GLASGOW_HASKELL__ >= 711
-- | '<>' = 'union'
--
-- /O(n+m)/
--
-- To obtain good performance, the smaller set must be presented as
-- the first argument.
--
-- ==== __Examples__
--
-- >>> fromList [1,2] <> fromList [2,3]
-- fromList [1,2,3]
instance (Hashable a, Eq a) => Semigroup (HashSet a) where
    <> :: HashSet a -> HashSet a -> HashSet a
(<>) = HashSet a -> HashSet a -> HashSet a
forall a. (Eq a, Hashable a) => HashSet a -> HashSet a -> HashSet a
union
    {-# INLINE (<>) #-}
#endif

-- | 'mempty' = 'empty'
--
-- 'mappend' = 'union'
--
-- /O(n+m)/
--
-- To obtain good performance, the smaller set must be presented as
-- the first argument.
--
-- ==== __Examples__
--
-- >>> mappend (fromList [1,2]) (fromList [2,3])
-- fromList [1,2,3]
instance (Hashable a, Eq a) => Monoid (HashSet a) where
    mempty :: HashSet a
mempty = HashSet a
forall a. HashSet a
empty
    {-# INLINE mempty #-}
#if __GLASGOW_HASKELL__ >= 711
    mappend :: HashSet a -> HashSet a -> HashSet a
mappend = HashSet a -> HashSet a -> HashSet a
forall a. Semigroup a => a -> a -> a
(<>)
#else
    mappend = union
#endif
    {-# INLINE mappend #-}

instance (Eq a, Hashable a, Read a) => Read (HashSet a) where
    readPrec :: ReadPrec (HashSet a)
readPrec = ReadPrec (HashSet a) -> ReadPrec (HashSet a)
forall a. ReadPrec a -> ReadPrec a
parens (ReadPrec (HashSet a) -> ReadPrec (HashSet a))
-> ReadPrec (HashSet a) -> ReadPrec (HashSet a)
forall a b. (a -> b) -> a -> b
$ Int -> ReadPrec (HashSet a) -> ReadPrec (HashSet a)
forall a. Int -> ReadPrec a -> ReadPrec a
prec Int
10 (ReadPrec (HashSet a) -> ReadPrec (HashSet a))
-> ReadPrec (HashSet a) -> ReadPrec (HashSet a)
forall a b. (a -> b) -> a -> b
$ do
      Ident [Char]
"fromList" <- ReadPrec Lexeme
lexP
      [a]
xs <- ReadPrec [a]
forall a. Read a => ReadPrec a
readPrec
      HashSet a -> ReadPrec (HashSet a)
forall (m :: * -> *) a. Monad m => a -> m a
return ([a] -> HashSet a
forall a. (Eq a, Hashable a) => [a] -> HashSet a
fromList [a]
xs)

    readListPrec :: ReadPrec [HashSet a]
readListPrec = ReadPrec [HashSet a]
forall a. Read a => ReadPrec [a]
readListPrecDefault

#if MIN_VERSION_base(4,9,0)
instance Show1 HashSet where
    liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> HashSet a -> ShowS
liftShowsPrec Int -> a -> ShowS
sp [a] -> ShowS
sl Int
d HashSet a
m =
        (Int -> [a] -> ShowS) -> [Char] -> Int -> [a] -> ShowS
forall a. (Int -> a -> ShowS) -> [Char] -> Int -> a -> ShowS
showsUnaryWith ((Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> [a] -> ShowS
forall (f :: * -> *) a.
Show1 f =>
(Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> f a -> ShowS
liftShowsPrec Int -> a -> ShowS
sp [a] -> ShowS
sl) [Char]
"fromList" Int
d (HashSet a -> [a]
forall a. HashSet a -> [a]
toList HashSet a
m)
#endif

instance (Show a) => Show (HashSet a) where
    showsPrec :: Int -> HashSet a -> ShowS
showsPrec Int
d HashSet a
m = Bool -> ShowS -> ShowS
showParen (Int
d Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
10) (ShowS -> ShowS) -> ShowS -> ShowS
forall a b. (a -> b) -> a -> b
$
      [Char] -> ShowS
showString [Char]
"fromList " ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> ShowS
forall a. Show a => a -> ShowS
shows (HashSet a -> [a]
forall a. HashSet a -> [a]
toList HashSet a
m)

instance (Data a, Eq a, Hashable a) => Data (HashSet a) where
    gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> HashSet a -> c (HashSet a)
gfoldl forall d b. Data d => c (d -> b) -> d -> c b
f forall g. g -> c g
z HashSet a
m   = ([a] -> HashSet a) -> c ([a] -> HashSet a)
forall g. g -> c g
z [a] -> HashSet a
forall a. (Eq a, Hashable a) => [a] -> HashSet a
fromList c ([a] -> HashSet a) -> [a] -> c (HashSet a)
forall d b. Data d => c (d -> b) -> d -> c b
`f` HashSet a -> [a]
forall a. HashSet a -> [a]
toList HashSet a
m
    toConstr :: HashSet a -> Constr
toConstr HashSet a
_     = Constr
fromListConstr
    gunfold :: (forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (HashSet a)
gunfold forall b r. Data b => c (b -> r) -> c r
k forall r. r -> c r
z Constr
c  = case Constr -> Int
constrIndex Constr
c of
        Int
1 -> c ([a] -> HashSet a) -> c (HashSet a)
forall b r. Data b => c (b -> r) -> c r
k (([a] -> HashSet a) -> c ([a] -> HashSet a)
forall r. r -> c r
z [a] -> HashSet a
forall a. (Eq a, Hashable a) => [a] -> HashSet a
fromList)
        Int
_ -> [Char] -> c (HashSet a)
forall a. HasCallStack => [Char] -> a
error [Char]
"gunfold"
    dataTypeOf :: HashSet a -> DataType
dataTypeOf HashSet a
_   = DataType
hashSetDataType
    dataCast1 :: (forall d. Data d => c (t d)) -> Maybe (c (HashSet a))
dataCast1 forall d. Data d => c (t d)
f    = c (t a) -> Maybe (c (HashSet a))
forall k1 k2 (c :: k1 -> *) (t :: k2 -> k1) (t' :: k2 -> k1)
       (a :: k2).
(Typeable t, Typeable t') =>
c (t a) -> Maybe (c (t' a))
gcast1 c (t a)
forall d. Data d => c (t d)
f

#if MIN_VERSION_hashable(1,2,6)
instance H.Hashable1 HashSet where
    liftHashWithSalt :: (Int -> a -> Int) -> Int -> HashSet a -> Int
liftHashWithSalt Int -> a -> Int
h Int
s = (Int -> a -> Int)
-> (Int -> () -> Int) -> Int -> HashMap a () -> Int
forall (t :: * -> * -> *) a b.
Hashable2 t =>
(Int -> a -> Int) -> (Int -> b -> Int) -> Int -> t a b -> Int
H.liftHashWithSalt2 Int -> a -> Int
h Int -> () -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
s (HashMap a () -> Int)
-> (HashSet a -> HashMap a ()) -> HashSet a -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. HashSet a -> HashMap a ()
forall a. HashSet a -> HashMap a ()
asMap
#endif

instance (Hashable a) => Hashable (HashSet a) where
    hashWithSalt :: Int -> HashSet a -> Int
hashWithSalt Int
salt = Int -> HashMap a () -> Int
forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
salt (HashMap a () -> Int)
-> (HashSet a -> HashMap a ()) -> HashSet a -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. HashSet a -> HashMap a ()
forall a. HashSet a -> HashMap a ()
asMap

fromListConstr :: Constr
fromListConstr :: Constr
fromListConstr = DataType -> [Char] -> [[Char]] -> Fixity -> Constr
mkConstr DataType
hashSetDataType [Char]
"fromList" [] Fixity
Prefix

hashSetDataType :: DataType
hashSetDataType :: DataType
hashSetDataType = [Char] -> [Constr] -> DataType
mkDataType [Char]
"Data.HashSet.Internal.HashSet" [Constr
fromListConstr]

-- | /O(1)/ Construct an empty set.
--
-- >>> HashSet.empty
-- fromList []
empty :: HashSet a
empty :: HashSet a
empty = HashMap a () -> HashSet a
forall a. HashMap a () -> HashSet a
HashSet HashMap a ()
forall k v. HashMap k v
H.empty

-- | /O(1)/ Construct a set with a single element.
--
-- >>> HashSet.singleton 1
-- fromList [1]
singleton :: Hashable a => a -> HashSet a
singleton :: a -> HashSet a
singleton a
a = HashMap a () -> HashSet a
forall a. HashMap a () -> HashSet a
HashSet (a -> () -> HashMap a ()
forall k v. Hashable k => k -> v -> HashMap k v
H.singleton a
a ())
{-# INLINABLE singleton #-}

-- | /O(1)/ Convert to set to the equivalent 'HashMap' with @()@ values.
--
-- >>> HashSet.toMap (HashSet.singleton 1)
-- fromList [(1,())]
toMap :: HashSet a -> HashMap a ()
toMap :: HashSet a -> HashMap a ()
toMap = HashSet a -> HashMap a ()
forall a. HashSet a -> HashMap a ()
asMap

-- | /O(1)/ Convert from the equivalent 'HashMap' with @()@ values.
--
-- >>> HashSet.fromMap (HashMap.singleton 1 ())
-- fromList [1]
fromMap :: HashMap a () -> HashSet a
fromMap :: HashMap a () -> HashSet a
fromMap = HashMap a () -> HashSet a
forall a. HashMap a () -> HashSet a
HashSet

-- | /O(n)/ Produce a 'HashSet' of all the keys in the given 'HashMap'.
--
-- >>> HashSet.keysSet (HashMap.fromList [(1, "a"), (2, "b")]
-- fromList [1,2]
--
-- @since 0.2.10.0
keysSet :: HashMap k a -> HashSet k
keysSet :: HashMap k a -> HashSet k
keysSet HashMap k a
m = HashMap k () -> HashSet k
forall a. HashMap a () -> HashSet a
fromMap (() () -> HashMap k a -> HashMap k ()
forall (f :: * -> *) a b. Functor f => a -> f b -> f a
<$ HashMap k a
m)

-- | /O(n*log m)/ Inclusion of sets.
--
-- ==== __Examples__
--
-- >>> fromList [1,3] `isSubsetOf` fromList [1,2,3]
-- True
--
-- >>> fromList [1,2] `isSubsetOf` fromList [1,3]
-- False
--
-- @since 0.2.12
isSubsetOf :: (Eq a, Hashable a) => HashSet a -> HashSet a -> Bool
isSubsetOf :: HashSet a -> HashSet a -> Bool
isSubsetOf HashSet a
s1 HashSet a
s2 = (() -> () -> Bool) -> HashMap a () -> HashMap a () -> Bool
forall k v1 v2.
(Eq k, Hashable k) =>
(v1 -> v2 -> Bool) -> HashMap k v1 -> HashMap k v2 -> Bool
H.isSubmapOfBy (\()
_ ()
_ -> Bool
True) (HashSet a -> HashMap a ()
forall a. HashSet a -> HashMap a ()
asMap HashSet a
s1) (HashSet a -> HashMap a ()
forall a. HashSet a -> HashMap a ()
asMap HashSet a
s2)

-- | /O(n+m)/ Construct a set containing all elements from both sets.
--
-- To obtain good performance, the smaller set must be presented as
-- the first argument.
--
-- >>> union (fromList [1,2]) (fromList [2,3])
-- fromList [1,2,3]
union :: (Eq a, Hashable a) => HashSet a -> HashSet a -> HashSet a
union :: HashSet a -> HashSet a -> HashSet a
union HashSet a
s1 HashSet a
s2 = HashMap a () -> HashSet a
forall a. HashMap a () -> HashSet a
HashSet (HashMap a () -> HashSet a) -> HashMap a () -> HashSet a
forall a b. (a -> b) -> a -> b
$ HashMap a () -> HashMap a () -> HashMap a ()
forall k v.
(Eq k, Hashable k) =>
HashMap k v -> HashMap k v -> HashMap k v
H.union (HashSet a -> HashMap a ()
forall a. HashSet a -> HashMap a ()
asMap HashSet a
s1) (HashSet a -> HashMap a ()
forall a. HashSet a -> HashMap a ()
asMap HashSet a
s2)
{-# INLINE union #-}

-- TODO: Figure out the time complexity of 'unions'.

-- | Construct a set containing all elements from a list of sets.
unions :: (Eq a, Hashable a) => [HashSet a] -> HashSet a
unions :: [HashSet a] -> HashSet a
unions = (HashSet a -> HashSet a -> HashSet a)
-> HashSet a -> [HashSet a] -> HashSet a
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
List.foldl' HashSet a -> HashSet a -> HashSet a
forall a. (Eq a, Hashable a) => HashSet a -> HashSet a -> HashSet a
union HashSet a
forall a. HashSet a
empty
{-# INLINE unions #-}

-- | /O(1)/ Return 'True' if this set is empty, 'False' otherwise.
--
-- >>> HashSet.null HashSet.empty
-- True
-- >>> HashSet.null (HashSet.singleton 1)
-- False
null :: HashSet a -> Bool
null :: HashSet a -> Bool
null = HashMap a () -> Bool
forall k v. HashMap k v -> Bool
H.null (HashMap a () -> Bool)
-> (HashSet a -> HashMap a ()) -> HashSet a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. HashSet a -> HashMap a ()
forall a. HashSet a -> HashMap a ()
asMap
{-# INLINE null #-}

-- | /O(n)/ Return the number of elements in this set.
--
-- >>> HashSet.size HashSet.empty
-- 0
-- >>> HashSet.size (HashSet.fromList [1,2,3])
-- 3
size :: HashSet a -> Int
size :: HashSet a -> Int
size = HashMap a () -> Int
forall k v. HashMap k v -> Int
H.size (HashMap a () -> Int)
-> (HashSet a -> HashMap a ()) -> HashSet a -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. HashSet a -> HashMap a ()
forall a. HashSet a -> HashMap a ()
asMap
{-# INLINE size #-}

-- | /O(log n)/ Return 'True' if the given value is present in this
-- set, 'False' otherwise.
--
-- >>> HashSet.member 1 (Hashset.fromList [1,2,3])
-- True
-- >>> HashSet.member 1 (Hashset.fromList [4,5,6])
-- False
member :: (Eq a, Hashable a) => a -> HashSet a -> Bool
member :: a -> HashSet a -> Bool
member a
a HashSet a
s = case a -> HashMap a () -> Maybe ()
forall k v. (Eq k, Hashable k) => k -> HashMap k v -> Maybe v
H.lookup a
a (HashSet a -> HashMap a ()
forall a. HashSet a -> HashMap a ()
asMap HashSet a
s) of
               Just ()
_ -> Bool
True
               Maybe ()
_      -> Bool
False
{-# INLINABLE member #-}

-- | /O(log n)/ Add the specified value to this set.
--
-- >>> HashSet.insert 1 HashSet.empty
-- fromList [1]
insert :: (Eq a, Hashable a) => a -> HashSet a -> HashSet a
insert :: a -> HashSet a -> HashSet a
insert a
a = HashMap a () -> HashSet a
forall a. HashMap a () -> HashSet a
HashSet (HashMap a () -> HashSet a)
-> (HashSet a -> HashMap a ()) -> HashSet a -> HashSet a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> () -> HashMap a () -> HashMap a ()
forall k v.
(Eq k, Hashable k) =>
k -> v -> HashMap k v -> HashMap k v
H.insert a
a () (HashMap a () -> HashMap a ())
-> (HashSet a -> HashMap a ()) -> HashSet a -> HashMap a ()
forall b c a. (b -> c) -> (a -> b) -> a -> c
. HashSet a -> HashMap a ()
forall a. HashSet a -> HashMap a ()
asMap
{-# INLINABLE insert #-}

-- | /O(log n)/ Remove the specified value from this set if present.
--
-- >>> HashSet.delete 1 (HashSet.fromList [1,2,3])
-- fromList [2,3]
-- >>> HashSet.delete 1 (HashSet.fromList [4,5,6])
-- fromList [4,5,6]
delete :: (Eq a, Hashable a) => a -> HashSet a -> HashSet a
delete :: a -> HashSet a -> HashSet a
delete a
a = HashMap a () -> HashSet a
forall a. HashMap a () -> HashSet a
HashSet (HashMap a () -> HashSet a)
-> (HashSet a -> HashMap a ()) -> HashSet a -> HashSet a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> HashMap a () -> HashMap a ()
forall k v. (Eq k, Hashable k) => k -> HashMap k v -> HashMap k v
H.delete a
a (HashMap a () -> HashMap a ())
-> (HashSet a -> HashMap a ()) -> HashSet a -> HashMap a ()
forall b c a. (b -> c) -> (a -> b) -> a -> c
. HashSet a -> HashMap a ()
forall a. HashSet a -> HashMap a ()
asMap
{-# INLINABLE delete #-}

-- | /O(n)/ Transform this set by applying a function to every value.
-- The resulting set may be smaller than the source.
--
-- >>> HashSet.map show (HashSet.fromList [1,2,3])
-- HashSet.fromList ["1","2","3"]
map :: (Hashable b, Eq b) => (a -> b) -> HashSet a -> HashSet b
map :: (a -> b) -> HashSet a -> HashSet b
map a -> b
f = [b] -> HashSet b
forall a. (Eq a, Hashable a) => [a] -> HashSet a
fromList ([b] -> HashSet b) -> (HashSet a -> [b]) -> HashSet a -> HashSet b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b) -> [a] -> [b]
forall a b. (a -> b) -> [a] -> [b]
List.map a -> b
f ([a] -> [b]) -> (HashSet a -> [a]) -> HashSet a -> [b]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. HashSet a -> [a]
forall a. HashSet a -> [a]
toList
{-# INLINE map #-}

-- | /O(n)/ Difference of two sets. Return elements of the first set
-- not existing in the second.
--
-- >>> HashSet.difference (HashSet.fromList [1,2,3]) (HashSet.fromList [2,3,4])
-- fromList [1]
difference :: (Eq a, Hashable a) => HashSet a -> HashSet a -> HashSet a
difference :: HashSet a -> HashSet a -> HashSet a
difference (HashSet HashMap a ()
a) (HashSet HashMap a ()
b) = HashMap a () -> HashSet a
forall a. HashMap a () -> HashSet a
HashSet (HashMap a () -> HashMap a () -> HashMap a ()
forall k v w.
(Eq k, Hashable k) =>
HashMap k v -> HashMap k w -> HashMap k v
H.difference HashMap a ()
a HashMap a ()
b)
{-# INLINABLE difference #-}

-- | /O(n)/ Intersection of two sets. Return elements present in both
-- the first set and the second.
--
-- >>> HashSet.intersection (HashSet.fromList [1,2,3]) (HashSet.fromList [2,3,4])
-- fromList [2,3]
intersection :: (Eq a, Hashable a) => HashSet a -> HashSet a -> HashSet a
intersection :: HashSet a -> HashSet a -> HashSet a
intersection (HashSet HashMap a ()
a) (HashSet HashMap a ()
b) = HashMap a () -> HashSet a
forall a. HashMap a () -> HashSet a
HashSet (HashMap a () -> HashMap a () -> HashMap a ()
forall k v w.
(Eq k, Hashable k) =>
HashMap k v -> HashMap k w -> HashMap k v
H.intersection HashMap a ()
a HashMap a ()
b)
{-# INLINABLE intersection #-}

-- | /O(n)/ Reduce this set by applying a binary operator to all
-- elements, using the given starting value (typically the
-- left-identity of the operator).  Each application of the operator
-- is evaluated before before using the result in the next
-- application.  This function is strict in the starting value.
foldl' :: (a -> b -> a) -> a -> HashSet b -> a
foldl' :: (a -> b -> a) -> a -> HashSet b -> a
foldl' a -> b -> a
f a
z0 = (a -> b -> () -> a) -> a -> HashMap b () -> a
forall a k v. (a -> k -> v -> a) -> a -> HashMap k v -> a
H.foldlWithKey' a -> b -> () -> a
g a
z0 (HashMap b () -> a)
-> (HashSet b -> HashMap b ()) -> HashSet b -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. HashSet b -> HashMap b ()
forall a. HashSet a -> HashMap a ()
asMap
  where g :: a -> b -> () -> a
g a
z b
k ()
_ = a -> b -> a
f a
z b
k
{-# INLINE foldl' #-}

-- | /O(n)/ Reduce this set by applying a binary operator to all
-- elements, using the given starting value (typically the
-- right-identity of the operator). Each application of the operator
-- is evaluated before before using the result in the next
-- application. This function is strict in the starting value.
foldr' :: (b -> a -> a) -> a -> HashSet b -> a
foldr' :: (b -> a -> a) -> a -> HashSet b -> a
foldr' b -> a -> a
f a
z0 = (b -> () -> a -> a) -> a -> HashMap b () -> a
forall k v a. (k -> v -> a -> a) -> a -> HashMap k v -> a
H.foldrWithKey' b -> () -> a -> a
g a
z0 (HashMap b () -> a)
-> (HashSet b -> HashMap b ()) -> HashSet b -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. HashSet b -> HashMap b ()
forall a. HashSet a -> HashMap a ()
asMap
  where g :: b -> () -> a -> a
g b
k ()
_ a
z = b -> a -> a
f b
k a
z
{-# INLINE foldr' #-}

-- | /O(n)/ Reduce this set by applying a binary operator to all
-- elements, using the given starting value (typically the
-- right-identity of the operator).
foldr :: (b -> a -> a) -> a -> HashSet b -> a
foldr :: (b -> a -> a) -> a -> HashSet b -> a
foldr b -> a -> a
f a
z0 = (b -> () -> a -> a) -> a -> HashMap b () -> a
forall k v a. (k -> v -> a -> a) -> a -> HashMap k v -> a
foldrWithKey b -> () -> a -> a
g a
z0 (HashMap b () -> a)
-> (HashSet b -> HashMap b ()) -> HashSet b -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. HashSet b -> HashMap b ()
forall a. HashSet a -> HashMap a ()
asMap
  where g :: b -> () -> a -> a
g b
k ()
_ a
z = b -> a -> a
f b
k a
z
{-# INLINE foldr #-}

-- | /O(n)/ Reduce this set by applying a binary operator to all
-- elements, using the given starting value (typically the
-- left-identity of the operator).
foldl :: (a -> b -> a) -> a -> HashSet b -> a
foldl :: (a -> b -> a) -> a -> HashSet b -> a
foldl a -> b -> a
f a
z0 = (a -> b -> () -> a) -> a -> HashMap b () -> a
forall a k v. (a -> k -> v -> a) -> a -> HashMap k v -> a
foldlWithKey a -> b -> () -> a
g a
z0 (HashMap b () -> a)
-> (HashSet b -> HashMap b ()) -> HashSet b -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. HashSet b -> HashMap b ()
forall a. HashSet a -> HashMap a ()
asMap
  where g :: a -> b -> () -> a
g a
z b
k ()
_ = a -> b -> a
f a
z b
k
{-# INLINE foldl #-}

-- | /O(n)/ Filter this set by retaining only elements satisfying a
-- predicate.
filter :: (a -> Bool) -> HashSet a -> HashSet a
filter :: (a -> Bool) -> HashSet a -> HashSet a
filter a -> Bool
p = HashMap a () -> HashSet a
forall a. HashMap a () -> HashSet a
HashSet (HashMap a () -> HashSet a)
-> (HashSet a -> HashMap a ()) -> HashSet a -> HashSet a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> () -> Bool) -> HashMap a () -> HashMap a ()
forall k v. (k -> v -> Bool) -> HashMap k v -> HashMap k v
H.filterWithKey a -> () -> Bool
q (HashMap a () -> HashMap a ())
-> (HashSet a -> HashMap a ()) -> HashSet a -> HashMap a ()
forall b c a. (b -> c) -> (a -> b) -> a -> c
. HashSet a -> HashMap a ()
forall a. HashSet a -> HashMap a ()
asMap
  where q :: a -> () -> Bool
q a
k ()
_ = a -> Bool
p a
k
{-# INLINE filter #-}

-- | /O(n)/ Return a list of this set's elements.  The list is
-- produced lazily.
toList :: HashSet a -> [a]
toList :: HashSet a -> [a]
toList HashSet a
t = (forall b. (a -> b -> b) -> b -> b) -> [a]
forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
build (\ a -> b -> b
c b
z -> (a -> () -> b -> b) -> b -> HashMap a () -> b
forall k v a. (k -> v -> a -> a) -> a -> HashMap k v -> a
foldrWithKey (((b -> b) -> () -> b -> b
forall a b. a -> b -> a
const ((b -> b) -> () -> b -> b) -> (a -> b -> b) -> a -> () -> b -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
.) a -> b -> b
c) b
z (HashSet a -> HashMap a ()
forall a. HashSet a -> HashMap a ()
asMap HashSet a
t))
{-# INLINE toList #-}

-- | /O(n*min(W, n))/ Construct a set from a list of elements.
fromList :: (Eq a, Hashable a) => [a] -> HashSet a
fromList :: [a] -> HashSet a
fromList = HashMap a () -> HashSet a
forall a. HashMap a () -> HashSet a
HashSet (HashMap a () -> HashSet a)
-> ([a] -> HashMap a ()) -> [a] -> HashSet a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (HashMap a () -> a -> HashMap a ())
-> HashMap a () -> [a] -> HashMap a ()
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
List.foldl' (\ HashMap a ()
m a
k -> a -> () -> HashMap a () -> HashMap a ()
forall k v.
(Eq k, Hashable k) =>
k -> v -> HashMap k v -> HashMap k v
H.insert a
k () HashMap a ()
m) HashMap a ()
forall k v. HashMap k v
H.empty
{-# INLINE fromList #-}

#if __GLASGOW_HASKELL__ >= 708
instance (Eq a, Hashable a) => Exts.IsList (HashSet a) where
    type Item (HashSet a) = a
    fromList :: [Item (HashSet a)] -> HashSet a
fromList = [Item (HashSet a)] -> HashSet a
forall a. (Eq a, Hashable a) => [a] -> HashSet a
fromList
    toList :: HashSet a -> [Item (HashSet a)]
toList   = HashSet a -> [Item (HashSet a)]
forall a. HashSet a -> [a]
toList
#endif