var zoom = 11;
var lat = 33.519787;
var lng = -86.812935;

var distances; // distances array from point x to point y = distances[x][y] in meters
var durations; // durations array from point x to point y = durations[x][y] in seconds
var pending; // number of the directions requests left. When 0, solving function should be dispatched
var BF_MAX_POINT = 8;
var MAX_POINT_LIMIT = 15;

var map; // google maps
var geocoder; // google maps geo coder
var icon; // default google maps icon
var directions; // google map directions object

/*******************
/* Status Messages 
/*****************/

var MAX_LIMIT = 0;
var BF_TOO_MANY_POINTS = 1;
var OPTION_DISABLED = 2;

var gmessages = new Array();
gmessages[G_GEO_BAD_REQUEST] = 'Bad Request.';
gmessages[G_GEO_SERVER_ERROR] = 'Server Error: Unknown Reason.';
gmessages[G_GEO_MISSING_ADDRESS] = 'Missing Address: No address in query.';
gmessages[G_GEO_UNKNOWN_ADDRESS] = 'Unknown Address: The address could be found and may be new or incorrect.';
gmessages[G_GEO_UNAVAILABLE_ADDRESS] = 'Unavailable Address: The address could not be returned due to legal or contractual reasons.';
gmessages[G_GEO_UNKNOWN_DIRECTIONS] = 'Unknown Directions: No route available between two points.';
gmessages[G_GEO_BAD_KEY] = 'Bad Key: The API key is invalid, or does not match the domain for which it was given.';
gmessages[G_GEO_TOO_MANY_QUERIES] = 'Too Many Queries. Please wait a few seconds and try again.';
gmessages[MAX_LIMIT] = 'Max number of points is ' + MAX_POINT_LIMIT + '.';
gmessages[BF_TOO_MANY_POINTS] = 'Max number of points for Brute Force is ' + BF_MAX_POINT + '.';
gmessages[OPTION_DISABLED] = 'This option is currently disabled.';

/****************************
 * Google Maps Functionality
 ***************************/

function initMap() {
  if (GBrowserIsCompatible()) {    
    map = new GMap2($('map'));
    geocoder = new GClientGeocoder();
    map.setCenter(new GLatLng(33.519787, -86.812935), 11);
    map.addControl(new GLargeMapControl());
    map.addControl(new GMapTypeControl());
  }
}

function getDirections() {
  directions = new GDirections();
  resetDirections();
  var p = wp.points.clone();
  p.push(wp.points.first());
  GEvent.addListener(directions, "load", function() {
    map.polyline = this.getPolyline();
    map.addOverlay(map.polyline);
    setMessage('Distance: ' + this.getDistance().meters + ' meters, duration: ' + this.getDuration().seconds + ' seconds for path.')
    printDirections(this);
  });
  directions.loadFromWaypoints(p, {getPolyline: true, getSteps: true});
}

var icons = {
  
  newIcon: function() {
    icon = new GIcon(G_DEFAULT_ICON);
    icon.iconSize = new GSize(32, 32);
    icon.shadow = 'http://maps.google.com/mapfiles/kml/paddle/A_maps.shadow.png';
    icon.shadowSize = new GSize(59, 32);
    icon.iconAnchor = new GPoint(14, 31);
    return icon;
  },

  create: function(n) {
    icon = this.newIcon();
    icon.image = n==1 ? './icons/blu1.png' : './icons/grn'+n+'.png';
    return icon;
  }
};

/*****************
 * Path Functions
 ****************/

function processPoints(callback) {
  if(wp.number() == 0) {
    alert('No points to process!');
    return;
  }  
  setupMatrices(wp.number());
  //wp.debug();

  var n = wp.number();
  distances[n-1][n-1] = 0; // the last location will never be reached with the following algorithm
  durations[n-1][n-1] = 0; // so set the x, y values for x = n and y = n to 0

  for(var i = 0; i < n-1; i++) {
    var points = [];
    for(var j = i; j < n; j++) {      
      if(i == j) {
        points.push(wp.points[i]);
        distances[i][j] = 0;
        durations[i][j] = 0;
      } else {
        points.push(wp.points[j]);
        points.push(wp.points[i]);
      }
    }
    directions = new GDirections();
    directions.from = i;
    pending = wp.number()-1;
    directions.handler = callback;
    GEvent.addListener(directions, "error", function() { setMessage(this.getStatus().code); });
    GEvent.addListener(directions, "load", setWeightValues);
    directions.loadFromWaypoints(points);
  }
}

// Initializes matricies to contain path information for the amount of points on the map
function setupMatrices(p) {
  distances = new Array();
  durations = new Array();
  for(var i = 0; i < p; i++) {
    distances.push([]);
    durations.push([]);
  }
}

// Sets the weight values for each matricies for every possible path on time and distance.
// Each path plots weights for a specific point, i.e. point 0 for the following example (given 4 points):
// 0 -> 1 -> 0 -> 2 -> 0 -> 3 -> 0
// Next path would plot all points from 1, excluding any points previously plotted:
// 1 -> 2 -> 1 -> 3 -> 1
// And so on until all points have their respective weight values populated.
function setWeightValues() {
  pending--;
  //var d = function(x,y,r){console.debug('['+x+'->'+y+']: '+getDistance(r)+'m & '+getTime(r)+'s.');};  
  var r = 0; // the route number in the path, i.e. 0->1 would be the first route (0)
  for(var i = this.from+1; r < this.getNumRoutes(); i++) {
    // get fromPoint->nextPoint(i)
    var route = this.getRoute(r++);
    //d(this.from, i, route);
    distances[this.from][i] = getDistance(route);
    durations[this.from][i] = getTime(route);
    // get nextPoint(i)->fromPoint
    route = this.getRoute(r++);
    //d(i, this.from, route);
    distances[i][this.from] = getDistance(route);
    durations[i][this.from] = getTime(route);
  }
  if(this.handler && pending == 0) this.handler();
}

function getDistance(r) {
  return r.getDistance().meters;
}

function getTime(r) {
  return r.getDuration().seconds;
}

// Takes a path, i.e. [0, 1, 2, 3], appends the first point to the end, and returns the
// total distance traveled for the given path.
function getPathDistance(p) {
  var d = 0; // total distance
  for(var i = 0; i < p.length; i++) {
    d += i == p.length-1 ? distances[p[i]][p.first()] : distances[p[i]][p[i+1]];
  }
  return d;
}

// Takes a path, i.e. [0, 1, 2, 3], appends the first point to the end, and returns the
// total time traveled for the given path.
function getPathTime(p) {
  var t = 0; // total time
  for(var i = 0; i < p.length; i++) {
    t += i == p.length-1 ? durations[p[i]][p.first()] : durations[p[i]][p[i+1]];
  }
  return t;
}

/**********************************
 * Brute Force Algorithm O((n-1)!)
 *********************************/
function bruteForce(start, op, time, best) {
  if(op.length == BF_MAX_POINT) {
    setMessage(BF_TOO_MANY_POINTS);
    return;
  }
  var weights = time && time == true ? getPathTime : getPathDistance;
  if(op.length == 1) {
    var path = start.concat(op.pop());
    if(!best) {
      best = path;
    } else {
      if(weights(path) < weights(best)) best = path;
    }
    return best;
  } else {  
    for(var i = 0; i < op.length; i++) {
      best = bruteForce(start.concat(op[i]), op.without(op[i]), time, best);
    }
    return best;
  }
}

/***************************************
 * Nearest Neighbor Algorithm O(log(n))
 **************************************/
function nearestNeighbor(start, op, time) {
  var weights = time && time == true ? durations : distances;
  var len = op.length;
  for(var i = 0; i < len; i++) {
    var shortest = -1;
    for(var j = 0; j < op.length; j++) {
      if(shortest < 0) {
        shortest = op[j];
      } else {
        if(weights[start[i]][op[j]] < weights[start[i]][shortest]) shortest = op[j]; 
      }      
    }
    op = op.without(shortest);
    start.push(shortest);
  }
  return start;
}

/******************
 * Point Functions
 *****************/

var wp = {
  
  addresses: [],
  points: [],
  markers: [],
  stack: [],
  
  addWaypoint: function(address, point, marker) {
    this.addresses.push(address);
    this.points.push(point);
    this.markers.push(marker);
    this.stack.push(this.stack.length);
  },
  
  getWaypoint: function(i) { 
    return { address: addresses[i], point: points[i], marker: markers[i] };
  },
  
  removeWaypoint: function(i) {
    this.addresses.splice(i, 1);
    this.points.splice(i, 1);
    this.markers.splice(i, 1);
    this.stack.pop();
  },
  
  clear: function() {
    this.addresses = [];
    this.points = [];
    this.markers = [];
    this.stack = [];
  },
  
  number: function() { return this.points.length; },
  
  reorder: function(r) {
    var a_tmp = [];
    var p_tmp = [];
    var m_tmp = [];
    for(var i = 0; i < this.number(); i++) {
      a_tmp[i] = this.addresses[r[i]];
      p_tmp[i] = this.points[r[i]];
      this.markers[i].setPoint(this.points[r[i]]);
    }
    this.addresses = a_tmp;
    this.points = p_tmp;
    updateWaypoints(); // updates any waypoints referenced on page after change
  },
  
  shift: function(p, n) {
    if(p==n) return;
    var o = this.stack.clone();
    o[p] = this.stack[n];
    o[n] = this.stack[p];
    this.reorder(o);
    resetDirections(); // resets any directions previously generated after change
  },
  
  debug: function() {
    for(var i = 0; i < this.number(); i++) {
      console.debug('[' + i + ']: ' + this.addresses[i] + ': ' + this.points[i]); 
    }    
  }
};

/************
 * Messaging
 ***********/

function setMessage(msg) {
  $('messages').innerHTML = typeof msg == 'number' ? gmessages[msg] : msg;
}

function clearMessage() {
  $('messages').innerHTML = '';
}

/*******************
 * Run Forest, Run!
 ******************/

function letsgo() {
  var solver = $('solver').value;
  switch(solver) {
    case 'nn':
      solver = nearestNeighbor;
      break;
    case 'bf':
      solver = bruteForce;
      break;
    case '':
      return;
  }
  var weights = $('solve4dist').checked ? false : true;
  var order = solver([0], wp.stack.without(0), weights);
  wp.reorder(order);
  getDirections();
}

/*************
 * Directions
 ************/

// Converts meters to feet or miles, depending on the distance
// greater than ~500 feet = miles, otherwise return feet
function convertMeters(m) {
  var mpm = 0.000621; // miles per meter
  if(m < 160) {
    return (m * 3.28).toFixed(0) + ' ft';
  } else {
    var mi = (m * mpm);
    if(m > 80467) { // ~50 miles
      return mi.toFixed(0) + ' mi';
    } else {
      return (mi % 1) == 0 ? mi.toFixed(0) + ' mi' : mi.toFixed(1) + ' mi';
    }
  }
  return m < 160 ? (m * 3.28).toFixed(0) + ' ft' : (m * 0.000621).toFixed(1) + ' mi';
}

function printDirections(directions) {
  var r = $('results');
  r.innerHTML = '';
  var h = '';
  var count = 1;
  h += '<table><thead><tr><th>Directions</th></tr></thead><tbody>';
  for(var i = 0; i < directions.getNumRoutes(); i++) {
    var route = directions.getRoute(i);
    var img = i == 0 ? './icons/blu-cir1.png' : './icons/grn-cir' + (i+1) + '.png';
    h += '<tr><th><span>' + route.getSummaryHtml() + '</span><img src="' + img + '" alt="' + (i+1) + '"/>' + wp.addresses[i] + ' ' + wp.points[i] + '</th></tr>';    
    for(var j = 0; j < route.getNumSteps(); j++) {
      var step = route.getStep(j);
      h += '<tr><td><span>' + convertMeters(step.getDistance().meters) + '</span>' + (count++) + '. ' + step.getDescriptionHtml() + '</td></tr>';
    }
  }
  h += '<tr><th><img src="./icons/blu-cir1.png" alt="1"/><span>Total Trip: ' + directions.getSummaryHtml() + '</span>' + wp.addresses[0] + ' ' + wp.points[0] + '</th></tr>';
  h += '</tbody></table>';
  r.innerHTML = h;
}

function resetDirections() {
  if(map.polyline) map.removeOverlay(map.polyline);
  $('results').innerHTML = '<table><thead><tr><th>Directions</th></tr></thead><tbody><tr><th>No directions available.</th></tr></tbody></table>';
}

/*************************
 * Build waypoints in DOM
 ************************/

// Calls the geocoder and returns a point for the given address
function addWaypoint(a) {
  if(wp.number() == MAX_POINT_LIMIT) {
    setMessage(MAX_LIMIT);
    return;
  }
  geocoder.getLatLng(a, function(p) { 
    if(p == null) {
      setMessage('The address ' + $F('address') + ' could not be located.');
    } else {
      resetDirections();
      var m = new GMarker(p, wp.number() == 0 ? icons.create(wp.number() + 1) : icons.create(wp.number() + 1));
      wp.addWaypoint(a, p, m);
      map.addOverlay(m);
      map.panTo(p);
      updateWaypoints();
    }
  });
}

function removeWaypoint(p) {
  resetDirections();
  wp.removeWaypoint(p);
  map.clearOverlays();
  for(var i = 0; i < wp.number(); i++) {
    var m = new GMarker(wp.points[i], i == 0 ? icons.create(i+1) : icons.create(i+1));
    map.addOverlay(m);
    wp.markers[i] = m;
  }
  updateWaypoints();
}

function updateWaypoints() {
  var a = $('points');
  a.innerHTML = '';
  if (wp.number() == 0) {
    resetPoints();
  } else {
    var h = '<ul>';
    h += '<a class="button" href="javascript:processPoints(letsgo);">Process</a>';
    h += '<a class="button" href="javascript:clearWaypoints();">Clear Points</a>';
    for(var i = 0; i < wp.number(); i++) {
      var pan = 'map.panTo(wp.points[' + i + ']);';
      var remove = 'removeWaypoint(' + i + ');';
      var start = 'wp.shift(' + i + ', 0)';
      h += ((i+1) % 2 == 0) ? '<li' : '<li class="odd"';
      h += ' title="' + wp.points[i] + '"><strong>' + (i+1) + '</strong>';
      h += '<a title="Remove" alt="Remove" href="javascript:' + remove + '">X</a>';
      h += '<a title="Pan To" alt="Pan To" href="javascript:' + pan + '">&raquo;</a>';
      h += i!=0 ? '<a title="Move Up" alt="Make Start" href="javascript:' + start + '">+</a>' : '<span>&nbsp;</span>';
      h += '<p>' + wp.addresses[i] + '</p></li>';
    }
    h += '</ul>';
    a.innerHTML = h;
  }   
}

function clearWaypoints() {
  map.clearOverlays();
  wp.clear();
  resetPoints();
  resetDirections();
}

function resetPoints() {
  $('points').innerHTML = '<em>No addresses available.</em>';
}

function toggleDsc(v) {
  var p = $('algorithms').select('p');
  for(var i = 0; i < p.length; i++) {
    p[i].id == v ? p[i].show() : p[i].hide();
  }
}

function toggleOps(str) {
  var a = $('algorithms');
  var s = $('selections');
  var l = $('options').select('ul')[0].immediateDescendants();
  switch (str) {
    case 'alg':
      a.show();
      s.hide();
      l[1].removeClassName('selected');
      l[0].addClassName('selected');
    break;
    case 'sel':
      a.hide();
      s.show();
      l[0].removeClassName('selected');
      l[1].addClassName('selected');
    break;
  }
}