Index.hs

-- |
-- Module    : G500.Index
-- Copyright : (C) 2013 Parallel Scientific Labs, LLC.
-- License   : GPLv2
--
-- Definition for the type of indices.
--
-- I think index type can change over time, so I made that
-- little file with type definition and class that allows one's code
-- to work with different index types.
--
-- On the second thought it looks like overengineering. Let it be.

-- TODO:
--  - type-safe index? (data VertexIndex v = VertexIndex !Index, as an example)

module G500.Index
    ( Index                                     -- index type.
    , RandomIndex(..)                           -- how to generate random index.
    ) where

import Data.Bits
import Data.Int
import System.Random


-- |Big enough for Graph500 benchmark purposes.
type Index = Int64

class Bits index => RandomIndex index where
	-- |Generate random index.
	-- Accepts max value and generator.
	-- Returns random index and updated generator.
	-- Max value should be power of 2 (valid for Graph500 generator).
	randomIndex :: RandomGen g => index -> g -> (index,g)

instance RandomIndex Int64 where
	-- simple version.
	-- we assume that we get a whole 30 bits of Int in @next@ call.
	-- (this is true for StdGen)
	randomIndex maxIndex g
		| maxIndex < shiftL 1 30 = (fromIntegral low30Bits .&. maxIndex,g')
		| otherwise = (fromIntegral low30Bits .|. shiftL highBits 30, g'')
		where
			(low30Bits,g') = next g
			(highBits,g'') = randomIndex (shiftR maxIndex 30) g'