/** * Padvinder! * Uit een verzameling punten die verbonden zijn met lijn, * vindt het kortste pad tussen 2 punten. */ /** * Alle padvinder-meuk zit in dit object */ var Padvinder = { /** * @var Array Punten alle punten */ Punten: [], /** * @var Array Lijnen alle lijnen */ Lijnen: [], /** * Callback voor het sorteren van 'n padvinder-object op lengte, kortste eerst */ kortsteEerst: function(a, b){ return a.lengte - b.lengte; }, /** * Punten zijn nodig om lijnen af te bakenen * * @param String naam de naam van dit Punt */ Punt: function(naam){ /** * @var Number id waar dit punt in de Punten array te vinden is */ this.id; /** * @var Array lijnen alle lijnen aan dit punt, voor gebruiksvriendelijkheid */ this.lijnen = []; /** * @var String naam puur voor aestetische redenen */ this.naam; /** * Laat het weten dat er (nog) een lijn aan dit punt verbonden is * * @param Lijn lijn */ this.voegLijnToe = function(lijn){ // Zorg ervoor dat geen Lijn er 2x in zit for(var x = 0; x < this.lijnen.length; x++){ if(this.lijnen[x] == lijn) return this.lijnen[x]; } // Nu weten we dat deze Lijn uniek aan dit Punt zit this.lijnen.push(lijn); // Sorteer de lijnen op volgorde van lengte, kortste eerst this.lijnen = this.lijnen.sort(Padvinder.kortsteEerst); } /** * Laat het bekend zijn dat de Lijn niet langer is * dit impliceert dus ook dat de Lijn eerst van het Punt * wordt gehaald en daarna pas echt weggegooid wordt * * @param Lijn lijn */ this.verwijderLijn = function(lijn){ for(var x = 0; x < this.lijnen.length; x++){ if(this.lijnen[x] == lijn) this.lijnen = this.lijnen.splice(x, 1); } // Sorteer de lijnen op volgorde van lengte, kortste eerst this.lijnen = this.lijnen.sort(Padvinder.kortsteEerst); } /** * Voor log */ this.toString = function(){ return "Punt: "+this.naam; } if(typeof(naam) != "undefined"){ this.naam = naam; } }, /** * Een lijn wordt gedefiniëerd door twee punten * * @param String naam de naam van deze Lijn * @param Punt puntA het ene uiteinde van de Lijn * @param Punt puntB het andere uiteinde * @param Number lengte de kosten */ Lijn: function(naam, puntA, puntB, lengte){ /** * @var Number id waar deze Lijn in de Lijnen array te vinden is */ this.id; /** * @var Punt puntA het ene uiteinde van deze lijn */ this.puntA; /** * @var Punt puntB het ander uiteinde */ this.puntB; /** * @var Number lengte de kosten van deze lijn */ this.lengte; /** * @var String naam puur voor aestetische redenen */ this.naam; /** * Gegeven het ene punt, retourneer het andere * * @param Punt enePunt het ene punt */ this.anderePunt = function(enePunt){ if(this.puntA == enePunt){ return this.puntB; } return this.puntA; } /** * Voor log */ this.toString = function(){ return "Lijn #"+this.naam+":"+this.lengte; } if(typeof(naam) != "undefined"){ this.naam = naam; } if(typeof(puntA) != "undefined"){ this.puntA = puntA; // Nu kunnen we deze Lijn ook toevoegen aan dit Punt this.puntA.voegLijnToe(this); } if(typeof(puntB) != "undefined"){ this.puntB = puntB; // Nu kunnen we deze Lijn ook toevoegen aan dit Punt this.puntB.voegLijnToe(this); } if(typeof(lengte) != "undefined"){ this.lengte = lengte; } }, /** * Een Route beschrijft een aantal Punten en Lijnen die aan elkaar zitten */ Route: function(naam){ /** * @var Array lijnen de lijnen in deze route */ this.pad = []; /** * @var Number lengte de gezamelijke lengte van de lijnen */ this.lengte = 0; /** * @var Punt puntA het ene uiteinde van deze Route */ this.puntA; /** * @var Punt puntB het andere uiteinde */ this.puntB; this.naam; /** * Een Lijn aan deze Route toevoegen * * @param Lijn de lijn toe te voegen */ this.voegLijnToe = function(lijn, puntB){ if(this.pad.length == 0){ // Eerste lijn this.pad.push(lijn.anderePunt(puntB)); this.puntA = this.pad[0]; this.pad.push(lijn); this.puntB = puntB; this.pad.push(puntB); }else{ if(lijn.anderePunt(puntB) != this.pad[this.pad.length-1]) throw new Error("Route niet consequent"); this.pad.push(lijn); this.puntB = puntB; this.pad.push(puntB); } this.lengte += lijn.lengte; } /** * Gegeven het ene punt, retourneer het andere * * @param Punt enePunt het ene punt */ this.anderePunt = function(enePunt){ if(this.puntA == enePunt){ return this.puntB; } if(this.puntB != enePunt) throw new Error("Punt ["+enePunt.id+"] zit niet aan deze lijn"); return this.puntA; } /** * Maak een nieuwe Route gebaseerd op deze * * @return Route een kopie van deze */ this.kloon = function(){ var nieuwe = new Padvinder.Route(); nieuwe.pad = this.pad.slice(0); // Wel'n kopie maken nieuwe.lengte = this.lengte; nieuwe.puntA = this.puntA; nieuwe.puntB = this.puntB; return nieuwe; } /** * Controleer of deze Route nog wel consequent is */ this.check = function(){ // Check beginpunt if(this.pad[0] != this.puntA) throw new Error("Eerste element is niet puntA"); for(var x = 1; x < this.pad; x++){ // Elk even element is 'n Lijn, elk oneven 'n Punt if(x % 2){ if(!(this.pad[x] instanceof Lijn)) throw new Error("Element ["+x+"] is even, maar geen Lijn"); // Kijk of het vorige element, 'n Punt, ook verbonden is aan deze lijn if(this.pad[x].puntA != this.pad[x-1] && this.pad[x].puntB != this.pad[x-1]) throw new Error("Vorige Punt niet verbonden met deze Lijn ["+x+"]"); }else{ if(!(this.pad[x] instanceof Punt)) throw new Error("Element ["+x+"] is oneven, maar geen Punt"); // Kijk of het vorige element, 'n Lijn, ook aan dit Punt zit if(this.pad[x].lijnen.indexOf(this.pad[x-1]) == -1) throw new Error("Vorige Lijn niet verbonden met dit Punt ["+x+"]"); } } // Check 't eindpunt if(this.pad.last() != this.puntB) throw new Error("Laatste element is niet puntB"); } /** * Voor log */ this.toString = function(){ var str = this.pad[0].naam+" "; for(var x = 1; x < this.pad.length; x++){ if(x % 2){ str += "--"+this.pad[x].naam+":"+this.pad[x].lengte+"-- "; }else{ str += ""+this.pad[x].naam+" "; } } return str+":: "+this.lengte; } if(typeof(naam) != "undefined"){ this.naam = naam; } }, /** * Voegt een punt toe aan de Punten array. * Dit is de enige juiste manier om een Punt te maken, * anders is'ie niet bruikbaar. * * @param String naam de naam van het Punt (Punt.naam) */ voegPuntToe: function(naam){ var puntje = new Padvinder.Punt(naam); puntje.id = Padvinder.Punten.push(puntje)-1; return puntje; }, /** * Haalt een Punt weg * Dit haalt ook alle Lijnen die aan het Punt zitten weg * * @param Punt punt */ verwijderPunt: function(punt){ // Eerst alle lijnen weghalen for(var x = 0; x < punt.lijnen.length; x++){ Padvinder.verwijderLijn(punt.lijnen[x]); } Padvinder.Punten = Padvinder.Punten.splice(punt.id, 1); punt = null; }, /** * Voegt een lijn toe aan de Lijnen array * Dit is de enige juiste manier om een Lijn te maken, * anders is'ie niet bruikbaar. * * @param String naam de naam van de Lijn (Lijn.naam) * @param Punt puntA het ene uiteinde van de Lijn (Lijn.puntA) * @param Punt puntB het andere uiteinde (Lijn.puntB) * @param Number lengte de lengte (Lijn.lengte) */ voegLijnToe: function(naam, puntA, puntB, lengte){ for(var x = 0; x < Padvinder.Lijnen.length; x++){ var dezeLijn = Padvinder.Lijnen[x]; if((dezeLijn.puntA == puntA && dezeLijn.puntB == puntB) || (dezeLijn.puntA == puntB && dezeLijn.puntB == puntA)){ throw new Error("Er is al een Lijn tussen Punt ["+puntA.id+"] en Punt ["+puntB.id+"]"); return; } } var lijntje = new Padvinder.Lijn(naam, puntA, puntB, lengte); lijntje.id = Padvinder.Lijnen.push(lijntje)-1; return lijntje; }, /** * Verwijdert een Lijn * * @param Lijn lijn */ verwijderLijn: function(lijn){ // Zorg dat de Punt'en het ook weten lijn.puntA.verwijderLijn(lijn); lijn.puntB.verwijderLijn(lijn); Padvinder.Lijnen = Padvinder.Lijnen.splice(lijn.id, 1); lijn = null; }, /** * De echte, ware, padvinder * * @param Punt start het begin-Punt * @param Punt eind waar we heen moeten * @return Array 'n lijst met Routes, gesorteerd op lengte, oplopend */ KortstePad: function(start, eind){ var routes = [], dezeLijn, dezeRoute, kortste, nieuweRoute, x, y; for(x = 0; x < start.lijnen.length; x++){ dezeLijn = start.lijnen[x]; // Elke lijn is een nieuwe Route dezeRoute = new Padvinder.Route(); routes.push(dezeRoute); dezeRoute.voegLijnToe(dezeLijn, dezeLijn.anderePunt(start)); } /* De routes array is nu gevuld met alle punten die 1 punt verder dan het startpunt zijn Nu gaan we langs die Routes en breiden we ze uit met de Lijnen en Punten die aan die punten liggen */ x = 0; kortste = null; // De tot-dan-toe kortste Route die al klaar is while(x < routes.length){ dezeRoute = routes[x]; // Deze route is klaar if(dezeRoute.puntB == eind){ // Nieuwe kortste Route if(dezeRoute.lengte < kortste || kortste === null){ kortste = dezeRoute.lengte; } x++; continue; } // Als deze Route (nu al) langer is dan de kortste, sla 'm dan over if(kortste !== null && dezeRoute.lengte > kortste){ x++; continue; } /* Ga langs alle lijnen en maak nieuwe Routes van alle lijnen die niet teruglopen naar een Punt waar we al geweest zijn */ for(y = 0; y < dezeRoute.puntB.lijnen.length; y++){ dezeLijn = dezeRoute.puntB.lijnen[y]; // Deze lijn gaat terug if(dezeRoute.pad.indexOf(dezeLijn.anderePunt(dezeRoute.puntB)) != -1){ continue; } nieuweRoute = dezeRoute.kloon(); nieuweRoute.voegLijnToe(dezeLijn, dezeLijn.anderePunt(dezeRoute.puntB)); routes.push(nieuweRoute); } x++; } // Einde while-lus // Haal nu alle lege elementen eruit en sorteer 'm op de lengte routes = routes.filter(function(elm){ return (elm != null && elm.puntB == eind); }).sort(Padvinder.kortsteEerst); return routes; } };