// JavaScript Document

// Encode a signed number in the encode format.
function encodeSignedNumber(num) {
  var sgn_num = num << 1;

  if (num < 0) {
    sgn_num = ~(sgn_num);
  }

  return(encodeNumber(sgn_num));
}

// Encode an unsigned number in the encode format.
function encodeNumber(num) {
	var encodeString = "";
	
	while (num >= 0x20) {
		encodeString += (String.fromCharCode((0x20 | (num & 0x1f)) + 63));
		num >>= 5;
	}
	
	encodeString += (String.fromCharCode(num + 63));
  	
	return encodeString;

}

// Create the encoded bounds.
function createEncodings(points,topoFormat) {
  var i = 0;
  var plat = 0;
  var plng = 0;
  var encoded_points = "";

  for(i = 0; i < points.length; ++i) {
	var point = points[i];
	if(topoFormat){
		var lat = point[0];
		var lng = point[1];
	}else{
		var lat = point.lat();
		var lng = point.lng();
	}

    var late5 = Math.floor(lat * 1e5);
    var lnge5 = Math.floor(lng * 1e5);

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

    plat = late5;
    plng = lnge5;

    encoded_points += encodeSignedNumber(dlat) + encodeSignedNumber(dlng);
  } 

	var re = new RegExp("\\\\", "g");
	var newString = encoded_points.replace(re, "\\\\");

  return newString;
}


// Decode an encoded string into a list of VE lat/lng.
function decodeLine(encoded) {
    var len = encoded.length;
    var index = 0;
    var array = [];
    var lat = 0;
    var lng = 0;
    try
    {
        while (index < len) {
            var b;
            var shift = 0;
            var result = 0;
            do {
                  b = encoded.charCodeAt(index++) - 63;
                  result |= (b & 0x1f) << shift;
                  shift += 5;
            } while (b >= 0x20);
            var dlat = ((result & 1) ? ~(result >> 1) : (result >> 1));
            lat += dlat;

            shift = 0;
            result = 0;
            do {
                  b = encoded.charCodeAt(index++) - 63;
                  result |= (b & 0x1f) << shift;
                  shift += 5;
            } while (b >= 0x20);
            var dlng = ((result & 1) ? ~(result >> 1) : (result >> 1));
            lng += dlng;

            array.push(new GLatLng((lat * 1e-5), (lng * 1e-5)));
        }
    } catch(ex)
    {
        //error in encoding.
    }
    return array;
}

function ComputeDistance(lat1, lon1, lat2, lon2) {
	lat1 = lat1 / 180 * Math.PI; 
	lon1 = lon1 / 180 * Math.PI; 
	lat2 = lat2 / 180 * Math.PI; 
	lon2 = lon2 / 180 * Math.PI; 
	var dlon = lon2 - lon1; 
	var dlat = lat2 - lat1; 
	var a = Math.sin(dlat / 2) * Math.sin(dlat / 2) + Math.cos(lat1) * Math.cos(lat2) * Math.sin(dlon / 2) * Math.sin(dlon / 2); 
	var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a)); 
	var R = 6378.137; 
	return R * c;
}

function ComputeIntermediate(lat1, lon1, lat2, lon2, fraction, dist) {
	if(!dist)dist = topoComputeDistance(lat1, lon1, lat2, lon2); 
	var R = 6378.137; 
	lat1 = lat1 / 180 * Math.PI; 
	lon1 = lon1 / 180 * Math.PI; 
	lat2 = lat2 / 180 * Math.PI; 
	lon2 = lon2 / 180 * Math.PI; 
	dist = dist / R; 
	var A = Math.sin((1 - fraction) * dist) / Math.sin(dist); 
	var B = Math.sin(fraction * dist) / Math.sin(dist); 
	var x = A * Math.cos(lat1) * Math.cos(lon1) + B * Math.cos(lat2) * Math.cos(lon2); 
	var y = A * Math.cos(lat1) * Math.sin(lon1) + B * Math.cos(lat2) * Math.sin(lon2); 
	var z = A * Math.sin(lat1) + B * Math.sin(lat2); 
	var lat = Math.atan2(z, Math.sqrt(x * x + y * y)); 
	var lon = Math.atan2(y, x); 
	lat = lat * 180 / Math.PI; 
	lon = lon * 180 / Math.PI; 
	return new Array(lat, lon);
}

function FindIndexOfNearestSmaller(arr, value) {
	var left = 0; 
	var right = arr.length - 1; 
	while(left < right) {
		var mid = Math.floor((left + right) / 2.0); 
		if(arr[mid] > value)right = mid; 
		else left = mid + 1}
	return left - 1;
}

function ResampleCoordinates(coordinates, maxCoordinates) {
	var UrlMaxCoordinates = 280; 
	var uniqueCoordinates = new Array(); 
	var markerCoordinates = new Array();
	
	if(maxCoordinates) UrlMaxCoordinates = maxCoordinates;
	
	
	uniqueCoordinates[0] = coordinates[0]; // Filter out any duplicate coordinates
	for(var i = 1; i < coordinates.length; i++){
		if(coordinates[i].length >= 3){
			if((coordinates[i][2]) && coordinates[i][2] != "") {
				markerCoordinates.push([i,coordinates[i]]);
			}
		}
		
		if((coordinates[i][0] != coordinates[i - 1][0]) || (coordinates[i][1] != coordinates[i - 1][1])) {
			uniqueCoordinates[uniqueCoordinates.length] = coordinates[i]
		}
	}
	var distArray = new Array(); 
	distArray[0] = 0.0; 
	var cumulativeDistance = 0.0; 
	for(var i = 1; i < uniqueCoordinates.length; i++) {
		cumulativeDistance = cumulativeDistance + ComputeDistance(uniqueCoordinates[i - 1][0], uniqueCoordinates[i - 1][1], uniqueCoordinates[i][0], uniqueCoordinates[i][1]); 
		distArray[i] = cumulativeDistance;
	}
	
	var points = new Array(); 
	var curMarkerCoordinateIndex = 0; // The current marker point we're comparing to smallerIndex
	for(var i = 0; i < UrlMaxCoordinates; i++) {
		var lookDistance = i / (UrlMaxCoordinates - 1) * cumulativeDistance; 
		var smallerIndex = FindIndexOfNearestSmaller(distArray, lookDistance); 
				
		if(curMarkerCoordinateIndex < markerCoordinates.length){ // If we still have marker points left to insert
			while(markerCoordinates[curMarkerCoordinateIndex][0] <= smallerIndex){ // While there's still marker points before our smallerIndex point
				points.push(markerCoordinates[curMarkerCoordinateIndex][1]); // Insert the marker point
				curMarkerCoordinateIndex++;
			}
		}
		
		if(smallerIndex == (uniqueCoordinates.length - 1)) {
			points.push(uniqueCoordinates[smallerIndex])
		}else {
			var distLR = distArray[smallerIndex + 1] - distArray[smallerIndex]; 
			var fraction = (lookDistance - distArray[smallerIndex]) / distLR; 
			points.push(ComputeIntermediate(uniqueCoordinates[smallerIndex][0], uniqueCoordinates[smallerIndex][1], uniqueCoordinates[smallerIndex + 1][0], uniqueCoordinates[smallerIndex + 1][1], fraction, distLR))
		}
		
	}
	return points;
}