# HG changeset patch
# User Sverre Rabbelier <srabbelier@gmail.com>
# Date 1239314778 0
# Node ID 32b0731f0bf5dd0f715261275228e62c6dc9b91c
# Parent  43a02512ebf77d4cd56da8a21bc89c001b38566a
Add a new allocation algorithm and use it

Patch by: Sverre Rabbelier

diff -r 43a02512ebf7 -r 32b0731f0bf5 app/soc/logic/allocations.py
--- a/app/soc/logic/allocations.py	Thu Apr 09 22:05:44 2009 +0000
+++ b/app/soc/logic/allocations.py	Thu Apr 09 22:06:18 2009 +0000
@@ -93,6 +93,9 @@
     if self.algorithm == 1:
       return self.preprocessingAllocation()
 
+    if self.algorithm == 2:
+      return self.reliableAlgorithm()
+
     return self.iterativeAllocation()
 
   def buildSets(self):
@@ -244,3 +247,71 @@
       allocations[org] = slots
 
     return allocations
+
+  def reliableAlgorithm(self):
+    """An algorithm that reliable calculates the slots assignments.
+    """
+
+    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
+    total_popularity = self.total_popularity
+
+    available_slots = self.slots
+    allocations = {}
+    slack = {}
+
+    # take out the easy ones
+    for org in locked_orgs:
+      popularity = self.popularity[org]
+      slots = locked_slots[org]
+      slots = float(slots)
+      slots = self.rangeSlots(slots, org)
+
+      total_popularity -= popularity
+      available_slots -= slots
+      allocations[org] = slots
+      del self.popularity[org]
+
+    total_popularity = sum(self.popularity.values())
+
+    pop_per_slot = float(available_slots)/float(total_popularity)
+
+    slack = 0
+    wanted = {}
+
+    # filter out all those that deserve more than their maximum
+    for org in unlocked_orgs:
+      popularity = self.popularity[org]
+      raw_slots = float(popularity)*pop_per_slot
+      slots = int(math.floor(raw_slots))
+      slots = self.rangeSlots(slots, org)
+      max = self.max[org]
+
+      if max > slots:
+        wanted[org] = max - slots
+
+      allocations[org] = slots
+
+    available_slots = self.slots - sum(allocations.values())
+
+    # distribute the slack
+    while available_slots > 0 and (sum(wanted.values()) > 0):
+      for org, amount in wanted.iteritems():
+        available_slots = self.slots - sum(allocations.values())
+        if available_slots <= 0:
+          break
+
+        if wanted[org] <= 0:
+          continue
+
+        current = allocations[org]
+        slots = self.rangeSlots(current + 1, org)
+        extra = current - slots
+
+        wanted[org] += extra
+        allocations[org] = slots
+
+    return allocations
diff -r 43a02512ebf7 -r 32b0731f0bf5 app/soc/views/models/program.py
--- a/app/soc/views/models/program.py	Thu Apr 09 22:05:44 2009 +0000
+++ b/app/soc/views/models/program.py	Thu Apr 09 22:06:18 2009 +0000
@@ -318,7 +318,7 @@
 
     max_slots_per_org = program.max_slots
     min_slots_per_org = program.min_slots
-    algorithm = 1
+    algorithm = 2
 
     allocator = allocations.Allocator(orgs.keys(), applications, max,
                                       program_slots, max_slots_per_org,
diff -r 43a02512ebf7 -r 32b0731f0bf5 tests/app/soc/logic/test_allocations.py
--- a/tests/app/soc/logic/test_allocations.py	Thu Apr 09 22:05:44 2009 +0000
+++ b/tests/app/soc/logic/test_allocations.py	Thu Apr 09 22:06:18 2009 +0000
@@ -66,7 +66,7 @@
     self.max_slots_per_org = 40
     self.min_slots_per_org = 2
     self.allocated = 0
-    self.algorithm = 1
+    self.algorithm = 2
 
     apps = {
         'asf': (20, 20),