Class.hs

-- | Generic class with properties and methods that are available for all
-- different implementations ('IntPSQ', 'OrdPSQ' and 'HashPSQ').
{-# LANGUAGE TypeFamilies        #-}
{-# LANGUAGE FlexibleInstances   #-}
{-# LANGUAGE Rank2Types          #-}
{-# LANGUAGE ScopedTypeVariables #-}
module Data.PSQ.Class
    ( PSQ (..)
    ) where

import           Data.Hashable (Hashable)

import qualified Data.IntPSQ   as IntPSQ
import qualified Data.HashPSQ  as HashPSQ
import qualified Data.OrdPSQ   as OrdPSQ

class PSQ (psq :: * -> * -> *) where
    type Key psq :: *

    -- Query
    null
        :: Ord p => psq p v -> Bool
    size
        :: Ord p => psq p v -> Int
    member
        :: Ord p => Key psq -> psq p v -> Bool
    lookup
        :: Ord p => Key psq -> psq p v -> Maybe (p, v)
    findMin
        :: Ord p => psq p v -> Maybe (Key psq, p, v)

    -- Construction
    empty
        :: Ord p => psq p v
    singleton
        :: Ord p => Key psq -> p -> v -> psq p v

    -- Insertion
    insert
        :: Ord p => Key psq -> p -> v -> psq p v -> psq p v

    -- Delete/update
    delete
        :: Ord p => Key psq -> psq p v -> psq p v
    deleteMin
        :: Ord p => psq p v -> psq p v
    alter
        :: Ord p
        => (Maybe (p, v) -> (b, Maybe (p, v)))
        -> Key psq -> psq p v -> (b, psq p v)
    alterMin
        :: Ord p
        => (Maybe (Key psq, p, v) -> (b, Maybe (Key psq, p, v)))
        -> psq p v -> (b, psq p v)

    -- Lists
    fromList
        :: Ord p => [(Key psq, p, v)] -> psq p v
    toList
        :: Ord p => psq p v -> [(Key psq, p, v)]
    keys
        :: Ord p => psq p v -> [Key psq]

    -- Views
    insertView
        :: Ord p => Key psq -> p -> v -> psq p v -> (Maybe (p, v), psq p v)
    deleteView
        :: Ord p => Key psq -> psq p v -> Maybe (p, v, psq p v)
    minView
        :: Ord p => psq p v -> Maybe (Key psq, p, v, psq p v)
    atMostView
        :: Ord p => p -> psq p v -> ([(Key psq, p, v)], psq p v)

    -- Traversals
    map :: Ord p => (Key psq -> p -> v -> w) -> psq p v -> psq p w
    fold'
        :: Ord p => (Key psq -> p -> v -> a -> a) -> a -> psq p v -> a

    -- Validity check
    valid
        :: Ord p => psq p v -> Bool

instance PSQ IntPSQ.IntPSQ where
    type Key IntPSQ.IntPSQ = Int

    null       = IntPSQ.null
    size       = IntPSQ.size
    member     = IntPSQ.member
    lookup     = IntPSQ.lookup
    findMin    = IntPSQ.findMin
    empty      = IntPSQ.empty
    singleton  = IntPSQ.singleton
    insert     = IntPSQ.insert
    delete     = IntPSQ.delete
    deleteMin  = IntPSQ.deleteMin
    alter      = IntPSQ.alter
    alterMin   = IntPSQ.alterMin
    fromList   = IntPSQ.fromList
    toList     = IntPSQ.toList
    keys       = IntPSQ.keys
    insertView = IntPSQ.insertView
    deleteView = IntPSQ.deleteView
    minView    = IntPSQ.minView
    atMostView = IntPSQ.atMostView
    map        = IntPSQ.map
    fold'      = IntPSQ.fold'
    valid      = IntPSQ.valid

instance forall k. Ord k => PSQ (OrdPSQ.OrdPSQ k) where
    type Key (OrdPSQ.OrdPSQ k) = k

    null       = OrdPSQ.null
    size       = OrdPSQ.size
    member     = OrdPSQ.member
    lookup     = OrdPSQ.lookup
    findMin    = OrdPSQ.findMin
    empty      = OrdPSQ.empty
    singleton  = OrdPSQ.singleton
    insert     = OrdPSQ.insert
    delete     = OrdPSQ.delete
    deleteMin  = OrdPSQ.deleteMin
    alter      = OrdPSQ.alter
    alterMin   = OrdPSQ.alterMin
    fromList   = OrdPSQ.fromList
    toList     = OrdPSQ.toList
    keys       = OrdPSQ.keys
    insertView = OrdPSQ.insertView
    deleteView = OrdPSQ.deleteView
    minView    = OrdPSQ.minView
    atMostView = OrdPSQ.atMostView
    map        = OrdPSQ.map
    fold'      = OrdPSQ.fold'
    valid      = OrdPSQ.valid

instance forall k. (Hashable k, Ord k) => PSQ (HashPSQ.HashPSQ k) where
    type Key (HashPSQ.HashPSQ k) = k

    null       = HashPSQ.null
    size       = HashPSQ.size
    member     = HashPSQ.member
    lookup     = HashPSQ.lookup
    findMin    = HashPSQ.findMin
    empty      = HashPSQ.empty
    singleton  = HashPSQ.singleton
    insert     = HashPSQ.insert
    delete     = HashPSQ.delete
    deleteMin  = HashPSQ.deleteMin
    alter      = HashPSQ.alter
    alterMin   = HashPSQ.alterMin
    fromList   = HashPSQ.fromList
    toList     = HashPSQ.toList
    keys       = HashPSQ.keys
    insertView = HashPSQ.insertView
    deleteView = HashPSQ.deleteView
    minView    = HashPSQ.minView
    atMostView = HashPSQ.atMostView
    map        = HashPSQ.map
    fold'      = HashPSQ.fold'
    valid      = HashPSQ.valid