package edu.uiuc.webcoord;

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.Vector;

public class CoordConverter {
	
	/**
	 * @param doc - HTMLDocument with elements
	 * @return Converts x and y coordinates of each web element in doc to integer notation.
	 * Instead of coordinates like x="1.1.1" and y="1.1.2" these become x="1" and y="2".
	 * Returns modified HTMLDocument object. (Naive Method: Count all unique x coordinates 
	 * and y coordinates in doc, sort them and associate an incremented integer value to each.
	 * Then simply replace each coordinate in original element with associated integer "rank". 
	 * @author Sergei Vasilevsky
	 */
	public HTMLDocument naiveToIntCoords(HTMLDocument doc) {
		HTMLDocument newDoc = new HTMLDocument();
		if ((doc == null) || (doc.getWebElements().length == 0)) {
			return doc;
		}
		
		WebElement[] eArr = doc.getWebElements();
		
		//Generate 1 array of unique x coordinates and 1 array of unique y coordinates
		Vector vX = new Vector();
		Vector vY = new Vector();
		for (int i = 0; i < eArr.length; i++) {
			//add x if unique
			Coord tempCoord = new Coord(eArr[i].getXCoord());
			if (!vX.contains(tempCoord)) {vX.add(tempCoord);}
			//add y if unique
			tempCoord = new Coord(eArr[i].getYCoord());
			if (!vY.contains(tempCoord)) {vY.add(tempCoord);}
		}
		
		//Create Coord Arrays for sorting
		Coord[] acX = (Coord[]) vX.toArray(new Coord[0]);
		Coord[] acY = (Coord[]) vY.toArray(new Coord[0]);
		
		//Sort
		Arrays.sort(acX);
		Arrays.sort(acY);
		
		//Convert to String arrays for simplicity
		String[] asX = new String[acX.length];
		for (int i = 0; i < acX.length; i++) {
			asX[i] = acX[i].toString();
		}
		String[] asY = new String[acY.length];
		for (int i = 0; i < acY.length; i++) {
			asY[i] = acY[i].toString();
		}
	
		//Replace old coords with the new integer ones
		for (int i = 0; i < eArr.length; i++) {
			WebElement we = eArr[i];
			
			//Find x in aX and set the coord in we to integer value
			int x = 0;
			while ((x < asX.length)&&(!asX[x].equals(eArr[i].getXCoord()))) {
				x++;
			}
			we.setXCoord(String.valueOf(x + 1));
			
//			Find y in aY and set the coord in we to integer value
			int y = 0;
			while ((y < asY.length)&&(!asY[y].equals(eArr[i].getYCoord()))) {
				y++;
			}
			we.setYCoord(String.valueOf(y + 1));
			
			//add we to newDoc
			newDoc.addWebElement(we);
		}
		
		return newDoc;
	}
	
	public HTMLDocument ToIntCoordsTree(HTMLDocument doc) {
		HTMLDocument newDoc = new HTMLDocument();
		if ((doc == null) || (doc.getWebElements().length == 0)) {
			return doc;
		}
		
		CoordTree ct = new CoordTree();
		WebElement[] weArr = doc.getWebElements();
		for (int i = 0; i < weArr.length; i++) {
			ct.AddWebElement(weArr[i]);
		}
		
		if (ct.convertToIntCoords()) {		
			return ct.getHTMLDocument();
		}
		else {
			return null;
		}
	}
	/**
	 * @param doc - HTMLDocument with elements
	 * @return Converts x and y coordinates of each web element in doc to integer notation.
	 * Instead of coordinates like x="1.1.1" and y="1.1.2" these become x="1" and y="2".
	 * Returns modified HTMLDocument object.
	 */
	public HTMLDocument toIntCoords(HTMLDocument doc) {
//		return naiveToIntCoords(doc);
		return ToIntCoordsTree(doc);
	}
	
	private class Coord implements Comparable{
		public int[] iArr = null;
		
		public Coord(String strNestedCoord) {
			 String[] cArr = strNestedCoord.split("\\.");
			 iArr = new int[cArr.length];
			 for (int i = 0; i < cArr.length; i++) {
			 	iArr[i] = Integer.parseInt(cArr[i]);
			 }
		}
		
		/* (non-Javadoc)
		 * @see java.lang.Comparable#compareTo(java.lang.Object)
		 */
		public int compareTo(Object anotherCoord) {
			if (!(anotherCoord instanceof Coord))
			      throw new ClassCastException("A Coord object expected.");
			
			Coord coordObj = (Coord)anotherCoord;
			int minLength = Math.min(this.iArr.length, coordObj.iArr.length);
			
			for (int i = 0; i < minLength; i++) {
				if (this.iArr[i] != coordObj.iArr[i]) { return (this.iArr[i] - coordObj.iArr[i]); }
			}
			
			if (this.iArr.length==coordObj.iArr.length) {
				return 0;
			}
			else {
				return this.iArr.length - coordObj.iArr.length;
			}
		}
		
		public boolean equals(Object anotherCoord) {
			if (!(anotherCoord instanceof Coord))
			      throw new ClassCastException("A Coord object expected.");
			
			Coord coordObj = (Coord)anotherCoord;
			int minLength = Math.min(this.iArr.length, coordObj.iArr.length);
			
			for (int i = 0; i < minLength; i++) {
				if (this.iArr[i] != coordObj.iArr[i]) { return false; }
			}
			
			if (this.iArr.length==coordObj.iArr.length) {
				return true;
			}
			else {
				return false;
			}
		}
		
		public String toString() {
			String retVal = "";
			for (int i = 0; i < iArr.length; i++) {
				retVal += iArr[i] + ".";
			}
			if ((retVal.length() > 0)&&(retVal.endsWith("."))) { retVal = retVal.substring(0, retVal.length() - 1); }
			return retVal;
		}
		
		public int depth() {
			if (this.iArr != null) { return this.iArr.length; }
			else { return 0; }
		}
		
		public Coord getTruncatedCoord(int level) {
			if ((level < 1) || (level > this.depth())) { return null; }
			
			String tempStr = "";
			for (int i = 0; i < level - 1; i++) {
				tempStr += this.iArr[i] + ".";
			}
			tempStr += this.iArr[level - 1];
			
			Coord tempCoord = new Coord(tempStr);
			return tempCoord;
		}
	}
	
	
	
	private class CoordTree {
		private class CoordTreeVirtualNode extends CoordTreeNode{
			private final WebElement webElement = null; //Override the parent webElement;

			public CoordTreeVirtualNode(Coord _x, Coord _y) {
				super(_x, _y);
			}
			
			public int Height() {
				if (this.children.size() < 1) { return 0; }
				
				Iterator iter = this.children.iterator();
				CoordTreeNode maxNode = (CoordTreeNode)this.children.firstElement();
				int maxVal = maxNode.y.iArr[maxNode.y.iArr.length -  1] + maxNode.Height() - 1;
				
				while (iter.hasNext()) {
					CoordTreeNode tmpNode = (CoordTreeNode)iter.next();
					int tmpVal = tmpNode.y.iArr[tmpNode.y.iArr.length -  1] + tmpNode.Height() - 1;
					if (tmpVal > maxVal) {
						maxNode = tmpNode;
						maxVal = tmpVal;
					}
				}
				
				return maxVal;
			}
			
			public int Width() {
				if (this.children.size() < 1) { return 0; }
				
				Iterator iter = this.children.iterator();
				CoordTreeNode maxNode = (CoordTreeNode)this.children.firstElement();
				int maxVal = maxNode.x.iArr[maxNode.x.iArr.length -  1] + maxNode.Width() - 1;
				
				while (iter.hasNext()) {
					CoordTreeNode tmpNode = (CoordTreeNode)iter.next();
					int tmpVal = tmpNode.x.iArr[tmpNode.x.iArr.length -  1] + tmpNode.Width() - 1;
					if (tmpVal > maxVal) {
						maxNode = tmpNode;
						maxVal = tmpVal;
					}
				}
				
				return maxVal;
			}
		}
		
		private class CoordTreeRootNode extends CoordTreeNode{
			public int getDepth() {
				return 0;
			}
			
			public CoordTreeRootNode() {
				this.webElement = null;
				this.children = new Vector();
			}
			
			public int Height() {
				if (this.children.size() < 1) { return 0; }
				
				Iterator iter = this.children.iterator();
				CoordTreeNode maxVal = (CoordTreeNode)this.children.firstElement();
				
				while (iter.hasNext()) {
					CoordTreeNode tmpNode = (CoordTreeNode)iter.next();
					if (tmpNode.y.compareTo(maxVal) > 0) {
						maxVal = tmpNode;
					}
				}
				
//				return sum of lowest element's y value and it's height - 1
				return maxVal.y.iArr[maxVal.y.iArr.length -  1] + maxVal.Height() - 1;
			}
			
			public int Width() {
				if (this.children.size() < 1) { return 0; }
				
				Iterator iter = this.children.iterator();
				CoordTreeNode maxVal = (CoordTreeNode)this.children.firstElement();
				
				while (iter.hasNext()) {
					CoordTreeNode tmpNode = (CoordTreeNode)iter.next();
					if (tmpNode.x.compareTo(maxVal) > 0) {
						maxVal = tmpNode;
					}
				}
				
				//return sum of rightmost element's x value and it's width - 1
				return maxVal.x.iArr[maxVal.x.iArr.length -  1] + maxVal.Width() - 1;
			}
			
//			Override parent's method
			public boolean addNodeToChildren(CoordTreeNode node) {
				if (children == null) { return false; } 
				else if (node.getDepth() == 1){
					int nextLvlX = node.x.iArr[0];
					int nextLvlY = node.y.iArr[0];
					
					//Search for a node with same coordinates already in children
					Iterator i = children.iterator();
					while (i.hasNext()) {
						CoordTreeNode tmpNode = (CoordTreeNode)i.next();
						if (tmpNode.x.equals(node.x)&&(tmpNode.y.equals(node.y))) {
							return false;
						}
					}
					
					//no duplicates exist in children
					children.add(node);
					return true;
				}
				else {
					// More than one level difference - find a virtual node, or create one
					
					int nextLvlX = node.x.iArr[0];
					int nextLvlY = node.y.iArr[0];
					
					//Search for a node with same coordinates already in children
					Iterator iter = children.iterator();
					boolean foundVirtualParent = false;
					while (iter.hasNext()) {
						CoordTreeNode tmpNode = (CoordTreeNode)iter.next();
						if ((tmpNode.x.iArr[0]==nextLvlX)&&(tmpNode.y.iArr[0] == nextLvlY)) {
							foundVirtualParent = true;
							return tmpNode.addNodeToChildren(node);
						}
					}
					
					if (!foundVirtualParent) {
						CoordTreeVirtualNode tmpNode = new CoordTreeVirtualNode(node.x.getTruncatedCoord(1), node.y.getTruncatedCoord(1));
						this.children.add(tmpNode);
						return tmpNode.addNodeToChildren(node);
					}
					
					// Will never get here, but gotta make the compiler happy
					return true;
				}
			}
		}
		
		private class CoordTreeNode{
			public Coord x;
			public Coord y;
			
			public int toX;
			public int toY;
			
			public Vector children;
			
			public WebElement webElement;
			
			private CoordTreeNode() {
			}
			
			public CoordTreeNode(Coord _x, Coord _y) {
				x = new Coord(_x.toString());
				y = new Coord(_y.toString());
				children = new Vector();
			}
			
			public CoordTreeNode(WebElement _we) {
				x = new Coord(_we.getXCoord());
				y = new Coord(_we.getYCoord());
				webElement = _we;
			}
			
			public boolean addNodeToChildren(CoordTreeNode node){
				if (children == null) { return false; } 
				else if (node.getDepth() - this.getDepth() < 1) {  //Node belongs somewhere above
					return false;
				}
				else if (node.getDepth() - this.getDepth() == 1){
					int nextLvlX = node.x.iArr[this.x.iArr.length];
					int nextLvlY = node.y.iArr[this.y.iArr.length];
					
					//Search for a node with same coordinates already in children
					Iterator i = children.iterator();
					while (i.hasNext()) {
						CoordTreeNode tmpNode = (CoordTreeNode)i.next();
						if (tmpNode.x.equals(node.x)&&(tmpNode.y.equals(node.y))) {
							return false;
						}
					}
					
					//no duplicates exist in children
					children.add(node);
					return true;
				}
				else {
					// More than one level difference - find a virtual node, or create one
					
					int nextLvlX = node.x.iArr[this.x.iArr.length];
					int nextLvlY = node.y.iArr[this.y.iArr.length];
					
					//Search for a node with same coordinates already in children
					Iterator iter = children.iterator();
					boolean foundVirtualParent = false;
					while (iter.hasNext()) {
						CoordTreeNode tmpNode = (CoordTreeNode)iter.next();
						if (tmpNode.x.equals(node.x)&&(tmpNode.y.equals(node.y))) {
							foundVirtualParent = true;
							return tmpNode.addNodeToChildren(node);
						}
					}
					
					if (!foundVirtualParent) {
						CoordTreeVirtualNode tmpNode = new CoordTreeVirtualNode(node.x.getTruncatedCoord(this.getDepth() + 1), node.y.getTruncatedCoord(this.getDepth() + 1));
						this.children.add(tmpNode);
						return tmpNode.addNodeToChildren(node);
					}
					
					// Will never get here, but gotta make the compiler happy
					return true;
				}
			}
			
			public int getDepth() {
				return Math.max(this.x.depth(), this.y.depth());
			}
			
			public int Height() {
				return 1;
			}
			
			public int Width() {
				return 1;
			}
		}
		
		private class NodeComparatorByX implements Comparator{
			
					/* (non-Javadoc)
			 * @see java.util.Comparator#compare(java.lang.Object, java.lang.Object)
			 */
			public int compare(Object obj1, Object obj2) {
				// TODO Auto-generated method stub
				if (!(obj1 instanceof CoordTreeNode) && (obj2 instanceof CoordTreeNode)) {
					throw new ClassCastException("CoordTreeNode object expected");
				}
				
				return ((CoordTreeNode)obj1).x.compareTo(((CoordTreeNode)obj2).x);
			}
}
		
		// ***************** START OF COORD TREE MEMBER VARIABLES AND FUNCTIONS **********************
		
		public CoordTreeRootNode root;
		public int coordState = NESTED_COORDS;
		
		//Constants
		public static final int NESTED_COORDS = 0;
		public static final int INTEGER_COORDS = 1;
		
		public CoordTree() {
			root = new CoordTreeRootNode();
			root.x = new Coord("0");
			root.y = new Coord("0");
			coordState = NESTED_COORDS;
		}
		
		public void AddWebElement(WebElement we) {
			CoordTreeNode temp = new CoordTreeNode();
			temp.x = new Coord(we.getXCoord());
			temp.y = new Coord(we.getYCoord());

			CoordTreeNode tmpNode = new CoordTreeNode(we);
			root.addNodeToChildren(tmpNode);
		}
		
		public boolean convertToIntCoords() {
			boolean retVal = false;
			if (coordState == NESTED_COORDS) {
				CoordTreeNode rt = root;
				
				if ((rt.children==null)||(rt.children.size()==0)) { return true; }
				
//				Sort all elements by y coord then by x
				//first get all unique y coordinates, put them in a list and sort that list
				Vector uniqueY = new Vector();
				Iterator iter = rt.children.iterator();
				while (iter.hasNext()) {
					CoordTreeNode tn = (CoordTreeNode)iter.next();
					if (!uniqueY.contains(tn.y)) { uniqueY.add(tn.y); }
				}
				Coord[] uniqueYArr = (Coord[])uniqueY.toArray(new Coord[0]);
				Arrays.sort(uniqueYArr);
				
				//now generate an array of vectors, group elements by y coordinate
				Vector[] vectorGroup = new Vector[uniqueYArr.length];
				for (int i = 0; i < vectorGroup.length; i++) {
					vectorGroup[i] = new Vector();
				}
				iter = rt.children.iterator();
				while (iter.hasNext()) {
					CoordTreeNode tn = (CoordTreeNode)iter.next();
					int vgIndex = 0;
					while (!uniqueYArr[vgIndex].equals(tn.y)) {
						vgIndex++;
					}
					vectorGroup[vgIndex].add(tn);
				}
				
//				now finally sort each vector by x coordinate
				for (int i = 0; i < vectorGroup.length; i++) {
					Collections.sort(vectorGroup[i], new NodeComparatorByX());
				}
				
//				First find all virtual nodes that will cause a skew and put them in a skew vector
				Vector horizontalSkewNodes = new Vector();
				Vector verticalSkewNodes = new Vector();
				for (int i = 0; i < vectorGroup.length; i++) {
					iter = vectorGroup[i].iterator();
					while (iter.hasNext()) {
						CoordTreeNode tn = (CoordTreeNode)iter.next();
						if (tn.Width() > 1) {
							horizontalSkewNodes.add(tn);
						}
						if (tn.Height() > 1) {
							verticalSkewNodes.add(tn);
						}
					}
				}
				
//				Assign appropriate toX and toY values (most important part)
//				Vertical skew remains, but horizontal skew only applies to same row
				for (int i = 0; i < vectorGroup.length; i++) {
					iter = vectorGroup[i].iterator();
					while (iter.hasNext()) {
						CoordTreeNode tn = (CoordTreeNode)iter.next();
						
						tn.toX = tn.x.iArr[tn.x.iArr.length - 1];
						tn.toY = tn.y.iArr[tn.y.iArr.length - 1];
						
//						Traverse through all horizontal skew nodes on the same row and increment toX by their width - 1
						for (int j = 0; j < horizontalSkewNodes.size(); j++) {
							if ((tn.x.compareTo(((CoordTreeNode)horizontalSkewNodes.elementAt(j)).x) > 0)&&(((CoordTreeNode)horizontalSkewNodes.elementAt(j)).y.equals(tn.y))) {
								tn.toX += ((CoordTreeNode)horizontalSkewNodes.elementAt(j)).Width() - 1;
							}
						}
						
//						Traverse through all vertical skew nodes and increment toY by their height - 1
						for (int j = 0; j < verticalSkewNodes.size(); j++) {
							if (tn.y.compareTo(((CoordTreeNode)verticalSkewNodes.elementAt(j)).y) > 0) {
								tn.toY += ((CoordTreeNode)verticalSkewNodes.elementAt(j)).Height() - 1;
							}
						}
		
					}
				}
				
//				Recursively process children of each node
				iter = rt.children.iterator();
				while (iter.hasNext()) {
					CoordTreeNode tn = (CoordTreeNode)iter.next();
					if ((tn.children != null) && (tn.children.size() > 0)) {
						convertChildrenToIntCoordsRecursive(tn, tn.toX - 1, tn.toY - 1);
					}
				}
				
				retVal = true;
			}
			coordState = INTEGER_COORDS;
			
			return retVal;
		}
		
		public void convertChildrenToIntCoordsRecursive(CoordTreeNode node, int xOffset, int yOffset) {
			if ((node.children==null)||(node.children.size()==0)) { return; }
			
			//Sort all elements by y coord then by x
			//first get all unique y coordinates, put them in a list and sort that list
			Vector uniqueY = new Vector();
			Iterator iter = node.children.iterator();
			while (iter.hasNext()) {
				CoordTreeNode tn = (CoordTreeNode)iter.next();
				if (!uniqueY.contains(tn.y)) { uniqueY.add(tn.y); }
			}
			Coord[] uniqueYArr = (Coord[])uniqueY.toArray(new Coord[0]);
			Arrays.sort(uniqueYArr);
			
			//now generate an array of vectors, group elements by y coordinate
			Vector[] vectorGroup = new Vector[uniqueYArr.length];
			for (int i = 0; i < vectorGroup.length; i++) {
				vectorGroup[i] = new Vector();
			}
			iter = node.children.iterator();
			while (iter.hasNext()) {
				CoordTreeNode tn = (CoordTreeNode)iter.next();
				int vgIndex = 0;
				while (!uniqueYArr[vgIndex].equals(tn.y)) {
					vgIndex++;
				}
				vectorGroup[vgIndex].add(tn);
			}
			
			//now finally sort each vector by x coordinate
			for (int i = 0; i < vectorGroup.length; i++) {
				Collections.sort(vectorGroup[i], new NodeComparatorByX());
			}
			
			//First find all virtual nodes that will cause a skew and put them in a skew vector
			Vector horizontalSkewNodes = new Vector();
			Vector verticalSkewNodes = new Vector();
			for (int i = 0; i < vectorGroup.length; i++) {
				iter = vectorGroup[i].iterator();
				while (iter.hasNext()) {
					CoordTreeNode tn = (CoordTreeNode)iter.next();
					if (tn.Width() > 1) {
						horizontalSkewNodes.add(tn);
					}
					if (tn.Height() > 1) {
						verticalSkewNodes.add(tn);
					}
				}
			}
			
//			Assign appropriate toX and toY values to each node
//			This is the critical section of conversion algorithm
			for (int i = 0; i < vectorGroup.length; i++) {
				iter = vectorGroup[i].iterator();
				while (iter.hasNext()) {
					CoordTreeNode tn = (CoordTreeNode)iter.next();

					tn.toX = tn.x.iArr[tn.x.iArr.length - 1] + xOffset;
					tn.toY = tn.y.iArr[tn.y.iArr.length - 1] + yOffset;
					
//					Traverse through all horizontal skew nodes and increment toX by their width - 1
					for (int j = 0; j < horizontalSkewNodes.size(); j++) {
						if (tn.x.compareTo(((CoordTreeNode)horizontalSkewNodes.elementAt(j)).x) > 0) {
							tn.toX += ((CoordTreeNode)horizontalSkewNodes.elementAt(j)).Width() - 1;
						}
					}
					
//					Traverse through all vertical skew nodes and increment toY by their height - 1
					for (int j = 0; j < verticalSkewNodes.size(); j++) {
						if (tn.y.compareTo(((CoordTreeNode)verticalSkewNodes.elementAt(j)).y) > 0) {
							tn.toY += ((CoordTreeNode)verticalSkewNodes.elementAt(j)).Height() - 1;
						}
					}
				}
			}
			
//			Recursively process children of each node
			iter = node.children.iterator();
			while (iter.hasNext()) {
				CoordTreeNode tn = (CoordTreeNode)iter.next();
				if ((tn.children != null) && (tn.children.size() > 0)) {
					convertChildrenToIntCoordsRecursive(tn, tn.toX - 1, tn.toY - 1);
				}
			}
		}
		
		public HTMLDocument getHTMLDocument() {
			HTMLDocument doc = new HTMLDocument();
			try {
				getHTMLDocumentRecursive(doc, root);
			}catch (Exception ex) { return null; }
			
			return doc;
		}
		
		private void getHTMLDocumentRecursive(HTMLDocument doc, CoordTreeNode node) throws Exception{
			if (node.webElement != null) {
//				Add web element to the document object
				node.webElement.setXCoord(String.valueOf(node.toX));
				node.webElement.setYCoord(String.valueOf(node.toY));
				doc.addWebElement(node.webElement);
			}
			
//			Now process all children if there are any
			if ((node.children!=null)&&(node.children.size()==0)&&(node.webElement == null)) {
//				Then something is wrong
				throw new Exception("Found virtual node with no children.");
			}
			else if ((node.children!=null)&&(node.children.size() > 0)) {
				Iterator iter = node.children.iterator();
				while (iter.hasNext()) {
					CoordTreeNode tn = (CoordTreeNode)iter.next();
					getHTMLDocumentRecursive(doc, tn);
				}
			}
			else {
//				There are no children to process and the web element was already added to doc above
				return;
			}
		}
	}
}