#!/usr/local/cpython-2.7/bin/python

#rofile_it = True
profile_it = False

import os
import sys
import time
import random
import functools

class Test:
	def __init__(self, kind, generate, proportion):
		self.kind = kind
		self.generate = generate
		self.proportion = proportion

class Slow_comparisons:
	def __init__(self, x):
		self.x = x

	def __cmp__(self, other):
		time.sleep(0.0000003)
		#print type(self), type(other)
		#sys.stdout.flush()
		return cmp(self.x, other.x)

def slow_generate(n):
	return [ Slow_comparisons(x) for x in xrange(n) ]

def small_generate(n):
	return range(n)

tests = [ \
	Test('slow', slow_generate, 1), \
	Test('small', small_generate, 2), \
	]

# 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

#mport quicksort_py as quicksort
import quicksort as quicksort

#mport insertionsort_py as insertionsort
import insertionsort as insertionsort

#mport binarysort_py as binarysort
import binarysort as binarysort

#mport bubblesort_py as bubblesort
import bubblesort as bubblesort

#mport shellsort_py as shellsort
import shellsort as shellsort

#mport mergesort_py as mergesort
import mergesort as mergesort

#mport timsort_reimp_py as timsort_reimp
import timsort_reimp as timsort_reimp

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_cext_fn(list_):
	list_.sort()

def timsort_cython_fn(list_):
	timsort_reimp.timsort(list_)

def mergesort_cython_fn(list_):
	mergesort.mergesort(list_)

def funnelsort_cython_fn(list_):
	funnelsort.funnelsort(list_)

def stable_quicksort_cython_fn(list_):
	quicksort.quicksort(list_, stable=True)

def quicksort_cython_fn(list_):
	quicksort.quicksort(list_)

def shellsort_cython_fn(list_):
	shellsort.shellsort(list_)

def insertionsort_cython_fn(list_):
	insertionsort.insertionsort(list_, 0, len(list_) - 1)

def binarysort_cython_fn(list_):
	binarysort.binarysort(list_, 0, len(list_) - 1)

def bubblesort_cython_fn(list_):
	bubblesort.bubblesort(list_, 0, len(list_) - 1)

for test in tests:
	for exponent in xrange(25):
		# we intentionally don't pick something nice and round, because we want to make sure merge sort doesn't get all powers of 2
		size = 3**exponent

		tuples = [ \
			('bubblesort_cython',       bubblesort_cython_fn,        6), \
			('insertionsort_cython',    insertionsort_cython_fn,     7), \
			('binarysort_cython',       binarysort_cython_fn,        7), \
			('shellsort_cython',        shellsort_cython_fn,        14), \
			('quicksort_cython',        quicksort_cython_fn,        14), \
			('stable_quicksort_cython', stable_quicksort_cython_fn, 14), \
			('funnelsort_cython',       funnelsort_cython_fn,       14), \
			('mergesort_cython',        mergesort_cython_fn,        14), \
			('timsort_cext',            timsort_cext_fn,            14), \
			('timsort_cython',          timsort_cython_fn,          14), \
			]

		for algorithm_description, algorithm_code, max_exponent in tuples:
			algorithm_description = '%s_%s' % (test.kind, algorithm_description)
			if exponent > max_exponent:
				continue
			sys.stdout.write('%30s 3**%0d ' % (algorithm_description, exponent))
			sys.stdout.write('ge')
			sys.stdout.flush()
			ints = test.generate(size)
			#for x in xrange(size):
			#	ints.append(Slow_comparisons(x))
			#print 'size is,', size, 'ints is', ints
			sys.stdout.write('t ')
			sys.stdout.write('shuff')
			sys.stdout.flush()
			shuffle(ints)
			sys.stdout.write('le ')
			sys.stdout.flush()

			sys.stdout.write('so')
			sys.stdout.flush()
			t0 = time.time()
			if profile_it:
				profile.run('algorithm_code(ints_copy)')
			else:
				algorithm_code(ints)
			t1 = time.time()
			diff_time = t1 - t0
			if is_sorted(ints, test.generate(size)):
				print 'rt', diff_time
			else:
				print 'rt', diff_time, 'failed'
				sys.exit(1)
			append('%s.dat' % algorithm_description, size, diff_time)