package org.openstreetmap.josm.actions;

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

import java.awt.event.ActionEvent;
import java.awt.event.KeyEvent;
import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Vector;

import javax.swing.JOptionPane;

import org.openstreetmap.josm.Main;
import org.openstreetmap.josm.command.ChangeCommand;
import org.openstreetmap.josm.command.Command;
import org.openstreetmap.josm.command.SequenceCommand;
import org.openstreetmap.josm.data.osm.Node;
import org.openstreetmap.josm.data.osm.OsmPrimitive;
import org.openstreetmap.josm.data.osm.Segment;
import org.openstreetmap.josm.data.osm.Way;
import org.openstreetmap.josm.data.osm.visitor.Visitor;

public class DirectAllWaySegmentsAction extends JosmAction {

	public DirectAllWaySegmentsAction() {
		super(tr("Direct all way segments"), "reorder", tr("Try to direct all way segments so that they face the same direction."), KeyEvent.VK_S, KeyEvent.CTRL_DOWN_MASK | KeyEvent.ALT_DOWN_MASK, true);
    }
	
	/**
	 * This method first sorts all the segments in a way, then makes sure that all 
	 * the segments are facing the same direction as the first one.
	 */
	public void actionPerformed(ActionEvent e) {
		Collection<Way> ways = new LinkedList<Way>();
		for (OsmPrimitive osm : Main.ds.getSelected())
			if (osm instanceof Way)
				ways.add((Way)osm);
		if (ways.size() < 1) {
			JOptionPane.showMessageDialog(Main.parent, tr("Please select at least one way."));
			return;
		}
		if (ways.size() > 1) {
			int answer = JOptionPane.showConfirmDialog(Main.parent, tr("You selected more than one way. Reorder the segments of {0} ways?"), tr("Reorder segments"), JOptionPane.OK_CANCEL_OPTION);
			if (answer != JOptionPane.OK_OPTION)
				return;
		}
		for (Way way : ways) {
			Way newWay = new Way(way);
			newWay.segments.clear();
			newWay.segments.addAll(sortSegments(new HashSet<Segment>(way.segments)));
			
			final LinkedList<Segment> sel = new LinkedList<Segment>();
	    	new Visitor(){
				public void visit(Node n)    {}
				public void visit(Segment s) {sel.add(s);}
				public void visit(Way w)     {sel.addAll(w.segments);}
	    	}.visit(newWay);

	    	Collection<Command> c = new LinkedList<Command>();

	    	boolean direction = false;
	    	if ( sel.size() >= 2 )
	    	{
	    		Node lastNode = null;
	    		// first we work out the direction the first segment is facing, the rest all face that way
	    		Segment firstSegment = sel.getFirst();
	    		Segment secondSegment = sel.get(1);
	    		direction = firstSegment.to == secondSegment.from || firstSegment.to == secondSegment.to;
	    		if ( direction ) // direction = true when 'from' is the first node in the Way
	    			lastNode = firstSegment.to;
	    		else
	    			lastNode = firstSegment.from;
	    		boolean ignoreSegment = true;
		    	for (Segment s : sel) {
		    		if ( !ignoreSegment ) // don't order the first segment
		    		{
		    			Segment snew = new Segment(s);
		    			boolean segDirection = s.from == lastNode;
		    			// segDirection = true when the 'from' node occurs before the 'to' node in the Way 
		    			if ( direction != segDirection )
		    			{    			
		    				// reverse the node's direction
		    				Node n = snew.from;
		    				snew.from = snew.to;
		    				snew.to = n;
		    				c.add(new ChangeCommand(s, snew));
		    			}	
		    			
			    		if ( direction ) // if its facing forwards,
			    			lastNode = snew.to; // our next node is the 'to' one
			    		else
			    			lastNode = snew.from; // otherwise its the 'from' one
		    		}
		    		else
		    			ignoreSegment = false;
		    	}
	    	}
	    	
	    	LinkedList<Segment> segments = new LinkedList<Segment>();
	    	
    		for (Segment s : sel) 
    			if ( !direction ) 
    				segments.addFirst(s);
    			else
    				segments.addLast(s);
    			
	    	Way newWay2 = new Way(way);
	    	newWay2.segments.clear();
			newWay2.segments.addAll(segments);
			c.add(new ChangeCommand(way, newWay2));	

	    	Main.main.editLayer().add(new SequenceCommand(tr("Direct all way segments"), c));
	    	
    	

		}
		Main.map.repaint();
	}

	/**
	 * sort the segments in best possible order. This is done by:
	 * 0  if no elements in list, quit
	 * 1  taking the first ls as pivot, remove it from list
	 * 2  searching for a connection at from or to of pivot
	 * 3  if found, attach it, remove it from list, goto 2
	 * 4  if not found, save the pivot-string and goto 0
	 */
	public static LinkedList<Segment> sortSegments(HashSet<Segment> segmentSet) {
		LinkedList<Segment> sortedSegments = new LinkedList<Segment>();
		LinkedList<Segment> segments = new LinkedList<Segment>(segmentSet);
		while (!segments.isEmpty()) {
			LinkedList<Segment> pivotList = new LinkedList<Segment>();
			pivotList.add(segments.getFirst());
			segments.removeFirst();
			for (boolean found = true; found;) {
				found = false;
				for (Iterator<Segment> it = segments.iterator(); it.hasNext();) {
					Segment ls = it.next();
					if (ls.incomplete)
						continue; // incomplete segments are never added to a new way
					if (ls.from == pivotList.getLast().to || ls.to == pivotList.getLast().to || ls.from == pivotList.getLast().from || ls.to == pivotList.getLast().from) {
						pivotList.addLast(ls);
						it.remove();
						found = true;
					} else if (ls.to == pivotList.getFirst().from || ls.from == pivotList.getFirst().from || ls.to == pivotList.getFirst().to || ls.from == pivotList.getFirst().to) {
						pivotList.addFirst(ls);
						it.remove(); 
						found = true;
					}
				}
			}
			sortedSegments.addAll(pivotList);
		}
	    return sortedSegments;
    }
}