#!/usr/bin/python

# Basic Python program to render animations for Wikipedia floodfill
# article (not a general floodfill example, very far from a shining example).

# This example uses the four-way floodfill algorithm, and generates 
# example animations using both a stack and a queue as intermediate
# storage schemes.

# Requirements:
# * python
# * Python Imaging Library (PIL)
# * ImageMagick (used to compile intermediate images to GIF animations)
# 
# The os.system() calls are written for unix; changing them for windows
# should be trivial

# Copyright (C) 2008 Finlay McWalter. 
# Licence: your choice from GFDL, GPLv2, GPLv3, CC-by-SA2.0
 

import os, Image, ImageColor, ImageDraw
from collections import deque

def floodfill(img, 
              (startx, starty), 
              targetcolour, 
              newcolour, 
              dumpEveryX=70,
              pattern=None,
              useQueue=False,
              startIndex=0):
    
    if useQueue:
        workpile = deque();
        getpoint = workpile.popleft
    else:
        workpile = []
        getpoint = workpile.pop

    max=0
    count=0

    workpile.append((startx,starty))
    while len(workpile)> 0:
        x,y=getpoint()
        
        if len(workpile)> max: 
            max=len(workpile)

        if img.getpixel((x,y)) == targetcolour:
            img.putpixel((x,y), newcolour)
            
            # every few pixels drawn, dump an image showing our progress
            count += 1
            if (count%dumpEveryX)==0 and pattern != None:
                img.save(pattern %(startIndex+count))

            # this demo code doesn't handle the case where we get to the edge
            if img.getpixel((x-1,y))== targetcolour: workpile.append((x-1,y))
            if img.getpixel((x+1,y))== targetcolour: workpile.append((x+1,y))
            if img.getpixel((x,y-1))== targetcolour: workpile.append((x,y-1))
            if img.getpixel((x,y+1))== targetcolour: workpile.append((x,y+1))

    print '    done with count %d, max %d' % (count,max)
    return count

def make_floodfill_example(filename, use_queue):
    print 'making image '+filename
    print '  removing old files'
    os.system('rm -f out*.png ' +filename )

    i = Image.new('RGB', (200,200), 'white')

    # draw a rough ying-yang
    draw = ImageDraw.Draw(i)
    draw.ellipse((30,30,170,170), outline='black')
    draw.arc((65,100,135,170), 90,270, fill='black')
    draw.arc((64,30,134,100), 270,90, fill='black')
    draw.ellipse((80,45,120,85), outline='black')
    draw.ellipse((80,115,120,155), outline='black')
    del draw

    print '  filling'
    redcount = floodfill(i, 
                         (100, 90), 
                         (255,255,255), #white
                         (255,0,0), #red
                         useQueue = use_queue,
                         pattern='out_%05d.png')

    print '  filling'
    bluecount = floodfill(i,
                          (110,110),
                          (255,255,255), # white
                          (0,0,255), # blue
                          useQueue = use_queue,
                          pattern='out_%05d.png',
                          startIndex=redcount)

    # push some extra frames of animation so we can see the finished fill
    for x in range(redcount+bluecount,redcount+bluecount+20):
        i.save('out_%05d.png' %(x))    

    print '  converting to animated GIF - this may take several minutes'
    os.system ('convert -loop 0 out*.png '+filename)

# draw one example image using a FIFO as the means of storing points,
# and another using a LIFO.
make_floodfill_example('wfm_floodfill_animation_queue.gif', True)
make_floodfill_example('wfm_floodfill_animation_stack.gif', False)
print 'done'