using System;
using System.Text;
using System.Collections.Generic;
using System.Collections;

/// <summary>
/// Author:		Gabriel Svennerberg
/// Created:	November 2008
/// E-mail:		gabriel@svennerberg.com
/// Url:		http://www.svennerberg.com/
///
/// Version:	0.2
/// Reimplementation of Mark Rambows Java PolylineEncoder
/// which is a reimplementation of Mark McClures Javascript PolylineEncoder
/// 
/// I have basically just ported Mark Rambows Java class to C# and made some small 
/// modifications that better suits me and/or C#. Fredrik Jonsson at http://www.freddes.se
/// helped me with some of the conversion.
/// 
/// All the mathematical logic is more or less copied by McClure
/// For more info please visit http://facstaff.unca.edu/mcmcclur/GoogleMaps/EncodePolyline/
/// 
/// Example usage:
/// 
/// Create an instance of PolyLineEncoder
/// 
///		PolylineEncoder encoder = new PolylineEncoder();
///		
///	Encode the polyline
///	EncodedPolyline polyLine = encoder.Encode(points);
///	
/// License: GPL
/// May be used and changed freely
/// No warranty apply
/// 
/// </summary>
public class PolylineEncoder
{
	public int NumLevels { get; set; }
	public double VerySmall { get; set; }
	public bool ForceEndPoints { get; set; }
	private double[] ZoomLevelBreaks { get; set; }
	private int ZoomFactor { get; set; }
	
	
	/// <summary>
	/// Constructor
	/// </summary>
	/// <param name="numLevels"></param>
	/// <param name="zoomFactor"></param>
	/// <param name="verySmall"></param>
	/// <param name="forceEndpoints"></param>
	public PolylineEncoder(int? numLevels, int? zoomFactor, double? verySmall, bool? forceEndpoints)
	{

		if (numLevels.HasValue)
		{
			this.NumLevels = numLevels.Value;
		}
		else
		{
			this.NumLevels = 18;
		}
		
		if (zoomFactor.HasValue)
		{
			this.ZoomFactor = zoomFactor.Value;
		}
		else
		{
			this.ZoomFactor = 2;
		}

		if (verySmall.HasValue)
		{
			this.VerySmall = verySmall.Value;
		}
		else
		{
			this.VerySmall = 0.00001;
		}

		if (forceEndpoints.HasValue)
		{
			this.ForceEndPoints = forceEndpoints.Value;
		}
		else
		{
			this.ForceEndPoints = true;
		}
		

		this.ZoomLevelBreaks = new double[NumLevels];

		for (int i = 0; i < this.NumLevels; i++)
		{
			this.ZoomLevelBreaks[i] = this.VerySmall * Math.Pow(this.ZoomFactor, this.NumLevels - i - 1);
		}
	}
	
	/// <summary>
	/// Constructor
	/// </summary>
	public PolylineEncoder()
	{
		this.NumLevels = 18;
		this.ZoomFactor = 2;
		this.VerySmall = 0.00001;
		this.ForceEndPoints = true;
		
		this.ZoomLevelBreaks = new double[this.NumLevels];

		for (int i = 0; i < this.NumLevels; i++)
		{
			this.ZoomLevelBreaks[i] = this.VerySmall * Math.Pow(this.ZoomFactor, this.NumLevels - i - 1);
		}
	}


		
	/// <summary>
	/// Douglas-Peucker algorithm, adapted for encoding
	/// </summary>
	/// <param name="points"></param>
	/// <returns></returns>
	public EncodedPolyline Encode(List<Trackpoint> points)
	{			
		int i, maxLoc = 0;
		Stack<int[]> stack = new Stack<int[]>();

		double[] dists = new double[points.Count];
		double maxDist = 0.0, absMaxDist = 0.0, temp = 0.0;
		int[] current;
		string encodedPoints = string.Empty;
		string encodedLevels = string.Empty;
		string encodedPointsLiteral = string.Empty;

		if (points.Count > 2)
		{
			int[] stackVal = new int[] { 
				0, 
				(points.Count - 1) 
			};
			stack.Push(stackVal);


			while (stack.Count > 0)
			{
				current = stack.Pop();
				maxDist = 0;

				for (i = current[0] + 1; i < current[1]; i++)
				{
					temp = this.Distance(points[i], points[current[0]], points[current[1]]);

					if (temp > maxDist)
					{
						maxDist = temp;
						maxLoc = i;
						if (maxDist > absMaxDist)
						{
							absMaxDist = maxDist;
						}
					}
				}
				if (maxDist > this.VerySmall)
				{
					dists[maxLoc] = maxDist;
					int[] stackValCurMax = { current[0], maxLoc };
					stack.Push(stackValCurMax);
					int[] stackValMaxCur = { maxLoc, current[1] };
					stack.Push(stackValMaxCur);
				}
			}
		}


		encodedPoints = CreateEncodings(points, dists);
		encodedLevels = EncodeLevels(points, dists, absMaxDist);

		EncodedPolyline polyline = new EncodedPolyline(encodedPoints, encodedLevels, this.ZoomFactor, this.NumLevels);

		return polyline;
	}
	
	/// <summary>
	/// Method to make it possible to encode a polyline from a List
	/// of double[] with the coordinates like this
	///		double[0] = Latitude
	///		double[1] = Longitude
	/// </summary>
	/// <param name="points"></param>
	/// <returns>An encoded polyline</returns>
	public EncodedPolyline EncodeFromList(List<double[]> points)
	{
		List<Trackpoint> trackPoints = new List<Trackpoint>();
		foreach (double[] coords in points)
		{
			Trackpoint tp = new Trackpoint(coords);
			trackPoints.Add(tp);
		}
		return Encode(trackPoints);
	}
	 
	/// <summary>
	/// distance(p0, p1, p2) computes the distance between the point p0 and the
	/// segment [p1,p2]. This could probably be replaced with something that is a
	/// bit more numerically stable.
	/// </summary>
	/// <param name="p0"></param>
	/// <param name="p1"></param>
	/// <param name="p2"></param>
	/// <returns>double</returns>
	/// 
	public double Distance(Trackpoint p0, Trackpoint p1, Trackpoint p2) {
		double u = 0.0;
		double outVal = 0.0;

		if (p1.Latitude == p2.Latitude && p1.Longitude== p2.Longitude) {
			outVal = Math.Sqrt(Math.Pow(p2.Latitude - p0.Latitude, 2) + Math.Pow(p2.Longitude - p0.Longitude, 2));
		} else {
			u = ((p0.Latitude - p1.Latitude)
					* (p2.Latitude - p1.Latitude) 
					+ (p0.Longitude - p1.Longitude)
					* (p2.Longitude - p1.Longitude))
					/ (Math.Pow(p2.Latitude - p1.Latitude, 2) 
					+ Math.Pow(p2.Longitude - p1.Longitude, 2)
					);

			if (u <= 0) {
				outVal = Math.Sqrt(Math.Pow(p0.Latitude - p1.Latitude, 2)
						+ Math.Pow(p0.Longitude - p1.Longitude, 2));
			}
			if (u >= 1) {
				outVal = Math.Sqrt(Math.Pow(p0.Latitude - p2.Latitude, 2)
						+ Math.Pow(p0.Longitude - p2.Longitude, 2));
			}
			if (0 < u && u < 1) {
				outVal = Math.Sqrt(Math.Pow(p0.Latitude - p1.Latitude - u 
						* (p2.Latitude - p1.Latitude), 2)
						+ Math.Pow(p0.Longitude - p1.Longitude - u
						* (p2.Longitude - p1.Longitude), 2)
						);
			}
		}
		return outVal;
	}


	/// <summary>
	/// set the points that should be encoded all points have to be in
	/// the following form: Latitude, longitude\n
	/// </summary>
	/// <param name="points"></param>
	/// <returns>A list of trackpoints</returns>
	public static List<Trackpoint> PointsToTrack(String points)
	{
		List<Trackpoint> trk = new List<Trackpoint>();
		string[] str = points.Split('\n');

		for (int i = 0; i < str.Length; i++)
		{
			string[] pointStrings = str[i].Split(',');
			trk.Add(new Trackpoint(double.Parse(pointStrings[0]), double.Parse(pointStrings[1])));
		}
		return trk;
	}

	/// <summary>
	/// set the points that should be encoded all points have to be in
	/// the following form: Longitude,Latitude,Altitude"_"...
	/// </summary>
	/// <param name="points"></param>
	/// <returns></returns>
	public static List<Trackpoint> KmlLineStringToTrack(String points)
	{
		List<Trackpoint> trk = new List<Trackpoint>();
		string[] str = points.Split(' ');
		for (int i = 0; i < str.Length; i++)
		{
			String[] pointStrings = str[i].Split(',');
			trk.Add(new Trackpoint(double.Parse(pointStrings[0]), double.Parse(pointStrings[1])));
		}

		return trk;
	}
	
	private static int Floor1e5(double coordinate)
	{
		return (int)Math.Floor(coordinate * 1e5);
	}

	private static String EncodeSignedNumber(int num)
	{
		int sgn_num = num << 1;
		if (num < 0)
		{
			sgn_num = ~(sgn_num);
		}
		return (EncodeNumber(sgn_num));
	}

	private static String EncodeNumber(int num)
	{
		StringBuilder encodeString = new StringBuilder();

		while (num >= 0x20)
		{
			int nextValue = (0x20 | (num & 0x1f)) + 63;
			encodeString.Append((char)(nextValue));
			num >>= 5;
		}

		num += 63;
		encodeString.Append((char)num);

		return encodeString.ToString();
	}

	 
	/// <summary>
	/// Now we can use the previous function to march down the list of points and
	/// encode the levels. Like createEncodings, we ignore points whose distance
	/// (in dists) is undefined.
	/// </summary>
	/// <param name="points"></param>
	/// <param name="dists"></param>
	/// <param name="absMaxDist"></param>
	/// <returns></returns>
	private String EncodeLevels(List<Trackpoint> points, double[] dists, double absMaxDist)
	{
		int i;

		StringBuilder encoded_levels = new StringBuilder();

		if (this.ForceEndPoints)
		{
			encoded_levels.Append(EncodeNumber(this.NumLevels - 1));
		}
		else
		{
			encoded_levels.Append(EncodeNumber(this.NumLevels - ComputeLevel(absMaxDist) - 1));
		}
		
		for (i = 1; i < points.Count - 1; i++)
		{
			if (dists[i] != 0)
			{
				encoded_levels.Append(EncodeNumber(this.NumLevels - ComputeLevel(dists[i]) - 1));
			}
		}
		
		if (this.ForceEndPoints)
		{
			encoded_levels.Append(EncodeNumber(this.NumLevels - 1));
		}
		else
		{
			encoded_levels.Append(EncodeNumber(this.NumLevels - ComputeLevel(absMaxDist) - 1));
		}

		return encoded_levels.ToString();
	}

	

	/// <summary>
	/// This computes the appropriate zoom level of a point in terms of it's
	/// distance from the relevant segment in the DP algorithm. Could be done in
	/// terms of a logarithm, but this approach makes it a bit easier to ensure
	/// that the level is not too large.
	/// </summary>
	/// <param name="absMaxDist"></param>
	/// <returns></returns>
	private int ComputeLevel(double absMaxDist)
	{
		int lev = 0;
		if (absMaxDist > this.VerySmall)
		{
			lev = 0;
			while (absMaxDist < (double)this.ZoomLevelBreaks[lev])
			{
				lev++;
			}
			return lev;
		}
		return lev;
	}

	/// <summary>
	/// Returns the encoding of the points
	/// </summary>
	/// <param name="points"></param>
	/// <param name="dists"></param>
	/// <returns></returns>
	/// 

	private String CreateEncodings(List<Trackpoint> points, double[] dists)
	{
		StringBuilder encodedPoints = new StringBuilder();

		double maxlat = 0, minlat = 0, maxlon = 0, minlon = 0;

		int plat = 0, plng = 0;

		for (int i = 0; i < points.Count; i++)
		{

			// determin bounds (max/min lat/lon)
			if (i == 0)
			{
				maxlat = minlat = points[i].Latitude;
				maxlon = minlon = points[i].Longitude;
			}
			else
			{
				if (points[i].Latitude > maxlat)
				{
					maxlat = points[i].Latitude;
				}
				if (points[i].Latitude < minlat)
				{
					minlat = points[i].Latitude;
				}
				if (points[i].Longitude > maxlon)
				{
					maxlon = points[i].Longitude;
				}
				if (points[i].Longitude < minlon)
				{
					minlon = points[i].Longitude;
				}
			}

			if (dists[i] != 0 || i == 0 || i == points.Count - 1)
			{
				Trackpoint point = points[i];

				int late5 = Floor1e5(point.Latitude);
				int lnge5 = Floor1e5(point.Longitude);

				int dlat = late5 - plat;
				int dlng = lnge5 - plng;

				plat = late5;
				plng = lnge5;

				encodedPoints.Append(EncodeSignedNumber(dlat));
				encodedPoints.Append(EncodeSignedNumber(dlng));

			}
		}
		
		return encodedPoints.ToString();
	}
	
			
	public static Hashtable CreateEncodings(List<Trackpoint> track, int level, int step) {
		Hashtable resultMap = new Hashtable();
		
		StringBuilder encodedPoints = new StringBuilder();
		StringBuilder encodedLevels = new StringBuilder();
		
		int plat = 0;
		int plng = 0;
		int counter = 0;

		int listSize = track.Count;

		Trackpoint trackpoint;

		for (int i = 0; i < listSize; i += step) {
			counter++;
			trackpoint = (Trackpoint)track[i];
			

			int late5 = Floor1e5(trackpoint.Latitude);
			int lnge5 = Floor1e5(trackpoint.Longitude);

			int dlat = late5 - plat;
			int dlng = lnge5 - plng;

			plat = late5;
			plng = lnge5;

			encodedPoints.Append(EncodeSignedNumber(dlat)).Append(EncodeSignedNumber(dlng));
			encodedLevels.Append(EncodeNumber(level));

		}

		resultMap.Add("encodedPoints", encodedPoints.ToString());
		resultMap.Add("encodedLevels", encodedLevels.ToString());
		

		return resultMap;
	}
}


/// <summary>
/// A class representing a point (coordinates)
/// </summary>
public class Trackpoint
{

	public double Latitude { get; set; }
	public double Longitude { get; set; }
	public double Altitude { get; set; }

	public Trackpoint(double lat, double lon)
	{
		this.Latitude = lat;
		this.Longitude = lon;
	}
	public Trackpoint(double lat, double lon, double altitude)
	{
		this.Latitude = lat;
		this.Longitude = lon;
		this.Altitude = altitude;
	}
	public Trackpoint(double[] coords)
	{
		this.Latitude = coords[0];
		this.Longitude = coords[1];
	}
}

/// <summary>
/// A class representing an encoded polyline
/// </summary>
public class EncodedPolyline
{
	public string Points { get; set; }
	public string Levels { get; set; }
	public int ZoomFactor { get; set; }
	public int NumLevels { get; set; }
	
	public EncodedPolyline(string points, string levels, int zoomFactor, int numLevels)
	{
		this.Points = points;
		this.Levels = levels;
		this.ZoomFactor = zoomFactor;
		this.NumLevels = numLevels;
	}
	
}