# -*- coding: utf-8 -*-
"""faster_simulations_sigs_revised.ipynb

Automatically generated by Colaboratory.

Original file is located at
    https://colab.research.google.com/drive/1_-oQDQXJCYRE3JnPBMlYaLIdoBOpX25f
"""

import numpy as np
import pandas as pd

class Worker(object):
    name = ""
    p = [] #original preferences, list of strings of names of hospitals ranked, unchanged
    p_dict = {} # same as p but as a mapping of hospital name to ranking in p
    ranking = [] #list of strings of names of hospitals ranked
    matchings = [] #list of hospitals that worker is matched to, t-algorithm
    wishes = [] #list of names of hospitals used in Gale-Shapley algorithm as rankings submitted
    wishes_dict = {} # same as above but a dictionary mapping name to ranking in p'
    current = None #hospital that worker is currently matched to in Gale-Shapley algorithm
    interviews = [] #simulated interviews, list of hospitals
    choices = [] #list of hospitals that worker wants to interview with, ranked
    pref = [] # this is the total utilities that hospitals provide this worker

    def __init__(self, cu, name, we,n):
        '''
        cu is common utility
        name is in format WN where N is a number
        we is the weight for common utility
        n is the number of hospitals
        '''
        self.name=name
        self.generateP(cu, we, n)
        self.start()

    def start(self):
        ''' sets starting conditions '''
        self.match([])
        self.matchings = []
        self.wishes = []
        self.setWishes()
        self.interviews = []
        self.current = None

    def generateP(self,cu,we,n):
        ''' generates the preferences p using cu and iu'''
        self.pref = [np.random.normal(0,1) * (1 - we) + cu[x] * we for x in range(n)] #creates array with weighted utility for firms with common utility weighed 60% and idiosyncratic utility weighed 40%
        self.ranking=["H" + str(x + 1) for x in range(n)]

        # ranks hospitals based on their weighted utility, highest utility ranked first
        self.pref, self.ranking = self.fastersort(self.pref, self.ranking)

        self.p = []
        self.p_dict = {}
        index = 1
        for x in self.ranking:
            self.p.append(x)
            self.p_dict[x] = index
            index += 1

    def setChoices(self, hospitals):
        ''' sets choices with ranked list of hospitals '''
        self.choices = []
        for h in self.p:
            self.choices.append(self.getEq(h, hospitals))

    def generateP2(self,cu,n):
        ''' generates the preferences using cu only'''
        self.ranking= ["H" + str(x + 1) for x in range(n)]
        pref = []
        for c in cu:
            pref.append(c)

        pref, self.ranking = self.fastersort(pref, self.ranking)

        self.p_dict = {}
        index = 1
        for x in self.ranking:
            self.p_dict[x] = index
            index += 1

    def fastersort(self, pref, ranking):
        return zip(*sorted(zip(pref, ranking), reverse=True))

    def bubblesort(self, pref, ranking):
        ''' sorts/ranks the hospitals based on the preferences'''
        for i in range(len(pref)):
            for k in range(len(pref) - 1, i, -1):
                if(pref[k] > pref[k - 1]):
                    self.swap(pref, ranking, k, k - 1)

    def swap(self, pref, ranking, x, y):
        '''  helper function for the bubble sort that swaps two hospitals in ranking '''
        temp1 = pref[x]
        temp2 = ranking[x]
        pref[x] = pref[y]
        ranking[x] = ranking[y]
        pref[y] = temp1
        ranking[y] = temp2

    def checkAvailability(self, goal, agent):
        '''
        agent is a hospital
        goal is number of desired matchings in T-algorithm (max number of interviews for hospitals)
        returns True if hospital is available, False otherwise
        '''
        if(not agent.getMatchings() or len(agent.getMatchings())<goal):
            return True

        if(len(agent.getMatchings())>goal):
            x = (agent.getMatchings()[:goal])[-1]
        else:
            x = agent.getMatchings()[-1]

        ranking = agent.getP_dict()

        return ranking[self.getName()] <= ranking[x.getName()]

    def getOldRank(self, agent, other=None):
        index = 1
        for a in agent.getRanking():
            if other is not None and a == other.getName():
                return index
            elif other is None and a == self.getName():
                return index
            index += 1

    def proposed(self):
        ''' simulates a worker proposing'''
        if(len(self.wishes) > 0):
            self.wishes = self.wishes[1:]

    def getEq(self, n, hospitals):
        ''' returns hospital with certain name (Hn)'''
        for h in hospitals:
            if(h.getName() == n):
                return h
        return None

    def getOrig(self):
        ''' return the original (untruncated) preference p '''
        return self.p

    def getHospitalUtilities(self):
        '''Returns the utilities that hospitals provide this worker, sorted in the
        Same order as p (so in decreasing total utility)'''
        return self.pref

    def getTotalUtilityByHospital(self, hospital_name):
        for i in range(len(self.p)):
            if (self.p[i] == hospital_name):
                return self.pref[i]

    def setOrig(self, op):
        ''' set the original preference p'''
        self.ranking = []
        self.p = []
        self.p_dict = {}
        index = 1
        for o in op:
            self.ranking.append(o)
            self.p.append(o)
            self.p_dict[o] = index
            index +=1

    def getPref(self, hospitals):
        ''' returns the top unproposed hospital for this worker '''
        h = self.getEq(self.wishes[0], hospitals)
        self.proposed()
        return h

    def getP_dict(self):
        return self.p_dict

    def match(self, avail):
        '''
        avail is list of hospitals that are available for this worker
        function matches worker to these hospitals
        '''
        self.matchings = []
        for m in avail:
            self.matchings.append(m)

    def judge(self, h):
        '''
        Used in Gale-Shapley algorithm when hospitals propose
        Returns rejected hospital if any  (so if None returned, then matched for now)
        '''
        if(len(self.wishes) == 1 and self.wishes[0] != h.getName()):
            return h
        x = None
        for i in range(len(self.wishes)):
            if(self.wishes[i] == h.getName()):
                self.wishes = self.wishes[:i + 1]
                if(self.current is not None):
                    self.current.setMatch(None)
                    x = self.current
                self.current = h
                h.setMatch(self)
                return x

        return h

    def interview(self, h):
        self.interviews.append(h)

    def getTopChoice(self):
        ''' Returns top choice hospital unproposed to
            And removes it from unproposed choices list '''
        h = self.choices[0]
        self.choices = self.choices[1:]
        return h

    def setMatch(self, h):
        ''' this is used in Gale-Shapley to set deferred acceptance match for this worker, h is hospital '''
        self.current = h

    def setWishes(self):
        ''' sets rankings (wishes) for Gale-shapley algorithm based on matchings produced by T-algorithm'''
        self.wishes = []
        self.wishes_dict = {}
        index = 1
        for r in self.matchings:
            self.wishes.append(r.getName())
            self.wishes_dict[r.getName()] = index
            index += 1

    def setWishes2(self):
        ''' sets rankings(wishes) for Gale-Shapley algorithm based on original preferences '''
        self.wishes = []
        self.wishes_dict = {}
        index = 1
        for r in self.ranking:
            self.wishes.append(r)
            self.wishes_dict[r] = index
            index += 1

    def setWishes3(self, max_interviews=5):
        ''' sets rankings(wishes) for Gale-Shapley algorithm based on truncated original preferences (top 5)'''
        self.wishes = []
        self.wishes_dict = {}
        index = 1
        for r in self.ranking:
            self.wishes.append(r)
            self.wishes_dict[r] = index
            index += 1
        # Note: change the 5 below to change the length of truncated preferences
        self.wishes=self.wishes[:max_interviews]

    def setWishes4(self):
        ''' sets rankings (wishes) for gale shapley algorithm based on matchings from simulated interviews'''
        self.wishes = []
        self.matchings = []
        self.wishes_dict = {}
        index = 1
        for r in self.interviews:
            self.wishes.append(r.getName())
            self.matchings.append(r)
            self.wishes_dict[r.getName()] = index
            index += 1

    def checkBlocking(self, h2):
        ''' returns number of blocking pairs contain this worker '''
        count = 0
        for h in self.p:
            if(self.current is not None and h == self.current.getName()):
                return count
            if(self.getEq(h, h2).block(self)):
                count += 1
        return count

    def checkBlocking2(self,h2):
        ''' returns number of blocking pairs that contain this worker, but only blocking pairs where both agents are matched'''
        count = 0
        if(self.current is None):
            return 0
        for h in self.p:
            if(h == self.current.getName()):
                return count
            if(self.getEq(h, h2).block2(self)):
                count += 1
        return count

    def block(self, h):
        ''' returns True if this worker with h is a blocking pair '''
        if(self.current is None): #since every hospital is ranked in p, then if worker is unmatched it prefers h to being unmatched
            return True

        for h2 in self.p:
            if(h2 == self.current.getName()):
                return False
            if(h2 == h.getName()):
                return True
        return False

    def getInterviews(self):
        return self.interviews

    def getChoices(self):
        return self.choices

    def getName(self):
        ''' returns string with name in form Wn where n is number '''
        return self.name

    def getMatchings(self):
        ''' returns list of hospitals '''
        return self.matchings

    def getRanking(self):
        ''' returns list of strings of names of hospitals ranked '''
        return self.ranking

    def getWishes(self):
        ''' returns list of strings of names of hospitals that will be ranked '''
        return self.wishes

    def getCurrent(self):
        ''' returns current match (hospital) during Gale Shapley algorithm '''
        return self.current

# note that the hospital class is identical since roles during T-algorithm and Gale-Shapley can be switched depending on who's proposing



class Hospital(object):
    name = ""
    p = [] #original preferences, list of strings of names of workers ranked, unchanged
    p_dict = {} # same as above but as a dictionary
    ranking = [] #list of strings of names of workers ranked
    matchings = [] #list of workers that hospital is matched to, t-algorithm
    wishes = [] #list of names of workers used in Gale-Shapley algorithm as rankings submitted
    wishes_dict = {} # same as above but as dictionary
    current = None #worker that hospital is currently matched to in Gale-Shapley algorithm assuming One-to-One matching
    interviews = [] #simulated interviews, list of doctors
    iu = [] #idiosyncratic utility that workers provide for this hospital
    iu_sorted = [] # idiosyncratic utility that workers provide for this hospital, in same order as p
    utilities_sorted = [] # combination of idiosyncratic and common utility, in same order as p
    cu_sorted = [] # common utility, in same order as p
    cu_unsorted = [] # cuw in original order, used to sort other lists in same order

    def __init__(self, cu, name,we,n):
        '''
        Cu is common utility
        Name is in format HN where N is number
        we is weight for common utility
        n is number of doctors
        '''
        self.name = name
        self.iu = []
        self.iu_sorted = []
        self.utilities_sorted = []
        self.cu_sorted = []
        self.cu_unsorted = []
        self.generateP(cu, we, n)
        self.start()
        self.interviews = []

    def start(self):
        ''' sets starting conditions '''
        self.match([])
        self.matchings = []
        self.wishes = []
        self.setWishes()
        self.current = None

    def generateP(self,cu,we,n):
        ''' this generates p using cu and iu (common and idiosyncratic utility weights)'''
        # First, let's store this order of common utility
        self.cu_unsorted = [c for c in cu]

        self.iu = [np.random.normal(0, 1) for x in range(n)]
        self.iu_sorted = [x for x in self.iu]
        self.utilities_sorted = []
        self.cu_sorted = [x for x in cu]
        pref = [self.iu[x] * (1 - we) + cu[x] * we for x in range(n)] #creates array with weighted utility for workers with common utility weighed 70% and idiosyncratic utility weighed 30%
        for x in pref:
            self.utilities_sorted.append(x)
        self.ranking = ["W" + str(x + 1) for x in range(n)]
        # ranks hospitals based on their weighted utility, highest utility ranked first
        pref, self.ranking = self.fastersort(pref, self.ranking)

        self.p = []
        self.p_dict = {}
        index = 1
        for x in self.ranking:
            self.p.append(x)
            self.p_dict[x] = index
            index += 1
        # now we also sort iu, cu, and total utility that doctors provide in order of decreasing cu (so doctor with highest cu is first)
        # the commented out lines below can be used to check that outcome is consistent with previous sorting method
        #cu_sorted_copy = [item for item in self.cu_sorted]
        #iu_sorted_copy = [item for item in self.iu_sorted]
        #utilities_sorted_copy = [item for item in self.utilities_sorted]
        #self.bubblesort2(cu_sorted_copy, iu_sorted_copy, utilities_sorted_copy)

        self.cu_sorted, self.iu_sorted, self.utilities_sorted = self.fastersort2(self.cu_sorted, self.iu_sorted, self.utilities_sorted)

        #for a, b in zip(cu_sorted_copy, self.cu_sorted):
        #    assert a == b, f"Old {a}, New: {b}"

        #for a, b in zip(iu_sorted_copy, self.iu_sorted):
        #    assert a == b, f"Old {a}, New: {b}"

        #for a, b in zip(utilities_sorted_copy, self.utilities_sorted):
        #    assert a == b, f"Old {a}, New: {b}"

    def generateP2(self,cu,n):
        ''' this generates p using cu only '''
        self.ranking = ["W" + str(x + 1) for x in range(n)]
        pref = []
        for c in cu:
            pref.append(c)

        self.cu_unsorted = [c for c in cu]

        pref, self.ranking = self.fastersort(pref, self.ranking)

        self.p = []
        self.p_dict = {}
        index = 1
        for x in self.ranking:
            self.p.append(x)
            self.p_dict[x] = index
            index += 1

    def fastersort(self, pref, ranking):
        return zip(*sorted(zip(pref, ranking), reverse=True))

    def bubblesort(self, pref, ranking):
        ''' used to get the rankings from the preferences '''
        for i in range(len(pref)):
            for k in range(len(pref) - 1, i, -1):
                if(pref[k] > pref[k - 1]):
                    self.swap(pref, ranking, k, k - 1)

    def bubblesort2(self, cu, iu, u):
        ''' used to get the rankings from the preferences '''
        for i in range(len(cu)):
            for k in range(len(cu) - 1, i, -1):
                if(cu[k] > cu[k - 1]):
                    self.swap2(cu, iu, u, k, k - 1)

    def fastersort2(self, pref, ranking1, ranking2):
        return zip(*sorted(zip(pref, ranking1, ranking2), reverse=True))

    def swap(self, pref, ranking, x, y):
        ''' helper function for bubble sort'''
        temp1 = pref[x]
        temp2 = ranking[x]
        pref[x] = pref[y]
        ranking[x] = ranking[y]
        pref[y] = temp1
        ranking[y] = temp2

    def swap2(self, cu, iu, u, x, y):
        ''' helper function for bubble sort'''
        temp1 = cu[x]
        temp2 = iu[x]
        temp3 = u[x]

        cu[x] = cu[y]
        iu[x] = iu[y]
        u[x] = u[y]

        cu[y] = temp1
        iu[y] = temp2
        u[y] = temp3

    def checkAvailability(self, goal, agent):
        '''
        agent is a worker
        goal is number of desired matchings in T-algorithm (max number of interviews for hospitals)
        returns True if hospital is available, False otherwise
        '''
        if(not agent.getMatchings() or len(agent.getMatchings()) < goal):
            return True
        if(len(agent.getMatchings()) > goal):
            x = (agent.getMatchings()[:goal])[-1]
        else:
            x = agent.getMatchings()[-1]

        ranking = agent.getP_dict()
        return ranking[self.getName()] <= ranking[x.getName()]

    def getOldRank(self, agent, other=None):
        index = 1
        for a in agent.getRanking():
            if other is not None and a == other.getName():
                return index
            elif other is None and a == self.getName():
                return index
            index += 1

    def proposed(self):
        ''' simulates a hospital proposing '''
        if(len(self.wishes) > 0):
            self.wishes = self.wishes[1:]

    def interview(self, w):
        self.interviews.append(w)

    def getEq(self, n, workers):
        ''' returns worker with certain name '''
        for w in workers:
            if(w.getName() == n):
                return w
        return None

    def getPref(self,workers):
        ''' returns the top unproposed worker for this hospital '''
        w = self.getEq(self.wishes[0], workers)
        self.proposed()
        return w

    def getP_dict(self):
        return self.p_dict

    def match(self, avail):
        ''' avail is list of workers that are available for this hospital
            this function matches hospital to those workers'''
        self.matchings = []
        for m in avail:
            self.matchings.append(m)

    def judge(self,w):
        ''' used in Gale-Shapley algorithm when workers propose
            returns rejected worker if any '''
        if(len(self.wishes) == 1 and self.wishes[0]!= w.getName()):
            return w
        x = None

        for i in range(len(self.wishes)):
            if(self.wishes[i] == w.getName()):
                self.wishes = self.wishes[:i + 1]
                if(self.current is not None):
                    self.current.setMatch(None)
                    x = self.current
                self.current = w
                w.setMatch(self)
                return x
        return w

    def setMatch(self, w):
        ''' this is used in Gale-Shapley to set deferred acceptance match for this hospital
            w is worker'''
        self.current = w

    def setWishes(self):
        ''' sets rankings (wishes) for Gale-shapley algorithm based on matchings produced by T-algorithm'''
        self.wishes = []
        self.wishes_dict = {}
        index = 1
        for r in self.matchings:
            self.wishes.append(r.getName())
            self.wishes_dict[r.getName()] = index
            index += 1

    def setWishes2(self):
        ''' sets rankings(wishes) for Gale-Shapley algorithm based on original preferences'''
        self.wishes = []
        self.wishes_dict = {}
        index = 1
        for r in self.ranking:
            self.wishes.append(r)
            self.wishes_dict[r] = index
            index += 1

    def setWishes3(self, max_interviews=5):
        ''' sets rankings(wishes) for Gale-Shapley algorithm based on truncated original preferences'''
        self.wishes = []
        self.wishes_dict = {}
        index = 1
        for r in self.ranking:
            self.wishes.append(r)
            self.wishes_dict[r] = index
            index += 1
        # Note: to change length of truncated preference, change 5 below
        self.wishes = self.wishes[:max_interviews]

    def setWishes4(self, cuh,we):
        '''
        cuh is common utility workers provide
        this adds idiosyncratic shock to matches from simulated interviews,
        we is weight for common utility
        '''
        utilities = []
        pref = []
        for w in self.interviews:
            utilities.append(cuh[int(w.getName()[1:]) - 1] * we + self.iu[int(w.getName()[1:]) - 1] * (1 - we))
            pref.append(w)
        self.bubblesort(utilities, pref)
        self.wishes = []
        self.wishes_dict = {}
        index = 1
        for p in pref:
            self.wishes.append(p.getName())
            self.wishes_dict[p.getName()] = index
            index  += 1


    def block(self, w):
        ''' returns True if this hospital with w is a blocking pair '''
        if(self.current is None): #since every worker is ranked in p, then if hospital is unmatched it prefers w to being unmatched
            return True

        for h in self.p:
            if(h == self.current.getName()):
                return False
            if(h == w.getName()):
                return True

    def block2(self,w):
        ''' returns True if this hospital with w is a blocking pair, but only if this hospital is matched'''
        if(self.current is None):
            return False

        for h in self.p:
            if (h == self.current.getName()):
                return False
            if (h == w.getName()):
                return True

    def getIU(self):
        ''' returns list of idiosyncratic utility values'''
        return self.iu


    def getIU_sorted(self):
        '''returns list of idiosyncratic utility values that doctors, ranked in order of p,  provide'''
        return self.iu_sorted

    def getCU_sorted(self):
        '''returns list of common utility values that doctors, ranked in order of p,  provide'''
        return self.cu_sorted

    def getUtilities_sorted(self):
        '''returns list of utility values that doctors, ranked in order of p,  provide'''
        return self.utilities_sorted

    def setIU(self, i):
        ''' sets idiosyncratic utility values '''
        self.iu = []
        for val in i:
            self.iu.append(val)

    def getInterviews(self):
        return self.interviews

    def getName(self):
        ''' returns name (string) in format Hn where n is number'''
        return self.name

    def getMatchings(self):
        ''' returns list of workers that hospital is matched to '''
        return self.matchings

    def getRanking(self):
        ''' returns list of strings of names of workers ranked '''
        return self.ranking

    def setRanking(self, another_ranking):
        self.ranking = []
        self.p = []
        self.p_dict = {}
        index = 1
        for r in another_ranking:
            self.ranking.append(r)
            self.p.append(r)
            self.p_dict[r] = index
            index += 1

    def getWishes(self):
        ''' returns list of strings of names of workers that will be ranked '''
        return self.wishes

    def getCurrent(self):
        ''' returns current match (worker) during Gale Shapley algorithm '''
        return self.current

def a(goal, w, hospitals):
    ''' this is the part of the T-algorithm where each worker "proposes"
        returns top n (or less) hospitals
        where n is desired number of matchings'''
    available = []

    for h in hospitals:
        if(w.checkAvailability(goal, h)):
            available.append(h)

    # available contains all hospitals available to this worker

    if len(available) > 0:
        temp, available = fastersort(getEquiv(available, w), available)

    if(len(available) <= goal):
        return available
    else:
        top = available[:goal]
        return top

def b(goal, h, workers):
    ''' same as above but this time hospital "proposes" '''
    available = []

    for w in workers:
        if(h.checkAvailability(goal, w)):
            available.append(w)

    if len(available) > 0:
        temp, available = fastersort(getEquiv(available, h), available)

    if(len(available) <= goal):
        return available
    else:
        top = available[:goal]
        return top

def fastersort(pref, ranking):
    # note this sorts in ascending order
    # previous sorts sort in descending order since the first argument, "pref"
    # represents utilities
    # here, "pref" represents a ranking, so we want "1" to be first
    return zip(*sorted(zip(pref, ranking)))

def bubblesort(pref, ranking):
    # note this sorts in ascending order
    for i in range(len(pref)):
        for k in range(len(pref) - 1, i, -1):
            if(pref[k] < pref[k - 1]):
                swap(pref,ranking, k, k - 1)

def swap(pref, ranking, x, y):
    temp1 = pref[x]
    temp2 = ranking[x]
    pref[x] = pref[y]
    ranking[x] = ranking[y]
    pref[y] = temp1
    ranking[y] = temp2

def getEquiv(avail, judge):
    equiv = []
    for a in avail:
        equiv.append(getRank(a, judge))
    return equiv

def getRank(desired, judge):
    ranking = judge.getP_dict()
    return ranking[desired.getName()]

def iteration(goal, workers, hospitals):
    ''' this is one iteration of t-algorithm
        this is done until no changes are made'''
    todo = []
    total = []
    for w in workers:
        todo.append(a(goal, w, hospitals))

    for h in hospitals:
        todo.append(b(goal, h, workers))

    for w in workers:
        w.match(todo.pop(0))
        total.append(w.getMatchings())

    for h in hospitals:
        h.match(todo.pop(0))
        total.append(h.getMatchings())
    return total

def equate(past, current):
    ''' checks if matchings remain same in t-algorithm in two consecutive iterations of "proposals" '''
    if(len(past) != len(current)):
        return False

    for i in range(len(past)):
        if(len(past[i]) != len(current[i])):
            return False
        for j in range(len(past[i])):
            if(past[i][j] != current[i][j]):
                return False
    return True

def getPreM(agent):
    ''' gets prematchings for t-algorithm '''
    updated = []
    for w in agent.getRanking():
        for j in agent.getMatchings():
            if(w == j.getName()):
                updated.append(j)
                continue
    return updated

def proposals(workers,hospitals):
    ''' gale shapley algorithm where workers propose
        If order of parameters is switched then hospitals propose '''

    while(len(workers)>0):
        y = None
        for i in range(len(workers)):
            w = workers[0]
            y = None

            if(len(w.getWishes()) > 0 and w.getCurrent() is None):
                y = w.getPref(hospitals).judge(w)
            workers = workers[1:]

            if(y is not None):
                workers.append(y)

def getWorker(name,workers):
    for w in workers:
        if(w.getName()==name):
            return w

def getNameToWorkerDict(workers):
    nameToWorker = {}
    for w in workers:
        nameToWorker[w.getName()] = w
    return nameToWorker

def getR(w):
    ''' gets rank of hospital w is matched to based on p' (t-algorithm results)
        Note that p' is reported preferences '''
    h = w.getCurrent()
    if(h is None):
        return 0 # unmatched

    for i in range(len(w.getMatchings())):
        if(w.getMatchings()[i].getName() == h.getName()):
            return i + 1

def getR2(w):
    ''' gets the rank of hospital w is matched to based on p (original preferences)
       (this is based on matchings after both t-algorithm and Gale Shapley are run) '''
    h = w.getCurrent()
    if(h is None):
        return 0 # unmatched

    for i in range(len(w.getRanking())):
        if(w.getRanking()[i] == h.getName()):
            return i + 1

def getR3(w, pprime):
    ''' gets rank of doctor h is matched to based on p' (IU and CU)
        Note that p' is reported preferences '''
    h = w.getCurrent()
    if(h is None):
        return 0 # unmatched

    for i in range(len(pprime)):
        if(pprime[i] == h.getName()):
            return i + 1
    return -1

def fillInUtilities(hospital, hospital_names, worker_index, cu_sorted, iu_sorted, utilities_sorted):
    '''
    Hospital_names, cu_sorted, iu_sorted, utilities_sorted are all in the same order (each entry is a preference list for a hospital)
    Within the cu_sorted, iu_sorted, utilities_sorted lists, they preferences lists are in the order of doctors with highest CU first
    worker_index is 0 for the doctor with highest CU, 1 for second highest, etc
    hospital is the hospital that the worker matched to (so we can match its name to hospital_name to get its preference)
    '''
    hospital_index = 0
    for h in hospital_names:
        if (hospital.getName() == h):
            break
        hospital_index += 1
    return cu_sorted[hospital_index][worker_index], iu_sorted[hospital_index][worker_index], utilities_sorted[hospital_index][worker_index]

def getDoctorsAndHospitals(num_doctors, num_hospitals, we_doctors, we_hospitals):
    '''
        we_doctors is weight for common utility for doctors
        we_hospitals is weight for common utility for hospitals '''
    # First, note that we can change the distribution and its parameters for common utility
    cuw = [np.random.normal(0, 1) for x in range(num_hospitals)] # common utility hospitals provide
    cuh = [np.random.normal(0, 1) for x in range(num_doctors)] # common utility workers provide

    # This generates the workers and hospitals for this run (same ones used for all algorithms)
    workers = [Worker(cuw, "W" + str(x), we_doctors, num_hospitals) for x in range(1, num_doctors + 1)] #creates array of workers with their own randomized preferences
    hospitals = [Hospital(cuh, "H" + str(x), we_hospitals, num_doctors) for x in range(1, num_hospitals + 1)] # creates array of hospitals with their own randomized preferences
    workers2 = [Worker(cuw, "W" + str(x), we_doctors, num_hospitals) for x in range(1, num_doctors + 1)] # creates array of workers with their own randomized preferences
    hospitals2 = [Hospital(cuh, "H" + str(x), we_hospitals, num_doctors) for x in range(1, num_hospitals + 1)] # creates array of hospitals with their own randomized preferences
    workers3 = [Worker(cuw, "W" + str(x), we_doctors, num_hospitals) for x in range(1, num_doctors + 1)] # creates array of workers with their own randomized preferences

    return workers, hospitals, workers2, workers3, hospitals2, cuw, cuh

def getDoctorsAndHospitalsExtended(num_doctors, num_hospitals, we_doctors, we_hospitals):
    '''
        we_doctors is weight for common utility for doctors
        we_hospitals is weight for common utility for hospitals '''
    # First, note that we can change the distribution and its parameters for common utility
    cuw = [np.random.normal(0, 1) for x in range(num_hospitals)] # common utility hospitals provide
    cuh = [np.random.normal(0, 1) for x in range(num_doctors)] # common utility workers provide

    # This generates the workers and hospitals for this run (same ones used for all algorithms)
    workers = [Worker(cuw, "W" + str(x), we_doctors, num_hospitals) for x in range(1, num_doctors + 1)] #creates array of workers with their own randomized preferences
    hospitals = [Hospital(cuh, "H" + str(x), we_hospitals, num_doctors) for x in range(1, num_hospitals + 1)] # creates array of hospitals with their own randomized preferences
    workers2 = [Worker(cuw, "W" + str(x), we_doctors, num_hospitals) for x in range(1, num_doctors + 1)] # creates array of workers with their own randomized preferences
    hospitals2 = [Hospital(cuh, "H" + str(x), we_hospitals, num_doctors) for x in range(1, num_hospitals + 1)] # creates array of hospitals with their own randomized preferences
    workers3 = [Worker(cuw, "W" + str(x), we_doctors, num_hospitals) for x in range(1, num_doctors + 1)] # creates array of workers with their own randomized preferences
    workers4 = [Worker(cuw, "W" + str(x), we_doctors, num_hospitals) for x in range(1, num_doctors + 1)] # creates array of workers with their own randomized preferences
    hospitals4 = [Hospital(cuh, "H" + str(x), we_hospitals, num_doctors) for x in range(1, num_hospitals + 1)] # creates array of hospitals with their own randomized preferences

    return workers, hospitals, workers2, workers3, hospitals2, cuw, cuh, workers4, hospitals4

def addDoctorsAndWorkersToLists(num_doctors, num_hospitals, docs, works, types, runs, run_num, cu_ranks):
    '''
    This just updates these lists (this is done the same way every run)
    '''
    for i in range(1, num_doctors + 1):
        docs.append(i)
        types.append("Doctor")
        runs.append(run_num)
        cu_ranks.append(i)

    for i in range(1, num_hospitals + 1):
        works.append(i)
        types.append("Hospital")
        runs.append(run_num)
        cu_ranks.append(i)

def recordBlockingPairs(x, y, workers_list, hospitals_list, array_to_record, num_doctors, min_index):
    # make a dictionary mapping worker names to workers
    name_to_worker = getNameToWorkerDict(workers_list)

    # same with hospitals
    name_to_hospital = getNameToWorkerDict(hospitals_list)

    # now we check for blocking pairs for each individual doctor/hospital
    for i in range(len(x)):
        d = x[i]

        # get the actual worker
        w = name_to_worker[d]

        for j in range(len(y)):
            e = y[j]

            # get the actual hospital
            h = name_to_hospital[e]

            if(h.block(w) and w.block(h)):
                array_to_record[i + min_index] += 1
                array_to_record[j + num_doctors + min_index] += 1

def doTruncatedGS(workers, hospitals, x, y, max_interviews, doDocsPropose, doctors_p, doctors_pprime, hospitals_p, hospital_pprime, match_gs_truncated_pp_docs, match_gs_truncated_p_docs, array_to_record, num_doctors, min_index, match_name):
    w5 = []
    h5 = []
    for w in workers:
        w.setWishes3(max_interviews)  # sets wishes according to original preferences, but truncated
        w.setMatch(None)
        w5.append(w)
    for h in hospitals:
        h.setWishes2()  # sets wishes according to original preferences
        h.setMatch(None)
        h5.append(h)
    print("Starting GS with truncated preferences.  Time: " + str(np.datetime64('now')))

    if (doDocsPropose):
        proposals(w5, h5)
    else:
        proposals(h5, w5)

    w5_nameToWorkerDict = getNameToWorkerDict(w5)
    h5_nameToWorkerDict = getNameToWorkerDict(h5)

    # Now we iterate through the doctors in the order of highest CU and record their matchings
    for i in range(len(x)):
        d = x[i]

        # get the actual worker
        w = w5_nameToWorkerDict[d]

        match_gs_truncated_pp_docs.append(getR3(w, doctors_pprime[i]))
        match_gs_truncated_p_docs.append(getR3(w, doctors_p[i]))
        if (w.getCurrent() is None):
            match_name.append("Unmatched")
        else:
            match_name.append(w.getCurrent().getName())

    # Now we do the same thing, but recording the matchings for hospitals
    for i in range(len(y)):
        d = y[i]

        # get the actual hospital
        h = h5_nameToWorkerDict[d]

        match_gs_truncated_pp_docs.append(getR3(h, hospital_pprime[i]))
        match_gs_truncated_p_docs.append(getR3(h, hospitals_p[i])) # For p, the rankings are based on CU only
        if (h.getCurrent() is None):
            match_name.append("Unmatched")
        else:
            match_name.append(h.getCurrent().getName())

    # now we record blocking pairs
    recordBlockingPairs(x, y, w5, h5, array_to_record, num_doctors, min_index)

def doGS(workers, hospitals, x, y, doDocsPropose, doctors_p, doctors_pprime, hospitals_p, hospital_pprime, match_gs_p_docs, match_gs_pp_docs, array_to_record, num_doctors, min_index, match_name):
    # Here, we run Gale Shapley with no interview stage
    # Thus, we see what happens if there were no interviews and
    # doctors reported their true, untruncated preferences
    w3gs = []
    h3gs = []
    for w in workers:
        w.setWishes2() #sets wishes according to original preferences
        w.setMatch(None)
        w3gs.append(w)

    for h in hospitals:
        h.setWishes2() #sets wishes according to original preferences
        h.setMatch(None)
        h3gs.append(h)

    print("Starting GS with no interview stage and untruncated preferences.  Time: " + str(np.datetime64('now')))

    if (doDocsPropose):
        proposals(w3gs, h3gs) # Actual gale shapley algorithm
    else:
        proposals(h3gs, w3gs)

    # Record results
    w3gs_nameToWorkerDict = getNameToWorkerDict(w3gs)
    h3gs_nameToWorkerDict = getNameToWorkerDict(h3gs)

    for i in range(len(x)):
        d = x[i]

        # get the actual worker
        w = w3gs_nameToWorkerDict[d]

        match_gs_pp_docs.append(getR3(w, doctors_pprime[i]))
        match_gs_p_docs.append(getR3(w, doctors_p[i]))
        if (w.getCurrent() is None):
            match_name.append("Unmatched")
        else:
            match_name.append(w.getCurrent().getName())

    # Now we do the same thing, but recording the matchings for hospitals
    for i in range(len(y)):
        d = y[i]

        # get the actual hospital
        h = h3gs_nameToWorkerDict[d]

        match_gs_pp_docs.append(getR3(h, hospital_pprime[i]))
        match_gs_p_docs.append(getR3(h, hospitals_p[i])) # For p, the rankings are based on CU only
        if (h.getCurrent() is None):
            match_name.append("Unmatched")
        else:
            match_name.append(h.getCurrent().getName())

    # Check stability for final matchings (we compare with original rankings, p)
    recordBlockingPairs(x, y, w3gs, h3gs, array_to_record, num_doctors, min_index)

    # Gale shapley has been run with original preferences and results recorded for how hospitals were ranked in p

def runSIGSOnly(num_doctors, num_hospitals, we_doctors, we_hospitals, max_interviews, ids, docs, works, types, runs, run_num, match_in_pp_docs, match_in_p_docs, cu_ranks):
    workers, hospitals, workers2, workers3, hospitals2, cuw, cuh = getDoctorsAndHospitals(num_doctors, num_hospitals, we_doctors, we_hospitals)

    # First, we simply update the docs, works, and runs lists
    addDoctorsAndWorkersToLists(num_doctors, num_hospitals, docs, works, types, runs, run_num, cu_ranks)

    # This generates the preferences for the hospitals based only on common utiltiy (for SIGS)
    for h in hospitals2:
        h.generateP2(cuh, num_doctors) #hospital's original preferences,p, only based on cu
    x = hospitals2[0].getRanking() #these are the names of workers ranked by cu

    # Now we do the same thing, simply to get the list of hospitals ranked by CU
    for w in workers3:
        w.generateP2(cuw, num_hospitals)
    y = workers3[0].getRanking() # these are the names of the hospitals ranked by cu

    # We add the names to the ids list
    for x_1 in x:
        ids.append(x_1)
    for y_1 in y:
        ids.append(y_1)

    workers2_nameToWorkerDict = getNameToWorkerDict(workers2)
    hospitals2_nameToWorkerDict = getNameToWorkerDict(hospitals2)

    # Now we get the actual doctors and hospitals corresponding to these names
    # so we can check their final matches at the end
    ranked_workers = []
    for n in x:
        #ranked_workers.append(getWorker(n, workers2))
        ranked_workers.append(workers2_nameToWorkerDict[n])

    ranked_hospitals = []
    for n in y:
        #ranked_hospitals.append(getWorker(n, hospitals2))
        ranked_hospitals.append(hospitals2_nameToWorkerDict[n])

    # Now we set "workers2" to have the same ranking as "workers" so they are identical
    for i in range(len(workers)):
        workers2[i].setOrig(workers[i].getOrig())

    # Similarly, we want "hospitals2" to have the same idiosyncratic utilities
    # as "hospitals"even if the rankings aren't changed (still only based off of CU)
    # we use these idiosyncratic utilities to update the preferences after the interviews
    for i in range(len(hospitals)):
        hospitals2[i].setIU(hospitals[i].getIU())

    for w in workers2:
        w.setChoices(hospitals2)

    # Simulated Interviews
    for w in ranked_workers:
        while(len(w.getInterviews()) < max_interviews and len(w.getChoices()) > 0): # while interviewed at less than the max and has at least one more hospital to apply to
            h = w.getTopChoice()
            if(len(h.getInterviews()) < max_interviews): # if hospital has interviewed less than the max allowed
                h.interview(w)
                w.interview(h)
    # end of simulated interviews

    w3=[]
    h3=[]
    m4=[] # m4 are matchings from simulated interviews and Gale shapley with p with doctors proposing

    # Report preferences for Gale-Shapley/Deferred Acceptance Algorithm
    # For SIGS
    for w in workers2:
        w.setWishes4() # sets wishes according to matches of simulated interviews
        w3.append(w)

    # For SIGS, hospitals initially only had common utility
    # After interviewing candidates, they now have an idiosyncratic utility to their preferences
    # We add this to to create a new ranking of doctors by each hospital
    for h in hospitals2:
        h.setWishes4(cuh, we_hospitals) # add idiosyncratic utility and sets wishes according to matches of simulated interviews
        h3.append(h)

    w3_nameToWorkerDict = getNameToWorkerDict(w3)
    h3_nameToWorkerDict = getNameToWorkerDict(h3)
    # Since we just added idiosyncratic utility, we can save the p prime rankings
    hospital_pprime = []
    for d in y:

        #h = getWorker(d, h3)
        h = h3_nameToWorkerDict[d]

        hospital_pprime.append(h.getWishes())

    doctors_pprime = []
    for d in x:

        w = getWorker(d, w3)
        w = w3_nameToWorkerDict[d]

        doctors_pprime.append(w.getWishes())

    # Gale Shapley Algorithm
    proposals(w3,h3) # gale shapley after simulated interviews with doctors proposing

    w3_nameToWorkerDict = getNameToWorkerDict(w3)
    h3_nameToWorkerDict = getNameToWorkerDict(h3)
    # Now we iterate through the doctors in the order of highest CU and record their matchings
    for i in range(len(x)):
        d = x[i]

        #w = getWorker(d, w3) # get the actual worker
        w = w3_nameToWorkerDict[d]

        match_in_pp_docs.append(getR3(w, doctors_pprime[i]))
        match_in_p_docs.append(getR2(w))

    # Now we do the same thing, but recording the matchings for hospitals
    for i in range(len(y)):
        d = y[i]

        #h = getWorker(d, h3) # get the actual hospital
        h = h3_nameToWorkerDict[d]

        match_in_pp_docs.append(getR3(h, hospital_pprime[i]))
        match_in_p_docs.append(getR2(h)) # For p, the rankings are based on CU only

def runTAGS_and_GS(num_doctors, num_hospitals, we_doctors, we_hospitals, max_interviews, ids, docs, works, types, runs, run_num, cu_ranks, match_gs_p_docs, match_gs_pp_docs, match_gs_p_hosp, match_gs_pp_hosp, match_gs_truncated_p_docs, match_gs_truncated_pp_docs, match_gs_truncated_p_hosp,
    match_gs_truncated_pp_hosp, match_tags_p_docs, match_tags_pp_docs, cu_provided_gs, u_provided_gs, iu_provided_gs, cu_provided_gs_truncated, u_provided_gs_truncated, iu_provided_gs_truncated, cu_provided_tags, u_provided_tags, iu_provided_tags, blocking_pair_counts,
    bp_TAGS, min_index, match_tags_b_p_docs, match_tags_b_pp_docs, cu_provided_tags_b, u_provided_tags_b, iu_provided_tags_b, bp_TAGS_b, bp_GS_Trunc_h, bp_GS_Trunc_d, bp_GS_d, bp_GS_h, preference_profile, match_name_tags_d, match_name_tags_h, match_name_gs_d, match_name_gs_h, match_name_gs_trunc_d, match_name_gs_trunc_h):
    workers, hospitals, workers2, workers3, hospitals2, cuw, cuh, workers4, hospitals4 = getDoctorsAndHospitalsExtended(num_doctors, num_hospitals, we_doctors, we_hospitals)
    # note that workers and hospitals have the preferences that we use for all the other workers/hospitals lists
    # so we can get these preferences
    iu_sorted = []
    cu_sorted = []
    utilities_sorted = []
    hospital_names = [] # this is so we can match hospitals to indices in these lists by name
    for h in hospitals:
        iu_sorted.append(h.getIU_sorted())
        cu_sorted.append(h.getCU_sorted())
        utilities_sorted.append(h.getUtilities_sorted())
        hospital_names.append(h.getName())

    # First, we simply update the docs, works, and runs lists
    addDoctorsAndWorkersToLists(num_doctors, num_hospitals, docs, works, types, runs, run_num, cu_ranks)

    # This generates the preferences for the hospitals based only on common utiltiy (for SIGS)
    for h in hospitals2:
        h.generateP2(cuh, num_doctors) #hospital's original preferences,p, only based on cu (note that hospitals2 and hospitals have different IU, but same CU)
    x = hospitals2[0].getRanking() #these are the names of workers ranked by cu

    # Now we do the same thing, simply to get the list of hospitals ranked by CU
    for w in workers3:
        w.generateP2(cuw, num_hospitals) # this isn't used for any matching
    y = workers3[0].getRanking() # these are the names of the hospitals ranked by cu

    # We add the names to the ids list
    for x_1 in x:
        ids.append(x_1)
    for y_1 in y:
        ids.append(y_1)

    # Now we get the actual doctors and hospitals corresponding to these names
    # so we can check their final matches at the end
    workers2_nameToWorkerDict = getNameToWorkerDict(workers2)
    hospitals2_nameToWorkerDict = getNameToWorkerDict(hospitals2)

    ranked_workers = []
    for n in x:
        ranked_workers.append(workers2_nameToWorkerDict[n])

    ranked_hospitals = []
    for n in y:
        ranked_hospitals.append(hospitals2_nameToWorkerDict[n])

    # Now we set "workers2" to have the same ranking as "workers" so they are identical
    for i in range(len(workers)):
        workers2[i].setOrig(workers[i].getOrig())
        workers4[i].setOrig(workers[i].getOrig()) # This sets the preferences of the workers for TAGS to be the exact same as those for SIGS and GS

    # Similarly, we want "hospitals2" to have the same idiosyncratic utilities
    # as "hospitals"even if the rankings aren't changed (still only based off of CU)
    # we use these idiosyncratic utilities to update the preferences after the interviews
    for i in range(len(hospitals)):
        hospitals2[i].setIU(hospitals[i].getIU())
        hospitals4[i].setIU(hospitals[i].getIU())
        hospitals4[i].setRanking(hospitals[i].getRanking()) # This sets the preferences of the hospitals for TAGS to be the exact same as those for SIGS (after interviews)

    for w in workers2:
        w.setChoices(hospitals2)

    print("Starting T-Algorithm. Time: " + str(np.datetime64('now')))
    past = []
    current = []

    for w in workers4: # prematches all hospitals to each worker for t-algorithm
        w.match(hospitals4)
        w.match(getPreM(w))
        past.append(w.getMatchings())

    # T-Algorithm
    goal = max_interviews #sets max amount of interviews (matches in T-algorithm for each agent)
    current = iteration(goal,workers,hospitals)

    while(not equate(past,current)): # while they don't converge
        past = []
        for p in current:
            past.append(p)
        current = iteration(goal, workers4, hospitals4)

    # end of t-algorithm

    # Report preferences for Gale-Shapley/Deferred Acceptance Algorithm
    # For TAGS
    workers4b = []
    hospitals4b = [] # in these lists we store hospitals/workers for when doctors propose in GS phase after T-algorithm
    for w in workers4:
        w.setWishes() # sets wishes (reported preferences) according to matches of t-algorithm
        workers4b.append(w)

    for h in hospitals4:
        h.setWishes() #sets wishes according to matches of t-algorithm
        hospitals4b.append(h)

    hospital_pprime2 = []
    hospitals_p2 = []

    workers4_nameToWorkerDict = getNameToWorkerDict(workers4)
    hospitals4_nameToWorkerDict = getNameToWorkerDict(hospitals4)

    for d in y:
        h = hospitals4_nameToWorkerDict[d]

        hospital_pprime2.append(h.getWishes())
        hospitals_p2.append(h.getRanking())

    doctors_pprime2 = []
    doctors_p2 = []
    for d in x:
        w = workers4_nameToWorkerDict[d]

        doctors_pprime2.append(w.getWishes())
        doctors_p2.append(w.getOrig())

    print("Starting DA after T-Algorithm. Time: " + str(np.datetime64('now')))
    # Gale Shapley Algorithm
    proposals(workers4, hospitals4) # gale-shapley algorithm with doctors proposing after t-algorithm

    workers4_nameToWorkerDict = getNameToWorkerDict(workers4)
    hospitals4_nameToWorkerDict = getNameToWorkerDict(hospitals4)

    # Now we iterate through the doctors in the order of highest CU and record their matchings
    for i in range(len(x)):
        d = x[i]

        # get the actual worker
        w = workers4_nameToWorkerDict[d]

        match_tags_pp_docs.append(getR3(w, doctors_pprime2[i]))
        match_tags_p_docs.append(getR3(w, doctors_p2[i]))
        if (w.getCurrent() is None):
            match_name_tags_d.append("Unmatched")
        else:
            match_name_tags_d.append(w.getCurrent().getName())

        if (getR3(w, doctors_pprime2[i]) == 0): # unmatched, so no hospital
            cu_provided_tags.append(-2)
            iu_provided_tags.append(-2)
            u_provided_tags.append(-2)
        else:

            # Get the worker's match
            h = workers4_nameToWorkerDict[d].getCurrent()

            cu_doc, iu_doc, u_doc = fillInUtilities(h, hospital_names, i, cu_sorted, iu_sorted, utilities_sorted)
            cu_provided_tags.append(cu_doc)
            iu_provided_tags.append(iu_doc)
            u_provided_tags.append(u_doc)

    # Now we do the same thing, but recording the matchings for hospitals
    for i in range(len(y)):
        d = y[i]

        # get the actual hospital
        h = hospitals4_nameToWorkerDict[d]

        match_tags_pp_docs.append(getR3(h, hospital_pprime2[i]))
        match_tags_p_docs.append(getR3(h, hospitals_p2[i])) # For p, the rankings are based on CU only

        if (h.getCurrent() is None):
            match_name_tags_d.append("Unmatched")
        else:
            match_name_tags_d.append(h.getCurrent().getName())

        cu_provided_tags.append(-1)
        iu_provided_tags.append(-1)
        u_provided_tags.append(-1)

    # Check stability for final matchings (we compare with original rankings, p)
    bp1 = 0
    bp2 = 0
    for w in workers4:
        bp1 += w.checkBlocking(hospitals4)
        bp2 += w.checkBlocking2(hospitals4) # this excludes unmatched doctors/hospitals
    blocking_pair_counts[4].append(bp1)
    blocking_pair_counts[5].append(bp2)

    # now we check for blocking pairs for each individual doctor/hospital
    for i in range(len(x)):
        d = x[i]

        # get the actual worker
        w = workers4_nameToWorkerDict[d]

        for j in range(len(y)):
            e = y[j]

            # get the actual hospital
            h = hospitals4_nameToWorkerDict[e]

            if(h.block(w) and w.block(h)):
                bp_TAGS[i + min_index] += 1
                bp_TAGS[j + num_doctors + min_index] += 1

    print("starting DA for TAGS with hospitals proposing")
    # Now we run TA GS by re-using the T-algorithm results, but have hospitals propose in GS
    for w in workers4b:
        w.setWishes()
        w.setMatch(None)

    for h in hospitals4b:
        h.setWishes()
        h.setMatch(None)


    workers4b_nameToWorkerDict = getNameToWorkerDict(workers4b)
    hospitals4b_nameToWorkerDict = getNameToWorkerDict(hospitals4b)

    # Now that we finished the T-Algorithm, we can fill out the relevant rows for the
    # preference profile
    for i in range(len(x)):
        d = x[i]

        # get the actual worker
        w = workers4b_nameToWorkerDict[d]

        for j in range(len(y)):
            dh = y[j]

            # get the actual hospital
            h = hospitals4b_nameToWorkerDict[dh]

            # Row:
            row = []
            # Run ID
            row.append(run_num)
            # Doctor ID (Common Ranking is (i + 1))
            row.append(w.getName())
            # Hospital ID (Common Ranking is (j + 1))
            row.append(h.getName())
            # Doctor (i + 1) total utility from Hospital (j + 1)
            row.append(w.getTotalUtilityByHospital(h.getName()))
            # Hospital (j + 1) total utility from Doctor (i + 1)
            _, _, u_doc = fillInUtilities(h, hospital_names, i, cu_sorted, iu_sorted, utilities_sorted)
            row.append(u_doc)
            # Did Doctor (i + 1) interview at Hospital (j + 1) in TAGS
            if (h.getName() in w.getWishes()):
                row.append(1)
            else:
                row.append(0)

            # Now we add the row
            preference_profile.append(row)


    proposals(hospitals4b, workers4b) # gale-shapley algorithm with hospitals proposing

    workers4b_nameToWorkerDict = getNameToWorkerDict(workers4b)
    hospitals4b_nameToWorkerDict = getNameToWorkerDict(hospitals4b)

    # Now we iterate through the doctors in the order of highest CU and record their matchings
    for i in range(len(x)):
        d = x[i]

        # get the actual worker
        w = workers4b_nameToWorkerDict[d]

        match_tags_b_pp_docs.append(getR3(w, doctors_pprime2[i]))
        match_tags_b_p_docs.append(getR3(w, doctors_p2[i]))

        if (w.getCurrent() is None):
            match_name_tags_h.append("Unmatched")
        else:
            match_name_tags_h.append(w.getCurrent().getName())

        if (getR3(w, doctors_pprime2[i]) == 0): # unmatched, so no hospital
            cu_provided_tags_b.append(-2)
            iu_provided_tags_b.append(-2)
            u_provided_tags_b.append(-2)
        else:

            # Get the worker's match
            h = workers4b_nameToWorkerDict[d].getCurrent()

            cu_doc, iu_doc, u_doc = fillInUtilities(h, hospital_names, i, cu_sorted, iu_sorted, utilities_sorted)
            cu_provided_tags_b.append(cu_doc)
            iu_provided_tags_b.append(iu_doc)
            u_provided_tags_b.append(u_doc)

    # Now we do the same thing, but recording the matchings for hospitals
    for i in range(len(y)):
        d = y[i]

        # get the actual hospital
        h = hospitals4b_nameToWorkerDict[d]

        match_tags_b_pp_docs.append(getR3(h, hospital_pprime2[i]))
        match_tags_b_p_docs.append(getR3(h, hospitals_p2[i])) # For p, the rankings are based on CU only

        if (h.getCurrent() is None):
            match_name_tags_h.append("Unmatched")
        else:
            match_name_tags_h.append(h.getCurrent().getName())

        cu_provided_tags_b.append(-1)
        iu_provided_tags_b.append(-1)
        u_provided_tags_b.append(-1)

    # Check stability for final matchings (we compare with original rankings, p)
    bp1 = 0
    bp2 = 0
    for w in workers4b:
        bp1 += w.checkBlocking(hospitals4b)
        bp2 += w.checkBlocking2(hospitals4b) # this excludes unmatched doctors/hospitals
    blocking_pair_counts[0].append(bp1)
    blocking_pair_counts[1].append(bp2)

    # now we check for blocking pairs for each individual doctor/hospital
    for i in range(len(x)):
        d = x[i]

        # get the actual worker
        w = workers4b_nameToWorkerDict[d]

        for j in range(len(y)):
            e = y[j]

            # get the actual hospital
            h = hospitals4b_nameToWorkerDict[e]

            if(h.block(w) and w.block(h)):
                bp_TAGS_b[i + min_index] += 1
                bp_TAGS_b[j + num_doctors + min_index] += 1

    # Now we do GS with untrucated preferences with both doctors proposing
    doGS(workers, hospitals, x, y, True, doctors_p2, doctors_pprime2, hospitals_p2, hospital_pprime2, match_gs_p_docs, match_gs_pp_docs, bp_GS_d, num_doctors, min_index, match_name_gs_d)

    # And doctors not proposing
    doGS(workers, hospitals, x, y, False, doctors_p2, doctors_pprime2, hospitals_p2, hospital_pprime2, match_gs_p_hosp, match_gs_pp_hosp, bp_GS_h, num_doctors, min_index, match_name_gs_h)

    # Here we do the same as above, but we only truncate the preferences for the doctors and assume the hospitals rank every doctor
    doTruncatedGS(workers, hospitals, x, y, max_interviews, True, doctors_p2, doctors_pprime2, hospitals_p2, hospital_pprime2, match_gs_truncated_pp_docs, match_gs_truncated_p_docs, bp_GS_Trunc_d, num_doctors, min_index, match_name_gs_trunc_d)

    # Now we have hospitals propose
    doTruncatedGS(workers, hospitals, x, y, max_interviews, False, doctors_p2, doctors_pprime2, hospitals_p2, hospital_pprime2, match_gs_truncated_pp_hosp, match_gs_truncated_p_hosp, bp_GS_Trunc_h, num_doctors, min_index, match_name_gs_trunc_h)

    for i in range(len(x) + len(y)):
        cu_provided_gs_truncated.append(-1)
        iu_provided_gs_truncated.append(-1)
        u_provided_gs_truncated.append(-1)
        cu_provided_gs.append(-1)
        iu_provided_gs.append(-1)
        u_provided_gs.append(-1)

def runSIGSandGS(num_doctors, num_hospitals, we_doctors, we_hospitals, max_interviews, ids, docs, works, types, runs, run_num, match_in_pp_docs, match_in_p_docs, cu_ranks, match_gs_p_docs, match_gs_pp_docs):
    workers, hospitals, workers2, workers3, hospitals2, cuw, cuh = getDoctorsAndHospitals(num_doctors, num_hospitals, we_doctors, we_hospitals)

    # First, we simply update the docs, works, and runs lists
    addDoctorsAndWorkersToLists(num_doctors, num_hospitals, docs, works, types, runs, run_num, cu_ranks)

    # This generates the preferences for the hospitals based only on common utiltiy (for SIGS)
    for h in hospitals2:
        h.generateP2(cuh, num_doctors) #hospital's original preferences,p, only based on cu
    x = hospitals2[0].getRanking() #these are the names of workers ranked by cu

    # Now we do the same thing, simply to get the list of hospitals ranked by CU
    for w in workers3:
        w.generateP2(cuw, num_hospitals)
    y = workers3[0].getRanking() # these are the names of the hospitals ranked by cu

    # We add the names to the ids list
    for x_1 in x:
        ids.append(x_1)
    for y_1 in y:
        ids.append(y_1)

    # Now we get the actual doctors and hospitals corresponding to these names
    # so we can check their final matches at the end
    ranked_workers = []
    for n in x:
        ranked_workers.append(getWorker(n, workers2))

    ranked_hospitals = []
    for n in y:
        ranked_hospitals.append(getWorker(n, hospitals2))

    # Now we set "workers2" to have the same ranking as "workers" so they are identical
    for i in range(len(workers)):
        workers2[i].setOrig(workers[i].getOrig())

    # Similarly, we want "hospitals2" to have the same idiosyncratic utilities
    # as "hospitals"even if the rankings aren't changed (still only based off of CU)
    # we use these idiosyncratic utilities to update the preferences after the interviews
    for i in range(len(hospitals)):
        hospitals2[i].setIU(hospitals[i].getIU())

    for w in workers2:
        w.setChoices(hospitals2)

    # Simulated Interviews
    for w in ranked_workers:
        while(len(w.getInterviews()) < max_interviews and len(w.getChoices()) > 0): # while interviewed at less than the max and has at least one more hospital to apply to
            h = w.getTopChoice()
            if(len(h.getInterviews()) < max_interviews): # if hospital has interviewed less than the max allowed
                h.interview(w)
                w.interview(h)
    # end of simulated interviews

    w3=[] # These are for SIGS with Doctors Proposing
    h3=[]


    # Report preferences for Gale-Shapley/Deferred Acceptance Algorithm
    # For SIGS
    for w in workers2:
        w.setWishes4() # sets wishes according to matches of simulated interviews
        w3.append(w)

    # For SIGS, hospitals initially only had common utility
    # After interviewing candidates, they now have an idiosyncratic utility to their preferences
    # We add this to to create a new ranking of doctors by each hospital
    for h in hospitals2:
        h.setWishes4(cuh, we_hospitals) # add idiosyncratic utility and sets wishes according to matches of simulated interviews
        h3.append(h)

    # Since we just added idiosyncratic utility, we can save the p prime rankings
    hospital_pprime = []
    hospitals_p = []
    for d in y:
        h = getWorker(d, h3)
        hospital_pprime.append(h.getWishes())
        hospitals_p.append(h.getRanking()) # this is the same as x (only based on CU)

    doctors_pprime = []
    doctors_p = []
    for d in x:
        w = getWorker(d, w3)
        doctors_pprime.append(w.getWishes())
        doctors_p.append(w.getOrig())

    # Gale Shapley Algorithm
    proposals(w3,h3) # gale shapley after simulated interviews with doctors proposing

    # Now we iterate through the doctors in the order of highest CU and record their matchings
    for i in range(len(x)):
        d = x[i]
        w = getWorker(d, w3) # get the actual worker
        match_in_pp_docs.append(getR3(w, doctors_pprime[i]))
        match_in_p_docs.append(getR3(w, doctors_p[i]))

    # Now we do the same thing, but recording the matchings for hospitals
    for i in range(len(y)):
        d = y[i]
        h = getWorker(d, h3) # get the actual hospital
        match_in_pp_docs.append(getR3(h, hospital_pprime[i]))
        match_in_p_docs.append(getR3(h, hospitals_p[i])) # For p, the rankings are based on CU only

    # Here, we run Gale Shapley with no interview stage
    # Thus, we see what happens if there were no interviews and
    # doctors reported their true, untruncated preferences
    w3gs = []
    h3gs = []
    for w in workers:
        w.setWishes2() #sets wishes according to original preferences
        w.setMatch(None)
        w3gs.append(w)

    for h in hospitals:
        h.setWishes2() #sets wishes according to original preferences
        h.setMatch(None)
        h3gs.append(h)

    proposals(w3gs, h3gs) # Actual gale shapley algorithm

    # Record results
    for i in range(len(x)):
        d = x[i]
        w = getWorker(d, w3gs) # get the actual worker
        match_gs_pp_docs.append(getR3(w, doctors_pprime[i]))
        match_gs_p_docs.append(getR3(w, doctors_p[i]))

    # Now we do the same thing, but recording the matchings for hospitals
    for i in range(len(y)):
        d = y[i]
        h = getWorker(d, h3gs) # get the actual hospital
        match_gs_pp_docs.append(getR3(h, hospital_pprime[i]))
        match_gs_p_docs.append(getR3(h, hospitals_p[i])) # For p, the rankings are based on CU only

    # Gale shapley has been run with original preferences and results recorded for how hospitals were ranked in p


def simulate(n, num_docs, num_hospitals, cud, cuh, max_interviews, filename='empty'):
    ids = []
    docs = []
    works = []
    runs = []
    cu_ranks = []
    types = []
    match_in_pp_docs = []
    match_in_p_docs = []
    match_gs_p_docs = []
    match_gs_pp_docs = []
    match_gs_p_hosp = []
    match_gs_pp_hosp = []
    match_in_pp_hosp = []
    match_in_p_hosp = []
    match_gs_truncated_p_docs = []
    match_gs_truncated_pp_docs = []
    match_gs_truncated_p_hosp = []
    match_gs_truncated_pp_hosp = []
    match_tags_p_docs = []
    match_tags_pp_docs = []
    cu_provided_sigs = []
    iu_provided_sigs = []
    u_provided_sigs = []
    cu_provided_gs = []
    iu_provided_gs = []
    u_provided_gs = []
    cu_provided_gs_truncated = []
    iu_provided_gs_truncated = []
    u_provided_gs_truncated = []
    cu_provided_tags = []
    iu_provided_tags = []
    u_provided_tags = []
    blocking_pair_counts = []
    for i in range(6):
        blocking_pair_counts.append([])
    bp_SIGS = []
    bp_TAGS = []
    match_tags_b_p_docs = []
    match_tags_b_pp_docs = []
    cu_provided_tags_b = []
    u_provided_tags_b = []
    iu_provided_tags_b = []
    bp_TAGS_b = []
    bp_GS_Trunc_h = []
    bp_GS_Trunc_d = []
    bp_GS_d = []
    bp_GS_h = []
    preference_profile = []
    match_name_tags_d = []
    match_name_tags_h = []
    match_name_gs_d = []
    match_name_gs_h = []
    match_name_gs_trunc_d = []
    match_name_gs_trunc_h = []

    run_nums = []
    m_i = []
    n_d = []
    n_h = []
    cu_d = []
    cu_h = []
    min_index = 0 # this is for indexing blocking pairs
    max_index = 0
    for run_num in range(1, n + 1):
        min_index = max_index
        print("Simulation #" + str(run_num) + " Time: " + str(np.datetime64('now')))
        run_nums.append(run_num)
        m_i.append(max_interviews)
        n_d.append(num_docs)
        n_h.append(num_hospitals)
        cu_d.append(cud)
        cu_h.append(cuh)
        for j in range(num_docs):
            bp_TAGS.append(0)
            bp_SIGS.append(0)
            bp_TAGS_b.append(0)
            bp_GS_Trunc_h.append(0)
            bp_GS_Trunc_d.append(0)
            bp_GS_d.append(0)
            bp_GS_h.append(0)
            max_index += 1
        for j in range(num_hospitals):
            bp_TAGS.append(0)
            bp_SIGS.append(0)
            bp_TAGS_b.append(0)
            bp_GS_Trunc_h.append(0)
            bp_GS_Trunc_d.append(0)
            bp_GS_d.append(0)
            bp_GS_h.append(0)
            max_index += 1

        #runTAGS_and_GS(num_docs, num_hospitals, cud, cuh, max_interviews, ids, docs, works, types, runs, run_num, cu_ranks, match_gs_p_docs, match_gs_pp_docs, match_gs_p_hosp, match_gs_pp_hosp, match_gs_truncated_p_docs, match_gs_truncated_pp_docs, match_gs_truncated_p_hosp,
        #    match_gs_truncated_pp_hosp, match_tags_p_docs, match_tags_pp_docs, cu_provided_gs, u_provided_gs, iu_provided_gs, cu_provided_gs_truncated, u_provided_gs_truncated, iu_provided_gs_truncated, cu_provided_tags, u_provided_tags, iu_provided_tags, blocking_pair_counts,
        #        bp_TAGS, min_index, match_tags_b_p_docs, match_tags_b_pp_docs, cu_provided_tags_b, u_provided_tags_b, iu_provided_tags_b, bp_TAGS_b, bp_GS_Trunc_h, bp_GS_Trunc_d, bp_GS_d, bp_GS_h, preference_profile, match_name_tags_d, match_name_tags_h, match_name_gs_d, match_name_gs_h, match_name_gs_trunc_d, match_name_gs_trunc_h)
        #runSIGSOnly(num_docs, num_hospitals, cud, cuh, max_interviews, ids, docs, works, types, runs, run_num, match_in_pp_docs, match_in_p_docs, cu_ranks)
        runSIGSandGS(num_docs, num_hospitals, cud, cuh, max_interviews, ids, docs, works, types, runs, run_num, match_in_pp_docs, match_in_p_docs, cu_ranks, match_gs_p_docs, match_gs_pp_docs)

    #columns = ['id', 'Run','Type', 'Common ranking', 'Match GS D','GS Match, P (D Prop)', 'GS Match, P Prime (D Prop)', 'Match GS H', 'GS Match, P (H Prop)', 'GS Match, P Prime (H Prop)', 'Match GS Trunc D','GS Truncated Match, P (D Prop)', 'GS Truncated Match, P Prime (D Prop)', 'Match GS Trunc H','GS Truncated Match, P (H Prop)', 'GS Truncated Match, P Prime (H Prop)', 'Match TAGS P D','TAGS, P (D Prop)', 'TAGS, P Prime(D Prop)', 'Match TAGS P H',
    #          'TAGS, P (H Prop)', 'TAGS, P Prime(H Prop)',  'blocking pairs TAGS (D Prop)', 'blocking pairs TAGS (H Prop)', 'blocking pairs Trunc. GS (H Prop)', 'blocking pairs Trunc. GS (D Prop)', 'blocking pairs GS (D Prop)', 'blocking pairs GS (H Prop)']
    #results = pd.DataFrame(list(zip(ids, runs, types, cu_ranks, match_name_gs_d, match_gs_p_docs, match_gs_pp_docs, match_name_gs_h, match_gs_p_hosp, match_gs_pp_hosp, match_name_gs_trunc_d, match_gs_truncated_p_docs, match_gs_truncated_pp_docs, match_name_gs_trunc_h, match_gs_truncated_p_hosp, match_gs_truncated_pp_hosp, match_name_tags_d, match_tags_p_docs, match_tags_pp_docs, match_name_tags_h, match_tags_b_p_docs, match_tags_b_pp_docs, bp_TAGS, bp_TAGS_b, bp_GS_Trunc_h, bp_GS_Trunc_d, bp_GS_d, bp_GS_h)), columns = columns)

    # This commented out code is to run just SIGS
    #columns = ['id', 'Run','Type', 'Common ranking', 'SIGS Match, P (D Proposing)', 'SIGS Match, P Prime (D Proposing)']
    #results = pd.DataFrame(list(zip(ids, runs, types, cu_ranks, match_in_p_docs, match_in_pp_docs)), columns = columns)

    # This runs SIGS and GS with doctor proposing
    columns = ['id', 'Run','Type', 'Common ranking', 'SIGS Match, P (D Proposing)', 'SIGS Match, P Prime (D Proposing)', 'GS Match, P (D Proposing)', 'GS Match, P Prime (D Proposing)']
    results = pd.DataFrame(list(zip(ids, runs, types, cu_ranks, match_in_p_docs, match_in_pp_docs, match_gs_p_docs, match_gs_pp_docs)), columns = columns)

    col2 = ['Run', 'Max Interviews', 'Num Doctors', 'Num Hospitals', 'Common utility weight Doctors', 'Common utility weight Hospitals']
    results2 = pd.DataFrame(list(zip(run_nums, m_i, n_d, n_h, cu_d, cu_h)), columns = col2)


    if (filename != 'empty'):
        fn = filename + ".csv"
        fn2 = filename + "_key.csv"
        fn3 = filename + "_preference_profile.csv"
        results.to_csv(fn, index = False)
        results2.to_csv(fn2, index = False)
    return results, results2

import cProfile
import pstats

def profile(filename, func, args=None):

    pr = cProfile.Profile()
    pr.enable()

    if args is not None:
        func(**args)
    else:
        func()

    pr.disable()

    f = open(filename, 'w')

    ps = pstats.Stats(pr, stream=f)
    ps.sort_stats('cumulative', 'tottime')
    ps.print_stats()

    f.close()

simulate(34,500,500,0.75,0.05,5,'OutSim_SIGS_500_75_05_5X')
