app/soc/logic/allocations.py

   1 #!/usr/bin/python2.5
   2 #
   3 # Copyright 2009 the Melange authors.
   4 #
   5 # Licensed under the Apache License, Version 2.0 (the "License");
   6 # you may not use this file except in compliance with the License.
   7 # You may obtain a copy of the License at
   8 #
   9 #   http://www.apache.org/licenses/LICENSE-2.0
  10 #
  11 # Unless required by applicable law or agreed to in writing, software
  12 # distributed under the License is distributed on an "AS IS" BASIS,
  13 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14 # See the License for the specific language governing permissions and
  15 # limitations under the License.
  16
  17 """Slot allocation logic.
  18 """
  19
  20 __authors__ = [
  21   '"Sverre Rabbelier" <sverre@rabbelier.nl>',
  22   ]
  23
  24
  25 import itertools
  26 import math
  27
  28
  29 class Error(Exception):
  30   """Error class for the Allocation module.
  31   """
  32
  33   pass
  34
  35
  36 class Allocator(object):
  37   """A simple student slots allocator.
  38
  39   The buildSets method is used to validate the allocation data as well as
  40   construct the sets that the algorithm then uses to distribute the slots.
  41   By separating these steps it is possible to write a different allocation
  42   algorithm but re-use the sets and validation logic.
  43   """
  44
  45   # I tried to write explicit code that does not require any
  46   # additional comments (with the exception of the set notation for
  47   # the convenience of any mathematicians that happen to read this
  48   # piece of code ;).
  49
  50   def __init__(self, orgs, applications, slots, max_slots_per_org):
  51     """Initializes the allocator.
  52
  53     Args:
  54       orgs: a list of all the orgs that need to be allocated
  55       applications: a dictionary with for each org a list of applicants
  56       slots: the total amount of available slots
  57     """
  58
  59     all_applications = []
  60
  61     for _, value in applications.iteritems():
  62       all_applications += value
  63
  64     self.locked_slots = {}
  65     self.adjusted_slots = {}
  66     self.adjusted_orgss = []
  67     self.locked_orgs = []
  68     self.unlocked_applications = []
  69     self.slots = slots
  70     self.max_slots_per_org = max_slots_per_org
  71     self.orgs = set(orgs)
  72     self.applications = applications
  73     self.all_applications = set(all_applications)
  74
  75   def allocate(self, locked_slots, adjusted_slots):
  76     """Allocates the slots and returns the result.
  77
  78     Args:
  79       locked_slots: a dict with orgs and the number of slots they get
  80       adjusted_slots: a dict with orgs and the number of extra slots they get
  81     """
  82
  83     self.locked_slots = locked_slots
  84     self.adjusted_slots = adjusted_slots
  85
  86     self.buildSets()
  87
  88     return self.iterativeAllocation()
  89
  90   def buildSets(self):
  91     """Allocates slots with the specified constraints
  92     """
  93
  94     # set s
  95     all_applications = self.all_applications
  96     locked_slots = self.locked_slots
  97     adjusted_slots = self.adjusted_slots
  98
  99     # set a and b
 100     locked_orgs = set(locked_slots.keys())
 101     adjusted_orgs = set(adjusted_slots.keys())
 102
 103     # set a' and b'
 104     # unlocked_orgs = self.orgs.difference(locked_orgs)
 105     # unadjusted_orgs = self.orgs.difference(adjusted_orgs)
 106
 107     # set a*b and a'*b'
 108     locked_and_adjusted_orgs = locked_orgs.intersection(adjusted_orgs)
 109
 110     # unlocked_and_unadjusted_orgs = unlocked_orgs.intersection(unadjusted_orgs)
 111
 112     # a+o and b+o should be o
 113     locked_orgs_or_orgs = self.orgs.union(locked_orgs)
 114     adjusted_orgs_or_orgs = self.orgs.union(adjusted_orgs)
 115
 116     # an item can be only a or b, so a*b should be empty
 117     if locked_and_adjusted_orgs:
 118       raise Error("Cannot have an org locked and adjusted")
 119
 120     # a+o should be o, testing length is enough though
 121     if len(locked_orgs_or_orgs) != len(self.orgs):
 122       raise Error("Unknown org as locked slot")
 123
 124     # same for b+o
 125     if len(adjusted_orgs_or_orgs) != len(self.orgs):
 126       raise Error("Unknown org as adjusted slot")
 127
 128     # set l and l'
 129     locked_applications = set(itertools.chain(*locked_slots.keys()))
 130     unlocked_applications = all_applications.difference(locked_applications)
 131
 132     self.adjusted_orgss = adjusted_orgs
 133     self.locked_orgs = locked_orgs
 134     self.unlocked_applications = unlocked_applications
 135
 136   def iterativeAllocation(self):
 137     """A simple iterative algorithm.
 138     """
 139
 140     adjusted_orgs = self.adjusted_orgss
 141     adjusted_slots = self.adjusted_slots
 142     locked_orgs = self.locked_orgs
 143     locked_slots = self.locked_slots
 144     unlocked_applications = self.unlocked_applications
 145
 146     unlocked_applications_count = len(unlocked_applications)
 147     unallocated_applications_count = unlocked_applications_count
 148
 149     available_slots = self.slots
 150     allocations = {}
 151
 152     for org in self.orgs:
 153       org_applications = self.applications[org]
 154       org_applications_count = len(org_applications)
 155
 156       if org in locked_orgs:
 157         slots = locked_slots[org]
 158       else:
 159         weight = float(org_applications_count) / unallocated_applications_count
 160         slots = int(math.floor(weight*available_slots))
 161
 162       if org in adjusted_orgs:
 163         slots += adjusted_slots[org]
 164
 165       slots = min(slots, self.max_slots_per_org)
 166       slots = min(slots, org_applications_count)
 167       slots = min(slots, available_slots)
 168
 169       allocations[org] = slots
 170       available_slots -= slots
 171       unallocated_applications_count -= org_applications_count
 172
 173     return allocations