# HG changeset patch
# User Sverre Rabbelier <srabbelier@gmail.com>
# Date 1236445745 0
# Node ID ca34f4a8c61bde92a1f1de3c1dedbb2d80362499
# Parent  d4c4c8668871c006170de6024e0a0ce3337ca751
Added an pre-processing algorithm

Patch by: Sverre Rabbelier

diff -r d4c4c8668871 -r ca34f4a8c61b app/soc/logic/allocations.py
--- a/app/soc/logic/allocations.py	Sat Mar 07 17:08:23 2009 +0000
+++ b/app/soc/logic/allocations.py	Sat Mar 07 17:09:05 2009 +0000
@@ -92,7 +92,10 @@
 
     self.buildSets()
 
-    return self.iterativeAllocation()
+    if self.iterative:
+      return self.iterativeAllocation()
+    else:
+      return self.preprocessingAllocation()
 
   def buildSets(self):
     """Allocates slots with the specified constraints
@@ -183,3 +186,76 @@
       unallocated_applications_count -= org_applications_count
 
     return allocations
+
+  def preprocessingAllocation(self):
+    """An algorithm that pre-processes the input before running as normal.
+    """
+
+    adjusted_orgs = self.adjusted_orgs
+    adjusted_slots = self.adjusted_slots
+    locked_orgs = self.locked_orgs
+    locked_slots = self.locked_slots
+    unlocked_orgs = self.unlocked_orgs
+    unlocked_applications = self.unlocked_applications
+
+    total_popularity = sum(self.popularity.values())
+
+    available_slots = self.slots
+    allocations = {}
+    slack = {}
+
+    for org in locked_orgs:
+      popularity = self.popularity[org]
+      mentors = self.mentors[org]
+      slots = locked_slots[org]
+      slots = min(slots, mentors)
+
+      total_popularity -= popularity
+      available_slots -= slots
+      allocations[org] = slots
+
+    # adjust the orgs in need of adjusting
+    for org in adjusted_orgs:
+      slots = adjusted_slots[org]
+
+      adjustment = (float(total_popularity)/float(available_slots))*slots
+      adjustment = int(math.ceil(adjustment))
+      self.popularity[org] += adjustment
+
+    # adjust the popularity so that the invariants are always met
+    for org in unlocked_orgs:
+      popularity = self.popularity[org]
+      mentors = self.mentors[org]
+
+      slots = (float(popularity)/float(total_popularity))*available_slots
+      slots = min(slots, self.max_slots_per_org)
+      slots = max(slots, self.min_slots_per_org)
+      slots = min(slots, mentors)
+
+      popularity = (float(total_popularity)/float(available_slots))*slots
+
+      self.popularity[org] = popularity
+
+    # do the actual calculation
+    for org in unlocked_orgs:
+      org_applications = self.applications[org]
+      org_applications_count = len(org_applications)
+
+      popularity = self.popularity[org]
+      raw_slots = (float(popularity)/float(total_popularity))*available_slots
+      slots = int(math.floor(raw_slots))
+
+      slack[org] = raw_slots - slots
+      allocations[org] = slots
+
+    slots_left = available_slots - sum(allocations.values())
+
+    # add leftover slots, sorted by slack, decending
+    for org, slack in sorted(slack.iteritems(), key=lambda (k,v): v, reverse=True):
+      if slots_left < 1:
+        break
+
+      slots_left -= 1
+      allocations[org] += 1
+
+    return allocations
diff -r d4c4c8668871 -r ca34f4a8c61b tests/app/soc/logic/test_allocations.py
--- a/tests/app/soc/logic/test_allocations.py	Sat Mar 07 17:08:23 2009 +0000
+++ b/tests/app/soc/logic/test_allocations.py	Sat Mar 07 17:09:05 2009 +0000
@@ -66,7 +66,7 @@
     self.max_slots_per_org = 40
     self.min_slots_per_org = 2
     self.allocated = 0
-    self.iterative = True
+    self.iterative = False
 
     apps = {
         'asf': self.allocate(20, 20),