sawine@5: """
sawine@5: Author: Eugen Sawin <sawine@informatik.uni-freiburg.de>
sawine@5: """
sawine@5: import math
sawine@5: 
sawine@5: def main():    
sawine@5:     args = parse_arguments()
sawine@5:     if args.d:
sawine@5:         probe = double_hash
sawine@5:     elif args.l:
sawine@5:         probe = linear_probing
sawine@5:     elif args.q:
sawine@5:         probe = quadratic_probing
sawine@5:     else:
sawine@5:         print "you need to select a probing procedure"
sawine@5:         exit()
sawine@5:     table = {}
sawine@5:     for key in args.values.split():
sawine@5:         table = hash(int(key), args.table_size, table, probe)
sawine@5:     for k, v in table.iteritems():      
sawine@5:         print "%i: %i" % (k, v)
sawine@5:     #print "%s: %i" % (key, double_hash(int(key), used))
sawine@5: 
sawine@5: def hash(k, size, table, probe):
sawine@5:     j = 0
sawine@5:     code = h(k, size) % size
sawine@5:     while code in table:
sawine@5:         j += 1
sawine@5:         code = (h(k, size) - probe(j, k, size)) % size
sawine@5:     table[code] = k
sawine@5:     return table
sawine@5: 
sawine@5: def linear_probing(j, k, size):
sawine@5:     return j
sawine@5: 
sawine@5: def quadratic_probing(j, k, size):
sawine@5:     return (-1)**j * math.ceil(j/2.0)**2
sawine@5: 
sawine@5: def double_hash(j, k, size):
sawine@5:     return j * h2(k, size)
sawine@5: 
sawine@5: def h(k, size):
sawine@5:     return k % size
sawine@5: 
sawine@5: def h2(k, size):
sawine@5:     return 1 + (k % (size - 2)) 
sawine@5: 
sawine@5: from argparse import ArgumentParser
sawine@5: 
sawine@5: def parse_arguments():
sawine@5:     parser = ArgumentParser(description="Returns the hash for given string using the double-hash technique.")
sawine@5:     parser.add_argument("table_size", type=int, help="size of the hash table")
sawine@5:     parser.add_argument("values", help="values")    
sawine@5:     parser.add_argument("-d", action="store_true", help="double hashing")
sawine@5:     parser.add_argument("-l", action="store_true", help="linear probing")
sawine@5:     parser.add_argument("-q", action="store_true", help="quadratic probing")
sawine@5:     return parser.parse_args()
sawine@5: 
sawine@5: if __name__ == "__main__":
sawine@5:     main()