#!/usr/bin/python

# cython: language_level=3

"""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 range(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 range(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 range(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 range(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