# HG changeset patch # User Sverre Rabbelier # Date 1233193171 0 # Node ID d0c82bdc2de235c991bd1ab95790d49b84aac4d6 # Parent 61c2d296cd91cdf81660321379f4b1927749be78 Added a simple slot allocation algorithm Comes with a whole bunch of tests, but not nearly enough. Patch by: Sverre Rabbelier diff -r 61c2d296cd91 -r d0c82bdc2de2 app/soc/logic/allocations.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/app/soc/logic/allocations.py Thu Jan 29 01:39:31 2009 +0000 @@ -0,0 +1,167 @@ +#!/usr/bin/python2.5 +# +# Copyright 2008 the Melange authors. +# +# Licensed under the Apache License, Version 2.0 (the "License"); +# you may not use this file except in compliance with the License. +# You may obtain a copy of the License at +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. + +"""Slot allocation logic. +""" + +__authors__ = [ + '"Sverre Rabbelier" ', + ] + + +import itertools +import math + + +class Error(Exception): + """Error class for the Allocation module. + """ + + pass + + +class Allocator(object): + """A simple student slots allocator. + + The buildSets method is used to validate the allocation data as well as + construct the sets that the algorithm then uses to distribute the slots. + By separating these steps it is possible to write a different allocation + algorithm but re-use the sets and validation logic. + """ + + # I tried to write explicit code that does not require any + # additional comments (with the exception of the set notation for + # the convenience of any mathematicians that happen to read this + # piece of code ;). + + def __init__(self, orgs, applications, slots, max_slots_per_org): + """Initializes the allocator. + + Args: + orgs: a list of all the orgs that need to be allocated + applications: a dictionary with for each org a list of applicants + slots: the total amount of available slots + """ + + all_applications = [] + + for _, value in applications.iteritems(): + all_applications += value + + self.slots = slots + self.max_slots_per_org = max_slots_per_org + self.orgs = set(orgs) + self.applications = applications + self.all_applications = set(all_applications) + + def allocate(self, locked_slots, adjusted_slots): + """Allocates the slots and returns the result. + + Args: + locked_slots: a dict with orgs and the number of slots they get + adjusted_slots: a dict with orgs and the number of extra slots they get + """ + + self.locked_slots = locked_slots + self.adjusted_slots = adjusted_slots + + self.buildSets() + + return self.iterativeAllocation() + + def buildSets(self): + """Allocates slots with the specified constraints + """ + + # set s + all_applications = self.all_applications + locked_slots = self.locked_slots + adjusted_slots = self.adjusted_slots + + # set a and b + locked_orgs = set(locked_slots.keys()) + adjusted_orgs = set(adjusted_slots.keys()) + + # set a' and b' + unlocked_orgs = self.orgs.difference(locked_orgs) + unadjusted_orgs = self.orgs.difference(adjusted_orgs) + + # set a*b and a'*b' + locked_and_adjusted_orgs = locked_orgs.intersection(adjusted_orgs) + unlocked_and_unadjusted_orgs = unlocked_orgs.intersection(unadjusted_orgs) + + # a+o and b+o should be o + locked_orgs_or_orgs = self.orgs.union(locked_orgs) + adjusted_orgs_or_orgs = self.orgs.union(adjusted_orgs) + + # an item can be only a or b, so a*b should be empty + if locked_and_adjusted_orgs: + raise Error("Cannot have an org locked and adjusted") + + # a+o should be o, testing length is enough though + if len(locked_orgs_or_orgs) != len(self.orgs): + raise Error("Unknown org as locked slot") + + # same for b+o + if len(adjusted_orgs_or_orgs) != len(self.orgs): + raise Error("Unknown org as adjusted slot") + + # set l and l' + locked_applications = set(itertools.chain(*locked_slots.keys())) + unlocked_applications = all_applications.difference(locked_applications) + + self.adjusted_orgss = adjusted_orgs + self.locked_orgs = locked_orgs + self.unlocked_applications = unlocked_applications + + def iterativeAllocation(self): + """A simple iterative algorithm. + """ + + adjusted_orgs = self.adjusted_orgss + adjusted_slots = self.adjusted_slots + locked_orgs = self.locked_orgs + locked_slots = self.locked_slots + unlocked_applications = self.unlocked_applications + + unlocked_applications_count = len(unlocked_applications) + unallocated_applications_count = unlocked_applications_count + + available_slots = self.slots + allocations = {} + + for org in self.orgs: + org_applications = self.applications[org] + org_applications_count = len(org_applications) + + if org in locked_orgs: + slots = locked_slots[org] + else: + weight = float(org_applications_count) / unallocated_applications_count + slots = int(math.floor(weight*available_slots)) + + if org in adjusted_orgs: + slots += adjusted_slots[org] + + slots = min(slots, self.max_slots_per_org) + slots = min(slots, org_applications_count) + slots = min(slots, available_slots) + + allocations[org] = slots + available_slots -= slots + unallocated_applications_count -= org_applications_count + + return allocations diff -r 61c2d296cd91 -r d0c82bdc2de2 tests/app/soc/logic/__init__.py diff -r 61c2d296cd91 -r d0c82bdc2de2 tests/app/soc/logic/test_allocations.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/tests/app/soc/logic/test_allocations.py Thu Jan 29 01:39:31 2009 +0000 @@ -0,0 +1,217 @@ +#!/usr/bin/python2.5 +# +# Copyright 2008 the Melange authors. +# +# Licensed under the Apache License, Version 2.0 (the "License"); +# you may not use this file except in compliance with the License. +# You may obtain a copy of the License at +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. + + +__authors__ = [ + '"Sverre Rabbelier" ', + ] + + +import unittest + +from soc.logic import allocations + + +class Student(object): + """Mocker for Student object. + """ + + def __init__(self, id): + """Simple init that stores id for later use. + """ + + self.id = id + + def __eq__(self, other): + """Simple eq that compares ids. + """ + + return self.id == other.id + + def __str__(self): + """Simple str that returns str(id). + """ + + return str(self.id) + + def __repr__(self): + """Simple repr that returns repr(id). + """ + + return repr(self.id) + + +class AllocationsTest(unittest.TestCase): + """Tests related to the slot allocation algorithm. + """ + + def setUp(self): + """Set up required for the slot allocation tests. + """ + + self.slots = 60 + self.max_slots_per_org = 40 + self.allocated = 0 + + self.applications = { + 'asf': self.allocate(20), + 'gcc': self.allocate(15), + 'git': self.allocate(6), + 'google': self.allocate(3), + 'melange': self.allocate(100), + } + + self.orgs = self.applications.keys() + + self.allocater = allocations.Allocator(self.orgs, self.applications, + self.slots, self.max_slots_per_org) + + def allocate(self, count): + """Returns a list with count new student objects. + """ + + i = self.allocated + j = i + count + self.allocated += count + + return [Student(i) for i in range(i,j)] + + def testAllocate(self): + """Test that the allocate helper works properly. + + A meta-test, it never hurts to be certain. + """ + + stash = self.allocated + self.allocated = 0 + + expected = [Student(0), Student(1), Student(2)] + actual = self.allocate(3) + self.failUnlessEqual(expected, actual) + + expected = [] + actual = self.allocate(0) + self.failUnlessEqual(expected, actual) + + expected = [Student(3)] + actual = self.allocate(1) + self.failUnlessEqual(expected, actual) + + self.allocated = stash + + def testInitialAllocation(self): + """Test that an allocation with no arguments does not crash. + """ + + locked_slots = {} + adjusted_slots = {} + self.allocater.allocate(locked_slots, adjusted_slots) + + def testLockedSlotsAllocation(self): + """Test that an allocation with an org locked does not crash. + """ + + locked_slots = {'melange': 3} + adjusted_slots = {} + self.allocater.allocate(locked_slots, adjusted_slots) + + def testAdjustedSlotsAllocation(self): + """Test that an allocation with an org adjusted does not crash. + """ + + locked_slots = {} + adjusted_slots = {'google': -1} + self.allocater.allocate(locked_slots, adjusted_slots) + + def testInvalidSlotsAllocation(self): + """Test that an allocation with an org locked and adjusted errors out. + """ + + locked_slots = {'git': 1} + adjusted_slots = {'git': 1} + self.failUnlessRaises(allocations.Error, self.allocater.allocate, + locked_slots, adjusted_slots) + + def testNonExistantOrgAllocation1(self): + """Test that locking a non-existing org errors out. + """ + + locked_slots = {'gnome': 1} + adjusted_slots = {} + self.failUnlessRaises(allocations.Error, self.allocater.allocate, + locked_slots, adjusted_slots) + + def testNonExistantOrgAllocation2(self): + """Test that adjusting a non-existing org errors out. + """ + + locked_slots = {} + adjusted_slots = {'gnome': 1} + self.failUnlessRaises(allocations.Error, self.allocater.allocate, + locked_slots, adjusted_slots) + + def testInitialAllocationBelowMaxSlots(self): + """Test that the initial allocation is below the max slot count. + """ + + locked_slots = {} + adjusted_slots = {} + + result = self.allocater.allocate(locked_slots, adjusted_slots) + self.failIf(sum(result.values()) > self.slots) + + def testLockedAllocationCorrect(self): + """Test that locking an allocation assigns the org the allocation. + """ + + locked_slots = {'git': 6} + adjusted_slots = {} + + result = self.allocater.allocate(locked_slots, adjusted_slots) + + expected = 6 + actual = result['git'] + + self.failUnlessEqual(expected, actual) + + def testOverassignedAllocationCorrect(self): + """Test that over-assigned allocation are cut down. + """ + + locked_slots = {'git': 20} + adjusted_slots = {} + + result = self.allocater.allocate(locked_slots, adjusted_slots) + + expected = 6 + actual = result['git'] + + self.failUnlessEqual(expected, actual) + + def testAdjustedAllocationCorrect(self): + """Test that locking an allocation assigns the org the allocation. + """ + + locked_slots = {} + adjusted_slots = {'google': 1} + + with_adjusting = self.allocater.allocate(locked_slots, adjusted_slots) + without_adjusting = self.allocater.allocate(locked_slots, {}) + + expected = without_adjusting['google'] + 1 + actual = with_adjusting['google'] + + self.failUnlessEqual(expected, actual)