# version 1.1.4
# modification by Thomas SG

from __future__ import division
from CvPythonExtensions import *
from copy import copy, deepcopy
from sys import maxint
from math import *

gc = CyGlobalContext()
game = gc.getGame()
dice = game.getSorenRand()

DMAX_EARTH = 20038	# max possible distance between two points on earth (WGS-84)

CoordinatesDictionary = {}

def InitCoordinatesDictionary():
	coords = []
	global CoordinatesDictionary
	coords.append(GeographicalCoordinate("CIVILIZATION_AMERICA", 38.895, -77.037))
	coords.append(GeographicalCoordinate("CIVILIZATION_ARABIA", 21.423, 39.826))
	coords.append(GeographicalCoordinate("CIVILIZATION_AUSTRIA", 48.208, 16.373))
	coords.append(GeographicalCoordinate("CIVILIZATION_AZTEC", 19.419, -99.146))
	coords.append(GeographicalCoordinate("CIVILIZATION_BABYLON", 32.536, 44.421))
	coords.append(GeographicalCoordinate("CIVILIZATION_BERBER", 36.700, 3.217))
	coords.append(GeographicalCoordinate("CIVILIZATION_BRAZIL", -15.780, -47.928))
	coords.append(GeographicalCoordinate("CIVILIZATION_BYZANTIUM", 41.009, 28.976))
	coords.append(GeographicalCoordinate("CIVILIZATION_CARIBBEAN", 23.123, -82.386))
	coords.append(GeographicalCoordinate("CIVILIZATION_CARTHAGE", 36.887, 10.315))
	coords.append(GeographicalCoordinate("CIVILIZATION_CELT", 46.923, 4.038))
	coords.append(GeographicalCoordinate("CIVILIZATION_CHINA", 39.929, 116.388))
	coords.append(GeographicalCoordinate("CIVILIZATION_EGYPT", 25.721, 32.610))
	coords.append(GeographicalCoordinate("CIVILIZATION_ENGLAND", 51.508, -0.128))
	coords.append(GeographicalCoordinate("CIVILIZATION_ETHIOPIA", 14.117, 38.733))
	coords.append(GeographicalCoordinate("CIVILIZATION_FRANCE", 48.867, 2.333))
	coords.append(GeographicalCoordinate("CIVILIZATION_GERMANY", 52.517, 13.417))
	coords.append(GeographicalCoordinate("CIVILIZATION_GREECE", 37.967, 23.717))
	coords.append(GeographicalCoordinate("CIVILIZATION_HOLY_ROMAN", 50.775, 6.084))
	coords.append(GeographicalCoordinate("CIVILIZATION_HUNGARY", 47.500, 19.050))
	coords.append(GeographicalCoordinate("CIVILIZATION_INCA", -13.508, -71.972))
	coords.append(GeographicalCoordinate("CIVILIZATION_INDIA", 28.667, 77.217))
	coords.append(GeographicalCoordinate("CIVILIZATION_INDONESIA", -6.2, 106.8))
	coords.append(GeographicalCoordinate("CIVILIZATION_ISRAEL", 31.779, 35.224))
	coords.append(GeographicalCoordinate("CIVILIZATION_JAPAN", 35.017, 135.767))
	coords.append(GeographicalCoordinate("CIVILIZATION_KHMER", 13.424, 103.856))
	coords.append(GeographicalCoordinate("CIVILIZATION_KOREA", 37.566, 126.978))
	coords.append(GeographicalCoordinate("CIVILIZATION_MALI", 16.773, -3.007))
	coords.append(GeographicalCoordinate("CIVILIZATION_MAYA", 17.222, -89.623))
	coords.append(GeographicalCoordinate("CIVILIZATION_MONGOL", 47.198, 102.821))
	coords.append(GeographicalCoordinate("CIVILIZATION_NATIVE_AMERICA", 38.659, -90.061))
	coords.append(GeographicalCoordinate("CIVILIZATION_NETHERLANDS", 52.371, 4.897))
	coords.append(GeographicalCoordinate("CIVILIZATION_OTTOMAN", 41.012, 28.976))
	coords.append(GeographicalCoordinate("CIVILIZATION_PERSIA", 29.934, 52.891))
	coords.append(GeographicalCoordinate("CIVILIZATION_POLAND", 52.217, 21.033))
	coords.append(GeographicalCoordinate("CIVILIZATION_POLYNESIA", -41.283, 174.766))
	coords.append(GeographicalCoordinate("CIVILIZATION_PORTUGAL", 38.717, -9.167))
	coords.append(GeographicalCoordinate("CIVILIZATION_ROME", 41.883, 12.483))
	coords.append(GeographicalCoordinate("CIVILIZATION_RUSSIA", 55.752, 37.632))
	coords.append(GeographicalCoordinate("CIVILIZATION_SCOTLAND", 55.950, -3.22))
	coords.append(GeographicalCoordinate("CIVILIZATION_SCYTHS", 55.8, 65.5))
	coords.append(GeographicalCoordinate("CIVILIZATION_SPAIN", 40.413, -3.704))
	coords.append(GeographicalCoordinate("CIVILIZATION_SUMERIA", 31.322, 45.636))
	coords.append(GeographicalCoordinate("CIVILIZATION_TIBET", 29.653, 91.131))
	coords.append(GeographicalCoordinate("CIVILIZATION_VIKING", 63.420, 10.393))
	coords.append(GeographicalCoordinate("CIVILIZATION_ZULU", -28.317, 31.417))
	CoordinatesDictionary = dict(zip([coord.getCivilization() for coord in coords], coords))


def assignCulturallyLinkedStarts(): 
	#print "CultureLink option enabled."
	InitCoordinatesDictionary()
	pCultureLink = CultureLink()
	pCultureLink.assignStartingPlots()
	del pCultureLink
	return None


class CultureLink:

	pStartingPlotsList = []
	pRWCoordinatesList = []

	def __init__(self):
		CultureLink.pStartingPlotsList = [] 
		self.__initStartingPlotsList()
		CultureLink.pRWCoordinatesList = [] 
		self.__initRWCoordinatesList()

	def __initStartingPlotsList(self):
		iNumPlayers = game.countCivPlayersEverAlive()
		for iPlayer in range(iNumPlayers):
			pPlayer = gc.getPlayer(iPlayer)
			pStartingPlot = pPlayer.getStartingPlot()
			CultureLink.pStartingPlotsList.append(pStartingPlot)

	def __initRWCoordinatesList(self):
		iNumPlayers = game.countCivPlayersEverAlive()
		for iPlayer in range(iNumPlayers):
			pPlayer = gc.getPlayer(iPlayer)
			eCivilization = pPlayer.getCivilizationType()
			pCoordinate = CoordinatesDictionary[eCivilization]
			CultureLink.pRWCoordinatesList.append(pCoordinate)

	def assignStartingPlots(self):
		
		iNumPlayers = game.countCivPlayersEverAlive()
		iPlayersList = range(iNumPlayers)
		
		iSPDistanceMatrix = ScaleMatrix(self.__computeSPDistanceMatrix())
		#print FormatMatrix(iSPDistanceMatrix, "Starting Plots Distance Matrix:")
		iRWDistanceMatrix = ScaleMatrix(self.__computeRWDistanceMatrix())
		#print FormatMatrix(iRWDistanceMatrix, "Real World Distance Matrix:")
		
		def runBruteForceSearch(permutation = [], depth = 0, best = (None, 'inf')):
			if depth < iNumPlayers:
				for i in iPlayersList:
					if not i in permutation: 
						permutation.append(i)
						best = runBruteForceSearch(permutation, depth + 1, best)
						permutation.pop()
			else:
				error = evaluatePermutation(permutation)
				if error < best[1]:
					best = (copy(permutation), error)
					#print "%s %.4f" % (best[0], best[1])
			return best
		
		def runAntColonyOptimization():
			# constants
			# NUM_RUNS = 50
			# NUM_ANTS = 250
			# NUM_BEST_ANTS = 5
			# PHEROMON_UPDATE = 0.025
			NUM_ANTS = iNumPlayers
			NUM_BEST_ANTS = int(iNumPlayers / 10)
			NUM_RUNS = iNumPlayers * 25
			PHEROMON_UPDATE = 0.34 / iNumPlayers
			# the best ant (permutation, error) we know
			TheBestAnt = (None, 'inf')
			# uniformly distributed pheromon at the beginning
			fPheromonMatrix = SquareMatrix(iNumPlayers, 1 / iNumPlayers)
			# the actual ACO:
			for iRun in xrange(NUM_RUNS):
				ants = {}
				# get some random ants:
				for i in xrange(NUM_ANTS):
					permutation = randomList(iPlayersList, fPheromonMatrix)
					error = evaluatePermutation(permutation)
					ants[error] = permutation
				bestants = [] 
				# get the x best ants (smallest error):
				for error in sorted(ants)[:NUM_BEST_ANTS]:
					ant = (ants[error], error)
					bestants.append(ant)
				# check if we have a new TheBestAnt:
				if bestants[0][1] < TheBestAnt[1]:
					TheBestAnt = bestants[0]
					#print "%s %.8f (%d)" % (TheBestAnt[0], TheBestAnt[1], iRun)
				# let the x best ants update the pheromon matrix:
				for i, pos in enumerate(fPheromonMatrix):
					for ant in bestants:
						value = ant[0][i]
						fPheromonMatrix[i][value] = pos[value] + PHEROMON_UPDATE
					# total probability for each pos has to be one:
					fPheromonMatrix[i] = ScaleList(fPheromonMatrix[i])
			return TheBestAnt
		
		def evaluatePermutation(permutation):
			fPermRWMatrix = []
			for i in permutation:
				row = [iRWDistanceMatrix[i][j] for j in permutation]
				fPermRWMatrix.append(row)
			fError = 0.0
			for i in iPlayersList:
				for j in iPlayersList:
					if i > j:
						# square to make it more robust against small errors
						fError += abs(iSPDistanceMatrix[i][j] - fPermRWMatrix[i][j]) ** 1.3
			return fError
		
		if iNumPlayers <= 9: # brute force 
			iBestPermutation = runBruteForceSearch()[0]
		else: # ants where brute force is impossible
			iBestPermutation = runAntColonyOptimization()[0]
			
		# assign the best found permutation:
		pStartingPlots = CultureLink.pStartingPlotsList
		for iPlayer, iStartingPlot in zip(iBestPermutation, range(len(pStartingPlots))):
			gc.getPlayer(iPlayer).setStartingPlot(pStartingPlots[iStartingPlot], True)

	def __computeRWDistanceMatrix(self):
		pCoordinates = CultureLink.pRWCoordinatesList
		fRWDistanceMatrix = SquareMatrix(len(pCoordinates), 0.0)
		for i, pCoordinateA in enumerate(pCoordinates):
			for j, pCoordinateB in enumerate(pCoordinates):
				if j > i:
					fRWDistance = RealWorldDistance(pCoordinateA, pCoordinateB) / DMAX_EARTH
					fRWDistanceMatrix[i][j] = fRWDistance
					fRWDistanceMatrix[j][i] = fRWDistance
		return fRWDistanceMatrix

	def __computeSPDistanceMatrix(self):
		fSPDistanceMatrix = SquareMatrix(len(CultureLink.pStartingPlotsList), 0.0)
		# fill the starting plot distance matrix with normalized step distances:
		for i, pStartingPlotA in enumerate(CultureLink.pStartingPlotsList):
			for j, pStartingPlotB in enumerate(CultureLink.pStartingPlotsList):
				if i > j:
					fSPDistance = StepDistance(pStartingPlotA, pStartingPlotB) / MaxPossibleStepDistance()
					if pStartingPlotA.getArea() != pStartingPlotB.getArea():
						#print "Area A: %s, Area B: %s" % (pStartingPlotA.getArea(), pStartingPlotB.getArea())
						fSPDistance = fSPDistance * 2
					fSPDistanceMatrix[i][j] = fSPDistance
					fSPDistanceMatrix[j][i] = fSPDistance
		return fSPDistanceMatrix


class GeographicalCoordinate:

	def __init__(self, sCivilizationType, dLatitude, dLongitude):
		self.civ = GetInfoType(sCivilizationType)
		self.lat = dLatitude
		self.lon = dLongitude

	def __str__(self):
		args = (self.getCityName(), self.lat, self.lon)
		return "%s:\t%8.4f   %8.4f" % args

	def getCivilization(self):
		return self.civ

	def getCityName(self):
		pCivilization = gc.getCivilizationInfo(self.civ)
		if pCivilization.getNumCityNames() > 0:
			return pCivilization.getCityNames(0)
		return "unknown city name"

	def getLatitude(self):
		return self.lat

	def getLongitude(self):
		return self.lon


## GLOBAL HELPER FUNCTIONS:

def GetInfoType(sInfoType, bIgnoreTypos = False):
	iInfoType = gc.getInfoTypeForString(sInfoType)
	#if iInfoType == -1 and not bIgnoreTypos:
		#arg = ("InfoType %s unknown! Probably just a Typing Error." % sInfoType)
		#raise ValueError, arg
	return iInfoType

def RealWorldDistance(pCoordA, pCoordB):
	# equator radius and earth flattening (WGS-84)
	SEMI_MAJOR_AXIS = 6378.137
	INVERSE_FLATTENING = 1/298.257223563
	# some variables to reduce redundancy
	F = pi * (pCoordA.getLatitude() + pCoordB.getLatitude()) / 360
	G = pi * (pCoordA.getLatitude() - pCoordB.getLatitude()) / 360
	l = pi * (pCoordA.getLongitude() - pCoordB.getLongitude()) / 360
	# calculate the rough distance
	S = sin(G)**2 * cos(l)**2 + cos(F)**2 * sin(l)**2
	C = cos(G)**2 * cos(l)**2 + sin(F)**2 * sin(l)**2
	w = atan(sqrt(S/C))
	D = 2 * w * SEMI_MAJOR_AXIS
	# flattening correction
	if w != 0:				
			R = sqrt(S * C) / w	
				H1 = INVERSE_FLATTENING * (3 * R - 1) / (2 * C)
				H2 = INVERSE_FLATTENING * (3 * R + 1) / (2 * S)
				return D * (1 + H1 * sin(F)**2 * cos(G)**2 - H2 * cos(F)**2 * sin(G)**2)
		return 0

def StepDistance(pPlotA, pPlotB): 
	return stepDistance(pPlotA.getX(), pPlotA.getY(), pPlotB.getX(), pPlotB.getY())

def MaxPossibleStepDistance():
	if CyMap().getGridWidth() > CyMap().getGridHeight():
		if CyMap().isWrapX(): 
			return (CyMap().getGridWidth() + 1) // 2
		return CyMap().getGridWidth()
	if CyMap().isWrapY(): 
		return (CyMap().getGridHeigth() + 1) // 2
	return CyMap().getGridHeight()

def ScaleList(xList):
	fSum = sum(xList)
	return [xElement / fSum for xElement in xList]

def SquareMatrix(iSize, xInitWith = None):
	return [[xInitWith] * iSize for i in range(iSize)]

def ScaleMatrix(matrix, absmin = None, absmax = None):
	minValue = absmin 
	maxValue = absmax
	if minValue == None:
		minValue = min([min(row) for row in matrix])
	if maxValue == None:
		maxValue = max([max(row) for row in matrix])
	if minValue == maxValue:
		return "geht nicht"
	return [map(lambda x: (x - minValue) / (maxValue - minValue), row) for row in matrix]

def FormatMatrix(matrix, description = None, rownames = None):
	if len(matrix) > 0:
		s = ""
		if description != None:
			s += description + 2 * "\n"
		s += "["
		for r in xrange(len(matrix)):
			if r > 0:
				s += " "
			s += "["
			for c in xrange(len(matrix[0])):
				if matrix[r][c] != None:
					s += "%8.4f" % matrix[r][c]
				else:
					s += "%8s" % "None"
				if c != len(matrix[0]) - 1:
					s+= ","
			if r == len(matrix) - 1:
				s += "]]"
			else:
				s += "],"
			if rownames != None:
				s += 3 * " " + rownames[r]
			s += "\n"
		return s
	return("Error while creating formated matrix string.")


def shuffle(xList):
	xShuffledList = []
	xListCopy = copy(xList)
	for x in range(len(xList)):
		r = dice.get(len(xListCopy), "CultureLink: shuffle")
		xShuffledList.append(xListCopy.pop(r))
	return  xShuffledList

'''
RANDOMLIST:
Returns a permutation of the items in xList. The probability for each element to appear at position x of
the permutation is defined by row x of the probabilities matrix. Element y in row x is the probability 
for element y in xList to appear at position x in the permutation. 
In other words: randmomList is a more general form of shuffling with non-uniform probabilities.
'''

def randomList(xList, fProbabilitiesMatrix):
		# make a copy so we can change the values
		fPrMxCopy = deepcopy(fProbabilitiesMatrix)
		iNumElements = len(fPrMxCopy)
		xRandomList = [None] * iNumElements
		# fill xRandomList in random order to prevent bias
		xShuffledList = shuffle(range(iNumElements))   
		for i in xShuffledList:
			for j in xRandomList:
				if j != None:
					fPrMxCopy[i][j] = 0.0
			fPrMxCopy[i] = ScaleList(fPrMxCopy[i])
			# get a random element from xList not in xRandomList
			xRandomList[i] = randomListElement(xList, fPrMxCopy[i])
		return xRandomList

def randomListElement(xList, fProbabilitiesList):
		maxsoren = 2 ** 16 - 1
		#for i in range(32):
		#	print i
		#	dice.get(2**i, "test")
		
		r = dice.get(maxsoren, "CultureLink: randomListElement") / maxsoren
		fCumulatedProbabilities = 0.0
		for i, fProbability in enumerate(fProbabilitiesList):
			fCumulatedProbabilities += fProbability
			if r < fCumulatedProbabilities:
				return xList[i]
		return xList[-1:][0]
