import java.awt.*;

public class MapList
{
	String name;
	ConnectionList connections;
	MapList next;
	int xPos;
	int yPos;

	public MapList(String NAME, int X, int Y)
	{
		name = NAME;
		xPos = X;
		yPos = Y;
		next = null;
		connections = null;
	}

	public MapList addMapListNode( String NAME, int X, int Y)
	{
		MapList newMapListNode = new MapList(NAME, X, Y);
		newMapListNode.next = next;
		next = newMapListNode;
		return newMapListNode;
	}

	public void addConnection( String FROMNODE, String TONODE, int COST )
	{
		ConnectionList newConnection = new ConnectionList( FROMNODE, TONODE, COST );
		newConnection.next = connections;
		connections = newConnection;
	}

	public MapList findMapNode ( String s)
	{
		MapList TempMapList = this;
		while( TempMapList != null )
		{
			if (TempMapList.name.equalsIgnoreCase( s ))
				return TempMapList;
			else
				TempMapList = TempMapList.next;
		}
		return null;
			
	}

	public SolutionList Solve( String fromName, String toName, Graphics g, SolutionList SOLUTIONPATH, MapList MAPNODESTOTRY, ConnectionList CONNECTIONSTOTRY )
	{
		SolutionList SolutionPath = SOLUTIONPATH;
		ConnectionList ConnectionsToTry = CONNECTIONSTOTRY;
		MapList MapsToTry = MAPNODESTOTRY;

		if ( ( fromName.equalsIgnoreCase( toName ) ) ){ 
			SolutionPath.addNode( toName );
			if ( SolutionPath != null ){
				g.setColor ( Color.green );
				SolutionPath.drawlist( g , MapsToTry);
				SolutionPath.wait( 1000 );
				g.setColor ( Color.black );
				SolutionPath.drawlist( g , MapsToTry);
			}
			return SolutionPath;
		}
		else {
			if ( SolutionPath != null ){
				if ( ( SolutionPath.findNode( fromName ) && !( SolutionPath.name.equalsIgnoreCase( fromName ) ) ) ){
					if ( SolutionPath.findNode( toName ) ){
						return null;
					}
					else{
						if ( ( SolutionPath.findNode( fromName ) ) && !( SolutionPath.lastNode().name.equals( fromName ) ) ){
							SolutionPath.addNode( fromName );
							g.setColor ( Color.red );
							SolutionPath.drawlist( g , MapsToTry);
							g.setColor ( Color.black );
							SolutionPath.wait( 1000 );
							SolutionPath.drawlist( g , MapsToTry);
						}
						return null;
					}
					
				}
			}
			if ( MapsToTry == null  ) return null;
			if ( ConnectionsToTry == null ) return  null;
			SolutionList SolutionPathHead;
			if ( SolutionPath == null ){
				SolutionPath = new SolutionList( fromName, 0 );
			}
			SolutionPathHead = SolutionPath.copy();
			SolutionPathHead.addNode( fromName, ConnectionsToTry.cost );
			//SolutionPath.addNode( fromName, ConnectionsToTry.cost );
			MapList MapNodeToTryHead = MapsToTry.findMapNode( ConnectionsToTry.toNode );
			SolutionList HeadSolution = null;
			SolutionList TailSolution = null;
			if ( MapNodeToTryHead.connections.toNode.equalsIgnoreCase( fromName ) ){
				HeadSolution = MapsToTry.Solve( ConnectionsToTry.toNode, toName, g, SolutionPathHead, MapsToTry, MapNodeToTryHead.connections.next );
				if ( ConnectionsToTry.next != null ){
					if ( ConnectionsToTry.toNode.equalsIgnoreCase( fromName ) ){
						TailSolution = MapsToTry.Solve( fromName, toName, g, SolutionPath, MapsToTry, ConnectionsToTry.next.next.next );
					}
					else{
						TailSolution = MapsToTry.Solve( fromName, toName, g, SolutionPath, MapsToTry, ConnectionsToTry.next.next );
					}
				}
				else{
					TailSolution = MapsToTry.Solve( fromName, toName, g, SolutionPath, MapsToTry, ConnectionsToTry.next );
				}
			}
			else{
				HeadSolution = MapsToTry.Solve( ConnectionsToTry.toNode, toName, g, SolutionPathHead, MapsToTry, MapNodeToTryHead.connections );
				if ( ConnectionsToTry.next != null ){
					if ( ConnectionsToTry.toNode.equalsIgnoreCase( fromName ) ){
						TailSolution = MapsToTry.Solve( fromName, toName, g, SolutionPath, MapsToTry, ConnectionsToTry.next.next );
					}
					else{
						
						if ( SolutionPath.lastNode().name.equalsIgnoreCase( ConnectionsToTry.next.toNode ) ){
							TailSolution = MapsToTry.Solve( fromName, toName, g, SolutionPath, MapsToTry, ConnectionsToTry.next.next );
						}
						else{
							TailSolution = MapsToTry.Solve( fromName, toName, g, SolutionPath, MapsToTry, ConnectionsToTry.next );
						}



						//TailSolution = MapsToTry.Solve( fromName, toName, g, SolutionPath, MapsToTry, ConnectionsToTry.next );
					}
				}
				else{
					TailSolution = MapsToTry.Solve( fromName, toName, g, SolutionPath, MapsToTry, ConnectionsToTry.next );
				}
			}
			
			int HeadCost = 9999;
			int TailCost = 9999;
			if ( HeadSolution != null ) HeadCost = HeadSolution.TotalCost();
			if ( TailSolution != null ) TailCost = TailSolution.TotalCost();

			if ( HeadCost < TailCost ){
				return HeadSolution;
			}
			else
			{
				return TailSolution;
			}
		}

	}




}