ps8_greedy

def greedyAdvisor(subjects, maxWork, comparator):
    """
    Returns a dictionary mapping subject name to (value, work) which includes
    subjects selected by the algorithm, such that the total ***work*** of subjects in
    the dictionary is not greater than maxWork.  The subjects are chosen using
    a greedy algorithm.  The subjects dictionary should not be mutated.

    subjects: dictionary mapping subject name to (value, work)
    maxWork: int >= 0
    comparator: function taking two tuples and returning a bool
    returns: dictionary mapping subject name to (value, work)
    """

    greedy_dict = {}
    greedy_list = []
    temp = ()
    work_total = 0
    sub_list = subjects.items() #[(subject,(value,work),(subject,(value,work))...]


    while work_total < maxWork:
        # bubble search
        for i in range(len(sub_list)-1):
            if comparator(sub_list[i][1], sub_list[i+1][1])==True:
                temp = sub_list[i]
                sub_list[i] = sub_list[i+1]
                sub_list[i + 1] = temp
        if sub_list[0]==sub_list[-1]: #if options run out
            print 'note: maximum work load exceeds possible work'
            greedy_list.append(sub_list[-1])
            break
        elif work_total + sub_list[-1][1][WORK] <= maxWork:
            work_total += sub_list[-1][1][WORK]
            greedy_list.append(sub_list.pop()) # take the course
        else:
            sub_list.pop() # do not take course
    # create dictionary from list
    for j in range(len(greedy_list)):
        greedy_dict[greedy_list[j][0]] = greedy_list[j][1]

    return greedy_dict

    #printSubjects(greedy_dict)