# experiment met evolutionary programming voor de kanalenplanning
# het genetische zit er nu nauwelijks in, en wat er in zit is ongetwijfeld
# fout. wat er wel goed in zit is het parseren van de bestaande situatie en
# het scoren van (nu random) configuraties.
#
# de score functie is nu redelijk simplistisch:
#   - de score van een combinatie van twee interfaces op een node is 1 als er
#     twee of meer kanalen tussen zitten, en -1 als er 1 kanaal tussen zit, -5
#     als er geen kanaal tussen zit en -10 als de kanalen hetzelfde zijn
#   - de score van een node is de som van de scores van alle combinaties van
#     interfaces van die node, maal het aantal interfaces. dat laatste omdat
#     een positieve score hebben knapper is met meer interfaces dan met minder,
#     dus dat moet beloond. een negatieve score is erger met meer interfaces
#     (belangrijker node, waarschijnlijk) dan met minder, dus dat moet
#     bestraft.
#   - de totale score is de som van de scores van de nodes
#
# het stukje "genetisch" aan het einde is afgeraffeld. mutation en
# recombination gebeuren op de oplossing zelf ipv op een bitstring
# representatie. selection is dom en neemt gewoon de helft beste oplossingen.
#
# lvoge@cs.vu.nl
import re
import random
import os

# deze twee zijn nodig voor de evaluatie van een configuratie
nodes = {}		# nodename -> Node
groups = {}		# essid -> WIGroup

population = []

# gegeven een lijst, geef de lijst zonder dubbele elementen
def uniq(l):
	d = {}
	for e in l:
		d[e] = 1
	return d.keys()

class Node:
	def __init__(self, name, wis):
		self.name = name
		self.wis = wis
		self.special = {}
		for wi in wis:
			wi.setNode(self)
	def score(self):
		score = 0
		for i in range(len(self.wis)):
			wi_i = self.wis[i]
			if wi_i.group == None:
				# orphaned interface
				continue
			if wi_i.group.channel == None:
				print "huh?"
			for j in range(len(self.wis)):
				if i != j:
					wi_j = self.wis[j]
					if wi_j.group == None:
						continue
					diff = abs(wi_i.group.channel - wi_j.group.channel)
					if diff > 2:
						score = score + 1
					elif diff == 2:
						score = score - 1
					elif diff == 1:
						score = score - 5
					else:
						score = score - 10
			if self.special.has_key(wi_i.group.channel):
				score = score + self.special[wi_i.group.channel]
		score = score * len(self.wis)
		return score
	def setSpecialScoreForChannels(self, score, channels):
		for c in channels:
			self.special[c] = score

# een supernode is een verzameling subnodes, bv cetim1, cetim2 en cetim3.
class SuperNode(Node):
	def __init__(self, name, nodes):
		self.name = name
		self.nodes = nodes
		self.wis = []
		self.special = {}
		for n in nodes:
			self.wis.extend(n.wis)

class WI:
	def __init__(self, name):
		self.name = name
		self.node = None
		self.group = None
		self.omni = 0
	def setNode(self, node):
		self.node = node
	def setGroup(self, group):
		self.group = group

class WIGroup:
	def __init__(self, name):
		self.name = name
		self.wis = []
		self.channel = None
	def add_wi(self, wi):
		self.wis.append(wi)
		wi.setGroup(self)
	def uniq(self):
		self.wis = uniq(self.wis)

# een configuratie is een bepaalde bedeling van kanalen aan groepen. aangezien
# groepen keyed zijn op essid is de concrete configuratie hier een dict van
# essids naar kanalen.
class Configuration:
	def __init__(self):
		self.conf = None
		self.calculated_score = None
	def copy(self):
		c = Configuration()
		c.conf = self.conf.copy()
		c.calculated_score = None
		return c
	def randomize(self):
		self.conf = {}
		for essid in groups.keys():
			self.conf[essid] = random.randint(1, 13)
		self.calculated_score = None
	def score(self):
		assert len(self.conf) == len(groups)
		if self.calculated_score != None:
			return self.calculated_score
		for essid in groups.keys():
			groups[essid].channel = self.conf[essid]
		score = 0
		for node in nodes.values():
			score = score + node.score()
		self.calculated_score = score
		return score
	def mutate(self, rate):
		for essid in groups.keys():
			if random.random() <= rate:
				self.conf[essid] = random.randint(1, 13)
	def crossover(self, partner, numpoints):
		# pick the crossover points
		essids = groups.keys()
		points = [random.randint(0, len(essids) - 1) for i in range(numpoints)]
		points.sort()
		conf = {}
		who = 0
		lastpoint = 0
		while len(points):
			point = points.pop(0)
			if who == 0:
				d = self.conf
			else:
				d = partner.conf
			who = 1 - who
			for i in range(lastpoint, point + 1):
				conf[essids[i]] = d[essids[i]]
			lastpoint = point
		if who == 0:
			d = self.conf
		else:
			d = partner.conf
		for i in range(lastpoint, len(essids)):
			conf[essids[i]] = d[essids[i]]
		assert len(conf) == len(groups)
		self.conf = conf


# BEGIN UGLY PARSING CODE

to_resolve = []		# list of (essid, WI) tuples

def parse_wleiden_conf(lines):
	essid = None
	wi = None
	wis = []
	for l in lines:
		if wi != None:
			match = re.match("^MODE=master.*", l)
			if match != None:
				master = 1
			match = re.match("^ESSID=(.*)", l)
			if match != None:
				essid = match.group(1)
			match = re.match("^EW[0-9]*", l)
			if match != None:
				if master == 1:
					group = WIGroup(essid)
					groups[essid] = group
					group.add_wi(wi)
				else:
					# defer, may come way later
					to_resolve.append( (essid, wi) )
				master = 0
				wi = None
				essid = None
		else:
			match = re.match("^\$nodename='([^']*)';.*", l)
			if match != None:
				nodename = match.group(1).lower()
			match = re.match("^\$config{'wi[0-9]*:[0-9].*", l)
			if match != None:
				continue
			match = re.match("^\$config{'(wi[0-9]*).*", l)
			if match != None:
				wi = WI(match.group(1))
				wis.append(wi)
				master = 0
	node = Node(nodename, wis)
	nodes[nodename] = node

# gegeven een file met filenames van wleiden.conf's, parseer ze allemaal en
# vul de datastructuren
def parse_metafile(filename):
	for fname in open(filename).readlines():
		parse_wleiden_conf(open(fname[:-1]).readlines())
	for essid, wi in to_resolve:
		if not groups.has_key(essid):
			print "Warning: node %s, %s refers to unknown essid %s" % (wi.node.name, wi.name, essid)
			continue
		groups[essid].add_wi(wi)
	for group in groups.values():
		group.uniq()

def parse_coupled(filename):
	try:
		for line in open(filename).readlines():
			supername, rest = line[:-1].split(':')
			subnodes = []
			for nodename in rest.split(' '):
				if nodename == '':
					continue
				node = nodes[nodename]
				del nodes[nodename]
				subnodes.append(node)
			node = SuperNode(supername, subnodes)
			nodes[supername] = node
	except:
		pass

def parse_special(filename):
	for line in open(filename).readlines():
		fields = line[:-1].split(' ')
		nodename = fields[0]
		score = int(fields[1])
		channels = map(lambda c: int(c), fields[2:])
		nodes[nodename].setSpecialScoreForChannels(score, channels)

# END UGLY PARSING CODE

def plot_configuration(conf, out):
	out.write("digraph plot {\n")
	for essid in groups:
		out.write("\"%s\" [shape=box label=\"%s\\n(%d)\"]\n" % (essid, essid, conf[essid]))
	for nodename in nodes.keys():
		for wi in nodes[nodename].wis:
			if wi.group == None:
				continue
			out.write("\"%s\" -> \"%s\"\n" % (nodename, wi.group.name))
	out.write("}")

parse_metafile('l')
parse_coupled('coupled.conf')
parse_special('special.conf')

for essid in groups.keys():
	print essid, map(lambda wi: wi.node.name, groups[essid].wis)

for i in range(20):
	conf = Configuration()
	conf.randomize()
	population.append(conf)

last_high_score = -10000000
iterations_since_new_high_score = 0
while iterations_since_new_high_score < 1000:
	for i in range(0, 9):
		p = population[i].copy()
		#population[i].crossover(population[i + 10], random.randint(1, 4) * 2)
		population[i + 10] = p
		population[i + 10].mutate(0.05)
	population.sort(lambda a, b: cmp(b.score(), a.score()))
	high_score = population[0].score()
	if high_score > last_high_score:
		last_high_score = high_score
		iterations_since_new_high_score = 0
	iterations_since_new_high_score = iterations_since_new_high_score + 1
	print high_score
plot_configuration(population[0].conf, open("foo.dot", 'w'))
os.system('neato -Gstart=foo -Goverlap=false/scale -Gsplines=true -Gsep=2 -Gratio=fill -Gnslimit=50.0 -Grotate=90 -Gsize="11,7.5" -Tps -o channelga.ps foo.dot')