/**
 * You should copy the declarations and definitions in this file to
 * the appropriate places in your kdtree.c.
 * 
 * The given implementation is inefficient -- it searches the entire
 * subtree.  You will have to modify it to meet the O(sqrt(n)) running
 * time.
 *
 * Note that this assumes there is a kdtree_node struct defined with
 * members left, right, and loc; edit accordingly if you use different
 * fields in your nodes.  Note that the functions declared here expect
 * dimension 0 to be longitude and dimension 1 to be latitude (the
 * opposite of how they're normally listed, but matching longitude as
 * analagous to x-coordinate and latitude as y-coordinate.
 */


/**
 * Information about a link to a node in a tree.
 */
typedef struct
{
  kdtree_node *n; // the node
  kdtree_node **ptr_to_n; // a pointer to the pointer to the node
  int n_dim; // the cutting dimention of n (0=lon, 1=lat)
} kdtree_link_info;


/**
 * Finds the node with the extremest (max or min) value in the
 * given dimension in the subtree rooted at the given node.
 *
 * @param r a pointer to the root of the subtree to search, non-NULL
 * @param r_dim the cutting dimension of that root, 0 for x/lon and 1 for y/lat
 * @param ptr_to_r a pointer to the pointer to r
 * @param dim the dimension to find the extreme in: 0 for x/lon, 1 for y/lat
 * @param factor 1 to find max, -1 to find min
 * @return a kdtree_link_info struct for the node in the subtree rooted at r
 * that contains the most extreme coordinate
 */
kdtree_link_info kdtree_find_extreme(kdtree_node *r, int r_dim, kdtree_node **ptr_to_r, int dim, int factor);

kdtree_link_info kdtree_find_extreme(kdtree_node *r, int r_dim, kdtree_node **ptr_to_r, int dim, int factor)
{
  kdtree_link_info info;
  
  if (r->left == NULL && r->right == NULL)
    {
      // node is a leaf, so it has the most extreme value in its subtree
      info.n = r;
      info.ptr_to_n = ptr_to_r;
      info.n_dim = r_dim;
    }
  else
    {
      // initialize extreme to value in root of subtree
      info.n = r;
      info.ptr_to_n = ptr_to_r;
      info.n_dim = r_dim;
      location extreme = r->loc;

      // compare extreme to extreme from left subtree
      if (r->left != NULL)
        {
          kdtree_link_info left_info = kdtree_find_extreme(r->left, 1 - r_dim, &r->left, dim, factor);

          // if cutting dimension is 0, compare by longitude, otherwise
          // by latitude; note that determining which of two values a and b
          // is the minimum is equivalent to determining the max of -a and -b
          // (this is how factor is used)
          if ((dim == 0 && factor * location_compare_longitude(&left_info.n->loc, &extreme) > 0)
              || (dim == 1 && factor * location_compare_latitude(&left_info.n->loc, &extreme) > 0))
            {
              info = left_info;
              extreme = info.n->loc;
            }
        }

      // compare extreme to extreme from right subtree
      if (r->right != NULL)
        {
          kdtree_link_info right_info = kdtree_find_extreme(r->right, 1 - r_dim, &r->right, dim, factor);

          if ((dim == 0 && factor * location_compare_longitude(&right_info.n->loc, &extreme) > 0)
              || (dim == 1 && factor * location_compare_latitude(&right_info.n->loc, &extreme) > 0))
            {
              info = right_info;
              extreme = info.n->loc;
            }
        }
    }

  return info;
}