module Hash where
import "Array"
import "Utils"

-- principle of the dictionary
-- hash of a string = integer part of
--  ((ord(char1) * ... * ord(char2))/500)*5 
-- This leaves the first 4 entries unused;
-- five entries are reserved for each hash-value;
-- when four are filled in extra space is reserved ;
-- the fifth entry points to the extra space (second entry
-- of the tuple; the string part is nil.)
-- 1000 places are reserved for extensions;
-- for a maximum number of atoms 3500.
-- The index is a string; the content type is generic.
-- Author: G.Naudts. Mail: naudts_vannoten@yahoo.com.

nthentry = 5
dictSize :: Int
dictSize = 3500
modSize = 500

data Content a = Content a|CNull
type Dict a = Array Int (Content a, String, Int) 
type ParamArray = Array Int Int

params :: Array Int Int
params = array (1,b) [ (i,0)| i <- [1 .. b]]

b :: Int
b = 10

-- show element n
f1 n = intToString(params1!n)
-- set element 5 to 1
    where params1 = params // [(5,1)]

dict :: Dict String
dict = array (1,dictSize) [ (i,(CNull,"",0)) | i <- [1 .. dictSize]]

initDict :: ParamArray -> ParamArray
initDict params = params4
   where params1 = params // [(1, 2520)] -- entry 1 is begin of overflow zone
         params2 = params // [(2, 3500)] -- entry 2 is array size of dict
         params3 = params // [(3, 500)]  -- entry 3 is modsize for hashing
         params4 = params // [(4, 5)]    -- entry 4 is zone size
 
f2 = show (ord 'a')  -- result 97

hash :: String -> Int
hash "" = -1                       
hash s  
       |bv1 = -1
       |x < 0 = fromInteger(x + modSize)
       |otherwise = fromInteger x 
       where x = ((fromInt(hash1 s)) `mod` modSize)*nthentry + 1
             bv1 = x == -1

-- hash1 makes the product of the ordinal numbers minus 96
hash1 :: String -> Int
hash1 "" = 1
hash1 (x:xs) = (ord x) * (hash1 xs) * 7


-- Next Int = gives the first entry of an overflow zone
-- Oflow indicates an overflow zone has to bee created
data Entry = Occupied|Free|Next Int|OFlow|Full

-- put a string in the dictionary
-- format of an entry = (content, String, Int). 
-- Steps: 1) get a hash of the string
--        2) read the entry. There are four possibilities:
--          a) The entry is empty. If it is the nth-entry (global constant)
-- then an extension must be created.
--          b) it is an available entry: put the tuple in place.
--          c) The content = CNull. This is a reference to another zone.
--             Get the referred adres (the int)
--              and restart at 2 with a new entry.
--          d) The string != "". Read the next entry.
putEntry :: String -> Content a -> Dict a
                                  -> ParamArray -> Dict a
putEntry s content dict params
        = putInHash index content 0 dict params 
	where index = hash s
              n = 0
              putInHash index content n dict params =
                 case entry of
                    Full -> dict
                    OFlow -> putInHash oFlowNr content 0 dict1 params1
                    Free -> dict2
                    Occupied ->  putInHash (index + 1) content (n + 1) dict params
                    Next next -> putInHash next content 0 dict params
                 where entry = checkEntry index n dict params
                       n1 = 0
                       oFlowNr = params!1  -- begin of overflow zone
                       dict1 = dict // [(index,(CNull,"",oFlowNr))]
                       oFlowNr1 = oFlowNr + 5
                       -- store updated begin of overflow zone 
                       params1 = params // [(1,oFlowNr1)]
                       dict2 = dict // [(index, (content, s, 0))]

-- check the status of an entry
-- The first int is the array index; the second int is the index in the zone;
-- if this int is equal to the zonesize then overflow.
checkEntry :: Int -> Int -> Dict a -> ParamArray -> Entry
checkEntry index nb dict params
        |index > params!2 = Full
        |next == 0 && nb == zoneSize = OFlow
        |next == 0 = Free
        |next /= 0 && nb == zoneSize = Next next  
        |next /= 0 = Occupied
	where zoneSize = params!4
              (_,_,next) = dict!index  -- next gives index of overflow zone

-- get a content from the dictionary
-- get a hash of the searched for entry.
-- read at the hash-entry; three possibilities:
-- a) the string is found at the entry; return the content
-- b) next index = 0. Return False.
-- c) the index is greater than the maximum size; return False.
-- d) get the next string.
getEntry :: String -> Dict a -> ParamArray -> (Bool, Content a)
getEntry s dict params
        = readEntry index s dict params
        where index = hash s
              readEntry index s dict params
                  |bool == False = (False, c)
                  |bool == True = (True, c)
                  where (bool, c) = checkRead index s dict params

-- check an entry for reading and return the content
checkRead :: Int -> String -> Dict a -> ParamArray -> (Bool, Content a)
checkRead index s dict params
        |bv1 = (False, CNull)
        |s == s1 = (True, Content a)
        |next == 0 = (False, CNull)
        |otherwise = checkRead next s dict params
        where (Content a, s1, next) = dict!index
              bv1 = index > params!2