--- /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" <sverre@rabbelier.nl>',
+  ]
+
+
+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

--- /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" <sverre@rabbelier.nl>',
+  ]
+
+
+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)