{-|
Module      : Data.Set.Ordered.Classes
Description : Type classes defining standard ordered-set operations
Copyright   : (C) Richard Cook, 2019
Licence     : MIT
Maintainer  : rcook@rcook.org
Stability   : stable
Portability : portable
-}

{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE NoImplicitPrelude #-}

module Data.Set.Ordered.Classes
    ( -- * Common operations on ordered sets
      Index
    , OrderedSet(..)
    , -- * Insertion
      PreserveL(..)
    , PreserveR(..)
    ) where

import           Data.Sequence (Seq)
import           Prelude
                    ( Bool
                    , Eq
                    , Int
                    , Maybe
                    , Ord
                    )

-- | A zero-based index with respect to insertion order.
type Index = Int

-- | Common operations on ordered sets. Set type is @c@, element
-- type is @a@.
class OrderedSet a c where
    -- | \(O(1)\). The empty set.
    empty :: c a
    -- | \(O(1)\). A singleton set containing the given element.
    singleton :: a -> c a
    -- | \(O(N log(N))\). Create a set from a finite list of elements.
    -- If an element occurs multiple times in the original list, only
    -- the first occurrence is retained in the resulting set. The
    -- function 'Data.Foldable.Foldable.toList', \(O(N)\), can be used
    -- to return a list of the elements in the original insert order
    -- with duplicates removed.
    fromListL :: Ord a => [a] -> c a
    -- | \(O(N log(N))\). Create a set from a finite list of elements.
    -- If an element occurs multiple times in the original list, only
    -- the last occurrence is retained in the resulting set. The
    -- function 'Data.Foldable.Foldable.toList', \(O(N)\), can be used
    -- to return a list of the elements in the original insert order
    -- with duplicates removed.
    fromListR :: Ord a => [a] -> c a
    -- | \(O(log(N))\). Determine if the element is in the set.
    -- Evaluate to 'Data.Bool.True' if element is in set,
    -- 'Data.Bool.False' otherwise.
    member :: Ord a => a -> c a -> Bool
    -- | \(O(log(N))\). Determine if the element is not in the set.
    -- Evaluate to 'Data.Bool.True' if element is not in set,
    -- 'Data.Bool.False' otherwise.
    notMember :: Ord a => a -> c a -> Bool
    -- | \(O(N log(N))\). Return the set obtained by applying a function
    -- to each element of this set. Note that the resulting set may be
    -- smaller than the original. Along with the 'Ord' constraint, this
    -- means that 'Data.Set.Ordered.OSet.OSet' cannot provide a lawful
    -- 'Data.Functor.Functor' instance.
    map :: Ord b => (a -> b) -> c a -> c b
    -- | \(O(N)\). Filter a set by returning a set whose elements
    -- satisfy the predicate.
    filter :: (a -> Bool) -> c a -> c a
    -- | \(O(1)\). The number of elements in the set.
    size :: c a -> Int
    -- | \(O(1)\). Return ordered sequence of elements in set. For
    -- obtaining a useful 'Data.Functor.Functor' instance this is
    -- recommended over 'Data.Foldable.Foldable.toList' due to its
    -- \(O(1)\) performance. Similarly, if you want to pattern-match on
    -- the 'Data.Set.Ordered.OSet.OSet', obtain the sequence and use
    -- view patterns or pattern synonyms instead of converting to a
    -- list.
    toSeq :: c a -> Seq a
    -- | \(O(N)\). Convert the set to an ascending list of elements.
    toAscList :: c a -> [a]
    -- | \(O(N)\). Finds the index of the leftmost element that matches
    -- the specified element or returns 'GHC.Maybe.Nothing' if no
    -- matching element can be found.
    findIndex :: Eq a => a -> c a -> Maybe Index
    -- | \(O(log(min(i, N - i)))\). Return the element at the specified
    -- position, \(i\), counting from 0. If the specified position is
    -- out of range, this function returns 'GHC.Maybe.Nothing'.
    elemAt :: c a -> Index -> Maybe a
    -- | \(O(log N)\). Delete an element from the set.
    delete :: Ord a => a -> c a -> c a
    -- | \(O(N M)\). Find the set difference: @r \\\\ s@ removes all @M@
    -- values in @s@ from @r@ with @N@ values.
    (\\) :: Ord a => c a -> c a -> c a

-- | 'Data.Set.Ordered.OSet.OSet' and 'Data.Set.Ordered.OSetL'
-- operations that preserve elements from the left-hand operand in the
-- case of duplicate elements. Set type is @c@, element type is @a@.
class PreserveL a c where
    -- | \(O(log(N))\) if the element is not in the set, \(O(N)\) if the
    -- element is already in the set. Add an element to the left end of
    -- the sequence if the set does not already contain the element.
    -- Move the element to the left end of the sequence if the element
    -- is already present in the set.
    (|<) :: a -> c a -> c a
    infixr 5 |<
    -- | \(O(log(N))\). Add an element to the right end of the sequence
    -- if the set does not already contain the element. Otherwise ignore
    -- the element.
    (|>) :: c a -> a -> c a
    infixl 5 |>
    -- | \(O(Nlog(N))\) worst case. Add elements from the right-hand set
    -- to the left-hand set. If elements occur in both sets, then this
    -- operation discards elements from the right-hand set and preserves
    -- those from the left.
    (|<>) :: c a -> c a -> c a
    infixr 6 |<>

-- | 'Data.Set.Ordered.OSet.OSet' and 'Data.Set.Ordered.OSetR'
-- operations that preserve elements from the right-hand operand in the
-- case of duplicate elements. Set type is @c@, element type is @a@.
class PreserveR a c where
    -- | \(O(log(N))\). Add an element to the left end of the sequence
    -- if the set does not already contain the element. Otherwise ignore
    -- the element.
    (<|) :: a -> c a -> c a
    infixr 5 <|
    -- | \(O(log(N))\) if the element is not in the set, \(O(N)\) if the
    -- element is already in the set. Add an element to the right end of
    -- the sequence if the set does not already contain the element.
    -- Move the element to the right end of the sequence if the element
    -- is already present in the set.
    (>|) :: c a -> a -> c a
    infixl 5 >|
    -- | \(O(N^2)\) worst case. Add elements from the right-hand set to
    -- the left-hand set. If elements occur in both sets, then this
    -- operation discards elements from the left-hand set and preserves
    -- those from the right.
    (<>|) :: c a -> c a -> c a
    infixr 6 <>|