#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <math.h>

#include "maze.h"
#include "grid.h"
#include "parser.h"
#include "cmumovie.h"

extern long long cells_expanded;
extern int nets_routed;
extern int max_queue_size;
extern int dir_cost,via_cost,bend_cost;
extern int global_num_cells_frame;
extern int dir_cost_array[4][6];
extern float RUBIN_CONST;
extern int global_cmuview_file;
extern char global_cmuview_filename[256];

int global_movie=0;
int global_movie_expand=0; // whether to show mazeroute expansion or not

//vector<list<cell> > net_paths;
vector<list<wire_segment> > net_paths_segment;
vector<int> net_partial;

int violations_wirelen(grid &g, int &violations, int &wirelen,
		       vector<int> &layer_wirelen)
{
	violations=wirelen=0;
	cell c;
	
	for (c.l=0; c.l<4; c.l++) {
		for (c.y=0; c.y<g.height; c.y++) {
			for (c.x=0; c.x<g.width; c.x++) {
				if (g.countNets(c)>1) {
					violations++;
				}
				if (g.countNets(c)>0) {
					if (!(g.isPin(c))) {
						layer_wirelen[(int)c.l]++;
						wirelen++;
					}
				}
			}
		}
	}

	return 0;
}
int net_violations_wirelen_bends(grid &g, int n, int &violations, int &wirelen,
				 int &vias, int &bends, vector<int> &layer_wirelen)
{
	violations=wirelen=vias=bends=0;

	list<cell>::iterator lci;
	list<cell> lc;
	segment_to_path(net_paths_segment[n],lc);
	lci=lc.begin();
	int old_layer=lci->l;
	int old_dir=0,dir=0,first=1;
	wire_segment ws;
	ws.x1=lci->x; ws.y1=lci->y; ws.z1=lci->l;
	for (;lci!=lc.end();++lci) {
		ws.x2=lci->x; ws.y2=lci->y; ws.z2=lci->l;
		if (g.countNets(*lci)>1) {
			violations++;
			//fprintf(stderr,"violation at net=%i (%i,%i,%i)\n",
			//	n,lci->x,lci->y,lci->l);
		}
		wirelen++;
		layer_wirelen[lci->l]++;
		// try to determine if this is a non-contiguous cell
		dir=get_seg_dir(ws);
		if (dir>=0) {
			if (lci->l != old_layer) vias++;
			if (dir!=old_dir && !first) bends++;
			first=0;
		} else {
			first=1;
		}
		old_layer=lci->l;
		old_dir=dir;
		ws.x1=ws.x2; ws.y1=ws.y2; ws.z1=ws.z2;
	}
	
	return 0;
}

int route_all_nets(grid &g, vector<net> &vn)
{
	// pick some random ordering of the nets... for now we'll
	// just do them in the order given to us

	int i,j,partial;
	for (i=0;i<vn.size();i++) {
		fprintf(stderr,"route_all_nets: routing net %i/%i\r",i,vn.size());
		fflush(stderr);
		int id=vn[i].id;
		// check to see if this net has already been routed
		if (net_paths_segment[id].size()>0) {
			// we need to rip up this path
			list<cell> lc;
			segment_to_path(net_paths_segment[id],lc);
			g.removeNetFromPath(lc,id);
			net_paths_segment[id].clear();
		}

		// now we need to route it again using the current
		// path costs as stored in the grid element
		list<pin> lp;
		for (j=0;j<vn[i].pins.size();j++)
			lp.push_back(vn[i].pins[j]);
		list<cell> lc;
		lc=net_maze_route(g,id,lp,partial);
		net_paths_segment[id]=path_to_segment(lc);
		net_partial[id]=partial;

		// now we should add this new path into the grid
		g.addNetToPath(lc,id);
	}
	return 0;
}

int tot_wirelen,tot_bends,tot_vias,tot_violations, max_violations;
vector<int> vi_violations, vi_bends, vi_wirelen, vi_vias;
vector<int> vi_layer_wirelen;
vector<net> vn;


int route_one_pass(grid &g, int max_id, int pass)
{
	int i;
	int netcost,mincost,badcost;

	// guess at a way to change net costs... needs to be more complicated
	// the violations subtraction should probably be something exponential
	// i.e. approach the minimum only as violations gets very large

	netcost=4*pass;
	if (pass>=5) netcost+=(int) (2.0*pow(pass-3,3.5));
	mincost=netcost/2;

	// number of violations should probably also be relative to number of
	// pins... nets with large number of pins will tend to have big numbers
	// of violations by default
       	for (i=0;i<max_id;i++) {
		if (max_violations==0) badcost=0;
		else badcost=vi_violations[i]*(netcost-mincost)/max_violations;
		badcost=vi_violations[i];
		g.net_costs[i]=max(netcost-badcost,mincost);
	}
	g.quantizeCosts();
	
	route_all_nets(g,vn);

	
	tot_wirelen=tot_bends=tot_vias=tot_violations=0;
	
	vi_violations.clear();
	vi_bends.clear();
	vi_wirelen.clear();
	vi_vias.clear();
	vi_layer_wirelen.resize(4); vi_layer_wirelen.clear();
	max_violations=0;
	
	for (i=0;i<vn.size();i++) {
		int violations,bends,wirelen,vias;
		net_violations_wirelen_bends(g, vn[i].id, violations, wirelen,
					     vias,bends,vi_layer_wirelen);
		vi_violations[vn[i].id]=violations;
		tot_violations+=violations;
		if (violations>max_violations) max_violations=violations;
		vi_bends[vn[i].id]=bends;
		tot_bends+=bends;
		vi_wirelen[vn[i].id]=wirelen;
		tot_wirelen+=wirelen;
		vi_vias[vn[i].id]=vias;
		tot_vias+=vias;
	}

	vi_layer_wirelen.resize(4); vi_layer_wirelen.clear();
	violations_wirelen(g,tot_violations,tot_wirelen,vi_layer_wirelen);

	fprintf(stderr, "\nPASS:%i  \t",pass);
	fprintf(stderr, "Wirelen: %i  Vias: %i  Bends: %i  Violations: %i\n",
	       tot_wirelen,tot_vias,tot_bends,tot_violations);

	if (global_movie) {
		if (cmumovie_newframe()<0) exit(1);
		// draw the routed nets
		cmumovie_drawnets(net_paths_segment,vi_violations);
	}
}	


int ripup_reroute(char *fname)
{
	vector<pin> vp;
	int width,height;
	int ret,i,y,j;

	ret=parse_placement(fname,vn,vp,width,height);

	if (ret<0) {
		printf("parsing failed!\n");
		return 0;
	}

	if (global_movie) {
		if (cmumovie_config(width,height)<0) exit(1);
	}
	
	int max_id=0;
	for (i=0;i<vn.size();i++) if (vn[i].id>max_id) max_id=vn[i].id;
	//	net_paths.resize(max_id+1);
	net_paths_segment.resize(max_id+1);
	net_partial.resize(max_id+1);

	grid g;
	g.makeGrid(vp,width,height,max_id);

	vi_violations.resize(max_id+1); vi_violations.clear();
	vi_bends.resize(max_id+1);
	vi_wirelen.resize(max_id+1);
	vi_vias.resize(max_id+1);

	float ratio,old_ratio;
	
	route_one_pass(g,max_id,0);

     	for (i=1;i<=6 || ratio>1.5 || old_ratio>1.5;i++) {
		old_ratio=ratio;
		ratio=tot_violations;
		route_one_pass(g,max_id,i);
		ratio=ratio/(float) tot_violations;
		if (tot_violations==0) ratio=0;
	}
	if (tot_violations==0) return 0;
	for (i=2;i<=5 || ratio>1.3 || old_ratio>1.3;i++) {
		old_ratio=ratio;
		ratio=tot_violations;
		route_one_pass(g,max_id,i);
		ratio=ratio/(float)(tot_violations);
		if (tot_violations==0) ratio=0;
	}
	if (tot_violations==0) return 0;
	route_one_pass(g,max_id,100);
	return 0;
}


int display_net(list<wire_segment> lws, int net_id, int violations, int partial)
{
	printf("n %i\n",net_id);
	if (partial) {
		printf("p\n");
		/*
	} else if (lws.size()==0 &&
		   vn[net_id].pins.size()>1) {
		printf("x\n");
		*/
	} else {
		printf("r\n");
	}

	printf("%i\n",violations);
	list<wire_segment>::iterator lwsi;

	for (lwsi=lws.begin();lwsi!=lws.end();++lwsi) {
		if (lwsi->z1!=lwsi->z2) {
			printf("v %i %i %i %i\n",lwsi->z1+1, lwsi->z2+1, lwsi->x1, lwsi->y1);
		} else {
			printf("w %i %i %i %i %i\n",lwsi->z1+1, lwsi->x1, lwsi->y1, lwsi->x2, lwsi->y2);
		}
	}
}

int display_results()
{
	int i;
	
	printf("%i\n",tot_wirelen);
	printf("%i\n",tot_bends);
	printf("%i\n",tot_vias);
	printf("%i %i %i %i\n",vi_layer_wirelen[0],vi_layer_wirelen[1],
	       vi_layer_wirelen[2],vi_layer_wirelen[3]);
	
	for (i=0;i<vn.size();i++) {
		//list<wire_segment> lws=path_to_segment(net_paths[vn[i].id]);
		display_net(net_paths_segment[vn[i].id],vn[i].id,
			    vi_violations[vn[i].id],net_partial[vn[i].id]);
	}
	printf("e\n");

	fprintf(stderr, "\ncells_expanded: %lld  nets_routed: %i  ave: %lld\n",
		cells_expanded, nets_routed, cells_expanded/nets_routed);
	return 0;
}	


void init_dir_cost()
{
	int l,dir;

	for (l=0;l<4;l++) {
		for (dir=0;dir<6;dir++) dir_cost_array[l][dir]=0;
	}
	dir_cost_array[0][0]=dir_cost;
	dir_cost_array[0][2]=dir_cost;
	dir_cost_array[2][0]=dir_cost;
	dir_cost_array[2][2]=dir_cost;
	dir_cost_array[1][1]=dir_cost;
	dir_cost_array[1][3]=dir_cost;
	dir_cost_array[3][1]=dir_cost;
	dir_cost_array[3][3]=dir_cost;
}

void usage()
{
	printf("Usage: route [OPTION]... [PLACEMENT FILE]...\n");
	printf("Performs ripup/reroute routing on the given placement file.\n");
	printf("Final routed design is written to standard output, intermediate\n");
	printf("status information is written to standard error\n");
	printf("  -m   Open cmuview and display results after each pass\n");
	printf("  -e   Ditto, but display cell expansion during mazerouting\n");
	printf("  -n   Number of expanded cells to show each frame\n");
	printf("  -d   Frame delay for cmumovie, default is 500ms\n");
	printf("  -f   Write cmuview output to given file\n");
	printf("  -v   Via cost, default is %i\n",via_cost);
        printf("  -w   Wrong direction cost, default is %i\n",dir_cost);
	printf("  -b   Bend cost, default is %i\n",bend_cost);
	printf("  -R   Rubin cost estimator fudge factor, default is %f\n",RUBIN_CONST);
	printf("  -h   Display this help and exit\n");
	printf("\n(c) 2002 Josh Pieper & Ricky Raedalli-Sanchez\n");
	exit(0);
}

int main(int argc, char **argv)
{
	char *short_opt="mew:v:d:hn:b:R:f:";
	int c;
	int movie_delay=500;

	init_dir_cost();

	while ((c=getopt(argc, argv, short_opt))!=-1) {
		switch (c) {
		case 'f':
			strncpy(global_cmuview_filename,optarg,255);
			global_cmuview_file=1;
			break;
		case 'm': // movie playing on
			global_movie=1;
			break;
		case 'e':
			global_movie_expand=1;
			global_movie=1;
			break;
		case 'w': // wrong direction cost
			dir_cost=atoi(optarg);
			init_dir_cost();
			break;
		case 'd': // movie delay
			movie_delay=atoi(optarg);
			break;
		case 'v':
			via_cost=atoi(optarg);
			break;
		case 'b':
			bend_cost=atoi(optarg);
			break;
		case 'n':
			global_num_cells_frame=atoi(optarg);
			break;
		case 'R':
			RUBIN_CONST=atof(optarg);
			break;
		case 'h':
			usage();
			break;
		default:
			printf("unrecognized option!\n");
			usage();
		}
	}

	if (optind>=argc) {
		printf("not enough args\n");
		usage();
	}

	if (global_movie) {
		if (cmumovie_open(movie_delay)<0) {
			fprintf(stderr,"cmumovie_open failed!\n");
			exit(1);
		}
	}
	ripup_reroute(argv[optind]);
	display_results();
	fflush(stdout);
	fflush(stderr);
	if (global_movie && ! global_cmuview_file) {
		// somehow wait for window to close
		while (1) sleep(1);
		
		cmumovie_close();
	}
	return 0;
}