/*
 * Copyright (C) 2013.
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License version 3 or
 * version 2 as published by the Free Software Foundation.
 *
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 */

package uk.me.parabola.mkgmap.osmstyle.housenumber;

import it.unimi.dsi.fastutil.ints.Int2IntOpenHashMap;
import it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap;
import it.unimi.dsi.fastutil.longs.Long2ObjectOpenHashMap;
import it.unimi.dsi.fastutil.longs.LongArrayList;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.TreeMap;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

import uk.me.parabola.imgfmt.MapFailedException;
import uk.me.parabola.imgfmt.Utils;
import uk.me.parabola.imgfmt.app.Coord;
import uk.me.parabola.imgfmt.app.net.Numbers;
import uk.me.parabola.log.Logger;
import uk.me.parabola.mkgmap.general.CityInfo;
import uk.me.parabola.mkgmap.general.LineAdder;
import uk.me.parabola.mkgmap.general.MapRoad;
import uk.me.parabola.mkgmap.general.ZipCodeInfo;
import uk.me.parabola.mkgmap.reader.osm.Element;
import uk.me.parabola.mkgmap.reader.osm.HousenumberHooks;
import uk.me.parabola.mkgmap.reader.osm.Node;
import uk.me.parabola.mkgmap.reader.osm.POIGeneratorHook;
import uk.me.parabola.mkgmap.reader.osm.Relation;
import uk.me.parabola.mkgmap.reader.osm.TagDict;
import uk.me.parabola.mkgmap.reader.osm.Way;
import uk.me.parabola.util.EnhancedProperties;
import uk.me.parabola.util.KdTree;
import uk.me.parabola.util.Locatable;
import uk.me.parabola.util.MultiHashMap;

/**
 * Collects all data required for OSM house number handling and adds the
 * house number information to the roads.
 * 
 * @author WanMil, Gerd Petermann
 */
public class HousenumberGenerator {
	private static final Logger log = Logger.getLogger(HousenumberGenerator.class);

	/** Gives the maximum distance between house number element and the matching road */
	public static final double MAX_DISTANCE_TO_ROAD = 150d;
	/** Gives the maximum distance for different elements with the same address */
	public static final double MAX_DISTANCE_SAME_NUM = 100d;
	
	private boolean numbersEnabled;

	// options for handling of unnamed (service?) roads	
	private int nameSearchDepth = 3;

	private MultiHashMap<String, HousenumberIvl> interpolationWays;
	private List<MapRoad> allRoads;
	private Map<Long,Integer> interpolationNodes;
	private List<HousenumberElem> houseElems;
	private HashMap<CityInfo, CityInfo> cityInfos = new HashMap<>();
	private HashMap<ZipCodeInfo, ZipCodeInfo> zipInfos = new HashMap<>();

	private static final short housenumberTagKey1 =  TagDict.getInstance().xlate("mkgmap:housenumber");
	private static final short housenumberTagKey2 =  TagDict.getInstance().xlate("addr:housenumber");
	private static final short streetTagKey = TagDict.getInstance().xlate("mkgmap:street");
	private static final short addrStreetTagKey = TagDict.getInstance().xlate("addr:street");
	private static final short addrInterpolationTagKey = TagDict.getInstance().xlate("addr:interpolation");
	private static final short addrPlaceTagKey = TagDict.getInstance().xlate("addr:place");
	private static final short cityTagKey = TagDict.getInstance().xlate("mkgmap:city");
	private static final short regionTagKey = TagDict.getInstance().xlate("mkgmap:region");
	private static final short countryTagKey = TagDict.getInstance().xlate("mkgmap:country");
	private static final short postalCodeTagKey = TagDict.getInstance().xlate("mkgmap:postal_code");
	private static final short numbersTagKey = TagDict.getInstance().xlate("mkgmap:numbers");
	
	public HousenumberGenerator(EnhancedProperties props) {
		this.interpolationWays = new MultiHashMap<>();
		this.allRoads = new ArrayList<>();
		this.interpolationNodes = new HashMap<>();
		this.houseElems = new ArrayList<>();
		
		numbersEnabled = props.containsKey("housenumbers");
		int n = props.getProperty("name-service-roads", 3);
		if (n != nameSearchDepth){
			nameSearchDepth = Math.min(25, Math.max(0, n));
			if (nameSearchDepth != n)
				System.err.println("name-service-roads=" + n + " was changed to name-service-roads=" + nameSearchDepth);
		}
	}

	/**
	 * Retrieves the street name of this element.
	 * @param e an OSM element
	 * @return the street name (or {@code null} if no street name set)
	 */
	private static String getStreetname(Element e) {
		String streetname = e.getTag(streetTagKey);
		if (streetname == null) {
			streetname = e.getTag(addrStreetTagKey);
		}	
		return streetname;
	}
	
	/**
	 * Retrieves the house number of this element.
	 * @param e an OSM element
	 * @return the house number (or {@code null} if no house number set)
	 */
	public static String getHousenumber(Element e) {
		String res = e.getTag(housenumberTagKey1); 
		if (res != null)
			return res;
		return e.getTag(housenumberTagKey2);
	}
	
	/**
	 * Parses the house number string. It accepts the first positive number part
	 * of a string. So all leading and preceding non number parts are ignored.
	 * So the following strings are accepted:
	 * <table>
	 * <tr>
	 * <th>Input</th>
	 * <th>Output</th>
	 * </tr>
	 * <tr>
	 * <td>23</td>
	 * <td>23</td>
	 * </tr>
	 * <tr>
	 * <td>-23</td>
	 * <td>23</td>
	 * </tr>
	 * <tr>
	 * <td>21-23</td>
	 * <td>21</td>
	 * </tr>
	 * <tr>
	 * <td>Abc 21</td>
	 * <td>21</td>
	 * </tr>
	 * <tr>
	 * <td>Abc 21.45</td>
	 * <td>21</td>
	 * </tr>
	 * <tr>
	 * <td>21 Main Street</td>
	 * <td>21</td>
	 * </tr>
	 * <tr>
	 * <td>Main Street</td>
	 * <td><i>IllegalArgumentException</i></td>
	 * </tr>
	 * </table>
	 * @throws IllegalArgumentException if parsing fails
	 */
	private static Integer parseHousenumber(String housenumberString) {
		if (housenumberString == null) {
			return null;
		}
		
		// the housenumber must match against the pattern <anything>number<notnumber><anything>
		int housenumber;
		Pattern p = Pattern.compile("\\D*(\\d+)\\D?.*");
		Matcher m = p.matcher(housenumberString);
		if (m.matches() == false) {
			return null;
		}
		try {
			// get the number part and parse it
			housenumber = Integer.parseInt(m.group(1));
		} catch (NumberFormatException exp) {
			return null;
		}
		return housenumber;
	}

	
	private HousenumberElem parseElement(Element el, String sign){
		String city = el.getTag(cityTagKey);
		String region = el.getTag(regionTagKey);
		String country = el.getTag(countryTagKey);
		CityInfo ci = getCityInfos(city,region,country);
		HousenumberElem house = new HousenumberElem(el, ci);
		if (house.getLocation() == null){
			// there has been a report that indicates match.getLocation() == null
			// could not reproduce so far but catching it here with some additional
			// information. (WanMil)
			log.error("OSM element seems to have no point.");
			log.error("Element: " + el.toBrowseURL() + " " + el);
			log.error("Please report on the mkgmap mailing list.");
			log.error("Continue creating the map. This should be possible without a problem.");
			return null;
		}
		
		house.setSign(sign);
		Integer hn = parseHousenumber(sign);
		if (hn == null){
			if (log.isDebugEnabled())
				log.debug("No housenumber (", el.toBrowseURL(), "): ", sign);
			return null;
		}
		if (hn < 0 || hn > 1_000_000){
			log.warn("Number looks wrong, is ignored",house.getSign(),hn,"element",el.toBrowseURL());
			return null;
		}
		house.setHousenumber(hn);
		house.setStreet(getStreetname(el));
		house.setPlace(el.getTag(addrPlaceTagKey));
		String zipStr = el.getTag(postalCodeTagKey);
		ZipCodeInfo zip = getZipInfos(zipStr);
		house.setZipCode(zip);
		return house;
	}
	
	private CityInfo getCityInfos(String city, String region, String country) {
		CityInfo ci = new CityInfo(city, region, country);
		CityInfo ciOld = cityInfos.get(ci);
		if (ciOld != null)
			return ciOld;
//		log.debug(ci);
		cityInfos.put(ci, ci);
		return ci;
	}

	private ZipCodeInfo getZipInfos(String zipStr) {
		ZipCodeInfo zip = new ZipCodeInfo(zipStr);
		ZipCodeInfo zipOld = zipInfos.get(zip);
		if (zipOld != null)
			return zipOld;
		zipInfos.put(zip, zip);
		return zip;
	}

	private HousenumberElem handleElement(Element el){
		String sign = getHousenumber(el);
		if (sign == null)
			return null;
		
		HousenumberElem he = parseElement(el, sign);
		if (he == null)
			return null;
		houseElems.add(he);
		return he;
	}
	/**
	 * Adds a node for house number processing.
	 * @param n an OSM node
	 */
	public void addNode(Node n) {
		if (numbersEnabled == false) {
			return;
		}
		if("false".equals(n.getTag(numbersTagKey)))
			return;
		
		if ("true".equals(n.getTag(POIGeneratorHook.AREA2POI_TAG))){
			// ignore POI created for buildings
			return; 		
		}
		HousenumberElem houseElem = handleElement(n);
		if (houseElem == null)
			return;
		
		if (n.getTag(HousenumberHooks.partOfInterpolationTagKey) != null)
			interpolationNodes.put(n.getId(),houseElems.size()-1);
	}
	
	/**
	 * Adds a way for house number processing.
	 * @param w a way
	 */
	public void addWay(Way w) {
		if (numbersEnabled == false) {
			return;
		}
		if("false".equals(w.getTag(numbersTagKey)))
			return;
		
		String ai = w.getTag(addrInterpolationTagKey);
		if (ai != null){
			// the way has the addr:interpolation=* tag, parse info
			// created by the HousenumberHook
			List<HousenumberElem> nodes = new ArrayList<>();
			String nodeIds = w.getTag(HousenumberHooks.mkgmapNodeIdsTagKey);
			if (nodeIds == null){
				// way was rejected by hook
			} else {
				String[] ids = nodeIds.split(",");
				for (String idString : ids){
					Long id = Long.decode(idString);
					Integer elemPos = interpolationNodes.get(id);
					if (elemPos != null){
						HousenumberElem node = houseElems.get(elemPos);
						if (node != null){
							assert node.getElement().getId() == id;
							nodes.add(node);
						}
					}
				}
				interpretInterpolationWay(w, nodes);
			}
			return;
		}
		
		if (w.hasIdenticalEndPoints()){
			// we are only interested in polygons now
			handleElement(w);
		}

	}
	
	/**
	 * Use the information provided by the addr:interpolation tag
	 * to generate additional house number elements. This increases
	 * the likelihood that a road segment is associated with the right 
	 * number ranges. 
	 * @param w the way
	 * @param nodes2 
	 * @param nodes list of nodes
	 */
	private void interpretInterpolationWay(Way w, List<HousenumberElem> nodes) {
		int numNodes = nodes.size();
		String addrInterpolationMethod = w.getTag(addrInterpolationTagKey);
		int step = 0;
		switch (addrInterpolationMethod) {
		case "all":
		case "1":
			step = 1;
			break;
		case "even":
		case "odd":
		case "2":
			step = 2;
			break;
		default:
			break;
		}
		if (step == 0)
			return; // should not happen here
		int pos = 0;
		List<HousenumberIvl> hivls = new ArrayList<>();
		String streetName = null;
		for (int i = 0; i+1 < numNodes; i++){
			// the way have other points, find the sequence including the pair of nodes    
			HousenumberElem he1 = nodes.get(i);
			HousenumberElem he2 = nodes.get(i+1);
			int pos1 = -1, pos2 = -1;
			for (int k = pos; k < w.getPoints().size(); k++){
				if (w.getPoints().get(k) == he1.getLocation()){
					pos1 = k;
					break;
				}
			}
			if (pos1 < 0){
				log.error("addr:interpolation node not found in way",w);
				return;
			}
			for (int k = pos1+1; k < w.getPoints().size(); k++){
				if (w.getPoints().get(k) == he2.getLocation()){
					pos2 = k;
					break;
				}
			}
			if (pos2 < 0){
				log.error("addr:interpolation node not found in way",w);
				return;
			}
			pos = pos2;
			String street = he1.getStreet();
			if (street != null && street.equals(he2.getStreet())){
				if (streetName == null)
					streetName = street;
				else if (streetName.equals(street) == false){
					log.warn(w.toBrowseURL(),"addr:interpolation=even is used with different street names",streetName,street);
					return;
				}
				
				int start = he1.getHousenumber();
				int end = he2.getHousenumber();
				HousenumberIvl hivl = new HousenumberIvl(street, w, (Node)he1.element, (Node)he2.element);
				hivl.setStart(start);
				hivl.setEnd(end);
				hivl.setStep(step);
				hivl.calcSteps();
				hivl.setPoints(w.getPoints().subList(pos1, pos2+1));
//				if (pos1 > 0){
//					double angle = Utils.getAngle(w.getPoints().get(pos1-1), w.getPoints().get(pos1), w.getPoints().get(pos1+1));
//					if (Math.abs(angle) > 75){
//						log.warn(w.toBrowseURL(),"addr:interpolation way has sharp angle at number",start,"cannot use it");
//						return;
//					}
//						
//				}
				
				hivls.add(hivl);
				if ("even".equals(addrInterpolationMethod) && (start % 2 != 0 || end % 2 != 0)){
					log.warn(w.toBrowseURL(),"addr:interpolation=even is used with odd housenumber(s)",start,end);
					return;
				}
				if ("odd".equals(addrInterpolationMethod) && (start % 2 == 0 || end % 2 == 0)){
					log.warn(w.toBrowseURL(),"addr:interpolation=odd is used with even housenumber(s)",start,end);
					return;
				}
				
				if (start == end && he1.getSign().equals(he2.getSign())){
					// handle special case from CanVec imports  
					if (pos1 == 0 && pos2 +1 == w.getPoints().size()){
						hivl.setEqualEnds();
						log.warn(w.toBrowseURL(),"addr:interpolation way connects two points with equal numbers, numbers are ignored");
					}
				}
			}
		}
		for (HousenumberIvl  hivl : hivls)
			interpolationWays.add(streetName, hivl);
	}

	private MapRoad firstRoadSameOSMWay = null;
	/**
	 * Adds a road to be processed by the house number generator.
	 * @param osmRoad the OSM way the defines the road 
	 * @param road a road
	 */
	public void addRoad(Way osmRoad, MapRoad road) {
		allRoads.add(road);
		if (numbersEnabled) {
			if("false".equals(osmRoad.getTag(numbersTagKey))) 
				road.setSkipHousenumberProcessing(true);
			
			/*
			 * If the style adds the same OSM way as two or more routable ways, we use
			 * only the first. This ensures that we don't try to assign numbers from bad
			 * matches to these copies.
			 */
			if(!road.isSkipHousenumberProcessing()){
				if (firstRoadSameOSMWay != null){
					if (firstRoadSameOSMWay.getRoadDef().getId() == road.getRoadDef().getId()){
						if (firstRoadSameOSMWay.getPoints().equals(road.getPoints())){
							road.setSkipHousenumberProcessing(true);
							return;
						}
					}
				} 
				firstRoadSameOSMWay = road;
				String name = road.getStreet(); 
				if (name != null) {
					if (log.isDebugEnabled())
						log.debug("Housenumber - Streetname:", name, "Way:",osmRoad.getId(),osmRoad.toTagString());
				}
			}
		} 
	}
	
	/**
	 * Evaluate type=associatedStreet relations.
	 */
	public void addRelation(Relation r) {
		String relType = r.getTag("type");
		// the wiki says that we should also evaluate type=street
		if ("associatedStreet".equals(relType) || "street".equals(relType)){
			List<Element> houses= new ArrayList<>();
			List<Element> streets = new ArrayList<>();
			for (Map.Entry<String, Element> member : r.getElements()) {
				if (member.getValue() instanceof Node) {
					Node node = (Node) member.getValue();
					houses.add(node);
				} else if (member.getValue() instanceof Way) {
					Way w = (Way) member.getValue();
					String role = member.getKey();
					switch (role) {
					case "house":
					case "addr:houselink":
					case "address":
						houses.add(w);
						break;
					case "street":
						streets.add(w);
						break;
					case "":
						if (w.getTag("highway") != null){
							streets.add(w);
							continue;
						}
						String buildingTag = w.getTag("building");
						if (buildingTag != null)
							houses.add(w);
						else 
							log.warn("Relation",r.toBrowseURL(),": role of member",w.toBrowseURL(),"unclear");
						break;
					default:
						if ("associatedStreet".equals(relType)) 
							log.warn("Relation",r.toBrowseURL(),": don't know how to handle member with role",role);
						break;
					}
				}
			}
			String streetName = r.getTag("name");
			String streetNameFromRoads = null;
			List<Element> unnamedStreetElems = new ArrayList<>();
			boolean nameFromStreetsIsUnclear = false;
			if (streets.isEmpty() == false) {
				for (Element street : streets) {
					String roadName = street.getTag(streetTagKey);
					if (roadName == null) 
						roadName = street.getTag("name");
					if (roadName == null){
						unnamedStreetElems.add(street);
						continue;
					}
					if (streetNameFromRoads == null)
						streetNameFromRoads = roadName;
					else if (streetNameFromRoads.equals(roadName) == false)
						nameFromStreetsIsUnclear = true;
				}
			}
			if (streetName == null){
				if (nameFromStreetsIsUnclear == false)
					streetName = streetNameFromRoads;
				else {
					log.warn("Relation",r.toBrowseURL(),": ignored, street name is not clear.");
					return;
				}

			} else {
				if (streetNameFromRoads != null){
					if (nameFromStreetsIsUnclear == false && streetName.equals(streetNameFromRoads) == false){
						if (unnamedStreetElems.isEmpty() == false){
							log.warn("Relation",r.toBrowseURL(),": ignored, street name is not clear.");
							return;
						}
						log.warn("Relation",r.toBrowseURL(),": street name is not clear, using the name from the way, not that of the relation.");
						streetName = streetNameFromRoads;
					} 
					else if (nameFromStreetsIsUnclear == true){
						log.warn("Relation",r.toBrowseURL(),": street name is not clear, using the name from the relation.");
					}
				} 
			}
			int countModHouses = 0;
			if (streetName != null && streetName.isEmpty() == false){
				for (Element house : houses) {
					if (addStreetTagFromRel(r, house, streetName) )
						countModHouses++;
				}
				for (Element street : unnamedStreetElems) {
					street.addTag(streetTagKey, streetName);
					street.addTag("name", streetName);
				}
			}
			if (log.isInfoEnabled()){
				if (countModHouses > 0 || !unnamedStreetElems.isEmpty()){
					if (countModHouses > 0)
						log.info("Relation",r.toBrowseURL(),": added tag mkgmap:street=",streetName,"to",countModHouses,"of",houses.size(),"house members" );
					if (!unnamedStreetElems.isEmpty())
						log.info("Relation",r.toBrowseURL(),": added tag mkgmap:street=",streetName,"to",unnamedStreetElems.size(),"of",streets.size(),"street members" );
				}
				else 
					log.info("Relation",r.toBrowseURL(),": ignored, no house or street member was changed");
			}

		}
	}
	
	/**
	 * Add the tag mkgmap:street=streetName to the element of the 
	 * relation if it does not already have a street name tag.
	 */
	private static boolean addStreetTagFromRel(Relation r, Element house, String streetName){
		String addrStreet = getStreetname(house);
		if (addrStreet == null){
			house.addTag(streetTagKey, streetName);
			if (log.isDebugEnabled())
				log.debug("Relation",r.toBrowseURL(),": adding tag mkgmap:street=" + streetName, "to house",house.toBrowseURL());
			return true;
		}
		else if (addrStreet.equals(streetName) == false){
			if (house.getTag(streetTagKey) != null){
				log.warn("Relation",r.toBrowseURL(),": street name from relation doesn't match existing mkgmap:street tag for house",house.toBrowseURL(),"the house seems to be member of another type=associatedStreet relation");
				house.deleteTag(streetTagKey);
			}
			else 
				log.warn("Relation",r.toBrowseURL(),": street name from relation doesn't match existing name for house",house.toBrowseURL());
		}
		return false;
	}
	
	
	/**
	 * 
	 * @param adder
	 * @param naxNodeId the highest nodeId used before
	 */
	public void generate(LineAdder adder, int naxNodeId) {
		if (numbersEnabled) {
			MultiHashMap<MapRoad,HousenumberMatch> initialHousesForRoads = findClosestRoadsToHouse();
			identifyServiceRoads();
			
			handleInterpolationWays(initialHousesForRoads);
			
			List<HousenumberRoad> hnrList = createHousenumberRoads(initialHousesForRoads);
			initialHousesForRoads = null;
			log.info("found",hnrList.size(),"road candidates for address search");
			
			useAddrPlaceTag(hnrList);
			Map<MapRoad, HousenumberRoad> road2HousenumberRoadMap = new HashMap<>();
			for (HousenumberRoad hnr : hnrList){
				road2HousenumberRoadMap.put(hnr.getRoad(), hnr);
			}
			Int2ObjectOpenHashMap<HashSet<MapRoad>> nodeId2RoadLists = new Int2ObjectOpenHashMap<>();
			for (MapRoad road : allRoads){
				for (Coord co : road.getPoints()){
					if (co.getId() == 0)
						continue;
					HashSet<MapRoad> connectedRoads = nodeId2RoadLists.get(co.getId());
					if (connectedRoads == null){
						connectedRoads = new HashSet<>();
						nodeId2RoadLists.put(co.getId(), connectedRoads);
					}
					connectedRoads.add(road);
				}
			}
			List<HousenumberRoad> addedRoads = new ArrayList<>();
			Iterator<HousenumberRoad> iter = hnrList.iterator();
			while (iter.hasNext()){
				HousenumberRoad hnr = iter.next();
				
				List<HousenumberMatch> lostHouses = hnr.checkStreetName(road2HousenumberRoadMap, nodeId2RoadLists);
				for (HousenumberMatch house : lostHouses){
					MapRoad r = house.getRoad();
					if (r != null){
						HousenumberRoad hnr2 = road2HousenumberRoadMap.get(r);
						if (hnr2 == null){
							CityInfo ci = getCityInfos(r.getCity(), r.getRegion(), r.getCountry());
							hnr2 = new HousenumberRoad(r, ci, Arrays.asList(house));
							if (r.getZip() != null)
								hnr2.setZipCodeInfo(getZipInfos(r.getZip()));
							road2HousenumberRoadMap.put(r,hnr2);
							addedRoads.add(hnr2);
						} else {
							hnr2.addHouse(house);
						}
					}
				}
				if (hnr.getName() == null){
					iter.remove();
					for (HousenumberMatch house : hnr.getHouses()){
						log.warn("found no plausible road name for address",house.toBrowseURL(),", closest road id:",house.getRoad());
					}
				}
			}
			hnrList.addAll(addedRoads);
			// TODO: interpolate addr:interpolation houses
			removeDupsGroupedByCityAndName(hnrList);
			
			// group by street name and city
			TreeMap<String, TreeMap<CityInfo, List<HousenumberRoad>>> streetnameCityRoadMap = new TreeMap<>();
			for (HousenumberRoad hnr : hnrList){
				TreeMap<CityInfo, List<HousenumberRoad>> cluster = streetnameCityRoadMap.get(hnr.getName());
				if (cluster == null){
					cluster = new TreeMap<>();
					streetnameCityRoadMap.put(hnr.getName(), cluster);
				}
				List<HousenumberRoad> roadsInCluster = cluster.get(hnr.getRoadCityInfo());
				if (roadsInCluster == null){
					roadsInCluster = new ArrayList<>();
					cluster.put(hnr.getRoadCityInfo(), roadsInCluster);
				}
				roadsInCluster.add(hnr);
			}
			
			for (Entry<String, TreeMap<CityInfo, List<HousenumberRoad>>> streetNameEntry : streetnameCityRoadMap.entrySet()){
				String streetName = streetNameEntry.getKey();
				
				for (Entry<CityInfo, List<HousenumberRoad>> clusterEntry : streetNameEntry.getValue().entrySet()){
					useInterpolationInfo(streetName, clusterEntry.getValue(), road2HousenumberRoadMap);
				}
				
				for (Entry<CityInfo, List<HousenumberRoad>> clusterEntry : streetNameEntry.getValue().entrySet()){
					List<HousenumberRoad> roadsInCluster = clusterEntry.getValue();
					if (log.isDebugEnabled()){
						log.debug("processing road(s) with name",streetName,"in",clusterEntry.getKey() );
					}
					for (HousenumberRoad hnr : roadsInCluster){
						hnr.buildIntervals();
					}
					boolean optimized = false;
					for (int loop = 0; loop < 10; loop++){
						for (HousenumberRoad hnr : roadsInCluster){
							hnr.checkIntervals();
						}
						checkWrongRoadAssignmments(roadsInCluster);
						boolean changed = hasChanges(roadsInCluster);
						if (!optimized && !changed){
							for (HousenumberRoad hnr : roadsInCluster){
								hnr.improveSearchResults();
							}
							changed = hasChanges(roadsInCluster);
							optimized = true;
						}
						if (!changed)
							break;
					}
					for (HousenumberRoad hnr : roadsInCluster){
						hnr.setNumbers();
					}
				}
			}
		}
			
		if (log.isInfoEnabled()){
			for (HousenumberElem house : houseElems){
				if (house.getRoad() == null){
					if (house.getStreet() != null)
						log.info("found no plausible road for house number element",house.toBrowseURL(),house.getStreet(),house.getSign());
					else 
						log.info("found no plausible road for house number element",house.toBrowseURL());
				}
			}
		}
		for (MapRoad r : allRoads) {
			if (log.isDebugEnabled()){
				List<Numbers> finalNumbers = r.getRoadDef().getNumbersList();
				if (finalNumbers != null){
					log.info("id:"+r.getRoadDef().getId(),", final numbers,",r,"in",r.getCity());
					for (Numbers cn : finalNumbers){
						if (cn.isEmpty())
							continue;
						log.info("id:"+r.getRoadDef().getId(),", Left: ",cn.getLeftNumberStyle(),cn.getIndex(),"Start:",cn.getLeftStart(),"End:",cn.getLeftEnd());
						log.info("id:"+r.getRoadDef().getId(),", Right:",cn.getRightNumberStyle(),cn.getIndex(),"Start:",cn.getRightStart(),"End:",cn.getRightEnd());
					}
				}
			}
			adder.add(r);
		}
	}
	
	private List<HousenumberRoad> createHousenumberRoads(
			MultiHashMap<MapRoad, HousenumberMatch> initialHousesForRoads) {
		List<HousenumberRoad> hnrList = new ArrayList<>();
		for (MapRoad road : allRoads){
			if (road.isSkipHousenumberProcessing())
				continue;
			List<HousenumberMatch> houses = initialHousesForRoads.get(road);
			if (houses == null || houses.isEmpty())
				continue;
			CityInfo ci = getCityInfos(road.getCity(), road.getRegion(), road.getCountry());
			HousenumberRoad hnr = new HousenumberRoad(road, ci, houses);
			if (road.getZip() != null)
				hnr.setZipCodeInfo(getZipInfos(road.getZip()));
				
			hnrList.add(hnr);
		}
		return hnrList;
	}

	private MultiHashMap<MapRoad, HousenumberMatch> findClosestRoadsToHouse() {
		// build road index
		long t1 = System.currentTimeMillis();
		RoadSegmentIndex roadSegmentIndex = new RoadSegmentIndex(allRoads, MAX_DISTANCE_TO_ROAD);
		long t2 = System.currentTimeMillis();
		log.debug("creation of road index took",t2-t1,"ms");
		
		long t3 = System.currentTimeMillis();
		MultiHashMap<MapRoad,HousenumberMatch> initialHousesForRoads = new MultiHashMap<>();
		for (int i = 0; i < houseElems.size(); i++){
			HousenumberElem house = houseElems.get(i);
			HousenumberMatch bestMatch = roadSegmentIndex.createHousenumberMatch(house);
			houseElems.set(i, bestMatch);
			if (bestMatch.getRoad() == null){
				bestMatch.setIgnored(true); // XXX maybe create a pseudo road with zero length?
//				log.warn("found no plausible road for house number element",house.getElement().toBrowseURL());
				continue;
			}
			initialHousesForRoads.add(bestMatch.getRoad(), bestMatch);
		}
		long t4 = System.currentTimeMillis();
		log.debug("identification of closest road for each house took",t4-t3,"ms");
		
		return initialHousesForRoads;
	}

	private void useAddrPlaceTag(List<HousenumberRoad> hnrList){
		HashMap<CityInfo,MultiHashMap<String,HousenumberMatch>> cityPlaceHouseMap = new LinkedHashMap<>();
		for (int i = 0; i < houseElems.size(); i++){
			HousenumberElem house = houseElems.get(i);
			if (house.getRoad() == null)
				continue;
			if (house.getPlace() == null)
				continue;
			if (house instanceof HousenumberMatch){
				HousenumberMatch hm = (HousenumberMatch) house;
				if (hm.getHousenumberRoad() == null)
					continue;
			} else 
				continue;
			MultiHashMap<String, HousenumberMatch> subMap = cityPlaceHouseMap.get(house.getCityInfo());
			if (subMap == null){
				subMap = new MultiHashMap<>();
				cityPlaceHouseMap.put(house.getCityInfo(), subMap);
			}
			subMap.add(house.getPlace(), (HousenumberMatch) house);
		}
		log.info("analysing",cityPlaceHouseMap.size(),"cities with addr:place=* houses" );
		for (Entry<CityInfo, MultiHashMap<String, HousenumberMatch>> topEntry : cityPlaceHouseMap.entrySet()){
			CityInfo cityInfo = topEntry.getKey();
			List<String> placeNames = new ArrayList<>(topEntry.getValue().keySet());
			Collections.sort(placeNames);
			for (String placeName : placeNames){
				List<HousenumberMatch> placeHouses = topEntry.getValue().get(placeName);
				HashSet<HousenumberRoad> roads = new LinkedHashSet<>();
				Int2IntOpenHashMap usedNumbers = new Int2IntOpenHashMap();
				HashMap<String,Integer> usedSigns = new HashMap<>();
				int dupSigns = 0;
				int dupNumbers = 0;
				int housesWithStreet = 0;
				int housesWithMatchingStreet = 0;
				int roadsWithNames = 0;
				int unnamedCloseRoads = 0;
				
				for (HousenumberMatch house : placeHouses){
					if (house.getStreet() != null ){
						++housesWithStreet;
						if (house.getStreet().equalsIgnoreCase(house.getRoad().getStreet())){
							++housesWithMatchingStreet;
						}
					} else {
						if (house.getRoad().getStreet() == null)
							++unnamedCloseRoads;
					}
					boolean added = roads.add(house.getHousenumberRoad());
					if (added && house.getRoad().getStreet() != null)
						++roadsWithNames;
					int oldCount = usedNumbers.put(house.getHousenumber(),1);
					if (oldCount != 0){
						usedNumbers.put(house.getHousenumber(), oldCount + 1);
						++dupNumbers;
					}
					Integer oldSignCount = usedSigns.put(house.getSign(), 1);
					if (oldSignCount != null){
						usedSigns.put(house.getSign(), oldSignCount + 1);
						++dupSigns;
					}
				}
				
				if (log.isDebugEnabled()){
					log.debug("place",placeName,"in city",cityInfo, ":", "houses:", placeHouses.size(),
							",duplicate numbers/signs:", dupNumbers+"/"+dupSigns,
							",roads (named/unnamed):", roads.size(),"("+roadsWithNames+"/"+(roads.size()- roadsWithNames)+")",
							",houses without addr:street:", placeHouses.size() - housesWithStreet,
							",street = name of closest road:", housesWithMatchingStreet,
							",houses without addr:street near named road:",	unnamedCloseRoads);
				}
				if ((float) dupSigns / placeHouses.size() < 0.25 ){
					if (log.isDebugEnabled())
						log.debug("will not use gaps in intervals for roads in",placeName );
					for (HousenumberRoad hnr : roads){
						hnr.setRemoveGaps(true);
					}
				}
				if (placeHouses.size() > housesWithStreet){ // XXX: threshold value?
					LongArrayList ids = new LongArrayList();
					for (HousenumberRoad hnr : roads){
						ids.add(hnr.getRoad().getRoadDef().getId());
						hnr.addPlaceName(placeName);
					}
					if (log.isDebugEnabled())
						log.debug("detected",placeName,"as potential address name for roads",ids);
				} else {
					if (log.isDebugEnabled())
						log.debug("will ignore addr:place for address search in",placeName,"in city",cityInfo);
				}
			}
		}
	}

	/**
	 * Update the house number information in the interpolation intervals and 
	 * use them to correct wrong road assignments.
	 * @param initialHousesForRoads map that is updated when wrong road assignments were found
	 */
	private void handleInterpolationWays(MultiHashMap<MapRoad, HousenumberMatch> initialHousesForRoads) {
		for (Entry<String, List<HousenumberIvl>> entry : interpolationWays.entrySet()){
			List<HousenumberIvl> infos = entry.getValue();
			for (HousenumberIvl info : infos){
				if (info.isBad()){
					continue;
				}
				boolean isOK = info.setNodeRefs(interpolationNodes, houseElems);
				if (!isOK)
					continue;
				HousenumberMatch[] houses = info.getHouseNodes();
				MapRoad uncheckedRoads[] = new MapRoad[houses.length];
				for (int i = 0 ; i < houses.length; i++)
					uncheckedRoads[i] = houses[i].getRoad();
				isOK = info.checkRoads();
				// check if houses are assigned to different roads now
				houses = info.getHouseNodes();
				for (int i = 0 ; i < houses.length; i++){
					if (houses[i].getRoad() != uncheckedRoads[i]){
						initialHousesForRoads.removeMapping(uncheckedRoads[i], houses[i]);
						if (houses[i].isIgnored() == false)
							initialHousesForRoads.add(houses[i].getRoad(), houses[i]);
						else {
							if (!isOK)
								log.info("housenumber is assigned to different road after checking addr:interpolation way which turned out to be invalid",houses[i],info );
						}
					}
				}
			}
		}
	}

	private void removeDupsGroupedByCityAndName(List<HousenumberRoad> hnrList){
		HashMap<CityInfo,MultiHashMap<String,HousenumberMatch>> cityNameHouseMap = new LinkedHashMap<>();
		for (int i = 0; i < houseElems.size(); i++){
			HousenumberElem house = houseElems.get(i);
			if (house.getRoad() == null)
				continue;
			if (house instanceof HousenumberMatch){
				HousenumberMatch hm = (HousenumberMatch) house;
				if (hm.isIgnored())
					continue;
				HousenumberRoad hnr = hm.getHousenumberRoad();
				if (hnr == null || hnr.getName() == null)
					continue;
				MultiHashMap<String, HousenumberMatch> subMap = cityNameHouseMap.get(hm.getCityInfo());
				if (subMap == null){
					subMap = new MultiHashMap<>();
					cityNameHouseMap.put(hm.getCityInfo(), subMap);
				}
				subMap.add(hnr.getName(), hm);
			}
		}
		
		for (Entry<CityInfo, MultiHashMap<String, HousenumberMatch>> topEntry : cityNameHouseMap.entrySet()){
			for (Entry<String, List<HousenumberMatch>> entry : topEntry.getValue().entrySet()){
				markSimpleDuplicates(entry.getKey(), entry.getValue());
			}
			
		}
	}	
	
	/**
	 * process option --x-name-service-roads=n
	 * The program identifies unnamed roads which are only connected to one
	 * road with a name or to multiple roads with the same name. The process is
	 * repeated n times. If n > 1 the program will also use unnamed roads which
	 * are connected to unnamed roads if those are connected to named roads.
	 * Higher values for n mean deeper search, but reasonable values are
	 * probably between 1 and 5.
	 * 
	 * These roads are then used for house number processing like the named
	 * ones. If house numbers are assigned to these roads, they are named so
	 * that address search will find them.
	 */
	private void identifyServiceRoads() {
		Int2ObjectOpenHashMap<String> roadNamesByNodeIds = new Int2ObjectOpenHashMap<>();
		HashMap<MapRoad, List<Coord>> coordNodesUnnamedRoads = new HashMap<>();
		HashSet<Integer> unclearNodeIds = new HashSet<>();

		long t1 = System.currentTimeMillis();

		List<MapRoad> unnamedRoads = new ArrayList<>();
		for (MapRoad road : allRoads){
			if (road.isSkipHousenumberProcessing())
				continue;
			
			if (road.getStreet() == null){
				// if a road has a label but getStreet() returns null,
				// the road probably has a ref. We assume these are not service roads. 
				if (road.getName() == null){
					unnamedRoads.add(road);
					List<Coord> nodes = new ArrayList<>();
					for (Coord co : road.getPoints()){
						if (co.getId() != 0)
							nodes.add(co);
					}
					coordNodesUnnamedRoads.put(road, nodes);
				}
			} else {
				identifyNodes(road.getPoints(), road.getStreet(), roadNamesByNodeIds, unclearNodeIds);
			}
		}
		int numUnnamedRoads = unnamedRoads.size();
		long t2 = System.currentTimeMillis();
		if (log.isDebugEnabled())
			log.debug("identifyServiceRoad step 1 took",(t2-t1),"ms, found",roadNamesByNodeIds.size(),"nodes to check and",numUnnamedRoads,"unnamed roads" );
		long t3 = System.currentTimeMillis();
		int named = 0;
		for (int pass = 1; pass <= nameSearchDepth; pass ++){
			int unnamed = 0;
			List<MapRoad> namedRoads = new ArrayList<>();
			for (int j = 0; j < unnamedRoads.size(); j++){
				MapRoad road = unnamedRoads.get(j);
				if (road == null)
					continue;
				unnamed++;
				List<Coord> coordNodes = coordNodesUnnamedRoads.get(road); 
				String name = null;
				for (Coord co : coordNodes){
					if (unclearNodeIds.contains(co.getId())){
						name = null;
						unnamedRoads.set(j, null); // don't process again
						break;
					}
					String possibleName = roadNamesByNodeIds.get(co.getId());
					if (possibleName == null)
						continue;
					if (name == null)
						name = possibleName;
					else if (name.equals(possibleName) == false){
						name = null;
						unnamedRoads.set(j, null); // don't process again
						break;
					}
				}
				if (name != null){
					named++;
					road.setStreet(name);
					namedRoads.add(road);
					unnamedRoads.set(j, null); // don't process again
				}
			}
			for (MapRoad road : namedRoads){
				road.setNamedByHousenumberProcessing(true);
				String name = road.getStreet();
				if (log.isDebugEnabled())
					log.debug("pass",pass,"using unnamed road for housenumber processing,id=",road.getRoadDef().getId(),":",name);
				List<Coord> coordNodes = coordNodesUnnamedRoads.get(road); 
				identifyNodes(coordNodes, name, roadNamesByNodeIds, unclearNodeIds);
			}

			if (namedRoads.isEmpty())
				break;
			if (log.isDebugEnabled())
				log.debug("pass",pass,unnamed,named);
		}
		long t4 = System.currentTimeMillis();
		if (log.isDebugEnabled()){
			log.debug("indentifyServiceRoad step 2 took",(t4-t3),"ms, found a name for",named,"of",numUnnamedRoads,"roads" );
		}
		return;
	}

	private void identifyNodes(List<Coord> roadPoints,
			String streetName, Int2ObjectOpenHashMap<String> roadNamesByNodeIds, HashSet<Integer> unclearNodes) {
		for (Coord co : roadPoints){
			if (co.getId() != 0){
				String prevName = roadNamesByNodeIds.put(co.getId(), streetName);
				if (prevName != null){
					if (prevName.equals(streetName) == false)
						unclearNodes.add(co.getId());
				}
			}
		}			
	}


	/**
	 * Find house number nodes which are parts of addr:interpolation ways.
	 *  Check each addr:interpolation way for plausibility. 
	 *  If the check is OK, interpolate the numbers, if not, ignore 
	 *  also the numbers connected to the implausible way.
	 *  
	 *  XXX: Known problem: Doesn't work well when the road was
	 *  clipped at the tile boundary.
	 * @param streetName
	 * @param roadsInCluster
	 * @param road2HousenumberRoadMap 
	 * @param interpolationInfos 
	 */
	private void useInterpolationInfo(String streetName,
			List<HousenumberRoad> roadsInCluster, Map<MapRoad, HousenumberRoad> road2HousenumberRoadMap) {
		List<HousenumberIvl> interpolationInfos = interpolationWays.get(streetName);
		if (interpolationInfos.isEmpty())
			return;
		List<HousenumberMatch> housesWithIvlInfo = new ArrayList<>();
		for (HousenumberRoad hnr : roadsInCluster){
			for (HousenumberMatch house : hnr.getHouses()){
				if (house.getIntervalInfoRefs() > 0)
					housesWithIvlInfo.add(house);
			}
		}
		if (housesWithIvlInfo.isEmpty())
			return;
		
		HashMap<String, HousenumberIvl> simpleDupCheckSet = new HashMap<>();
		HashSet<HousenumberIvl> badIvls = new HashSet<>();
		Long2ObjectOpenHashMap<HousenumberIvl> id2IvlMap = new Long2ObjectOpenHashMap<>();
		Int2ObjectOpenHashMap<HousenumberMatch> interpolatedNumbers = new Int2ObjectOpenHashMap<>();
		Int2ObjectOpenHashMap<HousenumberMatch> existingNumbers = new Int2ObjectOpenHashMap<>();
		HashMap<HousenumberIvl, List<HousenumberMatch>> housesToAdd = new LinkedHashMap<>();
		
		for (HousenumberRoad hnr : roadsInCluster){
			for (HousenumberMatch house : hnr.getHouses())
				existingNumbers.put(house.getHousenumber(), house);
		}
		int inCluster = 0;
		boolean allOK = true;
		// for loop may change the list 
		for (int i = 0; i < interpolationInfos.size(); i++){
			HousenumberIvl hivl = interpolationInfos.get(i);
			if (hivl.inCluster(housesWithIvlInfo) == false || hivl.ignoreForInterpolation())
				continue;
			++inCluster;
			String hivlDesc = hivl.getDesc();
			HousenumberIvl hivlTest = simpleDupCheckSet.get(hivlDesc);
			if (hivlTest != null){
				// happens often in Canada (CanVec imports): two or more addr:interpolation ways with similar meaning
				// sometimes at completely different road parts, sometimes at exactly the same
				log.warn("found additional addr:interpolation way with same meaning, is ignored:",streetName, hivl, hivlTest);
				badIvls.add(hivl);
				allOK = false;
				continue;
			}
			simpleDupCheckSet.put(hivlDesc, hivl);

			id2IvlMap.put(hivl.getId(), hivl);
			List<HousenumberMatch> interpolatedHouses = hivl.getInterpolatedHouses();
			if (interpolatedHouses.isEmpty() == false){
				if (interpolatedHouses.get(0).getRoad() == null){
					// the interpolated houses are not all along one road
					findRoadForInterpolatedHouses(streetName, interpolatedHouses, roadsInCluster);
				}
				
				int dupCount = 0;
				for (HousenumberMatch house : interpolatedHouses){
					if (house.getRoad() == null || house.getDistance() > HousenumberIvl.MAX_INTERPOLATION_DISTANCE_TO_ROAD)
						continue;
					boolean ignoreGenOnly = false;
					HousenumberMatch old = interpolatedNumbers.get(house.getHousenumber());
					if (old == null){
						ignoreGenOnly = true;
						old = existingNumbers.get(house.getHousenumber());
					}
					if (old != null){
						// try to build new intervals using existing node
						HousenumberIvl[] splitIvls = hivl.trySplitAt(old);
						if (splitIvls != null){
							log.info("adding address",streetName,old,old.toBrowseURL(),"to addr:interpolation way, replacing", hivl,"by",Arrays.deepToString(splitIvls));
							interpolationInfos.add(splitIvls[0]);
							interpolationInfos.add(splitIvls[1]);
							hivl.setIgnoreForInterpolation(true);
							break;
						}
						// forget both or only one ? Which one?
						house.setIgnored(true);
						double distToOld = old.getLocation().distance(house.getLocation()); 
						if (distToOld > MAX_DISTANCE_SAME_NUM){
							if (old.isInterpolated())
								log.info("conflict caused by addr:interpolation way",streetName,hivl,"and interpolated address",old,"at",old.getLocation().toDegreeString());
							else 
								log.info("conflict caused by addr:interpolation way",streetName,hivl,"and address element",old,"at",old.getLocation().toDegreeString());
							dupCount++;
							if (!ignoreGenOnly){
								old.setIgnored(true);
								long ivlId = old.getElement().getOriginalId();
								HousenumberIvl bad = id2IvlMap.get(ivlId);
								if (bad != null)
									badIvls.add(bad);
							}
						}
					}
				}
				if (hivl.ignoreForInterpolation())
					continue;
				if (dupCount > 0){
					log.warn("addr:interpolation way",streetName,hivl,"is ignored, it produces",dupCount,"duplicate number(s) too far from existing nodes");
					badIvls.add(hivl);
				}
				else {
					housesToAdd.put(hivl, interpolatedHouses);
					for (HousenumberMatch hnm : interpolatedHouses)
						interpolatedNumbers.put(hnm.getHousenumber(), hnm);
				}
			}
		}
		if (inCluster == 0)
			return;
		for (HousenumberIvl badIvl: badIvls){
			allOK = false;
			badIvl.ignoreNodes();
			housesToAdd.remove(badIvl);
		}
		Iterator<Entry<HousenumberIvl, List<HousenumberMatch>>> iter = housesToAdd.entrySet().iterator();
		while (iter.hasNext()){
			Entry<HousenumberIvl, List<HousenumberMatch>> entry = iter.next();
			if (log.isInfoEnabled())
				log.info("using generated house numbers from addr:interpolation way",entry.getKey());
			for (HousenumberMatch house : entry.getValue()){
				if (house.getRoad() != null && house.isIgnored() == false){
					HousenumberRoad hnr = road2HousenumberRoadMap.get(house.getRoad());
					if (hnr == null){
						log.error("internal error: found no housenumber road for interpolated house",house.toBrowseURL());
						continue;
					}
					hnr.addHouse(house);
				}
			}
		}
		if (log.isDebugEnabled()){
			if (allOK)
				log.debug("found no problems with interpolated numbers from addr:interpolations ways for roads with name",streetName);
			else 
				log.debug("found problems with interpolated numbers from addr:interpolations ways for roads with name",streetName);
		}
	}
	
	private static void findRoadForInterpolatedHouses(String streetName,
			List<HousenumberMatch> houses,
			List<HousenumberRoad> roadsInCluster) {
		if (houses.isEmpty())
			return;
		Collections.sort(houses, new HousenumberMatchByNumComparator());
		
		HousenumberMatch prev = null;
		for (HousenumberMatch house : houses) {
			if (house.isIgnored())
				continue;
			house.setDistance(Double.POSITIVE_INFINITY); // make sure that we don't use an old match
			house.setRoad(null);
			List<HousenumberMatch> matches = new ArrayList<>();
			for (HousenumberRoad hnr : roadsInCluster){
				MapRoad r = hnr.getRoad();
				// make sure that we use the street info if available
				if (house.getPlace() != null){
					if (house.getStreet() != null && r.getStreet() != null && house.getStreet().equals(r.getStreet()) == false)
						continue;
				}
				HousenumberMatch test = new HousenumberMatch(house);
				findClosestRoadSegment(test, r);
				if (test.getRoad() != null && test.getGroup() != null || test.getDistance() < MAX_DISTANCE_TO_ROAD){
					matches.add(test);
				}
			}
			if (matches.isEmpty()){
				house.setIgnored(true);
				continue;
			}
			
			
			HousenumberMatch closest, best; 
			best = closest  = matches.get(0);
			
			if (matches.size() > 1){
				// multiple roads, we assume that the closest is the best
				// but we may have to check the alternatives as well
				
				Collections.sort(matches, new HousenumberGenerator.HousenumberMatchByDistComparator());
				closest  = matches.get(0);
				best = checkAngle(closest, matches);	
			}
			house.setDistance(best.getDistance());
			house.setSegmentFrac(best.getSegmentFrac());
			house.setRoad(best.getRoad());
			house.setSegment(best.getSegment());
			for (HousenumberMatch altHouse : matches){
				if (altHouse.getRoad() != best.getRoad() && altHouse.getDistance() < MAX_DISTANCE_TO_ROAD)
					house.addAlternativeRoad(altHouse.getRoad());
			}
				
			if (house.getRoad() == null) {
				house.setIgnored(true);
			} else {
				house.calcRoadSide();
			}
			// plausibility check for duplicate house numbers
			if (prev != null && prev.getHousenumber() == house.getHousenumber()){
				// duplicate number (e.g. 10 and 10 or 10 and 10A or 10A and 10B)
				if (prev.getSign().equals(house.getSign())){
					prev.setDuplicate(true);
					house.setDuplicate(true);
				}
			}
			
			if (house.getRoad() == null) {
				if (house.isIgnored() == false)
					log.warn("found no plausible road for house number element",house.toBrowseURL(),"(",streetName,house.getSign(),")");
			}
			if (!house.isIgnored())
				prev = house;
		}
	}

	
	private static void markSimpleDuplicates(String streetName, List<HousenumberMatch> housesNearCluster) {
		List<HousenumberMatch> sortedHouses = new ArrayList<>(housesNearCluster);
		Collections.sort(sortedHouses, new HousenumberMatchByNumComparator());
		int n = sortedHouses.size();
		for (int i = 1; i < n; i++){
			HousenumberMatch house1 = sortedHouses.get(i-1);
			if (house1.isIgnored())
				continue;
			HousenumberMatch house2 = sortedHouses.get(i);
			if (house2.isIgnored())
				continue;
			if (house1.getHousenumber() != house2.getHousenumber())
				continue;
			if (house1.getRoad() == house2.getRoad()){
				if (house1.isFarDuplicate())
					house2.setFarDuplicate(true);
				continue; // handled later
			}
			// we have two equal house numbers in different roads
			// check if they should be treated alike
			boolean markFarDup = false;
			double dist = house1.getLocation().distance(house2.getLocation());
			if (dist > MAX_DISTANCE_SAME_NUM)
				markFarDup = true;
			else {
				CityInfo city1 = house1.getCityInfo();
				CityInfo city2 = house2.getCityInfo();
				if (city1 != null && city1.equals(city2) == false){
					markFarDup = true;
				}
			}
			if (markFarDup){
				if (log.isDebugEnabled())
					log.debug("keeping duplicate numbers assigned to different roads in cluster ", streetName, house1,house2);
				house1.setFarDuplicate(true);
				house2.setFarDuplicate(true);
				continue;
			}
			boolean ignore2nd = false;
			if (dist < 30){
				ignore2nd = true;
			} else {
				Coord c1s = house1.getRoad().getPoints().get(house1.getSegment());
				Coord c1e = house1.getRoad().getPoints().get(house1.getSegment() + 1);
				Coord c2s = house2.getRoad().getPoints().get(house2.getSegment());
				Coord c2e = house2.getRoad().getPoints().get(house2.getSegment() + 1);
				if (c1s == c2s || c1s == c2e || c1e == c2s || c1e == c2e){
					// roads are directly connected
					ignore2nd = true;
				} 
			}
			if (ignore2nd){
				house2.setIgnored(true);
				if (log.isDebugEnabled()){
					if (house1.getSign().equals(house2.getSign()))
						log.debug("duplicate number is ignored",streetName,house2.getSign(),house2.toBrowseURL() );
					else 
						log.info("using",streetName,house1.getSign(), "in favor of",house2.getSign(),"as target for address search");
				}
			} else {
				if (log.isDebugEnabled())
					log.debug("keeping duplicate numbers assigned to different roads in cluster ", streetName, house1,house2);
				house1.setFarDuplicate(true);
				house2.setFarDuplicate(true);
			}
		}
	}


	public static void findClosestRoadSegment(HousenumberMatch house, MapRoad r) {
		findClosestRoadSegment(house, r, 0, r.getPoints().size());
	}
	
	/**
	 * Fill/overwrite the fields in house which depend on the assigned road.  
	 */
	public static void findClosestRoadSegment(HousenumberMatch house, MapRoad r, int firstSeg, int stopSeg) {
		Coord cx = house.getLocation();
		double oldDist = house.getDistance();
		MapRoad oldRoad = house.getRoad();
		house.setRoad(null);
		house.setDistance(Double.POSITIVE_INFINITY);
		boolean foundGroupLink = false;
		int end = Math.min(r.getPoints().size(), stopSeg+1);
		for (int node = firstSeg; node + 1 < end; node++){
			Coord c1 = r.getPoints().get(node);
			Coord c2 = r.getPoints().get(node + 1);
			double frac = getFrac(c1, c2, cx);
			double dist = distanceToSegment(c1,c2,cx,frac);
			if (house.getGroup() != null && house.getGroup().linkNode == c1){
				if (c1.highPrecEquals(c2) == false){
					log.debug("block doesn't have zero length segment! Road:",r,house);
				}
				foundGroupLink = true;
				house.setDistance(dist);
				house.setSegmentFrac(frac);
				house.setRoad(r);
				house.setSegment(node);
				break;
			} else if (dist < house.getDistance()) {
				house.setDistance(dist);
				house.setSegmentFrac(frac);
				house.setRoad(r);
				house.setSegment(node);
			} 
		}
		
		if (house.getGroup() != null && house.getGroup().linkNode != null && foundGroupLink == false){
			log.debug(r,house,"has a group but the link was not found, should only happen after split of zero-length-segment");
		}
		if (oldRoad == r){
			if (house.getDistance() > MAX_DISTANCE_TO_ROAD + 2.5 && oldDist <= MAX_DISTANCE_TO_ROAD ){
				log.warn("line distorted? Road segment was moved by more than",
						String.format("%.2f m", 2.5), ", from address", r, house.getSign());
			}
		}
	}

	private static boolean hasChanges(
			List<HousenumberRoad> housenumberRoads) {
		for (HousenumberRoad hnr : housenumberRoads){
			if (hnr.isChanged())
				return true;
		}
		return false;
	}

	/**
	 * 
	 * @param housenumberRoads
	 */
	private static void checkWrongRoadAssignmments(List<HousenumberRoad> housenumberRoads) {
		if (housenumberRoads.size() < 2)
			return;
		for (int loop = 0; loop < 10; loop++){
			boolean changed = false;
			for (int i = 0; i+1 < housenumberRoads.size(); i++){
				HousenumberRoad hnr1 = housenumberRoads.get(i);
				hnr1.setChanged(false);
				for (int j = i+1; j < housenumberRoads.size(); j++){
					HousenumberRoad hnr2 = housenumberRoads.get(j);
					hnr2.setChanged(false);
					hnr1.checkWrongRoadAssignmments(hnr2);
					if (hnr1.isChanged()){
						changed = true;
						hnr1.checkIntervals();
					}
					if (hnr2.isChanged()){
						changed = true;
						hnr2.checkIntervals();
					}
				}
			}
			if (!changed)
				return;
		}
	}

	/**
	 * Sorts house numbers by roads, road segments and position of the house number.
	 * @author WanMil
	 */
	public static class HousenumberMatchByPosComparator implements Comparator<HousenumberMatch> {

		public int compare(HousenumberMatch o1, HousenumberMatch o2) {
			if (o1 == o2) {
				return 0;
			}
			if (o1.getRoad() == null || o2.getRoad() == null){
				log.error("road is null in sort comparator",o1,o2);
				throw new MapFailedException("internal error in housenumber processing"); 
			}
			if (o1.getRoad() != o2.getRoad()) {
				// should not happen
				return o1.getRoad().getRoadId() - o2.getRoad().getRoadId();
			} 
			
			int dSegment = o1.getSegment() - o2.getSegment();
			if (dSegment != 0) {
				return dSegment;
			}
			
			double dFrac = o1.getSegmentFrac() - o2.getSegmentFrac();
			if (dFrac != 0d) {
				return (int)Math.signum(dFrac);
			}
			
			int d = o1.getHousenumber() - o2.getHousenumber();
			if (d != 0)
				return d;
			d = o1.getSign().compareTo(o2.getSign());
			if (d != 0)
				return d;
			return 0;
		}
		
	}
	
	/**
	 * Sorts house numbers by house number and segment 
	 * @author Gerd Petermann
	 */
	public static class HousenumberMatchByNumComparator implements Comparator<HousenumberMatch> {
		public int compare(HousenumberMatch o1, HousenumberMatch o2) {
			if (o1 == o2)
				return 0;
			int d = o1.getHousenumber() - o2.getHousenumber();
			if (d != 0)
				return d;
			d = o1.getSign().compareTo(o2.getSign());
			if (d != 0)
				return d;
			d = o1.getSegment() - o2.getSegment();
			if (d != 0)
				return d;
			double dDist = o1.getDistance() - o2.getDistance();
			if (dDist != 0d) {
				return (int)Math.signum(dDist);
			}
			return Long.compare(o1.getElement().getId(), o2.getElement().getId());
		}
	}
	/**
	 * Sorts house numbers by distance. If eqaul, compare segment and road to produce
	 * predictable results.  
	 * @author Gerd Petermann
	 */
	public static class HousenumberMatchByDistComparator implements Comparator<HousenumberMatch> {
		public int compare(HousenumberMatch o1, HousenumberMatch o2) {
			if (o1 == o2)
				return 0;
			int d = Double.compare(o1.getDistance(), o2.getDistance());
			if (d != 0)
				return d;
			d = Integer.compare(o1.getSegment(), o2.getSegment());
			if (d != 0)
				return d;
			d = Integer.compare(o1.getRoad().getRoadId(), o2.getRoad().getRoadId());
			if (d != 0)
				return d;
			return 0;
		}
	}
	
	/**
	 * If the closest point to a road is a junction, try to find the road
	 * segment that forms a right angle with the house 
	 * @param closestMatch one match that is closest to the node
	 * @param otherMatches  the other matches with the same distance
	 * @return the best match
	 */
	private static HousenumberMatch checkAngle(HousenumberMatch closestMatch,
			List<HousenumberMatch> otherMatches) {
		
		if (otherMatches.isEmpty())
			return closestMatch;
		HousenumberMatch bestMatch = closestMatch;
		for (HousenumberMatch alternative : otherMatches){
			if (alternative == closestMatch)
				continue;
			if (closestMatch.getDistance() < alternative.getDistance())
				break;
			// a house has the same distance to different road objects
			// if this happens at a T-junction, make sure not to use the end of the wrong road 
			Coord c1 = closestMatch.getRoad().getPoints().get(closestMatch.getSegment());
			Coord c2 = closestMatch.getRoad().getPoints().get(closestMatch.getSegment()+1);
			Coord cx = closestMatch.getLocation();
			double dist = closestMatch.getDistance();
			double dist1 = cx.distance(c1);
			double angle, altAngle;
			if (dist1 == dist)
				angle = Utils.getAngle(c2, c1, cx);
			else 
				angle = Utils.getAngle(c1, c2, cx);
			Coord c3 = alternative.getRoad().getPoints().get(alternative.getSegment());
			Coord c4 = alternative.getRoad().getPoints().get(alternative.getSegment()+1);
			
			double dist3 = cx.distance(c3);
			if (dist3 == dist)
				altAngle = Utils.getAngle(c4, c3, cx);
			else 
				altAngle = Utils.getAngle(c3, c4, cx);
			double delta = 90 - Math.abs(angle);
			double deltaAlt = 90 - Math.abs(altAngle);
			if (delta > deltaAlt){
				bestMatch = alternative;
				c1 = c3;
				c2 = c4;
			} 
		}
		if (log.isDebugEnabled()){
			if (closestMatch.getRoad() != bestMatch.getRoad()){
				log.debug("check angle: using road",bestMatch.getRoad().getRoadDef().getId(),"instead of",closestMatch.getRoad().getRoadDef().getId(),"for house number",bestMatch.getSign(),bestMatch.toBrowseURL());
			} else if (closestMatch != bestMatch){
				log.debug("check angle: using road segment",bestMatch.getSegment(),"instead of",closestMatch.getSegment(),"for house number element",bestMatch.toBrowseURL());
			}
		}
		return bestMatch;
	}

	/**
	 * Evaluates if the given point lies on the left side of the line spanned by spoint1 and spoint2.
	 * @param spoint1 first point of line
	 * @param spoint2 second point of line
	 * @param point the point to check
	 * @return {@code true} point lies on the left side; {@code false} point lies on the right side
	 */
	public static boolean isLeft(Coord spoint1, Coord spoint2, Coord point) {
		if (spoint1.distance(spoint2) == 0){
			log.warn("road segment length is 0 in left/right evaluation");
		}

		return ((spoint2.getHighPrecLon() - spoint1.getHighPrecLon())
				* (point.getHighPrecLat() - spoint1.getHighPrecLat()) - (spoint2
				.getHighPrecLat() - spoint1.getHighPrecLat())
				* (point.getHighPrecLon() - spoint1.getHighPrecLon())) > 0;
	}
	
	/**
	 * Calculates the distance to the given segment in meter.
	 * @param spoint1 segment point 1
	 * @param spoint2 segment point 2
	 * @param point point
	 * @param frac the fraction returned from {@code getFrac()} 
	 * @return the distance in meter
	 */
	public static double distanceToSegment(Coord spoint1, Coord spoint2, Coord point, double frac) {
		if (frac <= 0) {
			return spoint1.distance(point);
		} else if (frac >= 1) {
			return spoint2.distance(point);
		} else {
			return point.distToLineSegment(spoint1, spoint2);
		}
	}
	
	/**
	 * Calculates the fraction at which the given point is closest to 
	 * the infinite line going through both points.
	 * @param spoint1 segment point 1
	 * @param spoint2 segment point 2
	 * @param point point
	 * @return the fraction (can be <= 0 or >= 1 if the perpendicular is not on
	 * the line segment between spoint1 and spoint2) 
	 */
	public static double getFrac(Coord spoint1, Coord spoint2, Coord point) {
		int aLon = spoint1.getHighPrecLon();
		int bLon = spoint2.getHighPrecLon();
		int pLon = point.getHighPrecLon();
		int aLat = spoint1.getHighPrecLat();
		int bLat = spoint2.getHighPrecLat();
		int pLat = point.getHighPrecLat();
		
		double deltaLon = bLon - aLon;
		double deltaLat = bLat - aLat;

		if (deltaLon == 0 && deltaLat == 0) 
			return 0;
		else {
			// scale for longitude deltas by cosine of average latitude  
			double scale = Math.cos(Coord.hpToRadians((aLat + bLat + pLat) / 3) );
			double deltaLonAP = scale * (pLon - aLon);
			deltaLon = scale * deltaLon;
			if (deltaLon == 0 && deltaLat == 0)
				return 0;
			else 
				return (deltaLonAP * deltaLon + (pLat - aLat) * deltaLat) / (deltaLon * deltaLon + deltaLat * deltaLat);
		}
	}

	/**
	 * @param length
	 * @return string with length, e.g. "0.23 m" or "116.12 m"
	 */
	public static String formatLen(double length){
		return String.format("%.2f m", length);
	}
	

	/**
	 * A performance critical part:
	 * Index all road segments to be able to find all road segments within a given range
	 * around a point.  
	 * @author Gerd Petermann
	 *
	 */
	private static class RoadSegmentIndex {
		private final KdTree<RoadPoint> kdTree = new KdTree<>();
		private final Int2ObjectOpenHashMap<Set<RoadPoint>> nodeId2RoadPointMap = new Int2ObjectOpenHashMap<>(); 
		private final double range;
		private final double maxSegmentLength;
		private final double kdSearchRange;

		private static class RoadPoint implements Locatable{
			final Coord p;
			final MapRoad r;
			final int segment;
			final int partOfSeg;
			
			public RoadPoint(MapRoad road, Coord co, int s, int part) {
				this.p = co;
				this.r = road;
				this.segment = s;
				this.partOfSeg = part;
			}
			@Override
			public Coord getLocation() {
				return p;
			}
			@Override
			public String toString() {
				return r + " " + segment + " " + partOfSeg;
			}
		}

		public RoadSegmentIndex(List<MapRoad> roads, double rangeInMeter) {
			this.range = rangeInMeter;
			this.maxSegmentLength = range * 2 / 3;
			this.kdSearchRange = Math.sqrt(Math.pow(rangeInMeter, 2) + Math.pow(maxSegmentLength/2, 2));
			build(roads);
			
		}

		public void build(List<MapRoad> roads){
			for (MapRoad road : roads){
				if (road.isSkipHousenumberProcessing())
					continue;
				List<Coord> points = road.getPoints();
				if (points.size() < 2)
					continue;

				List<RoadPoint> roadPoints = new ArrayList<>();
				RoadPoint rp;
				for (int i = 0; i + 1 < points.size(); i++){
					Coord c1 = points.get(i);
					Coord c2 = points.get(i + 1);
					int part = 0;
					rp = new RoadPoint(road, c1, i, part++);
					roadPoints.add(rp);
					while (true){
						double segLen = c1.distance(c2);
						double frac = maxSegmentLength / segLen;
						if (frac >= 1)
							break;
						// if points are not close enough, add extra point
						c1 = c1.makeBetweenPoint(c2, frac);
						rp = new RoadPoint(road, c1, i, part++);
						roadPoints.add(rp);
						segLen -= maxSegmentLength;
					}
				}
				int last = points.size() - 1;
				rp = new RoadPoint(road, points.get(last) , last, -1);
				roadPoints.add(rp);
				
				Collections.shuffle(roadPoints);
				for (RoadPoint toAdd : roadPoints){
					int id = toAdd.p.getId();
					if (id == 0)
						kdTree.add(toAdd);
					else {
						// Coord node, add only once to KD-tree with all roads
						Set<RoadPoint> set = nodeId2RoadPointMap.get(id);
						if (set == null){
							set = new LinkedHashSet<>();
							nodeId2RoadPointMap.put(id, set);
							kdTree.add(toAdd);
						}
						set.add(toAdd);
					}  		
				}
			}
		}
		
		public List<RoadPoint> getCLoseRoadPoints(HousenumberElem house){
			Set<RoadPoint> closeRoadPoints = kdTree.findNextPoint(house, kdSearchRange);
			List<RoadPoint> result = new ArrayList<>();
			for (RoadPoint rp : closeRoadPoints){
				int id = rp.p.getId();
				if (id != 0)
					result.addAll(nodeId2RoadPointMap.get(id));
				else 
					result.add(rp);
			}
			return result;
		}
		
		/**
		 * Find closest road segment and other plausible roads for a house
		 * @param house
		 * @return null if no road was found, else a {@link HousenumberMatch} instance 
		 */
		public HousenumberMatch createHousenumberMatch(HousenumberElem house){
			HousenumberMatch closest = new HousenumberMatch(house);
			List<RoadPoint> closeRoadPoints = getCLoseRoadPoints(house);
			if (closeRoadPoints.isEmpty())
				return closest;
			Collections.sort(closeRoadPoints, new Comparator<RoadPoint>() {
				// sort by distance (smallest first)
				public int compare(RoadPoint o1,  RoadPoint o2) {
					if (o1 == o2)
						return 0;
					int d = Integer.compare(o1.r.getRoadId(), o2.r.getRoadId());
					if (d != 0)
						return d;
					d = Integer.compare(o1.segment, o2.segment);
					if (d != 0)
						return d; 
					return Integer.compare(o1.partOfSeg, o2.partOfSeg);
				}
			});

			List<HousenumberMatch> matches = new ArrayList<>(40);
			BitSet testedSegments = new BitSet();
			MapRoad lastRoad = null;
			HousenumberMatch hnm = null;
			for (RoadPoint rp : closeRoadPoints){
				if (house.getStreet() != null){
					// we have a given street name, accept only roads with similar name or no name
					if (rp.r.getStreet() != null && house.getStreet().equalsIgnoreCase(rp.r.getStreet()) == false)
						continue;
				}
				if (rp.r != lastRoad){
					hnm = new HousenumberMatch(house);
					testedSegments.clear();
					matches.add(hnm);
					lastRoad = rp.r;
				}
				double oldDist = hnm.getDistance();
				if (rp.partOfSeg >= 0){
					// rp.p is at start or before end of segment 
					if (testedSegments.get(rp.segment) == false){
						testedSegments.set(rp.segment);
						checkSegment(hnm, rp.r, rp.segment);
					}
				} 
				if (rp.partOfSeg < 0){
					// rp is at end of road, check (also) the preceding segment 
					if (rp.segment < 1){
						log.error("internal error: trying to use invalid roadPoint",rp);
					} else if (testedSegments.get(rp.segment - 1) == false){
						testedSegments.set(rp.segment-1);
						checkSegment(hnm, rp.r, rp.segment-1);
					}
				}
				if (oldDist == hnm.getDistance())
					continue;
			}
			if (matches.isEmpty())
				return closest; // closest has not yet a road
			
			Collections.sort(matches, new HousenumberGenerator.HousenumberMatchByDistComparator());
			closest = matches.get(0);
			closest = checkAngle(closest, matches);
			closest.calcRoadSide();
			HousenumberMatch bestMatchingName = null; 
			if (closest.getStreet() != null && closest.getStreet().equalsIgnoreCase(closest.getRoad().getStreet()))
				bestMatchingName = closest;
			
			for (HousenumberMatch altHouse : matches){
				if (altHouse.getDistance() >= MAX_DISTANCE_TO_ROAD)
					break;
				if (altHouse.getRoad() != closest.getRoad()){
					if (house.getStreet() != null && altHouse.getDistance() > closest.getDistance()){
						if (house.getStreet().equalsIgnoreCase(altHouse.getRoad().getStreet())){
							if (bestMatchingName == null || bestMatchingName.getDistance() > altHouse.getDistance()){
								bestMatchingName = altHouse;
							}
						} else {
							if (bestMatchingName != null && altHouse.getDistance() > bestMatchingName.getDistance())
								continue;
						}
					}
					closest.addAlternativeRoad(altHouse.getRoad());
				}
			}
			if (bestMatchingName != null){
				if (house.getStreet().equals(bestMatchingName.getRoad().getStreet()) == false){
					log.warn("accepting match in spite of different capitalisation" , house.getStreet(),house.getSign(), bestMatchingName.getRoad().getRoadDef(), "house:",house.toBrowseURL());
					bestMatchingName.setStreet(bestMatchingName.getRoad().getStreet());
					closest.setStreet(bestMatchingName.getStreet());
				}
			}
			if (closest == bestMatchingName || bestMatchingName == null || bestMatchingName.getDistance() > MAX_DISTANCE_TO_ROAD)
				return closest;
			
			double ratio = closest.getDistance() / bestMatchingName.getDistance();
			if (ratio < 0.25)
				return closest;
			HousenumberMatch best = closest;
			if (ratio > 0.75){
				// prefer the road with the matching name
				for (MapRoad r : closest.getAlternativeRoads()){
					if (house.getStreet().equalsIgnoreCase(r.getStreet()))
						bestMatchingName.addAlternativeRoad(r);
				}
				best = bestMatchingName;
				best.calcRoadSide();
			} else {
				if (log.isDebugEnabled()){
					log.debug("further checks needed for address", closest.getStreet(), closest.getSign(), closest.toBrowseURL(), 
							formatLen(closest.getDistance()), formatLen(bestMatchingName.getDistance()));
				}

			}
			return best;
		}

	}
	
	private static void checkSegment(HousenumberMatch house, MapRoad road, int seg){
		Coord cx = house.getLocation();
		Coord c0 = road.getPoints().get(seg);
		Coord c1 = road.getPoints().get(seg + 1);
		double frac = getFrac(c0, c1, cx);
		double dist = distanceToSegment(c0,c1,cx,frac);
		if (dist < house.getDistance()){
			house.setDistance(dist);
			house.setRoad(road);
			house.setSegment(seg);
			house.setSegmentFrac(frac);
		}
	}

}


