import Data.List
import Data.Maybe

--Het werkgeheugen bestaat uit een lijst van tuples (Pagina, hoeveel beurten niet gebruikt)
type Werkgeheugen = [(Pagina, Int)]

--Een pagina wordt voorgesteld door een Int
type Pagina = Int

--Een pagineringsfout is een 4-tuple ingevuld als volgt:
--(tijdstip, positie, oudePagina, nieuwePagina)
type Fout = (Tijdstip, Int, Pagina, Pagina)

--Een tijdstip wordt voorgesteld door een Int
type Tijdstip = Int

--Zie opgave
--lru :: Int -> Int -> [Pagina] -> [Fout]
lru m n paginas = verwerk (

leesvolgende :: Pagina -> Werkgeheugen -> [Fout] -> Tijdstip -> (Werkgeheugen, [Fout])
leesvolgende pagina geheugen fouten tijdstip
        |elem pagina (map fst geheugen) = (geheugen, fouten)
        |otherwise = vervangPagina pagina geheugen fouten tijdstip

--Vervangt de minst gebruikte pagina in het geheugen door een meegegeven pagina
--De lijst van fouten wordt ook geupdate
vervangPagina :: Pagina -> Werkgeheugen -> [Fout] -> Tijdstip -> (Werkgeheugen, [Fout])
vervangPagina pagina geheugen fouten tijdstip = (updatedGeheugen, fouten++[(tijdstip, positie, oudepagina, pagina)])
        where   updatedGeheugen = updateGeheugen pagina geheugen
                positie = fromJust $ elemIndex pagina (map fst updatedGeheugen)
                oudepagina = head $ (map fst updatedGeheugen) \\ (map fst geheugen) --beetje vuile truuk ;)

updateGeheugen :: Pagina -> Werkgeheugen -> Werkgeheugen
updateGeheugen pagina geheugen = vervangPaginaN positie pagina geheugen
        where positie = vindIndexMetGebruikt (maximum (map snd geheugen)) geheugen 0

--Vervangt een pagina op de gegeven positie door een nieuwe pagina
--Een nieuwe pagina is nog nooit gebruikt dus het tweede element van het tupel is 0
vervangPaginaN :: Int -> Pagina -> Werkgeheugen -> Werkgeheugen
vervangPaginaN positie nieuwePagina (pagina:rest)
         | positie == 0 = (nieuwePagina, 0):rest
         | otherwise = pagina:vervangPaginaN (positie-1) nieuwePagina rest

vindIndexMetGebruikt :: Int -> Werkgeheugen -> Int-> Int
vindIndexMetGebruikt _ [] _ = error "Kan niet"
vindIndexMetGebruikt keerGebruikt ((pagina, aantal):rest) positie
        |keerGebruikt == aantal = positie
        |otherwise = vindIndexMetGebruikt keerGebruikt rest (positie+1)