#!/usr/bin/env python3
 
import glob
from PIL import Image
from random import shuffle
 
MAXSIZE = (640,480)
 
images = []
 
imagefilelist = list(glob.glob("images/*.*"))
 
for imagefile in imagefilelist:
    image = Image.open(imagefile)
    image.thumbnail(MAXSIZE)
    images.append(image)
 
images.sort(key=lambda image: image.size[0] * image.size[1], reverse=True)
#shuffle(images)
 
class Rectangle:
    def __init__(self, x1, y1, x2, y2, image=None):
        self.x1 = x1
        self.x2 = x2
        self.y1 = y1
        self.y2 = y2
        self.width = x2 - x1
        self.height = y2 - y1
        self.area = self.width * self.height
        self.ratio = self.width / self.height
        self.image = image
    def __eq__(self, other):
        return (self.x1 == other.x1 and self.y1 == other.y1 and
                self.x2 == other.x2 and self.y2 == other.y2)
    def __hash__(self):
        return (self.x1, self.y1, self.x2, self.y2).__hash__()
    def __repr__(self):
        return "(" + str(self.x1) + " " + str(self.y1) + " " + str(self.x2) + " " + str(self.y2) + ")"
    def intersects(self, other):
        if type(other) == Rectangle:
            return (self.x1 < other.x2 and self.x2 > other.x1 and
                    self.y1 < other.y2 and self.y2 > other.y1)
        for r in other:
            if self.intersects(r):
                return True
        return False
    def grow(self, other):
        if type(other) != Rectangle:
            raise Exception()
        return Rectangle(self.x1 if self.x1 < other.x1 else other.x1,
                         self.y1 if self.y1 < other.y1 else other.y1,
                         self.x2 if self.x2 > other.x2 else other.x2,
                         self.y2 if self.y2 > other.y2 else other.y2)
 
 
OFFSET = 16
offset = OFFSET
 
rectangles = []
overall = None
inflections = set([])
c = 0
for image in images:
    if not len(rectangles):
        rectangles.append(Rectangle(0,0, image.size[0], image.size[1], image))
        overall = Rectangle(0, 0, image.size[0], image.size[1])
        inflections.update([(overall.x1-OFFSET, overall.y1-OFFSET),
                            (overall.x2+OFFSET, overall.y1-OFFSET),
                            (overall.x1-OFFSET, overall.y2+OFFSET),
                            (overall.x2+OFFSET, overall.y2+OFFSET)])
        continue
    options = set([])
    for point in inflections:
        options.update([(point[0],point[1]),
                        (point[0]-image.size[0],point[1]),
                        (point[0],point[1]-image.size[1]),
                        (point[0]-image.size[0],point[1]-image.size[1])])
    potentials = []
    for option in options:
        testrect = Rectangle(option[0], option[1], option[0]+image.size[0], option[1]+image.size[1])
        if testrect.intersects(rectangles):
            continue
        potentials.append(testrect)
    #print("Overall:", overall)
    smallestgrow = None
    bestrect = None
    shuffle(potentials)
    for pot in potentials:
        newgrow = overall.grow(pot)
        if (smallestgrow is None) or (newgrow.width + newgrow.height < smallestgrow.width + smallestgrow.height):
            if newgrow.ratio > 1.33:
                smallestgrow = newgrow
                bestrect = pot
    bestrect.image = image
    rectangles.append(bestrect)
    #print("Best Match:", bestrect)
    overall = smallestgrow
    #print("New Overall:", overall)
    inflections.update([(bestrect.x1-OFFSET, bestrect.y1-OFFSET),
                        (bestrect.x2+OFFSET, bestrect.y1-OFFSET),
                        (bestrect.x1-OFFSET, bestrect.y2+OFFSET),
                        (bestrect.x2+OFFSET, bestrect.y2+OFFSET)])
    c += 1
    #if c == 1000:
    #    break
 
minx = rectangles[0].x1
miny = rectangles[0].y1
for rectangle in rectangles:
    if minx > rectangle.x1:
        minx = rectangle.x1
    if miny > rectangle.y1:
        miny = rectangle.y1
for rectangle in rectangles:
    rectangle.x1 -= minx
    rectangle.y1 -= miny
    rectangle.x2 -= minx
    rectangle.y2 -= miny
 
overall.x1 -= minx
overall.y1 -= miny
overall.x2 -= minx
overall.y2 -= miny
 
final = Image.new("RGB", (overall.x2,overall.y2), (128,128,128))
 
for rectangle in rectangles:
    final.paste(rectangle.image, (rectangle.x1, rectangle.y1))
 
final.save("/tmp/out.png")