module Geomodel

# File lib/geomodel.rb, line 35
def self.filter_result_set_by_bounding_box(bounding_box, result_set)
  result_set.select do |row|
    row.latitude >= bounding_box.south &&
    row.latitude <= bounding_box.north &&
    row.longitude >= bounding_box.west &&
    row.longitude <= bounding_box.east
  end
end

# File lib/geomodel.rb, line 26
def self.geocells_for_bounding_box(bounding_box, cost_function = nil)
  cost_function = DEFAULT_COST_FUNCTION if cost_function.nil?
  Geomodel::GeoCell.best_bbox_search_cells(bounding_box, cost_function)
end

# File lib/geomodel.rb, line 51
def self.proximity_fetch(center, query_runner, max_results = 10, max_distance = 0)
  results = []

  searched_cells = Set.new
  
  # The current search geocell containing the lat,lon.
  cur_containing_geocell = Geomodel::GeoCell.compute(center)
  
  # The currently-being-searched geocells.
  # NOTES:
  #     * Start with max possible.
  #     * Must always be of the same resolution.
  #     * Must always form a rectangular region.
  #     * One of these must be equal to the cur_containing_geocell.
  cur_geocells = [cur_containing_geocell]

  closest_possible_next_result_dist = 0
  
  # Assumes both a and b are lists of (entity, dist) tuples, *sorted by dist*.
  # NOTE: This is an in-place merge, and there are guaranteed
  # no duplicates in the resulting list.
  
  cmp_fn = lambda do |x, y| 
    (!x.empty? && !y.empty?) ? x[1] <=> y[1] : 0
  end
  
  dup_fn = lambda do |x|
    (x.nil? || x.empty?) ? nil : x[0].id 
  end # assuming the the element responds to #id

  sorted_edges = [[0,0]]
  sorted_edge_distances = [0]
  
  while !cur_geocells.empty?
    closest_possible_next_result_dist = sorted_edge_distances[0]
    
    break if max_distance && closest_possible_next_result_dist > max_distance

    cur_geocells_unique = cur_geocells - searched_cells.to_a
      
    # Run query on the next set of geocells.
    cur_resolution = cur_geocells[0].size
    
    # Update results and sort.
    new_results = query_runner.call(cur_geocells_unique)
    
    searched_cells.merge(cur_geocells)
    
    # Begin storing distance from the search result entity to the
    # search center along with the search result itself, in a tuple.
    new_results = new_results.map { |entity|  [entity, Geomodel::Math.distance(center, entity.location)] }
    new_results.sort! { |x, y| (!x.empty? && !y.empty?) ? x[1] <=> y[1] : 0 }
    new_results = new_results[0...max_results]
    
    # Merge new_results into results or the other way around, depending on
    # which is larger.
    if results.size > new_results.size
      Geomodel::Util.merge_in_place(results, [new_results], dup_fn, cmp_fn)
    else
      Geomodel::Util.merge_in_place(new_results, [results], dup_fn, cmp_fn)
      results = new_results
    end

    results = results[0...max_results]
    
    sorted_edges, sorted_edge_distances = Geomodel::Util.distance_sorted_edges(cur_geocells, center)

    if results.empty? || cur_geocells.size == 4
      # Either no results (in which case we optimize by not looking at adjacents, go straight to the parent)
      # or we've searched 4 adjacent geocells, in which case we should now search the parents of those
      # geocells.
      cur_containing_geocell = cur_containing_geocell[0...-1]
      cur_geocells = cur_geocells.map { |cell| cell[0...-1] }   
      break if cur_geocells.empty? || !cur_geocells[0] # Done with search, we've searched everywhere.
    elsif cur_geocells.size == 1
      # Get adjacent in one direction.
      # TODO(romannurik): Watch for +/- 90 degree latitude edge case geocells.
      nearest_edge = sorted_edges[0]
      cur_geocells << Geomodel::GeoCell.adjacent(cur_geocells[0], nearest_edge)
    elsif cur_geocells.size == 2
      # Get adjacents in perpendicular direction.
      nearest_edge = Geomodel::Util.distance_sorted_edges([cur_containing_geocell], center)[0][0]
      if nearest_edge[0] == 0
        # Was vertical, perpendicular is horizontal.
        perpendicular_nearest_edge = sorted_edges.keep_if { |x| x[0] != 0 }.first
      else
        # Was horizontal, perpendicular is vertical.
        perpendicular_nearest_edge = sorted_edges.keep_if { |x| x[0] == 0 }.first
      end
      
      cur_geocells.concat(
        cur_geocells.map { |cell| Geomodel::GeoCell.adjacent(cell, perpendicular_nearest_edge) } 
      )
    end
    
    # We don't have enough items yet, keep searching.
    next if results.size < max_results

    # If the currently max_results'th closest item is closer than any
    # of the next test geocells, we're done searching.
    current_farthest_returnable_result_dist = Geomodel::Math.distance(center, results[max_results - 1][0].location)
    break if (closest_possible_next_result_dist >= current_farthest_returnable_result_dist)
  end
  
  results[0...max_results].keep_if { |result| max_distance == 0 || result.last < max_distance }  
end