# coding: utf-8

import random
import re
import sys, os, glob
from PIL import Image, ImageFont, ImageDraw

class elem:
	def __init__( self, grpCnt, dataCnt, rngCnt, grpRng, data ):
		self.grpCnt = grpCnt
		self.dataCnt = dataCnt
		self.rngCnt = rngCnt
		self.grpRng = grpRng
		self.data = data

def analysis( store ):
	
	dataCntBuf = [ 1 ] * store.dataCnt
	rangeBuf = [ [ 0 ] * store.dataCnt for idx in range( store.dataCnt ) ]
	
	for idx in range( store.dataCnt ):
		store.grpRng[ idx ] = idx
		ndx = idx + 1
		while ndx < store.dataCnt:
			rangeBuf[ idx ][ ndx ] = getRange( store, idx, ndx )
			ndx += 1
	
	for idx in range( store.dataCnt ):
		ndx = idx + 1
		while ndx < store.dataCnt:
			rangeBuf[ ndx ][ idx ] = rangeBuf[ idx ][ ndx ]
			ndx += 1
	
	loopCnt = store.dataCnt
	while loopCnt > store.grpCnt:
		curRange = getMinimumRange( store, rangeBuf )
		for idx in range( store.dataCnt ):
			if store.grpRng[ idx ] == idx :
				ndx = idx + 1
				while ndx < store.dataCnt:
					if store.grpRng[ ndx ] == ndx :
						if idx != curRange[ "to" ] and ndx != curRange[ "to" ] :
							if idx == curRange[ "from" ] :
								rangeBuf[ idx ][ ndx ] = analyticRange({
									"dest1" : rangeBuf[ curRange[ "from" ] ][ ndx ],
									"dest2" : rangeBuf[ curRange[ "to" ] ][ ndx ],
									"dest3" : rangeBuf[ curRange[ "from" ] ][ curRange[ "to" ] ],
									"size1" : dataCntBuf[ curRange[ "from" ] ],
									"size2" : dataCntBuf[ curRange[ "to" ] ],
									"size3" : dataCntBuf[ ndx ]
								})
								rangeBuf[ ndx ][ idx ] = rangeBuf[ idx ][ ndx ]
							elif ndx == curRange[ "to" ] :
								rangeBuf[ idx ][ ndx ] = analyticRange({
									"dest1" : rangeBuf[ idx ][ curRange[ "from" ] ],
									"dest2" : rangeBuf[ idx ][ curRange[ "to" ] ],
									"dest3" : rangeBuf[curRange[ "from" ] ][ curRange[ "to" ] ],
									"size1" : dataCntBuf[ curRange[ "from" ] ],
									"size2" : dataCntBuf[ curRange[ "to" ] ],
									"size3" : dataCntBuf[ ndx ]
								});
								rangeBuf[ ndx ][ idx ] = rangeBuf[ idx ][ ndx ]
					ndx += 1
		dataCntBuf[ curRange[ "from" ] ] += dataCntBuf[ curRange[ "to" ] ]
		for idx in range( store.dataCnt ):
			if store.grpRng[ idx ] == curRange[ "to" ] : 
				store.grpRng[ idx ] = curRange[ "from" ]
		loopCnt -= 1
	
	grpidx = 1
	retCluster = []
	while( grpidx <= store.grpCnt ):
		curGrp = []
		grpndx = -1;
		idx = 0
		while ( idx < store.dataCnt and grpndx < 0 ) :
			if store.grpRng[ idx ] >= 0 :
				grpndx = store.grpRng[ idx ]
			idx += 1
		
		idx = 0
		while ( idx < store.dataCnt ) :
			if store.grpRng[ idx ] == grpndx :
				ndx = 0
				while ( ndx < store.rngCnt ):
					curGrp.append( ( store.data[ idx ][ ndx ], idx ) )
					ndx += 1
				store.grpRng[ idx ] = -1;
			idx += 1
		grpidx+=1
		retCluster.append( curGrp )
	
	return retCluster

def getRange( store, _from, _to ):
	buf = 0
	retRange = 0
	for idx in range( store.rngCnt ):
		buf = store.data[ _from ][ idx ] - store.data[ _to ][ idx ]
		retRange = retRange + ( buf * buf )
	return retRange


def getMinimumRange( store, rangeBuf ) :
	curRange = { "from" : 0, "to" : 0 }
	min = -1.0
	for idx in range( store.dataCnt ):
		if store.grpRng[ idx ] == idx :
			ndx = idx + 1
			while ndx < store.dataCnt:
				if store.grpRng[ ndx ] == ndx :
					if min < 0.0 or rangeBuf[ idx ][ ndx ] < min :
						min = rangeBuf[ idx ][ ndx ]
						curRange[ "from" ] = idx
						curRange[ "to" ] = ndx
				ndx += 1
	
	return curRange


def analyticRange( relation ) :
	range = (
		( relation[ "size1" ] + relation[ "size3" ] ) * relation[ "dest1" ] +
		( relation[ "size2" ] + relation[ "size3" ] ) * relation[ "dest2" ] -
		relation[ "size3" ] * relation[ "dest3" ]
	) / ( relation[ "size1" ] + relation[ "size2" ] + relation[ "size3" ] )
	return range;

def main():
	paletteSize = 5
	paletteFile = open('palette.txt', 'w')
	paletteFileIdx = 0
	fileList = glob.glob('*.*')
	for imgFile in fileList:
		if re.compile( "\.jpg$|\.jpeg$", re.IGNORECASE ).search( imgFile ) == None :
			continue
		print imgFile
		image = Image.open( imgFile )
		result = image.convert( 'P', palette=Image.ADAPTIVE, colors=255 )
		palette = result.getpalette()
		hstgrm = [ [ idx ] for idx in result.histogram() ]
		count = len( result.histogram() ) -1
		dataStore = elem( paletteSize, count, 1, [ 0 ] * count, hstgrm )
		clst = analysis( dataStore )
		maxColorPalette = []
		minColorPalette = []
		rndColorPalette = []
		 
		for idx in range( paletteSize ):
			maxColorPalette.append( 
				( 
					palette[ ( max(clst[ idx ])[ 1 ] * 3 ) ], 
					palette[ ( max(clst[ idx ])[ 1 ] * 3 ) + 1 ], 
					palette[ ( max(clst[ idx ])[ 1 ] * 3 ) + 2 ]
				) 
			)
			minColorPalette.append( 
				( 
					palette[ ( min(clst[ idx ])[ 1 ] * 3 ) ], 
					palette[ ( min(clst[ idx ])[ 1 ] * 3 ) + 1 ], 
					palette[ ( min(clst[ idx ])[ 1 ] * 3 ) + 2 ]
				) 
			)
			rndColorPalette.append( 
				( 
					palette[ ( clst[ idx ][int( random.random() * len( clst[ idx ] ) )][ 1 ] * 3 ) ], 
					palette[ ( clst[ idx ][int( random.random() * len( clst[ idx ] ) )][ 1 ] * 3 ) + 1 ], 
					palette[ ( clst[ idx ][int( random.random() * len( clst[ idx ] ) )][ 1 ] * 3 ) + 2 ]
				) 
			)
		ctgry = [ "max value in histogram of clusters", "min value in histogram of clusters", "random per clusters"]
		for palette in [ maxColorPalette, minColorPalette, rndColorPalette ]:
			palette.sort()
			palette.reverse()
			paletteFile.write( str( palette ) + " // " + ctgry[ paletteFileIdx%3 ] + " [ " + imgFile + " to " + '%(#)04d'%{'#':paletteFileIdx} + ".png ]\n" )
			paletteImg = Image.new( "RGB", ( paletteSize * 20, int( paletteSize * 20 * 5 / 8 ) ), ( 0xff, 0xff, 0xff ) )
			draw = ImageDraw.Draw( paletteImg )
			for idx in range( paletteSize ):
				draw.rectangle( 
					( idx * 20, 0, idx * 20 + 20, int( paletteSize * 20 * 5 / 8 ) ), 
					outline = ( 
						palette[ idx ][ 0 ], 
						palette[ idx ][ 1 ], 
						palette[ idx ][ 2 ] 
					), 
					fill = ( 
						palette[ idx ][ 0 ], 
						palette[ idx ][ 1 ], 
						palette[ idx ][ 2 ] 
					)
				)
			paletteImg.save( '%(#)04d'%{'#':paletteFileIdx} + ".png", "png" )
			paletteFileIdx += 1
	paletteFile.close()

if __name__ == '__main__':
	main()