#!/usr/bin/env python

#    Copyright (C) 2004 Paul Harrison
#    This program is free software; you can redistribute it and/or modify
#    it under the terms of the GNU General Public License as published by
#    the Free Software Foundation; either version 2 of the License, or
#    (at your option) any later version.
#
#    This program is distributed in the hope that it will be useful,
#    but WITHOUT ANY WARRANTY; without even the implied warranty of
#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#    GNU General Public License for more details.
#
#    You should have received a copy of the GNU General Public License
#    along with this program; if not, write to the Free Software
#    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

"""  Ghost Diagrams
     
     This program takes sets of tiles that connect together in certain
     ways, and looks for the patterns these tiles imply. The patterns
     are often surprising. 
     

     This software is currently somewhat alpha.
     
  Tile set specification:
  
     A tile set specification is a list of 6-character strings,
     eg 'B Aa  ', 'b  Aa '
     
     Each character represents a tile edge. Letters (abcd, ABCD)
     match with their opposite case. Numbers match with themselves.
     
     A number of extra paramters can also be supplied:
     
         thickness : the thickness of the border
         width : minimum width of diagram
         height : minimum height of diagram
         colors : a list of colors 
            [ background color, edge color, tile 1 color, tile 2 color... ]
            
     eg 'B Aa  ', 'b  Aa ', width=1000, height=1000, thickness=0.5, colors=['#000','#000','#fff','#f00']
     
  Change log:
     
     0.1 -- initial release
     0.2 -- don't segfault on empty tiles
     0.3 -- random keeps trying till it finds something that will grow
            optimization (options_cache)
     0.4 -- assembly algorithm tweaks
            random tile set tweaks
     0.5 -- Patch by Jeff Epler
             - allow window resizing
             - new connection types (33,44,cC,dD)
             - DNA tile set 
            widget to set size of tiles
            no repeated tiles in random
            improvements to assembler
     0.6 -- Use Bezier curves
            Parameters to set width, height, thickness, color
            Save images

  TODO: (blue sky) 3D, third dimension == time
"""

__version__ = '0.6'

import sys, os, random, gtk, pango, string, math

# TODO: properly random algorithm, equivalent to generate and test
#       (is this possible?)

# ========================================================================
# Constants

# Hexagonal connection pattern:
#
#     o o
#   o * o
#   o o
#
# (all points remain on a square grid, but a regular hexagon pattern 
#  can be formed by a simple linear transformation)
connections = [ (-1, 0, 3), (-1, 1, 4), (0, 1, 5), (1, 0, 0), (1, -1, 1), (0, -1, 2) ]
# [ (y, x, index of reverse connection) ]

# What edge type connects with what?
# (a tile is represented as a string of 6 characters representing the 6 edges)
compatabilities = { 
    ' ':' ', 
    'A':'a', 'a':'A', 'B':'b', 'b':'B', 'c':'C', 'C':'c', 'd':'D', 'D':'d',
    '1':'1', '2':'2', '3':'3', '4':'4'
}


# Amount of oversampling in drawing
factor = 3


# Some cool tile sets people have found
catalogue = [
    "'B Aa  ', 'b  Aa '",
    "'  22Aa', ' 22 Aa'",
    "'ab A  ', 'B  C  ', 'B  c  ', 'B  D  ', 'B  d  '",
    "'d D 4 ', 'd  D  ', '44    '",
    "'AaAa  '",
    "'44    ', '11  4 '",
    "'3 3 3 ', '33    '",
    "'1 1 1 ', '2  12 '",
    "' a    ', 'a AA  '",
    "' AAaa ', 'a  A  '",
    "' a A  ', 'Aaa  A'",
    "'a  a  ', ' aAA A'",
    "' a A a', '    A '",
    "'  AA A', 'a a a '",
    "'a  aa ', '    AA'",
    "'A A a ', 'a a   '",
    "'A A a ', 'a  a  '",
    "' a   4', 'a4 44A', '4A    '",
    "'a2  A ', ' a2 A2'",
    "'a 2a2 ', ' A   A', '     2'",
    "'141   ', '4  4  ', '1 1   '",
    "' 22 22', '22    '",
    "' Aaa  ', 'A1A   ', 'a 1AAa'",
    "'aA a2 ', '2A    ', '  2  A'",
    "'  bB1 ', ' b  B '",
    "'BbB 1 ', '     b'",
    "'b  b b', '  BbB '",
    "'aA1   ', '   AA ', 'a  2  '",
    "' a  4 ', ' 4 4  ', '  A441'",
    "'212111', ' 1 2  '",
    "'22222a', '22 A22'",
    "'2 222 ', '2   B2', '  b  2'",
    "' 21221', '   221', '   2 2'",
    "' a a a', '   A A'",
    "' Dd cA', '   d D', '   a C'",
    "'  CCCc', ' 3Ca A', '  3  c', '     c'",
    "' C dDc', '  CC C', '   ccC'",
    "' Aa Cc', '     c', '     C'",
    "' CcDdC', '  cC c', '     C'",
]


default_colors = [ '#ffffff', '#000000', '#ffeedd', '#cc88ff', '#009999', '#ff8800', '#ff0088', '#ff4088', '#ff4040', '#ff00ff', '#40c0ff' ]

default_thickness = 3.0/16

# ========================================================================
# Utility functions

class Point:
    def __init__(self, x,y):
        self.x = x
        self.y = y
    
    def __add__(self, other): return Point(self.x+other.x,self.y+other.y)
    def __sub__(self, other): return Point(self.x-other.x,self.y-other.y)
    def __mul__(self, factor): return Point(self.x*factor, self.y*factor)
    def length(self): return (self.y*self.y + self.x*self.x) ** 0.5
    def int_xy(self): return int(self.x+0.5), int(self.y+0.5)
    def left90(self): return Point(-self.y, self.x)


def bezier(a,b,c,d):
    result = [ ]
    n = 12
    for i in xrange(1,n):
        u = float(i) / n
        result.append(
            a * ((1-u)*(1-u)*(1-u)) +
            b * (3*u*(1-u)*(1-u)) +
            c * (3*u*u*(1-u)) +
            d * (u*u*u)
        )
    return result


def normalize(form):
    best = form
    for i in xrange(len(form)-1):
        form = form[1:] + form[0]
        if form < best: best = form
    return best


def interpret_specification( *forms, **kwargs ):
    if len(forms) < 1: raise 'error'
    
    for item in forms:
        if type(item) != type('') or len(item) != 6:
            raise 'error'
        for edge in item:
            if edge not in compatabilities:
                raise 'error'
                
    colors = kwargs.get('colors', [ ])
    colors += default_colors[len(colors):]
    
    thickness = kwargs.get('thickness', default_thickness)
    width = kwargs.get('width', -1)
    height = kwargs.get('height', -1)

    return forms, colors, thickness, width, height

# ========================================================================


class Assembler:
    def __init__(self, connections, compatabilities, forms, point_set):
        self.connections = connections    # [(y,x,index of reverse connection)]
        self.compatabilities = compatabilities    # { edge-char -> edge-char }
        self.point_set = point_set   # (y,x) -> True

        self.basic_forms = forms   # ['edge types']
        self.forms = [ ]   # ['edge types']
        self.form_id = [ ]   # [original form number]
        
        for id, form in enumerate(forms):
            current = form
            for i in xrange(len(self.connections)):
                if current not in self.forms:
                    self.forms.append(current)
                    self.form_id.append(id)
                current = current[1:] + current[0]

        self.tiles = { }   # (y,x) -> form number
        
        self.dirty = { }   # (y,x) -> True   -- Possible sites for adding tiles 
        
        self.options_cache = { }   # pattern -> [form_ids]
        
        self.total_y = 0
        self.total_x = 0
        
        self.put(0,0,0)

    def put(self, y,x, value):
        if (y,x) in self.tiles:
            self.total_y -= y
            self.total_x -= x
            
        if value == None:
            if (y,x) not in self.tiles: return
            del self.tiles[(y,x)]
            self.dirty[(y,x)] = True
        else:
            self.tiles[(y,x)] = value
            self.total_y += y
            self.total_x += x
        
        for oy, ox, opposite in self.connections:
            y1 = y + oy
            x1 = x + ox
            if (y1,x1) not in self.tiles and (y1, x1) in self.point_set:
                self.dirty[(y1,x1)] = True
    
    def get_pattern(self, y,x):
        result = ''
        for oy, ox, opposite in self.connections:
            y1 = y + oy
            x1 = x + ox
            if self.tiles.has_key((y1,x1)):
                result += self.compatabilities[self.forms[self.tiles[(y1,x1)]][opposite]]
            else:
                result += '.'
        
        return result

    def fit_ok(self, pattern,form_number):
        form = self.forms[form_number]
        for i in xrange(len(self.connections)):
            if pattern[i] != '.' and pattern[i] != form[i]:
                return False
               
        return True
    
    def options(self, y,x):
        pattern = self.get_pattern(y,x)
        if pattern in self.options_cache:
            return self.options_cache[pattern]
        
        result = [ ]
        for i in xrange(len(self.forms)):
            if self.fit_ok(pattern,i):
                result.append(i)
                
        self.options_cache[pattern] = result
        return result
        
    def any_links_to(self, y,x):
        for oy, ox, opposite in self.connections:
            y1 = y + oy
            x1 = x + ox
            if (y1, x1) in self.tiles:
                if self.forms[self.tiles[(y1,x1)]][opposite] != ' ':
                    return True
        return False

    def garbage_collect(self):
        remaining_tiles = self.tiles.copy()
        best_set = { }
        while remaining_tiles:
            queue = [ remaining_tiles.iterkeys().next() ]
            set = { }
            while queue:
                y,x = queue.pop(0)
                if (y,x) not in remaining_tiles: continue
                form_number = remaining_tiles[(y,x)]
                set[(y,x)] = True
                del remaining_tiles[(y,x)]

                for i in xrange(len(self.connections)):
                    if self.forms[form_number][i] != ' ':
                        queue.append( (y+self.connections[i][0],x+self.connections[i][1]) )
            
            if len(set) > len(best_set):
                best_set = set

        for y, x in self.tiles.keys():
            if (y,x) not in best_set:
                self.put(y,x,None)
    
    def nuke(self, y,x,n):
        queue = [ (y,x) ]
        while queue and n:
            y,x = queue.pop(0)
            
            if (y,x) in self.tiles:
                self.put(y,x,None)
                n -= 1

            temp = self.connections[:]
            random.shuffle(temp)
            for oy, ox, opposite in temp:
                yy = y + oy
                xx = x + ox
                if (yy,xx) in self.tiles:
                    if self.forms[self.tiles[(yy,xx)]][opposite] != ' ':
                        queue.append((yy,xx))

    def iterate(self):
        mid_y = float(self.total_y) / len(self.tiles)
        mid_x = float(self.total_x) / len(self.tiles)
        
        point_list = [ ]
        for y, x in self.dirty.keys():
            if (y,x) in self.tiles or not self.any_links_to(y,x): 
                del self.dirty[(y,x)]
                continue
            yy = y - mid_y
            xx = x - mid_x
            sorter = ((yy*2)**2+(xx*2+yy)**2)**0.5 #+ random.random()*4
            point_list.append( (sorter,y,x) )
            
        point_list.sort()
        
        best = None        

        for sorter, y, x in point_list: 
            options = self.options(y,x)
            if len(options) < 2:
                score = 0
            else:
                score = 1
                
            if best == None or score < best_score:
                best = options
                best_score = score
                best_x = x
                best_y = y
                if score == 0: break

        if best == None: return False        
        
        if len(best) > 0:
            self.put(best_y,best_x,random.choice(best))
        elif len(self.tiles) > 1:
            # Shape of distribution
            autism = 1.0 # 1.0 == autistic, 2.0 == normal
            
            # Overall level
            adhd = 2.5 # Lower == more adhd
            
            # (garbage collection confounds these factors slightly)
            
            n = 1
            while n < len(self.tiles)-1 and random.random() < ( n/(n+autism) )**adhd:
                n += 1
            
            self.nuke(best_y,best_x,n)        
            self.garbage_collect()

        return True




# ========================================================================


class Interface:
    def __init__(self):
        self.iteration = 0
        self.idle_enabled = False

        self.drawing = gtk.DrawingArea()
        self.drawing.unset_flags(gtk.DOUBLE_BUFFERED)
        self.drawing.connect('expose-event', self.on_expose)
        self.drawing.connect('size-allocate', self.on_size)
        
        scroller = gtk.ScrolledWindow()
        scroller.set_policy(gtk.POLICY_AUTOMATIC, gtk.POLICY_AUTOMATIC)
        scroller.add_with_viewport(self.drawing)
    
        self.combo = gtk.Combo()
        for item in catalogue:
            item = gtk.ListItem(item)
            item.get_children()[0].modify_font(pango.FontDescription("mono"))
            item.show()
            self.combo.list.append_items([item])
        self.combo.list.connect('select-child', lambda widget, child: self.reset())
        self.combo.entry.modify_font(pango.FontDescription("mono"))
        
        scale_label = gtk.Label(' Size: ')
        scale = gtk.SpinButton()
        scale.set_digits(1)
        scale.set_increments(1.0,1.0)
        scale.set_range(3.0, 50.0)
        scale.set_value(8.0)
        scale.connect('value-changed', self.on_set_scale)

        random_button = gtk.Button(' Random ')
        random_button.connect('clicked', lambda widget: self.random())
        
        reset = gtk.Button(' Restart ')
        reset.connect('clicked', lambda widget: self.reset())

        save = gtk.Button(' Save image... ')
        save.connect('clicked', self.on_save)

        hbox = gtk.HBox(False,5)
        hbox.set_border_width(3)
        hbox.pack_end(save, False,False,0)
        hbox.pack_end(reset, False,False,0)
        hbox.pack_end(random_button, False,False,0)
        hbox.pack_end(scale, False,False,0)
        hbox.pack_end(scale_label, False,False,0)

        vbox = gtk.VBox(False,5)
        vbox.pack_start(self.combo, False,False,0)
        vbox.pack_start(hbox, False,False,0)
        vbox.pack_start(scroller, True,True,0)

        self.window = gtk.Window()
        self.window.set_default_size(600,650)
        self.window.set_title('Ghost Diagrams')
        self.window.add(vbox)
        self.window.connect('destroy', lambda widget: gtk.main_quit())

        self.drawing.realize()
        
        self.gc = gtk.gdk.GC(self.drawing.window)

        self.pixbuf_ready = False
        self.render_iterator = None
        
        self.randomizing = False
        
        self.set_scale(scale.get_value())
    
    def on_size(self, widget, event):
        self.pixbuf_ready = False
        
        self.width = event.width * factor
        self.height = event.height * factor
        self.pixmap = gtk.gdk.Pixmap(self.drawing.window, self.width,self.height)

        self.pixbuf = gtk.gdk.Pixbuf(gtk.gdk.COLORSPACE_RGB, False, 8, self.width,self.height)
        self.scaled_pixbuf = gtk.gdk.Pixbuf(gtk.gdk.COLORSPACE_RGB, False, 8, 
                                            self.width/factor,self.height/factor)
        self.reset()

    def on_set_scale(self, widget):
        self.set_scale(widget.get_value())
        self.reset()

    def set_scale(self, value):
        self.scale = value * factor

    def reset(self):
        try:
            forms, colors, thickness, width, height = \
                eval('interpret_specification('+self.combo.entry.get_text()+')')
        except:
            forms, colors, thickness, width, height = \
                interpret_specification( '      ')

        colormap = self.drawing.get_colormap()
        self.colors = [ colormap.alloc_color(item) for item in colors ]
        
        self.gc.set_line_attributes(max(factor,int(self.scale * thickness)),
             gtk.gdk.LINE_SOLID, gtk.gdk.CAP_ROUND, gtk.gdk.JOIN_ROUND)

        point_set = { }
        yr = int( self.height/self.scale / (4*(3**0.5)) +2)
        xr = int( self.width/self.scale / (4*2) +2)
        for y in xrange(-yr,yr+1):
            for x in xrange(-xr-(y+1)/2,xr+1-y/2):
                point_set[(y,x)] = True     

        self.assembler = Assembler(connections, compatabilities, forms, point_set)
        self.pixbuf_ready = False
        self.render_iterator = None
        self.randomizing = False
        self.iteration = 0
        self.drawing.queue_draw()
        if not self.idle_enabled:
            gtk.idle_add(self.idle)
            self.idle_enabled = True
            
        self.drawing.set_size_request(width, height)
            
    def run(self):
        self.window.show_all()
        gtk.main()

    def idle(self):
        if self.render_iterator:
            try:
                self.render_iterator.next()
            except StopIteration:
                self.render_iterator = None
            return True
        
        if not self.idle_enabled: 
            return False
        
        self.idle_enabled = self.assembler.iterate()

        self.iteration += 1
        
        if self.randomizing and \
           (self.iteration == 200 or not self.idle_enabled):
            self.randomizing = False
            
            forms_present = { }
            for item in self.assembler.tiles.values():
                forms_present[self.assembler.form_id[item]] = 1
            
            if len(self.assembler.tiles) < 16 or \
               len(forms_present) < len(self.assembler.basic_forms):
                self.idle_enabled = False
                self.random(True)
                return False
        
        if self.iteration % (75*factor) == 0 or not self.idle_enabled:
            self.render_iterator = self.make_render_iter()

        return True

    def make_render_iter(self):
        yield None
        
        self.gc.set_rgb_fg_color(self.colors[0])
        self.pixmap.draw_rectangle(self.gc, True, 0,0,self.width,self.height)
    
        def pos(x,y):
            return Point(x*self.scale*2+y*self.scale+self.width/2, 
                         y*(3**0.5)*self.scale+self.height/2)

        for (y,x), form_number in self.assembler.tiles.items():
            middle = pos(x*2,y*2)
        
            result = [ ]
            for i in xrange(len(self.assembler.connections)):
                yy, xx = self.assembler.connections[i][:2]
                symbol = self.assembler.forms[form_number][i]
                if symbol == ' ': continue
            
                edge = pos(x*2+xx,y*2+yy)
                out = edge - middle
                left = out.left90()
        
                if symbol in 'aA1':
                    r = 0.4
                elif symbol in 'bB2': 
                    r = 0.3
                elif symbol in 'cC3':
                    r = 0.225
                else:
                    r = 0.15
                        
                if symbol in 'ABCD': 
                    poke = 0.3 #r
                elif symbol in 'abcd': 
                    poke = -0.3 #-r
                else:
                    poke = 0.0

                points = [
                    edge + left*-r,
                    edge + out*poke,
                    edge + left*r,
                ]
                result.append( (out * (1.0/out.length()), points, 0.5)) 
                # Note: set constant to ~0.35 for old-style circular look

            if len(result) == 1:
                 point = middle-result[0][0]*(self.scale*0.7)
                 result.append( (result[0][0].left90()*-1.0, [point], 0.8) )
                 result.append( (result[0][0].left90(), [point], 0.8) )

            poly = [ ]
            for i in xrange(len(result)):
                a = result[i-1][1][-1]
                d = result[i][1][0]
                length = (d-a).length() * ((result[i][2]+result[i-1][2])*0.5)
                b = a - result[i-1][0]*length
                c = d - result[i][0]*length
                poly.extend(bezier(a,b,c,d))                 
                poly.extend(result[i][1])
        
            poly = [ point.int_xy() for point in poly ]

            if len(poly) > 0:
                color = self.assembler.form_id[form_number] % (len(self.colors)-2) + 2  
                self.gc.set_rgb_fg_color(self.colors[color])
                self.pixmap.draw_polygon(self.gc, True, poly)
                self.gc.set_rgb_fg_color(self.colors[1])
                self.pixmap.draw_polygon(self.gc, False, poly)

            yield None
            
        self.pixbuf.get_from_drawable(self.pixmap, self.pixmap.get_colormap(), 
                                      0,0,0,0, self.width,self.height)
                                      
        yield None
            
        self.pixbuf.scale(self.scaled_pixbuf, 0,0,self.width/factor,self.height/factor,
              0,0,1.0/factor,1.0/factor,gtk.gdk.INTERP_BILINEAR)
        
        self.pixbuf_ready = True
        self.drawing.queue_draw()
    
    def on_expose(self, widget, event):
        if self.pixbuf_ready:
            self.drawing.window.draw_pixbuf(self.gc, self.scaled_pixbuf, 0,0,0,0,-1,-1)
        else:
            self.gc.set_rgb_fg_color(self.colors[0])
            self.drawing.window.draw_rectangle(self.gc, True, 0,0,self.width/factor,self.height/factor)

    def random(self, same_form=False):
        if same_form:
            n = len(self.assembler.basic_forms)
        else:
            n = random.randrange(2,5)
            
        while True:
            edge_counts = [ random.choice([1,2,3,4,5,6]) 
                            for i in xrange(n) ]
            edge_counts.sort()
            edge_counts.reverse()
            if edge_counts[0] != 1: break
        
        while True:
            try:
                result = [ ]
                previous = '1234' + 'aAbBcCdD' * 3
                for edge_count in edge_counts:
                    item = [' ']*(6-edge_count)
                    for j in xrange(edge_count): 
                        selection = random.choice(previous)
                        previous += compatabilities[selection]*12
                        item.append(selection)
                
                    random.shuffle(item)
                    item = normalize(string.join(item,''))
                    if item in result: raise "repeat"
                    result.append(item)
            
                all = string.join(result,'')
                for a, b in compatabilities.items():
                    if a in all and b not in all: raise "repeat"
        
                break
            except "repeat":
                pass
        
        self.combo.entry.set_text(repr(result)[1:-1])
        self.reset()
        self.randomizing = True

    def on_save(self, widget):
        selecter = gtk.FileSelection('Save image')
        selecter.set_filename('diagram.png')
        
        def on_ok(widget):
            filename = selecter.get_filename()
            selecter.destroy()
            
            if self.pixbuf_ready:
                self.scaled_pixbuf.save(filename, 'png')
            else:
                pass
                # TODO: show error
            
        def on_cancel(widget):
            selecter.destroy()
            
        selecter.ok_button.connect('clicked', on_ok)
        selecter.cancel_button.connect('clicked', on_ok)
        
        selecter.show()



if __name__ == '__main__':
    Interface().run()