"""

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()