    {-# 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
    $cfrom :: forall a x. Set a -> Rep (Set a) x
    from :: forall x. Set a -> Rep (Set a) x
    $cto :: forall a x. Rep (Set a) x -> Set a
    to :: forall x. Rep (Set a) x -> Set a
    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
    $cshowsPrec :: forall a. Show a => Int -> Set a -> ShowS
    showsPrec :: Int -> Set a -> ShowS
    $cshow :: forall a. Show a => Set a -> String
    show :: Set a -> String
    $cshowList :: forall a. Show a => [Set a] -> ShowS
    showList :: [Set a] -> ShowS
    Show, Typeable (Set a)
    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 -> Constr
    Set a -> DataType
    (forall b. Data b => b -> b) -> Set a -> Set a
    forall {a}. (Data a, Ord a) => Typeable (Set a)
    forall a. (Data a, Ord a) => Set a -> Constr
    forall a. (Data a, Ord a) => Set a -> DataType
    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))
    $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)
    gfoldl :: forall (c :: * -> *).
    (forall d b. Data d => c (d -> b) -> d -> c b)
    -> (forall g. g -> c g) -> Set a -> 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)
    gunfold :: forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c (Set a)
    $ctoConstr :: forall a. (Data a, Ord a) => Set a -> Constr
    toConstr :: Set a -> Constr
    $cdataTypeOf :: forall a. (Data a, Ord a) => Set a -> DataType
    dataTypeOf :: Set a -> DataType
    $cdataCast1 :: forall a (t :: * -> *) (c :: * -> *).
    (Data a, Ord a, Typeable t) =>
    (forall d. Data d => c (t d)) -> Maybe (c (Set a))
    dataCast1 :: forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> 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))
    dataCast2 :: forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Set a))
    $cgmapT :: forall a.
    (Data a, Ord a) =>
    (forall b. Data b => b -> b) -> Set a -> Set a
    gmapT :: (forall b. Data b => b -> b) -> Set a -> Set a
    $cgmapQl :: forall a r r'.
    (Data a, Ord a) =>
    (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Set a -> r
    gmapQl :: forall r r'.
    (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
    gmapQr :: forall r r'.
    (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Set a -> r
    $cgmapQ :: forall a u.
    (Data a, Ord a) =>
    (forall d. Data d => d -> u) -> Set a -> [u]
    gmapQ :: forall u. (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
    gmapQi :: forall u. Int -> (forall d. Data d => d -> u) -> Set a -> u
    $cgmapM :: forall a (m :: * -> *).
    (Data a, Ord a, Monad m) =>
    (forall d. Data d => d -> m d) -> Set a -> m (Set a)
    gmapM :: forall (m :: * -> *).
    Monad m =>
    (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)
    gmapMp :: forall (m :: * -> *).
    MonadPlus m =>
    (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)
    gmapMo :: forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> Set a -> m (Set a)
    Data, Set a -> ()
    (Set a -> ()) -> NFData (Set a)
    forall a. NFData a => Set a -> ()
    forall a. (a -> ()) -> NFData a
    $crnf :: forall a. NFData a => Set a -> ()
    rnf :: Set a -> ()
    NFData, (forall (m :: * -> *). Quote m => Set a -> m Exp)
    -> (forall (m :: * -> *). Quote m => Set a -> Code m (Set a))
    -> Lift (Set a)
    forall a (m :: * -> *). (Lift a, Quote m) => Set a -> m Exp
    forall a (m :: * -> *).
    (Lift a, Quote m) =>
    Set a -> Code m (Set a)
    forall t.
    (forall (m :: * -> *). Quote m => t -> m Exp)
    -> (forall (m :: * -> *). Quote m => t -> Code m t) -> Lift t
    forall (m :: * -> *). Quote m => Set a -> m Exp
    forall (m :: * -> *). Quote m => Set a -> Code m (Set a)
    $clift :: forall a (m :: * -> *). (Lift a, Quote m) => Set a -> m Exp
    lift :: forall (m :: * -> *). Quote m => Set a -> m Exp
    $cliftTyped :: forall a (m :: * -> *).
    (Lift a, Quote m) =>
    Set a -> Code m (Set a)
    liftTyped :: forall (m :: * -> *). Quote m => Set a -> Code m (Set a)
    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 :: forall m a. Monoid m => (a -> m) -> Set a -> m
    foldMap a -> m
    f (Set Set a
    _ Seq a
    x) = (a -> m) -> Seq a -> m
    forall m a. Monoid m => (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 :: forall a. Set a -> [a]
    toList = Set a -> [a]
    forall a. Set a -> [a]
    Dhall.Set.toList
        {-# INLINABLE toList #-}

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

        length :: forall a. 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 :: forall a. 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 :: forall a. 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 :: forall a. Set a -> [a]
    toList (Set Set a
    _ Seq a
    xs) = Seq a -> [a]
    forall a. 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 :: forall a. 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 :: forall a. Ord a => [a] -> Set a
    fromList = (Set a -> a -> Set a) -> Set a -> [a] -> Set a
    forall b a. (b -> a -> b) -> b -> [a] -> b
    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 :: forall a. 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 :: forall a. Ord a => 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 :: forall a. 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 :: forall a. Ord a => 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 :: forall a. Ord a => 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 :: forall a. Ord a => 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 :: forall a. 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 :: forall a. Set a -> Int
    size (Set Set a
    s Seq a
    _) = Set a -> Int
    forall a. Set a -> Int
    Data.Set.size Set a
    s