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) {

	// ***** YOUR CODE HERE *****

	//make sure (x1,y1) is left most point
	int temp;
	if (x2 < x1) {
	    temp = x1; x1 = x2; x2 = temp;
	    temp = y1; y1 = y2; y2 = temp;
	}

	//plot first point
	view.setPixel(x1,y1);

	int dx, dy;
	dx = x2-x1;
	dy = y2-y1;
	
	int a,b,yinc;
	if (dy < 0) {yinc = -1; dy = -dy;}
	else yinc = 1;
	boolean xstep;
	//vertical line
	if (dx == 0) {
	    if (y1>y2) for (a=y1-1;a>=y2;a--) view.setPixel(x1,a);
	    else for (a=y1+1;a<=y2;a++) view.setPixel(x1,a);
	}
	//horizontal line
	else if (dy == 0) for (a=x1+1;a<=x2;a++) view.setPixel(a,y1);
	//dx=dy
	else if (dy == dx) for (a=x1+1,b=y1+yinc;a<=x2;a++,b+=yinc) view.setPixel(a,b);
	//else begin Bresenham
	else {
	    if (dy/dx >= 1) {a = dy; b = dx; xstep = false;}
	    else {a = dx; b = dy; xstep = true;}

	    int p;
	    p = 2*b-a;

	    int k,x,y;
	    for (k=0,x=x1,y=y1;k<a;k++) {
		if (p <= 0) {
		    if (xstep == true) ++x;
		    else y += yinc;
		    view.setPixel(x,y);
		    p = p + 2*b;
		}
		else {
		    y += yinc; ++x;
		    view.setPixel(x,y);
		    p = p + 2*b - 2*a;
		}
	    }
	}
	//For debugging:
	System.out.println("Entering BresenhamAlgorithm");

    }
}