package mergeoverlap;

import static org.openstreetmap.josm.gui.conflict.tags.TagConflictResolutionUtil.combineTigerTags;
import static org.openstreetmap.josm.gui.conflict.tags.TagConflictResolutionUtil.completeTagCollectionForEditing;
import static org.openstreetmap.josm.gui.conflict.tags.TagConflictResolutionUtil.normalizeTagCollectionBeforeEditing;
import static org.openstreetmap.josm.tools.I18n.tr;

import java.awt.event.ActionEvent;
import java.awt.event.KeyEvent;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

import javax.swing.JOptionPane;

import mergeoverlap.hack.MyCombinePrimitiveResolverDialog;

import org.openstreetmap.josm.Main;
import org.openstreetmap.josm.actions.JosmAction;
import org.openstreetmap.josm.actions.SplitWayAction;
import org.openstreetmap.josm.actions.CombineWayAction.NodeGraph;
import org.openstreetmap.josm.actions.SplitWayAction.SplitWayResult;
import org.openstreetmap.josm.command.AddCommand;
import org.openstreetmap.josm.command.ChangeCommand;
import org.openstreetmap.josm.command.Command;
import org.openstreetmap.josm.command.DeleteCommand;
import org.openstreetmap.josm.command.SequenceCommand;
import org.openstreetmap.josm.corrector.ReverseWayTagCorrector;
import org.openstreetmap.josm.corrector.UserCancelException;
import org.openstreetmap.josm.data.osm.Node;
import org.openstreetmap.josm.data.osm.OsmPrimitive;
import org.openstreetmap.josm.data.osm.Relation;
import org.openstreetmap.josm.data.osm.RelationMember;
import org.openstreetmap.josm.data.osm.TagCollection;
import org.openstreetmap.josm.data.osm.Way;
import org.openstreetmap.josm.gui.layer.OsmDataLayer;
import org.openstreetmap.josm.tools.Pair;
import org.openstreetmap.josm.tools.Shortcut;

/**
 * Merge overlapping part of ways.
 */
public class MergeOverlapAction extends JosmAction {

    /**
     * Constructs a new {@code MergeOverlapAction}.
     */
    public MergeOverlapAction() {
        super(tr("Merge overlap"), "merge_overlap",
                tr("Merge overlap of ways."), 
                Shortcut.registerShortcut("tools:mergeoverlap",tr("Tool: {0}", tr("Merge overlap")), KeyEvent.VK_O,
                Shortcut.ALT_CTRL), true);
    }

    Map<Way, List<Relation>> relations = new HashMap<>();
    Map<Way, Way> oldWays = new HashMap<>();
    Map<Relation, Relation> newRelations = new HashMap<>();
    Set<Way> deletes = new HashSet<>();

    /**
     * The action button has been clicked
     * 
     * @param e
     *            Action Event
     */
    @Override
    public void actionPerformed(ActionEvent e) {

        // List of selected ways
        List<Way> ways = new ArrayList<>();
        relations.clear();
        newRelations.clear();

        // For every selected way
        for (OsmPrimitive osm : Main.main.getCurrentDataSet().getSelected()) {
            if (osm instanceof Way && !osm.isDeleted()) {
                Way way = (Way) osm;
                ways.add(way);
                List<Relation> rels = new ArrayList<>();
                for (Relation r : OsmPrimitive.getFilteredList(way.getReferrers(), Relation.class)) {
                    rels.add(r);
                }
                relations.put(way, rels);
            }
        }

        List<Way> sel = new ArrayList<>(ways);
        Collection<Command> cmds = new LinkedList<>();

        // *****
        // split
        // *****
        for (Way way : ways) {
            Set<Node> nodes = new HashSet<>();
            for (Way opositWay : ways) {
                if (way != opositWay) {
                    List<NodePos> nodesPos = new LinkedList<>();

                    int pos = 0;
                    for (Node node : way.getNodes()) {
                        int opositPos = 0;
                        for (Node opositNode : opositWay.getNodes()) {
                            if (node == opositNode) {
                                if (opositWay.isClosed()) {
                                    opositPos %= opositWay.getNodesCount() - 1;
                                }
                                nodesPos.add(new NodePos(node, pos, opositPos));
                                break;
                            }
                            opositPos++;
                        }
                        pos++;
                    }

                    NodePos start = null;
                    NodePos end = null;
                    int increment = 0;

                    boolean hasFirst = false;
                    for (NodePos node : nodesPos) {
                        if (start == null) {
                            start = node;
                        } else {
                            if (end == null) {
                                if (follows(way, opositWay, start, node, 1)) {
                                    end = node;
                                    increment = +1;
                                } else if (follows(way, opositWay, start, node, -1)) {
                                    end = node;
                                    increment = -1;
                                } else {
                                    start = node;
                                    end = null;
                                }
                            } else {
                                if (follows(way, opositWay, end, node, increment)) {
                                    end = node;
                                } else {
                                    hasFirst = addNodes(start, end, way, nodes, hasFirst);
                                    start = node;
                                    end = null;
                                }
                            }
                        }
                    }

                    if (start != null && end != null) {
                        hasFirst = addNodes(start, end, way, nodes, hasFirst);
                        start = null;
                        end = null;
                    }
                }
            }
            if (!nodes.isEmpty() && !way.isClosed() || nodes.size() >= 2) {
                List<List<Node>> wayChunks = SplitWayAction.buildSplitChunks(way, new ArrayList<>(nodes));
                SplitWayResult result = splitWay(getEditLayer(), way, wayChunks);

                cmds.add(result.getCommand());
                sel.remove(way);
                sel.add(result.getOriginalWay());
                sel.addAll(result.getNewWays());
                List<Relation> rels = relations.remove(way);
                relations.put(result.getOriginalWay(), rels);
                for (Way w : result.getNewWays()) {
                    relations.put(w, rels);
                }
            }
        }

        // *****
        // merge
        // *****
        ways = new ArrayList<>(sel);
        while (!ways.isEmpty()) {
            Way way = ways.get(0);
            List<Way> combine = new ArrayList<>();
            combine.add(way);
            for (Way opositWay : ways) {
                if (way != opositWay && way.getNodesCount() == opositWay.getNodesCount()) {
                    boolean equals1 = true;
                    for (int i = 0; i < way.getNodesCount(); i++) {
                        if (way.getNode(i) != opositWay.getNode(i)) {
                            equals1 = false;
                            break;
                        }
                    }
                    boolean equals2 = true;
                    for (int i = 0; i < way.getNodesCount(); i++) {
                        if (way.getNode(i) != opositWay.getNode(way.getNodesCount() - i - 1)) {
                            equals2 = false;
                            break;
                        }
                    }
                    if (equals1 || equals2) {
                        combine.add(opositWay);
                    }
                }
            }
            ways.removeAll(combine);
            if (combine.size() > 1) {
                sel.removeAll(combine);
                // combine
                Pair<Way, List<Command>> combineResult;
                try {
                    combineResult = combineWaysWorker(combine);
                } catch (UserCancelException ex) {
                    return;
                }
                sel.add(combineResult.a);
                cmds.addAll(combineResult.b);
            }
        }

        for (Relation old : newRelations.keySet()) {
            cmds.add(new ChangeCommand(old, newRelations.get(old)));
        }

        List<Way> del = new LinkedList<>();
        for (Way w : deletes) {
            if (w.getDataSet() != null && !w.isDeleted()) {
                del.add(w);
            }
        }
        if (!del.isEmpty()) {
            cmds.add(new DeleteCommand(del));
        }

        // Commit
        Main.main.undoRedo.add(new SequenceCommand(tr("Merge Overlap (combine)"), cmds));
        getCurrentDataSet().setSelected(sel);
        Main.map.repaint();

        relations.clear();
        newRelations.clear();
        oldWays.clear();
    }

    private static class NodePos {
        Node node;
        int pos;
        int opositPos;

        NodePos(Node n, int p, int op) {
            node = n;
            pos = p;
            opositPos = op;
        }

        @Override
        public String toString() {
            return "NodePos: " + pos + ", " + opositPos + ", " + node;
        }
    }

    private boolean addNodes(NodePos start, NodePos end, Way way,
            Set<Node> nodes, boolean hasFirst) {
        if (way.isClosed() || (start.node != way.getNode(0) && start.node != way.getNode(way.getNodesCount() - 1))) {
            hasFirst = hasFirst || start.node == way.getNode(0);
            nodes.add(start.node);
        }
        if (way.isClosed() || (end.node != way.getNode(0) && end.node != way.getNode(way.getNodesCount() - 1))) {
            if (hasFirst && (end.node == way.getNode(way.getNodesCount() - 1))) {
                nodes.remove(way.getNode(0));
            } else {
                nodes.add(end.node);
            }
        }
        return hasFirst;
    }

    private boolean follows(Way way1, Way way2, NodePos np1, NodePos np2,
            int incr) {
        if (way2.isClosed() && incr == 1 && np1.opositPos == way2.getNodesCount() - 2) {
            return np2.pos == np1.pos + 1 && np2.opositPos == 0;
        } else if (way2.isClosed() && incr == 1 && np1.opositPos == 0) {
            return np2.pos == np1.pos && np2.opositPos == 0
                    || np2.pos == np1.pos + 1 && np2.opositPos == 1;
        } else if (way2.isClosed() && incr == -1 && np1.opositPos == 0) {
            return np2.pos == np1.pos && np2.opositPos == 0 || np2.pos == np1.pos + 1
                    && np2.opositPos == way2.getNodesCount() - 2;
        } else {
            return np2.pos == np1.pos + 1 && np2.opositPos == np1.opositPos + incr;
        }
    }

    /**
     * Splits a way
     * 
     * @param layer
     * @param way
     * @param wayChunks
     * @return
     */
    private SplitWayResult splitWay(OsmDataLayer layer, Way way, List<List<Node>> wayChunks) {
        // build a list of commands, and also a new selection list
        Collection<Command> commandList = new ArrayList<>(wayChunks.size());

        Iterator<List<Node>> chunkIt = wayChunks.iterator();
        Collection<String> nowarnroles = Main.pref.getCollection("way.split.roles.nowarn",
                Arrays.asList(new String[] { "outer", "inner", "forward", "backward" }));

        // First, change the original way
        Way changedWay = new Way(way);
        oldWays.put(changedWay, way);
        changedWay.setNodes(chunkIt.next());
        commandList.add(new ChangeCommand(way, changedWay));

        List<Way> newWays = new ArrayList<>();
        // Second, create new ways
        while (chunkIt.hasNext()) {
            Way wayToAdd = new Way();
            wayToAdd.setKeys(way.getKeys());
            newWays.add(wayToAdd);
            wayToAdd.setNodes(chunkIt.next());
            commandList.add(new AddCommand(layer, wayToAdd));
        }
        boolean warnmerole = false;
        boolean warnme = false;
        // now copy all relations to new way also

        for (Relation r : getParentRelations(way)) {
            if (!r.isUsable()) {
                continue;
            }
            Relation c = null;
            String type = r.get("type");
            if (type == null) {
                type = "";
            }

            int ic = 0, ir = 0;
            List<RelationMember> relationMembers = r.getMembers();
            for (RelationMember rm : relationMembers) {
                if (rm.isWay() && rm.getMember() == way) {
                    boolean insert = true;
                    if ("restriction".equals(type)) {
                        /*
                         * this code assumes the restriction is correct. No real
                         * error checking done
                         */
                        String role = rm.getRole();
                        if ("from".equals(role) || "to".equals(role)) {
                            OsmPrimitive via = null;
                            for (RelationMember rmv : r.getMembers()) {
                                if ("via".equals(rmv.getRole())) {
                                    via = rmv.getMember();
                                }
                            }
                            List<Node> nodes = new ArrayList<>();
                            if (via != null) {
                                if (via instanceof Node) {
                                    nodes.add((Node) via);
                                } else if (via instanceof Way) {
                                    nodes.add(((Way) via).lastNode());
                                    nodes.add(((Way) via).firstNode());
                                }
                            }
                            Way res = null;
                            for (Node n : nodes) {
                                if (changedWay.isFirstLastNode(n)) {
                                    res = way;
                                }
                            }
                            if (res == null) {
                                for (Way wayToAdd : newWays) {
                                    for (Node n : nodes) {
                                        if (wayToAdd.isFirstLastNode(n)) {
                                            res = wayToAdd;
                                        }
                                    }
                                }
                                if (res != null) {
                                    if (c == null) {
                                        c = getNew(r);
                                    }
                                    c.addMember(new RelationMember(role, res));
                                    c.removeMembersFor(way);
                                    insert = false;
                                }
                            } else {
                                insert = false;
                            }
                        } else if (!"via".equals(role)) {
                            warnme = true;
                        }
                    } else if (!("route".equals(type)) && !("multipolygon".equals(type))) {
                        warnme = true;
                    }
                    if (c == null) {
                        c = getNew(r);
                    }

                    if (insert) {
                        if (rm.hasRole() && !nowarnroles.contains(rm.getRole())) {
                            warnmerole = true;
                        }

                        Boolean backwards = null;
                        int k = 1;
                        while (ir - k >= 0 || ir + k < relationMembers.size()) {
                            if ((ir - k >= 0) && relationMembers.get(ir - k).isWay()) {
                                Way w = relationMembers.get(ir - k).getWay();
                                if ((w.lastNode() == way.firstNode()) || w.firstNode() == way.firstNode()) {
                                    backwards = false;
                                } else if ((w.firstNode() == way.lastNode()) || w.lastNode() == way.lastNode()) {
                                    backwards = true;
                                }
                                break;
                            }
                            if ((ir + k < relationMembers.size()) && relationMembers.get(ir + k).isWay()) {
                                Way w = relationMembers.get(ir + k).getWay();
                                if ((w.lastNode() == way.firstNode()) || w.firstNode() == way.firstNode()) {
                                    backwards = true;
                                } else if ((w.firstNode() == way.lastNode()) || w.lastNode() == way.lastNode()) {
                                    backwards = false;
                                }
                                break;
                            }
                            k++;
                        }

                        int j = ic;
                        for (Way wayToAdd : newWays) {
                            RelationMember em = new RelationMember(rm.getRole(), wayToAdd);
                            j++;
                            if ((backwards != null) && backwards) {
                                c.addMember(ic, em);
                            } else {
                                c.addMember(j, em);
                            }
                        }
                        ic = j;
                    }
                }
                ic++;
                ir++;
            }

            if (c != null) {
                // commandList.add(new ChangeCommand(layer, r, c));
                newRelations.put(r, c);
            }
        }
        if (warnmerole) {
            JOptionPane.showMessageDialog(Main.parent,
                tr("<html>A role based relation membership was copied to all new ways.<br>You should verify this and correct it when necessary.</html>"),
                tr("Warning"), JOptionPane.WARNING_MESSAGE);
        } else if (warnme) {
            JOptionPane.showMessageDialog(Main.parent,
                tr("<html>A relation membership was copied to all new ways.<br>You should verify this and correct it when necessary.</html>"),
                tr("Warning"), JOptionPane.WARNING_MESSAGE);
        }

        return new SplitWayResult(new SequenceCommand(tr("Split way"), commandList), null, changedWay, newWays);
    }

    /**
     * @param ways
     * @return null if ways cannot be combined. Otherwise returns the combined
     *         ways and the commands to combine
     * @throws UserCancelException
     */
    private Pair<Way, List<Command>> combineWaysWorker(Collection<Way> ways) throws UserCancelException {

        // prepare and clean the list of ways to combine
        if (ways == null || ways.isEmpty())
            return null;
        ways.remove(null); // just in case - remove all null ways from the collection

        // remove duplicates, preserving order
        ways = new LinkedHashSet<>(ways);

        // try to build a new way which includes all the combined ways
        NodeGraph graph = NodeGraph.createUndirectedGraphFromNodeWays(ways);
        List<Node> path = graph.buildSpanningPath();

        // check whether any ways have been reversed in the process
        // and build the collection of tags used by the ways to combine
        TagCollection wayTags = TagCollection.unionOfAllPrimitives(ways);

        List<Way> reversedWays = new LinkedList<>();
        List<Way> unreversedWays = new LinkedList<>();
        for (Way w : ways) {
            if ((path.indexOf(w.getNode(0)) + 1) == path.lastIndexOf(w.getNode(1))) {
                unreversedWays.add(w);
            } else {
                reversedWays.add(w);
            }
        }
        // reverse path if all ways have been reversed
        if (unreversedWays.isEmpty()) {
            Collections.reverse(path);
            unreversedWays = reversedWays;
            reversedWays = null;
        }
        if ((reversedWays != null) && !reversedWays.isEmpty()) {
            // filter out ways that have no direction-dependent tags
            unreversedWays = ReverseWayTagCorrector.irreversibleWays(unreversedWays);
            reversedWays = ReverseWayTagCorrector.irreversibleWays(reversedWays);
            // reverse path if there are more reversed than unreversed ways with
            // direction-dependent tags
            if (reversedWays.size() > unreversedWays.size()) {
                Collections.reverse(path);
                List<Way> tempWays = unreversedWays;
                unreversedWays = reversedWays;
                reversedWays = tempWays;
            }
            // if there are still reversed ways with direction-dependent tags,
            // reverse their tags
            if (!reversedWays.isEmpty()) {
                List<Way> unreversedTagWays = new ArrayList<>(ways);
                unreversedTagWays.removeAll(reversedWays);
                ReverseWayTagCorrector reverseWayTagCorrector = new ReverseWayTagCorrector();
                List<Way> reversedTagWays = new ArrayList<>();
                Collection<Command> changePropertyCommands = null;
                for (Way w : reversedWays) {
                    Way wnew = new Way(w);
                    reversedTagWays.add(wnew);
                    changePropertyCommands = reverseWayTagCorrector.execute(w, wnew);
                }
                if ((changePropertyCommands != null) && !changePropertyCommands.isEmpty()) {
                    for (Command c : changePropertyCommands) {
                        c.executeCommand();
                    }
                }
                wayTags = TagCollection.unionOfAllPrimitives(reversedTagWays);
                wayTags.add(TagCollection.unionOfAllPrimitives(unreversedTagWays));
            }
        }

        // create the new way and apply the new node list
        Way targetWay = getTargetWay(ways);
        Way modifiedTargetWay = new Way(targetWay);
        modifiedTargetWay.setNodes(path);

        TagCollection completeWayTags = new TagCollection(wayTags);
        combineTigerTags(completeWayTags);
        normalizeTagCollectionBeforeEditing(completeWayTags, ways);
        TagCollection tagsToEdit = new TagCollection(completeWayTags);
        completeTagCollectionForEditing(tagsToEdit);

        MyCombinePrimitiveResolverDialog dialog = MyCombinePrimitiveResolverDialog.getInstance();
        dialog.getTagConflictResolverModel().populate(tagsToEdit, completeWayTags.getKeysWithMultipleValues());
        dialog.setTargetPrimitive(targetWay);
        Set<Relation> parentRelations = getParentRelations(ways);
        dialog.getRelationMemberConflictResolverModel().populate(parentRelations, ways, oldWays);
        dialog.prepareDefaultDecisions();

        // resolve tag conflicts if necessary
        if (askForMergeTag(ways) || duplicateParentRelations(ways)) {
            dialog.setVisible(true);
            if (dialog.isCanceled())
                throw new UserCancelException();
        }

        List<Command> cmds = new LinkedList<>();
        deletes.addAll(ways);
        deletes.remove(targetWay);

        cmds.add(new ChangeCommand(targetWay, modifiedTargetWay));
        cmds.addAll(dialog.buildWayResolutionCommands());
        dialog.buildRelationCorrespondance(newRelations, oldWays);

        return new Pair<>(targetWay, cmds);
    }

    private static Way getTargetWay(Collection<Way> combinedWays) {
        // init with an arbitrary way
        Way targetWay = combinedWays.iterator().next();

        // look for the first way already existing on the server
        for (Way w : combinedWays) {
            targetWay = w;
            if (!w.isNew()) {
                break;
            }
        }
        return targetWay;
    }

    /**
     * @return has tag to be merged (=> ask)
     */
    private static boolean askForMergeTag(Collection<Way> ways) {
        for (Way way : ways) {
            for (Way oposite : ways) {
                for (String key : way.getKeys().keySet()) {
                    if (!"source".equals(key) && oposite.hasKey(key)
                            && !way.get(key).equals(oposite.get(key))) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    /**
     * @return has duplicate parent relation
     */
    private boolean duplicateParentRelations(Collection<Way> ways) {
        Set<Relation> relations = new HashSet<>();
        for (Way w : ways) {
            List<Relation> rs = getParentRelations(w);
            for (Relation r : rs) {
                if (relations.contains(r)) {
                    return true;
                }
            }
            relations.addAll(rs);
        }
        return false;
    }

    /**
     * Replies the set of referring relations
     * 
     * @return the set of referring relations
     */
    private List<Relation> getParentRelations(Way way) {
        List<Relation> rels = new ArrayList<>();
        for (Relation r : relations.get(way)) {
            if (newRelations.containsKey(r)) {
                rels.add(newRelations.get(r));
            } else {
                rels.add(r);
            }
        }
        return rels;
    }

    private Relation getNew(Relation r) {
        return getNew(r, newRelations);
    }

    public static Relation getNew(Relation r, Map<Relation, Relation> newRelations) {
        if (newRelations.containsValue(r)) {
            return r;
        } else {
            Relation c = new Relation(r);
            newRelations.put(r, c);
            return c;
        }
    }
/*
    private Way getOld(Way r) {
        return getOld(r, oldWays);
    }*/

    public static Way getOld(Way w, Map<Way, Way> oldWays) {
        if (oldWays.containsKey(w)) {
            return oldWays.get(w);
        } else {
            return w;
        }
    }

    /**
     * Replies the set of referring relations
     * 
     * @return the set of referring relations
     */
    private Set<Relation> getParentRelations(Collection<Way> ways) {
        Set<Relation> ret = new HashSet<>();
        for (Way w : ways) {
            ret.addAll(getParentRelations(w));
        }
        return ret;
    }

    /** Enable this action only if something is selected */
    @Override
    protected void updateEnabledState() {
        if (getCurrentDataSet() == null) {
            setEnabled(false);
        } else {
            updateEnabledState(getCurrentDataSet().getSelected());
        }
    }

    /** Enable this action only if something is selected */
    @Override
    protected void updateEnabledState(
            Collection<? extends OsmPrimitive> selection) {
        if (selection == null) {
            setEnabled(false);
            return;
        }
        for (OsmPrimitive primitive : selection) {
            if (!(primitive instanceof Way) || primitive.isDeleted()) {
                setEnabled(false);
                return;
            }
        }
        setEnabled(selection.size() >= 2);
    }
}