-- | A set of unique values. The values can be any comparable type. This
-- includes @Int@, @Float@, @Time@, @Char@, @String@, and tuples or lists
-- of comparable types.
--
-- Insert, remove, and query operations all take /O(log n)/ time.
module Set
  ( -- * Sets
    Set,

    -- * Build
    empty,
    singleton,
    insert,
    remove,

    -- * Query
    isEmpty,
    member,
    size,

    -- * Combine
    union,
    intersect,
    diff,

    -- * Lists
    toList,
    fromList,

    -- * Transform
    map,
    foldl,
    foldr,
    filter,
    partition,
  )
where

import Basics (Bool, Int, Ord, (>>))
import qualified Data.Set
import List (List)
import qualified Prelude

-- | Represents a set of unique values. So @(Set Int)@ is a set of integers and
-- @(Set String)@ is a set of strings.
type Set t =
  Data.Set.Set t

-- | Create an empty set.
empty :: Set a
empty :: forall a. Set a
empty =
  Set a
forall a. Set a
Data.Set.empty

-- | Create a set with one value.
singleton :: comparable -> Set comparable
singleton :: forall comparable. comparable -> Set comparable
singleton =
  comparable -> Set comparable
forall comparable. comparable -> Set comparable
Data.Set.singleton

-- | Insert a value into a set.
insert :: (Ord comparable) => comparable -> Set comparable -> Set comparable
insert :: forall comparable.
Ord comparable =>
comparable -> Set comparable -> Set comparable
insert =
  comparable -> Set comparable -> Set comparable
forall comparable.
Ord comparable =>
comparable -> Set comparable -> Set comparable
Data.Set.insert

-- | Remove a value from a set. If the value is not found, no changes are made.
remove :: (Ord comparable) => comparable -> Set comparable -> Set comparable
remove :: forall comparable.
Ord comparable =>
comparable -> Set comparable -> Set comparable
remove =
  comparable -> Set comparable -> Set comparable
forall comparable.
Ord comparable =>
comparable -> Set comparable -> Set comparable
Data.Set.delete

-- | Determine if a set is empty.
isEmpty :: Set a -> Bool
isEmpty :: forall a. Set a -> Bool
isEmpty =
  Set a -> Bool
forall a. Set a -> Bool
Data.Set.null

-- | Determine if a value is in a set.
member :: (Ord comparable) => comparable -> Set comparable -> Bool
member :: forall comparable.
Ord comparable =>
comparable -> Set comparable -> Bool
member =
  comparable -> Set comparable -> Bool
forall comparable.
Ord comparable =>
comparable -> Set comparable -> Bool
Data.Set.member

-- | Determine the number of elements in a set.
size :: Set a -> Int
size :: forall a. Set a -> Int
size =
  Set a -> Int
forall a. Set a -> Int
Data.Set.size (Set a -> Int) -> (Int -> Int) -> Set a -> Int
forall a b c. (a -> b) -> (b -> c) -> a -> c
>> Int -> Int
forall a b. (Integral a, Num b) => a -> b
Prelude.fromIntegral

-- | Get the union of two sets, preferring the first set when equal elements are
--  encountered.
--
-- In Elm it's not possible to have two comparable elements that are not equal, but
-- it is possible in Haskell.
union :: (Ord comparable) => Set comparable -> Set comparable -> Set comparable
union :: forall comparable.
Ord comparable =>
Set comparable -> Set comparable -> Set comparable
union =
  Set comparable -> Set comparable -> Set comparable
forall comparable.
Ord comparable =>
Set comparable -> Set comparable -> Set comparable
Data.Set.union

-- | Get the intersection of two sets, preferring the first set when equal elements
--  are encountered.
--
-- In Elm it's not possible to have two comparable elements that are not equal, but
-- it is possible in Haskell.
intersect :: (Ord comparable) => Set comparable -> Set comparable -> Set comparable
intersect :: forall comparable.
Ord comparable =>
Set comparable -> Set comparable -> Set comparable
intersect =
  Set comparable -> Set comparable -> Set comparable
forall comparable.
Ord comparable =>
Set comparable -> Set comparable -> Set comparable
Data.Set.intersection

-- | Get the difference between the first set and the second. Keeps values
-- that do not appear in the second set.
diff :: (Ord comparable) => Set comparable -> Set comparable -> Set comparable
diff :: forall comparable.
Ord comparable =>
Set comparable -> Set comparable -> Set comparable
diff =
  Set comparable -> Set comparable -> Set comparable
forall comparable.
Ord comparable =>
Set comparable -> Set comparable -> Set comparable
Data.Set.difference

-- | Convert a set into a list, sorted from lowest to highest.
toList :: Set a -> List a
toList :: forall a. Set a -> List a
toList =
  Set a -> [a]
forall a. Set a -> List a
Data.Set.toAscList

-- | Convert a list into a set, removing any duplicates.
fromList :: (Ord comparable) => List comparable -> Set comparable
fromList :: forall comparable.
Ord comparable =>
List comparable -> Set comparable
fromList =
  [comparable] -> Set comparable
forall comparable.
Ord comparable =>
List comparable -> Set comparable
Data.Set.fromList

-- | Fold over the values in a set, in order from lowest to highest.
foldl :: (a -> b -> b) -> b -> Set a -> b
foldl :: forall a b. (a -> b -> b) -> b -> Set a -> b
foldl a -> b -> b
func =
  (b -> a -> b) -> b -> Set a -> b
forall a b. (a -> b -> a) -> a -> Set b -> a
Data.Set.foldl' (\b
a a
b -> a -> b -> b
func a
b b
a)

-- | Fold over the values in a set, in order from highest to lowest.
foldr :: (a -> b -> b) -> b -> Set a -> b
foldr :: forall a b. (a -> b -> b) -> b -> Set a -> b
foldr =
  (a -> b -> b) -> b -> Set a -> b
forall a b. (a -> b -> b) -> b -> Set a -> b
Data.Set.foldr'

-- | Map a function onto a set, creating a new set with no duplicates.
map :: (Ord comparable2) => (comparable -> comparable2) -> Set comparable -> Set comparable2
map :: forall comparable2 comparable.
Ord comparable2 =>
(comparable -> comparable2) -> Set comparable -> Set comparable2
map =
  (comparable -> comparable2) -> Set comparable -> Set comparable2
forall comparable2 comparable.
Ord comparable2 =>
(comparable -> comparable2) -> Set comparable -> Set comparable2
Data.Set.map

-- | Only keep elements that pass the given test.
--
-- >  import Set exposing (Set)
-- >
-- >  numbers : Set Int
-- >  numbers =
-- >    Set.fromList [-2,-1,0,1,2]
-- >
-- >  positives : Set Int
-- >  positives =
-- >    Set.filter (\x -> x > 0) numbers
-- >
-- >  -- positives == Set.fromList [1,2]
filter :: (comparable -> Bool) -> Set comparable -> Set comparable
filter :: forall comparable.
(comparable -> Bool) -> Set comparable -> Set comparable
filter =
  (comparable -> Bool) -> Set comparable -> Set comparable
forall comparable.
(comparable -> Bool) -> Set comparable -> Set comparable
Data.Set.filter

-- | Create two new sets. The first contains all the elements that passed the
-- given test, and the second contains all the elements that did not.
partition :: (comparable -> Bool) -> Set comparable -> (Set comparable, Set comparable)
partition :: forall comparable.
(comparable -> Bool)
-> Set comparable -> (Set comparable, Set comparable)
partition =
  (comparable -> Bool)
-> Set comparable -> (Set comparable, Set comparable)
forall comparable.
(comparable -> Bool)
-> Set comparable -> (Set comparable, Set comparable)
Data.Set.partition