"""
This module contains a class that uses a greedy algorithm to find
a semi-optimal partition for a collection of items into a given
set of containers.
"""

from itertools import *
from sets import Set


class Error(Exception):
	pass


class Item:
	"""This class models an item.  It is always supposed to be just a
	reference to an outside entity, so you're supposed to use short
	labels in additon to the size.
	"""
	def __init__(self, label, size):
		self.label = label
		self.size = size

	def __repr__(self):
		return 'Item("%s", %d)'%(self.label, self.size)

	def getSize(self):
		return self.size
	
	def getLabel(self):
		return self.label


class Container:
	"""This class models a container for Items.
	"""
	def __init__(self, size, startItems=[]):
		self.capacity = size
		self.contents = startItems[:]
		self.curSize = 0

	def __repr__(self):
		return "Container(%d, [%s])"%(self.capacity, ", ".join([repr(i) 
			for i in self.contents]))

	def __iter__(self):
		return iter(self.contents)

	def getCapacity(self):
		return self.capacity

	def getRemainingCapacity(self):
		return self.capacity-self.curSize

	def getContents(self):
		return self.contents
	
	def add(self, item):
		if item.getSize()>self.getRemainingCapacity():
			raise Error, "%s is to big for this Container"%item
		self.contents.append(item)
		self.curSize += item.getSize()


class Partitioner:
	"""This class models a partitioner for a Set of Items into a Set
	of Containers.  They are modified in place.
	This one uses the following stratgem:
	While you can still assign an item:
		find the item that leaves the least space in any of the containers
		assign it to that container.
	"""
	def __init__(self, containers, items, verbose=0):
		self.verbose = verbose
		self.items = items
		self.containers = containers
		if self.verbose:
			print "Items to partition:"
			print "  "+("\n  ".join(["%s/%d"%(i.getLabel(), i.getSize())
				for i in self.items]))

	def _iterDiffs(self):
		for c in self.containers:
			for i in self.items:
				d = c.getRemainingCapacity()-i.getSize()
				if d>=0:
					yield d, c, i

	def _assignNext(self):
		"""We could probably save quite a few of these calculations by
		some sort of dynamic programming -- but our problems aren't 
		large enough to bother.
		"""
		bestAssignment = None
		for ass in self._iterDiffs():
			if bestAssignment is None or bestAssignment[0]>ass[0]:
				bestAssignment = ass
		if bestAssignment:
			if self.verbose:
				print "Best assignment: %s (%d), leaving %d in target container"%(
					bestAssignment[2].getLabel(), bestAssignment[2].getSize(),
					bestAssignment[0])
			newContainer, assignedItem = bestAssignment[1:]
			newContainer.add(assignedItem)
			self.items.remove(assignedItem)
			return 1
		return 0
	
	def partition(self):
		while self._assignNext():
			pass


def _test():
	import random
	items = Set([Item("item%d"%i, random.randint(1,20)**2+random.randint(1,20))
		for i in range(100)])
	containers = Set([Container(700) 
		for i in range(10)])
	part = Partitioner(containers, items)
	part.partition()
	print "Resulting containers: ", containers
	print "Leftover items: ", items
	print "Remaining total cap: %d"%sum([c.getRemainingCapacity()
		for c in containers])


if __name__=="__main__":
	_test()