-- | This example encodes the Fibonacci sequence as a dynamic program, and explores 
--   using several different solvers to compute the result.

module Data.DP.Examples.Fibonacci where 

--{{{  Imports
import Data.DP
import Data.DP.Solvers
import Data.Array.Unboxed
import Data.Semiring
import Data.Semiring.Counting
import Data.Array.ST
import qualified Data.Map as M
import Control.Monad.ST
import Control.Monad
import Control.Monad.Identity
import Data.Int
import Safe
--}}}


fib :: SimpleDP Int Counting  
fib 0 = one
fib 1 = one
fib i = (f (i-2)) `mappend` (f (i-1))

runRecursive :: Int -> Counting
runRecursive i = getSimpleResult $ runIdentity $ solveSimpleDP recursive i fib 

-- | Run top down  using a map
runMemo :: Int -> Counting
runMemo i = getSimpleResult $ runIdentity $  solveSimpleDP topDownMap i fib

-- | Run bottom up using a map
runOrderedMap :: Int -> Counting
runOrderedMap i = getSimpleResult $ runIdentity $ solveSimpleDP bottomUpLazyMap [0..i] fib

-- | Run bottom up using an Array
runOrdered :: Int -> Counting
runOrdered i = getSimpleResult $ runIdentity $ solveSimpleDP (bottomUpLazyArray (0,i)) [0..i]  fib


-- | Shows one way to run using an impure data structure like @'STUArray'@. 
runOrderedUnboxed :: Int -> IO Counting
runOrderedUnboxed i = (runIdentity . getResult) `liftM` (stToIO $  
                                                       solveSimpleDP (bottomUpStrictSTUArray
                                                                      (fromIntegral::Counting -> Int64) 
                                                                      (fromIntegral::Int64 -> Counting) (0,i)) 
                                                                         [0..i] fib)
  


data NMap key val = NMap Int (M.Map key val)
    deriving (Show)

nmapInsert :: (Ord key) =>  key -> val -> NMap key val -> Identity (NMap key val) 
nmapInsert a v (NMap n m) = 
    return $ NMap n $ M.insert a v (if M.size m == n then M.delete (fst $ M.findMin m) m else m)  

nmapSolver n = mkSolver $ BottomUpStrict {
                bus_insert = nmapInsert,
                bus_empty = return $ NMap n M.empty,
                bus_lookup = (\ i (NMap _ m) -> return ((M.!) m i)) 
              }

-- | An NMap is a Map that only keeps track of the last n values seen. 
--   For fibonacci there is no need to keep more than the last two value in 
--   memory, so we can easily code up a 2-Map to use as our chart.
runNMap :: Int -> Counting                                      
runNMap i = getSimpleResult $ runIdentity $ solveSimpleDP (nmapSolver 2) [0..i] fib