-----------------------------------------------------------------------------
-- |
-- Module  :  ForSyDe.Shallow.Utility.Queue
-- Copyright   :  (c) ForSyDe Group, KTH 2007-2008
-- License     :  BSD-style (see the file LICENSE)
-- 
-- Maintainer  :  forsyde-dev@ict.kth.se
-- Stability   :  experimental
-- Portability :  portable
--
--
-- This provides two data types, that can be used to model queue
-- structures, such as FIFOs. There is a data type for an queue of
-- infinite size 'Queue' and one for finite size 'FiniteQueue'.
-----------------------------------------------------------------------------
module ForSyDe.Shallow.Utility.Queue where

import ForSyDe.Shallow.Core.AbsentExt 

-- | A queue is modeled as a list. The data type 'Queue' modelles an
-- queue of infinite size.
data Queue a = Q [a] deriving (Queue a -> Queue a -> Bool
(Queue a -> Queue a -> Bool)
-> (Queue a -> Queue a -> Bool) -> Eq (Queue a)
forall a. Eq a => Queue a -> Queue a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Queue a -> Queue a -> Bool
$c/= :: forall a. Eq a => Queue a -> Queue a -> Bool
== :: Queue a -> Queue a -> Bool
$c== :: forall a. Eq a => Queue a -> Queue a -> Bool
Eq, Int -> Queue a -> ShowS
[Queue a] -> ShowS
Queue a -> String
(Int -> Queue a -> ShowS)
-> (Queue a -> String) -> ([Queue a] -> ShowS) -> Show (Queue a)
forall a. Show a => Int -> Queue a -> ShowS
forall a. Show a => [Queue a] -> ShowS
forall a. Show a => Queue a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Queue a] -> ShowS
$cshowList :: forall a. Show a => [Queue a] -> ShowS
show :: Queue a -> String
$cshow :: forall a. Show a => Queue a -> String
showsPrec :: Int -> Queue a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> Queue a -> ShowS
Show)

-- | The data type 'FiniteQueue' has an additional parameter, that
-- determines the size of the queue.
data FiniteQueue a = FQ Int [a] deriving (FiniteQueue a -> FiniteQueue a -> Bool
(FiniteQueue a -> FiniteQueue a -> Bool)
-> (FiniteQueue a -> FiniteQueue a -> Bool) -> Eq (FiniteQueue a)
forall a. Eq a => FiniteQueue a -> FiniteQueue a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: FiniteQueue a -> FiniteQueue a -> Bool
$c/= :: forall a. Eq a => FiniteQueue a -> FiniteQueue a -> Bool
== :: FiniteQueue a -> FiniteQueue a -> Bool
$c== :: forall a. Eq a => FiniteQueue a -> FiniteQueue a -> Bool
Eq, Int -> FiniteQueue a -> ShowS
[FiniteQueue a] -> ShowS
FiniteQueue a -> String
(Int -> FiniteQueue a -> ShowS)
-> (FiniteQueue a -> String)
-> ([FiniteQueue a] -> ShowS)
-> Show (FiniteQueue a)
forall a. Show a => Int -> FiniteQueue a -> ShowS
forall a. Show a => [FiniteQueue a] -> ShowS
forall a. Show a => FiniteQueue a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [FiniteQueue a] -> ShowS
$cshowList :: forall a. Show a => [FiniteQueue a] -> ShowS
show :: FiniteQueue a -> String
$cshow :: forall a. Show a => FiniteQueue a -> String
showsPrec :: Int -> FiniteQueue a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> FiniteQueue a -> ShowS
Show)

{-
Table \ref{tab:QueueFunctions} shows the functions an the data types \haskell{Queue} and \haskell{FiniteQueue}.
%
\begin{table}
\label{tab:QueueFunctions}
\begin{tabular}{lll}
\hline
infinite & finite & description \\
\hline
\hline
\haskell{pushQ} & \haskell{pushFQ} & pushes one element on the queue \\
\haskell{pushListQ} & \haskell{pushListFQ} & pushes a list of elements on the queue \\
\haskell{popQ} & \haskell{popFQ} & pops one element from the queue \\
\haskell{queue} & \haskell{finiteQueue} & transforms a list into a queue \\
\hline
\end{tabular}
\caption{Functions on the data types \haskell{Queue} and \haskell{FiniteQueue}}
\end{table}
-}

-- | 'pushQ' pushes one element into an infinite queue.
pushQ :: Queue a -> a -> Queue a

-- | 'pushListQ' pushes a list of elements into an infinite queue.
pushListQ :: Queue a -> [a] -> Queue a

-- | 'popQ' pops one element from an infinite queue.
popQ :: Queue a -> (Queue a, AbstExt a)

-- | 'queue' transforms a list into an infinite queue.
queue :: [a] -> Queue a

-- | 'pushFQ' pushes one element into a finite queue.
pushFQ :: FiniteQueue a -> a -> FiniteQueue a

-- | 'pushListFQ' pushes a list of elements into a finite queue.
pushListFQ :: FiniteQueue a -> [a] -> FiniteQueue a

-- | 'popFQ' pops one element from a finite queue.
popFQ :: FiniteQueue a -> (FiniteQueue a, AbstExt a)

-- | 'finiteQueue' transforms a list into an infinite queue.
finiteQueue :: Int -> [a] -> FiniteQueue a


-- Implementation

pushQ :: Queue a -> a -> Queue a
pushQ (Q [a]
q) a
x = [a] -> Queue a
forall a. [a] -> Queue a
Q ([a]
q [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a
x])

pushListQ :: Queue a -> [a] -> Queue a
pushListQ (Q [a]
q) [a]
xs =  [a] -> Queue a
forall a. [a] -> Queue a
Q ([a]
q [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a]
xs)

popQ :: Queue a -> (Queue a, AbstExt a)
popQ (Q [])     =  ([a] -> Queue a
forall a. [a] -> Queue a
Q [], AbstExt a
forall a. AbstExt a
Abst)
popQ (Q (a
x:[a]
xs)) =  ([a] -> Queue a
forall a. [a] -> Queue a
Q [a]
xs, a -> AbstExt a
forall a. a -> AbstExt a
Prst a
x)

queue :: [a] -> Queue a
queue [a]
xs =  [a] -> Queue a
forall a. [a] -> Queue a
Q [a]
xs

pushFQ :: FiniteQueue a -> a -> FiniteQueue a
pushFQ (FQ Int
n [a]
q) a
x =  if [a] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
q Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
n then
                       (Int -> [a] -> FiniteQueue a
forall a. Int -> [a] -> FiniteQueue a
FQ Int
n ([a]
q [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a
x]))
                     else 
                       (Int -> [a] -> FiniteQueue a
forall a. Int -> [a] -> FiniteQueue a
FQ Int
n [a]
q)

pushListFQ :: FiniteQueue a -> [a] -> FiniteQueue a
pushListFQ (FQ Int
n [a]
q) [a]
xs =  Int -> [a] -> FiniteQueue a
forall a. Int -> [a] -> FiniteQueue a
FQ Int
n (Int -> [a] -> [a]
forall a. Int -> [a] -> [a]
take Int
n ([a]
q [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a]
xs))

popFQ :: FiniteQueue a -> (FiniteQueue a, AbstExt a)
popFQ (FQ Int
n [])     =  (Int -> [a] -> FiniteQueue a
forall a. Int -> [a] -> FiniteQueue a
FQ Int
n [], AbstExt a
forall a. AbstExt a
Abst)
popFQ (FQ Int
n (a
q:[a]
qs)) =  (Int -> [a] -> FiniteQueue a
forall a. Int -> [a] -> FiniteQueue a
FQ Int
n [a]
qs, a -> AbstExt a
forall a. a -> AbstExt a
Prst a
q)
                 
finiteQueue :: Int -> [a] -> FiniteQueue a
finiteQueue Int
n [a]
xs =  Int -> [a] -> FiniteQueue a
forall a. Int -> [a] -> FiniteQueue a
FQ Int
n (Int -> [a] -> [a]
forall a. Int -> [a] -> [a]
take Int
n [a]
xs)