Utils.hs

module Utils where

import Data.Map (Map)
import qualified Data.Map as M

data Heap a = Heap
  { hNumObjs :: Int
  , hUnused  :: [Addr]
  , hMap     :: Map Addr a
  }
  deriving (Eq, Ord)

instance Show a => Show (Heap a) where
  show (Heap num free m) = "Heap " ++ show num ++ " [" ++ show (head free) ++ "..] " ++ show m

type Addr = Int

hInitial :: Heap a
hInitial = Heap 0 [1..] M.empty

hAlloc :: Heap a -> a -> (Heap a, Addr)
hAlloc h@(Heap { hNumObjs = size
               , hUnused  = next:free
               , hMap     = cts
               })
       n = (h { hNumObjs = size+1
              , hUnused  = free
              , hMap     = M.insert next n cts }, next)
hAlloc _ _ = error "Invalid heap"

hUpdate :: Heap a -> Addr -> a -> Heap a
hUpdate h@(Heap { hMap = cts }) a n
  = h { hMap = M.update (const (Just n)) a cts }

hLookup :: Heap a -> Addr -> a
hLookup h a = maybe (error ("can't find node " ++ show a ++ " in heap"))
                    id (M.lookup a (hMap h))

hNull :: Int
hNull = (-1)