<commit_before>/**
 * AStar Path finding algorithm
 * @see http://eloquentjavascript.net/chapter7.html
 */
var BinaryHeap = require('gamejs/utils/binaryheap').BinaryHeap;

/**
 * helper function for A*
 */
function ReachedList() {
   var list = {};

   this.store = function(point, route) {
      list[point.hash()] = route;
      return;
   };

   this.find = function(point) {
      return list[point.hash()];
   };
   return this;
};


/** A* search function.
 *
 * This function expects a `Map` implementation and the origin and destination
 * `Point`s. If there is a path between the two it will return the optimal
 * path as a linked list. If there is no path it will return null.
 *
 * The linked list is in reverse order: the first item is the destination and
 * the path to the origin follows.
 *
 * @param {Map} map map instance, must follow interface defined in {Map}
 * @param {Point} origin
 * @param {Point} destination
 **/
exports.findRoute = function(map, from, to) {
   var open = new BinaryHeap(routeScore);
   var reached = new ReachedList();

   function routeScore(route) {
      if (route.score == undefined) {
         route.score = map.estimatedDistance(route.point, to) + route.length;
      }
      return route.score;
   }
   function addOpenRoute(route) {
      open.push(route);
      reached.store(route.point, route);
   }
   addOpenRoute({point: from,
                from: null,
                length: 0});

   while (open.size() > 0) {
      var route = open.pop();
      if (typeof route.point.equals === 'function' && route.point.equals(to)) {
         return route;
      }
      map.adjacent(route.point).forEach(function(direction) {
         var known = reached.find(direction);
         var newLength = route.length +
                         map.weightedDistance(route.point, direction);
         if (!known || known.length > newLength){
            if (known) {
               open.remove(known);
            }
            addOpenRoute({point: direction,
                          from: route,
                           length: newLength});
         }
      });
   } // end while
   return null;
};

/**
 * Point class on which A* operates.
 *
 * Constructor accepts either array `new Point([x,y])`
 * or `new Point(x, y)`.
 */
var Point = exports.Point = function() {
   var x = arguments[0];<commit_msg>astar: optional timeout for findRoute() - you don't want to use astar without timeout in browsers<commit_after>/**
 * AStar Path finding algorithm
 * @see http://eloquentjavascript.net/chapter7.html
 */
var BinaryHeap = require('gamejs/utils/binaryheap').BinaryHeap;

/**
 * helper function for A*
 */
function ReachedList() {
   var list = {};

   this.store = function(point, route) {
      list[point.hash()] = route;
      return;
   };

   this.find = function(point) {
      return list[point.hash()];
   };
   return this;
};


/** A* search function.
 *
 * This function expects a `Map` implementation and the origin and destination
 * `Point`s. If there is a path between the two it will return the optimal
 * path as a linked list. If there is no path it will return null.
 *
 * The linked list is in reverse order: the first item is the destination and
 * the path to the origin follows.
 *
 * @param {Map} map map instance, must follow interface defined in {Map}
 * @param {Point} origin
 * @param {Point} destination
 * @param {Number} timeout milliseconds after which search should be canceled
 **/
exports.findRoute = function(map, from, to, timeout) {
   var open = new BinaryHeap(routeScore);
   var reached = new ReachedList();

   function routeScore(route) {
      if (route.score == undefined) {
         route.score = map.estimatedDistance(route.point, to) + route.length;
      }
      return route.score;
   }
   function addOpenRoute(route) {
      open.push(route);
      reached.store(route.point, route);
   }
   addOpenRoute({point: from,
                from: null,
                length: 0});

   var startMs = Date.now();
   while (open.size() > 0 && (!timeout || Date.now() - startMs < timeout)) {
      var route = open.pop();
      if (typeof route.point.equals === 'function' && route.point.equals(to)) {
         return route;
      }
      map.adjacent(route.point).forEach(function(direction) {
         var known = reached.find(direction);
         var newLength = route.length +
                         map.weightedDistance(route.point, direction);
         if (!known || known.length > newLength){
            if (known) {
               open.remove(known);
            }
            addOpenRoute({point: direction,
                          from: route,
                           length: newLength});
         }
      });
   } // end while
   return null;
};

/**
 * Point class on which A* operates.
 *
 * Constructor accepts either array `new Point([x,y])`
 * or `new Point(x, y)`.
 */
var Point = exports.Point = function() {
   var x = arguments[0];
{'fraction_non_alphanumeric': 0.12545454545454546, 'fraction_numerical': 0.0016161616161616162, 'mean_word_length': 2.386456908344733, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4204742', 'n_tokens_mistral': 1422, 'n_tokens_neox': 1399, 'n_words': 441}