-- |
-- Module      : Cola
-- Description : TAD de las colas.
-- License     : Creative Commons
-- Maintainer  : José A. Alonso
-- 
-- TAD (tipo abstracto de datos) de las colas.
--
-- Este módulo contiene el código del TAD de las colas 
-- estudiado en el <http://bit.ly/1F5RSjM tema 15> del curso.

module I1M.Cola
  (Cola,
   vacia,   -- Cola a
   inserta, -- a -> Cola a -> Cola a
   primero, -- Cola a -> a
   resto,   -- Cola a -> Cola a
   esVacia, -- Cola a -> Bool
   valida   -- Cola a -> Bool
  ) where

-- | Tipo de las colas.
newtype Cola a = C [a]
  deriving (Int -> Cola a -> ShowS
[Cola a] -> ShowS
Cola a -> String
(Int -> Cola a -> ShowS)
-> (Cola a -> String) -> ([Cola a] -> ShowS) -> Show (Cola a)
forall a. Show a => Int -> Cola a -> ShowS
forall a. Show a => [Cola a] -> ShowS
forall a. Show a => Cola a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: forall a. Show a => Int -> Cola a -> ShowS
showsPrec :: Int -> Cola a -> ShowS
$cshow :: forall a. Show a => Cola a -> String
show :: Cola a -> String
$cshowList :: forall a. Show a => [Cola a] -> ShowS
showList :: [Cola a] -> ShowS
Show, Cola a -> Cola a -> Bool
(Cola a -> Cola a -> Bool)
-> (Cola a -> Cola a -> Bool) -> Eq (Cola a)
forall a. Eq a => Cola a -> Cola a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: forall a. Eq a => Cola a -> Cola a -> Bool
== :: Cola a -> Cola a -> Bool
$c/= :: forall a. Eq a => Cola a -> Cola a -> Bool
/= :: Cola a -> Cola a -> Bool
Eq)

-- | c1 es un ejemplo de cola que se usará en los siguientes ejemplos.
-- 
-- > ghci> c1
-- > C [10,9,8,7,6,5,4,3,2,1]
-- c1 = foldr inserta vacia [1..10]

-- | vacia es la cola vacía. Por ejemplo,
-- 
-- > ghci> vacia
-- > C []
vacia :: Cola a
vacia :: forall a. Cola a
vacia = [a] -> Cola a
forall a. [a] -> Cola a
C []

-- | (inserta x c) es la cola obtenida añadiendo x al final de la cola
-- c. Por ejemplo,
-- 
-- > inserta 12 (foldr inserta vacia [1..10])  ==  C [10,9,8,7,6,5,4,3,2,1,12]
inserta :: a -> Cola a -> Cola a
inserta :: forall a. a -> Cola a -> Cola a
inserta a
x (C [a]
c) = [a] -> Cola a
forall a. [a] -> Cola a
C ([a]
c [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [a
x])

-- Nota: La operación inserta usa O(n) pasos.

-- | (primero c) es el primer elemento de la cola c. Por ejemplo,
-- 
-- > primero (foldr inserta vacia [1..10])  ==  10
primero :: Cola a -> a
primero :: forall a. Cola a -> a
primero (C (a
x:[a]
_)) = a
x
primero (C [])    = String -> a
forall a. HasCallStack => String -> a
error String
"primero: cola vacia"

-- | (resto c) es la cola obtenida eliminando el primer elemento de la
-- cola c. Por ejemplo,
-- 
-- > resto (foldr inserta vacia [1..10])  ==  C [9,8,7,6,5,4,3,2,1]
resto :: Cola a -> Cola a
resto :: forall a. Cola a -> Cola a
resto (C (a
_:[a]
xs)) = [a] -> Cola a
forall a. [a] -> Cola a
C [a]
xs
resto (C [])     = String -> Cola a
forall a. HasCallStack => String -> a
error String
"resto: cola vacia"

-- | (esVacia c) se verifica si c es la cola vacía. Por ejemplo,
-- 
-- > esVacia (foldr inserta vacia [1..10])  ==  False
-- > esVacia vacia                          ==  True
esVacia :: Cola a -> Bool
esVacia :: forall a. Cola a -> Bool
esVacia (C [a]
xs)  = [a] -> Bool
forall a. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null [a]
xs

-- | (valida c) se verifica si c representa una cola válida. Con esta
-- representación, todas las colas son válidas.
valida :: Cola a -> Bool
valida :: forall a. Cola a -> Bool
valida Cola a
_ = Bool
True