// neartree.js - Bruce Dodson, ESRI Canada, Jan 2002
//
// I need a search-structure to represent a set of point features
// to be used in on the client-side to implement things like
// tooltips.  There could be many sites points, so this needs to
// be fairly efficient.  (But doesn't need to be optimal.)

// I took an implementation of a simple nearest-neighbor tree from
// C/C++ User's Journal, November 2001, and ported the relevant
// bits to JavaScript.

// The coordinate reference is hardcoded as a 2D euclidian plane
// since that was what I needed.  I also only ported the two
// functions that were required in my app: insert() and nearest().
//
// For ECO-NOVA the new function within() was also needed, so I
// added that.  This part is original work; particularly the
// support
//
// aNearTree.insert(x,y,...)
//  - inserts a node into the tree
//  - any arguments past x,y are put in an array and associated
//    with the node.  If there are no arguments past x,y, the
//    data array will be empty initially.
//  - returns the associated data on success; null on failure.
//
// aNearTree.within(x,y, searchRadius, [maxResults])
//  - finds all nodes within searchRadius of x,y
//  - the result is returned as an array of objects, each
//    having properties x, y, distance, and data.  The data
//    property is the associated data array, and can be modified.
//  - if there is no match, an empty array is returned.
//  - if there are more than maxResults matches, the closest
//    ones are returned, sorted by distance.
//
// aNearTree.nearest(x,y, searchRadius)
//  - finds the closest node to x,y, to a maximum tolerance
//  - if a match is found, returns the associated data array.
//  - if no match found within the tolerance, null is returned
//  - this is similar to within(x,y,searchRadius)[0].data, except
//    a different result might be returned in case of a tie.
//
// You can modify the arrays returned from insert(), within(), or
// nearest().  However, do not modify the NearTree's internal data
// structures directly; only through the functions documented above.
//
// aNearTree.beginSelection(dataIndex)
//  - initializes the selection environment, which allows elements
//    to be filtered according to an attribute in the data arrays.
//  - dataIndex is the index within the data array of each node.
//  - elements having no data at that index are skipped
//  - until elements are added with addToSelection, there will be
//    no matches in nearest() and within() searches.
//
// aNearTree.addToSelection(dataValue)
//  - adds dataValue to the list of values matched in the data
//    array associated with each point.
//  - elements that whose data[dataIndex] value does not match
//    one of the dataValues added through addToSelection are
//    skipped in nearest() and within() searches.
//  - if dataValue is null, this has no effect since nulls are
//    always skipped anyway.
//  
// aNearTree.clearSelection()
//  - resets the selection environments so that all features are
//    once again searchable
//
// These methods were added for ECO-NOVA.  The map will normally
// display all of the ships, and only occasionally contains a
// subset (due to an attribute selection).  This is different
// from MEG, where there was an order of magnitude more points,
// but no map was ever shown without a selection.  So instead
// of generating a new NearTree at server-side for each selection,
// we we just apply a filter (that's what the selection methods
// are) to subset the results before adding them to the result
// set.

// For IE/Mac, it was discovered that the Array object there
// doesn't support shift / unshift / push / pop.  However, the
// array returned from aNearTree.within is guaranteed to have
// these functions (emulated, if necessary).


//===============================================
// ORIGINAL COPYRIGHT NOTES - DO NOT REMOVE
// Nearest Neighbor algorithm after Kalantari and McDonald,
// (IEEE Transactions on Software Engineering, v. SE-9, pp.
//    631-634,1983)
//  modified to use recursion instead of a double-linked tree
//  and simplified so that it does a bit less checking for
//  things like is the distance to the right less than the
//  distance to the left; it was found that these checks little
//  to no difference.
//
// copyright by Larry Andrews, 2001
//  may be freely distributed or used as long as this copyright
//  notice is included
//===============================================



function NearTree() {
  //these must be negative initially.
  this.m_leftMax = -1;
  this.m_rightMax = -1;

  //the rest can be null initially in JavaScript.
  //m_leftX/Y/Data, m_leftBranch
  //m_rightY/Y/Data, m_rightBranch
}

new NearTree(); // instantiate prototype


function NearTree_beginSelection(dataIndex) {
  this.clearSelection();
  this.m_selectionKeys = new Object();
  this.m_selectionDataIndex = (dataIndex >= 0) ? 0 + dataIndex : -1;
}
NearTree.prototype.beginSelection = NearTree_beginSelection;

function NearTree_addToSelection(dataValue) {
  if (this.m_selectionKeys && (this.m_selectionDataIndex >= 0)) {
    this.m_selectionKeys[dataValue] = this.m_selectionDataIndex;
  }
}
NearTree.prototype.addToSelection = NearTree_addToSelection;

function NearTree_clearSelection() {
  this.m_selectionKeys = null;
  this.m_selectionDataIndex = null;
}
NearTree.prototype.clearSelection = NearTree_clearSelection;


function NearTree_insert(x, y) {
  if ((x==null) || (y==null)) return null;

  // make the data array and insert any arguments past x,y.
  // Array.slice cannot be used since it's non-portable.
  // Array length constructor should not be used since it's deprectated.
  
  var data = new Array();
  var dataCount = NearTree_insert.arguments.length - 2;
  for (var dataIndex = 0; dataIndex < dataCount; ++dataIndex) {
    data[dataIndex] = NearTree_insert.arguments[dataIndex+2];
  }
  
  // descend_subtree approximates the recursive private member
  // function in the C++ implementation, but does not require
  // as many arguments because, in JavaScript, a nested
  // function binds to the local variables and arguments of
  // the enclosing function.

  function descend_subtree(tree) {
    if (tree.m_leftData == null) {
      tree.m_leftData = data;
      tree.m_leftX = 0+x;
      tree.m_leftY = 0+y;
      return true;
    } else if (tree.m_rightData == null ) {
      tree.m_rightData = data;
      tree.m_rightX = 0+x;
      tree.m_rightY = 0+y;
      return true;
    } else {
      var leftDistance  = Math.sqrt(Math.pow(x - tree.m_leftX,2)  + Math.pow(y - tree.m_leftY,2));
      var rightDistance = Math.sqrt(Math.pow(x - tree.m_rightX,2) + Math.pow(y - tree.m_rightY,2));

      if ( leftDistance > rightDistance ) {
        if (tree.m_rightBranch == null) tree.m_rightBranch = new NearTree();
        if (descend_subtree(tree.m_rightBranch)) {
          tree.m_rightMax = Math.max(tree.m_rightMax, rightDistance);
          return true;
        }
      } else {
        if (tree.m_leftBranch == null) tree.m_leftBranch  = new NearTree();
        if (descend_subtree(tree.m_leftBranch)) {
          tree.m_leftMax = Math.max(tree.m_leftMax, leftDistance);
          return true;
        }
      }
    }
    return false;
  }

  if (descend_subtree(this)) {
    if (this.count) {
      this.count++;
    } else {
      this.count = 1;
    }
    
    return data;
  } else {
    return null;
  }
}
NearTree.prototype.insert = NearTree_insert;


function NearTree_nearest(x, y, searchRadius) {
  // returns the data for closest object within the searchRadius,
  // or null if there was nothing within the tolerance
  
  // This is practically the same as

  if ((x==null) || (y==null) || (searchRadius<0)) return null;

  // Variables and arguments defined in the enclosing function
  // are accessible in the nested function.  'this' is also
  // accessible, but is confusing.

  var selection = this.m_selectionKeys;
  var dataIndex = this.m_selectionDataIndex;

  var search = new Object();
  search.result = null;
  if (searchRadius >= 0) {
    search.radius = searchRadius;
    search.distance2 = searchRadius * searchRadius;
  } else {
    search.radius = search.distance2 = Number.MAX_VALUE;
  }

  function descend_subtree(tree) {
    // first test each of the left and right positions to see if
    // one holds a point nearer than the nearest so far discovered.
    
    // ESRI Optimization: since the distances are never negative, 
    // comparing squares will give the same answer as comparing the
    // distances, so sqrt can be avoided.
    
    var leftDistance2, rightDistance2;
    if (tree.m_leftX != null) {
      var dx = x - tree.m_leftX;
      var dy = y - tree.m_leftY;
      leftDistance2 = (dx * dx) + (dy * dy);
      if (leftDistance2 <= search.distance2) {
        if ((selection==null) || ((tree.m_leftData.length > dataIndex) && selection[tree.m_leftData[dataIndex]] != null)) {
          search.distance2 = leftDistance2;
          search.radius = Math.sqrt(leftDistance2);
          search.result = tree.m_leftData;
        }
      }
    }

    if (tree.m_rightX != null) {
      var dx = x - tree.m_rightX;
      var dy = y - tree.m_rightY;
      rightDistance2 = (dx * dx) + (dy * dy);
      if (rightDistance2 <= search.distance2) {
        if ((selection==null) || ((tree.m_rightData.length > dataIndex) && selection[tree.m_rightData[dataIndex]] != null)) {
          search.distance2 = rightDistance2;
          search.radius = Math.sqrt(rightDistance2);
          search.result = tree.m_rightData;
        }
      }
    }

    // Now we test to see if the branches below might hold an object 
    // nearer than the best so far found. The triangle rule is used
    // to test whether it's even necessary to descend.
    // (See C/C++ User's Journal, Nov 2001)
    
    var leftRange = search.radius + tree.m_leftMax;
    if ( tree.m_leftBranch && ((leftRange * leftRange) >= leftDistance2) ) {
      descend_subtree(tree.m_leftBranch);
    }
    var rightRange = search.radius + tree.m_rightMax;
    if ( tree.m_rightBranch && ((rightRange * rightRange) >= rightDistance2) ) {
      descend_subtree(tree.m_rightBranch);
    }
  }

  descend_subtree(this);

  return search.result;
}
NearTree.prototype.nearest = NearTree_nearest;



function NearTree_within_result_push(v) {
  this[this.length] = v;
}

function NearTree_within_result_pop() {
  var result = null;
  if (this.length > 0) {
    var newLength = this.length - 1;
    result = this[newLength];
    this[newLength] = null;
    this.length = newLength;
  }
  return result;
}

function NearTree_within_result_unshift(v) {
  var i;
  for (i = this.length; i > 0; --i) {
    this[i] = this[i - 1];
  }
  this[0] = v;
}

function NearTree_within_result_shift() {
  var result = null;
  if (this.length > 0) {
    result = this[0];
    for (i = 1; i < this.length; ++i) {
      this[i - 1] = this[i];
    }
    var newLength = this.length - 1;
    this[newLength] = null;
    this.length = newLength;
  }
  return result;
}

function NearTree_within(x, y, searchRadius, maxResults) {
  if (maxResults <= 0) maxResults = null;

  var matches = new Array();

  //IE5 for Mac doesn't have these on its Array object...

  if (matches.shift == null) {
    matches.shift = NearTree_within_result_shift;
  }
  if (matches.unshift == null) {
    matches.unshift = NearTree_within_result_unshift;
  }
  if (matches.push == null) {
    matches.push = NearTree_within_result_push;
  }
  if (matches.pop == null) {
    matches.pop = NearTree_within_result_pop;
  }

  var selection = this.m_selectionKeys;
  var dataIndex = this.m_selectionDataIndex;

  var search = new Object();
  search.inclusive = true; // include matches that are on the boundary
  if (searchRadius >= 0) {
    search.radius = searchRadius;
    search.distance2 = searchRadius * searchRadius;
  } else {
    search.radius = search.distance2 = Number.MAX_VALUE;
  }

  function Match_toString() {
    return 'Match(' + this.x + ', ' + this.y + ', ' + this.distance + ', [' + String(this.data) + '])';
  }

  function Match(x, y, distance, data) {
    this.x = x;
    this.y = y;
    this.distance = distance;
    this.data = data;
    this.toString = Match_toString;
  }

  function compare_distance(a, b) {
    return a.distance - b.distance;
  }

  function add_match(x, y, distance2, data) {
    // Should the sqrt be deferred until later?  It could be, and the results array fixed up
    // right before it's returned.  The math would be slightly simpler when there are more
    // potential matches than we need.  But then name 'distance' is temporarily a lie.
    var distance = Math.sqrt(distance2); 
    var match = new Match(x, y, distance, data);
    if ((!maxResults) || (matches.length < maxResults)) {
      matches.push(match);

      if (matches.length == maxResults) {
        // the array is now full, but the search will continue in
        // case there are any closer matches.
        matches.sort(compare_distance);
        search.radius = matches[maxResults - 1].distance;
        search.distance2 = search.radius * search.radius;
        search.inclusive = false;
      }
    } else if (distance < matches[matches.length - 1].distance) {
      // already got a full set of matches, but this one is closer,
      // so the farthest match wil be bumped.

      if (matches.length == 1 || matches[matches.length - 2].distance <= distance) {
        // this element is closer than the farthest match, but is
        // farther than any other match.  so this element replaces
        // the farthest match and the search radius is reduced.
        matches[matches.length - 1] = match;
        search.radius = distance;
        search.distance2 = distance2;

      } else {
        // the farthest match is still bumped, but the new
        // element doesn't go at the end of the array

        matches.pop(1);
        search.radius = matches[matches.length - 1].distance;
        search.distance2 = search.radius * search.radius;

        // The match needs to be inserted somewhere in the array.
        // If we are here, the array is already sorted, so insertion sort.
        for (var i = matches.length - 1; i > 0; --i) {
          if (matches[i - 1].distance < distance) {
            matches.splice(i, 0, match);

            return null;
          }
        }
        // The new item is closer than any previous, so the insertion sort
        // falls through and the element goes at the very beginning.
        matches.unshift(match);
      }
    }
    return null;
  }

  // This is a copy and paste from _nearest.  It can be refactored into a common method.
  function descend_subtree(tree) {
    // first test each of the left and right positions to see if
    // one holds a point nearer than the nearest so far discovered.
    var leftDistance2, rightDistance2;
    if (tree.m_leftX != null) {
      var dx = x - tree.m_leftX;
      var dy = y - tree.m_leftY;
      leftDistance2 = (dx * dx) + (dy * dy);
      if (search.inclusive ? leftDistance2 <= search.distance2 : leftDistance2 < search.distance2) {
        if ((selection==null) || ((tree.m_leftData.length > dataIndex) && selection[tree.m_leftData[dataIndex]] != null)) {
          add_match(0 + tree.m_leftX, 0 + tree.m_leftY, leftDistance2, tree.m_leftData);
        }
      }
    }

    if (tree.m_rightX != null) {
      var dx = x - tree.m_rightX;
      var dy = y - tree.m_rightY;
      rightDistance2 = (dx * dx) + (dy * dy);
      if (search.inclusive ? rightDistance2 <= search.distance2 : rightDistance2 < search.distance2) {
        if ((selection==null) || ((tree.m_rightData.length > dataIndex) && selection[tree.m_rightData[dataIndex]] != null)) {
          add_match(0 + tree.m_rightX, 0 + tree.m_rightY, rightDistance2, tree.m_rightData);
        }
      }
    }

    // Now we test to see if the branches below might hold an object nearer than the current
    // search radius (which may have reduced since the beginning of the search, if max matches
    // have already been found).  The triangle rule is used to test whether it's even necessary
    // to descend.  (See C/C++ User's Journal, Nov 2001)
    
    // As an optimization, squared distances are used to reduce the number of sqrt calculations.
    // (With this optimization, sqrt is still needed for matches, to calculate the distance and
    // the new search radius if it has been reduced, but is not needed for non-matches.  Non
    // matches may still have matches in their subtrees.)  sqrt(x) is about 50% slower than x*x.
    
    if (search.inclusive) {
      var leftRange = search.radius + tree.m_leftMax;
      if ( tree.m_leftBranch && ((leftRange * leftRange) >= leftDistance2) ) {
        descend_subtree(tree.m_leftBranch);
      }
      var rightRange = search.radius + tree.m_rightMax;
      if ( tree.m_rightBranch && ((rightRange * rightRange) >= rightDistance2) ) {
        descend_subtree(tree.m_rightBranch);
      }
    } else if (search.radius > 0) {
      var leftRange = search.radius + tree.m_leftMax;
      if ( tree.m_leftBranch && ((leftRange * leftRange) > leftDistance2) ) {
        descend_subtree(tree.m_leftBranch);
      }
      var rightRange = search.radius + tree.m_rightMax;
      if ( tree.m_rightBranch && ((rightRange * rightRange) > rightDistance2) ) {
        descend_subtree(tree.m_rightBranch);
      }
    }
  }

  descend_subtree(this);

  if ((matches.length > 1) && ((!maxResults) || (matches.length < maxResults))) {
    matches.sort(compare_distance);
  }
  
  return matches;
}
NearTree.prototype.within = NearTree_within;


/**
 * As noted above, this file is is based in part on the work of Larry
 * Andrews.  The following notice applies to this file, with the
 * proviso that Larry Andrews' copyright notice cannot be removed.
 *
 *
 * These materials were developed by ESRI Canada and delivered under
 * contract to ECO-NOVA Productions.  The following license terms and
 * disclaimers apply.
 * 
 * Unless otherwise stated, the definition of "deliverables" includes the
 * complete contents of this file.  However, "deliverables" shall not not
 * include software, data and documentation that is subject to a separate
 * license from Environmental Systems Research Institute, Inc. of USA.
 * 
 * Copyright (c) 1997-2004 ESRI Canada Limited.
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this original work of authorship including all deliverables, to
 * deal with the deliverables without restriction, including without
 * limitation the rights to use, copy, modify, merge, publish, distribute,
 * sublicense, and/or sell copies of the deliverables, and to permit
 * persons to whom the deliverables are furnished to do so, subject to the
 * following conditions:
 * 
 *  * The above copyright notice and this permission notice shall be
 *    included in all copies of the software.
 *  
 *  * The name ESRI Canada shall not be used to endorse or promote
 *    products derived from the the software without specific prior
 *    written permission.
 * 
 * To the maximum extent permitted by applicable law, in no event shall
 * ESRI Canada be liable for any special, incidental, indirect or
 * consequential damanages whatsoever (including without limitation,
 * damages for loss of business profits, business interruption, loss of
 * business information, or any other pecuniary loss) arising out of the
 * use or inability to use the software, even if caused by ESRI Canada's
 * negligence or even if ESRI Canada has been advised of the possibility
 * of such damages.
 * 
 * ESRI Canada has extended a "Limited Warranty on Services" to ECO-NOVA
 * Productions as specified in the contract.  To the maximum extent
 * permitted by applicable law, ESRI Canada and its suppliers disclaim
 * all other warranties, representations, conditions or guarantees,
 * either express or implied, including but not limited to, implied
 * warranties of durability, merchantability and fitness for a
 * particular purpose, with regard to the software, services and any
 * accompanying documentation.
**/