def new_hash_table(size)
  ht = Array.new(size)
  for i in 0..size-1 do
    ht[i] = []
  end
  return ht
end

def ht_insert!(ht, key, hash_fun)
  if hash_fun == "h0"
    bucket = ht[h0(key,ht.length)] 
  elsif hash_fun == "h1"
    bucket = ht[h1(key,ht.length)] 
  elsif hash_fun == "h2"
    bucket = ht[h2(key,ht.length)] 
  elsif hash_fun == "h3"
    bucket = ht[h3(key,ht.length)] 
  elsif hash_fun == "h4"
    bucket = ht[h4(key,ht.length)] 
  end

  bucket << key
end

def ht_search?(ht, key, hash_fun)
  if hash_fun == "h0"
    bucket = ht[h0(key,ht.length)] 
  elsif hash_fun == "h1"
    bucket = ht[h1(key,ht.length)] 
  elsif hash_fun == "h2"
    bucket = ht[h2(key,ht.length)] 
  elsif hash_fun == "h3"
    bucket = ht[h3(key,ht.length)] 
  elsif hash_fun == "h4"
    bucket = ht[h4(key,ht.length)] 
  end

  bucket.each {|entry|
    return true if entry == key
  }
  return false
end


def h0(key,ht_size)
  return 0
end

def h1(key,ht_size)
  return key[0] % ht_size
end

def h2(key,ht_size)
  x = 0
  for i in 0..key.length-1 do
    ascii_code = key[i]
    x = x + ascii_code
  end
  return x % ht_size
end

def h3(key,ht_size)
  x = 0
  for i in 0..key.length-1 do
    ascii_code = key[i]
    x = 128 * x + ascii_code
  end
  return x % ht_size
end


def run(hash_fun)
  #create a hash table with 10000 buckets
  size = 10000
  ht = nil
  create_time = time {
    ht = new_hash_table(size)
  }
  print "Created hash table with ", size, " buckets in "
  print create_time, " seconds\n"

  # Make the experiments repeatable by seeding a constant number
  # in the random number generator
  srand(15110)

  # create an array with a couple hundred thousand words in random order
  words = TestArray.new(:all, :words)

  # insert each word into the hash table
  insert_time = time {
    words.each{|x|
      ht_insert!(ht, x, hash_fun)
    }
  }
  print "Inserted ", words.length, " words in ", insert_time, " seconds.\n"

  # lookup a hundred words
  lookup_time = time {
    100.times {
      random_word = words[rand(words.length)]
      ht_search?(ht, random_word, hash_fun)
    }
  }
  print "Searched for 100 words in ", lookup_time, " seconds.\n"

  print "\nStatistics: \n"
  print "  number of entries in largest bucket: ", largest_bucket(ht), "\n"
  print "  mean size of non-empty buckets: ", mean_bucket(ht), "\n"
end