package cz.cuni.amis.pogamut.defcon.utils.quadtree;
   
   import java.util.LinkedList;
   import java.util.List;
   import java.util.regex.Matcher;
   import java.util.regex.Pattern;
   
   import cz.cuni.amis.pogamut.base3d.worldview.object.Location;
   
  /**
   * Node for a {@link cz.cuni.amis.pogamut.defcon.utils.quadtree.QuadTree}.
   * 
   * @author Radek 'Black_Hand' Pibil
   * 
   */
  public class QuadTreeNode {
  	private final QuadTree quadTree;
  	private final double EPSILON = 1d;
  
  	private double x1, x2, y1, y2;
  
  	private QuadTreeNode[] nodes = null;
  	private QuadTreeNode parent;
  	private LinkedList<List<Location>> subList;
  	private Location center;
  	private double inner_side;
  	private boolean label = false;
  	private static final Pattern pattern = Pattern.compile("\n");
  
  	/**
  	 * Constructor for a tree node. Suitable only inside QuadTree code
  	 * 
  	 * @param quadTree
  	 *            parent tree
  	 * @param x1
  	 *            upper left x coord
  	 * @param y1
  	 *            upper left y coord
  	 * @param x2
  	 *            lower right x coord
  	 * @param y2
  	 *            lower right y coord
  	 * @param parent
  	 *            parent node
  	 * @param subList
  	 *            list of lists of vertices that constitute a line crossing
  	 *            through this nodes rectangle
  	 */
  	public QuadTreeNode(QuadTree quadTree, double x1, double y1, double x2,
  			double y2,
  			QuadTreeNode parent, List<List<Location>> subList) {
  		this.quadTree = quadTree;
  		this.x1 = x1;
  		this.x2 = x2;
  		this.y1 = y1;
  		this.y2 = y2;
  		this.parent = parent;
  		inner_side = (x2 - x1) / 2;
  		center = new Location(x1 + inner_side, y1 + inner_side);
  
  		this.subList = findVerticesFormingIntersectingLines(subList);
  
  		if (inner_side < EPSILON)
  			return;
  
  		subdivide();
  	}
  
  	public final double getX1() {
  		return x1;
  	}
  
  	public final double getX2() {
  		return x2;
  	}
  
  	public final double getY1() {
  		return y1;
  	}
  
  	public final double getY2() {
  		return y2;
  	}
  
  	/**
  	 * Creates new nodes for this node, unless intersecting lines are exactly
  	 * the same as this node's rectangle
  	 */
  	private void subdivide() {
  		if (subList.isEmpty())
  			return;
  
  		if (RectangularFillTester.isSameRectangle(
  				subList.getFirst(),
  				x1,
  				y1,
  				x2,
  				y2))
  			return;
 
 		nodes = new QuadTreeNode[4];
 
 		nodes[0] = new QuadTreeNode(
 				this.quadTree,
 				x1,
 				y1,
 				x1 + inner_side,
 				y1 + inner_side,
 				this,
 				subList);
 		nodes[1] = new QuadTreeNode(
 				this.quadTree,
 				x1 + inner_side,
 				y1,
 				x2,
 				y1 + inner_side,
 				this,
 				subList);
 		nodes[2] = new QuadTreeNode(
 				this.quadTree,
 				x1,
 				y1 + inner_side,
 				x1 + inner_side,
 				y2,
 				this,
 				subList);
 		nodes[3] = new QuadTreeNode(
 				this.quadTree,
 				x1 + inner_side,
 				y1 + inner_side,
 				x2,
 				y2,
 				this,
 				subList);
 	}
 
 	/**
 	 * Filters out vertices of the parent's polygon that do not produce a line
 	 * intersecting this node.
 	 * 
 	 * @param sections
 	 *            list of lists of vertices forming parent's intersecting lines
 	 * @return filtered vertices
 	 */
 	private LinkedList<List<Location>> findVerticesFormingIntersectingLines(
 			List<List<Location>> sections) {
 
 		LinkedList<List<Location>> filteredVertices =
 				new LinkedList<List<Location>>();
 
 		if (sections.isEmpty())
 			return filteredVertices;
 
 		LinkedList<Location> current = new LinkedList<Location>();
 
 		for (List<Location> vertices : sections) {
 			Location last = null;
 
 			for (Location vertex : vertices) {
 
 				if (last == null) {
 					last = vertex;
 					continue;
 				}
 
 				if (lineIntersectsRectangle(last.getX(), last.getY(),
 						vertex.getX(), vertex.getY(),
 						x1, y1, x2, y2)) {
 					if (current.isEmpty()
 							|| current.getLast() != last) {
 						current.add(last);
 					}
 					current.add(vertex);
 					label = true;
 				} else {
 					if (!current.isEmpty()) {
 						filteredVertices.add(current);
 						current = new LinkedList<Location>();
 					}
 				}
 
 				last = vertex;
 			}
 
 			if (!current.isEmpty()) {
 				filteredVertices.add(current);
 				current = new LinkedList<Location>();
 			}
 		}
 
 		if (!filteredVertices.isEmpty()
 				&& ((LinkedList<Location>) filteredVertices.getFirst())
 						.getFirst() ==
 					((LinkedList<Location>) filteredVertices.getLast())
 							.getLast()) {
 			LinkedList<Location> tmp = (LinkedList<Location>) filteredVertices
 					.pollLast();
 			tmp.pollLast();
 			if (!filteredVertices.isEmpty()) {
 				tmp.addAll(filteredVertices.pollFirst());
 			}
 			filteredVertices.addFirst(tmp);
 		}
 
 		return filteredVertices;
 	}
 
 	/**
 	 * Checks whether given point [px, py] is inside the rectangle [x1, y1, x2,
 	 * y2].
 	 * 
 	 * @param px
 	 * @param py
 	 * @param x1
 	 * @param y1
 	 * @param x2
 	 * @param y2
 	 * @return true if point is in rectangle
 	 */
 	private boolean pointInRectangle(double px, double py, double x1,
 			double y1, double x2, double y2) {
 		return (px >= x1 && px < x2 && py >= y1 && py < y2);
 	}
 
 	/**
 	 * Checks whether line [lx1, ly1, lx2, ly2] intersects given rectangle [x1,
 	 * y1, x2, y2] somewhere.
 	 * 
 	 * @param lx1
 	 * @param ly1
 	 * @param lx2
 	 * @param ly2
 	 * @param x1
 	 * @param y1
 	 * @param x2
 	 * @param y2
 	 * @return true if line intersects given rectangle
 	 */
 	private boolean lineIntersectsRectangle(
 			double lx1, double ly1, double lx2, double ly2,
 			double x1, double y1, double x2, double y2) {
 
 		if (pointInRectangle(lx1, ly1, x1, y1, x2, y2))
 			return true;
 
 		if (pointInRectangle(lx2, ly2, x1, y1, x2, y2))
 			return true;
 
 
 		if (ly2 - ly1 == 0) {
 			return (y1 <= ly1 && ly1 < y2 && ((lx1 < x1 && x1 <= lx2) || (lx2 < x1 && x1 <= lx1)));
 		}
 
 		if (lx2 - lx1 == 0) {
 			return (x1 <= lx1 && lx1 < x2 && ((ly1 < y1 && y1 <= ly2) || (ly2 < y1 && y1 <= ly1)));
 		}
 
 		double t = (lx2 - lx1) / (ly2 - ly1), x = 0, y = 0;
 
 		// x = lx1 + (lx2 - lx1)*t
 		// y = ly1 + (ly2 - ly1)*t
 
 		// ---> top
 		// dir vect [ lx2 - lx1, ly2 - ly1 ]
 
 
 		if (ly1 > y1 && ly2 <= y1 ||
 				ly1 <= y1 && ly2 > y1) {
 
 			// y = y1
 			x = lx1 + t * (y1 - ly1);
 
 			if (x1 <= x && x < x2)
 				return true;
 		}
 
 		// ---> bottom
 
 		if (ly1 > y2 && ly2 <= y2 ||
 				ly1 <= y2 && ly2 > y2) {
 
 			// y = y2
 			x = lx1 + t * (y2 - ly1);
 
 			if (x1 <= x && x < x2)
 				return true;
 
 		}
 
 		// ---> left
 		// dir vect [ lx2 - lx1, ly2 - ly1 ]
 
 		if (lx1 > x1 && lx2 <= x1 ||
 				lx1 <= x1 && lx2 > x1) {
 
 			// x = x1
 			y = ly1 + (x1 - lx1) / t;
 
 			if (y1 <= y && y < y2)
 				return true;
 		}
 
 		// ---> right
 		// ! NO REAL NEED FOR THIS ONE BECAUSE LINE HAS TO CROSS RECT AT LEAST
 		// TWICE
 
 		return false;
 	}
 
 	/**
 	 * Retrieves a point [ (x1 + x2) / 2, (y1 + y2) / 2 ].
 	 * 
 	 * @return center point of this node
 	 */
 	public Location getCenter() {
 		return center;
 	}
 
 	/**
 	 * Returns the upper left child node. If it exists, otherwise throws an
 	 * exception.
 	 * 
 	 * @return upper left child node
 	 */
 	public final QuadTreeNode getFirst() {
 		return nodes[0];
 	}
 
 	/**
 	 * Returns the upper right child node. If it exists, otherwise throws an
 	 * exception.
 	 * 
 	 * @return upper right child node
 	 */
 	public final QuadTreeNode getSecond() {
 		return nodes[1];
 	}
 
 	/**
 	 * Returns the lower left child node. If it exists, otherwise throws an
 	 * exception.
 	 * 
 	 * @return lower left child node
 	 */
 	public final QuadTreeNode getThird() {
 		return nodes[2];
 	}
 
 	/**
 	 * Returns the lower right child node. If it exists, otherwise throws an
 	 * exception.
 	 * 
 	 * @return lower right child node
 	 */
 	public final QuadTreeNode getFourth() {
 		return nodes[3];
 	}
 
 	/**
 	 * Returns an array containing all nodes (if there are any). Nodes are in
 	 * the following order [ ul, ur, ll, lr ]
 	 * 
 	 * @return array of child nodes
 	 */
 	public final QuadTreeNode[] getNodes() {
 		return nodes;
 	}
 
 	/**
 	 * Returns the parent node of this node
 	 * 
 	 * @return parent node
 	 */
 	public final QuadTreeNode getParent() {
 		return parent;
 	}
 
 	/*
 	 * public boolean pointInPolygon(double x, double y, LinkedList<Location>
 	 * poly) {
 	 * 
 	 * Location last = poly.getLast(); boolean oddNodes = false;
 	 * 
 	 * for (Location current : poly) { if (current.getY() < y && last.getY() >=
 	 * y || last.getY() < y && current.getY() >= y) { if (current.getX() + (y -
 	 * current.getY()) / (last.getY() - current.getY()) (last.getY() -
 	 * current.getX()) < x) { oddNodes = !oddNodes; } } last = current; }
 	 * 
 	 * return oddNodes; }
 	 * 
 	 * 
 	 * public boolean[] pointsInPolygon( LinkedList<Location> locations,
 	 * LinkedList<Location> poly) {
 	 * 
 	 * Location last = poly.getLast(); boolean[] oddNodes = new
 	 * boolean[locations.size()];
 	 * 
 	 * for (Location current : poly) { int i = 0; for (Location location :
 	 * locations) {
 	 * 
 	 * if (current.getY() <= location.getY() && last.getY() >= location.getY()
 	 * || last.getY() <= location.getY() && current.getY() >= location.getY()) {
 	 * if (current.getX() + (location.getY() - current.getY()) / (last.getY() -
 	 * current.getY()) (last.getY() - current.getX()) < location .getX()) {
 	 * oddNodes[i] = !oddNodes[i]; } } last = current; ++i; } }
 	 * 
 	 * return oddNodes; }
 	 */
 	
 	@Override
 	public String toString() {
 		StringBuilder builder = new StringBuilder();
 
 		builder.append(String.format(
 				"o{%.1f, %.1f, %.1f, %.1f}[",
 				x1,
 				y1,
 				x2,
 				y2));
 
 		builder.append(label);
 
 		if (nodes == null) {
 			builder.append("]");
 			return builder.toString();
 		}
 
 		builder.append("\n");
 
 		Matcher matcher;
 
 		if (nodes[0] != null) {
 			matcher = pattern.matcher(nodes[0].toString());
 
 			builder.append("    ");
 			builder.append(matcher.replaceAll("\n    "));
 			builder.append("\n");
 		}
 		if (nodes[1] != null) {
 			matcher = pattern.matcher(nodes[1].toString());
 
 			builder.append("    ");
 			builder.append(matcher.replaceAll("\n    "));
 			builder.append("\n");
 		}
 		if (nodes[2] != null) {
 			matcher = pattern.matcher(nodes[2].toString());
 
 			builder.append("    ");
 			builder.append(matcher.replaceAll("\n    "));
 			builder.append("\n");
 		}
 		if (nodes[3] != null) {
 			matcher = pattern.matcher(nodes[3].toString());
 
 			builder.append("    ");
 			builder.append(matcher.replaceAll("\n    "));
 			builder.append("\n");
 		}
 		if (subList != null && !subList.isEmpty()) {
 			builder.append("    ");
 			builder.append("{");
 			builder.append(subList.toString());
 			builder.append("}\n");
 		}
 		builder.append("]");
 		return builder.toString();
 	}
 
 	/**
 	 * All nodes through which a line passes are labeled. Other nodes can be
 	 * labeled by user.
 	 * 
 	 * @return is node labeled
 	 */
 	public final boolean isLabeled() {
 		return label;
 	}
 
 	/**
 	 * Use for you own purposes. Perhaps, you want to label the whole inside of
 	 * the polygon?
 	 * 
 	 * @param value
 	 *            set to true or false
 	 */
 	public final void setLabel(boolean value) {
 		label = value;
 	}
 
 	/**
 	 * Returns the width of this node.
 	 * 
 	 * @return width
 	 */
 	public double getSize() {
 		return Math.abs(x2 - x1);
 	}
 }