import java.awt.Point2D;


/**
 *  Utility-class for working with the Google Maps polyline encoding.
 *  The documentation can be found at
 *  {@link http://www.google.com/apis/maps/documentation/overlays.html#Drawing_Polylines}.
 *  
 * @author David Lee Lambert
 */
public class GMapPolylineUtil {

		/**
		 *  This is basically a base64-encoded, sign-magnitude,
		 *  fixed-point representation, also compressed by only
		 *  including significant pentets.  The formal description
		 *  of the algorithm (from Google's wesite) is as follows:
		 *
		 *  <ol>
		 *    <li> Take the initial signed value:<br>
		 *         <b>-179.9832104</b>
		 *    <li> Take the decimal value and multiply it by 1e5, 
		 *         flooring the result:
		 *         <b>-17998321</b>
		 *    <li> Convert the decimal value to binary. Note that 
		 *         a negative value must be inverted and provide 
		 *         padded values toward the byte boundary:<br>
		 *      00000001 00010010 10100001 11110001<br>
		 *      11111110 11101101 10100001 00001110<br>
		 *      11111110 11101101 01011110 00001111<br>
		 *    <li> Shift the binary value:<br>
		 *      11111110 11101101 01011110 00001111 0
		 *    <li> If the original decimal value is negative, 
		 *         invert this encoding:<br>
		 *      00000001 00010010 10100001 11110000 1
		 *    <li>Break the binary value out into 5-bit chunks 
		 *        (starting from the right hand side):<br>
		 *      00001 00010 01010 10000 11111 00001
		 *    <li>Place the 5-bit chunks into reverse order:<br>
		 *      00001 11111 10000 01010 00010 00001
		 *    <li> OR each value with 0x20 if another bit chunk 
		 *       follows:<*>
		 *      100001 111111 110000 101010 100010 000001<br>
		 *    <li>Convert each value to decimal:<br>
		 *      33 63 48 42 34 1
		 *    <li>Add 63 to each value:
		 *      96 126 111 105 97 64
		 *    <li>Convert each value to its ASCII equivalent:
		 *      <b>`~oia&#64;</b>
		 *   </ol>
		 */
   private static String f(double x) { 
      int xx = (int)(x * 1e5),j,i; 
      StringBuffer s = new StringBuffer(6);
 
      xx <<= 1; 
      if (x<0) xx = ~xx; 
      for (j=6; j>=0; j--) 
	 if (((xx>>(5*j))&0x1F)!=0) 
	    break; 
      if (j==-1) j=0;
      for (i=0 ; i<=j ; i++) { 
	 char ch = (char)( (((xx>>(5*i))&0x1F) 
			    | (j==i ? 0x0 : 0x20)) + 63 ); 
	 s.append(ch);
      }
      return s.toString();
   }

		/** 
		 *  Encode a path.  Only the initial points
		 *  and differential distances to successive ones
		 *  are encoded.
		 */
   public static encode(Number[] coordSeq) {
      if (coordSeq==null || coordSeq.length==0) 
	 return "";
      if (coordSeq.length%2 == 1)
	 throw new IllegalArgumentException("even number of points required");
      StringBuffer buf = new StringBuffer(6*coordSeq.length);
      buf.append(f(coordSeq[0]));
      buf.append(f(coordSeq[1]));
      for (int i=2; i<coordSeq.length; i+=2) {
	 buf.append(f(coordSeq[i].doubleValue()
		      -coordSeq[i-2].doubleValue()));
	 buf.append(f(coordSeq[i+1].doubleValue()
		      -coordSeq[i-1].doubleValue()));
      }
      return buf.toString();
   }

   public static encode(float[] coordSeq) {
      if (coordSeq==null) return "";
      Number[] arr = new Number[coordseq.length];
      for (int i=0; i<coordSeq.length; i++)
	 arr[i] = new Float(coordSeq[i]);
      return encode(arr); 
   }

   public static encode(Point2D[] points) {
      if (points==null) return "";
      Number[] arr = new Double[points.length*2];
      for (int i=0; i<points.length; i++) {
	 arr[i*2]  =new Double(points[i].getY());
	 arr[i*2+1]=new Double(points[i].getX());
      }
      return encode(arr);
   }

}