package squidpony.squidmath;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Provides a means to generate Bresenham lines in 2D and 3D.
 *
 * @author Eben Howard - http://squidpony.com - howard@squidpony.com
 * @author Lewis Potter
 */
public class Bresenham {

    /**
     * Prevents any instances from being created
     */
    private Bresenham() {
    }

    /**
     * Generates a 2D Bresenham line between two points.
     *
     * @param a the starting point
     * @param b the ending point
     * @return
     */
    public static Queue<Coord> line2D(Coord a, Coord b) {
        return line2D(a.x, a.y, b.x, b.y);
    }

    /**
     * Generates a 2D Bresenham line between two points.
     *
     * @param startX the x coordinate of the starting point
     * @param startY the y coordinate of the starting point
     * @param endX the x coordinate of the ending point
     * @param endY the y coordinate of the ending point
     * @return
     */
    public static Queue<Coord> line2D(int startX, int startY, int endX, int endY) {
        Queue<Coord> line = new LinkedList<>();
        Queue<Coord3D> found = line3D(startX, startY, 0, endX, endY, 0);
        while (!found.isEmpty()) {
            line.offer(found.poll());
        }
        return line;
    }

    /**
     * Generates a 3D Bresenham line between two points.
     *
     * @param a Coord to start from. This will be the first element of the list
     * @param b Coord to end at. This will be the last element of the list.
     * @return A list of points between a and b.
     */
    public static Queue<Coord3D> line3D(Coord3D a, Coord3D b) {
        return line3D(a.x, a.y, a.z, b.x, b.y, b.z);
    }

    /**
     * Generates a 3D Bresenham line between the given coordinates.
     *
     * @param startx the x coordinate of the starting point
     * @param starty the y coordinate of the starting point
     * @param startz the z coordinate of the starting point
     * @param endx the x coordinate of the starting point
     * @param endy the y coordinate of the starting point
     * @param endz the z coordinate of the starting point
     * @return
     */
    public static Queue<Coord3D> line3D(int startx, int starty, int startz, int endx, int endy, int endz) {
        Queue<Coord3D> result = new LinkedList<>();

        int dx = endx - startx;
        int dy = endy - starty;
        int dz = endz - startz;

        int ax = Math.abs(dx) << 1;
        int ay = Math.abs(dy) << 1;
        int az = Math.abs(dz) << 1;

        int signx = (int) Math.signum(dx);
        int signy = (int) Math.signum(dy);
        int signz = (int) Math.signum(dz);

        int x = startx;
        int y = starty;
        int z = startz;

        int deltax, deltay, deltaz;
        if (ax >= Math.max(ay, az)) /* x dominant */ {
            deltay = ay - (ax >> 1);
            deltaz = az - (ax >> 1);
            while (true) {
                result.offer(new Coord3D(x, y, z));
                if (x == endx) {
                    return result;
                }

                if (deltay >= 0) {
                    y += signy;
                    deltay -= ax;
                }

                if (deltaz >= 0) {
                    z += signz;
                    deltaz -= ax;
                }

                x += signx;
                deltay += ay;
                deltaz += az;
            }
        } else if (ay >= Math.max(ax, az)) /* y dominant */ {
            deltax = ax - (ay >> 1);
            deltaz = az - (ay >> 1);
            while (true) {
                result.offer(new Coord3D(x, y, z));
                if (y == endy) {
                    return result;
                }

                if (deltax >= 0) {
                    x += signx;
                    deltax -= ay;
                }

                if (deltaz >= 0) {
                    z += signz;
                    deltaz -= ay;
                }

                y += signy;
                deltax += ax;
                deltaz += az;
            }
        } else if (az >= Math.max(ax, ay)) /* z dominant */ {
            deltax = ax - (az >> 1);
            deltay = ay - (az >> 1);
            while (true) {
                result.offer(new Coord3D(x, y, z));
                if (z == endz) {
                    return result;
                }

                if (deltax >= 0) {
                    x += signx;
                    deltax -= az;
                }

                if (deltay >= 0) {
                    y += signy;
                    deltay -= az;
                }

                z += signz;
                deltax += ax;
                deltay += ay;
            }
        }
        return result;
    }
}

@@ -1170,24 +1170,18 @@
 dY, 0);%0A
-        
+%09%09
 while (!
@@ -1203,31 +1203,31 @@
 ) %7B%0A
-            line.offer(
+%09%09%09final Coord3D c3d = 
 foun
@@ -1238,29 +1238,78 @@
 ll()
-)
 ;%0A
-        %7D%0A        
+%09%09%09line.offer(/* translate to 2D */ Coord.get(c3d.x, c3d.y));%0A%09%09%7D%0A%09%09
 retu

Return instances of Coord instead of Coord3d in Bresenham::line2D. That's less surprising for callers that call methods like 'Collection::contains(Object)' on the result or pours the result into a Collection<Coord>