source: osm/applications/editors/josm/plugins/reltoolbox/src/relcontext/actions/TheRing.java

// License: GPL. For details, see LICENSE file.
package relcontext.actions;

import static org.openstreetmap.josm.tools.I18n.tr;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import javax.swing.JOptionPane;

import org.openstreetmap.josm.command.AddCommand;
import org.openstreetmap.josm.command.ChangeCommand;
import org.openstreetmap.josm.command.ChangeMembersCommand;
import org.openstreetmap.josm.command.ChangeNodesCommand;
import org.openstreetmap.josm.command.ChangePropertyCommand;
import org.openstreetmap.josm.command.Command;
import org.openstreetmap.josm.command.DeleteCommand;
import org.openstreetmap.josm.data.osm.DataSet;
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.Way;
import org.openstreetmap.josm.gui.MainApplication;
import org.openstreetmap.josm.spi.preferences.Config;
import org.openstreetmap.josm.tools.Geometry;
import org.openstreetmap.josm.tools.Geometry.PolygonIntersection;
import org.openstreetmap.josm.tools.Logging;

/**
 * One ring that contains segments forming an outer way of multipolygon.
 * This class is used in {@link CreateMultipolygonAction#makeManySimpleMultipolygons(java.util.Collection)}.
 *
 * @author Zverik
 */
public class TheRing {
    private static final String PREF_MULTIPOLY = "reltoolbox.multipolygon.";

    private final Way source;
    private final List<RingSegment> segments;
    private Relation relation;

    public TheRing(Way source) {
        this.source = source;
        segments = new ArrayList<>(1);
        segments.add(new RingSegment(source));
    }

    public static boolean areAllOfThoseRings(Collection<Way> ways) {
        List<Way> rings = new ArrayList<>();
        for (Way way : ways) {
            if (way.isClosed()) {
                rings.add(way);
            } else
                return false;
        }
        if (rings.isEmpty() || ways.size() == 1)
            return false;

        // check for non-containment of rings
        for (int i = 0; i < rings.size() - 1; i++) {
            for (int j = i + 1; j < rings.size(); j++) {
                PolygonIntersection intersection = Geometry.polygonIntersection(rings.get(i).getNodes(), rings.get(j).getNodes());
                if (intersection == PolygonIntersection.FIRST_INSIDE_SECOND || intersection == PolygonIntersection.SECOND_INSIDE_FIRST)
                    return false;
            }
        }

        return true;
    }

    /**
     * Creates ALOT of Multipolygons and pets him gently.
     * @return list of new relations.
     */
    public static List<Relation> makeManySimpleMultipolygons(Collection<Way> selection, List<Command> commands) {
        log("---------------------------------------");
        List<TheRing> rings = new ArrayList<>(selection.size());
        for (Way w : selection) {
            rings.add(new TheRing(w));
        }
        for (int i = 0; i < rings.size() - 1; i++) {
            for (int j = i + 1; j < rings.size(); j++) {
                rings.get(i).collide(rings.get(j));
            }
        }
        redistributeSegments(rings);
        List<Relation> relations = new ArrayList<>();
        Map<Relation, Relation> relationCache = new HashMap<>();
        for (TheRing r : rings) {
            commands.addAll(r.getCommands(relationCache));
            relations.add(r.getRelation());
        }
        updateCommandsWithRelations(commands, relationCache);
        return relations;
    }

    public void collide(TheRing other) {
        boolean collideNoted = false;
        for (int i = 0; i < segments.size(); i++) {
            RingSegment segment1 = segments.get(i);
            if (!segment1.isReference()) {
                for (int j = 0; j < other.segments.size(); j++) {
                    RingSegment segment2 = other.segments.get(j);
                    if (!segment2.isReference()) {
                        log("Comparing " + segment1 + " and " + segment2);
                        Node[] split = getSplitNodes(segment1.getNodes(), segment2.getNodes(), segment1.isRing(), segment2.isRing());
                        if (split != null) {
                            if (!collideNoted) {
                                log("Rings for ways " + source.getUniqueId() + " and " + other.source.getUniqueId() + " collide.");
                                collideNoted = true;
                            }
                            RingSegment segment = splitRingAt(i, split[0], split[1]);
                            RingSegment otherSegment = other.splitRingAt(j, split[2], split[3]);
                            if (!areSegmentsEqual(segment, otherSegment))
                                throw new IllegalArgumentException(
                                        "Error: algorithm gave incorrect segments: " + segment + " and " + otherSegment);
                            segment.makeReference(otherSegment);
                        }
                    }
                    if (segment1.isReference()) {
                        break;
                    }
                }
            }
        }
    }

    /**
     * Returns array of {start1, last1, start2, last2} or null if there is no common nodes.
     */
    public static Node[] getSplitNodes(List<Node> nodes1, List<Node> nodes2, boolean isRing1, boolean isRing2) {
        int pos = 0;
        while (pos < nodes1.size() && !nodes2.contains(nodes1.get(pos))) {
            pos++;
        }
        boolean collideFound = pos == nodes1.size();
        if (pos == 0 && isRing1) {
            // rewind a bit
            pos = nodes1.size() - 1;
            while (pos > 0 && nodes2.contains(nodes1.get(pos))) {
                pos--;
            }
            if (pos == 0 && nodes1.size() == nodes2.size()) {
                JOptionPane.showMessageDialog(MainApplication.getMainFrame(),
                        tr("Two rings are equal, and this must not be."), tr("Multipolygon from rings"), JOptionPane.ERROR_MESSAGE);
                return null;
            }
            pos = pos == nodes1.size() - 1 ? 0 : pos + 1;
        }
        int firstPos = isRing1 ? pos : nodes1.size();
        while (!collideFound) {
            log("pos=" + pos);
            int start1 = pos;
            int start2 = nodes2.indexOf(nodes1.get(start1));
            int last1 = incrementBy(start1, 1, nodes1.size(), isRing1);
            int last2 = start2;
            int increment2 = 0;
            if (last1 >= 0) {
                last2 = incrementBy(start2, -1, nodes2.size(), isRing2);
                if (last2 >= 0 && nodes1.get(last1).equals(nodes2.get(last2))) {
                    increment2 = -1;
                } else {
                    last2 = incrementBy(start2, 1, nodes2.size(), isRing2);
                    if (last2 >= 0 && nodes1.get(last1).equals(nodes2.get(last2))) {
                        increment2 = 1;
                    }
                }
            }
            log("last1=" + last1 + " last2=" + last2 + " increment2=" + increment2);
            if (increment2 != 0) {
                // find the first nodes
                boolean reachedEnd = false;
                while (!reachedEnd) {
                    int newLast1 = incrementBy(last1, 1, nodes1.size(), isRing1);
                    int newLast2 = incrementBy(last2, increment2, nodes2.size(), isRing2);
                    if (newLast1 < 0 || newLast2 < 0 || !nodes1.get(newLast1).equals(nodes2.get(newLast2))) {
                        reachedEnd = true;
                    } else {
                        last1 = newLast1;
                        last2 = newLast2;
                    }
                }
                log("last1=" + last1 + " last2=" + last2);
                if (increment2 < 0) {
                    int tmp = start2;
                    start2 = last2;
                    last2 = tmp;
                }
                return new Node[] {nodes1.get(start1), nodes1.get(last1), nodes2.get(start2), nodes2.get(last2)};
            } else {
                pos = last1;
                while (pos != firstPos && pos >= 0 && !nodes2.contains(nodes1.get(pos))) {
                    pos = incrementBy(pos, 1, nodes1.size(), isRing1);
                }
                if (pos < 0 || pos == firstPos || !nodes2.contains(nodes1.get(pos))) {
                    collideFound = true;
                }
            }
        }
        return null;
    }

    private static int incrementBy(int value, int increment, int limit1, boolean isRing) {
        int result = value + increment;
        if (result < 0)
            return isRing ? result + limit1 : -1;
        else if (result >= limit1)
            return isRing ? result - limit1 : -1;
        else
            return result;
    }

    private static boolean areSegmentsEqual(RingSegment seg1, RingSegment seg2) {
        List<Node> nodes1 = seg1.getNodes();
        List<Node> nodes2 = seg2.getNodes();
        int size = nodes1.size();
        if (size != nodes2.size())
            return false;
        boolean reverse = size > 1 && !nodes1.get(0).equals(nodes2.get(0));
        for (int i = 0; i < size; i++) {
            if (!nodes1.get(i).equals(nodes2.get(reverse ? size-1-i : i)))
                return false;
        }
        return true;
    }

    /**
     * Split the segment in this ring at those nodes.
     * @return The segment between nodes.
     */
    private RingSegment splitRingAt(int segmentIndex, Node n1, Node n2) {
        if (n1.equals(n2))
            throw new IllegalArgumentException("Both nodes are equal, id=" + n1.getUniqueId());
        RingSegment segment = segments.get(segmentIndex);
        boolean isRing = segment.isRing();
        log("Split segment " + segment + " at nodes " + n1.getUniqueId() + " and " + n2.getUniqueId());
        boolean reversed = segment.getNodes().indexOf(n2) < segment.getNodes().indexOf(n1);
        if (reversed && !isRing) {
            // order nodes
            Node tmp = n1;
            n1 = n2;
            n2 = tmp;
        }
        RingSegment secondPart = isRing ? segment.split(n1, n2) : segment.split(n1);
        // if secondPart == null, then n1 == firstNode
        RingSegment thirdPart = isRing ? null : secondPart == null ? segment.split(n2) : secondPart.split(n2);
        // if secondPart == null, then thirdPart is between n1 and n2
        // otherwise, thirdPart is between n2 and lastNode
        // if thirdPart == null, then n2 == lastNode
        int pos = segmentIndex + 1;
        if (secondPart != null) {
            segments.add(pos++, secondPart);
        }
        if (thirdPart != null) {
            segments.add(pos++, thirdPart);
        }
        return isRing || secondPart == null ? segment : secondPart;
    }

    /**
     * Tries to arrange segments in order for each ring to have at least one.
     * Also, sets source way for all rings.
     * <p>
     * If this method is not called, do not forget to call {@link #putSourceWayFirst()} for all rings.
     */
    public static void redistributeSegments(List<TheRing> rings) {
        // build segments map
        Map<RingSegment, TheRing> segmentMap = new HashMap<>();
        for (TheRing ring : rings) {
            for (RingSegment seg : ring.segments) {
                if (!seg.isReference()) {
                    segmentMap.put(seg, ring);
                }
            }
        }

        // rearrange references
        for (TheRing ring : rings) {
            if (ring.countNonReferenceSegments() == 0) {
                // need to find one non-reference segment
                for (RingSegment seg : ring.segments) {
                    TheRing otherRing = segmentMap.get(seg.references);
                    if (otherRing.countNonReferenceSegments() > 1) {
                        // we could check for >0, but it is prone to deadlocking
                        seg.swapReference();
                    }
                }
            }
        }

        // initializing source way for each ring
        for (TheRing ring : rings) {
            ring.putSourceWayFirst();
        }
    }

    private int countNonReferenceSegments() {
        int count = 0;
        for (RingSegment seg : segments) {
            if (!seg.isReference()) {
                count++;
            }
        }
        return count;
    }

    public void putSourceWayFirst() {
        for (RingSegment seg : segments) {
            if (!seg.isReference()) {
                seg.overrideWay(source);
                return;
            }
        }
    }

    public List<Command> getCommands() {
        return getCommands(true, null);
    }

    public List<Command> getCommands(Map<Relation, Relation> relationChangeMap) {
        return getCommands(true, relationChangeMap);
    }

    /**
     * Returns a list of commands to make a new relation and all newly created ways.
     * The first way is copied from the source one, ChangeCommand is issued in this case.
     */
    public List<Command> getCommands(boolean createMultipolygon, Map<Relation, Relation> relationChangeMap) {
        Way sourceCopy = new Way(source);
        Map<String, String> tagsToRemove = new HashMap<>();
        if (createMultipolygon) {
            Collection<String> linearTags = Config.getPref().getList(PREF_MULTIPOLY + "lineartags",
                    CreateMultipolygonAction.DEFAULT_LINEAR_TAGS);
            relation = new Relation();
            relation.put("type", "multipolygon");
            for (String key : source.keySet()) {
                if (linearTags.contains(key)
                        || ("natural".equals(key) && "coastline".equals(source.get("natural"))))
                    continue;
                
                relation.put(key, source.get(key));
                sourceCopy.remove(key);
                tagsToRemove.put(key, null);
            }
        }

        // build a map of referencing relations
        Map<Relation, Integer> referencingRelations = new HashMap<>();
        List<Command> relationCommands = new ArrayList<>();
        for (OsmPrimitive p : source.getReferrers()) {
            if (p instanceof Relation) {
                Relation rel;
                if (relationChangeMap != null) {
                    rel = relationChangeMap.get(p);
                    if (rel == null) {
                        rel = new Relation((Relation) p);
                        relationChangeMap.put((Relation) p, rel);
                    }
                } else {
                    rel = new Relation((Relation) p);
                    relationCommands.add(new ChangeCommand(p, rel)); // should not happen 
                }
                for (int i = 0; i < rel.getMembersCount(); i++) {
                    if (rel.getMember(i).getMember().equals(source)) {
                        referencingRelations.put(rel, i);
                    }
                }
            }
        }

        DataSet ds = MainApplication.getLayerManager().getEditDataSet();
        List<Command> commands = new ArrayList<>();
        boolean foundOwnWay = false;
        for (RingSegment seg : segments) {
            boolean needAdding = !seg.isWayConstructed();
            Way w = seg.constructWay(seg.isReference() ? null : sourceCopy);
            if (needAdding) {
                commands.add(new AddCommand(ds, w));
            }
            if (w.equals(source)) {
                if (createMultipolygon || !seg.getWayNodes().equals(source.getNodes())) {
                    sourceCopy.setNodes(seg.getWayNodes());
                    if (!tagsToRemove.isEmpty()) {
                        commands.add(new ChangePropertyCommand(Collections.singleton(source), tagsToRemove));
                    }
                    if (!sourceCopy.getNodes().equals(source.getNodes()))
                        commands.add(new ChangeNodesCommand(source, sourceCopy.getNodes()));
                }
                foundOwnWay = true;
            } else {
                for (Map.Entry<Relation, Integer> entry : referencingRelations.entrySet()) {
                    Relation rel = entry.getKey();
                    int relIndex = entry.getValue();
                    rel.addMember(new RelationMember(rel.getMember(relIndex).getRole(), w));
                }
            }
            if (createMultipolygon) {
                relation.addMember(new RelationMember("outer", w));
            }
        }
        sourceCopy.setNodes(null); // see #19885
        if (!foundOwnWay) {
            final Command deleteCommand = DeleteCommand.delete(Collections.singleton(source));
            if (deleteCommand != null) {
                commands.add(deleteCommand);
            }
        }
        commands.addAll(relationCommands);
        if (createMultipolygon) {
            commands.add(new AddCommand(ds, relation));
        }
        return commands;
    }

    public static void updateCommandsWithRelations(List<Command> commands, Map<Relation, Relation> relationCache) {
        for (Map.Entry<Relation, Relation> entry : relationCache.entrySet()) {
            Relation oldRel = entry.getKey();
            Relation newRel = entry.getValue();
            if (oldRel.getKeys().equals(newRel.getKeys())) {
                commands.add(new ChangeMembersCommand(oldRel, newRel.getMembers()));
                newRel.setMembers(null); // see #19885
            } else {
                commands.add(new ChangeCommand(oldRel, newRel)); // should not happen
            }
        }
    }

    /**
     * Returns the relation created in {@link #getCommands()}.
     */
    public Relation getRelation() {
        return relation;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("TheRing@");
        sb.append(this.hashCode()).append('[').append("wayId: ").append(source == null ? "null" : source.getUniqueId()).append("; segments: ");
        if (segments.isEmpty()) {
            sb.append("empty");
        } else {
            sb.append(segments.get(0));
            for (int i = 1; i < segments.size(); i++) {
                sb.append(", ").append(segments.get(i));
            }
        }
        return sb.append(']').toString();
    }

    private static void log(String s) {
        Logging.debug(s);
    }

    private static class RingSegment {
        private List<Node> nodes;
        private RingSegment references;
        private Way resultingWay;
        private boolean wasTemplateApplied;
        private boolean isRing;

        RingSegment(Way w) {
            this(w.getNodes());
        }

        RingSegment(List<Node> nodes) {
            this.nodes = nodes;
            isRing = nodes.size() > 1 && nodes.get(0).equals(nodes.get(nodes.size() - 1));
            if (isRing) {
                nodes.remove(nodes.size() - 1);
            }
            references = null;
        }

        /**
         * Splits this segment at node n. Retains nodes 0..n and moves
         * nodes n..N to a separate segment that is returned.
         * @param n node at which to split.
         * @return new segment, {@code null} if splitting is unnecessary.
         */
        public RingSegment split(Node n) {
            if (nodes == null)
                throw new IllegalArgumentException("Cannot split segment: it is a reference");
            int pos = nodes.indexOf(n);
            if (pos <= 0 || pos >= nodes.size() - 1)
                return null;
            List<Node> newNodes = new ArrayList<>(nodes.subList(pos, nodes.size()));
            nodes.subList(pos + 1, nodes.size()).clear();
            return new RingSegment(newNodes);
        }

        /**
         * Split this segment as a way at two nodes. If one of them is null or at the end,
         * split as an arc. Note: order of nodes is important.
         * @return A new segment from n2 to n1.
         */
        public RingSegment split(Node n1, Node n2) {
            if (nodes == null)
                throw new IllegalArgumentException("Cannot split segment: it is a reference");
            if (!isRing) {
                if (n1 == null || nodes.get(0).equals(n1) || nodes.get(nodes.size() - 1).equals(n1))
                    return split(n2);
                if (n2 == null || nodes.get(0).equals(n2) || nodes.get(nodes.size() - 1).equals(n2))
                    return split(n1);
                throw new IllegalArgumentException("Split for two nodes is called for not-ring: " + this);
            }
            int pos1 = nodes.indexOf(n1);
            int pos2 = nodes.indexOf(n2);
            if (pos1 == pos2)
                return null;

            List<Node> newNodes = new ArrayList<>();
            if (pos2 > pos1) {
                newNodes.addAll(nodes.subList(pos2, nodes.size()));
                newNodes.addAll(nodes.subList(0, pos1 + 1));
                if (pos2 + 1 < nodes.size()) {
                    nodes.subList(pos2 + 1, nodes.size()).clear();
                }
                if (pos1 > 0) {
                    nodes.subList(0, pos1).clear();
                }
            } else {
                newNodes.addAll(nodes.subList(pos2, pos1 + 1));
                nodes.addAll(new ArrayList<>(nodes.subList(0, pos2 + 1)));
                nodes.subList(0, pos1).clear();
            }
            isRing = false;
            return new RingSegment(newNodes);
        }

        public List<Node> getNodes() {
            return nodes == null ? references.nodes : nodes;
        }

        public List<Node> getWayNodes() {
            if (nodes == null)
                throw new IllegalArgumentException("Won't give you wayNodes: it is a reference");
            List<Node> wayNodes = new ArrayList<>(nodes);
            if (isRing) {
                wayNodes.add(wayNodes.get(0));
            }
            return wayNodes;
        }

        public boolean isReference() {
            return nodes == null;
        }

        public boolean isRing() {
            return isRing;
        }

        public void makeReference(RingSegment segment) {
            log(this + " was made a reference to " + segment);
            this.nodes = null;
            this.references = segment;
        }

        public void swapReference() {
            this.nodes = references.nodes;
            references.nodes = null;
            references.references = this;
            this.references = null;
        }

        public boolean isWayConstructed() {
            return isReference() ? references.isWayConstructed() : resultingWay != null;
        }

        public Way constructWay(Way template) {
            if (isReference())
                return references.constructWay(template);
            if (resultingWay == null) {
                resultingWay = new Way();
                resultingWay.setNodes(getWayNodes());
            }
            if (template != null && !wasTemplateApplied) {
                resultingWay.setKeys(template.getKeys());
                wasTemplateApplied = true;
            }
            return resultingWay;
        }

        public void overrideWay(Way source) {
            if (isReference()) {
                references.overrideWay(source);
            } else {
                resultingWay = source;
                wasTemplateApplied = true;
            }
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder("RingSegment@");
            sb.append(this.hashCode()).append('[');
            if (isReference()) {
                sb.append("references ").append(references.hashCode());
            } else if (nodes.isEmpty()) {
                sb.append("empty");
            } else {
                if (isRing) {
                    sb.append("ring:");
                }
                sb.append(nodes.get(0).getUniqueId());
                for (int i = 1; i < nodes.size(); i++) {
                    sb.append(',').append(nodes.get(i).getUniqueId());
                }
            }
            return sb.append(']').toString();
        }
    }
}