import Ix
import Data.Array.IO
import Data.Array.MArray
import Data.IORef
import System.IO.Unsafe
import Monad

-- finta 1: rozdilova pole
-- navenek se chovaji funkcionalne, uvnitr realizovany pomoci destruktivniho zapisu
-- teorie -- pokud se vzdy pristupuje k nejnovejsi verzi, je casova slozitost O(1)
--           na operaci

data DArray i e = DArray {daStamp :: Integer,           -- cislo verze
                          daShared :: IORef (DASh i e)} -- obsah pole; sdileno pro vsechny verze

data DASh i e = DASh {daLast :: Integer,                -- cislo verze pole
                      daArray :: IOArray i [(Integer, e)]} -- obsah pole, s verzemi

daNew b e = unsafePerformIO (daNewIO b e)
daGet a i = unsafePerformIO (daGetIO a i)
daPut a i e = unsafePerformIO (daPutIO a i e)

daNewIO::Ix i => (i,i)->e->IO (DArray i e)
daNewIO bnds val = 
  do
    arr <- newArray bnds [(0,val)]
    ref <- newIORef DASh {daLast = 0, daArray = arr}
    return DArray {daStamp = 0, daShared = ref}

daGetIO::Ix i => DArray i e -> i -> IO e
daGetIO arr i = 
  do
    sh <- readIORef (daShared arr)
    es <- readArray (daArray sh) i
    let ver = daStamp arr
        aes = dropWhile (\x-> fst x > ver) es
        l = length (takeWhile (\x-> fst x > ver) es)
    putStrLn (show l)  -- pocet preskocenych verzi; pri pristupu k nejnovejsi verzi 0
    return $ snd (head aes)

daPutIO::Ix i => DArray i e -> i -> e -> IO (DArray i e)
daPutIO arr i e =
  do
    let ref = daShared arr
    sh <- readIORef ref
    let curr = daStamp arr
    if daLast sh > curr
      then
        do -- menime starou verzi pole; vytvorime kopii
          cl <- daClone arr
          daPutIO cl i e
      else
        do -- menime aktualni verzi pole; pridame prvek
          let arr = daArray sh
          old <- readArray arr i
          writeArray arr i ((curr + 1, e) : old)
          writeIORef ref DASh {daLast = curr + 1, daArray = arr}
          return DArray {daStamp = curr + 1, daShared = ref}

daClone::Ix i => DArray i e -> IO (DArray i e)
daClone arr = 
  do
    sh <- readIORef (daShared arr)
    let arri = daArray sh
        bnds = bounds arri
        ixs = range bnds
    narr <- daNewIO bnds undefined
    foldM addElt narr ixs
  where
   addElt a i = 
     do
       x <- daGetIO arr i
       daPutIO a i x

-- praxe -- je obtizne zajistit, abychom vzdy pristupovali k nejnovejsi verzi

test::()->Integer
test _ = b + a
  where
    d = daNew (1,100) 0
    d1 = foldl (\p x -> daPut p x x) d [1..100]
    a = sum [daGet d1 i | i <- [1..100]]
    d2 = foldl (\p x -> daPut p x (2*x)) d1 [1..100]
    b = sum [daGet d2 i | i <- [1..100]]

-- Vylepseni:
--    kazdych Omega(n) operaci lze pole zkopirovat, a tak zajistit, ze celkova delka
--       seznamu je O(n) (slozitost O(1) na operaci, pokud pristupujeme k poli "nahodne")
--    misto seznamu verzi lze pouzit stromy (slozitost O(log n) worst-case) nebo
--        Van Emde Boasovy fronty (slozitost O(log log n) worst-case)
-- Problem -- diffarray muze udrzovat nazivu pamet, ktera jiz neni dostupna