/*
 * This is a set of methods used to generate the most optimal route.
 * It is broken into 2 primary parts; the first is generating a
 * matrix of distances between all the points; the second is the
 * actual route generation.
 *
 * In considering the traveling salesman problem, we have to keep in
 * mind that the distance from A to B may not be the same as the
 * distance from B to A; the routes between the points may not be
 * symmetric due to roads that are one-way, for example. So we can
 * track the distances between N points as an N x N matrix which
 * is NOT symmetrical (but does have zeros down the diagonal).
 * 
 * We use this matrix, googleDistanceArray, such that:
 * 
 *    googleDistanceArray[A][B]
 *
 * is the distance starting at point (index) A and traveling to
 * point (index) B.  We make calls to Google to build up the array
 * of distances; we then take that distance array, and produce an
 * optimal route, passing through each point once.
 */

var googleDistanceArray = [];
var googleTimeArray = [];
var googleStartIndex = 0;
var googlePoints = [];

var googleBranchCutoverSize = 2;

var googleFullRouteOptLimit = 9;
var googleBranchCutMinimizingLimit = 13;

var maxTripDuration = 2000000000; // Approx. 63 years., this long a route should not be reached...

var numIncrements = 0;
/*
 *
 */
function DistanceByGoogle(addList,destinationAddress,isSort,callback) {

  this.googleRouteDestination = destinationAddress;
  this.addressList = addList;
	var refpoint = null;
  var googleDone = false;
  var theCallback = callback;

	this.GetOptimizedAddress = function() {
     if( this.addressList.length < 2 ) 
     { 
    	 theCallback( this.addressList );
    	 return;
     }
     
     Log("Using new optimization method.");
     Log("addList length = " + addList.length );

     if( addList.length < googleFullRouteOptLimit ) { googleBranchCutoverSize = addList.length; }
     else if( addList.length < googleBranchCutMinimizingLimit ) { googleBranchCutoverSize = 3; }
     else { googleBranchCutoverSize = 2; }

     Log("Using googleBranchCutoverSize = " + googleBranchCutoverSize);
     googleStartIndex = 0;
     googleDistanceArray = [];
     googleTimeArray = [];

     googleAddList = [];
     for( var i = 0; i < this.addressList.length; i++ )
     {
    	 if( this.addressList[i] !== null )
    	 {
    		 googleAddList.push( this.addressList[i] );
    	 }
     }
     
     //googleAddList = this.addressList;
     if( this.googleRouteDestination === null )
     {
    	 googleAddList.push( googleAddList[0] );
     }
     else
     {
    	 googleAddList.push( this.googleRouteDestination );
     }

     // Build an n x n matrix for distances, and initialize all entries to zero
     // make it (n+1)x(n+1) to account for end point.
     for( var i = 0; i <= googleAddList.length; i++ )
     {
        googleDistanceArray[i] = [];
        googleTimeArray[i] = [];
        for( var j = 0; j <= googleAddList.length; j++ )
        {
           googleDistanceArray[i][j] = 0.0;
           googleTimeArray[i][j] = 0.0;
        }
     }
     
     numIncrements = googleAddList.length * googleAddList.length;

     // Start at x = 1, y = 0;
     googleIndexX = 1;
     googleIndexY = 0;
 
     mylist = getSetOfPointsForGoogle();

     googleDirectionObj = new GDirections(null, null );
     GEvent.addListener(googleDirectionObj, "load", this.myGoogleSortedDirections );
     GEvent.addListener(googleDirectionObj, "error", this.myGoogleErrorGenerated );
     googleDirectionObj.loadFromWaypoints( mylist );

     return; //  this.addressList;
	};

	this.myGoogleErrorGenerated = function() {
		var error = googleDirectionObj.getStatus();
		var googleStatus = "";
		if( error.code == G_GEO_SUCCESS ) { googleStatus = "No error."; }
		else if( error.code == G_GEO_BAD_REQUEST ) { googleStatus = "Bad request (too may waypoints?)."; }
		else if( error.code == G_GEO_SERVER_ERROR ) { googleStatus = "Server error (exact cause unknown)."; }
		else if( error.code == G_GEO_MISSING_QUERY ) { googleStatus = "Incomplete query format."; }
		else if( error.code == G_GEO_MISSING_ADDRESS) { googleStatus = "Incomplete query format."; }
		else if( error.code == G_GEO_UNKNOWN_ADDRESS) { googleStatus = "An address could not be geocoded."; }
		else if( error.code == G_GEO_UNAVAILABLE_ADDRESS ) { googleStatus = "Either address could not be geocoded, or legal reasons block generation of a route."; }
		else if( error.code == G_GEO_UNKNOWN_DIRECTIONS ) { googleStatus = "No route could be found between at least 2 of the points."; }
		else if( error.code == G_GEO_BAD_KEY) { googleStatus = "Google maps key is invalid."; }
		else if( error.code == G_GEO_TOO_MANY_QUERIES) { googleStatus = "Too many requests have been made with this Google key; try again later."; }
		
		alert("We're sorry but the route could not be generated.\n" + googleStatus );
	};
	
	// Increment indices, being careful that we keep to the limits.
	// Set the y index to -1 to indicate that we are done.
	// Interestingly, this must be a global function
	function googleIncrementIndices() 
	{
	  googleIndexX = googleIndexX + 1;
	  if( googleIndexX > googleAddList.size() - 1 )
	  {
	    //Log("Reached end of x (" + googleIndexX + ") so reset x,y");
	    googleStartIndex = googleStartIndex + 1;
	    googleIndexX = googleStartIndex+1;
	    googleIndexY = googleStartIndex;
	    //Log("New x,y = " + googleIndexX + ", " + googleIndexY);
	  }

	  if( googleIndexX > googleAddList.size() - 1 )
	  {
	    googleIndexY = -1;  // exit out
	  }
	  else if( googleIndexX == googleIndexY && googleIndexX < googleAddList.size()-1 )
	  {
	    googleIncrementIndices();
	  }

	  if( googleIndexX == googleAddList.size()-1 && googleIndexY == googleAddList.size()-1 )
	  {
	    googleIndexY = -1;
	  }
	}


getSetOfPointsForGoogle = function() {
     // we will return an array of the indices we are calculating
     // This loop builds up a set of points from A to B and back to A.
     // Google only allows us to send 25 points, so ... given 3 per point,
     // the loop goes to 8 each time. We may have to abord early if the index
     // increment sends us past the end of our data.
     //
     // Note we store the data in googlePoints for retrieval by the global method.

     googlePoints = [];
     mylist = [];

     // This is better, but slightly inefficent, as we're going a -> b -> a -> a -> c -> a ...
     // Still, we're making 1/7 the calls to Google that we were, so getting distances
     // is much faster.
     var currentY = googleIndexY;
     var returnPoint = null;

     //for( var index = 0; index < 11; index++ )

     var MAXPOINTSINGOOGLE = 22;   // max 3 added, this would be 25.
     
     numIncrements = numIncrements / MAXPOINTSINGOOGLE;
     
     var currentIncrement = 0;
     while( googlePoints.length < MAXPOINTSINGOOGLE )
     {
        mylist.push( googleAddList[googleIndexY].GetLatLng() );  // A
        mylist.push( googleAddList[googleIndexX].GetLatLng() );  // -> B
        returnPoint = googleAddList[googleIndexY].GetLatLng();   // -> A (if needed)

        googlePoints.push( [googleIndexY, googleIndexX] ); // index stored of B
        googlePoints.push( [googleIndexX, googleIndexY] ); // index stored of B

        googleIncrementIndices();

        if( googleIndexY != currentY || googlePoints.length >= MAXPOINTSINGOOGLE-1)
        {
           mylist.push( returnPoint );
           googlePoints.push( [-1, -1] );  // a skip index
           currentY = googleIndexY;
        }

        currentIncrement += 1;
        
//        jQuery("#progressbar").progressbar("progress", 100.0 * (currentIncrement/numIncrements) );
        
        // If googleIndexY is negative, that's our signal that we're done.
        if( googleIndexY < 0 ) 
        { 
          break; 
        }

     }

     return mylist;
  };


  function googleSortPoints( pointsToVisit, currentIndex ) 
  {
        var distances = [];
        for( var i = 0; i < pointsToVisit.length; i++ )
        {
           distances[i] = googleDistanceArray[currentIndex][pointsToVisit[i]];
        }

        // now sort.
        var newOrder = [];

        var numPoints = pointsToVisit.length;
        for( var i = 0; i < numPoints; i++ )
        {
           var curDist = 9999999999999;
           var minIndex = -1;
           for( var j = 0; j < pointsToVisit.length; j++ )
           {
             if( distances[j] < curDist )
             {
               curDist = distances[j];
               minIndex = j;
             }
           }

          // Build the new order
          newOrder.push( pointsToVisit[minIndex] );

          // Remove that minimum point
          pointsToVisit.splice( minIndex, 1 );     
          distances.splice( minIndex, 1 );     
        }

        return newOrder;
  }

  function goDownBranch( visitedPoints, pointsToVisit, currentIndex, parentPoint, prevDistance, endOfPath )
  {
     googleOptimizationCalls++;

     // The first thing we want to do is reorder the "pointsToVisit" in order of distance
     // from us
     //Log("before = " + pointsToVisit);
  //   if( pointsToVisit != null )
  //   {
//        pointsToVisit = googleSortPoints( pointsToVisit, currentIndex );
  //   }

     //   Log("Parent point = " + parentPoint );
     //   Log("Current point = " + currentIndex);
     //   Log("Current path = " + visitedPoints );
     //   Log("Current distance = " + prevDistance );

     // Build a new visitedPoints array (really just adding in our current point.
     visitedPoints.push( currentIndex );

     //Log("New path = " + visitedPoints );

     var fullPathDistance = 0.0;
     var newDistance = 0.0;

     if( parentPoint !== null )
     {
        newDistance = prevDistance + googleDistanceArray[parentPoint][currentIndex];
     }

     //   Log("New distance = " + newDistance );
     // Here's where we can cull points (i.e., Branch and CUT) .... :)
     if( newDistance > currentFullMinimumDistance )
     {
       googleCutOptimizationCalls++;
       return newDistance;
     }

     // How to tell if we're on the last point .... the "pointsToVisit" is null or empty.
     
     if( pointsToVisit === null || pointsToVisit.length === 0 )
     {
        // and at the end of a path, endOfPath is true (endOfPath meaning we visited end point).
        if( endOfPath === false )
        {
      	  // set current index to zero to calculate back to the start.
            //var fullPathDistance = goDownBranch( visitedPoints, null, 0, currentIndex, newDistance, true );
            fullPathDistance = goDownBranch( visitedPoints, null, googleAddList.length - 1, currentIndex, newDistance, true );
           
           //Log( "2: Back from call, fullPath = " + fullPath );
           //Log( "2:      and fullPathDistance = " + fullPathDistance );
           if( fullPathDistance < currentFullMinimumDistance )
           { 
              currentFullMinimumDistance = fullPathDistance;
              currentFullMinimumPath = visitedPoints.slice();
           }
           visitedPoints.pop(); // remove last visited

           return fullPathDistance;
        }
        else
        {
          // done
          return newDistance;
        }
     }

     // In this, the visited points contains all points already touched.
     // currentIndex is the point we are currently on.
     // pointsToVisit is the set of points we have yet to go down.

     // We want to go down each one in the "pointsToVisit" array.

     var numPointsToVisit = pointsToVisit.length;
     if( numPointsToVisit > googleBranchCutoverSize ) 
     { 
        if( pointsToVisit !== null )
        {
           pointsToVisit = googleSortPoints( pointsToVisit, currentIndex );
        }
        numPointsToVisit = googleBranchCutoverSize; 
        Log("altered Number of points to visit = " + numPointsToVisit + " while pointsToV.l = " + pointsToVisit.length );
     } 

     for( var i = 0; i < numPointsToVisit; i++ )
     {
         var newPointsToVisit = pointsToVisit.slice();
         newPointsToVisit.splice( i, 1 ); // remove the current index
         fullPathDistance = goDownBranch( visitedPoints, newPointsToVisit, pointsToVisit[i], currentIndex, newDistance, false );
         visitedPoints.pop(); // remove last visited
     }

     return fullPathDistance;
  }

  function googleOptimizeRoute( theCallback )
  {
     // We force starting position 0 to be stable (always our starting position)

     // We want to go from point 0, through points (1 ... addList.length - 1) and back to 0.
     // So the permutations we want to walk are over 1 .. addList.length-1.
     // Create an array of what points are left to visit, and which have been visited.
    
     var visitedPoints = []; // leave empty ... haven't been anywhere! 
     var pointsToVisit = [];
     for( var i = 0; i < googleAddList.length-2; i++ ) // skipping the first points, leaving out destination
     {
        pointsToVisit[i] = i+1; // loading index of point in array
     }

     // 2 globals to track our current state
     currentFullMinimumPath = [];
     currentFullMinimumDistance = 9999999999;
     googleOptimizationCalls = 0;
     googleCutOptimizationCalls = 0;

     var retValue = goDownBranch( visitedPoints, pointsToVisit, 0, null, false );
     visitedPoints.pop(); // remove last visited
     var fullPath = visitedPoints;
     var distance = retValue;

     //Log("Minimum path at end = " + currentFullMinimumPath );
     //Log("Minimum distance at end  = " + currentFullMinimumDistance );

     tempAddList = [];
     Log("fullPath = " + currentFullMinimumPath);
     for( i = 0; i < currentFullMinimumPath.length-1; i++ ) // skip end point
     {
       // Setting new add list
       tempAddList.push(googleAddList[ currentFullMinimumPath[i] ]);
       //Log("route point " + googleAddList[minimumRoute[i]].GetActualAddress() );
     }

     Log("Number of calls to goDownBranch = " + googleOptimizationCalls);
     Log("Number of calls cut short in goDownBranch = " + googleCutOptimizationCalls);
     googleAddList = tempAddList;
     theCallback( googleAddList );
  }

  /* Computes a near-optimal solution to the TSP problem, 
   * using Ant Colony Optimization and local optimization
   * in the form of k2-opting each candidate route.
   * Run time is O(numWaves * numAnts * numActive ^ 2) for ACO
   * and O(numWaves * numAnts * numActive ^ 3) for rewiring?
   */
  function tspAntColonyK2() {
    var alfa = 1.0; // The importance of the previous trails
    var beta = 2.0; // The importance of the durations
    var rho = 0.1;  // The decay rate of the pheromone trails
    var asymptoteFactor = 0.9; // The sharpness of the reward as the solutions approach the best solution

    var pher = [];
    var nextPher = [];
    var prob = [];
    var numAnts = numActive;   // was set to 10 always
    var numWaves = numActive;  // was set to 10 always

    for (var i = 0; i < numActive; ++i) {
      pher[i] = [];
      nextPher[i] = [];
    }
    for (var i = 0; i < numActive; ++i) {
      for (var j = 0; j < numActive; ++j) {
        pher[i][j] = 1;
        nextPher[i][j] = 0.0;
      }
    }

    for (var wave = 0; wave < numWaves; ++wave) {
      for (var ant = 0; ant < numAnts; ++ant) {
        // var startNode = Math.floor(Math.random() * numActive);
        var startNode = 0;
        var endNode = numActive-1;
        
        var curr = startNode;
        var currDist = 0;
        for (var i = 0; i < numActive; ++i) {
  	       visited[i] = false;
        }
        currPath[0] = curr;
        for (var step = 0; step < numActive-2; ++step) {
         	visited[curr] = true;
         	var cumProb = 0.0;
         	for (var next = 0; next < numActive-1; ++next) {
         	  if (!visited[next]) {
         	    prob[next] = Math.pow(pher[curr][next], alfa) * Math.pow(dur[curr][next], 0.0-beta);
         	    cumProb += prob[next];
            }
  	    }

          var guess = Math.random() * cumProb;
          var nextI = -1;
          for (var next = 0; next < numActive-1; ++next) {
            if (!visited[next]) {
              nextI = next;
              guess -= prob[next];
              if (guess < 0) {
                nextI = next;
                break;
              }
            }
          }

          currDist += dur[curr][nextI];
          currPath[step+1] = nextI;
          curr = nextI;
        }
        
        // JWW --- I think this is the point where we tie back to the "end" (i.e., start) node.
        currPath[numActive-1] = endNode; // the end node // startNode;
        currDist += dur[curr][endNode];
        //currDist += dur[curr][startNode];
        
        // k2-rewire:
        // cerr << "Before rewire, soln with duration = " << currDist << endl;
        var changed = true;
        while (changed) {
          changed = false;
          for (var i = 0; i < numActive-3 && !changed; ++i) {
            var cost = dur[currPath[i+1]][currPath[i+2]];
            var revCost = dur[currPath[i+2]][currPath[i+1]];
            for (var j = i+2; j < numActive-1 && !changed; ++j) {
              if (cost + dur[currPath[i]][currPath[i+1]] +
                  dur[currPath[j]][currPath[j+1]] > revCost + 
                  dur[currPath[i]][currPath[j]] + 
                  dur[currPath[i+1]][currPath[j+1]]) {
                   currDist += revCost + dur[currPath[i]][currPath[j]] + 
                              dur[currPath[i+1]][currPath[j+1]] - cost -
                              dur[currPath[i]][currPath[i+1]]  -
                              dur[currPath[j]][currPath[j+1]];
                   var tmp;
                   for (var k = 0; k < Math.floor((j-i)/2); ++k) {
                     tmp = currPath[i+1+k];
                     currPath[i+1+k] = currPath[j-k];
                     currPath[j-k] = tmp;
                   }
                   changed = true;
              }
              cost += dur[currPath[j]][currPath[j+1]];
              revCost += dur[currPath[j+1]][currPath[j]];
            }
          }
        }
        if (currDist < bestTrip) {
          bestPath = currPath;
          bestTrip = currDist;
        }
        for (var i = 0; i < numActive; ++i) {
          nextPher[currPath[i]][currPath[i+1]] += (bestTrip - asymptoteFactor * bestTrip) / (numAnts * (currDist-asymptoteFactor*bestTrip));
        }
      }
      for (var i = 0; i < numActive; ++i) {
        for (var j = 0; j < numActive; ++j) {
          pher[i][j] = pher[i][j] * (1.0 - rho) + rho * nextPher[i][j];
          nextPher[i][j] = 0.0;
        }
      }
    }
  }

  function readyTsp() {

	  // Get distances and durations into 2-d arrays:
	  distIndex = 0;
	  dist = googleDistanceArray;
	//  dur = googleTimeArray;
	  dur = googleDistanceArray;
	  
	  numActive = 0;
	  waypoints = googleAddList;
	  for (var i = 0; i < waypoints.length; ++i) {
	      dist.push([]);
	      dur.push([]);
	      numActive++;
	  }

	  // Calculate shortest roundtrip:
	  visited = [];
	  for (var i = 0; i < numActive; ++i) {
	    visited[i] = false;
	  }
	  currPath = [];
	  bestPath = [];
	  bestTrip = maxTripDuration;
	  visited[0] = true;
	  currPath[0] = 0;

	  tspAntColonyK2();

	  var newAddressList = [];
	  
	  for(var i = 0; i < bestPath.length - 1; i++ )
	  {
	     newAddressList.push( googleAddList[ bestPath[i] ] );
	  }
	  return newAddressList;
	}

  function antColonyOptimizeRoute( theCallback )
  {
     var antOptimizedAddresses = readyTsp();
     theCallback( antOptimizedAddresses );
  }

/*
 * This is the callback that we specify the google GDirections object call when results
 * are ready for parsing. It parses the incoming set of directions, and then sets up a
 * call to get the next set.
 */
  this.myGoogleSortedDirections = function() {

    // Are there routes present?
    //Log("Number of routes = " + googleDirectionObj.getNumRoutes() );
    //Log("Google points = " + googlePoints.size() );

    //Log( googlePoints );
    if( parseInt(googleDirectionObj.getNumRoutes(), 10) > 0 )
    {
      for( var i = 0; i < googleDirectionObj.getNumRoutes(); i++ )
      {
        // Do this if it's not a transition boundary
        if( !(googlePoints[i][0] == -1 && googlePoints[i][1] == -1) )
        {
           route = googleDirectionObj.getRoute( i );
           googleDistanceArray[googlePoints[i][0]][googlePoints[i][1]] = parseFloat(route.getDistance().meters);
           googleTimeArray[googlePoints[i][0]][googlePoints[i][1]] = parseFloat(route.getDuration().seconds);
        }
      }

      // If googleIndexY is negative, that's our signal that we're done.
      if( googleIndexY >= 0 )
      {
         mylist = getSetOfPointsForGoogle();
         // We use setTimeout because if we spam google too fast, we'll get locked out.
	     setTimeout( function(){ googleDirectionObj.loadFromWaypoints( mylist ); }, 150);
      }
      else
      {
        if( addList.length <= googleFullRouteOptLimit )
        {
          googleOptimizeRoute( theCallback );
        }
        else
        {
//          alert("With " + addList.length + " locations, there are more than " + commaFormatted(factorial(addList.length)) + " possible routes. We will find a near-optimal route.");
          antColonyOptimizeRoute( theCallback );
        }
      }
    }
  };
}


function factorial(n)
{
   if(n === 1 || n === 0) //your base case
   {
     return 1;
   }

   return n * factorial(n - 1);
}

function commaFormatted(amount)
{
  var str = '';
  while( amount > 0 )
  {
    var part = amount - 1000 * Math.floor(amount / 1000, 10);

    if( amount > 999 )
    {
      if( part < 10 ) { part = "00" + part; }
      else if( part < 100 ) { part = "0" + part; }
      else { part = "" + part; }
    }

    if( str === '' )
    {
      str = part + '';
    }
    else
    {
      str = part + ',' + str;
    }

    amount = Math.floor( (amount - part)/1000, 10 );
  }
  return str;
}