#!/usr/bin/python

'''Module provides a quick sort implementation'''

import insertionsort

def quicksort(ifdef(`m4pyx',list )list_, stable=False):
	'''Quicksort function'''
	if stable:
		stable_quicksort(list_)
	else:
		unstable_quicksort(list_)

def stable_quicksort(ifdef(`m4pyx',list )list_):
	'''Decorate, sort, undecorate - to make quicksort stable'''
	length = `len'(list_)
	# decorate, sort, undecorate - to make it stable
	decorated = []
	for index, value in enumerate(list_):
		decorated.append((value, index))
	del list_[:]
	quicksort_c(decorated, 0, length - 1)
	for value, index in decorated:
		list_.append(value)

def unstable_quicksort(ifdef(`m4pyx',list )list_):
	'''Fast quicksort - ignore stability'''
	length = `len'(list_)
	quicksort_c(list_, 0, length - 1)

ifdef(`m4pyx',c)def is_inorder(ifdef(`m4pyx',list )list_, ifdef(`m4pyx',unsigned int) left, ifdef(`m4pyx',unsigned int) right):
	'''Is the list passed in order for the region of interest?'''
	ifdef(`m4pyx',cdef unsigned int index)
	for index in xrange(left, right - 1):
		if list_[index] > list_[index+1]:
			return False
	return True

ifdef(`m4pyx',c)def is_reverseorder(ifdef(`m4pyx',list )list_, ifdef(`m4pyx',unsigned int) left, ifdef(`m4pyx',unsigned int) right):
	'''Is the list passed in reverse order for the region of interest?'''
	ifdef(`m4pyx',cdef unsigned int index)
	for index in xrange(left, right - 1):
		if list_[index] < list_[index+1]:
			return False
	return True

ifdef(`m4pyx',c)def reverse_order(ifdef(`m4pyx',list )list_, ifdef(`m4pyx',unsigned int) left, ifdef(`m4pyx',unsigned int) right):
	'''Reverse the order of the list subregion of interest'''
	ifdef(`m4pyx',cdef unsigned int width)
	ifdef(`m4pyx',cdef unsigned int index)
	width = right - left + 1
	for index in xrange(width / 2):
		left_index = left + index
		right_index = right - index
		list_[left_index], list_[right_index] = list_[right_index], list_[left_index]

ifdef(`m4pyx',c)def quicksort_c(ifdef(`m4pyx',list )list_, ifdef(`m4pyx',unsigned int) left, ifdef(`m4pyx',unsigned int) right):
	'''The behind-the-scenes quicksort function'''
	# How many values?
	ifdef(`m4pyx',cdef unsigned int num_values)
	ifdef(`m4pyx',cdef unsigned int pivot_index)
	ifdef(`m4pyx',cdef unsigned int store_index)
	num_values = right - left + 1
	# 31 is arbitrary and is perhaps something to tune
	if num_values < 31:
		insertionsort.insertionsort(list_, left, right)
	else:
		if right > left:
			sample_values = []
			quarter = num_values / 4
			for index in [ left, left + quarter, left + num_values / 2, left + quarter * 3, right ]:
				sample_values.append((list_[index], index))
			length_of_sample_values_m1 = `len'(sample_values) - 1
			if is_inorder(sample_values, 0, length_of_sample_values_m1):
				if is_inorder(list_, left, right):
					return
			elif is_reverseorder(sample_values, 0, length_of_sample_values_m1):
				if is_reverseorder(list_, left, right):
					reverse_order(list_, left, right)
					return
			insertionsort.insertionsort(sample_values, 0, 4)
			pivot_index = sample_values[2][1]
			# the number of ways we split this is arbitrary and perhaps something to tune.  It's traditional to split in half, but is that best?
			store_index = partition(list_, left, right, pivot_index)
			quicksort_c(list_, left, store_index - 1)
			quicksort_c(list_, store_index + 1, right)

ifdef(mypyx,c)def partition(ifdef(`m4pyx',list )list_, ifdef(`m4pyx',unsigned int) left, ifdef(`m4pyx',unsigned int) right, ifdef(`m4pyx',unsigned int) pivot_index):
	'''partition function - see any good definition of how quicksort works'''
	ifdef(`m4pyx',cdef unsigned int store_index)
	ifdef(`m4pyx',cdef unsigned int i)
	pivot_value = list_[pivot_index]
	# Move pivot to end
	list_[pivot_index], list_[right] = list_[right], list_[pivot_index]
	store_index = left
	# left <= i < right  
	for i in xrange(left, right):
		if list_[i] <= pivot_value:
			list_[i], list_[store_index] = list_[store_index], list_[i]
			store_index += 1
	# Move pivot to its final place
	list_[store_index], list_[right] = list_[right], list_[store_index]
	return store_index