class Boundary:
	def __init__(self, type, position, obj):
		self.type = type
		self.position = position
		self.obj = obj

class RDCEntity:
	"""
	Base class you should override to make things which are RDC collideable.
	
	axisFns is a list of dimension bounding axis conditions.
	These must be methods which return the values of each bound on a particular axis for this entity.
	"""
	axisFns = [["GetLeft", "GetRight"], ["GetTop", "GetBottom"]]
	
	def Collide(self, who):
		"""
		'who' is the other entity who we collided with.
		"""
	
	def SetGroup(self, group, friends):
		"""
		Set the group identifier number that we are part of.
		group is the integer ID.
		friends is a list of friends in my collision group.
		"""
	
	##################
	# Axis functions #
	##################
	
	def GetLeft(self):
		"""
		Example axis function which returns the left bound on the x axis.
		"""

class RDC:
	def __init__(self, entityClass):
		# Array of functions that contain the sort and position functions for each axis
		self.axisFns = entityClass.axisFns
		# which axis we are currently checking on in this pass
		self.idx = 0
		# test if there has been a division or not
		self.divided = True
	
	def DoSort(self, clusters, axis):
		# we're going to replace all clusters with new found ones
		newclusters = []
		# assume that we won't divide any further
		self.divided = False
		
		# for every sub cluster in our group of clusters
		for c in clusters:
			if len(c) > 1:
				boundaries = []
				count = 0
				group = []
				
				# store the intervals for a given axis in a list data structure
				for obj in c:
					boundaries.append(Boundary('o', getattr(obj, axis[0])(), obj))
					boundaries.append(Boundary('c', getattr(obj, axis[1])(), obj))
				
				# sort our list of all boundaries on position
				boundaries.sort(lambda a, b: cmp(a.position, b.position))
				
				# finally, make new chunks out of our existing collection
				for i in xrange(len(boundaries)):
					b = boundaries[i]
					# if we find a leading edge, increment our count
					# and push it onto our stack of the current group
					if b.type == "o":
						count += 1
						group.append(b.obj)
					elif b.type == "c":
						count -= 1
						# if we have finished finding a group
						# push this group onto the stack on new clusters
						# empty out our group
						if count == 0:
							newclusters.append(group)
							group = []
							# if we're not at the very end of our array then we've just made a new subdivision
							if i != len(boundaries) - 1:
								self.divided = True
			
		return newclusters
	
	def FindGroups(self, group):
		clusters = [group]
		while (self.divided):
			# find the new clusters
			clusters = self.DoSort(clusters, self.axisFns[self.idx])
			# select the next axis for subdivision
			self.idx = (self.idx + 1) % len(self.axisFns)
		return clusters
	
	def DoRDC(self, entities):
		groups = self.FindGroups(entities)
		for g in xrange(len(groups)):
			# Do collision callbacks
			self.BruteForceRectangles(groups[g])
			# set which group each entity belongs to
			# pass in group friends
			[d.SetGroup(g, groups[g]) for d in groups[g]]
	
	def BruteForceRectangles(self, group):
		"""
		Bruteforce collision detection.
		Pass in an array of objects, and an array that looks like this:
		[[leading1, trailing1], [leading2, trailing2], [leading3, trailing3]...]
		
		leading1 is the function that returns the leading edge of an axis bounding box.
		trailing1 is the function that returns the trailing edge of an axis bounding box.
	
		You can pass in the name of the collide method too.
		"""
		glen = len(group)
		for i in xrange(glen):
			for j in xrange(i + 1, glen):
				collided = True
				for a in self.axisFns:
					if (getattr(group[i], a[0])() > getattr(group[j], a[1])()):
						collided = False
					if collided and (getattr(group[j], a[0])() > getattr(group[i], a[1])()):
						collided = False
				
				if collided:
					group[i].Collide(group[j])
					group[j].Collide(group[i])