Queue.hs

{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE ViewPatterns #-}
{-# LANGUAGE FlexibleInstances #-}
{-
 - The Queue data type, a worklist data type for search.
 -
 - 	Monadic Constraint Programming
 - 	http://www.cs.kuleuven.be/~toms/Haskell/
 - 	Tom Schrijvers
 -}

module Control.CP.Queue (
  Queue,
  Elem,
  emptyQ,
  isEmptyQ,
  popQ,
  pushQ
) where

import qualified Data.Sequence
import qualified Control.CP.PriorityQueue as PriorityQueue

class Queue q where   
  type Elem q :: *
  emptyQ   :: q -> q
  isEmptyQ :: q -> Bool
  popQ     :: q -> (Elem q,q)
  pushQ    :: Elem q -> q -> q

instance Queue [a] where
  type Elem [a] = a
  emptyQ _     = []
  isEmptyQ     = Prelude.null
  popQ (x:xs)  = (x,xs)
  pushQ        = (:)

instance Queue (Data.Sequence.Seq a) where
  type Elem (Data.Sequence.Seq a)  = a
  emptyQ _                   = Data.Sequence.empty
  isEmptyQ                   = Data.Sequence.null 
--  popQ (Data.Sequence.viewl -> x Data.Sequence.:< xs)  = (x,xs)
  popQ l                     = case Data.Sequence.viewl l of
    x Data.Sequence.:< xs -> (x,xs)
  pushQ                      = flip (Data.Sequence.|>)

instance Ord a => Queue (PriorityQueue.PriorityQueue a (a,b,c)) where
  type Elem (PriorityQueue.PriorityQueue a (a,b,c)) = (a,b,c)
  emptyQ _ = PriorityQueue.empty
  isEmptyQ = PriorityQueue.is_empty 
  pushQ x@(k,_,_)  = PriorityQueue.insert k x
  popQ q   = let ((_,x),q') = PriorityQueue.deleteMin q
             in (x,q')