package ij.gui;

import java.awt.*;
import ij.*;
import ij.process.*;

/** This class implements ImageJ's wand (tracing) tool. */
public class Wand {
	static final int UP=0, DOWN=1, UP_OR_DOWN=2, LEFT=3, RIGHT=4, LEFT_OR_RIGHT=5, NA=6;
	
	/** 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. */
	public int[] xpoints = new int[maxPoints];
	/** The y-coordinates of the points in the outline. */
	public int[] ypoints = new int[maxPoints];

	private ImageProcessor ip;
	private byte[] bpixels;
	private int[] cpixels;
	private short[] spixels;
	private float[] fpixels;
	private int width, height;
	private float lowerThreshold, upperThreshold;

	/** Constructs a Wand object from an ImageProcessor. */
	public Wand(ImageProcessor ip) {
		if (ip instanceof ByteProcessor)
			bpixels = (byte[])ip.getPixels();
		else if (ip instanceof ColorProcessor)
			cpixels = (int[])ip.getPixels();
		else if (ip instanceof ShortProcessor)
			spixels = (short[])ip.getPixels();
		else if (ip instanceof FloatProcessor)
			fpixels = (float[])ip.getPixels();
		width = ip.getWidth();
		height = ip.getHeight();
	}
	
	private float getColorPixel(int x, int y) {
		if (x>=0 && x<width && y>=0 && y<height)
			return cpixels[y*width + x];
		else
			return Float.MAX_VALUE;
	}

	private float getBytePixel(int x, int y) {
		if (x>=0 && x<width && y>=0 && y<height)
			return bpixels[y*width + x] & 0xff;
		else
			return Float.MAX_VALUE;
	}

	private float getShortPixel(int x, int y) {
		if (x>=0 && x<width && y>=0 && y<height)
			return spixels[y*width + x] & 0xffff;
		else
			return Float.MAX_VALUE;
	}

	private float getFloatPixel(int x, int y) {
		if (x>=0 && x<width && y>=0 && y<height)
			return fpixels[y*width + x];
		else
			return Float.MAX_VALUE;
	}

	private float getPixel(int x, int y) {
		if (bpixels!=null)
			return getBytePixel(x,y);
		else if (spixels!=null)
			return getShortPixel(x,y);
		else if (fpixels!=null)
			return getFloatPixel(x,y);
		else
			return getColorPixel(x,y);
	}

	private boolean inside(int x, int y) {
		float value;
		if (bpixels!=null)
			value = getBytePixel(x,y);
		else if (spixels!=null)
			value = getShortPixel(x,y);
		else if (fpixels!=null)
			value = getFloatPixel(x,y);
		else
			value = getColorPixel(x,y);
		return value>=lowerThreshold && value<=upperThreshold;
	}

	/* Are we tracing a one pixel wide line? */
	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.75?"line ":"blob ")+insideCount+" "+area+" "+IJ.d2s(((double)insideCount)/area));
		return ((double)insideCount)/area>=0.75;
	}
	
	/** Traces the boundary of an area of uniform color, where
		'startX' and 'startY' are somewhere inside the area. The
		boundary points are stored in the public xpoints and ypoints
		fields. A 16 entry lookup table is used to determine the
		direction at each step of the tracing process. Note that
		the four argument version [autoOutline(x, y, lower, upper)]
		works more reliably. */
	public void autoOutline(int startX, int startY) {
		int x = startX;
		int y = startY;
		int direction;
		lowerThreshold = upperThreshold = getPixel(startX, startY);
		do {x++;} while (inside(x,y));
		if (isLine(x, y)) {
			lowerThreshold = upperThreshold = getPixel(x, y);
			direction = UP;
		} else {
			if (!inside(x-1,y-1))
				direction = RIGHT;
			else if (inside(x,y-1))
				direction = LEFT;
			else
				direction = DOWN;
		}
		traceEdge(x, y, direction);
	}
		
	/** Traces an object defined by lower and upper threshold values. The
		boundary points are stored in the public xpoints and ypoints fields.
		This verson works more reliably than autoOutline(x, y). */
	public void autoOutline(int startX, int startY, double lower, double upper) {
		//IJ.log(startX+"  "+startY+"  "+lower+"  "+upper);
		npoints = 0;
		int x = startX;
		int y = startY;
		int direction;
		lowerThreshold = (float)lower;
		upperThreshold = (float)upper;
		if (inside(x,y)) {
			do {x++;} while (inside(x,y));
			if (!inside(x-1,y-1))
				direction = RIGHT;
			else if (inside(x,y-1))
				direction = LEFT;
			else
				direction = DOWN;
		} else {
			do {x++;} while (!inside(x,y) && x<width);
				direction = UP;
			if (x>=width) return;
		}
		traceEdge(x, y, direction);
	}

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

	void traceEdge(int xstart, int ystart, int startingDirection) {
		int[] table = {
						// 1234, 1=upper left pixel,  2=upper right, 3=lower left, 4=lower right
			NA,			// 0000, should never happen
			RIGHT,		// 000X,
			DOWN,		// 00X0
			RIGHT,		// 00XX
			UP,			// 0X00
			UP,			// 0X0X
			UP_OR_DOWN, // 0XX0 Go up or down depending on current direction
			UP,			// 0XXX
			LEFT,		// X000
			LEFT_OR_RIGHT, // X00X  Go left or right depending on current direction
			DOWN,		// X0X0
			RIGHT,		// X0XX
			LEFT,		// XX00
			LEFT,		// XX0X
			DOWN,		// XXX0
			NA,			// XXXX Should never happen
			};
		int index;
		int newDirection;
		int x = xstart;
		int y = ystart;
		int direction = startingDirection;

		boolean UL = inside(x-1, y-1);	// upper left
		boolean UR = inside(x, y-1);	// upper right
		boolean LL = inside(x-1, y);	// lower left
		boolean LR = inside(x, y);		// lower right
		//xpoints[0] = x;
		//ypoints[0] = y;
		int count = 0;
	//IJ.write("");
	//IJ.write(count + " " + x + " " + y + " " + direction + " " + insideValue);
		do {
			index = 0;
			if (LR) index |= 1;
			if (LL) index |= 2;
			if (UR) index |= 4;
			if (UL) index |= 8;
			newDirection = table[index];
			if (newDirection==UP_OR_DOWN) {
				if (direction==RIGHT)
					newDirection = UP;
				else
					newDirection = DOWN;
			}
			if (newDirection==LEFT_OR_RIGHT) {
				if (direction==UP)
					newDirection = LEFT;
				else
					newDirection = RIGHT;
			}
			if (newDirection!=direction) {
				xpoints[count] = x;
				ypoints[count] = y;
				count++;
			if (count==xpoints.length) {
				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;
			}
		//if (count<10) IJ.write(count + " " + x + " " + y + " " + newDirection + " " + index);
			}
			switch (newDirection) {
				case UP:
					y = y-1;
					LL = UL;
					LR = UR;
					UL = inside(x-1, y-1);
					UR = inside(x, y-1);
					break;
				case DOWN:
					y = y + 1;
					UL = LL;
					UR = LR;
					LL = inside(x-1, y);
					LR = inside(x, y);
					break;
				case LEFT:
					x = x-1;
					UR = UL;
					LR = LL;
					UL = inside(x-1, y-1);
					LL = inside(x-1, y);
					break;
				case RIGHT:
					x = x + 1;
					UL = UR;
					LL = LR;
					UR = inside(x, y-1);
					LR = inside(x, y);
					break;
			}
			direction = newDirection;
		} while ((x!=xstart || y!=ystart || direction!=startingDirection));
		npoints = count;
	}

}