#!/usr/bin/env python

'''Simple radix sort'''

import sys
#mport copy
import math
#mport time

ifdef(m4pyx,cdef )class Comparator(object):
    # pylint: disable=R0903,E1101
    # R0903: We don't need a lot of public methods; we're a base class
    # E1101: We're an abstract class, so of course some things don't exist yet
    '''Abstract base class for our comparators'''
    ifdef(m4pyx,cdef )def __init__(self, chunk_size):
        self.chunk_size = chunk_size
        self.max_length = None
        self.part = None

    ifdef(m4pyx,c)def radix_sort(self, list_):
        # pylint: disable=E1101
        # E1101: We are a base class; not everything we require exists yet
        '''Perform a radix sort'''
        self.max_length = max(self.length(element) for element in list_)
        # go from least significant "digit" to most
        self.part = self.initial_part
        for dummy in range(self.max_length):
            temps = [ [] for dummy2 in range(self.indices()) ]
            for element in list_:
                ind = self.`index'(element)
                temps[ind].append(element)
            self.next()
            list_ = []
            for temp in temps:
                list_.extend(temp)
        return list_

ifdef(m4pyx,cdef )class Int_comparator(Comparator):
    '''Integer comparator'''
    ifdef(m4pyx,c)def __init__(self, base):
        Comparator.__init__(self, base)
        self.part = Int_comparator.initial_part

    ifdef(m4pyx,c)def `index'(self, number):
        '''Find the index of this chunk'''
        return (number // self.part) % self.chunk_size

    ifdef(m4pyx,c)def length(self, i):
        '''Compute the "length" of an integer, base self.chunk_size'''
        retval = 0
        j = i
        while j > 0:
            j //= self.chunk_size
            retval += 1
        return retval

    initial_part = 1

    ifdef(m4pyx,c)def next(self):
        '''Compute where the "part" of an integer lies'''
        self.part *= self.chunk_size

    ifdef(m4pyx,c)def indices(self):
        '''Return an index for our chunk size'''
        return self.chunk_size * 8 + 1

ifdef(m4pyx,cdef )class Str_comparator(Comparator):
    '''String comparator'''
    ifdef(m4pyx,c)def __init__(self, base):
        Comparator.__init__(self, base)
        self.part = Str_comparator.initial_part

    # returns an integer!
    ifdef(m4pyx,c)def `index'(self, string):
        '''Compute the "index" of a chunk'''
        total = 0
        # need to chnage this to go from most significant to least, not least to most
        left = self.part
        right = self.part + self.chunk_size - 1
        # we can't just use a negative index here, because not all strings have the same length
        releft = self.max_length*self.chunk_size - left - 1
        reright = self.max_length*self.chunk_size - right - 1
        for i in range(reright, releft+1):
            piece = string[i:i+1]
            if piece == '':
                total *= 257
            else:
                total = total * 257 + ord(piece) + 1
        return total

    ifdef(m4pyx,c)def length(self, string):
        '''Compute the "length" of a string in chunks'''
        # this needs to change somehow - we're sometimes in chunks of chunk_size, and sometimes in bytes - in the
        # string version
        subresult = float(`len'(string)) / float(self.chunk_size)
        result = int(math.ceil(subresult))
        return result

    initial_part = 0

    ifdef(m4pyx,c)def next(self):
        '''Find the position of the next chunk'''
        self.part += self.chunk_size

    ifdef(m4pyx,c)def indices(self):
        '''Find the index of a chunk'''
        # the + chunk_size is to hold null strings
        return int(math.pow(2, self.chunk_size * 8)) + self.chunk_size

ifdef(m4pyx,cp)def radix_sort(list_):
    '''A radix sort that makes use of our previously-defined comparators as needed'''
    if list_[1:]:
        if type(list_[0]) == type(''):
            comparator = Str_comparator(2)
        elif type(list_[0]) == type(0):
            comparator = Int_comparator(1000)
        else:
            sys.stderr.write('Sorry, radix_sort can only sort integers or strings at this time\n')
            sys.exit(1)
    else:
        return list_
    sorted_result = comparator.radix_sort(list_)
    list_[:] = sorted_result