"""

 Name: perfect_hashing - applies the two-level scheme to build a perfect hash function

 Description: Perfect Hashing builds a perfect hash function.

 Author: Eugen Sawin <sawine@me73.com>

 """

 def main():

 	args = parse_args()

 	N = args.n

 	k = args.k

 	s = [int(e) for e in args.s.split(',')]

 	perfect_hashing(N, len(s), k, s)

 def hkx(N, n, k, x):

 	return ((k*x) % N) % n

 def find_ki(N, mi, Wi):

 	def injective():

 		hx = []

 		for x in Wi:

 			thx = hkx(N, mi, ki, x)

 			if thx in hx:

 				return False

 			else:

 				hx.append(thx)

 		return True

 	ki = 1

 	while not injective():

 		ki += 1

 	return ki

 def perfect_hashing(N, n, k, xi):

 	hx = {}

 	for x in xi:

 		hx[(k, x)] = hkx(N, n, k, x)

 		print "h%i(%i) = (%i * %i mod %i) mod %i = %i" % (k, x, k, x, N, n, hx[(k,x)])	

 	ml = []

 	sl = [] 

 	kl = []

 	for i in xrange(n):

 		Wi = [thx[0][1] for thx in hx.iteritems() if thx[1] == i]

 		bi = len(Wi)

 		mi = 2 * bi * (bi - 1) + 1

 		si = sum(ml)

 		ki = find_ki(N, mi, Wi)

 		ml.append(mi)

 		sl.append(si)

 		kl.append(ki)

 		print "\nW%i = " % i, Wi

 		print "=> b%i = %i" % (i, bi), "m%i = %i" % (i, mi), "s%i = %i" % (i, si), "k%i = %i" % (i, ki)

 		if bi > 1:

 			print "=> hk%i = (%i * x mod %i) mod %i" % (i, ki, N, mi)

 	print

 	for x in xi:

 		i = hx[(k, x)]

 		posx = sl[i] + hkx(N, ml[i], kl[i], x)

 		print "x = %i => pos(%i) = %i" % (x, x, posx)

 from argparse import ArgumentParser

 def parse_args():

     parser = ArgumentParser(description='Builds a perfect hash function.')

     parser.add_argument('n', type=int, help='size of the universe U')

     parser.add_argument('k', type=int, help='parameter k of the hash function')

     parser.add_argument('s', help='comma-separated values defining the given set S')

     return parser.parse_args()

 if __name__ == "__main__":

 	main()