# Programmer: Don Curtis
# Date: March 23rd, 2009
import random

# generate a random list of integers
# list size = n, range of ints: 1 to max
def genIntList(n, max):
    # we are generating a new list so define it
    lst = []
    for i in range(n):
        # create a new random integer (r)
        r = random.randint(1, max)

        # append this random integer to our list
        lst.append(r)

    # return our list
    return lst

def countingSort(lst, max):
    # let counters be a list that counts occurances of
    # numbers in the range 1 to max
    counters = []

    # initially counters is an empty list (ie. there are no elements)
    # but since we want counters[i] to hold the number of occurances
    # of the number 'i' in our list (lst), we need to initialize the
    # elements of the list.  since the range of values in lst is
    # from 1 to max, we need to create elements for 1 <= i <= max
    # in counters.
    #
    #
    # indexlist = range(max+1)
    # for i in indexlist:
    #
    # the code above is longhand for what is below
    for i in range(max+1):
        counters.append(0)

    # at this point counters[i] for 1 <= i <= max is equal to 0
    # this is expected and OK since we haven't yet counted the 
    # occurances of each i in our list (lst)
    #
    # now, we need to do the counting...

    # for i in range(len(lst):
    #   item = lst[i]
    # this is longhand for what is below.
    for item in lst:
        c = counters[item]
        c = c + 1
        counters[item] = c

    # at this point each i for 1 <= i <= max that is 
    # in the list (lst) has been counted.  in other words,
    #
    # count[5] = the number of 5s that occur in lst.
    # count[10] = the number of 10s that occur in lst.
    # count[max] = the number of 'max' that occur in lst.
    #
    # since we know the occurance of each time, we only need to 
    # output our list and as a result it will be sorted...

    # out is our list we want to output (return) at the end
    # of the function
    out = []

    # numcounts is just the length of our counters, this is
    # the same as max+1 because if you look above where we
    # initialized counters (line 35), we appended max+1 0s.
    #
    # the idea here is that I need to iterate through my possible
    # values, 1 through max, and output the appropriate number of
    # occurances that I found in my original list (lst).  since
    # the indices of my 'counters' list are increasing (they go
    # from 1 to max), my output will be sorted.
    numcounts = len(counters)
    for i in range(numcounts):
        # at this point i is some index in counters
        # if i == 3 we are concerned with outputing 3s to our output list.
        # if i == 6 we are concerned with outputing 6s to our output list.

        # here i let 'numofi' represent how many occurances of i we found
        # in our original list (lst)
        numofi = counters[i]
        for j in range(numofi):
            # append 'i' to our output list.
            # j is simply a junk variable, in other words, say we need to 
            # output 4 'i's.  this loop will append 'i' the appropriate 
            # number of times.
            out.append(i)

    # this should be obvious.
    return out