import display.*;


//The class that the students will fill up with the correct algorithm.

public class Bresenham {

    /*
      Inputs: x1, y1, x2 and y2 -- the endpoints of the line. The line
				   stretches from (x1, y1) to (x2, y2)
              Grid view         -- an object representing the display

      Outputs: none, just draw the line

      Something useful: in order to draw the line, you must set a
	 	 	series of individual pixels. You can do this
	 	 	by making a call to the setPixel method of the
	 	 	Grid object. In other words, the command
	 	 	         view.setPixel(3,4); 
			would turn the pixel at position (3, 4) black.


      NOTE: If you want to have any auxiliary methods (helpers), you
	    must make sure to declare them "static" as well.

     */
    public static void BresenhamAlgorithm(int x1, int y1, 
					  int x2, int y2, Grid view) {

	int newfXY;

	// dely/delx = slope from endpoint to endpoint
	int delx = x2-x1;
	int dely = y2-y1;
	int y = y1;
	int x = x1;

	// xsign and ysign determine whether to add 1 or -1 while iterating
	int xsign = 1;
	int ysign = 1;
	if (delx < 0) {xsign = -1;}
	if (dely < 0) {ysign = -1;}


	/* Normally, you use: fXY = y - m*x - (y1- m*x1), and see
	       if -fXY > 0.5.  However, to use purely integer
	       arithmetic, you have to fix two non-integer values:
	       m and 0.5

	       Thus, the following calculations are performed:

	       fXY = y - (dely/delx)*x - (y1 - (dely/delx)*x1)
	       delx * fXY = delx*y - dely*x - delx*y1 + dely*x1
	       -delx * fXY = -(delx*y - dely*x - delx*y1 + dely*x1) ?> delx/2 
	       -2*delx*fXY = -2 * (delx*y - dely*x -delx*y1 + dely*x1) ?> delx

	     */

	if (java.lang.Math.abs(delx) >= java.lang.Math.abs(dely)){
	    if (delx > 0){
		//     from -45 to 45 degrees
		for (x = x1; x < x2; x++){	
		newfXY = -2 * (y*delx - dely*x - delx*y1 + dely*x1);
		newfXY *= ysign * xsign;
		if (newfXY > delx){    // equivalent to -fXY > 1/2
		    y += ysign;} // ysign == -1 if dely <0
		view.setPixel(x,y);
	    }
		view.setPixel(x2, y2);}
	    else{
		// from 135 to 225 degrees
		for (x = x1; x > x2; x--){	
		newfXY = -2 * (y*delx - dely*x - delx*y1 + dely*x1);
		if (java.lang.Math.abs(newfXY) > java.lang.Math.abs(delx)){    
		    // equivalent to -fXY > 1/2
		    y += ysign;} // ysign == -1 if dely < 0
		view.setPixel(x,y);
	    }
		view.setPixel(x2, y2);}


	    }	
	else{
	    if (dely > 0){    // from 45 to 135 degrees
		for (y = y1; y < y2; y++){	
		    newfXY = -2 * (y*delx - dely*x - delx*y1 + dely*x1);
		    newfXY *= ysign * xsign;
		  if (java.lang.Math.abs(newfXY) > java.lang.Math.abs(dely)){
			x += xsign;} // xsign == -1 if delx < 0
		    view.setPixel(x,y);
		}
		view.setPixel(x2, y2);}
	    else{   // from 225 to 315 (= -45) degrees
		for (y = y1; y > y2; y--){	
		    newfXY = -2 * (y*delx - dely*x - delx*y1 + dely*x1);
		    if (java.lang.Math.abs(newfXY) > java.lang.Math.abs(dely)){    
			// equivalent to -fXY > 1/2
			x += xsign;} // xsign == -1 if delx < 0
		    view.setPixel(x,y);
		}
		view.setPixel(x2, y2);}



	    }

	//For debugging:
	System.out.println("Entering BresenhamAlgorithm");

    }
}