package ij.gui;
import ij.*;
import ij.process.*;
import ij.plugin.WandToolOptions;
import java.awt.*;

/** This class implements ImageJ's wand (tracing) tool.
  * The wand selects pixels of equal or similar value or thresholded pixels
  * forming a contiguous area.
  * The wand creates selections that have only one boundary line (inner holes
  * are not excluded from the selection). There may be holes at the boundary,
  * however, if the boundary line touches the same vertex twice (both in
  * 4-connected and 8-connected mode).
  *
  * Version 2009-06-01  (code refurbished; tolerance, 4- & 8-connected options added)
  */
public class Wand {
    /** Wand operation type: trace outline of 4-connected pixels */
    public final static int FOUR_CONNECTED = 4;
    /** Wand operation type: trace outline of 8-connected pixels */
    public final static int EIGHT_CONNECTED = 8;
    /** Wand operation type similar to  that of ImageJ 1.42p and before; for backwards
      * compatibility.
      * In this mode, no checking is done whether the foreground or the background
      * gets selected; four- or 8-connected behaviour depends on foreground/background
      * and (if no selection) on whether the initial pixel is on a 1-pixel wide line. */
    public final static int LEGACY_MODE = 1;    
    /** The number of points in the generated outline. */
    public int npoints;
    private int maxPoints = 1000; // will be increased if necessary
    /** The x-coordinates of the points in the outline.
        A vertical boundary at x separates the pixels at x-1 and x. */
    public int[] xpoints = new int[maxPoints];
    /** The y-coordinates of the points in the outline.
        A horizontal boundary at y separates the pixels at y-1 and y. */
    public int[] ypoints = new int[maxPoints];

    private final static int THRESHOLDED_MODE = 256; //work on threshold
    private ImageProcessor ip;
    private byte[] bpixels;
    private int[] cpixels;
    private short[] spixels;
    private float[] fpixels;
    private int width, height;
    private float lowerThreshold, upperThreshold;
    private int xmin;                   // of selection created
    private boolean exactPixelValue;    // For color, match RGB, not gray value
    private static boolean allPoints;  // output contains intermediate points


    /** Constructs a Wand object from an ImageProcessor. */
    public Wand(ImageProcessor ip) {
        this.ip = ip;
        Object pixels = ip.getPixels();
        if (pixels instanceof byte[])
            bpixels = (byte[])pixels;
        else if (pixels instanceof int[])
            cpixels = (int[])pixels;
        else if (pixels instanceof short[])
            spixels = (short[])pixels;
        else if (pixels instanceof float[])
            fpixels = (float[])pixels;
        width = ip.getWidth();
        height = ip.getHeight();
    }



    /** Traces an object defined by lower and upper threshold values.
      * 'mode' can be FOUR_CONNECTED or EIGHT_CONNECTED.
      * ('LEGACY_MODE' is also supported and may result in selection of
      * interior holes instead of the thresholded area if one clicks left
      * of an interior hole).
      * The start coordinates must be inside the area or left of it.
      * When successful, npoints>0 and the boundary points can be accessed
      * in the public xpoints and ypoints fields. */
    public void autoOutline(int startX, int startY, double lower, double upper, int mode) {
        lowerThreshold = (float)lower;
        upperThreshold = (float)upper;
        autoOutline(startX, startY, 0.0, mode|THRESHOLDED_MODE);
    }

    /** Traces an object defined by lower and upper threshold values or an
      * interior hole; whatever is found first ('legacy mode').
      * For compatibility with previous versions of ImageJ.
      * The start coordinates must be inside the area or left of it.
      * When successful, npoints>0 and the boundary points can be accessed
      * in the public xpoints and ypoints fields. */
    public void autoOutline(int startX, int startY, double lower, double upper) {
        autoOutline(startX, startY, lower, upper, THRESHOLDED_MODE|LEGACY_MODE);
    }

    /** This is a variation of legacy autoOutline that uses int threshold arguments. */
    public void autoOutline(int startX, int startY, int lower, int upper) {
        autoOutline(startX, startY, (double)lower, (double)upper, THRESHOLDED_MODE|LEGACY_MODE);
    }

    /** Traces the boundary of an area of uniform color, where
      * 'startX' and 'startY' are somewhere inside the area.
      * When successful, npoints>0 and the boundary points can be accessed
      * in the public xpoints and ypoints fields.
      * For compatibility with previous versions of ImageJ only; otherwise
      * use the reliable method specifying 4-connected or 8-connected mode
      * and the tolerance. */
    public void autoOutline(int startX, int startY) {
        autoOutline(startX, startY, 0.0, LEGACY_MODE);
    }

    /** Traces the boundary of the area with pixel values within
      * 'tolerance' of the value of the pixel at the starting location.
      * 'tolerance' is in uncalibrated units.
      * 'mode' can be FOUR_CONNECTED or EIGHT_CONNECTED.
      * Mode LEGACY_MODE is for compatibility with previous versions of ImageJ;
      * ignored if tolerance > 0.
      * Mode bit THRESHOLDED_MODE for internal use only; it is set by autoOutline
      * with 'upper' and 'lower' arguments.
      * When successful, npoints>0 and the boundary points can be accessed
      * in the public xpoints and ypoints fields. */
    public void autoOutline(int startX, int startY, double tolerance, int mode) {
        if (startX<0 || startX>=width || startY<0 || startY>=height) return;
        if (fpixels!=null && Float.isNaN(getPixel(startX, startY))) return;
        WandToolOptions.setStart(startX, startY);
        exactPixelValue = tolerance==0;
        boolean thresholdMode = (mode & THRESHOLDED_MODE) != 0;
        boolean legacyMode = (mode & LEGACY_MODE) != 0 && tolerance == 0;
        if (!thresholdMode) {
            double startValue = getPixel(startX, startY);
            lowerThreshold = (float)(startValue - tolerance);
            upperThreshold = (float)(startValue + tolerance);
        }
        int x = startX;
        int y = startY;
        int seedX;                      // the first inside pixel
        if (inside(x,y)) {              // find a border when coming from inside
            seedX = x;                // (seedX, startY) is an inside pixel
            do {x++;} while (inside(x,y));
        } else {                        // find a border when coming from outside (thresholded only)
            do {
                x++;
                if (x>=width) return;   // no border found
            } while (!inside(x,y));
            seedX = x;
        }
        boolean fourConnected;
        if (legacyMode)
            fourConnected = !thresholdMode && !(isLine(x, y));
        else
            fourConnected = (mode & FOUR_CONNECTED) != 0;
        //now, we have a border between (x-1, y) and (x,y)
        boolean first = true;
        while (true) {                  // loop until we have not traced an inner hole
            boolean insideSelected = traceEdge(x, y, fourConnected);
            if (legacyMode) return;     // in legacy mode, don't care what we have got
            if (insideSelected) {       // not an inner hole
                if (first) return;      // started at seed, so we got it (sucessful)
                if (xmin<=seedX) {      // possibly the correct particle
                    Polygon poly = new Polygon(xpoints, ypoints, npoints);
                    if (poly.contains(seedX, startY))
                        return;         // successful, particle contains seed
                }
            }
            first = false;
            // we have traced an inner hole or the wrong particle
            if (!inside(x,y)) do {
                x++;                    // traverse the hole
                if (x>width) throw new RuntimeException("Wand Malfunction"); //should never happen
            } while (!inside(x,y));
            do {x++;} while (inside(x,y)); //retry here; maybe no inner hole any more
        }
    }


    /* Trace the outline, starting at a point (startX, startY). 
     * Pixel (startX-1, startY) must be outside, (startX, startY) must be inside,
     * or reverse. Otherwise an endless loop will occur (and eat up all memory).
     * Traces 8-connected inside pixels unless fourConnected is true.
     * Returns whether the selection created encloses an 'inside' area
     * and not an inner hole.
     */
    private boolean traceEdge(int startX, int startY, boolean fourConnected) {
        // Let us name the crossings between 4 pixels vertices, then the
        // vertex (x,y) marked with '+', is between pixels (x-1, y-1) and (x,y):
        //
        //    pixel    x-1    x
        //      y-1        |
        //             ----+----
        //       y         |
        //
        // The four principal directions are numbered such that the direction
        // number * 90 degrees gives the angle in the mathematical sense; and
        // the directions to the adjacent pixels (for inside(x,y,direction) are
        // at (number * 90 - 45) degrees:
        //      walking                     pixel
        //   directions:   1           directions:     2 | 1
        //              2  +  0                      ----+----
        //                 3                           3 | 0
        //
        // Directions, like angles, are cyclic; direction -1 = direction 3, etc.
        //
        // The algorithm: We walk along the border, from one vertex to the next,
        // with the outside pixels always being at the left-hand side.
        // For 8-connected tracing, we always trying to turn left as much as
        // possible, to encompass an area as large as possible.
        // Thus, when walking in direction 1 (up, -y), we start looking
        // at the pixel in direction 2; if it is inside, we proceed in this
        // direction (left); otherwise we try with direction 1 (up); if pixel 1
        // is not inside, we must proceed in direction 0 (right).
        //
        //                     2 | 1                 (i=inside, o=outside)
        //      direction 2 < ---+---- > direction 0
        //                     o | i
        //                       ^ direction 1 = up = starting direction
        //
        // For 4-connected pixels, we try to go right as much as possible:
        // First try with pixel 1; if it is outside we go in direction 0 (right).
        // Otherwise, we examine pixel 2; if it is outside, we go in
        // direction 1 (up); otherwise in direction 2 (left).
        //
        // When moving a closed loop, 'direction' gets incremented or decremented
        // by a total of 360 degrees (i.e., 4) for counterclockwise and clockwise
        // loops respectively. As the inside pixels are at the right side, we have
        // got an outline of inner pixels after a cw loop (direction decremented
        // by 4).
        //
        npoints = 0;
        xmin = width;
        final int startDirection;
        if (inside(startX,startY))      // inside at left, outside right
            startDirection = 1;         // starting in direction 1 = up
        else {
            startDirection = 3;         // starting in direction 3 = down
            startY++;                   // continue after the boundary that has direction 3
        }
        int x = startX;
        int y = startY;
        int direction = startDirection;
        do {
            int newDirection;
            if (fourConnected) {
                newDirection = direction;
                do {
                    if (!inside(x, y, newDirection)) break;
                    newDirection++;
                } while (newDirection < direction+2);
                newDirection--;
            } else { // 8-connected
                newDirection = direction + 1;
                do {
                if (inside(x, y, newDirection)) break;
                    newDirection--;
                } while (newDirection >= direction);
            }
            if (allPoints || newDirection!=direction)
                addPoint(x,y);          // a corner point of the outline polygon: add to list
            switch (newDirection & 3) { // '& 3' is remainder modulo 4
                case 0: x++; break;
                case 1: y--; break;
                case 2: x--; break;
                case 3: y++; break;
            }
            direction = newDirection;
        } while (x!=startX || y!=startY || (direction&3)!=startDirection);
        if (xpoints[0]!=x && !allPoints)            // if the start point = end point is a corner: add to list
            addPoint(x, y);
        return (direction <= 0);        // if we have done a clockwise loop, inside pixels are enclosed
    }

    // add a point x,y to the outline polygon
    private void addPoint (int x, int y) {
        if (npoints==maxPoints) {
            int[] xtemp = new int[maxPoints*2];
            int[] ytemp = new int[maxPoints*2];
            System.arraycopy(xpoints, 0, xtemp, 0, maxPoints);
            System.arraycopy(ypoints, 0, ytemp, 0, maxPoints);
            xpoints = xtemp;
            ypoints = ytemp;
            maxPoints *= 2;
        }
        xpoints[npoints] = x;
        ypoints[npoints] = y;
        npoints++;
        if (xmin > x) xmin = x;
    }

    // check pixel at (x,y), whether it is inside traced area
    private boolean inside(int x, int y) {
        if (x<0 || x>=width || y<0 || y>=height)
            return false;
        float value = getPixel(x, y);
        return value>=lowerThreshold && value<=upperThreshold;
    }

    // check pixel in a given direction from vertex (x,y)
    private boolean inside(int x, int y, int direction) {
        switch(direction & 3) {         // '& 3' is remainder modulo 4
            case 0: return inside(x, y);
            case 1: return inside(x, y-1);
            case 2: return inside(x-1, y-1);
            case 3: return inside(x-1, y);
        }
        return false; //will never occur, needed for the compiler
    }

    // get a pixel value; returns Float.NaN if outside the field.
    private float getPixel(int x, int y) {
        if (x<0 || x>=width || y<0 || y>=height)
            return Float.NaN;
        if (bpixels!=null)
            return bpixels[y*width + x] & 0xff;
        else if (spixels!=null)
            return spixels[y*width + x] & 0xffff;
        else if (fpixels!=null)
            return fpixels[y*width + x];
        else if (exactPixelValue)   //RGB for exact match
            return cpixels[y*width + x] & 0xffffff; //don't care for upper byte
        else                      //gray value of RGB
            return ip.getPixelValue(x,y);
    }

    /* Are we tracing a one pixel wide line? Makes Legacy mode 8-connected instead of 4-connected */
    private boolean isLine(int xs, int ys) {
        int r = 5;
        int xmin=xs;
        int xmax=xs+2*r;
        if (xmax>=width) xmax=width-1;
        int ymin=ys-r;
        if (ymin<0) ymin=0;
        int ymax=ys+r;
        if (ymax>=height) ymax=height-1;
        int area = 0;
        int insideCount = 0;
        for (int x=xmin; (x<=xmax); x++)
            for (int y=ymin; y<=ymax; y++) {
                area++;
                if (inside(x,y))
                    insideCount++;
            }
        if (IJ.debugMode)
            IJ.log((((double)insideCount)/area<0.25?"line ":"blob ")+insideCount+" "+area+" "+IJ.d2s(((double)insideCount)/area));
        return ((double)insideCount)/area<0.25;
    }

    /** Set 'true' and output will contain intermediate points for straight lines longer than one pixel. */
    public static void setAllPoints(boolean b) {
        allPoints = b;
    }

	/** Returns 'true' if output contains intermediate points for straight lines longer than one pixel. */
	public static boolean allPoints() {
		return allPoints;
	}

}