#!/usr/bin/python

import math
import copy
import random
import Image
import ImageDraw


class RectBase(object):
	def __init__(self):
		self.x = 0
		self.y = 0
		self.width = 0
		self.height = 0
	
	def area(self):
		return self.width * self.height
		
	
class Rectangle(RectBase):
	def __init__(self, width, height, color):
		super(Rectangle,self).__init__()
		
		self.width = width
		self.height = height
		self.color = color
	
	
class Packer:
	def __init__(self, width, height, search_resolution):
		self.rect_list = []
		self.packed_rect_list = []
		self.search_step = 0
		self.area_covered = 0
	
		self.width = width
		self.height = height
		
		self.image = Image.new("RGB", (width, height))
		self.draw = ImageDraw.ImageDraw(self.image)
		
		self.search_resolution = search_resolution
		
	def add_rect(self, width, height, color):
		self.rect_list.append(Rectangle(width, height, color))
		
	def compile(self):
		# sort rectangles by surface area
		self._sort_rects()
		
		# generate node tree
		#self._build_tree(self.node)
		self._build_tree((0 ,0, self.width, self.height))
		
		# returns list of rectangles that did not fit
		return self.rect_list
	
	def save_image(self, filename):
		a = 0
		for r in self.packed_rect_list:
			#self.draw.rectangle(((r.x, r.y), (r.x + r.width-1, r.y + r.height-1)), fill=r.color, outline=(r.color[0]*2/3, r.color[1]*2/3, r.color[2]*2/3))
			self.draw.rectangle(((r.x, r.y), (r.x + r.width-1, r.y + r.height-1)), fill=r.color, outline=((255+r.color[0])/2, (255+r.color[1])/2, (255+r.color[2])/2))
			a += r.area()
			
		self.image.save(filename)
		print float(a) / float(self.width * self.height)
		
	def _sort_rects(self):
		self.rect_list.sort(lambda x, y: cmp(x.area(), y.area()), reverse=True)
		#self.rect_list.sort(lambda x, y: cmp(x.area()+(x.width/x.height), y.area()+(y.width/y.height)), reverse=True)
		
	def _build_tree(self, free_space):
		global search_step, search_resolution
		
		if free_space[2] <= 0 or free_space[3] <= 0:
			return
			
		if len(self.rect_list) == 0:
			return
		
		#self.draw.rectangle(((free_space[0], free_space[1]), (free_space[0] + free_space[2], free_space[1] + free_space[3])), fill=None, outline=(255,255,255))
		
		# Find rectangle that fits in current node
		rect_index = 0
		done = False
		step = max(rect_index + len(self.rect_list) / self.search_resolution, 1)
		while not done:
			if (self.rect_list[rect_index].width <= free_space[2]) and (self.rect_list[rect_index].height <= free_space[3]):
				done = True
			else:
				self.search_step += 1
				rect_index += step
				#rect_index = max(rect_index + len(self.rect_list) / 20, 1)
				if rect_index >= len(self.rect_list):
					return
				
		#print rect_index
		
		# Move rectangle from rect_list to packed_rect_list		
		rect = self.rect_list.pop(rect_index)
		self.packed_rect_list.append(rect)
		
		# Set rectangle x, y
		rect.x = free_space[0]
		rect.y = free_space[1]
		
		self.area_covered += rect.width * rect.height
		
		# Determine cutting direction (horizontal or vertical)
		# Split current node
		if (free_space[2] - rect.height) > (free_space[3] - rect.width):
			# cut into two nodes side-by-side
			# Shrink first node of spit nodes
			# call _build_tree for each new node
			#self._build_tree((free_space[0] + rect.width, free_space[1], free_space[2] - rect.width, free_space[3]))
			self._build_tree((free_space[0], free_space[1] + rect.height, rect.width, free_space[3] - rect.height))
			self._build_tree((free_space[0] + rect.width, free_space[1], free_space[2] - rect.width, free_space[3]))
		else:
			# cut into two nodes one on top of the other
			# Shrink first node of spit nodes
			# call _build_tree for each new node
			#self._build_tree((free_space[0], free_space[1] + rect.height, free_space[2], free_space[3] - rect.height))
			self._build_tree((free_space[0] + rect.width, free_space[1], free_space[2] - rect.width, rect.height))
			self._build_tree((free_space[0], free_space[1] + rect.height, free_space[2], free_space[3] - rect.height))


if __name__ == "__main__":
	p = Packer(256, 256, 2000)
	#p = Packer(43 * 5, 129 * 5, 20000)
	for i in xrange(465):
		#p.add_rect(math.pow(2,random.randint(2,6)), math.pow(2,random.randint(2,6)), (random.randint(0, 255), random.randint(0, 255), random.randint(0, 255)))
		#p.add_rect(random.randint(1, 4)*8, random.randint(1, 4)*8, (random.randint(0, 255), random.randint(0, 255), random.randint(0, 255)))
		p.add_rect(random.randint(1, 5)*4, random.randint(1, 5)*4, (random.randint(0, 255), random.randint(0, 255), random.randint(0, 255)))
		#p.add_rect((i+1)*5,(i+1)*5,(random.randint(0, 255), random.randint(0, 255), random.randint(0, 255)))
		#p.add_rect(random.randint(1, 25), random.randint(1, 25), (random.randint(0, 255), random.randint(0, 255), random.randint(0, 255)))
		#p.add_rect(random.randint(1, 10)*4, random.randint(1, 10)*4, (random.randint(0, 255), random.randint(0, 255), random.randint(0, 255)))
		
	print "Compiling"
	r = p.compile()
	print "rectangles that did not fit:", len(r)
	print [(i.width, i.height) for i in r]
	#for i in r:
	#	print "%i x %i" % (i.width, i.height)
	print "wasted search steps:", p.search_step
	print "area used:", float(p.area_covered) / float(p.width*p.height)
	
	p.save_image("rect_pack.png")