package net.thewebsitedoctor.gmap;
import java.util.*;
import org.w3c.dom.*;
import org.apache.xerces.dom.*;

/**
 *  Support functions for <a href="http://www.google.com/apis/maps/">Google Maps</a>.
 *
 *  <p>Provides static methods that can be called from
 *  <a href="http://xml.apache.org/xalan-j/">Xalan</a> as a
 * <a href="http://xml.apache.org/xalan-j/extensions.html#java-namespace">Java extension</a>
 *  to support <a href="http://www.w3.org/TR/xslt">XSLT</a> scripts
 *  that generate data for input to the
 *  <a href="http://www.google.com/apis/maps/">Google Maps API</a>.</p>
 *
 *  <p>Copyright 2007 Walter O. Haas</p>
 *
 *  <p>This program is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU General Public License as
 *  published by the Free Software Foundation; either version 2 of the
 *  License, or (at your option) any later version.</p>
 *
 *  <p>This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 *  General Public License for more details.</p>   
 *
 *  <p>You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
 *  02110-1301 USA </p>
 *
 *  @author <a href="http://www.xmission.com/~haas/">Walter O. Haas</a>
 *  @version $Id: GMap2.java,v 1.2 2007/05/08 13:46:10 haas Exp $
 *  @see GMap2Test
 */
public class GMap2 {

    /**
     *  minimum increment
     */
    private static final double verySmall = 0.00001;

    private static double[] zoomLevelBreaks;


    /**
     *  Stores one point on a polyline.
     */
    static private class Point {

	/**
	 *  Latitude of the point on the earth's surface
	 */
	double lat;

	/**
	 *  Longitude of the point on the earth's surface
	 */
    	double lon;

	/**
	 *  Distance from the point's enclosing line segment as
	 *  calculated by the Douglas-Peucker algorithm in
	 *  {@link GMap2#dpEncode}
	 */
    	double dist = Double.NaN;

	/**
	 *  Constructor
	 *  @param lat  Latitude
	 *  @param lon  Longitude
	 */
    	Point(double lat, double lon) {
	    this.lat = lat;
	    this.lon = lon;
    	}
    } // private class Point

    /**
     *  Defines a segment of a polyline as the indexes of the two
     *  endpoints of the segment.
     */
    static private class Segment {
	/**
	 *  First point of pair.  Value from zero to last point in
	 *  line.
	 */
	int first;

	/**
	 *  Last point of pair.  Value from <code>first+1</code> to
	 *  last point in the line
	 */
	int last;

	/**
	 *  Constructor
	 */
	Segment(int first, int last) {
	    this.first = first;
	    this.last = last;
	}
    } // private class Segment

    /**
     *  Encode polyline from a DOM tree.
     *
     *  <p>This is a Java version of
     *  <a href="http://facstaff.unca.edu/mcmcclur/GoogleMaps/EncodePolyline/">Mark McClure's JavaScript program</a>,
     *  modified to be called as a Xalan Java extension.
     *  The DOM tree format is
     *  <pre>
          &lt;path&gt;
            &lt;coordinates&gt;<i>lng</i>,<i>lat</i>&lt;/coordinates&gt;
            &lt;coordinates&gt;<i>lng</i>,<i>lat</i>&lt;/coordinates&gt;
            &lt;coordinates&gt;<i>lng</i>,<i>lat</i>&lt;/coordinates&gt;
            ...
          &lt;/path&gt;
        </pre>
     *  where <i>lng</i>,<i>lat</i> is a longitude, latitude pair
     *  describing a point on the earth's surface.</p>
     *  @param nList       DOM tree containing coordinates for polyline
     *  @param zoomFactor  Zoom size between levels
     *  @param numLevels   Number of zoom levels
     *  @return  DOM tree containing encoded points and levels
     */
    public static Node encodePolyline(NodeList nList,
				      int zoomFactor, int numLevels)
	throws GMap2BadArgException {
	
	Node root = nList.item(0);
	if (root == null) {
	    throw new GMap2BadArgException();
	}
	ArrayList<Point> points = new ArrayList<Point>();
	
	//  Table of level breakpoints
	zoomLevelBreaks = new double[numLevels];
	for (int i=0; i < numLevels; i++) {
	    zoomLevelBreaks[i] = verySmall * Math.pow(zoomFactor,
						      numLevels-i-1);
	}

	//  Walk the input DOM tree to find the coordinates of each
	//  point of the polyline and store the coordinates in "points"
	if (root.hasChildNodes()) {
	    NodeList nl = root.getChildNodes();
	    for (int i=0; i<nl.getLength(); i++) {
		if (nl.item(i).getNodeName() == "coordinates") {
		    NodeList cl = nl.item(i).getChildNodes();
		    String value = nl.item(i).getFirstChild().getNodeValue();
		    String[] sCoords = new String[2];
		    sCoords = value.split(",", 2);
		    points.add(new Point(Double.valueOf(sCoords[1]),
					 Double.valueOf(sCoords[0])));
		}
	    }
	} else {
	    throw new GMap2BadArgException();
	}

	StringBuilder encoded_levels = new StringBuilder();
	String encoded_points = new String();
	if (points.size() > 0) {
	    // End points get an arbitrarily large distance which will
	    // cause them to be visible at any zoom level
	    points.get(0).dist = verySmall * Math.pow(zoomFactor, numLevels);
	    points.get(points.size()-1).dist =
		verySmall * Math.pow(zoomFactor, numLevels);

	    // Compute the zoom level for every other point to be visible
	    // usiing the DP algorithm
	    dpEncode(points);

	    // Generate the encoded level string from computed zoom levels
	    for (int i=0; i<points.size(); i++) {
		if (!Double.isNaN(points.get(i).dist)) {
		    encoded_levels.append(
			  encodeNumber(numLevels
			       - computeLevel(points.get(i).dist)-1));
		} else {
		    System.out.format("ignoring %f,%f%n",
				      points.get(i).lon, points.get(i).lat);
		}
	    }

	    // Generate the encoded points string
	    encoded_points = createEncodings(points);
	}

	//  Generate and return a DOM tree with the encoded polyline
	//  Very simple DOM tree, but it's the only way to pass back
	//  two strings at once.
        DocumentImpl encodedLine = new DocumentImpl();
        encodedLine.setErrorChecking(true);
        Element encodedLineRoot = encodedLine.createElement("encodedLine");
        encodedLine.appendChild(encodedLineRoot);
        Element encodedPoints = encodedLine.createElement("encodedPoints");
        encodedLineRoot.appendChild(encodedPoints);
        Text pointsElement =
	    encodedLine.createTextNode(encoded_points);
        encodedPoints.appendChild(pointsElement);
        Element encodedLevels = encodedLine.createElement("encodedLevels");
        encodedLineRoot.appendChild(encodedLevels);
        Text levels = encodedLine.createTextNode(encoded_levels.toString());
        encodedLevels.appendChild(levels);
	return encodedLine;
    }

    /**
     *  Calculates the zoom level at which to display each point in
     *  the polyline.
     *
     *  This is the
     *  <a href="http://geometryalgorithms.com/Archive/algorithm_0205/algorithm_0205.htm#Douglas-Peucker%20Algorithm">Douglas-Peucker algorithm</a>
     *  adapted for encoding.  Rather than eliminating points, we record
     *  their distance from the segment which occurs at that recursive
     *  step.  These distances are converted to zoom levels later.
     *  @param points  Polyline to be encoded.  At entry, Point.dist
     *                 is NaN for each point of the polyline except
     *                 the end points.  At return, the value in
     *                 Point.dist has been set to select the zoom
     *                 level at which the point is displayed; if
     *                 Point.dist is still NaN for some point, that
     *                 point is never displayed. 
     */
    private static void dpEncode(ArrayList<Point> points) {
	double maxDist = 0.0;
	double temp;
	ArrayDeque<Segment> stack = new ArrayDeque<Segment>();
	Segment current;
	int maxLoc = 0;

	//  A line two points long is the degenerate case, there is
	//  no point eligible for reduction
	if (points.size() > 2) {

	    //  The line has more than two points, so push the whole
	    //  line onto the stack
	    stack.push(new Segment(0, points.size()-1));

	    //  Find that point most distant from the line, then if it
	    //  is more distant than a very small amount, recursively
	    //  find the most distant point from each of the line
	    //  segments before and after that point.
	    while (stack.size() > 0) {

		//  Find that point which is most distant from the
		//  line segment now on top of the stack
		current = stack.pop();
		maxDist = 0;

		//  If there are only two points in the line segment,
		//  this loop falls through immediately leaving
		//  maxDist == 0 so no recursion will occur.
		for (int i = current.first+1; i<current.last; i++) {
		    temp = distance(points.get(i),
				    points.get(current.first),
				    points.get(current.last));
		    if (temp > maxDist) {
			maxDist = temp;
			maxLoc = i;
		    }
		}

		//  If the most distant point is more than a very
		//  small distance from the line segment, recurse to
		//  the two line segments before and after.
		if (maxDist > verySmall) {

		    //  Remember the distance value computed for this
		    //  point.  It will control the zoom level at
		    //  which this point is displayed.
		    points.get(maxLoc).dist = maxDist;
		    stack.push(new Segment(current.first, maxLoc));
		    stack.push(new Segment(maxLoc, current.last));
		}
	    }
	}

    } // private static void dpEncode()

    /**
     *  Compute distance between a point and a line segment.
     *  @param  p0  Point
     *  @param  p1  One end of a line segment
     *  @param  p2  The other end of a line segment
     *  @return distance from point p0 to line segment [p1,p2]
     */
    private static double distance(Point p0, Point p1, Point p2) {
	double u;
	double out = 0.0;

	if ( (p1.lat == p2.lat)
	     && (p1.lon == p2.lon) ) {
	    //  Zero-length line segment, ie. the end points are identical
	    out = Math.sqrt(Math.pow(p2.lat-p0.lat,2)
			    + Math.pow(p2.lon-p0.lon,2));
	} else {
	    //  Non-zero-length line segment.
	    u = ((p0.lat-p1.lat)*(p2.lat-p1.lat)
		 + (p0.lon-p1.lon)*(p2.lon-p1.lon))
		/(Math.pow(p2.lat-p1.lat,2) + Math.pow(p2.lon-p1.lon,2));
  
	    if(u <= 0) {
		out = Math.sqrt(Math.pow(p0.lat - p1.lat,2)
				+ Math.pow(p0.lon - p1.lon,2));
	    }
	    if(u >= 1) {
		out = Math.sqrt(Math.pow(p0.lat - p2.lat,2)
				+ Math.pow(p0.lon - p2.lon,2));
	    }
	    if(0 < u && u < 1) {
		out = Math.sqrt(Math.pow(p0.lat-p1.lat-u*(p2.lat-p1.lat),2) +
				Math.pow(p0.lon-p1.lon-u*(p2.lon-p1.lon),2));
	    }
	}
	return out;

    } // private static void distance()

    /**
     *  Compute zoom level of a point.
     *
     *  Compute the appropriate zoom level of a point in terms of it's 
     *  distance from the relevant segment in the DP algorithm.
     */
    private static int computeLevel(double dd) {
	int lev = 0;

	if (dd > verySmall) {
	    while (dd < zoomLevelBreaks[lev]) {
		lev++;
	    }
	}
	return lev;
    } // private static char computeLevel()

    /**
     *  Encode points.
     *
     *  This function is very similar to Google's
     *  <a href="http://www.google.com/apis/maps/documentation/polyline.js">
     *  polyline.js</a>
     *  The key difference is that not all points are encoded, 
     *  since some were eliminated by Douglas-Peucker.
     */
    private static String createEncodings(ArrayList<Point> points) {
	Point point;
	long plat = 0;
	long plng = 0;
	StringBuilder encoded_points = new StringBuilder();

	for(int i = 0; i < points.size(); i++) {
	    point = points.get(i);
	    if (!Double.isNaN(point.dist)) {
		double lat = point.lat;
		double lng = point.lon;
		long late5 = (long)Math.floor(lat * 1e5);
		long lnge5 = (long)Math.floor(lng * 1e5);
		long dlat = late5 - plat;
		long dlng = lnge5 - plng;
		plat = late5;
		plng = lnge5;
		encoded_points.append(encodeSignedNumber(dlat)
				      + encodeSignedNumber(dlng));
	    }
	}
	return encoded_points.toString();
    } // private static void createEncodings()

    /**
     *  Encode a 32-bit signed binary number in little-endian base64.
     *
     *  See the <a href="http://www.google.com/apis/maps/documentation/polylinealgorithm.html">Google Maps API documentation</a>
     *  of how this works
     *  @param number  Number to encode
     *  @return Number encoded in base64
     */
    private static String encodeSignedNumber(long number) {
	number = number << 1;
	if (number < 0) {
	    number = number ^ -1;
	}
	return encodeNumber(number);
    } // private String encodeSignedNumber()

    /**
     *  Encode a 32-bit positive binary number in little-endian base64.
     *
     *  See the <a
     *  href="http://www.google.com/apis/maps/documentation/polylinealgorithm.html">Google Maps API documentation</a> of how this works
     *  @param number  Number to encode
     *  @return Number encoded in base64
     */
    private static String encodeNumber(long number) {
	int[] chunks = new int[6];

	chunks[0] = ((int)(number & 0x0000001F)      );
	chunks[1] = ((int)(number & 0x000003E0) >>  5);
	chunks[2] = ((int)(number & 0x00007C00) >> 10);
	chunks[3] = ((int)(number & 0x000F8000) >> 15);
	chunks[4] = ((int)(number & 0x01F00000) >> 20);
	chunks[5] = ((int)(number & 0x3E000000) >> 25);

	//  Find which chunks are significant (from 1 to 6 will be)
	int last_chunk;
	for (last_chunk = 5; last_chunk > 0; last_chunk--) {
	    if (chunks[last_chunk] != 0) {
		break;
	    }
	}

	for (int i = 0; i < last_chunk; i++) {
	    chunks[i] |= 0x20;
	}

	char[] enc_chunk = new char[2];
	StringBuilder result = new StringBuilder();
	for (int i = 0; i <= last_chunk; i++) {
	    enc_chunk = Character.toChars(chunks[i] + 63);
	    result.append(enc_chunk[0]);
	}
	return result.toString();
    } // private String encodeNumber()

} // public class GMap2