'''
Here are a lot of simple things you can do by looping over a list
'''

'''
1. Print list
'''
def print_list(a_list):
    for x in a_list:
        print x

'''
2. Print list, 10 per line
'''
def print_list_wrapped(a_list):
    output_count = 0
    for x in a_list:
        print x,    # notice the comma!
        output_count += 1
        if output_count == 10:
            # start a new line, and reset the counter
            print
            output_count = 0
    
    if output_count < 10:
        print   # start a new line, in case we didn't end on a ten-number line

'''
3. return biggest value
or use the built-in function: max(a_list)
'''
def biggest(a_list):
    big = a_list[0]
    for x in a_list[1:] :
        if x > big:
            big = x

    return big
    
'''
4. return smallest value
or use the built-in function: min(a_list)
'''
def smallest(a_list):
    small = a_list[0]
    for x in a_list[1:] :
        if x < small:
            small = x

    return small
    
'''
5. return sum of values
or use the built-in function: sum(a_list)
'''
def add_up(a_list):
    total = 0
    for x in a_list:
        total += x

    return total

'''
6. return average of values
'''
def average(a_list):
    return add_up(a_list) / len(a_list)

'''
7. return how many times the value x appears in the list
or use the built-in function: a_list.count(x)
'''
def count_x(a_list, x):
    n_x = 0
    for a in a_list:
        if a == x:
            n_x += 1

    return n_x

'''
8. does the list have a run of two values?
'''
def has_run(a_list):
    prev_value = a_list[0]
    for a in a_list[1:] :
        if a == prev_value:
            return True      # stop looking, return now

        prev_value = a

    return False             # checked all values, no runs found

'''
9. does the list have a run of two values?
(This uses indexes, instead of remembering the previous value)
'''
def has_run2(a_list):
    for i in range(len(a_list) - 1):
        if a_list[i] == a_list[i+1]:
            return True      # stop looking, return now

    return False             # checked all values, no runs found


'''
10. where does x occur in the list (at what index)?
or use the built-in function: a_list.index(x)
'''
def index_of(a_list, x):
    for i in range(len(a_list)):   # walk down a list of indexes
        if a_list[i] == x:
            return i      # stop looking, return now

    raise ValueError      # checked all values, didn't find x

'''
11. does the list have duplicates?
Version 1: double loop
'''
def has_duplicates(a_list):
    for i in range(len(a_list)):   # walk down a list of indexes
        x = a_list[i]
        for j in range(i + 1, len(a_list)):
            y = a_list[j]
            if x == y:
                return True   # found a duplicate, return now

    return False              # checked them all, found no dupes


'''
12. does the list have duplicates?
Version 2: use the 'in' operator
'''
def has_duplicates2(a_list):
    for i in range(len(a_list)):   # walk down a list of indexes
        x = a_list[i]              # get i-th value
        if x in a_list[i+1:] :     # look in the remainder of the list
            return True            # found a duplicate, return now

    return False                   # checked them all, found no dupes

'''
13. does the list have duplicates?
Version 3: count the number of occurrences
'''
def has_duplicates3(a_list):
    for x in a_list:
        if a_list.count(x) > 1:
            return True            # found a duplicate, return now

    return False                   # checked them all, found no dupes

'''
14. return all indexes where values change (where a run ends)
'''
def run_end_indexes(a_list):
    end_indexes = []
    for i in range(1, len(a_list)):
        if a_list[i - 1] != a_list[i]:
            end_indexes.append(i-1)  # previous (i-1) index ended a run

    # also mention the very last run
    end_indexes.append(len(a_list) - 1)
    return end_indexes

'''
15. Is the list sorted?
NOTE: this is different from the built-in function sorted().
      sorted(a_list) return a new list, which has a_list's values sorted
'''
def is_sorted(a_list):
    for i in range(1, len(a_list)):
        if a_list[i - 1] >= a_list[i]:
            # found a pair of values out of order. stop.
            return False

    return True  # never found an out-of-order pair

'''
16. bubble sort the list
NOTE: this REARRANGES a_list!
'''
def bubble_sort(a_list):
    # Each pass will go up to 'last',
    # and each time we will decrease 'last'.
    # this can be done using 'range'

    for last in range(len(a_list) - 1, 0, -1):
        for i in range(0, last):
            if a_list[i] >= a_list[i + 1]:
                # found a pair of values out of order.
                # swap them using a pair assignment
                a_list[i + 1], a_list[i] = a_list[i], a_list[i + 1]


'''
17. bubble sort again, but now exit if no swaps occur
NOTE: this REARRANGES a_list!
'''
def bubble_sort2(a_list):
    for last in range(len(a_list) - 1, 0, -1):
        n_swaps = 0
        for i in range(0, last):
            if a_list[i] >= a_list[i + 1]:
                # found a pair of values out of order.
                # swap them using a pair assignment
                a_list[i + 1], a_list[i] = a_list[i], a_list[i + 1]
                n_swaps += 1

        if n_swaps == 0:
            return   # no swaps done in this pass, quit now


'''
18. return a run-length encoded version of the list
'''
def rle(a_list):
    runs = []

    # the first value starts a run, initially with length 1
    prev_value = a_list[0]
    run_length = 1
    for x in a_list[1:] :
        if x == prev_value:
            # current run continues
            run_length += 1
        else:
            # run ended, new one began
            # record the ending run
            runs.append(run_length)
            runs.append(prev_value)
            # and start counting the new run
            run_length = 1
        prev_value = x

    # at the end, we'll always have a (length value) pair left over
    runs.append(run_length)
    runs.append(prev_value)

    return runs

def main():
    # run tests on the above functions
    print 'Printing tests'
    print_list( [1,2,3] )
    print_list_wrapped( range(30, 3, -1) )
    
    pi = [3,1,4,1,5,9,2,6,5,3]
    print 'biggest(pi)=', biggest(pi)
    print 'smallest(pi)=', smallest(pi)
    one_to_10 = range(1,11)
    print 'should be',sum(one_to_10), ':', add_up(one_to_10)
    print 'should be',sum(one_to_10)/10, ':', average(one_to_10)
    print '1 occurs', count_x(pi, 1),'times in pi'
    print '0 occurs', count_x(pi, 0),'times in pi'
    print 'runs in pi?', has_run(pi)
    runny = [1,2,2,0,0,0,4,1,2]
    print 'runs in runny?', has_run(runny)
    print 'runs in runny?', has_run2(runny)
    print 'should be', pi.index(9), ':', index_of(pi, 9)
    print 'must be True:', has_duplicates(pi) and not has_duplicates(one_to_10)
    print 'must be True:', has_duplicates2(pi) and not has_duplicates2(one_to_10)
    print 'must be True:', has_duplicates3(pi) and not has_duplicates3(one_to_10)
    print 'run_ends:', run_end_indexes(runny)
    print 'must be True:', is_sorted(one_to_10) and not is_sorted(range(10,0,-1))
    bubble_sort(pi)
    print 'pi sorted:', pi
    pi = [3,1,4,1,5,9,2,6,5,3]
    bubble_sort2(pi)
    print 'pi sorted:', pi
    print 'run-length encoded:',rle(runny)

if __name__ == '__main__':
    main()