#!/usr/bin/python

import os
import time
import random

import radixsort

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):
#		percentage = index * 100.0 / len_lst
#		if index and percentage % 10 == 0:
#			print percentage
		random_index = int(random.random() * len_lst)
		lst[index], lst[random_index] = lst[random_index], lst[index]

def is_sorted(lst):
	if not lst:
		return True
	else:
		for left, right in zip(lst, lst[1:]):
			if left > right:
				return False
		return True

if 0 == 1:
	#ints = [ 1, 5, 8, 3, 10, 101, 9999, 23, 2000 ]
	print 'getting consecutive integers'
	ints = range(10000000)
	print 'shuffling integers'
	shuffle(ints)

	print 'starting int sort', time.ctime(time.time())
	# two digits at a time
	int_c = int_comparator(100)
	dummy = int_c.radix_sort(ints)
	print 'done with int sort', time.ctime(time.time())
	ints.sort()
	print 'done with native int sort', time.ctime(time.time())
elif 0 == 2:
	import random

	def random_char():
		return chr(int(random.random()*26) + ord('a'))
		
	def random_string(letters):
		lst = []
		for s_no in xrange(letters):
			lst.append(random_char())
		return ''.join(lst)
		
	#strings = [ 'abd', 'abc', 'defg', 'hijkl', 'bongo', 'string value', 'gorilla' ]
	if 1 == 1:
		strings = []
		for s_no in xrange(1000000):
			strings.append(random_string(int(random.random() * 20) + 1))
		strings_copy = copy.copy(strings)
	elif 0 == 1:
		strings = [ 'auoalzkrd', 'aounci' ]
	#shuffle(strings)
	print 'radix sorting'
	str_c = str_comparator(1)
	result = str_c.radix_sort(strings)
	print 'done radix sorting'
	if is_sorted(result):
		print 'sorted correctly'
	else:
		print 'sorted _in_correctly'
	print 'tim sorting'
	strings_copy.sort()
	print 'done tim sorting'
if 3 == 3:
	for x in xrange(9):
		size = 10**x
		#ints = [ 1, 5, 8, 3, 10, 101, 9999, 23, 2000 ]
		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()))

		ints_copy = ints[:]

		print 'starting int radix_sort', time.ctime(time.time())
		t0 = time.time()
		# two digits at a time
		dummy = radixsort.radix_sort(ints)
		t1 = time.time()
		print 'done with int sort', time.ctime(time.time())
		diff_radix_sort = t1 - t0
		append('radix_sort.dat', size, diff_radix_sort)
		print 'radix sort time was', diff_radix_sort
		print 'starting tim sort', time.ctime(time.time())
		t0 = time.time()
		ints_copy.sort()
		t1 = time.time()
		print 'done with tim sort', time.ctime(time.time())
		diff_tim_sort = t1 - t0
		print 'tim sort time was', diff_tim_sort
		append('tim_sort.dat', size, diff_tim_sort)
		print 'radix sort time was %3.2f%% of the tim sort time' % (float(diff_radix_sort - diff_tim_sort) * 100.0 / diff_tim_sort)
		print