// Copyright (c) 2008 Tony Garnock-Jones <tonyg@lshift.net>

 // Copyright (c) 2008 LShift Ltd. <query@lshift.net>

 //

 // Permission is hereby granted, free of charge, to any person

 // obtaining a copy of this software and associated documentation files

 // (the "Software"), to deal in the Software without restriction,

 // including without limitation the rights to use, copy, modify, merge,

 // publish, distribute, sublicense, and/or sell copies of the Software,

 // and to permit persons to whom the Software is furnished to do so,

 // subject to the following conditions:

 //

 // The above copyright notice and this permission notice shall be

 // included in all copies or substantial portions of the Software.

 //

 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,

 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF

 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND

 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS

 // BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN

 // ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN

 // CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE

 // SOFTWARE.

 Graph = {

     _foreach: function(arr, f) {

         for (var i = 0; i < arr.length; i++) {

             f(arr[i]);

         }

     },

     least_common_ancestor: function(parentsFun, leafId1, leafId2) {

         /* This is a pretty crude approximation. Since we're working

         with DAGs, rather than trees, it may not return the very very

         least common ancestor. */

         var potentialMatches = {};

         function augmentPotentialMatches(nodeId) {

             if (!potentialMatches[nodeId]) {

                 potentialMatches[nodeId] = nodeId;

                 Graph._foreach(parentsFun(nodeId), augmentPotentialMatches);

             }

         }

         augmentPotentialMatches(leafId2);

         var searchOrder = [leafId1];

         function queueForExamination(nodeId) {

             searchOrder.push(nodeId);

         }

         while (searchOrder.length) {

             var candidateId = searchOrder.shift();

             if (potentialMatches[candidateId]) {

                 return candidateId;

             } else {

                 Graph._foreach(parentsFun(candidateId), queueForExamination);

             }

         }

         return null; // no LCA found.

     }

 };