/*
 * Copyright (C) 2014.
 *
 * 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.filters;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.Collections;
import java.util.Comparator;
import java.util.IdentityHashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

import it.unimi.dsi.fastutil.ints.IntArrayList;
import uk.me.parabola.imgfmt.app.Coord;
import uk.me.parabola.log.Logger;
import uk.me.parabola.mkgmap.general.MapShape;
import uk.me.parabola.mkgmap.osmstyle.WrongAngleFixer;
import uk.me.parabola.mkgmap.reader.osm.FakeIdGenerator;
import uk.me.parabola.mkgmap.reader.osm.GType;
import uk.me.parabola.util.Java2DConverter;


/**
 * Merge shapes with same Garmin type and similar attributes if they have common 
 * points. This reduces the number of shapes as well as the number of points.
 * @author GerdP
 *
 */
public class ShapeMergeFilter{
	private static final Logger log = Logger.getLogger(ShapeMergeFilter.class);
	private final int resolution;
	private final static ShapeHelper DUP_SHAPE = new ShapeHelper(new ArrayList<Coord>(0)); 
	private final boolean orderByDecreasingArea;

	public ShapeMergeFilter(int resolution, boolean orderByDecreasingArea) {
		this.resolution = resolution;
		this.orderByDecreasingArea = orderByDecreasingArea;
	}

	/**
	 * Merge shapes that are similar and have identical points.
	 * @param shapes list of shapes
	 * @return list of merged shapes (might be identical to original list)
	 */
	public List<MapShape> merge(List<MapShape> shapes) {
		if (shapes.size() <= 1)
			return shapes;
		List<MapShape> mergedShapes = new ArrayList<>();
		List<MapShape> usableShapes = new ArrayList<>();
		for (MapShape shape: shapes) {
			if (shape.getMinResolution() > resolution || shape.getMaxResolution() < resolution)
				continue;
			if (shape.getPoints().get(0) != shape.getPoints().get(shape.getPoints().size()-1)){
				// should not happen here
				log.error("shape is not closed with identical points", shape.getOsmid(),
					  shape.getPoints().get(0).toOSMURL());
				mergedShapes.add(shape);
				continue;
			}
			usableShapes.add(shape);
		}
		if (usableShapes.size() < 2) {
			mergedShapes.addAll(usableShapes);
			return mergedShapes;
		}
		
		Comparator<MapShape> comparator = new MapShapeComparator();
		usableShapes.sort(comparator);
		int p1 = 0;
		MapShape s1 = usableShapes.get(0);
		for (int i = 1; i < usableShapes.size(); i++) {
			if (comparator.compare(s1, usableShapes.get(i)) == 0)
				continue;
			mergeSimilar(usableShapes.subList(p1, i), mergedShapes);
			s1 = usableShapes.get(i);
			p1 = i;
		}
		if (p1 < usableShapes.size())
			mergeSimilar(usableShapes.subList(p1, usableShapes.size()), mergedShapes);
		return mergedShapes;
	}
	
	/**
	 * Merge similar shapes.
	 * @param similar list of similar shapes
	 * @param mergedShapes list to which the shapes are added 
	 */
	private void mergeSimilar(List<MapShape> similar, List<MapShape> mergedShapes) {
		if (similar.size() == 1) {
			mergedShapes.addAll(similar);
			return;
		}
		List<ShapeHelper> list = new ArrayList<>();
		MapShape s1 = similar.get(0);
		for (MapShape ms : similar) {
			ShapeHelper sh = new ShapeHelper(ms.getPoints());
			sh.id = ms.getOsmid();
			list.add(sh);
		}
		tryMerge(s1, list);
		for (ShapeHelper sh : list) {
			MapShape newShape = s1.copy();

			assert sh.getPoints().get(0) == sh.getPoints().get(sh.getPoints().size() - 1);
			if (sh.id == 0) {
				// this shape is the result of a merge
				List<Coord> optimizedPoints = WrongAngleFixer.fixAnglesInShape(sh.getPoints());
				if (optimizedPoints.isEmpty())
					continue;
				newShape.setPoints(optimizedPoints);
				newShape.setOsmid(FakeIdGenerator.makeFakeId());
			} else {
				newShape.setPoints(sh.getPoints());
				newShape.setOsmid(sh.id);
			}
			mergedShapes.add(newShape);
		}
	}

	/**
	 * Merge ShapeHelpers. Calls itself recursively.
	 * @param pattern a MapShape
	 * @param similarShapes {@link ShapeHelper} instances created from similar {@link MapShape}.
	 * This list is modified if shapes were merged.
	 */
	private void tryMerge(MapShape pattern, List<ShapeHelper> similarShapes) {
		if (similarShapes.size() <= 1)
			return;

		List<ShapeHelper> noMerge = new ArrayList<>();
		BitSet toMerge = new BitSet(similarShapes.size());
		
		// abuse highway count to find identical points in different shapes
		similarShapes.forEach(sh -> sh.getPoints().forEach(Coord::resetHighwayCount));
		similarShapes.forEach(sh -> sh.getPoints().forEach(Coord::incHighwayCount));
		// decrement counter for duplicated start/end node
		similarShapes.forEach(sh -> sh.getPoints().get(0).decHighwayCount());
		
		// points with count > 1 are probably shared by different shapes, collect the shapes
		IdentityHashMap<Coord, BitSet> coord2Shape = new IdentityHashMap<>();
		BitSet[] candidates = new BitSet[similarShapes.size()];
		
		for (int i = 0; i < similarShapes.size(); i++) {
			ShapeHelper sh0 = similarShapes.get(i);
			List<Coord> sharedPoints = new ArrayList<>(); 
			for (int j = 1; j < sh0.getPoints().size(); j++) {
				Coord c = sh0.getPoints().get(j);
				if (c.getHighwayCount() > 1) {
					sharedPoints.add(c);
				}
			}
			if (sharedPoints.size() == 0 || sh0.getPoints().size() - sharedPoints.size()> PolygonSplitterFilter.MAX_POINT_IN_ELEMENT) {
				// merge will not work 
				noMerge.add(sh0);
				continue;
			}
			
			assert candidates[i] == null;
			candidates[i] = new BitSet();
			BitSet curr = candidates[i];
			curr.set(i);
			
			toMerge.set(i);
			for (Coord c: sharedPoints) { 
				BitSet set = coord2Shape.get(c);
				if (set == null) {
					set = new BitSet();
					coord2Shape.put(c, set);
				} else { 
					for (int j = set.nextSetBit(0); j >= 0; j = set.nextSetBit(j + 1)) {
						candidates[j].set(i);
					}
					curr.or(set);
				}
				set.set(i);
			}
		}
		if (coord2Shape.isEmpty()) {
			// nothing to do
			return;
		}
		
		List<ShapeHelper> next = new ArrayList<>();
		boolean merged = false;
		BitSet done = new BitSet();
		BitSet delayed = new BitSet();  

		for (int i = toMerge.nextSetBit(0); i >= 0; i = toMerge.nextSetBit(i + 1)) {
			if (done.get(i))
				continue;
			BitSet all = candidates[i];
			if (all.cardinality() <= 1) {
				if (!all.isEmpty())
					delayed.set(i);
				continue;
			}
			all.andNot(done);
			
			if (all.isEmpty())
				continue;
			List<ShapeHelper> result = new ArrayList<>();
			for (int j = all.nextSetBit(0); j >= 0; j = all.nextSetBit(j + 1)) {
				ShapeHelper sh = similarShapes.get(j);
				int oldSize = result.size();
				result = addWithConnectedHoles(result, sh, pattern.getType());
				if (result.size() < oldSize + 1) {
					merged = true;
					log.debug("shape with id", sh.id, "was merged", (oldSize + 1 - result.size()),
							" time(s) at resolution", resolution);
				}
			}
			// XXX : not exact, there may be other combinations of shapes which can be merged
			// e.g. merge of shape 1 + 2 may not work but 2 and 3 could still be candidates.
			done.or(all);
			next.addAll(result);
		}
		
		delayed.andNot(done);
		if (!delayed.isEmpty()) {
			for (int i = delayed.nextSetBit(0); i >= 0; i = delayed.nextSetBit(i+1)) {
				noMerge.add(similarShapes.get(i));
			}
		}
		similarShapes.clear();
		similarShapes.addAll(noMerge);
		
		if (merged) 
			tryMerge(pattern, next);
		
		// Maybe add final step which calls addWithConnectedHoles for all remaining shapes
		// this will find a few more merges but is still slow for maps with lots of islands 
		similarShapes.addAll(next);
	}


	/**
	 * Try to merge a shape with one or more of the shapes in the list.
	 *  If it cannot be merged, it is added to the list.
	 *  Holes in shapes are connected with the outer lines,
	 *  so no following routine must use {@link Java2DConverter}
	 *  to process these shapes.
	 * @param list list of shapes with equal type
	 * @param toAdd new shape
	 * @param type garmin type of pattern MapShape
	 * @return new list of shapes, this might contain fewer (merged) elements
	 */
	private List<ShapeHelper> addWithConnectedHoles(List<ShapeHelper> list,
			final ShapeHelper toAdd, final int type) {
		assert toAdd.getPoints().size() > 3;
		List<ShapeHelper> result = new ArrayList<>(list.size() + 1);
		ShapeHelper shNew = new ShapeHelper(toAdd);
		for (ShapeHelper shOld : list) {
			ShapeHelper mergeRes = tryMerge(shOld, shNew);
			if (mergeRes == shOld){
				result.add(shOld);
				continue;
			} else if (mergeRes != null){
				shNew = mergeRes;
			}
			if (shNew == DUP_SHAPE){
				log.warn("ignoring duplicate shape with id", toAdd.id, "at",  toAdd.getPoints().get(0).toOSMURL(), "with type", GType.formatType(type), "for resolution", resolution);
				return list; // nothing to do
			}
		}
		if (shNew != null && shNew != DUP_SHAPE)
			result.add(shNew);
		if (result.size() > list.size()+1 )
			log.error("result list size is wrong", list.size(), "->", result.size());
		return result;
	}

	/**
	 * Find out if two shapes have common points. If yes, merge them.
	 * @param sh1 1st shape1
	 * @param sh2 2st shape2
	 * @return merged shape or 1st shape if no common point found or {@code dupShape} 
	 * if both shapes describe the same area. 
	 */
	private ShapeHelper tryMerge(ShapeHelper sh1, ShapeHelper sh2) {
		
		// both clockwise or both ccw ?
		boolean sameDir = sh1.areaTestVal > 0 && sh2.areaTestVal > 0 || sh1.areaTestVal < 0 && sh2.areaTestVal < 0;
		
		List<Coord> points1, points2;
		if (sh2.getPoints().size()> sh1.getPoints().size()){
			points1 = sh2.getPoints();
			points2 = sh1.getPoints();
		} else {
			points1 = sh1.getPoints();
			points2 = sh2.getPoints();
		}
		// find all coords that are common in the two shapes 
		IntArrayList sh1PositionsToCheck = new IntArrayList();
		IntArrayList sh2PositionsToCheck = new IntArrayList();

		findCommonCoords(points1, points2, sh1PositionsToCheck, sh2PositionsToCheck); 		
		if (sh1PositionsToCheck.isEmpty()){
			return sh1;
		}
		if (sh2PositionsToCheck.size() + 1 >= points2.size()){
			// all points are identical, might be a duplicate
			// or a piece that fills a hole 
			if (points1.size() == points2.size() && Math.abs(sh1.areaTestVal) == Math.abs(sh2.areaTestVal)){ 
				// it is a duplicate, we can ignore it
				// XXX this might fail if one of the shapes is self intersecting
				return DUP_SHAPE;
			}
		}
		List<Coord> merged = null; 
		if (points1.size() + points2.size() - 2*sh1PositionsToCheck.size() < PolygonSplitterFilter.MAX_POINT_IN_ELEMENT){
			merged = mergeLongestSequence(points1, points2, sh1PositionsToCheck, sh2PositionsToCheck, sameDir);
			if (merged.isEmpty())
				return DUP_SHAPE;
			if (merged.get(0) != merged.get(merged.size()-1))
				merged = null;
			else if (merged.size() > PolygonSplitterFilter.MAX_POINT_IN_ELEMENT){
				// don't merge because merged polygon would be split again
				log.info("merge rejected: merged shape has too many points " + merged.size());
				merged = null;
			}
		}
		ShapeHelper shm = null;
		if (merged != null){
			shm = new ShapeHelper(merged);
			if (Math.abs(shm.areaTestVal) != Math.abs(sh1.areaTestVal) + Math.abs(sh2.areaTestVal)){
				log.warn("merging shapes skipped for shapes near", points1.get(sh1PositionsToCheck.getInt(0)).toOSMURL(), 
						"(maybe overlapping shapes?)");
				merged = null;
				shm = null;
			} else {
				if (log.isInfoEnabled()){
					log.info("merge of shapes near",points1.get(sh1PositionsToCheck.getInt(0)).toOSMURL(), 
							"reduces number of points from",(points1.size()+points2.size()),
							"to",merged.size());
				}
			}
		}
		if (shm != null)
			return shm;
		if (merged == null)
			return sh1;
		return null;
	}

	/**
	 * Find the common Coord instances and save their positions for both shapes.
	 * @param s1 shape 1
	 * @param s2 shape 2
	 * @param s1PositionsToCheck will contain common positions in shape 1   
	 * @param s2PositionsToCheck will contain common positions in shape 2
	 */
	private static void findCommonCoords(List<Coord> s1, List<Coord> s2,
			IntArrayList s1PositionsToCheck,
			IntArrayList s2PositionsToCheck) {
		Map<Coord, Integer> s2PosMap = new IdentityHashMap<>(s2.size() - 1);
		
		for (int i = 0; i+1 < s1.size(); i++){
		    Coord co = s1.get(i);
		    co.setPartOfShape2(false);
		}
		for (int i = 0; i+1 < s2.size(); i++){
		    Coord co = s2.get(i);
		    co.setPartOfShape2(true);
		    s2PosMap.put(co, i); 
		}
		
		int start = 0;
		while(start < s1.size()){
			Coord co = s1.get(start);
			if (!co.isPartOfShape2())
				break;
			start++;
		}
		int pos = start+1;
		int tested = 0;
		while(true){
			if (pos+1 >= s1.size())
				pos = 0;
			Coord co = s1.get(pos);
			if (++tested >= s1.size())
				break;
			if (co.isPartOfShape2()){
				s1PositionsToCheck.add(pos);
				Integer posInSh2 = s2PosMap.get(co);
				assert posInSh2 != null;
				s2PositionsToCheck.add(posInSh2);
			}
			pos++;
		}
		return;
	} 	
	
	/**
	 * Finds the longest sequence of common points in two shapes.
	 * @param points1 list of Coord instances that describes the 1st shape 
	 * @param points2 list of Coord instances that describes the 2nd shape
	 * @param sh1PositionsToCheck positions in the 1st shape that are common
	 * @param sh2PositionsToCheck positions in the 2nd shape that are common
	 * @param sameDir true if both shapes are clockwise or both are ccw
	 * @return the merged shape or null if no points are common.
	 */
	private static List<Coord> mergeLongestSequence(List<Coord> points1, List<Coord> points2, IntArrayList sh1PositionsToCheck,
			IntArrayList sh2PositionsToCheck, boolean sameDir) {
		if (sh1PositionsToCheck.isEmpty())
			return null;
		int s1Size = points1.size(); 
		int s2Size = points2.size();
		int longestSequence = 0;
		int startOfLongestSequence = 0;
		int length = 0;
		int start = -1;
		int n1 = sh1PositionsToCheck.size();
		
		assert sh2PositionsToCheck.size() == n1;
		boolean inSequence = false;
		for (int i = 0; i+1 < n1; i++){
			int pred1 = sh1PositionsToCheck.getInt(i);
			int succ1 = sh1PositionsToCheck.getInt(i+1);
			if (Math.abs(succ1-pred1) == 1 || pred1+2 == s1Size && succ1 == 0 || succ1+2 == s1Size && pred1 == 0 ){
				// found sequence in s1
				int pred2 = sh2PositionsToCheck.getInt(i);
				int succ2 = sh2PositionsToCheck.getInt(i+1);
				if (Math.abs(succ2-pred2) == 1 || pred2+2 == s2Size && succ2 == 0 || succ2+2 == s2Size && pred2 == 0 ){
					// found common sequence
					if (start < 0)
						start = i;
					inSequence = true;
					length++; 
				} else {
					inSequence = false;
				}
			} else {
				inSequence = false;
			}
			if (!inSequence){
				if (length > longestSequence){
					longestSequence = length;
					startOfLongestSequence = start;
				}
				length = 0;
				start = -1;
			}
		}
		if (length > longestSequence){
			longestSequence = length;
			startOfLongestSequence = start;
		}
		// now merge the shapes. The longest sequence of common points is removed.
		// The remaining points are connected in the direction of the 1st shape.
		int remaining = s1Size + s2Size - 2*longestSequence -1;
		if (remaining < 3) {
			return Collections.emptyList(); // may happen with self-intersecting duplicated shapes
		}
		List<Coord> merged = new ArrayList<>(remaining);
		int s1Pos = sh1PositionsToCheck.getInt(startOfLongestSequence+longestSequence);
		for (int i = 0; i < s1Size - longestSequence - 1; i++){
			merged.add(points1.get(s1Pos));
			s1Pos++;
			if (s1Pos+1 >= s1Size)
				s1Pos = 0;
		}
		int s2Pos = sh2PositionsToCheck.getInt(startOfLongestSequence);
		int s2Step = sameDir ? 1:-1;
		for (int i = 0; i < s2Size - longestSequence; i++){
			merged.add(points2.get(s2Pos));
			s2Pos += s2Step;
			if (s2Pos < 0) 
				s2Pos = s2Size-2;
			else if (s2Pos+1 >= s2Size)
				s2Pos = 0;
		}
		return merged;
	}
 	
	private static class ShapeHelper {
		final private List<Coord> points;
		long id;
		long areaTestVal;

		public ShapeHelper(List<Coord> merged) {
			this.points = merged;
			areaTestVal = calcAreaSizeTestVal(points);
		}

		public ShapeHelper(ShapeHelper other) {
			this.points = other.points;
			this.areaTestVal = other.areaTestVal;
			this.id = other.id;
		}

		public List<Coord> getPoints() {
			return points;
		}
	}
	
	public final static long SINGLE_POINT_AREA = 1L << Coord.DELTA_SHIFT * 1L << Coord.DELTA_SHIFT;
	
	/**
	 * Calculate the high precision area size test value.  
	 * @param points
	 * @return area size in high precision map units * 2.
	 * The value is >= 0 if the shape is clockwise, else < 0   
	 */
	public static long calcAreaSizeTestVal(List<Coord> points){
		if (points.size() < 4)
			return 0; // straight line cannot enclose an area
		if (points.get(0).highPrecEquals(points.get(points.size()-1)) == false){
			log.error("shape is not closed");
			return 0;
		}
		Iterator<Coord> polyIter = points.iterator();
		Coord c2 = polyIter.next();
		long signedAreaSize = 0;
		while (polyIter.hasNext()) {
			Coord c1 = c2;
			c2 = polyIter.next();
			signedAreaSize += (long) (c2.getHighPrecLon() + c1.getHighPrecLon())
					* (c1.getHighPrecLat() - c2.getHighPrecLat());
		}
		if (Math.abs(signedAreaSize) < SINGLE_POINT_AREA){
			if (log.isDebugEnabled()) {
				log.debug("very small shape near", points.get(0).toOSMURL(), "signed area in high prec map units:", signedAreaSize );
			}
		}
		return signedAreaSize;
	}
	
	private class MapShapeComparator implements Comparator<MapShape> {
		@Override
		public int compare(MapShape o1, MapShape o2) {
			int d = Integer.compare(o1.getType(), o2.getType());
			if (d != 0) 
				return d;
			d = Boolean.compare(o1.isSkipSizeFilter(), o2.isSkipSizeFilter());
			if (d != 0)
				return d;
			// XXX wasClipped() is ignored here, might be needed if later filters need it  
			if (orderByDecreasingArea) {
				d = Long.compare(o1.getFullArea(), o2.getFullArea());
				if (d != 0)
					return d;
			}
			String n1 = o1.getName();
			String n2 = o2.getName();
			if (n1 == n2)
				return 0;
			if (n1 == null) {
				return (n2 == null) ? 0 : 1;
			}
			if (n2 == null)
				return -1;
			
			return n1.compareTo(n2);
		}
	}
}

