radix.py

"""
A radix sort implementation to illustrate:

    + testing with doctest
    + __main__
    + yield
    + refactoring for legibility (your future self may thank you)
    + Python is __magic__
    + PEP 8
    + ...
"""

from collections import deque


def radix(sequence):
    """Sort sequence of positiver integers using LSD radix sort

    >>> radix([])
    []

    >>> radix([1])
    [1]

    >>> radix([2, 1, 3, 1, 2])
    [1, 1, 2, 2, 3]

    >>> radix([11, 1])
    [1, 11]

    >>> radix([11, 1, 2])
    [1, 2, 11]

    >>> radix([2000, 30, 10])
    [10, 30, 2000]

    >>> import random
    >>> data = [random.randint(1, 10000) for _ in range(100)]
    >>> all(r == t for r, t in zip(radix(data), sorted(data)))
    True
    """
    buckets = Buckets(range(10))
    buckets[0] = sequence
    N = max_number_of_digits(sequence)
    for n in range(1, N + 2):
        for element in buckets:
            digit = least_significant_nth_digit(element, n)
            buckets[digit].append(element)
    return list(buckets[0])


class Buckets(object):
    """Buckets of Queue(s) associated to keys from the instantiating sequence

    Iterable consumes its values (frozen) in order of the instantiating sequence
    then appending order (FIFO over mutliple queues).

    >>> buckets = Buckets(range(10))

    >>> buckets[0]
    Queue([])

    >>> buckets[0] = [1, 2, 3]
    >>> buckets[0]
    Queue([1, 2, 3])

    >>> for elements in buckets:
    ...     pass
    """
    def __init__(self, keys):
        self.keys = keys
        self._dict = {key: Queue() for key in keys}

    def __getitem__(self, key):
        return self._dict[key]

    def __setitem__(self, key, sequence):
        for element in sequence:
            self._dict[key].append(element)

    def __iter__(self):
        man = [(key, len(self._dict[key])) for key in self.keys]
        for key, count in man:
            for _ in range(count):
                yield self._dict[key].pop()

def max_number_of_digits(sequence):
    """
    >>> max_number_of_digits([1, 45, 890, 2])
    3

    >>> max_number_of_digits([])
    0
    """
    return len(str(max(sequence))) if sequence else 0

def least_significant_nth_digit(integer, n):
    """
    >>> least_significant_nth_digit(23, 1)
    3

    >>> least_significant_nth_digit(23, 2)
    2

    >>> least_significant_nth_digit(23, 3)
    0
    """
    i = 1
    man = integer
    while i <= n and man > 0:
        result = man % 10
        man /= 10
        i += 1
    if i > n:
        return result
    else:
        return 0

class Queue(object):
    """An iterable FIFO queue

    append at the back
    pop from the front

    >>> queue = Queue()
    >>> for i in range(10):
    ...     queue.append(i)

    >>> queue.pop()
    0

    >>> len(queue)
    9
    """

    def __init__(self):
        self._deque = deque()

    def append(self, value):
        self._deque.append(value)

    def pop(self):
        return self._deque.popleft()

    def __iter__(self):
        for value in self._deque:
            yield value

    def __len__(self):
        return len(self._deque)

    def __repr__(self):
        return 'Queue({0})'.format(list(self._deque))


if __name__ == '__main__':
    import doctest
    doctest.testmod()