Table.hs

{-# LANGUAGE BangPatterns #-}
--
-- orbit-int hash table (storing vertices on a worker)
--
module Table( -- Types
              Freq
            , VTable
            , Vertex
              -- Functions
            , new
            , to_list
            , is_member
            , insert
            , get_freq
            , sum_freqs
            , sum_freqs2
            , freq_to_slots
            , freq_to_nonempty_slots
            , freq_to_vertices
            , max_freq
            , avg_freq
            , avg_nonempty_freq
            , freq_to_stat
            , freq_from_stat
            , fill_deg
            ) where

import Data.Array (Array, elems, listArray, (!), (//))

import Utils      (Vertex)

type Freq   = [Int]
type VTable = Array Int [Vertex]
type TableStats = [(String, String)]

-- Note: Hash tables have a fixed number of slots but each slot can store
-- a list of vertices. The functions is_member/3 and insert/3
-- expect its slot argument to be in range.

-- new(Size) creates a table with Size slots, each containing an empty list.
new :: Int -> VTable
new size = listArray (0, size - 1) $ cycle [[]]

-- to_list(T) converts a table T into a list of its entries.
to_list :: VTable -> [Vertex]
to_list arr = concat' (elems arr) []

concat' :: [[Vertex]] -> [Vertex] -> [Vertex]
concat' [] acc = acc
concat' ((h:t):t') acc = concat' (t:t') (h:acc)
concat' (([]):t) acc = concat' t acc

-- is_member(X, I, T) is true iff X is stored in table T at slot I.
is_member :: Vertex -> Int -> VTable -> Bool
is_member x i t = elem x (t ! i)

-- insert(X, I, T) inserts X into table T at slot I.
insert :: Vertex -> Int -> VTable -> VTable
insert !x i t = t!i `seq` t // [(i, x : t ! i)]

-- get_freq computes the fill frequency of table T;
-- the output is a list of integers where the number at position I
-- indicates how many slots of T are filled with I entries;
-- the sum of the output lists equals the number of slots of T.
get_freq :: VTable -> Freq
get_freq t = elems $ foldl (flip inc) freqArr freqs
  where freqs = map length $ elems t
        maxFreq = foldl max (head freqs) (tail freqs)
        freqArr = listArray (0, maxFreq) $ cycle [0]

-- freq_to_slots computes the number of slots from a table fill frequency.
freq_to_slots :: Freq -> Int
freq_to_slots = sum

-- freq_to_nonempty_slots computes the number of non empty slots from a table
-- fill frequency.
freq_to_nonempty_slots :: Freq -> Int
freq_to_nonempty_slots = sum . tail

-- freq_to_vertices computes the number of vertices from a table fill frequency.
freq_to_vertices :: Freq -> Int
freq_to_vertices f = snd $ foldl (\(i, x) n -> (i + 1, (i * n + x))) (0, 0) f

-- max_freq returns the maximum fill frequency.
max_freq :: Freq -> Int
max_freq f = length f - 1

-- avg_freq returns the average fill frequency
avg_freq :: Freq -> Float
avg_freq f = (fi $ freq_to_vertices f) / (fi $ freq_to_slots f)

-- avg_nonempty_freq returns the average fill frequency of non empty slots.
avg_nonempty_freq :: Freq -> Float
avg_nonempty_freq f =
    if verts > 0 then (fi verts) / (fi $ freq_to_nonempty_slots f)
    else 0.0
  where verts = freq_to_vertices f

-- fill_deg determines the filling degree of the table.
fill_deg :: Freq -> Float
fill_deg f = (fi $ freq_to_nonempty_slots f) / (fi $ freq_to_slots f)

-- sum_freqs/2 sums two fill frequencies.
sum_freqs2 :: Freq -> Freq -> Freq
sum_freqs2 [] sumF = sumF
sum_freqs2 f [] = f
sum_freqs2 (n : f) (m : sumF) = n + m : sum_freqs2 f sumF

-- sum_freqs/1 sums a list of fill frequencies.
sum_freqs :: [Freq] -> Freq
sum_freqs fs = foldl (flip sum_freqs2) [] fs

-- freq_to_stat produces a readable statistics from a table fill frequency;
-- the input frequency F is itself part of the statistics
freq_to_stat :: Freq -> TableStats
freq_to_stat frequency =
    [ ("freq", show frequency)
    , ("size", show $ freq_to_vertices frequency)
    , ("slots", show $ freq_to_slots frequency)
    , ("nonempty_slots", show $ freq_to_nonempty_slots frequency)
    , ("fill_deg", show $ fill_deg frequency)
    , ("max_freq", show $ max_freq frequency)
    , ("avg_freq", show $ avg_freq frequency)
    , ("nonempty_avg_freq", show $ avg_nonempty_freq frequency) ]

-- freq_from_stat extracts a table fill frequency from a statistics Stat
-- (assuming Stat was produced by freq_to_stat/1, otherwise returns []);
freq_from_stat :: TableStats -> Freq
freq_from_stat stat =
    case "freq" `lookup` stat of
        Just val -> read val :: [Int]
        Nothing -> []

--------------------------------------------------------------------------------
-- auxiliary functions
inc :: Int -> Array Int Int -> Array Int Int
inc i t = t!i `seq` t // [(i, t!i + 1)]

fi :: (Integral a, Num b) => a -> b
fi = fromIntegral