function CwayPoint(p, c, i) {  // extends GLatLang
    this.constructor(p.lat(), p.lng());
    this.charge = c;
    this.jobID = i;
//    this.toString = function(){ return "a Bikepoint" };
}

CwayPoint.prototype = new GLatLng();


var currJobID = 0;
function Cjob(s,e)
{
    currJobID++;
    this.start= new CwayPoint(s,1, currJobID);
    this.end = new CwayPoint(e,-1, currJobID);
    this.car = 0;
    this.getArray = function()
                    {
                        return new Array(this.start,this.end);
                    };

    this.distance = s.distanceFrom(e);
    this.routed = 0;
    this.getStation = function()
                      {
                          if (this.routed==0) return this.start;
                          return this.end;
                      };
    this.popStation = function(c)
                      {
                          this.car = c;
                          var r=this.getStation();
                          this.routed++;
                          return r;
                      };
}

Cjob.prototype = new Array();


function Cedge(p1, p2) {
    this.selected = 0;
    this.distance = p1.distanceFrom(p2);
}




//<![CDATA[


var completeRoute = new Array();


var jobs   = new Array();
var cars   = new Array();

var allLine  = new Array();
var routeOverlays = new Array();
var map;
var totalDistance = 0.0;
var lineIx = 0;

var baseIcon = new GIcon();
baseIcon.iconSize=new GSize(16,16);
baseIcon.iconAnchor=new GPoint(8,8);
baseIcon.infoWindowAnchor=new GPoint(10,0);

var carIcon = (new GIcon(baseIcon, "/images/lkw.png", null, ""));
var greenIcon = (new GIcon(baseIcon, "/images/greenCircle.png", null, ""));
var redIcon = (new GIcon(baseIcon, "/images/redCircle.png", null, ""));
//var orangeIcon = (new GIcon(baseIcon, "/images/orangeCircle.png", null, ""));
//var blueIcon = (new GIcon(baseIcon, "/images/blueCircle.png", null, ""));
//var violetIcon = (new GIcon(baseIcon, "/images/violetCircle.png", null, ""));

//]]>

function logClear() {
    document.getElementById("logging").innerHTML = "";
}
function logger(x) {
    document.getElementById("logging").innerHTML = document.getElementById("logging").innerHTML + '<br>'+ x;
}

function load() {
  logger('Lade Google Maps');
  if (GBrowserIsCompatible()) {
  
	var centerPoint = new GLatLng(48.72822792893935,  13.381519317626953);

	map = new GMap2(document.getElementById("map"),{draggableCursor:"crosshair"});
	map.setCenter(centerPoint, 6);
	getMapcenter();

	map.addControl(new GMapTypeControl());
	map.addControl(new GScaleControl());
	map.addControl(new GLargeMapControl());


	map.enableContinuousZoom();
	// Listener für Klick handling usw.
	//GEvent.addListener(map, "moveend", getMapcenter);
	GEvent.addListener(map, "click", mapClick);
  
  }
  logger('init done');
  
  loadPoints();
}

// === click handlers 
function getMapcenter() {
	logger('handler:getMapcenter');

}

function mapClick(marker, point) {
    if (!marker) {
	addRoutePoint(point)
    }
}


// andere functions

var lastPoint = null;

// Route-Point hinzufügen. zwei aufeinander folgende bilden einen Job
function addJob(latLngFrom, latLngTo) {
    jobs.push(new Cjob(latLngFrom, latLngTo));
}

function addRoutePoint(point) {
    if (lastPoint) {
	jobs.push(new Cjob(lastPoint, point)); // neuen job anlegen
	lastPoint = null;
    } else {
	lastPoint = point
    }
}


function addCarPoint(point) {
    cars.push(new CwayPoint(point,0,0) );
    var car = new GMarker(point,{icon:carIcon,title:'Hans'});
    map.addOverlay(car);
    
}

function plotJobs(bComplete) {

	var i = jobs.length - 1
	if (bComplete) {
	    map.clearOverlays;
	    i = 0;
	}
	for (; i < jobs.length; i++) {
	    markerStart = new GMarker(jobs[i].start,{icon:greenIcon,title:'Start:'+i});
	    markerEnd = new GMarker(jobs[i].end,{icon:redIcon,title:'Ziel:'+i});
	    line = new GPolyline(jobs[i].getArray(),'#C602C8',1,1);
	    map.addOverlay(line);
	    /*map.addOverlay(line);*/
	    map.addOverlay(markerStart);
	    map.addOverlay(markerEnd);
	}
}

function drawCompleteRoute ()
{
    // clear lines
    for (i = 0; i < allLine.length; i++)
    {
        if (allLine[i])
            map.removeOverlay (allLine[i]);
    }
    allLine = Array ();

    // make new lines
    for (var car = 0; car < cars.length; car++)
    {
	bikes = 0;
        for (i = 0; i < completeRoute[car].length - 1; i++)
        {
            bikes += completeRoute[car][i].charge;
            shortLine = Array ();
            shortLine.push (completeRoute[car][i]);
            shortLine.push (completeRoute[car][i + 1]);

            if (bikes > 0)
            {
		var color = '#000080';
		switch (car) {
		    case 0:
			color = '#008080';
			break;
		    case 1:
			color = '#800000';
			break;
		
		}
                allLine[i] = new GPolyline (shortLine, color, bikes, 1);
            }
            else
            {
                allLine[i] = new GPolyline (shortLine, '#008000', 2, 1);
            }
            map.addOverlay (allLine[i]);
        }
    }
}


function prepareAutoRoute() {

    var i;
    
    for (i = 0; i < cars.length; i++) completeRoute[i] = Array(cars[i],cars[i]);
    for (i = 0; i < jobs.length; i++) jobs[i].routed = 0;

    drawCompleteRoute();
}

function jobSort(a,b) {
    return a[0] - b[0];
}



function doAutoRoute() {
    
    //prepareAutoRoute();
    var i;
    var doNextCar = -1;
    var stack = Array();
    //logClear();
    for (var car = 0; car < cars.length; car++) {
	var route = completeRoute[car]; 
	for (i = 0; i < jobs.length; i++) {
	    // finde besten Job
	    if (jobs[i].routed == 2) continue; // fertig
	    var job = jobs[i];
	    for (gap1 = 0; gap1 < route.length-1; gap1++) {
		// Berechne zuerst AditionalLength bei vollkommenen Insert zwischen zwei Gaps
		var leftNode = route[gap1];
		var rightNode = route[gap1 + 1];
		var dist = leftNode.distanceFrom(job.start) + rightNode.distanceFrom(job.end);
		if (route.length > 2) {
		    dist += job.distance;
		    dist -= leftNode.distanceFrom(rightNode); // Diese Stecke wird ersetzt
		}
		
		stack.push(Array(dist, car, i, gap1, gap1));
		//logger("JobC "+i+" Distance: " + dist);
		var dist1 = leftNode.distanceFrom(job.start) + 
			    rightNode.distanceFrom(job.start) - 
			    leftNode.distanceFrom(rightNode);
		
		for (gap2 = gap1+1; gap2 < route.length-1; gap2++) {
		    leftNode = route[gap2];
	    	    rightNode = route[gap2 + 1];
		    var dist2 = leftNode.distanceFrom(job.end) + 
				rightNode.distanceFrom(job.end) -
				leftNode.distanceFrom(rightNode);
		    dist = dist1+ dist2;
		    stack.push(Array(dist, car, i, gap1, gap2));
		    //logger("JobN "+i+" Distance: " + dist);
		}
		
		
	    }
	}
	
    }
    
    if (stack.length == 0) {
	alert("Routenberechnung zu Ende, es sind " +  (calcRouteLength(completeRoute[0])/1000) + " km zu fahren ")
	return; // fertig
    }
    stack.sort(jobSort);
    
    var i = 0;
    var chargeMax = 0;    
    do {
	best = stack[i];
	logger ("Am Besten fährt " + best[1] + " den Auftrag " + best[2] + " mit " + (best[0]/1000) +" zus. km, Gaps " + best[3] + ","+best[4] );
	var currRoute = completeRoute[best[1]]
	var currCharge=0;

	var newRoute = Array();
	var k = 0;
	var job = jobs[best[2]];
	job.routed = 2;
	for (j = 0; j < currRoute.length; j++) {
	    newRoute[k++] = currRoute[j]; // copy
	    if (j == best[3]) newRoute[k++] = job.start;
	    if (j == best[4]) newRoute[k++] = job.end;
	}
	chargeMax = 0;
	for (j = 0; j < newRoute.length; j++) {
	    currCharge += newRoute[j].charge;
	    if (currCharge > chargeMax) chargeMax = currCharge;
	}
	i++;
    } while (chargeMax > 5)
    logger ("Es sind max " + chargeMax + " Bikes geladen");
    // In Route von Auto einfügen
    completeRoute[best[1]] = newRoute
    drawCompleteRoute();    

    window.setTimeout("doAutoRoute()",50);
    return;

}

// calculate the minimal additional distance to a given route and a point
// this is also the best gap where to insert the point
function calcMinAddDist(route, point, jobID, gapStart) {

    var optimalLen = Number.MAX_VALUE;
    var optimalGap = -1;
    for (var i = gapStart; i < route.length - 1; i++) {
	var gapLen = route[i].distanceFrom(route[i+1]);
	var wayLen = route[i].distanceFrom(point) +
		     route[i+1].distanceFrom(point);
	wayLen -= gapLen;
	if (wayLen < optimalLen) {
	    optimalLen = wayLen;
	    optimalGap = i;
	}
    }
    return Array(optimalLen,optimalGap, jobID);
}


function calcRouteLength(route) {
    var dist = 0;
    for (var i = 0; i < route.length - 1; i++) {
	dist = dist + route[i].distanceFrom(route[i+1]);
    }
    return dist;
}
/*

var allLine;

var currDist; // distance of current way

function addAutoRoute(route, waypoints, gapStart) {
    
    var dist = 0;
    var minDist = 100000000;
    var res = Array();
    logging("Starte riesenschleife, currDist" + currDist);
	
    
       for (gapEnd = gapStart; gapEnd < route.length - 1; gapEnd++) {
	    dist = 0;
	    gapdist = 0;
	    if (gapStart == gapEnd) {
		dist += 	route[gapStart].distanceFrom(waypoints[0]) + 
		    		waypoints[0].distanceFrom(waypoints[1]) +
				waypoints[1].distanceFrom(route[gapStart+1]);
		gapdist =	route[gapStart].distanceFrom(route[gapStart+1]);
	    } else {
		    dist +=	route[gapStart].distanceFrom(waypoints[0]) + 
				waypoints[0].distanceFrom(route[gapStart+1]);
		    dist +=	route[gapEnd].distanceFrom(waypoints[1]) + 
				waypoints[1].distanceFrom(route[gapEnd+1]);
		    gapdist =	route[gapStart].distanceFrom(route[gapStart+1]) + 
				route[gapEnd].distanceFrom(route[gapEnd+1]);
    	    }
	    newDist = currDist - gapdist + dist;
	    //logging("MinDist " + minDist + " newDist " + newDist);
	    if (newDist > minDist) continue;	
	    // Route wird zw. Gapstart und Gapend eingefügt    
	    for (i = 0; i < route.length - 1; i++) {
		if (i == gapStart) continue;
		if (i == gapEnd) continue;
		dist = dist + route[i].distanceFrom(route[i+1]);
		calls++;
	    }
	    
	    if (dist < minDist) {
		minDist = dist;
		goodStart = gapStart;
		goodEnd = gapEnd;
	    }

	}
    logging("Calls nach Schleife: "+ calls);
    for (i = 0; i < route.length; i++) {
	res.push(route[i]);
	if (i == goodStart) res.push(waypoints[0]);
	//if (i == goodEnd) res.push(waypoints[1]);
	
    }
    
    currDist = minDist;
        
    return res;
}

function orderRoutePoints() {
    // bubblesort
    var l = routePoints.length;
    var lenCache = Array();

    for (var i = 0; i <l; i++) lenCache[i] = calcRouteLength(routePoints[i]);
    logging("lenCache init");
    for (var i = 0; i < l - 1; i++) {
	for (var j = i + 1; j < l; j++) {
	    if (lenCache[i] < lenCache[j]) {
		swap = routePoints[i];
		routePoints[i] = routePoints[j];
		routePoints[j] = swap;

		swap = lenCache[i];
		lenCache[i] = lenCache[j];
		lenCache[j] = swap;
	    }
	}
    }
}
var currPoint; // aktueller Fortschritt
var allLine;
var calls;

var isRouted = Array;





// route one point
function doAutoRoute() {
    car = 0;
    takeRoute = -1;
    var pointCandidates = Array();
    logging("pointCandidates calculating");

    for (var i = 0; i < routePoints.length; i++) {
	if (!isRouted[i]) pointCandidates[i] = calcMinAddDist(completeRoute[car], routePoints[i][0]);
    }
    
    var optimalLen = Number.MAX_VALUE;
    var candidate = -1;
    var gap;
    for (var i = 0; i < routePoints.length; i++) {
	if (!isRouted[i]) {
	    if (pointCandidates[i][0] < optimalLen) {
		optimalLen = pointCandidates[i][0];
		gap = pointCandidates[i][1];
		candidate = i;
	    }
	}
    }
    logging("pointCandidates calculated. Candidate " + candidate + " len: "+optimalLen);

    isRouted[candidate] = 1;

    completeRoute[car]=addAutoRoute(completeRoute[car],routePoints[candidate], gap);   

    for (i = 0; i < routePoints.length; i++) {
    }
    drawRouteControls();    
    drawCompleteRoute();
    return;
        
    if (currPoint < routePoints.length) {
    	window.setTimeout("doAutoRoute()",50);
    } else alert("Routenberechnung zu Ende, es sind " +  calcRouteLength(completeRoute[car]) + " m zu fahren, " + calls +" calls");
}

function drawCompleteRoute() {
    // clear lines
    for (i = 0; i < allLine.length; i++)
        if (allLine[i]) map.removeOverlay(allLine[i]);
	
    allLine = Array();
    bikes = 0;
    // make new lines
    for (i = 0; i < completeRoute[car].length-1; i++) {
	bikes += completeRoute[car][i].charge;
	shortLine = Array();
	shortLine.push(completeRoute[car][i]);
	shortLine.push(completeRoute[car][i+1]);
	
	if (bikes > 0) {
	    allLine[i] = new GPolyline(shortLine,'#000080',bikes,1);
	} else {
	    allLine[i] = new GPolyline(shortLine,'#008000',2,1);
	}
	map.addOverlay(allLine[i]);
    }
}

function generateText() {
    logClear()
    for (i = 0; i < routePoints.length; i++) {
	logging("addRoutePoint(new GLatLng" + routePoints[i][0] + ");");	
	logging("addRoutePoint(new GLatLng" + routePoints[i][1] + ");");
	logging("//--");
    }
    
}



function mvFwd(i) {
    swap=completeRoute[0][i];
    completeRoute[0][i]=completeRoute[0][i+1];
    completeRoute[0][i+1]=swap;
    drawRouteControls();    
    drawCompleteRoute();
}

function mvBwd(i) {
    swap=completeRoute[0][i];
    completeRoute[0][i]=completeRoute[0][i-1];
    completeRoute[0][i-1]=swap;
    drawRouteControls();    
    drawCompleteRoute();
}

function drawRouteControls() {
    html  = (calcRouteLength(completeRoute[0]) / 1000) + " km<br>";
    for (i = 0; i < completeRoute[0].length; i++) {
	myitem = completeRoute[0][i];  
	fwd="";
	bwd="";
	if (myitem.charge > 0) {
	    if (completeRoute[0][i+1].routeID != myitem.routeID) {
		fwd = "<span class=buttonM onclick='mvFwd(" + i + ")'>-&gt;</span>";
	    } else {
		fwd = "-|";
	    }
	    if (i > 1) {
		bwd = "<span class=buttonM onclick='mvBwd(" + i +")'>&lt;-</span>";
	    } else {
		bwd = "|=";
	    }
	}
	
	if (myitem.charge < 0) {
	    if (i < completeRoute[0].length - 1) {
		fwd = "<span class=buttonM onclick='mvFwd(" + i + ")'>-&gt;</span>";
	    } else {
		fwd = "-|";
	    }
	    if (completeRoute[0][i-1].routeID != myitem.routeID) {
		bwd = "<span class=buttonM onclick='mvBwd(" + i +")'>&lt;-</span>";
	    } else {
		bwd = "|=";
	    }
	}
	
	html = html + "["+bwd + myitem.routeID + fwd+"] ";
    }
    document.getElementById("coords").innerHTML = html;
}
*/


function loadPoints() {
    // lade Punkte
// Hamburg-Nürtingen    
addJob(new GLatLng(53.46, 9.94),
       new GLatLng(48.62, 9.35));

// Overath - Klaus
addJob(new GLatLng(50.95, 7.30),
       new GLatLng(47.31, 9.63));
// Biberach -Hausham 
addJob(new GLatLng(48.09, 9.70),
       new GLatLng(47.75, 11.82));

// Backnang - vadum 
addJob(new GLatLng(48.94, 9.43),
       new GLatLng(57.15, 9.87));

// Dresden - Bottrop
addJob(new GLatLng(51.12, 13.62),
       new GLatLng(51.53, 6.96));

// Frankfurt - Vantrupp
addJob(new GLatLng(52.35, 14.52),
       new GLatLng(55.41, 9.23));

// Sonthofen
addJob(new GLatLng(53.36, 9.91),
       new GLatLng(47.41, 10.27));

// Rheinberg - Landsberg
addJob(new GLatLng(51.58, 6.56),
       new GLatLng(50.85, 6.63));

// Schneverdingen Rumor
addJob(new GLatLng(53.12, 9.80),
       new GLatLng(54.24, 10.03));

// Jetzendorf - DK
addJob(new GLatLng(48.43,11.41),
       new GLatLng(55.41, 9.23));
       
// alter heugew - Kerpen
addJob(new GLatLng(52.67, 9.61),
       new GLatLng(50.85, 6.63));

// Hugo Klemm Str - Duttenhofer str
addJob(new GLatLng(53.46, 9.94),
       new GLatLng(48.62, 9.35));

// Potsdam - kaarst
addJob(new GLatLng(52.40, 13.11),
       new GLatLng(51.22, 6.60));


//--


plotJobs(1);

//addCarPoint(new GLatLng(48.58114989850295, 13.51268310546875));
addCarPoint(new GLatLng(48.72, 13.38));
//addCarPoint(new GLatLng(48.72, 14.38));


}