#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# This script will take as input a list of filenames and output a list of
# all tiles referenced in those files and their parent and child tiles. This
# is for use with osm2pgsql's --expire-tiles output.
#
# Copyright (c) 2009 Jonas Häggqvist <rasher_at_rasher_dot_dk>
#
# Permission is hereby granted, free of charge, to any person
# obtaining a copy of this software and associated documentation
# files (the "Software"), to deal in the Software without
# restriction, including without limitation the rights to use,
# copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the
# Software is furnished to do so, subject to the following
# conditions:
#
# The above copyright notice and this permission notice shall be
# included in all copies or substantial portions of the Software.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
# OTHER DEALINGS IN THE SOFTWARE.


import sys
import os

def getparent(z, x, y):
    if z < 1:
        return None
    return (z-1, x/2, y/2)

def getchildren(z, x, y):
    if z >= MAXZOOM:
        return None
    return [
            (z+1, x*2+1, y*2+1),
            (z+1, x*2+1, y*2  ),
            (z+1, x*2,   y*2+1),
            (z+1, x*2,   y*2  ),
            ]

def expiretile(z, x, y, AndChildren = False):
    if not expired.has_key(z):
        expired[z] = {}
    if not expired[z].has_key((x,y)):
        expired[z][(x,y)] = True

        # Expire the parent, if unexpired
        p = getparent(z, x, y)
        if p != None and (not expired.has_key(p[0]) or not expired[p[0]].has_key((p[1], p[2]))):
            expiretile(p[0], p[1], p[2])

        # Expire each of the children, if unexpired (in case osm2pgsql outputs
        # z17 instead of z18 - possibly this can be ripped out)
        #
        # This is only done for tiles in the expire-file and children
        cs = getchildren(z, x, y)
        if AndChildren and cs != None:
            for c in cs:
                if not expired.has_key(c[0]) or not expired[c[0]].has_key((c[1], c[2])):
                    expiretile(c[0], c[1], c[2], True)


def readexpiredlist(tilelist):
    fh = file(tilelist)
    for line in fh:
        (z, x, y) = line.strip().split("/")
        expiretile(int(z), int(x), int(y), True)

expired = {}
try:
    MAXZOOM = os.environ['MAXZOOM']
except KeyError:
    MAXZOOM = 18

if __name__ == "__main__":
    for tilelist in sys.argv[1:]:
        readexpiredlist(tilelist)
    for z in expired:
        for tile in expired[z]:
            print "%d/%d/%d" % (z, tile[0], tile[1])