#!/usr/bin/env python

import re
import random

stu_file = 'list_students'
uni_file = 'list_unis'
una_file = 'unis_translate'
sep      = ("\n", ' ')



''' Get content of a textfile '''
def get_content(filename):
    fp = open(filename, 'r')
    lines = fp.read()
    fp.close()

    ws = ("\n", "\t", ' ')
    for i in ws:
        lines = re.sub('^'+i, '', lines)
        lines = re.sub(i+'$', '', lines)

    return lines



''' Returns True if text is only made of whitespaces
eg. '   \n' return True '''
def is_empty(text):
    text = re.sub("\n", '', text)
    text = re.sub("\t", '', text)
    text = re.sub(" ", '', text)
    return (text == '')


''' Can read tables
eg. '1 table
2 tables' returns [[1, 'table'], [2, 'tables']] '''
def read_table(table):
    rows = table.split(sep[0])
    count_rows = len(rows)
    count_cols = len(rows[0].split(sep[1]))
    columns = [[ ] * count_cols for _ in xrange(count_rows)]
    table = ''
    index = 0

    for (rownr, row) in enumerate(rows):
        values = row.split(' ')
        for (columnnr, column) in enumerate(values):
            if not is_empty(column):
                columns[rownr].append(column)
    return columns


''' Can read a table and may return a specific column
eg. 'a 1
b 2' return [['a', '1']]'''
def read_columns(data, col=None):
    lines = data.split("\n")
    col1 = []
    col2 = []
    columns = [[], []]

    for line in lines:
        cols = line.split(' ')
        col1.append(str(cols[0]))
        col2.append(str(cols[1:]))
        columns[0].append(cols[0])
        columns[1].append(' '.join(cols[1:]))

    if col == 1:
        return col1
    elif col == 2:
        return col2
    else:
        return columns

''' Asks user if he wants to give a parameter '''
def another_question(qu = 'x'):
    while type(qu) != int:
        qu = raw_input('Which one? ')
        try:
            qu = int(qu)
        except ValueError:
            print 'This value is not allowed'
    return qu


''' Returns uni_id of uni the student prefers (according to the table) '''
def student_prefers(student, a, b, students):
    student = str(student)
    for i in students:
        if i[0] == str(student):
            for j in i:
                if j == a:
                    return a
                if j == b:
                    return b


''' Return student_id of student the uni prefers (according to the table) '''
def university_prefers(uni, student1, student2, unis):
    uni = str(uni)
    student1 = str(student1)
    student2 = str(student2)
    return student_prefers(uni, student1, student2, unis)



''' Checks allocation, if there are two identical allocations
eg. {1:'a', 2:'b'} return True '''
def unallocated_student_exists(alloc, students):
    #if len(alloc) != len(students):
    #    raise ValueError, 'allocation and students must have equal number of elements'
    if len(alloc) < len(students):
        return True

    # set False for each student
    check = { }
    for student in alloc.keys():
        check[student] = False

    # if student exists in alloc, set True
    for student in students:
        if alloc.get(student) != None:
            check[student] = True
   
    # if some value is still False: return False
    for student_exists_in_alloc in check:
        if not check[student_exists_in_alloc]:
            return True
    return False

''' Returns student_id of student which attends university XY (according to the table) '''
def somebody_attends_university(uni, alloc):
    for key in alloc:
        if alloc[key] == uni:
            return key
    return False


''' Will allocate students and universities randomly
eg. ([1,2,3], ['a','b','c']) returns {1:'c', 2:'a', 3:'a'} '''

def get_rand_allocation(students, unis):
    unis = list(unis)
    alloc = { }
    if type(students) != list or type(unis) != list:
        print 'Arguments of get_rand_allocation must be lists'
        return 0
    if len(students) != len(unis):
        print 'Number of students and universities must be equal'
        return 0
    
    for student in students:
        while not student in alloc:
            rand = random.choice(unis)
            if alloc.get(student) == None:
                alloc[student] = rand
                del unis[unis.index(rand)]
    return alloc




''' Search for two identical allocations
eg. {1:'a', 2:'b', 3:'a'} return True '''

def double_allocation_exists(alloc):
    if len(students) != len(unis):
        print 'Number of students and universities must be equal'
        return 0

    value = { }
    for i in alloc:
        if value.get(alloc[i]) != None:
            return True
        else:
            value[alloc[i]] = True
    return False

''' Translates short names to university
eg. B return 'TU Berlin' '''
def translate_uni(letter, unis):
    return unis[1][unis[0].index(letter)]

''' Will return a list of students
eg. 1\n2\n3\n4 returns [1,2,3,4] '''
def make_list_of_students(students, integer=True):
    stud = []
    for a in students:
        i = 0
        while is_empty(a[i]):
            i += 1
        if integer:
            stud.append(int(a[i]))
        else:
            stud.append(a[i])
    return stud

''' Will return a list of universities '''
def make_list_of_universities(unis):
    return make_list_of_students(unis, False)




# get tables
unis     = get_content(uni_file)
students = get_content(stu_file)
uni_name = get_content(una_file)
unis     = read_table(unis)
students = read_table(students)
uni_name = read_columns(uni_name)

list_of_stud = make_list_of_students(students)
list_of_unis = make_list_of_universities(unis)
rand_alloc = get_rand_allocation(list_of_stud, list_of_unis)
allocation = { } #rand_alloc


#print unallocated_student_exists(rand_alloc, list_of_stud)
#print double_allocation_exists(rand_alloc)

# test
#print '== A FEW TEST =='
#print 'Student #5 prefers (TUG or K): ', student_prefers(5, 'TUG', 'K', students)
#print 'University K prefers (student 3 or 5): ', university_prefers('K', 3, 5, unis)
#print 'In the current allocation no unallocated student exists: ', unallocated_student_exists(allocation, list_of_stud)
#print 'In the current allocation a university is allocated twice: ', double_allocation_exists(allocation)
#print 'Somebody attends university TUG: student', somebody_attends_university('TUG', allocation)
#print 'The university TUG is better known as ', translate_uni('TUG', uni_name)
#print 'This is a random allocation:'
#print get_rand_allocation(list_of_stud, list_of_unis)


# allocation test
#allocation = {1:'a', 2:'b', 3:'c', 4:'d'}
#list_of_stud = [1,2,3,4]
#list_of_unis = ['a', 'b', 'c', 'd']
#students = [['1', 'a', 'b', 'c', 'd'], ['2', 'a', 'c', 'b', 'd'], ['3', 'a', 'd', 'b', 'c'], ['4', 'd', 'c', 'b', 'a']]
#unis = [['a', '1', '2', '3', '4'], ['b', '2', '1', '3', '4'], ['c', '3', '4', '1', '2'], ['d', '3', '2', '1', '4']]

#print double_allocation_exists(allocation)
#print unallocated_student_exists(allocation, list_of_stud)
#print somebody_attends_university('g', allocation)
#print university_prefers('c', 2, 1, unis)







# algorithm
# Alle Studenten unzugeordnet
# while (Es gibt) unzugeordneten Studenten
while unallocated_student_exists(allocation, list_of_stud) or double_allocation_exists(allocation):
    # s ist Element der Menge S
    for student in students:
        s = int(student[0])
        u = student[1:]
        # u ... erste Uni auf der Liste, bei der er sich noch nicht beworben hat
        for pref_uni in u:
            occupied_by = somebody_attends_university(pref_uni, allocation)
            # if u hat noch keinen Studenten then
            if not occupied_by:
                # s vorl"aufig inskribiert
                allocation[s] = pref_uni
                break
            # else
            else:
                # s' vorl"aufig inskribiert
                # if u bevorzugt s anstelle von s'
                if university_prefers(pref_uni, s, occupied_by, unis) == s:
                    # vorl"aufig inskribiert
                    allocation[s] = pref_uni
                    # s' frei
                    allocation[occupied_by] = False
                # s bleibt frei
                else:
                    allocation[s] = False
print allocation