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