text: # -*- 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 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)
  
      #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)
      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)
  
      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.05,0.95,5,'OutSim_SIGS_500_05_95_5X')