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.

	    --------------------------------------------

     The code below handles all eight octants, with some attempt made to
     minimize the number of Java statements.

	    Approach used to solve the problem:

     Original formula from class:
          F'(x+1, y) = F(x,y) + m
          if (F'>0.5) y++;

    The approach used here was to think of F(x,y) as 2*abs(x2-x1) times the 
    value from the formula in class. Thus, 2*abs(y2-y1) (since m=dy/dx) is 
    added to F every x step, and it is compared with (x2-x1) rather than .5
    to decide to change y.

    This code was generalized to eight octants by using variables to indicate
    the sign on x, sign on y, and whether x and y have to be flipped.
    This is sufficient to map the problem to the equivalent of the first octant
    (with minor changes, i.e. y+=ysign vs. y++, different x comparisons, 
    swapping x and y while plotting, etc.)

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

      int xsign = ((x2>x1) ? 1: -1);
      int dx = (x2 - x1)*xsign;

      int ysign = ((y2>y1) ? 1: -1);
      int dy = (y2 - y1)*ysign;

      boolean xyflipped = (dy>dx);
      if (xyflipped) { 
	int a=x1; x1=y1; y1=a; a=x2; x2=y2; y2=a;
	a = dy; dy=dx; dx=a; a=ysign; ysign=xsign; xsign=a;
      }

      int twody = 2*dy; int twodx = 2*dx;

      int x=x1; int y=y1; int error = 0;

      while ( ((xsign==1)&&(x<=x2)) || ((xsign==-1)&&(x>=x2))) {
	
	if (!xyflipped) view.setPixel(x,y); else view.setPixel(y,x);

	x+=xsign;
	if ((error += twody)> dx) {
	  y+=ysign;
	  error -= twodx;
	}
      }
    }


}