# gegeven een succesvolle route-bereken run, laat de berekende route tussen
# twee nodes zien
#
# lvoge@cs.vu.nl
#
# Copyright 2004 Lodewijk Voge / Stichting Wireless Leiden,
#                All Rights Reserved.
# License: http://www.wirelessleiden.nl/LICENSE.
import os
import re
import string
import sys
import popen2

def tr(from_, to_, separator):
	nodere = re.compile("^(.*):")
	routere = re.compile("^\t([^ ]*) -> ([^ ]*)")

	def parseaddr(s):
		f = s.split('.')
		return (long(f[0]) << 24L) + \
			(long(f[1]) << 16L) + \
			(long(f[2]) << 8L) + \
			long(f[3])

	routes = {}	# NodeName -> [ (ParsedAddress, Netmask, Gateway) ]
	for l in open('routes').readlines():
		l = l[:-1]
		match = nodere.search(l)
		if match != None:
			node = match.group(1)
			routes[node] = []
		match = routere.search(l)
		if match != None:
			(addr, mask) = match.group(1).split('/')
			routes[node].append( (parseaddr(addr), int(mask), match.group(2) ) )

	def showaddr(a):
		return "%d.%d.%d.%d" % ((a >> 24) & 0xff, (a >> 16) & 0xff, (a >> 8) & 0xff, a & 0xff)

	# gegeven de naam van de 'huidige' node en een gewenste bestemming (in
	# geparseerd, integer formaat), geef de naam van de volgende hop, of None als
	# er niet zo'n route is.
	def lookup(nodename, dest):
		for (addr, mask, gw) in routes[nodename]:
			m = ~((1 << (32 - mask)) - 1)
			if (dest & m) == (addr & m):
				return addrs[gw]
		return None

	addrs = {}	# dict van adres naar nodename waar dat adres bij hoort
	non_interlink_of_node = {}	# dict van nodename naar primair adres
	for l in open('nodes').readlines():
		fields = l[:-1].split('|')
		nodename = fields.pop(0)
		for f in fields:
			addr = f.split('/')[0]
			if addr[:6] != '172.16' and addr[:6] != '172.31':
				non_interlink_of_node[nodename] = parseaddr(addr)
			addrs[addr] = nodename
		if not non_interlink_of_node.has_key(nodename):
			# okee, dan maar whatever adres er is
			non_interlink_of_node[nodename] = parseaddr(addr)

	route = [from_]
	while from_ != to_:
		from_ = lookup(from_, non_interlink_of_node[to_])
		route.append(from_)
	return separator.join(route)

if __name__ == "__main__":
	if len(sys.argv) < 3:
		print "Usage: python tr.py fromnode tonode"
		sys.exit(1)
	if len(sys.argv) == 4 and sys.argv[3] == '1':
		separator = ' '
	else:
		separator = "\n"
	print tr(sys.argv[1], sys.argv[2], separator)