// Mark Huang <markman@mit.edu>
// MIT 6.837 Fall 1999
// Assignment 2

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 *****

	/* Bresenham error equation is
	 * e = m*x + b - y                                       <>= 0.5
	 * e = y1 + (x-x1)*(y2-y1)/(x2-x1) - y                   <>= 0.5
         * E = 2*(x2-x1)*e = 2*((y1-y)*(x2-x1) + (x-x1)*(y2-y1)) <>= (x2-x1)
	 * E(x+1,y) = E(x,y) + 2*(y2-y1)
	 * E(x,y+1) = E(x,y) - 2*(x2-x1)
	 */

	int x = x1, y = y1;
	int dx = x2 - x1, dy = y2 - y1;
	int xinc = 1, yinc = 1;
	int E = 0, i = 0;

	// Keep dx positive, but remember that we should increment left instead
	if (dx < 0) {
	    xinc = -1;
	    dx = -dx;
	} 

	// Keep dy positive, but remember that we should increment down instead
	if (dy < 0) {
	    yinc = -1;
	    dy = -dy;
	}

	if (dx > dy) {
	    // If the magnitude of the slope is between 0 and 1, loop over x
	    for (i = 0; i <= dx; i++) {
		while (E > dx) {
		    y += yinc;
		    E -= 2*dx;
		}
		// System.out.println("("+x+", "+y+")");
		view.setPixel(x, y);
		x += xinc;
		E += 2*dy;
	    }
	} else {
	    // Otherwise, loop over y
	    for (i = 0; i <= dy; i++) {
		while (E > dy) {
		    x += xinc;
		    E -= 2*dy;
		}
		// System.out.println("("+x+", "+y+")");
		view.setPixel(x, y);
		y += yinc;
		E += 2*dx;
	    }
	}
    }

    /*
    public static void main(String[] args) {
	try {
	    BresenhamAlgorithm(Integer.parseInt(args[0]), 
			       Integer.parseInt(args[1]), 
			       Integer.parseInt(args[2]), 
			       Integer.parseInt(args[3]), null);
	} catch (ArrayIndexOutOfBoundsException e) {
	    System.err.println("Usage: java Bresenham [x1] [y1] [x2] [y2]");
	}

	System.exit(0);
    }
    */
}