{-# LANGUAGE DeriveAnyClass     #-}
{-# LANGUAGE DeriveDataTypeable #-}
{-# LANGUAGE DeriveGeneric      #-}
{-# LANGUAGE DeriveLift         #-}

-- | This module only exports ways of constructing a Set,
-- retrieving List, Set, and Seq representations of the same data,
-- as well as a novel "difference" function.
-- Any other Set-like or List-like functionality
-- should be obtained through toSet and toList, respectively.
module Dhall.Set (
      Set(..)
    , toList
    , toAscList
    , toSet
    , toSeq
    , fromList
    , fromSet
    , append
    , empty
    , difference
    , sort
    , isSorted
    , null
    , size
    ) where

import Control.DeepSeq            (NFData)
import Data.Data                  (Data)
import Data.List                  (foldl')
import Data.Sequence              (Seq, (|>))
import GHC.Generics               (Generic)
import Instances.TH.Lift          ()
import Language.Haskell.TH.Syntax (Lift)
import Prelude                    hiding (null)

import qualified Data.Foldable
import qualified Data.Sequence
import qualified Data.Set

{-| This is a variation on @"Data.Set".`Data.Set.Set`@ that remembers the
    original order of elements.  This ensures that ordering is not lost when
    formatting Dhall code
-}
data Set a = Set (Data.Set.Set a) (Seq a)
    deriving ((forall x. Set a -> Rep (Set a) x)
-> (forall x. Rep (Set a) x -> Set a) -> Generic (Set a)
forall x. Rep (Set a) x -> Set a
forall x. Set a -> Rep (Set a) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall a x. Rep (Set a) x -> Set a
forall a x. Set a -> Rep (Set a) x
$cto :: forall a x. Rep (Set a) x -> Set a
$cfrom :: forall a x. Set a -> Rep (Set a) x
Generic, Int -> Set a -> ShowS
[Set a] -> ShowS
Set a -> String
(Int -> Set a -> ShowS)
-> (Set a -> String) -> ([Set a] -> ShowS) -> Show (Set a)
forall a. Show a => Int -> Set a -> ShowS
forall a. Show a => [Set a] -> ShowS
forall a. Show a => Set a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Set a] -> ShowS
$cshowList :: forall a. Show a => [Set a] -> ShowS
show :: Set a -> String
$cshow :: forall a. Show a => Set a -> String
showsPrec :: Int -> Set a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> Set a -> ShowS
Show, Typeable (Set a)
DataType
Constr
Typeable (Set a)
-> (forall (c :: * -> *).
    (forall d b. Data d => c (d -> b) -> d -> c b)
    -> (forall g. g -> c g) -> Set a -> c (Set a))
-> (forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c (Set a))
-> (Set a -> Constr)
-> (Set a -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c (Set a)))
-> (forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Set a)))
-> ((forall b. Data b => b -> b) -> Set a -> Set a)
-> (forall r r'.
    (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Set a -> r)
-> (forall r r'.
    (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Set a -> r)
-> (forall u. (forall d. Data d => d -> u) -> Set a -> [u])
-> (forall u. Int -> (forall d. Data d => d -> u) -> Set a -> u)
-> (forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d) -> Set a -> m (Set a))
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> Set a -> m (Set a))
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> Set a -> m (Set a))
-> Data (Set a)
Set a -> DataType
Set a -> Constr
(forall d. Data d => c (t d)) -> Maybe (c (Set a))
(forall b. Data b => b -> b) -> Set a -> Set a
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Set a -> c (Set a)
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (Set a)
forall a. (Data a, Ord a) => Typeable (Set a)
forall a. (Data a, Ord a) => Set a -> DataType
forall a. (Data a, Ord a) => Set a -> Constr
forall a.
(Data a, Ord a) =>
(forall b. Data b => b -> b) -> Set a -> Set a
forall a u.
(Data a, Ord a) =>
Int -> (forall d. Data d => d -> u) -> Set a -> u
forall a u.
(Data a, Ord a) =>
(forall d. Data d => d -> u) -> Set a -> [u]
forall a r r'.
(Data a, Ord a) =>
(r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Set a -> r
forall a r r'.
(Data a, Ord a) =>
(r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Set a -> r
forall a (m :: * -> *).
(Data a, Ord a, Monad m) =>
(forall d. Data d => d -> m d) -> Set a -> m (Set a)
forall a (m :: * -> *).
(Data a, Ord a, MonadPlus m) =>
(forall d. Data d => d -> m d) -> Set a -> m (Set a)
forall a (c :: * -> *).
(Data a, Ord a) =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (Set a)
forall a (c :: * -> *).
(Data a, Ord a) =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Set a -> c (Set a)
forall a (t :: * -> *) (c :: * -> *).
(Data a, Ord a, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (Set a))
forall a (t :: * -> * -> *) (c :: * -> *).
(Data a, Ord a, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Set 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) -> Set a -> u
forall u. (forall d. Data d => d -> u) -> Set a -> [u]
forall r r'.
(r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Set a -> r
forall r r'.
(r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Set a -> r
forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> Set a -> m (Set a)
forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> Set a -> m (Set a)
forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (Set a)
forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Set a -> c (Set a)
forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c (Set a))
forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Set a))
$cSet :: Constr
$tSet :: DataType
gmapMo :: (forall d. Data d => d -> m d) -> Set a -> m (Set a)
$cgmapMo :: forall a (m :: * -> *).
(Data a, Ord a, MonadPlus m) =>
(forall d. Data d => d -> m d) -> Set a -> m (Set a)
gmapMp :: (forall d. Data d => d -> m d) -> Set a -> m (Set a)
$cgmapMp :: forall a (m :: * -> *).
(Data a, Ord a, MonadPlus m) =>
(forall d. Data d => d -> m d) -> Set a -> m (Set a)
gmapM :: (forall d. Data d => d -> m d) -> Set a -> m (Set a)
$cgmapM :: forall a (m :: * -> *).
(Data a, Ord a, Monad m) =>
(forall d. Data d => d -> m d) -> Set a -> m (Set a)
gmapQi :: Int -> (forall d. Data d => d -> u) -> Set a -> u
$cgmapQi :: forall a u.
(Data a, Ord a) =>
Int -> (forall d. Data d => d -> u) -> Set a -> u
gmapQ :: (forall d. Data d => d -> u) -> Set a -> [u]
$cgmapQ :: forall a u.
(Data a, Ord a) =>
(forall d. Data d => d -> u) -> Set a -> [u]
gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Set a -> r
$cgmapQr :: forall a r r'.
(Data a, Ord a) =>
(r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Set a -> r
gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Set a -> r
$cgmapQl :: forall a r r'.
(Data a, Ord a) =>
(r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Set a -> r
gmapT :: (forall b. Data b => b -> b) -> Set a -> Set a
$cgmapT :: forall a.
(Data a, Ord a) =>
(forall b. Data b => b -> b) -> Set a -> Set a
dataCast2 :: (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Set a))
$cdataCast2 :: forall a (t :: * -> * -> *) (c :: * -> *).
(Data a, Ord a, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Set a))
dataCast1 :: (forall d. Data d => c (t d)) -> Maybe (c (Set a))
$cdataCast1 :: forall a (t :: * -> *) (c :: * -> *).
(Data a, Ord a, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (Set a))
dataTypeOf :: Set a -> DataType
$cdataTypeOf :: forall a. (Data a, Ord a) => Set a -> DataType
toConstr :: Set a -> Constr
$ctoConstr :: forall a. (Data a, Ord a) => Set a -> Constr
gunfold :: (forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (Set a)
$cgunfold :: forall a (c :: * -> *).
(Data a, Ord a) =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (Set a)
gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Set a -> c (Set a)
$cgfoldl :: forall a (c :: * -> *).
(Data a, Ord a) =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Set a -> c (Set a)
$cp1Data :: forall a. (Data a, Ord a) => Typeable (Set a)
Data, Set a -> ()
(Set a -> ()) -> NFData (Set a)
forall a. NFData a => Set a -> ()
forall a. (a -> ()) -> NFData a
rnf :: Set a -> ()
$crnf :: forall a. NFData a => Set a -> ()
NFData, Set a -> Q Exp
Set a -> Q (TExp (Set a))
(Set a -> Q Exp) -> (Set a -> Q (TExp (Set a))) -> Lift (Set a)
forall a. Lift a => Set a -> Q Exp
forall a. Lift a => Set a -> Q (TExp (Set a))
forall t. (t -> Q Exp) -> (t -> Q (TExp t)) -> Lift t
liftTyped :: Set a -> Q (TExp (Set a))
$cliftTyped :: forall a. Lift a => Set a -> Q (TExp (Set a))
lift :: Set a -> Q Exp
$clift :: forall a. Lift a => Set a -> Q Exp
Lift)
-- Invariant: In @Set set seq@, @toAscList set == sort (toList seq)@.

instance Eq a => Eq (Set a) where
    (Set Set a
_ Seq a
x) == :: Set a -> Set a -> Bool
== (Set Set a
_ Seq a
y) = Seq a
x Seq a -> Seq a -> Bool
forall a. Eq a => a -> a -> Bool
== Seq a
y
    {-# INLINABLE (==) #-}

instance Ord a => Ord (Set a) where
    compare :: Set a -> Set a -> Ordering
compare (Set Set a
_ Seq a
x) (Set Set a
_ Seq a
y) = Seq a -> Seq a -> Ordering
forall a. Ord a => a -> a -> Ordering
compare Seq a
x Seq a
y
    {-# INLINABLE compare #-}

instance Foldable Set where
    foldMap :: (a -> m) -> Set a -> m
foldMap a -> m
f (Set Set a
_ Seq a
x) = (a -> m) -> Seq a -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap a -> m
f Seq a
x
    {-# INLINABLE foldMap #-}

    toList :: Set a -> [a]
toList = Set a -> [a]
forall a. Set a -> [a]
Dhall.Set.toList
    {-# INLINABLE toList #-}

    null :: Set a -> Bool
null = Set a -> Bool
forall a. Set a -> Bool
Dhall.Set.null
    {-# INLINABLE null #-}

    length :: Set a -> Int
length = Set a -> Int
forall a. Set a -> Int
Dhall.Set.size
    {-# INLINABLE length #-}

-- | Convert to an unordered @"Data.Set".`Data.Set.Set`@
toSet :: Set a -> Data.Set.Set a
toSet :: Set a -> Set a
toSet (Set Set a
s Seq a
_) = Set a
s

-- | Convert to an ordered `Seq`
toSeq :: Set a -> Seq a
toSeq :: Set a -> Seq a
toSeq (Set Set a
_ Seq a
xs) = Seq a
xs

{-| Convert a `Dhall.Set.Set` to a list, preserving the original order of the
    elements
-}
toList :: Set a -> [a]
toList :: Set a -> [a]
toList (Set Set a
_ Seq a
xs) = Seq a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
Data.Foldable.toList Seq a
xs

-- | Convert a `Dhall.Set.Set` to a list of ascending elements
toAscList :: Set a -> [a]
toAscList :: Set a -> [a]
toAscList (Set Set a
s Seq a
_) = Set a -> [a]
forall a. Set a -> [a]
Data.Set.toAscList Set a
s

-- | Convert a list to a `Dhall.Set.Set`, remembering the element order
fromList :: Ord a => [a] -> Set a
fromList :: [a] -> Set a
fromList = (Set a -> a -> Set a) -> Set a -> [a] -> Set a
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' ((a -> Set a -> Set a) -> Set a -> a -> Set a
forall a b c. (a -> b -> c) -> b -> a -> c
flip a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
append) Set a
forall a. Set a
empty
-- O(n log n) time complexity, O(n) space complexity.
-- Implementing it this way is a little silly, but is faster than (nub xs).
-- n.b. toList . fromList = id, only if the list elements are unique

-- | Convert a @"Data.Set".`Data.Set.Set`@ to a sorted `Dhall.Set.Set`
fromSet :: Data.Set.Set a -> Set a
fromSet :: Set a -> Set a
fromSet Set a
s = Set a -> Seq a -> Set a
forall a. Set a -> Seq a -> Set a
Set Set a
s ([a] -> Seq a
forall a. [a] -> Seq a
Data.Sequence.fromList (Set a -> [a]
forall a. Set a -> [a]
Data.Set.elems Set a
s))

-- | Append an element to the end of a `Dhall.Set.Set`
append :: Ord a => a -> Set a -> Set a
append :: a -> Set a -> Set a
append a
x os :: Set a
os@(Set Set a
s Seq a
xs)
    | a -> Set a -> Bool
forall a. Ord a => a -> Set a -> Bool
Data.Set.member a
x Set a
s = Set a
os
    | Bool
otherwise = Set a -> Seq a -> Set a
forall a. Set a -> Seq a -> Set a
Set (a -> Set a -> Set a
forall a. Ord a => a -> Set a -> Set a
Data.Set.insert a
x Set a
s) (Seq a
xs Seq a -> a -> Seq a
forall a. Seq a -> a -> Seq a
|> a
x)
-- O(log n) time complexity.

-- | The empty `Dhall.Set.Set`
empty :: Set a
empty :: Set a
empty = Set a -> Seq a -> Set a
forall a. Set a -> Seq a -> Set a
Set Set a
forall a. Set a
Data.Set.empty Seq a
forall a. Seq a
Data.Sequence.empty

-- | Returns, in order, all elements of the first Set not present in the second.
-- (It doesn't matter in what order the elements appear in the second Set.)
difference :: Ord a => Set a -> Set a -> [a]
difference :: Set a -> Set a -> [a]
difference Set a
os (Set Set a
s Seq a
_) =
    (a -> Bool) -> [a] -> [a]
forall a. (a -> Bool) -> [a] -> [a]
filter (\ a
x -> Bool -> Bool
not (a -> Set a -> Bool
forall a. Ord a => a -> Set a -> Bool
Data.Set.member a
x Set a
s)) (Set a -> [a]
forall a. Set a -> [a]
toList Set a
os)

{-| Sort the set elements, forgetting their original ordering.

>>> sort (fromList [2, 1]) == fromList [1, 2]
True
-}
sort :: Ord a => Set a -> Set a
sort :: Set a -> Set a
sort (Set Set a
s Seq a
_) = Set a -> Seq a -> Set a
forall a. Set a -> Seq a -> Set a
Set Set a
s ([a] -> Seq a
forall a. [a] -> Seq a
Data.Sequence.fromList (Set a -> [a]
forall a. Set a -> [a]
Data.Set.toList Set a
s))

{-|
>>> isSorted (fromList [2, 1])
False
>>> isSorted (fromList [1, 2])
True
-}
isSorted :: Ord a => Set a -> Bool
isSorted :: Set a -> Bool
isSorted Set a
s = Set a -> [a]
forall a. Set a -> [a]
toList Set a
s [a] -> [a] -> Bool
forall a. Eq a => a -> a -> Bool
== Set a -> [a]
forall a. Set a -> [a]
Data.Set.toList (Set a -> Set a
forall a. Set a -> Set a
toSet Set a
s)

{-|
>>> null (fromList [1])
False
>>> null (fromList [])
True
-}
null :: Set a -> Bool
null :: Set a -> Bool
null (Set Set a
s Seq a
_) = Set a -> Bool
forall a. Set a -> Bool
Data.Set.null Set a
s

{-|
>>> size (fromList [1])
1
-}
size :: Set a -> Int
size :: Set a -> Int
size (Set Set a
s Seq a
_) = Set a -> Int
forall a. Set a -> Int
Data.Set.size Set a
s