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

module I1M.ColaDePrioridad
  (CPrioridad,
   vacia,   -- Ord a => CPrioridad a 
   inserta, -- Ord a => a -> CPrioridad a -> CPrioridad a 
   primero, -- Ord a => CPrioridad a -> a
   resto,   -- Ord a => CPrioridad a -> CPrioridad a
   esVacia, -- Ord a => CPrioridad a -> Bool 
   valida   -- Ord a => CPrioridad a -> Bool
  ) where

import qualified I1M.Monticulo as M

-- | Tipo de datos de las colas de prioridad.
newtype CPrioridad a = CP (M.Monticulo a)
  deriving (CPrioridad a -> CPrioridad a -> Bool
(CPrioridad a -> CPrioridad a -> Bool)
-> (CPrioridad a -> CPrioridad a -> Bool) -> Eq (CPrioridad a)
forall a. Ord a => CPrioridad a -> CPrioridad a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: forall a. Ord a => CPrioridad a -> CPrioridad a -> Bool
== :: CPrioridad a -> CPrioridad a -> Bool
$c/= :: forall a. Ord a => CPrioridad a -> CPrioridad a -> Bool
/= :: CPrioridad a -> CPrioridad a -> Bool
Eq, Int -> CPrioridad a -> ShowS
[CPrioridad a] -> ShowS
CPrioridad a -> String
(Int -> CPrioridad a -> ShowS)
-> (CPrioridad a -> String)
-> ([CPrioridad a] -> ShowS)
-> Show (CPrioridad a)
forall a. Show a => Int -> CPrioridad a -> ShowS
forall a. Show a => [CPrioridad a] -> ShowS
forall a. Show a => CPrioridad a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: forall a. Show a => Int -> CPrioridad a -> ShowS
showsPrec :: Int -> CPrioridad a -> ShowS
$cshow :: forall a. Show a => CPrioridad a -> String
show :: CPrioridad a -> String
$cshowList :: forall a. Show a => [CPrioridad a] -> ShowS
showList :: [CPrioridad a] -> ShowS
Show)

-- Ejemplo de cola de prioridad
--    ghci> foldr inserta vacia [3,1,7,2,9]
--    CP (M 1 2 
--          (M 2 2 
--             (M 9 1 VacioM VacioM) 
--             (M 7 1 VacioM VacioM)) 
--          (M 3 1 VacioM VacioM))
-- cp1 :: CPrioridad Int
-- cp1 = foldr inserta vacia [3,1,7,2,9]

-- | vacia es la cola de prioridad vacía. Por ejemplo,
-- 
-- > vacia  ==  CP Vacio
vacia :: Ord a => CPrioridad a 
vacia :: forall a. Ord a => CPrioridad a
vacia = Monticulo a -> CPrioridad a
forall a. Monticulo a -> CPrioridad a
CP Monticulo a
forall a. Ord a => Monticulo a
M.vacio

-- | (inserta x c) añade el elemento x a la cola de prioridad c. Por ejemplo, 
-- 
-- > ghci> foldr inserta vacia [3,1,7,2,9]
-- > CP (M 1 2 
-- >       (M 2 2 
-- >          (M 9 1 VacioM VacioM) 
-- >          (M 7 1 VacioM VacioM)) 
-- >       (M 3 1 VacioM VacioM))
-- > ghci> inserta 5 (foldr inserta vacia [3,1,7,2,9])
-- > CP (M 1 2 
-- >       (M 2 2 
-- >          (M 9 1 VacioM VacioM) 
-- >          (M 7 1 VacioM VacioM)) 
-- >       (M 3 1 
-- >          (M 5 1 VacioM VacioM) VacioM))
inserta :: Ord a => a -> CPrioridad a -> CPrioridad a 
inserta :: forall a. Ord a => a -> CPrioridad a -> CPrioridad a
inserta a
v (CP Monticulo a
c) = Monticulo a -> CPrioridad a
forall a. Monticulo a -> CPrioridad a
CP (a -> Monticulo a -> Monticulo a
forall a. Ord a => a -> Monticulo a -> Monticulo a
M.inserta a
v Monticulo a
c)

-- | (primero c) es la cabeza de la cola de prioridad c. Por ejemplo,
-- 
-- > primero (foldr inserta vacia [3,1,7,2,9])  ==  1
primero :: Ord a => CPrioridad a -> a
primero :: forall a. Ord a => CPrioridad a -> a
primero (CP Monticulo a
c) = Monticulo a -> a
forall a. Ord a => Monticulo a -> a
M.menor Monticulo a
c

-- | (resto c) elimina la cabeza de la cola de prioridad c. Por ejemplo, 
--  
-- > ghci> (foldr inserta vacia [3,1,7,2,9])
-- > CP (M 1 2 
-- >       (M 2 2 
-- >          (M 9 1 VacioM VacioM) 
-- >          (M 7 1 VacioM VacioM)) 
-- >       (M 3 1 VacioM VacioM))
-- > ghci> resto (foldr inserta vacia [3,1,7,2,9])
-- > CP (M 2 2 
-- >       (M 9 1 VacioM VacioM) 
-- >       (M 3 1 
-- >          (M 7 1 VacioM VacioM) VacioM))
resto :: Ord a => CPrioridad a -> CPrioridad a
resto :: forall a. Ord a => CPrioridad a -> CPrioridad a
resto (CP Monticulo a
c) = Monticulo a -> CPrioridad a
forall a. Monticulo a -> CPrioridad a
CP (Monticulo a -> Monticulo a
forall a. Ord a => Monticulo a -> Monticulo a
M.resto Monticulo a
c)

-- | (esVacia c) se verifica si la cola de prioridad c es vacía. Por
-- ejemplo,   
-- 
-- > esVacia (foldr inserta vacia [3,1,7,2,9])  ==  False
-- > esVacia vacia                              ==  True
esVacia :: Ord a => CPrioridad a -> Bool 
esVacia :: forall a. Ord a => CPrioridad a -> Bool
esVacia (CP Monticulo a
c) = Monticulo a -> Bool
forall a. Ord a => Monticulo a -> Bool
M.esVacio Monticulo a
c

-- | (valida c) se verifica si c es una cola de prioridad válida. En la
-- representación mediante montículo todas las colas de prioridad son
-- válidas. 
valida :: Ord a => CPrioridad a -> Bool
valida :: forall a. Ord a => CPrioridad a -> Bool
valida CPrioridad a
_ = Bool
True