'''
=======================================================================
Python for Parallelism in Introductory Computer Science Education
SC '12 Educator Program

Python Crash Course

Steven Bogaerts
Wittenberg University

Joshua Stough
Washington and Lee University

This document contains some simple Python examples to serve as a quick start
guide for those familiar with programming but unfamiliar with Python.

For complete documentation on Python, see www.python.org
=======================================================================
'''

#######################################################################
# Basic Types and Loops

def loops():
    ls1 = [2,4,6,8]
    ls2 = range(0, 10, 1) # range(start, upToButNotIncluding, step) returns a list
    print "==============================="
    print "ls1: " + str(ls1) # string concatenation, string conversion
    print "ls2: " + str(ls2)
    
    for item in ls1:
        print item, # comma means space, instead of \n
    print # now \n

    for itemID in ls2:
        print ls2[itemID],
    print

    print "==============================="
    for item in range(15, 4, -2):
        print item,
    print

    print "==============================="
    s = "Supercomputing"
    for c in s:
        print c,
    print

    for cID in range(len(s)): # or  range(0, len(s), 1):
        print s[cID],
    print

    cID = 0
    while cID < len(s):
        # Keywords   and, or, not   work as you'd expect
        print s[cID],
        cID += 1  # Indentation matters!
    print

    print "==============================="
    infilename = raw_input("Enter a file name: ")
    # raw_input for strings
    # input for other types (equivalent to eval(raw_input(...))

    printWithLineNumbers(infilename)
    
    print "==============================="

# Arguments in Python:
# While different in actual implementation, in terms of behavior you can
# think of them as you would in Java, where primitive types are copied
# and reference types are aliased.

def printWithLineNumbers(infilename):
    infile = open(infilename, "r")
    lineNumber = 1
    for line in infile:    # iterate over file
        print str(lineNumber) + ":", line[:-1]
        lineNumber = lineNumber + 1
    
    infile.close()

#######################################################################
# Writing to a File

def writePractice():
    outfilename = raw_input("Enter output file name: ")

    outfile = open(outfilename, "w")
    s = raw_input("Type something: ")
    outfile.write(s + "\n")
    outfile.write("Bam!")

    outfile.close()

#######################################################################
# Dictionaries

def dictionaryPractice():
    nameToAge = {}
    nameToAge["Jimmy"] = 15
    nameToAge["Samantha"] = 16
    print "Jimmy" in nameToAge
    print nameToAge.keys()
    print nameToAge.values()
    print nameToAge.items()
    print nameToAge["Jimmy"]
    print nameToAge.get("Alfred", -1)
    # del nameToAge["Jimmy"]
    # nameToAge.clear()

#######################################################################
# A Simple Class

class Student(object):

    def __init__(self, name, hours, qpoints):
        self.name = name
        self.hours = hours
        self.qpoints = qpoints

    def calcGPA(self):
        return self.qpoints / float(self.hours)

    def __repr__(self):
        return "(Student: %s, gpa: %f)" % (self.name, self.calcGPA())
    # Could also use __str__ for a slightly different effect, but we won't
    # worry about that here

def testStudent():
    s1 = Student("Jimmy", 65, 150)
    s2 = Student("Samantha", 50, 150)
    print s1, s2

#######################################################################
# First-Class Functions, Comparators, and a MyList Class

# This is actually equivalent to the built-in cmp function, but just to
# demonstrate:
def ascendingComparator(n1, n2):
    if n1 < n2:
        return -1
    elif n1 == n2:
        return 0
    else:
        return 1

def descendingComparator(n1, n2):
    # return -1 * cmp(n1, n2)
    return -1 * ascendingComparator(n1, n2)

class MyList(object):
    """This class is totally unnecessary, because we already have a built-in
    list type in Python.  But I wrote this to demonstrate the general idea of
    what is happening with the sort method for lists."""

    def __init__(self, ls):
        self.ls = ls

    def __repr__(self):
        return str(self.ls)
    
    def mySort(self, comparator):
        """This method performs a *selection sort* on the list."""
        for pos in range(len(self.ls)):
            swapPos = self.__getFirstPos(pos, comparator)
            self.ls[pos], self.ls[swapPos] = self.ls[swapPos], self.ls[pos]

    # The __ kind of makes this method private.
    def __getFirstPos(self, startPos, comparator):
        """Among the list items at position startPos or later, returns
        the position of the item that should be first, according to
        comparator."""

        best = self.ls[startPos]
        bestPos = startPos
        for i in range(startPos+1, len(self.ls)):
            if comparator(self.ls[i], best) == -1:
                # current item comes before "best"
                best = self.ls[i]
                bestPos = i

        return bestPos

def testMyList():
    mine = MyList([4,6,2,8,6,9,3])
    print "Before:", mine
    mine.mySort(cmp)
    print "After:", mine

    print "=========="

    mine = MyList([4,6,2,8,6,9,3])
    print "Before:", mine
    mine.mySort(descendingComparator)
    print "After:", mine

    print "==========================================="
    # I can do the same thing with the already existing list type:
    mine = [4,6,2,8,6,9,3]
    print "Before:", mine
    mine.sort() # alternatively, mine.sort(cmp)
    print "After:", mine

    print "=========="

    mine = [4,6,2,8,6,9,3]
    print "Before:", mine
    mine.sort(descendingComparator)
    print "After:", mine

###############################################################
# Searching and Timing

def linSearch(x, nums):
    for i in range(len(nums)):
        if nums[i] == x:       # item found, return the index value
            return i
    return -1                  # loop finished, item was not in list...

# Binary Search
# Only works for *sorted* lists (ascending order, in this example)
def binSearch(x, nums):
    low = 0
    high = len(nums)-1
    while low <= high:          # There is still a range to search
        mid = (low + high) / 2  # position of middle item
        item = nums[mid]
        if x == item :          # Found it! Return the index
            return mid
        elif x < item:          # x is in lower half of range
            high = mid - 1      #     move top marker down
        else:                   # x is in upper half
            low = mid + 1       #     move bottom marker up
    return -1                   # no range left to search, x is not there

# Less efficient than linSearch !
def searchUnsorted(x, nums):
    nums.sort() # mutates the list
    return binSearch(x, nums)

import time, random

def randomNumber():
    return random.randint(0, 999999)

import string
def randomString():
    length = random.randint(0, 20)
    return string.join([chr(random.randint(97, 122)) for i in range(length)], '')
    # The above line contains a "list comprehension":
    # [<expression(var)> for <var> in <sequence>]
    # Evaluates the expression for var being each value in the sequence, returns list of results.

    # Alternative:
    '''
    length = random.randint(0, 20)
    s = ""
    for i in range(length):
        s = s + chr(random.randint(97, 122))
    return s
    '''
    # For comparison of string concatenation techniques, see:
    # http://www.skymind.com/~ocrow/python_string/

def randomStudent():
    return Student2(randomString(), random.random()*4)

class Student2(object):
    def __init__(self, name, gpa):
        self.name = name
        self.gpa = gpa

    def __cmp__(self, other):
        compare = cmp(self.name, other.name)
        if compare == 0:
            return cmp(self.gpa, other.gpa)
        else:
            return compare

    def __repr__(self):
        return "<Student2 " + self.name + ", " + str(self.gpa) + ">"

def avgTime(search, generator, n, trials):
    startTime = time.time()
    
    ls = []
    # Make an unordered list
    for i in range(n):
        ls.append(generator())

    # Sort the list, if necessary
    if search == binSearch:
        print "Sorting...",
        ls.sort()
        print "done!"
        
    endTime = time.time()
    print "List built in", endTime-startTime, "seconds."

    # Run a number of trials and compute average time
    sum = 0.0
    for i in range(trials):
        print i+1,                    # show progress
            
        target = generator()
        
        # Get system time just before search
        startTime = time.time()
        pos = search(target, ls)
        
        # Get system time just after search
        endTime = time.time()
        
        # Add elapsed time to sum
        sum = sum + (endTime-startTime)
        
    print "\naverage:", sum/trials

# avgTime(binSearch, randomStudent, 200000, 10)
# avgTime(binSearch, randomString, 200000, 10)
# avgTime(binSearch, randomNumber, 200000, 10)

# avgTime(linSearch, randomStudent, 200000, 10)
# avgTime(linSearch, randomString, 200000, 10)
# avgTime(linSearch, randomNumber, 200000, 10)

# Can consider list construction times and algorithm times for each type.