package jp.sourceforge.qrcode.codec.reader.pattern;


import jp.sourceforge.qrcode.codec.reader.*;
import jp.sourceforge.qrcode.codec.exception.FinderPatternNotFoundException;
import jp.sourceforge.qrcode.codec.exception.InvalidVersionInformationException;
import jp.sourceforge.qrcode.codec.exception.UnsupportedVersionException;
import jp.sourceforge.qrcode.codec.exception.VersionInformationException;
import jp.sourceforge.qrcode.codec.geom.*;

import java.util.*;
import jp.sourceforge.qrcode.codec.util.*;

public class FinderPattern {
	public static final int UL = 0;
	public static final int UR = 1;
	public static final int DL = 2;
	static final int[] VersionInfoBit = {
			0x07C94,0x085BC,0x09A99,0x0A4D3,0x0BBF6,0x0C762,0x0D847,
			0x0E60D,0x0F928,0x10B78,0x1145D,0x12A17,0x13532,0x149A6,
			0x15683,0x168C9,0x177EC,0x18EC4,0x191E1,0x1AFAB,0x1B08E,
			0x1CC1A,0x1D33F,0x1ED75,0x1F250,0x209D5,0x216F0,0x228BA,
			0x2379F,0x24B0B,0x2542E,0x26A64,0x27541,0x28C69
	};
	
	static DebugCanvas canvas = DebugCanvas.getCanvas();
	Point[] center;
	int version;
	int[] sincos;
	int[] width;
	int moduleSize;
	
	public static FinderPattern findFinderPattern(boolean[][] image)
			throws FinderPatternNotFoundException,
			VersionInformationException {
		Line[] lineAcross = findLineAcross(image);
		Line[] lineCross = findLineCross(lineAcross);
		Point[] center = null;
		try {
			center = getCenter(lineCross);
		} catch (FinderPatternNotFoundException e) {
			throw e;
			//e.printStackTrace();
		}
//		if (center == null)
//			return new FinderPattern (center, 0, new int[2], new int[3], 0);
		int[] sincos = getAngle(center);
		center = sort(center, sincos);
		int[] width = getWidth(image, center, sincos);
		int[] moduleSize = {(width[UR] << QRCodeImageReader.DECIMAL_POINT) / 7,(width[DL] << QRCodeImageReader.DECIMAL_POINT) / 7};
		int version = calcRoughVersion(center, width);
		if (version > 6) {
			try {
				version = calcExactVersion(center, sincos, moduleSize, image);
			} catch (VersionInformationException e) {
				throw e;
			}
		}
		return new FinderPattern (center, version, sincos, width, moduleSize[0]);
	}
	
	FinderPattern (Point[] center, int version, int[] sincos, int[] width, int moduleSize) {
		this.center = center;
		this.version = version;
		this.sincos = sincos;
		this.width = width;
		this.moduleSize = moduleSize;
	}
	
	public Point[] getCenter() {
		return center;
	}
	
	public Point getCenter(int position) {
		if (position >= UL && position <= DL)
			return center[position];	
		else
			return null;
	}
	
	public int getWidth(int position) {
		return width[position];
	}
	
	public int[] getAngle() {
		return sincos;
	}
	
	public int getVersion() {
		return version;
	}
	
	public int getModuleSize() {
		return moduleSize;
	}
	public int getSqrtNumModules() {
		return 17 + 4 * version;
	}
	
	/*
	 * 埵抲梫慺専弌僷僞乕儞傪専弌偡傞偨傔偵丄(埫:柧:埫:柧:埫)=(1:1:3:1:1)偺
	 * 僷僞乕儞偵堦抳偡傞嬫娫傪慄暘偲偟偰拪弌偡傞丅
	 * 拲堄丗埵抲梫慺僷僞乕儞傪墶愗傜側偄晹暘偑拪弌偝傟傞偙偲傕偁傞
	 */
	static Line[] findLineAcross(boolean[][] image) {
		final int READ_HORIZONTAL = 0;
		final int READ_VERTICAL = 1;

		int imageWidth = image.length;
		int imageHeight = image[0].length;

		//int currentX = 0, currentY = 0;
		Point current = new Point();
		Vector lineAcross = new Vector();
		
		//捈嬤偺丄摨偠怓偱楢懕偟偨梫慺偺挿偝
		int[] lengthBuffer = new int[5];
		int  bufferPointer = 0;
		
		int direction = READ_HORIZONTAL; //暯峴曽岦偐傜撉傒巒傔傞
		boolean lastElement = QRCodeImageReader.POINT_LIGHT;
	
		while(true) {
			//梫慺僠僃僢僋
			boolean currentElement = image[current.getX()][current.getY()];
			if (currentElement == lastElement) { //慜夞偺梫慺偲摨偠
				lengthBuffer[bufferPointer]++;
			}
			else { //慜夞偺梫慺偲堘偆
				if (currentElement == QRCodeImageReader.POINT_LIGHT) {
					if (checkPattern(lengthBuffer, bufferPointer)) { //僷僞乕儞傪専弌偟偨傜
						int x1, y1, x2, y2;
						if (direction == READ_HORIZONTAL) {
							//僷僞乕儞岓曗偺椉抂偺x嵗昗傪媮傔傞
							//嵍抂偼尰嵼偺梫慺偺x嵗昗偲僶僢僼傽偺挿偝偺榓偐傜嶼弌
							x1 = current.getX(); 
							for (int j = 0; j < 5; j++) {
								x1 -= lengthBuffer[j];
							}
							x2 = current.getX() - 1; //塃抂偼捈慜偺梫慺偺x嵗昗
							y1 = y2 = current.getY();
						}
						else {
							x1 = x2 = current.getX();
							//僷僞乕儞岓曗偺椉抂偺y嵗昗傪媮傔傞
							//嵍抂偼尰嵼偺梫慺偺y嵗昗偲僶僢僼傽偺挿偝偺榓偐傜嶼弌
							y1 = current.getY(); 
							for (int j = 0; j < 5; j++) {
								y1 -= lengthBuffer[j];
							}
							y2 = current.getY() - 1; //塃抂偼捈慜偺梫慺偺y嵗昗
						}
						lineAcross.addElement(new Line(x1, y1, x2, y2));
					}
				}
				bufferPointer = (bufferPointer + 1) % 5; 
				lengthBuffer[bufferPointer] = 1;
				lastElement = !lastElement;
			}
			
			//師傪撉傓 or 撉傒庢傝曽岦揮姺 or 儖乕僾廔椆 敾掕
			if (direction == READ_HORIZONTAL) { //X幉曽岦撉傒崬傒拞
				if (current.getX() < imageWidth - 1) {
					current.translate(1, 0);
				}
				else if (current.getY() < imageHeight - 1) {
					current.set(0, current.getY() + 1);
					lengthBuffer =  new int[5];
				}
				else {
					current.set(0, 0); //撉傒崬傒揰傪儕僙僢僩偟
					lengthBuffer =  new int[5];
					direction = READ_VERTICAL; //師偼Y幉曽岦偵撉傒巒傔傞
				}
			}
			else { //Y幉曽岦撉傒崬傒拞
				if (current.getY() < imageHeight - 1)
					current.translate(0, 1);
				else if (current.getX() < imageWidth - 1) {
					current.set(current.getX() + 1, 0);
					lengthBuffer = new int[5];
				}
				else {
					break;
				}
			}
		}
		
		Line[] foundLines = new Line[lineAcross.size()];

		for (int i = 0; i < foundLines.length; i++)
			foundLines[i] = (Line) lineAcross.elementAt(i);
		
		canvas.drawLines(foundLines,Color.LIGHTGREEN);
		return foundLines;
	}
	
	static boolean checkPattern(int[] buffer, int pointer) {
		final int[] modelRatio = {1, 1, 3, 1, 1};	

		int baselength = 0;
		for (int i = 0; i < 5; i++) {
			baselength += buffer[i];
		}
		baselength <<= QRCodeImageReader.DECIMAL_POINT; //娵傔岆嵎傪尭傜偡偨傔偵4098攞偡傞
		baselength /= 7;
		int i;
		for  (i = 0; i < 5; i++) {
			int leastlength = baselength * modelRatio[i] - baselength / 2;
			int mostlength = baselength * modelRatio[i] + baselength / 2;
			
			//FIXME 帋尡揑偵忦審傪娒偔偡傞
			leastlength -= baselength / 8;
			mostlength += baselength / 8;
			
			int targetlength = buffer[(pointer + i + 1) % 5] << QRCodeImageReader.DECIMAL_POINT;
			if (targetlength < leastlength || targetlength > mostlength) {
				return false;
			}
		}
		return true;
	}

	
	//埵抲梫慺専弌僷僞乕儞偺拞怱傪捠傝丄屳偄偵岎嵎偟偰偄傞偲巚傢傟傞慄暘傪摼傞
	static Line[] findLineCross(Line[] lineAcross) {
		Vector crossLines = new Vector();
		Vector lineNeighbor = new Vector();
		Vector lineCandidate = new Vector();
		Line compareLine;
		for (int i = 0; i < lineAcross.length; i++)
			lineCandidate.addElement(lineAcross[i]);
		
		for (int i = 0; i < lineCandidate.size() - 1; i++) {
			lineNeighbor.removeAllElements();
			lineNeighbor.addElement(lineCandidate.elementAt(i));
			for (int j = i + 1; j < lineCandidate.size(); j++) {
				if (Line.isNeighbor((Line)lineNeighbor.lastElement(), (Line)lineCandidate.elementAt(j))) {
					lineNeighbor.addElement(lineCandidate.elementAt(j));
					compareLine = (Line)lineNeighbor.lastElement();
					if (lineNeighbor.size() * 5 > compareLine.getLength() &&
							j == lineCandidate.size() - 1) {
						crossLines.addElement(lineNeighbor.elementAt(lineNeighbor.size() / 2));
						for (int k = 0; k < lineNeighbor.size(); k++)
							lineCandidate.removeElement(lineNeighbor.elementAt(k));
					}
				}
				//偙傟埲忋挷傋偰傕椬傝崌偆Line偑尒偮偐傞壜擻惈偑側偄応崌偼斾妑懪偪愗傝
				else if (cantNeighbor((Line)lineNeighbor.lastElement(), (Line)lineCandidate.elementAt(j)) ||
					(j == lineCandidate.size() - 1)) {
					compareLine = (Line)lineNeighbor.lastElement();
					//椬傝崌偭偨慄暘摨巑偺暆偑偦傟傪峔惉偡傞慄暘偺挿偝偺
					//1/6埲忋偩偭偨傜丄埵抲梫慺専弌僷僞乕儞傪墶愗偭偰偄傞偲敾抐偡傞					
					if (lineNeighbor.size() * 6 > compareLine.getLength()) {
						crossLines.addElement(lineNeighbor.elementAt(lineNeighbor.size() / 2));
						for (int k = 0; k < lineNeighbor.size(); k++) {
							lineCandidate.removeElement(lineNeighbor.elementAt(k));
						}
					}
					break;
				}
			}
		}	

		Line[] foundLines = new Line[crossLines.size()];
		for (int i = 0; i < foundLines.length; i++) {
			foundLines[i] = (Line) crossLines.elementAt(i);
		}
		return foundLines;
	}
	
	static boolean cantNeighbor(Line line1, Line line2) {
		if (Line.isCross(line1, line2))
			return true;

		if (line1.isHorizontal()) {
			if (Math.abs(line1.getP1().getY() - line2.getP1().getY()) > 1)
				return true;
			else
				return false;
		} 
		else {
			if (Math.abs(line1.getP1().getX() - line2.getP1().getX()) > 1)
				return true;
			else
				return false;
			
		}
	}
	
	//僔儞儃儖偺孹幬妏搙傪媮傔傞
	static int[] getAngle(Point[] centers) {

		Line[] additionalLine = new Line[3];

		for (int i = 0; i < additionalLine.length; i++) {
			additionalLine[i] = new Line(centers[i],
					centers[(i + 1) % additionalLine.length]);
		}
		Line longestLine = Line.getLongest(additionalLine);
		Point originPoint = new Point();
		for (int i = 0; i < centers.length; i++) {
			if ((centers[i].getX() != longestLine.getP1().getX() ||
					centers[i].getY() != longestLine.getP1().getY()) &
					(centers[i].getX() != longestLine.getP2().getX() ||
					centers[i].getY() != longestLine.getP2().getY())) {
				originPoint = centers[i];
				break;
			}
		}
		Point remotePoint = new Point();


		//嵍忋偺僷僞乕儞拞怱揰傪尨揰偲偟偰丄懠偺2僷僞乕儞偺拞怱揰偑偳偙偵偁傞偐
		//偍傛傃丄妏搙寁應偺懳徾偲側傞揰偼偦傟傜偺偆偪偳偪傜偐
		if (originPoint.getY() <= longestLine.getP1().getY() & //戞1傑偨偼戞2徾尷
				originPoint.getY() <= longestLine.getP2().getY())
			if (longestLine.getP1().getX() < longestLine.getP2().getX())
				remotePoint = longestLine.getP2();
			else
				remotePoint = longestLine.getP1();
		else if (originPoint.getX() >= longestLine.getP1().getX() & //戞2傑偨偼戞3徾尷
				originPoint.getX() >= longestLine.getP2().getX())
			if (longestLine.getP1().getY() < longestLine.getP2().getY())
				remotePoint = longestLine.getP2();
			else
				remotePoint = longestLine.getP1();