#!/usr/bin/ruby
#
# Expires tiles based on database queries.
#
# Phil! Gold <phil_g@pobox.com>
#
# Some parts derived from osm2pgsql, http://wiki.openstreetmap.org/wiki/Osm2pgsql
#
# This script is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; either version 2 of the License, or
# (at your option) any later version.

# Borrowed from osm2pgsql/reprojection.c
EARTH_CIRCUMFERENCE = 40075016.68
# How many tiles worth of space to leave either side of a changed feature
TILE_EXPIRY_LEEWAY = 0.5
# Maximum width or height of a bounding box (metres)
EXPIRE_TILES_MAX_BBOX = 30000

require 'optparse'
require 'dbi'

options = {}

optparse = OptionParser.new do |opts|
  opts.banner = "Usage: expire-query [options] query query ..."

  opts.separator ""
  opts.separator "Runs each query and generates a tile expiry list for every tile crossed"
  opts.separator "by the geometries returned from the queries.  Each query must return the"
  opts.separator "geometries in a column named \"way\"."
  opts.separator ""

  options[:db] = 'osm'
  opts.on('-d', '--database DATABASE',
          "Database to connect to (default \"#{options[:db]}\")") do |db|
    options[:db] = db
  end

  opts.on('-h', '--host HOST', 'Host to connect to') do |host|
    options[:host] = host
  end

  options[:user] = ENV['USER']
  opts.on('-u', '--user USER', "User to connect as (default \"#{options[:user]}\")") do |user|
    options[:user] = user
  end

  opts.on('-p', '--password PASSWORD', 'Password to use') do |password|
    options[:password] = password
  end

  options[:output] = '-'
  opts.on('-o', '--output FILE',
          "Output file; \"-\" for stdout (default \"#{options[:output]}\")") do |output|
    options[:output] = output
  end

  options[:zoom] = 18
  opts.on('-z', '--zoom ZOOM', Integer,
          "Zoom level at which to generate expired tiles",
          "  (default #{options[:zoom]})") do |zoom|
    options[:zoom] = zoom
  end

  #opts.on('-h', '--help', 'Display this message') do
  #  puts opts
  #  exit
  #end
end

optparse.parse!

class Point < Struct.new(:x, :y)
  def initialize(*args)
    if args.empty?
      super(0, 0)
    elsif args.count == 1
      super(*args[0].split)
    else
      super(*args)
    end
    unless self.x.kind_of? Numeric
      self.x = self.x.to_f
    end
    unless self.y.kind_of? Numeric
      self.y = self.y.to_f
    end
  end
end

def split_geometry(geometry)
  result = []
  current = ''
  level = 0
  geometry.each_char do |c|
    case c
    when ','
      if level == 0
        result << current
        current = ''
      else
        current << c
      end
    when '('
      level = level + 1
      current << c
    when ')'
      level = level - 1
      current << c
    else
      current << c
    end
  end
  result << current
  result.map do |s| s.strip end
end

def unwrap_geometry(geometry)
  geometry.gsub(/^\(|\)$/, '')
end

def coords_to_tile(z, point)
  map_width = 1 << z
  Point.new(map_width * (0.5 + point.x / EARTH_CIRCUMFERENCE),
            map_width * (0.5 - point.y / EARTH_CIRCUMFERENCE))
end

def expire_tile(z, tile, expired)
  x = tile.x.to_i
  y = tile.y.to_i

  unless expired[z]
    expired[z] = {}
  end
  unless expired[z][x]
    expired[z][x] = {}
  end
  expired[z][x][y] = true
end

def expire_point(z, point, expired)
  expire_tile(z, coords_to_tile(z, Point.new(point)), expired)
end

def expire_bbox(z, bbox, expired)
  map_width = 1 << z
  (bbox.min {|a,b| a.x <=> b.x}.x .. bbox.max {|a,b| a.x <=> b.x}.x).step(1) do |x|
    (bbox.min {|a,b| a.y <=> b.y}.y .. bbox.max {|a,b| a.y <=> b.y}.y).step(1) do |y|
      expire_tile(z, Point.new(x % map_width, y), expired)
    end
  end
end

def expire_linestring(z, line, expired)
  map_width = 1 << z

  points = split_geometry(line)
  points[0..-2].zip(points[1..-1]).each do |segment|
    a = coords_to_tile(z, Point.new(segment[0]))
    b = coords_to_tile(z, Point.new(segment[1]))

    # Line always goes from left to right.
    if a.x > b.x
      a, b = b, a
    end

    # If the line is wider than half the map, assume it crosses the
    # international date line.  These coordinates get normalised again later.
    if b.x - a.x > map_width
      a.x += map_width
      a, b = b, a
    end

    x_len = b.x - a.x
    y_len = b.y - a.y
    hyp_len = Math.sqrt(x_len**2 + y_len**2)  # Pythagoras
    x_step = x_len / hyp_len
    y_step = y_len / hyp_len
    (0..hyp_len).step(1) do |step|
      next_step = step + 1 > hyp_len ? hyp_len : step + 1
      tile = Point.new(a.x + step * x_step, a.y + step * y_step)
      next_tile = Point.new(a.x + next_step * x_step, a.y + next_step * y_step)

      # The line tile..next_tile is up to 1 tile width long tile.x will always
      # be <= next_tile.x
      # We could be smart and figure out the exact tiles intersected, but for
      # simplicity, treat the coordinates as a bounding box and expire
      # everything within that box.
      if tile.y > next_tile.y
        tile.y, next_tile.y = next_tile.y, tile.y
      end
      expire_bbox(z,
                  [Point.new(tile.x - TILE_EXPIRY_LEEWAY, tile.y - TILE_EXPIRY_LEEWAY),
                   Point.new(next_tile.x + TILE_EXPIRY_LEEWAY, next_tile.y + TILE_EXPIRY_LEEWAY)],
                  expired)
    end
  end
end

def get_polygon_bbox(polygon)
  points = split_geometry(polygon).map do |p| Point.new(p) end
  ll = points.inject(Point.new(points[0].x, points[0].y)) do |ll, p|
    ll.x = p.x if p.x < ll.x
    ll.y = p.y if p.y < ll.y
    ll
  end
  ur = points.inject(Point.new(points[0].x, points[0].y)) do |ur, p|
    ur.x = p.x if p.x > ur.x
    ur.y = p.y if p.y > ur.y
    ur
  end
  [ll, ur]
end

def expire_simple_polygon(z, polygon, expired)
  bbox = get_polygon_bbox(polygon)
  width = bbox[1].x - bbox[0].x
  height = bbox[1].y - bbox[0].y
  if width < EXPIRE_TILES_MAX_BBOX and height < EXPIRE_TILES_MAX_BBOX
    expire_bbox(z, bbox.map { |p| coords_to_tile(z, p) }, expired)
  else
    STDERR.puts "Large polygon (#{width.to_i} x #{height.to_i} metres) - only expiring perimeter"
    expire_linestring(z, polygon, expired)
  end
end

def expire_polygon(z, polygon, expired)
  split_geometry(polygon).each do |simple|
    expire_simple_polygon(z, unwrap_geometry(simple), expired)
  end
end

def expire(z, way, expired)
  match = /^([^(]+)(.*)$/.match(way)
  type = match[1]
  content = unwrap_geometry(match[2])
  case type
  when "POINT"
    expire_point(z, content, expired)
  when "LINESTRING"
    expire_linestring(z, content, expired)
  when "POLYGON"
    expire_polygon(z, content, expired)
  when "MULTIPOINT"
    split_geometry(content).each do |point|
      expire_point(z, point, expired)
    end
  when "MULTILINESTRING"
    split_geometry(content).each do |line|
      expire_linestring(z, line, expired)
    end
  when "MULTIPOLYGON"
    split_geometry(content).each do |polygon|
      expire_polygon(z, polygon, expired)
    end
  when "GEOMETRYCOLLECTION"
    split_geometry(content).each do |geometry|
      expire(z, geometry, expired)
    end
  end
end

def output_expired(expired, file)
  expired.each do |z, z_exp|
    z_exp.each do |x, x_exp|
      x_exp.each_key do |y|
        file.puts "#{z}/#{x}/#{y}"
      end
    end
  end
end

connect_str = 'DBI:Pg:' + options[:db]
if options[:host]
  connect_str = connect_str + ':' + options[:host]
end
DBI.connect(connect_str, options[:user], options[:password]) do |osm_db|
  expired = {}
  ARGV.each do |query|
    osm_db.select_all("SELECT ST_AsText(way) FROM (#{query}) ways") do |row|
      expire(options[:zoom], row[0], expired)
    end
  end
  if options[:output] == '-'
    output_expired(expired, STDOUT)
  else
    File.open(options[:output], 'w') do |file|
      output_expired(expired, file)
    end
  end
end