#!/usr/bin/python

#rofile_it = True
profile_it = False

import os
import sys
import time
import random
import functools

# this does a function-resolution profiling
if profile_it:
	import cProfile
	profile = cProfile

#import psyco
#psyco.full()

#mport funnelsort_py as funnelsort
import funnelsort as funnelsort

sys.setrecursionlimit(100000)

def append(filename, size, duration):
	file = open(filename, 'a')
	file.write('%d %f\n' % (size, duration))
	file.close()
	
def shuffle(lst):
	len_lst = len(lst)
	for index in xrange(len_lst):
		random_index = int(random.random() * len_lst)
		lst[index], lst[random_index] = lst[random_index], lst[index]

def is_sorted(test_list, original_list):
	if test_list == original_list:
		return True
	else:
		return False

def timsort_fn(list_):
	list_.sort()

def funnelsort_fn(list_):
	funnelsort.funnelsort(list_)

for x in xrange(8):
#for x in xrange(6):
#for x in [ 7 ]:
#for x in xrange(5):
#for x in xrange(2):
	size = 10**x
	#ints = [ 1, 5, 8, 3, 10, 101, 9999, 23, 2000 ]

	tuples = [ \
		('timsort', timsort_fn), \
		('funnelsort', funnelsort_fn), \
		]

	for algorithm_description, algorithm_code in tuples:
		print 'starting getting %d (10**%d) consecutive integers, %s' % (size, x, time.ctime(time.time()))
		ints = range(size)
		print 'done getting %d consecutive integers, %s' % (size, time.ctime(time.time()))
		print 'starting shuffling %d consecutive integers, %s' % (size, time.ctime(time.time()))
		shuffle(ints)
		print 'done shuffling %d consecutive integers, %s' % (size, time.ctime(time.time()))

		print 'starting', algorithm_description, time.ctime(time.time())
		t0 = time.time()
		if profile_it:
			profile.run('algorithm_code(ints_copy)')
		else:
			algorithm_code(ints)
		t1 = time.time()
		if is_sorted(ints, range(size)):
			print 'sorted correctly'
		else:
			print 'sorted _in_correctly'
			print ints
			sys.exit(1)
		print 'done with', algorithm_description, time.ctime(time.time())
		diff_time = t1 - t0
		append('%s.dat' % algorithm_description, size, diff_time)
		print algorithm_description, 'time was', diff_time