//package cgen;
import java.awt.*;
import java.applet.*;
import java.io.*;
import graph.*;
import graph.test.*;
import graph.editor.*;
import graph.layout.*;
import graph.cluster.*;
import graph.layer.*;
import graph.dot.*;
import graph.filter.*;
import graph.rep.*;
import graph.dot.*;
import java.util.*;
import java.net.URL;
/**
* A switchbox routing tool.
*
* Written (for the most part) by Adrian Wrixon, 97.
*
* @version $Id$
*/
public class SimpleRouter extends Applet implements Runnable{
Image offscreenImg;
Graphics offscreenG;
Editor m_editor = new Editor(null);
public int xdim = 0, ydim = 0, num_nets=0, num_pins=0;
public int board[][] = new int[20][20];
public listnode movelist = new listnode();
public int xpos=0, ypos=0, moves=0;
public listnode drawnode = new listnode();
int mag = 30, xoff = 70, yoff = 70;
boolean go = false;
Thread runner;
/**
* Initialize the graph from a file.
*/
public void start(){
if (runner==null) {
runner =new Thread(this);
runner.start();
}
}
public void stop(){
if (runner!=null){
runner.stop();
runner=null;
}
}
public void init() {
resize(400,400);
setBackground(Color.black);
//add("Center", m_editor);
offscreenImg = createImage(this.size().width,this.size().height);
offscreenG=offscreenImg.getGraphics();
offscreenG.setColor(Color.black);
offscreenG.fillRect(0,0,this.size().width,this.size().height);
setLayout(null);
addNotify();
//}}
}
public void run(){
try {
/* Uncomment this line if you want to use the web version. */
String input_file = getParameter("file");
URL url = new URL(input_file);
System.out.println("input file = " + input_file);
DataInputStream data = new DataInputStream(url.openStream());
m_editor.graph = DotParser.parse(data);
// m_editor.graph = DotParser.parse(new DataInputStream(new FileInputStream("data" + File.separator + "switchbox.dot")));
while(true){
go = false;
if (!go){
route(m_editor.graph);
xdim = 0; ydim = 0; num_nets=0; num_pins=0;
movelist = new listnode();
xpos=0; ypos=0; moves=0;
for (int i=0;i<=19;i++){
for (int j=0;j<=19;j++){
board[i][j]=0;
}
}
go = true;
while(go){};
offscreenG.setColor(Color.black);
offscreenG.fillRect(0,0,this.size().width,this.size().height);
repaint();
}
}
}
catch(Exception e) {
System.out.println(e);
System.exit(0);
}
}
public void paint(Graphics g){
g.drawImage(offscreenImg,0,0,this);
}
public void update(Graphics g){
paint(g);
}
/**
* Perform a hacky post-processing on the graph so that
* it looks nice. This is a total hack to show how to
* manipulate the graph. Traverse the graph and send routables
* and unroutables to the back and color them funny.
* Figure out where to place "net" nodes and make them
* invisible.
*
* This routine could also be used to build some auxiliary
* data structure, but there are probably more elegant ways
* to do it...
*/
void hackPostProcess(Graph g) {
for(int i = 0; i < g.nodes.size(); i++) {
Node n = (Node)g.nodes.elementAt(i);
String type = getType(n);
if(type == null) {
n.rep.fill = Color.orange;
n.w = 10;
n.h = 10;
// System.out.println("XXX null type property");
/* ignore? */
}
else if(type.equals("net")) {
n.rep.show = false;
for(Enumeration e = n.out.elements(); e.hasMoreElements();) {
Node n2 = ((Edge)e.nextElement()).head;
}
}
else if(type.equals("terminal")) {
n.rep.fill = Color.blue;
}
else if(type.equals("routable")) {
n.rep.fill = Color.yellow;
}
else if(type.equals("unroutable")) {
n.rep.fill = Color.gray;
}
else {
// System.out.println("XXX unknown type");
/* ignore for now? */
}
}
}
void route(Graph g) {
listnode paths[] = new listnode[20];
int counter = 0;
int net[] = new int[100];
int position[][] = new int[100][2];
int pinlist[][] = new int[10][20];
int pinnums[]=new int[10];
int freshboard[][] = new int[20][20];
for(int i = 0; i < 19; i++){
paths[i]=null;
}
for(int i = 0; i < 9; i++){
pinnums[i]=0;
}
for(int i = 0; i < g.nodes.size(); i++) {
Node n = (Node)g.nodes.elementAt(i);
String type = getType(n);
if(type == null) {
}
else if(type.equals("net")) {
n.rep.show = false;
for(Enumeration e = n.out.elements(); e.hasMoreElements();) {
Node n2 = ((Edge)e.nextElement()).head;
int a = Integer.parseInt(n2.name.substring(1));
position[counter][0] = a;
int b = Character.digit(n2.name.charAt(0),16)-9;
position[counter][1] = b;
int c = Integer.parseInt(n.name.substring(1));
net[counter] = c;
if (iftrue((b==1|b==3)&(a>xdim)) == 1)
xdim = a;
if (iftrue((b==2|b==4)&(a>ydim)) == 1)
ydim = a;
num_nets = iftrue(net[counter]=num_nets)*net[counter];
counter ++;
}
}
}
// Build the circuit to be routed in grid format
xdim = xdim + 1;
ydim = ydim + 1;
// System.out.println(xdim);
// System.out.println(ydim);
// System.out.println(num_nets);
for (int i=0 ; i<= counter & net[i]!=0 ; i++){
int xindex = iftrue((position[i][1]==1)|(position[i][1]==3))*(position[i][0]);
xindex = xindex + iftrue(position[i][1]==4) * xdim;
int yindex = iftrue((position[i][1]==2)|(position[i][1]==4))*(position[i][0]);
yindex = yindex + iftrue(position[i][1]==3) * ydim;
board[yindex][xindex]=net[i];
pinlist[net[i]][pinnums[net[i]]*2]=yindex;
pinlist[net[i]][pinnums[net[i]]*2+1]=xindex;
pinnums[net[i]]++;
num_pins++;
}
for (int i=0;i<=ydim;i++){
for(int j=0;j<=xdim;j++){
freshboard[i][j]=board[i][j];
}
}
// show_board();
// show_pinlist(pinlist,pinnums);
// set up the screen
Font f = new Font("TimesRoman",Font.BOLD,18);
offscreenG.setFont(f);
int width = 10;
for (int k=1; k0){
// select pin to route
ypos = pinlist[i][(pinnums[i]-1)*2];
xpos = pinlist[i][(pinnums[i]-1)*2+1];
// System.out.println("Starting at "+ypos+", "+xpos);
// set up the board constraints
for (int j=0;j<=ydim;j++){
for (int k=0;k<=xdim;k++){
board[j][k]=freshboard[j][k]; //reset board
}
}
setupboard(i,paths);
for (int k=0;k<=xdim;k++){
board[0][k]=freshboard[0][k];
board[ydim][k]=freshboard[ydim][k];
if(second_time_around & board[ydim][k]==i){
board[ydim][k]=0;
}
if(second_time_around & board[0][k]==i){
board[0][k]=0;
}
}
for (int k=0;k<=ydim;k++){
board[k][0]=freshboard[k][0];
board[k][xdim]=freshboard[k][xdim];
if(second_time_around & board[k][xdim]==i){
board[k][xdim]=0;
}
if(second_time_around & board[k][0]==i){
board[k][0]=0;
}
}
// show_board();
// select where to route it to
int pos = findwheretorouteto(i);
int xpos1 = (pos-1)%(ydim+1);
int ypos1 = (pos-1)/(ydim+1);
// System.out.println("Found at"+ypos1+" "+xpos1);
// find a valid routing
int free_entry = firstfree(paths);
paths[free_entry]=routeab(ypos1,xpos1,i,paths);
// delete the pin(s) from the list of pins to route
pinnums[i]=pinnums[i]-1;
for(int k=0;k<=pinnums[i];k++){
int temp1 = pinlist[i][k*2];
int temp2 = pinlist[i][k*2+1];
if (temp1==paths[free_entry].ypos & temp2==paths[free_entry].xpos){
pinlist[i][k*2] = pinlist[i][(pinnums[i]-1)*2];
pinlist[i][k*2+1] = pinlist[i][(pinnums[i]-1)*2+1];
pinlist[i][(pinnums[i]-1)*2]=temp1;
pinlist[i][(pinnums[i]-1)*2+1]=temp2;
pinnums[i]=pinnums[i]-1;
break;
}
}
showpaths(paths);
repaint();
try{Thread.sleep(100);}
catch (InterruptedException e){}
// or else rip up for rerouting
}
routed = true;
for(int k=1;k0)
routed = false;
}
}
showpaths(paths);
repaint();
}
void makeborder(int x1,int y1,int x2,int y2,int wid){
Color c1 = new Color(140,140,140);
Color c2 = new Color(180,180,180);
Color c3 = new Color(220,220,220);
offscreenG.setColor(c2);
offscreenG.fillRect(x1,y1,wid,y2-y1);
offscreenG.fillRect(x1,y1,x2-x1,wid);
offscreenG.fillRect(x1,y2-wid,x2-x1,y2);
offscreenG.fillRect(x2-wid,y1,x2,y2-y1);
offscreenG.setColor(c3);
for (int i=0;i<=4;i++){
offscreenG.setColor(c3);
offscreenG.drawLine(x1+i,y1+i,x1+i,y2-i);
offscreenG.drawLine(x1+i,y1+i,x2-i,y1+i);
offscreenG.drawLine(x2-wid+i,y1+wid-i,x2-wid+i,y2-wid+i);
offscreenG.drawLine(x1+wid-i,y2-wid+i,x2-wid+i,y2-wid+i);
offscreenG.setColor(c1);
offscreenG.drawLine(x2-i,y1+i,x2-i,y2-i);
offscreenG.drawLine(x1+i,y2-i,x2-i,y2-i);
offscreenG.drawLine(x1+wid-i,y1+wid-i,x1+wid-i,y2-wid+i);
offscreenG.drawLine(x1+wid-i,y1+wid-i,x2-wid+i,y1+wid-i);
}
}
void showpaths(listnode paths[]){
listnode a;
int i=0;
int width=10;
while (paths[i]!=null){
// System.out.println(paths[i].net);
for(a=paths[i];a.link!=null;a=a.link){
int xpos1 = a.xpos*mag+xoff;
int ypos1 = a.ypos*mag+yoff;
int xpos2 = a.link.xpos*mag+xoff;
int ypos2 = a.link.ypos*mag+yoff;
if (ypos1 "+xpos1+","+ypos1);
// System.out.println(p_left+" "+p_straight+" "+p_right);
if (!(p_straight>=1|p_right>=1|p_left>=1)){
// System.out.println("1");
// move backwards
board[ypos][xpos]= -1;
xpos = xpos - xdir;
ypos = ypos - ydir;
movelist = movelist.link;
moves--;
}
else if (st){ // if a straight move is forced
// System.out.println("2");
// move forwards
movelist.up = Math.abs(ydir) == 1;
movepos(xdir,ydir,netnumber);
}
else if (p_straight==1 & isgoodmove(xpos1,ypos1,xdir,ydir)){
// System.out.println("3");
// move forwards
movelist.up = Math.abs(ydir) == 1;
movelist.block = false;
movepos(xdir,ydir,netnumber);
}else if(p_right==1 & isgoodmove(xpos1,ypos1,-ydir,xdir)){
// System.out.println("4");
// change direction and move
temp = xdir;
xdir = -ydir;
ydir = temp;
movelist.up = Math.abs(ydir) == 1;
movelist.block = true;
movepos(xdir,ydir,netnumber);
}else if(p_left==1 & isgoodmove(xpos1,ypos1,ydir,-xdir)){
// System.out.println("5");
// change direction and move
temp = xdir;
xdir = ydir;
ydir = -temp;
movelist.up = Math.abs(ydir) == 1;
movelist.block = true;
movepos(xdir,ydir,netnumber);
}else{
// System.out.println("6");
if (p_straight==1){
// move forwards
movelist.up = Math.abs(ydir) == 1;
movelist.block = false;
movepos(xdir,ydir,netnumber);
}else if(p_right==1){
// change direction and move
temp = xdir;
xdir = -ydir;
ydir = temp;
movelist.up = Math.abs(ydir) == 1;
movelist.block = true;
movepos(xdir,ydir,netnumber);
}else if(p_left==1){
// change direction and move
temp = xdir;
xdir = ydir;
ydir = -temp;
movelist.up = Math.abs(ydir) == 1;
movelist.block = true;
movepos(xdir,ydir,netnumber);
}
}
}
if (xpos==0 | ypos==0 | xpos==xdim | ypos==ydim){
movelist.block=false;
}else{
movelist.block=true;
}
return(movelist);
}
boolean forcestraight(int xdir, int ydir, int xpos1, int ypos1){
// don't turn if the resulting via blocks a pin's entry
if (xpos==1 & board[ypos][0] != 0 & Math.abs(ydir) == 1){
return(true);
}else if(ypos==1 & board[0][xpos] != 0 & Math.abs(xdir) == 1){
return(true);
}else if(xpos==xdim-1 & board[ypos][xdim] != 0 & Math.abs(ydir) == 1){
return(true);
}else if(ypos==ydim-1 & board[ydim][xpos] != 0 & Math.abs(xdir) == 1){
return(true);
}else if (xpos==1 & xpos1==0 & xdir == 1){
return(true);
}else if(ypos==1 & ypos1==0 & ydir == 1){
return(true);
}else if(xpos==xdim-1 & xpos1==xdim & xdir == -1){
return(true);
}else if(ypos==ydim-1 & ypos1==ydim & ydir == -1){
return(true);
}else{
return(false);
}
}
void movepos(int xdir, int ydir, int netnumber){
xpos = xpos + xdir;
ypos = ypos + ydir;
int i=0;
moves++;
listnode a = new listnode();
listnode b = new listnode();
for (b=movelist;b!=null;b=b.link){
if (b.xpos == xpos && b.ypos == ypos){
movelist=b;
moves=moves-i;
return;
}
i++;
}
a.xpos = xpos;
a.ypos = ypos;
a.net = netnumber;
a.up = true;
a.link = movelist;
movelist = a;
}
int ispossiblemove(int xd,int yd, int netnumber){
int at_pos;
int x = xpos, y = ypos;
boolean up;
if (Math.abs(yd)==1){
up = true;
}else{
up = false;
}
at_pos = board[y+yd][x+xd];
if (at_pos == -1){
return(0);
}else if (at_pos == 0 & x+xd>0 & y+yd>0 & x+xd=0)&(y>=0)&(x<=xdim)&(y<=ydim))
return true;
else
return false;
}
/**
* The index where "dot" information is stored.
*/
static int s_dotIndex = AttributeManager.getIndex("Dot");
/**
* Get the "type" field of the node.
*/
String getType(Node n) {
DotInfo info = (DotInfo)n.getAttr(s_dotIndex);
if(info != null) {
return (String)info.props.get("type");
}
else {
return null;
}
}
public static int iftrue(boolean b){
if (b)
return(1);
else
return(0);
}
public boolean mouseDown(Event evt, int x, int y){
if (go==false){
go = true;
}else{
go = false;
}
return true;
}
public void show_board(){
for (int a_count=0; a_count<=9; a_count++){
for (int b_count=0; b_count<=9; b_count++){
System.out.print(board[a_count][b_count]+" ");
}
System.out.println();
}
System.out.println(" ");
}
public static void show_pinlist(int pinlist[][],int pinnums[]){
for (int a_count=1; a_count<=7; a_count++){
System.out.print(a_count+" "+pinnums[a_count]+": ");
for (int b_count=0; b_count