|
1 #!/usr/bin/python2.5 |
|
2 # |
|
3 # Copyright 2008 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.slots = slots |
|
65 self.max_slots_per_org = max_slots_per_org |
|
66 self.orgs = set(orgs) |
|
67 self.applications = applications |
|
68 self.all_applications = set(all_applications) |
|
69 |
|
70 def allocate(self, locked_slots, adjusted_slots): |
|
71 """Allocates the slots and returns the result. |
|
72 |
|
73 Args: |
|
74 locked_slots: a dict with orgs and the number of slots they get |
|
75 adjusted_slots: a dict with orgs and the number of extra slots they get |
|
76 """ |
|
77 |
|
78 self.locked_slots = locked_slots |
|
79 self.adjusted_slots = adjusted_slots |
|
80 |
|
81 self.buildSets() |
|
82 |
|
83 return self.iterativeAllocation() |
|
84 |
|
85 def buildSets(self): |
|
86 """Allocates slots with the specified constraints |
|
87 """ |
|
88 |
|
89 # set s |
|
90 all_applications = self.all_applications |
|
91 locked_slots = self.locked_slots |
|
92 adjusted_slots = self.adjusted_slots |
|
93 |
|
94 # set a and b |
|
95 locked_orgs = set(locked_slots.keys()) |
|
96 adjusted_orgs = set(adjusted_slots.keys()) |
|
97 |
|
98 # set a' and b' |
|
99 unlocked_orgs = self.orgs.difference(locked_orgs) |
|
100 unadjusted_orgs = self.orgs.difference(adjusted_orgs) |
|
101 |
|
102 # set a*b and a'*b' |
|
103 locked_and_adjusted_orgs = locked_orgs.intersection(adjusted_orgs) |
|
104 unlocked_and_unadjusted_orgs = unlocked_orgs.intersection(unadjusted_orgs) |
|
105 |
|
106 # a+o and b+o should be o |
|
107 locked_orgs_or_orgs = self.orgs.union(locked_orgs) |
|
108 adjusted_orgs_or_orgs = self.orgs.union(adjusted_orgs) |
|
109 |
|
110 # an item can be only a or b, so a*b should be empty |
|
111 if locked_and_adjusted_orgs: |
|
112 raise Error("Cannot have an org locked and adjusted") |
|
113 |
|
114 # a+o should be o, testing length is enough though |
|
115 if len(locked_orgs_or_orgs) != len(self.orgs): |
|
116 raise Error("Unknown org as locked slot") |
|
117 |
|
118 # same for b+o |
|
119 if len(adjusted_orgs_or_orgs) != len(self.orgs): |
|
120 raise Error("Unknown org as adjusted slot") |
|
121 |
|
122 # set l and l' |
|
123 locked_applications = set(itertools.chain(*locked_slots.keys())) |
|
124 unlocked_applications = all_applications.difference(locked_applications) |
|
125 |
|
126 self.adjusted_orgss = adjusted_orgs |
|
127 self.locked_orgs = locked_orgs |
|
128 self.unlocked_applications = unlocked_applications |
|
129 |
|
130 def iterativeAllocation(self): |
|
131 """A simple iterative algorithm. |
|
132 """ |
|
133 |
|
134 adjusted_orgs = self.adjusted_orgss |
|
135 adjusted_slots = self.adjusted_slots |
|
136 locked_orgs = self.locked_orgs |
|
137 locked_slots = self.locked_slots |
|
138 unlocked_applications = self.unlocked_applications |
|
139 |
|
140 unlocked_applications_count = len(unlocked_applications) |
|
141 unallocated_applications_count = unlocked_applications_count |
|
142 |
|
143 available_slots = self.slots |
|
144 allocations = {} |
|
145 |
|
146 for org in self.orgs: |
|
147 org_applications = self.applications[org] |
|
148 org_applications_count = len(org_applications) |
|
149 |
|
150 if org in locked_orgs: |
|
151 slots = locked_slots[org] |
|
152 else: |
|
153 weight = float(org_applications_count) / unallocated_applications_count |
|
154 slots = int(math.floor(weight*available_slots)) |
|
155 |
|
156 if org in adjusted_orgs: |
|
157 slots += adjusted_slots[org] |
|
158 |
|
159 slots = min(slots, self.max_slots_per_org) |
|
160 slots = min(slots, org_applications_count) |
|
161 slots = min(slots, available_slots) |
|
162 |
|
163 allocations[org] = slots |
|
164 available_slots -= slots |
|
165 unallocated_applications_count -= org_applications_count |
|
166 |
|
167 return allocations |