topkata-0.2.3: Dijkstra.hs

module Dijkstra 
    (dijkstra)
where

import Data.Ix
import Data.Array
import Data.Maybe
import Data.List

{-
class RasterWorld rw where
    neighbors :: Ix a => rw -> a -> [a]
    rwbounds  :: Ix a => rw -> (a, a)
-} 

-- dijkstra :: (Ix a, RasterWorld rw) => rw -> a -> Array a Int
dijkstra rw pos bnds neighbors =
    dijkstraUpdate rw (initArray // [(pos, 0)]) (neighbors rw pos) neighbors
  where 
    rng        = range bnds
    initArray  = array bnds [ (ix, maxBound :: Int) | ix <- rng ]

-- dijkstraUpdate :: (Ix a, RasterWorld rw) => rw -> Array a Int -> [a] -> Array a Int
dijkstraUpdate rw a todo neighbors = 
    if null todo' then a' else dijkstraUpdate rw a' (nub todo') neighbors
  where 
    (update, todo')  = foldl updateOne ([], []) todo
    a'               = a // update
    updateOne acc@(u, td) ix =
        let nbDist = 1+(minimum $ map (a !) nb)
            nb      = neighbors rw ix
        in
           if nbDist < a ! ix then ((ix, nbDist):u, nb ++ td)
              else acc