#include <stdio.h>
#include <stdlib.h>
#include <stl.h>
#include <hash_set>

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

float RUBIN_CONST=1.1;

extern int global_movie_expand;
extern vector<list<wire_segment> > net_paths_segment;
extern vector<int> vi_violations;
long long cells_expanded=0;
int nets_routed=0;
int dir_cost=10;
int via_cost=10;
int bend_cost=1;
int global_num_cells_frame=10;
int dir_cost_array[4][6];

list<cell> maze_route(grid &g, list<cell> &source, int net_dest,
		      list<pin> &remaining);

bool operator<(const active_cell &ac, const active_cell &ac2)
{
	return (ac.total_cost>ac2.total_cost);
}


static int estimated_pathcost(cell c, cube r)
{
	int dx=0,dy=0,dz=0;

	if (c.x < r.x1) {
		dx=r.x1-c.x;
	} else if (c.x > r.x2) {
		dx=c.x - r.x2;
	}

	if (c.y < r.y1) {
		dy=r.y1-c.y;
	} else if (c.y > r.y2) {
		dy=c.y-r.y2;
	}

	if (c.l < r.z1) {
		dz=r.z1 - c.l;
	} else if (c.l > r.z2) {
		dz=c.l-r.z2;
	}

	return dx+dy+dz*(via_cost);
}

// estimated path cost for a destination pin
// to a source cube -- how to deal with levels
static int estimated_pathcost(pin p, cube r)
{
	int dx=0,dy=0,dz=0;

	if (p.x < r.x1) {
		dx=r.x1-p.x;
	} else if (p.x > r.x2) {
		dx=p.x - r.x2;
	}

	if (p.y < r.y1) {
		dy=r.y1-p.y;
	} else if (p.y > r.y2) {
		dy=p.y-r.y2;
	}

	// pins have no level information
	/*
	if (p.l < r.z1) {
		dz=r.z1 - p.l;
	} else if (p.l > r.z2) {
		dz=p.l-r.z2;
	}
	*/

	//	return dx+dy+dz*(via_cost+1);
	return dx+dy;
}
		

static cube get_bounding_cube(list<pin> &vp)
{
	int i,count=0;
	int vp_size=vp.size();
	cube r;
	r.x1=vp.front().x;
	r.x2=vp.front().x;
	r.y1=vp.front().y-1;
	r.y2=vp.front().y+1;

	list<pin>::iterator lpi;
	lpi=vp.begin();
	++lpi;
	for (;lpi!=vp.end();++lpi,++count) {
		if (lpi->x<r.x1) r.x1=lpi->x;
		if ((lpi->x)>r.x2) r.x2=(lpi->x);
		if ((lpi->y-1)<r.y1) r.y1=(lpi->y-1);
		if ((lpi->y+2)>r.y2) r.y2=(lpi->y+1);
	}
	r.z1=0;
	r.z2=1;
	return r;
}

// cells from pin cannot be in lc to begin with
static void add_cells_from_pin(list<cell> &lc, pin p)
{
	int y;
	int l=-1,h=1;

	if (p.pad) {
		l=0;h=0;
	}
	
	cell c;

	for (y=l;y<=h;y++) {
		c.x=p.x;
		c.y=p.y+y;
		c.l=1;
		c.l2=-1;
		lc.push_back(c);
		c.l=0;
		lc.push_back(c);
	}
}

int get_seg_dir(wire_segment ws)
{
	if (ws.x1==ws.x2 && ws.y1==ws.y2) {
		if ((ws.z1-ws.z2)==1) return 0;
		if ((ws.z2-ws.z1)==1) return 1;
		return -2; // up/down
	}
	if (ws.x1==ws.x2 && ws.z1==ws.z2) {
		if ((ws.y1-ws.y2)==1) return 2;
		if ((ws.y2-ws.y1)==1) return 3;
		return -2; // north/south
	}
	if (ws.y1==ws.y2 && ws.z1==ws.z2) {
		if ((ws.x1-ws.x2)==1) return 4;
		if ((ws.x2-ws.x1)==1) return 5;
		return -2; // east/west
	}
	return -2;
}

void segment_to_path(list<wire_segment> &path, list<cell> &ret)
{
	cell c;
	
	list<wire_segment>::iterator lwsi;
	for (lwsi=path.begin();lwsi!=path.end();++lwsi) {
		if (lwsi->z1==lwsi->z2) { // not a via
			if (lwsi->x1 != lwsi->x2) { // x dir
				c.y=lwsi->y1;
				c.l=lwsi->z1;
				for (c.x=min(lwsi->x1,lwsi->x2);
				     c.x<=(max(lwsi->x1,lwsi->x2));c.x++)
					     ret.push_back(c);
			} else { // y dir
				c.x=lwsi->x1;
				c.l=lwsi->z1;
				for (c.y=min(lwsi->y1,lwsi->y2);
				     c.y<=(max(lwsi->y1,lwsi->y2));c.y++)
					     ret.push_back(c);
			}
		}
	}
}

list<wire_segment> path_to_segment(list<cell> &path)
{
	list<wire_segment> ret;
	wire_segment cur_seg,tseg;
	int dir=-1;

	cur_seg.x1=-1;
	cur_seg.x2=-1;

	list<cell>::iterator lci;
	for (lci=path.begin();lci!=path.end();++lci) {
		if (lci->l2>=0) { // we have a via
			if (cur_seg.x2>=0) { // current segment is valid, so push it onto return list
				ret.push_back(cur_seg);
			}
			cur_seg.x1=lci->x; cur_seg.y1=lci->y; cur_seg.z1=lci->l;
			cur_seg.x2=lci->x; cur_seg.y2=lci->y; cur_seg.z2=lci->l2;
			ret.push_back(cur_seg);
			cur_seg.x1=-1; cur_seg.x2=-1;
		} else {
			if (cur_seg.x1==-1) { //we have no current segment,
				//new one will be just this cell
				cur_seg.x1=lci->x; cur_seg.y1=lci->y; cur_seg.z1=lci->l;
				cur_seg.x2=lci->x; cur_seg.y2=lci->y; cur_seg.z2=lci->l;
				dir=-1;
			} else {
				tseg.x1=cur_seg.x2; tseg.y1=cur_seg.y2;	tseg.z1=cur_seg.z2;
				tseg.x2=lci->x;	tseg.y2=lci->y;	tseg.z2=lci->l;
				if (get_seg_dir(tseg)==-2) { //cells are not adjacent
					ret.push_back(cur_seg);
					cur_seg.x1=lci->x; cur_seg.y1=lci->y; cur_seg.z1=lci->l;
					cur_seg.x2=lci->x; cur_seg.y2=lci->y; cur_seg.z2=lci->l;
					dir=-1;
				} else {
					if (dir==-1 || dir==get_seg_dir(tseg)) {
						cur_seg.x2=lci->x;
						cur_seg.y2=lci->y; cur_seg.z2=lci->l;
						dir=get_seg_dir(tseg);
					} else {
						ret.push_back(cur_seg);
						cur_seg=tseg;
						dir=get_seg_dir(tseg);
					}
				}
			}
		}
	}
	if (cur_seg.x1!=-1) {
		ret.push_back(cur_seg);
	}
	return ret;
}

list<pin> find_pin_to_route(list<pin> &remaining_pins, list<pin> &used_pins)
{
	list<pin>::iterator lpi,best;
	int pin_to_route_cost=1<<30;;
	list<pin> pin_to_route;

	cube source_cube = get_bounding_cube(used_pins);
	for (lpi=remaining_pins.begin();lpi!=remaining_pins.end();++lpi) {
		if (estimated_pathcost(*lpi,source_cube)<pin_to_route_cost) {
			pin_to_route_cost = estimated_pathcost(*lpi,source_cube);
			best = lpi;
		}
	}
	pin_to_route.push_front(*best);
	return pin_to_route;
		
}

list<cell> net_maze_route(grid &g, int net, list<pin> &pins, int &partial)
{
	// we have to route each of the pins in turn until all the pins are
	// connected

	int pins_size=pins.size();
	// for now we'll just do the pins in order
	list<cell> source;
	list<pin> remaining_pins=pins,used_pins;
	list<cell> actual_paths;
	int remaining_pins_size=remaining_pins.size();

	list<pin> pin_to_route;
	
	add_cells_from_pin(source,remaining_pins.front());
	used_pins.push_back(remaining_pins.front());
	remaining_pins.pop_front();
	remaining_pins_size=remaining_pins.size();

	while(!remaining_pins.empty()) {
		list<pin>::iterator lpi,start_pin;
		list<cell>::iterator lci;
		
		pin_to_route = find_pin_to_route(remaining_pins,used_pins);
		list<cell> path=maze_route(g,source,net,pin_to_route);
		if (path.empty()) {
			//			printf("ERROR, no route to cell!\n");
			partial=1;
			return actual_paths;
		}

		for (lpi=remaining_pins.begin();lpi!=remaining_pins.end();++lpi) {
			if (lpi->x==path.back().x &&
			    (path.back().y>=(lpi->y-1) && path.back().y<=(lpi->y+1))) {
				break;
			}
		}

		if (lpi==remaining_pins.end()) {
			printf("ERROR in net_maze_route... path doesn't end on\n");
			printf("one of the remaining pins!\n");
			printf("it ends at (%i,%i,%i)\n",path.back().x,path.back().y,
			       path.back().l);
			printf("remaining pins are: ");
			for (lpi=remaining_pins.begin();lpi!=remaining_pins.end();++lpi) {
				printf("(%i,%i,%i)\n",lpi->x,lpi->y,0);
			}

			printf("\n\nSource list is:\n");
			for (lci=source.begin();lci!=source.end();++lci) {
				printf("(%i,%i,%i)\n",lci->x,lci->y,lci->l);
			}
			printf("\n\nBad path is:\n");
			for (lci=path.begin();lci!=path.end();++lci) {
				printf("(%i,%i,%i)\n",lci->x,lci->y,lci->l);
			}
			
			exit(1);
		}
		
		add_cells_from_pin(source,*lpi);
		used_pins.push_back(*lpi);
		remaining_pins.erase(lpi);

		// copy path to actual path
		for (lci=path.begin();lci!=path.end();++lci)
			actual_paths.push_back(*lci);

		path.pop_front();
		path.pop_back();
		
		for (lci=path.begin();lci!=path.end();++lci) {
			source.push_back(*lci);
		}
		//fprintf(stderr,"net_maze_route %i/%i\r",used_pins.size(),
		//	remaining_pins.size());
		//fflush(stderr);
	}
	partial=0;
	return actual_paths;
}

void expand_cell(grid &g, priority_queue<active_cell> &pqa, cell &new_cell,
		 active_cell &ac, cube &dest_cube, char dir, int dest)
{
	cells_expanded++;
	active_cell nac;
	nac.pathcost=ac.pathcost+1;
	if (dest==0) nac.pathcost+=g.cellCost(new_cell);

	// now we will check for bends
	
	int old_dir=g.getPrevDir(ac.pos);
	if (old_dir<4 && dir<4 && old_dir!=dir) nac.pathcost+=bend_cost;
	
	// now we will check for vias
	if (new_cell.l != ac.pos.l) nac.pathcost+=via_cost;

	// let's penalize for the wrong direction:
	//  odd layers: north-south, even layers: east-west

	if (new_cell.l&1) { // horizontal
		if (dir==1 || dir==3) {
			nac.pathcost+=dir_cost;
		}
	} else { // vertical
		if (dir==0 || dir==2) {
			nac.pathcost+=dir_cost;
		}
	}

	// trying to add the heuristic fudge factor to
	// make things go faster...  turns out k=2 ended up being 10%
	// faster than k=1, but much worse results
	nac.total_cost=nac.pathcost+
		(estimated_pathcost(new_cell,dest_cube))*RUBIN_CONST;

	nac.pos=new_cell;

	nac.dir=dir;
	pqa.push(nac);
	
	//fprintf(stderr,"reached cell (%i,%i,%i) path_cost=%.2f total_cost=%.2f\n",
	//	nac.pos.x,nac.pos.y,nac.pos.l,nac.pathcost,
	//	nac.total_cost);
	
}

struct hash_cell_struct {
	size_t operator() (const cell &c) const {
		return c.x+c.y+c.l;
	}
};

struct eqcell {
	size_t operator() (const cell &a, const cell &b) const {
		return (a.x==b.x && a.y==b.y && a.l==b.l);
	}
};

hash_set<cell, hash_cell_struct, eqcell> get_destinations_from_pins(list<pin> &pins)
{
	hash_set<cell, hash_cell_struct, eqcell> ret;

	list<pin>::iterator lpi;
	for (lpi=pins.begin();lpi!=pins.end();++lpi) {
		cell c;
		c.x=lpi->x;
		for (c.l=0;c.l<2;c.l++) {
			for (c.y=(lpi->y-1);c.y<=(lpi->y+1);c.y++) {
				ret.insert(c);
			}
		}
	}
	return ret;
}

list<cell> maze_route(grid &g, list<cell> &source, int net_dest,
			list<pin> &remaining_pins)
{
	int i;
	int count=0;
	list<cell> vc;
	list<cell> expanded_cells;
	
	priority_queue<active_cell> pqa;
	
	cube dest_cube;

	g.clearVisitedAndPrev();
	cell zero;
	zero.x=-1;
	zero.y=-1;
	zero.l=0;

	list<cell>::iterator lci;
	// calc dest rectangle somehow
	dest_cube = get_bounding_cube(remaining_pins); 
	hash_set<cell, hash_cell_struct, eqcell> destinations=
		get_destinations_from_pins(remaining_pins);
	
	for (lci=source.begin();lci!=source.end();++lci) {
		if (lci->l2 >= 0) continue;
		active_cell ac;
		ac.pathcost=0;
		ac.total_cost=estimated_pathcost(*lci,dest_cube)*RUBIN_CONST;
		ac.pos=*lci;
		ac.dir=7;
		pqa.push(ac);
	}

	if (global_movie_expand) {
		cmumovie_newframe();
		cmumovie_drawnets(net_paths_segment,vi_violations);
		cmumovie_drawsourcedest(source,remaining_pins);
	}
	
	while (!pqa.empty()) {
		count++;
		if (global_movie_expand && (count%global_num_cells_frame)==0) {
			// draw an expanded cell movie frame
			cmumovie_newframe_short();
			//cmumovie_drawnets(net_paths_segment,vi_violations);
			cmumovie_drawexpansion(expanded_cells);
			expanded_cells.clear();
		}
		active_cell ac=pqa.top();
		pqa.pop();
		if (g.getVisited(ac.pos)) continue; // don't expand a cell twice
		g.setVisited(ac.pos);
		g.setPrev(ac.pos,ac.pos,ac.dir);
		if (global_movie_expand) expanded_cells.push_back(ac.pos);
		//fprintf(stderr,"expanding cell (%i,%i,%i) path_cost=%.2f total_cost=%.2f\n",
		//       ac.pos.x,ac.pos.y,ac.pos.l,ac.pathcost,ac.total_cost);

		
		// expanding cell ac
		int done2=(destinations.find(ac.pos)!=destinations.end());
		if (done2) {
			// we have hit the target
			//		printf("We hit the target, backtracing\n");
			cell c=ac.pos;
			unsigned char d;
			do {
				c.l2=-1;
				vc.push_front(c);
				d=g.getPrevDir(c);
				if ((d==4) || (d==5)) {
					if (d==4) c.l2=c.l-1;
					if (d==5) c.l2=c.l+1;
					vc.push_front(c);
				}
			} while ((c=g.getPrev(c)).x!=-1);
			nets_routed++;
			return vc;
		}
		int dir;
		for (dir=0;dir<6;dir++) {
			//			printf("checking dir=%i\n",dir);
			cell new_cell;
			if (g.getNeighbor(ac.pos,dir,new_cell) &&
			    !g.getVisited(new_cell)) {

				int dest;
				if (destinations.find(new_cell)!=destinations.end())
					dest=1;
				else dest=0;
				expand_cell(g,pqa,new_cell,ac,
					    dest_cube,dir,dest);
				//}
			}
		}
	}
	return vc; // no path found, return empty
}