package relcontext.actions;

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

import javax.swing.JOptionPane;

import org.openstreetmap.josm.Main;
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.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.tools.Geometry;
import org.openstreetmap.josm.tools.Geometry.PolygonIntersection;

/**
 * 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 Way source;
    private List<RingSegment> segments;
    private Relation relation = null;

    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(Main.parent, "Two rings are equal, and this must not be.", "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 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.
     * 
     * 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( int i = 0; i < rings.size(); i++ ) {
        TheRing ring = rings.get(i);
        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);
    if( createMultipolygon ) {
        Collection<String> linearTags = Main.pref.getCollection(PREF_MULTIPOLY + "lineartags", CreateMultipolygonAction.DEFAULT_LINEAR_TAGS);
        relation = new Relation();
        relation.put("type", "multipolygon");
        for( String key : sourceCopy.keySet() ) {
                if( linearTags.contains(key) ) continue;
                if( key.equals("natural") && sourceCopy.get("natural").equals("coastline") ) continue;
                relation.put(key, sourceCopy.get(key));
                sourceCopy.remove(key);
        }
    }

    // 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 = null;
        if( relationChangeMap != null ) {
            if( relationChangeMap.containsKey((Relation)p) )
            rel = relationChangeMap.get((Relation)p);
            else {
            rel = new Relation((Relation)p);
            relationChangeMap.put((Relation)p, rel);
            }
        } else {            
            rel = new Relation((Relation)p);
            relationCommands.add(new ChangeCommand((Relation)p, rel));
        }
        for( int i = 0; i < rel.getMembersCount(); i++ )
            if( rel.getMember(i).getMember().equals(source) )
            referencingRelations.put(rel, Integer.valueOf(i));
        }
    }
    // todo: когда два кольца мен�ют одно и то же отношение, в �пи�ок команд добавл�ет��
    // изменение базового отношени� на новое, а не предыдущего
    // по�тому �охран�ет�� только первое изменение

    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(w));
        if( w.equals(source) ) {
        if( createMultipolygon || !seg.getWayNodes().equals(source.getNodes()) ) {
            sourceCopy.setNodes(seg.getWayNodes());
            commands.add(new ChangeCommand(source, sourceCopy));
        }
        foundOwnWay = true;
        } else {
        for( Relation rel : referencingRelations.keySet() ) {
            int relIndex = referencingRelations.get(rel);
            rel.addMember(new RelationMember(rel.getMember(relIndex).getRole(), w));
        }
        }
        if( createMultipolygon )
        relation.addMember(new RelationMember("outer", w));
    }
    if( !foundOwnWay )
        commands.add(new DeleteCommand(source));
    commands.addAll(relationCommands);
    if( createMultipolygon )
        commands.add(new AddCommand(relation));
    return commands;
    }
    
    public static void updateCommandsWithRelations( List<Command> commands, Map<Relation, Relation> relationCache ) {
    for( Relation src : relationCache.keySet() )
        commands.add(new ChangeCommand(src, relationCache.get(src)));
    }

    /**
     * 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();
    }

    /**
     * Appends "append" to "base" so the closed polygon forms.
     */
    /*private static void closePolygon( List<Node> base, List<Node> append ) {
    if( append.get(0).equals(base.get(0)) && append.get(append.size() - 1).equals(base.get(base.size() - 1)) ) {
        List<Node> ap2 = new ArrayList<Node>(append);
        Collections.reverse(ap2);
        append = ap2;
    }
    base.remove(base.size() - 1);
    base.addAll(append);
    }*/

    /**
     * Checks if a middle point between two nodes is inside a polygon. Useful to check if the way is inside.
     */
    /*private static boolean segmentInsidePolygon( Node n1, Node n2, List<Node> polygon ) {
    EastNorth en1 = n1.getEastNorth();
    EastNorth en2 = n2.getEastNorth();
    Node testNode = new Node(new EastNorth((en1.east() + en2.east()) / 2.0, (en1.north() + en2.north()) / 2.0));
    return Geometry.nodeInsidePolygon(testNode, polygon);
    }*/
    
    private static void log( String s ) {
//    System.out.println(s);
    }
    
    private static class RingSegment {
    private List<Node> nodes;
    private RingSegment references;
    private Way resultingWay = null;
    private boolean wasTemplateApplied = false;
    private boolean isRing;

    /*private RingSegment() {
    }*/

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

    public 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;
    }

    /*public RingSegment( RingSegment ref ) {
        this.nodes = null;
        this.references = ref;
    }*/

    /**
     * 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;
        }
    }

    /**
     * Compares two segments with respect to referencing.
     * @return true if ways are equals, or one references another.
     */
    /*public boolean isReferencingEqual( RingSegment other ) {
        return this.equals(other) || (other.isReference() && other.references == this) || (isReference() && references == other);
    }*/

    @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();
    }
    }
}