{-# LANGUAGE DeriveDataTypeable #-}
{-# LANGUAGE DeriveGeneric #-}

-- | 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
    , toSet
    , toSeq
    , fromList
    , append
    , empty
    , difference
    ) where

import Prelude
import Data.List (foldl')
import Data.Sequence (Seq, (|>))
import Data.Data (Data)
import GHC.Generics (Generic)

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

data Set a = Set (Data.Set.Set a) (Seq a)
    deriving (Eq, Generic, Ord, Show, Data)

instance Foldable Set where
    foldMap f = foldMap f . toSeq

toSet :: Set a -> Data.Set.Set a
toSet (Set s _) = s

toSeq :: Set a -> Seq a
toSeq (Set _ xs) = xs

toList :: Set a -> [a]
toList = Data.Foldable.toList

-- 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
fromList :: Ord a => [a] -> Set a
fromList = foldl' (flip append) empty

-- O(log n) time complexity.
append :: Ord a => a -> Set a -> Set a
append x os@(Set s xs)
    | Data.Set.member x s = os
    | otherwise = Set (Data.Set.insert x s) (xs |> x)

empty :: Set a
empty = Set Data.Set.empty 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 os (Set s _) =
    filter (\ x -> not (Data.Set.member x s)) (toList os)