Town *AirportGetNearestTownKdTree(const AirportSpec *as, const TileIterator &it)
{
	Town *nearest = NULL;
	if (Town::GetNumItems() == 0) return nearest;

//	uint add = as->size_x + as->size_y - 2; // CalcClosestTownFromTile can differ from DistanceManhattan by this much
	uint mindist = UINT_MAX - 1; // prevent overflow

	TileIterator *copy = it.Clone();
	for (TileIndex cur_tile = *copy; cur_tile != INVALID_TILE; cur_tile = ++*copy) {
		Town *t = CalcClosestTownFromTile(cur_tile, mindist + 1);
		if (t == NULL) continue;

		uint dist = DistanceManhattan(t->xy, cur_tile);
		if (dist == mindist && t->index < nearest->index) nearest = t;
		if (dist < mindist) {
			nearest = t;
			mindist = dist;
		}
	}
	delete copy;

	return nearest;
}

Town *AirportGetNearestTownForAllTowns(const AirportSpec *as, const TileIterator &it)
{
	Town *t, *nearest = NULL;
	uint add = as->size_x + as->size_y - 2; // GetMinimalAirportDistanceToTile can differ from DistanceManhattan by this much
	uint mindist = UINT_MAX - add; // prevent overflow
	FOR_ALL_TOWNS(t) {
		if (DistanceManhattan(t->xy, it) < mindist + add) { // avoid calling GetMinimalAirportDistanceToTile too often
			TileIterator *copy = it.Clone();
			uint dist = GetMinimalAirportDistanceToTile(*copy, t->xy);
			delete copy;
			if (dist < mindist) {
				nearest = t;
				mindist = dist;
			}
		}
	}

	return nearest;
}

/**
 * Finds the town nearest to given airport. Based on minimal manhattan distance to any airport's tile.
 * If two towns have the same distance, town with lower index is returned.
 * @param as airport's description
 * @param it An iterator over all airport tiles
 * @return nearest town to airport
 */
Town *AirportGetNearestTown(const AirportSpec *as, const TileIterator &it)
{
	assert(AirportGetNearestTownForAllTowns(as, it) == AirportGetNearestTownKdTree(as, it));
	return AirportGetNearestTownKdTree(as, it);
}