// behavior file for generating the graph for the
// graph edge linking algorithm

GraphGenerator {
    {{  
	GraphGenerator(PixelCoord _src, PixelCoord _target) {
	    src = _src;
	    target = _target;
	    lineequation = new LineEquation(_src, _target);
	    generatedGraph = new Graph(new GraphNode_List());
	    generateGraph();
	}
	
	public void generateGraph() {
	    // first add edges for the source and destination
	    int direction = lineequation.get_direction();
	    lineequation.processSource(generatedGraph, src, direction);
	    lineequation.processDest(generatedGraph, target, direction);
	    
	    // add edges along the line
	    if (!lineequation.isVerticalLine())
		lineequation.processNonVerticalEdges(generatedGraph, src.get_x(), target.get_x());
	    else
		lineequation.processVerticalEdges(generatedGraph, src.get_y(), target.get_y());
	    
	}

    }}
}


LineEquation {

    {{
	// print debug info
	boolean debug = false;

	// true if it's a vertical line
	boolean _isVerticalLine=false;
	

	// the defintion for direction
	static int N = 0;
	static int S = 1;	
	static int E = 2;	
	static int W = 3;
	static int NE = 4;
	static int NW = 5;
	static int SE = 6;
	static int SW = 7;
	
	LineEquation(PixelCoord _src, PixelCoord _target) {
	    float deltaY = _target.get_y() - _src.get_y();
	    float deltaX = _target.get_x() - _src.get_x();
	    
	    if (deltaX == 0) {
		_isVerticalLine = true;
		Constant = _target.get_x();
		if (debug) System.out.println("New Vertical Line");
	    } else {
		Slope = deltaY/deltaX;
		Constant = _src.get_y() - Slope * _src.get_x();
		if (debug) System.out.println("New Line Equation with slope="
					      +Slope+" const="+Constant);
	    }
	    
	    // determine the direction of the path

	    // if delta y is greater than 0 then  we're going south
	    if (deltaY >= 0) {

		// deltaY dominate so we decide between vertical directions
		if (deltaX >= 0 && deltaY > deltaX)
		    direction = S;
		if (deltaX < 0 && deltaY >= deltaX*-1)
		    direction = S;

		// the deltaX dominate so we choose between horizontal directions
		if (deltaX > 0 && deltaY <= deltaX)
		    direction = E;
		if (deltaX < 0 && deltaY <= deltaX*-1)
		    direction = W;

		// else deltaY < 0  
	    } else {
		float posDeltaY = deltaY*-1;

		// deltaY dominate so we decide between vertical directions
		if (deltaX >= 0 && posDeltaY > deltaX)
		    direction = N;
		if (deltaX < 0 && posDeltaY >= deltaX*-1)
		    direction = N;

		// the deltaX dominate so we choose between horizontal directions
		if (deltaX > 0 && posDeltaY <= deltaX)
		    direction = E;
		if (deltaX < 0 && posDeltaY <= deltaX*-1)
		    direction = W;
	    }
	    
	    if (debug) System.out.println("direction = " + direction);

	}

	boolean isVerticalLine() {
	    return _isVerticalLine;
	}
	
	float getY(float x) {
	    float floatX = (float) x;
	    float floatY = Slope * floatX + Constant;
	    if (debug) System.out.println("x="+x+"y="+floatY);
	    return floatY;
	}
	

	protected void processSource(Graph graph, PixelCoord src, int direction) {
	    PixelCoord otherSide=null;

	    if (direction == N) {
		otherSide = PixelCoord.parse("(" + src.get_x() + ","+(src.get_y() +1) +")" );
	    } else if (direction == S) {
		otherSide = PixelCoord.parse("(" + src.get_x() + ","+(src.get_y() -1) +")" );		
	    } else if (direction == W) {
		otherSide = PixelCoord.parse("(" + (src.get_x()+1) + ","+src.get_y() +")" );				
	    } else if (direction == E) {
		otherSide = PixelCoord.parse("(" + (src.get_x()-1) + ","+src.get_y() +")" );
	    }
	    // add the edges
	    graph.get_graphnode_list().addElement(new SourceNode(src, otherSide));
	    graph.get_graphnode_list().addElement(new SourceNode(otherSide, src));	    
	}

	protected void processDest(Graph graph, PixelCoord src, int direction) {
	    PixelCoord otherSide=null;

	    if (direction == N) {
		otherSide = PixelCoord.parse("(" + src.get_x() + ","+(src.get_y() -1) +")" );
	    } else if (direction == S) {
		otherSide = PixelCoord.parse("(" + src.get_x() + ","+(src.get_y() +1) +")" );		
	    } else if (direction == W) {
		otherSide = PixelCoord.parse("(" + (src.get_x()-1) + ","+src.get_y() +")" );				
	    } else if (direction == E) {
		otherSide = PixelCoord.parse("(" + (src.get_x()+1) + ","+src.get_y() +")" );
	    }
	    // add the edges
	    graph.get_graphnode_list().addElement(new TargetNode(src, otherSide));
	    graph.get_graphnode_list().addElement(new TargetNode(otherSide, src));	    
	}


	public void processVerticalEdges(Graph graph, int starty, int endy){
	    if (direction != N && direction != S) 
		System.out.println("Error for processing vertical edges, no vertical direction!");

	    int xval = (int)Constant;
	    int begin; 
	    int finish;
	    
	    if (starty > endy) {
		begin = endy;
		finish = starty;
	    } else {
		begin = starty;
		finish = endy;
	    }	    
	    
	    for (int y = begin; y < finish; y++) {
		processPoint(graph, xval, y);		
	    }
	    int width = 2;
	    processLastPoint(graph, xval, finish, width);
	}

	public void processNonVerticalEdges(Graph graph, int startx, int endx){

	    int beginx; 
	    int finishx;
	    
	    if (startx > endx) {
		beginx = endx;
		finishx = startx;
	    } else {
		beginx = startx;
		finishx = endx;
	    }
	    
	    if (debug) System.out.println("beginx = " + beginx + " finishx = " + finishx);
	    
	    // loop through each of the pixels in the line connecting the source and
	    // destination
	    for (int x = beginx; x < finishx; x++) {
		
		
		// number of steps for each delta x = 1
		float stepVal = 1/abs(Slope);
		float runningVal = (float)x;
		int steps = (int) abs(Slope);
		
		if (debug) System.out.println("stepval = " + stepVal 
					      + " runningVal = " + runningVal + " steps = " + steps);
		
		for (int s = 0; s <= steps ; s++) {
		    int yval = (int)getY(runningVal);
		    runningVal = runningVal + stepVal;
		    
		    if (debug) System.out.println("yval=" + yval + " runningval="+runningVal);
		    // for each point add edges
		    processPoint(graph, x, yval);
		}
		
	    }

	    int width = 2;
	    processLastPoint(graph, finishx, (int)getY(finishx), width);
	    
	}
    
	public void processLastPoint(Graph graph, int x, int yval, int width) {
	    addLeftEdge(graph,x, yval);
	    for (int v = 1; v < width; v++) {
		if (direction == N || direction == S) {
		    addLeftEdge(graph,x+v, yval);
		    addLeftEdge(graph,x-v, yval);
		} else if (direction == W || direction == E) {
		    addLeftEdge(graph,x, yval+v);
		    addLeftEdge(graph,x, yval-v);
		}
	    }
	    addRightEdge(graph, x, yval, width);
	    
	}
	
	public void processPoint(Graph graph, int x, int yval) {
	    int width = 2;

	    addIntermediatePoint(graph,x, yval);
	    for (int v = 1; v < width; v++) {
		if (direction == N || direction == S) {
		    addIntermediatePoint(graph,x+v, yval);
		    addIntermediatePoint(graph,x-v, yval);
		} else if (direction == W || direction == E) {
		    addIntermediatePoint(graph,x, yval+v);
		    addIntermediatePoint(graph,x, yval-v);
		}
	    }
	    addRightEdge(graph, x, yval, width);
	}

	public void addLeftEdge(Graph graph, int x, int yval) {

	    PixelCoord src = PixelCoord.parse("("+(x)+","+yval+")");
	    PixelCoord parallel = null;
	    
	    if (direction == N) {
		parallel = PixelCoord.parse("(" + (x-1) + ","+ yval +")" );
	    } else if (direction == S) {
		parallel = PixelCoord.parse("(" + (x+1) + ","+ yval +")" );
	    } else if (direction == W) {
		parallel = PixelCoord.parse("(" + x + ","+ (yval+1) +")" );
	    } else if (direction == E) {
		parallel = PixelCoord.parse("(" + x + ","+ (yval-1) +")" );
	    }

	    // add the edges
	    graph.get_graphnode_list().addElement(new IntermediateNode(parallel, src));	    
	
	    if (debug) {
		System.out.print("Adding right edge:");
		PrintVisitor pv = new PrintVisitor(System.out);
		src.universal_trv0(pv);
		parallel.universal_trv0(pv);
		pv.finish();
		System.out.println();
	    }

	}
	public void addRightEdge(Graph graph, int x, int yval, int width) {

	    PixelCoord src = null;
	    PixelCoord parallel = null;
	    
	    if (direction == N) {
		src = PixelCoord.parse("("+(x+width-1)+","+yval+")");
		parallel = PixelCoord.parse("(" + (x+width) + ","+ yval +")" );
	    } else if (direction == S) {
		src = PixelCoord.parse("("+(x-width+1)+","+yval+")");
		parallel = PixelCoord.parse("(" + (x-width) + ","+ yval +")" );
	    } else if (direction == W) {
		src = PixelCoord.parse("("+x+","+(yval-width+1)+")");
		parallel = PixelCoord.parse("(" + x + ","+ (yval-width) +")" );
	    } else if (direction == E) {
		src = PixelCoord.parse("("+x+","+(yval+width-1)+")");
		parallel = PixelCoord.parse("(" + x + ","+ (yval+width) +")" );
	    }

	    // add the edges
	    graph.get_graphnode_list().addElement(new IntermediateNode(src, parallel));	    
	
	    if (debug) {
		System.out.print("Adding right edge:");
		PrintVisitor pv = new PrintVisitor(System.out);
		src.universal_trv0(pv);
		parallel.universal_trv0(pv);
		pv.finish();
		System.out.println();
	    }

	}

	public void addIntermediatePoint(Graph graph, int x, int yval) {

	    PixelCoord src = PixelCoord.parse("("+x+","+yval+")");
	    PixelCoord otherSide=null;
	    PixelCoord parallel = null;
	    
	    if (direction == N) {
		otherSide = PixelCoord.parse("(" + x + ","+ (yval -1) +")" );
		parallel = PixelCoord.parse("(" + (x-1) + ","+ yval +")" );
	    } else if (direction == S) {
		otherSide = PixelCoord.parse("(" + x + ","+(yval +1) +")" );		
		parallel = PixelCoord.parse("(" + (x+1) + ","+ yval +")" );
	    } else if (direction == W) {
		otherSide = PixelCoord.parse("(" + (x-1) + ","+yval +")" );				
		parallel = PixelCoord.parse("(" + x + ","+ (yval+1) +")" );
	    } else if (direction == E) {
		otherSide = PixelCoord.parse("(" + (x+1) + ","+yval +")" );
		parallel = PixelCoord.parse("(" + x + ","+ (yval-1) +")" );
	    }
	    // add the edges
	    graph.get_graphnode_list().addElement(new IntermediateNode(src, otherSide));
	    graph.get_graphnode_list().addElement(new IntermediateNode(otherSide, src));	    
	    graph.get_graphnode_list().addElement(new IntermediateNode(parallel, src));	    
	
	    if (debug) {
		System.out.print("Adding edges for nodes:");
		PrintVisitor pv = new PrintVisitor(System.out);
		src.universal_trv0(pv);
		otherSide.universal_trv0(pv);
		parallel.universal_trv0(pv);
		pv.finish();
		System.out.println();
	    }
	}
	
	public static float abs(float x) { 
	    if (x < 0) return x*-1;
	    return x;
	}
    }}
    
}


SourceNode {

    {{
	public SourceNode(PixelCoord left, PixelCoord right) {
	    super();
	    set_edgeloc(new EdgeLoc(left, right));
	    set_nodedata(new NodeData(0, null));
	}
    }}
}

TargetNode {

    {{
	public TargetNode(PixelCoord left, PixelCoord right) {
	    super();
	    set_edgeloc(new EdgeLoc(left, right));
	    set_nodedata(new NodeData(0, null));
	}
    }}
}

IntermediateNode {

    {{
	public IntermediateNode(PixelCoord left, PixelCoord right) {
	    super();
	    set_edgeloc(new EdgeLoc(left, right));
	    set_nodedata(new NodeData(0, null));
	}
    }}
}