// RoadNetwork.java
/**
 * Framework for discrete event simulation.
 * @author Douglas Jones
 * @version MP4?
 */

import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.Random;

class Simulator {

	public static abstract class Event {
		public float time;       // the time of this event
		abstract void trigger(); // the action to take
	}

	private static PriorityQueue <Event> eventSet
	= new PriorityQueue <Event> (
		(Event e1, Event e2) -> Float.compare( e1.time, e2.time )
	);

	static void schedule( Event e ) {
		/** Call schedule to make e happen at its time.
		 */
		eventSet.add( e );
	}

	static void run() {
		/** Call run after scheduling some initial events
		 *  to run the simulation.
		 */
		while (!eventSet.isEmpty()) {
			Event e = eventSet.remove();
			e.trigger();
		}
	}
}

class Errors {
	/** Error reporting framework
	 */
	static void fatal( String message ) {
		/** Report a fatal error with the given message
		 */
		System.err.println( message );
		System.exit( 1 );
	}
}

class SyntaxCheck {
	/** Syntax checking support
	 */

	// Framework for lambda binding of a string parameter.
	// -- outsiders do not directly use this class.
	public interface ByName { String s(); }

	static void lineEnd( Scanner sc, ByName c ) {
		/** Check for end of line on sc,
		 *  Use c to provide context in any error message
		 */
		String s = sc.nextLine();
		if (!s.isEmpty()) {
			Errors.fatal(
				c.s()
				+ " has non-empty line end '"
				+ s
				+ "'"
			);
		}
	}
}

class Road {
	/** Roads are one-way streets linking intersections
	 *  @see Intersection
	 */
	float travelTime;         //measured in seconds
	Intersection destination; //where the road goes
	Intersection source;      //where the comes from
	int population;           //how many vehicles are here
	// name of road is source-destination 

	// initializer
	public Road( Scanner sc ) {
		/** Initialize a road by scanning its description from sc
		 */

		String srcName = sc.next();
		source = RoadNetwork.findIntersection( srcName );
		String dstName = sc.next();
		destination = RoadNetwork.findIntersection( dstName );
		population = 0; // no vehicles here yet

		if (source == null) {
			Errors.fatal(
				"Road '" + srcName + "' '" + dstName + "'"
				+ "-- the first name is undefined"
			);
		}

		if (destination == null) {
			Errors.fatal(
				"Road '" + srcName + "' '" + dstName + "'"
				+ "-- the second name is undefined"
			);
		}
		source.addOutgoing( this,
			"Road '" + srcName + "' '" + dstName + "'"
		);
		destination.addIncoming( this,
			"Road '" + srcName + "' '" + dstName + "'"
		);

		if (!sc.hasNextFloat()) {
			Errors.fatal(
				"Road '" + srcName + "' '" + dstName + "'"
				+ "-- travel time not specified"
			);
		}
		travelTime = sc.nextFloat();

		SyntaxCheck.lineEnd(
			sc,
			() -> "Road '" + srcName + "' '" + dstName + "'"
		);
	}

	// simulation methods for Road

	public static class EnterEvent extends Simulator.Event {
		Vehicle v;
		Road r;

		EnterEvent( Vehicle v, Road r, float t ) {
			time = t;
			this.v = v;
			this.r = r;
			Simulator.schedule( this );
		}

		void trigger() {
			// We could put the code for r.exit here
			r.enter( v, time );
		}
	}

	private static class ExitEvent extends Simulator.Event {
		Vehicle v;
		Road r;

		ExitEvent( Vehicle v, Road r, float t ) {
			time = t;
			this.v = v;
			this.r = r;
			Simulator.schedule( this );
		}

		void trigger() {
			System.out.println( "Exiting " + this.toString()
				+ " at time = " + time
			);

			// track state of road
			r.population = r.population - 1;

			// report that v will enter the destination intersetion
			r.destination.enter( v, time );
		}
	}

	public void enter( Vehicle v, float t ) {
		/** Simulate v entering this road at time t.
		 *  This is always called at the same time as intersection exit.
		 */

		System.out.println( "Entering " + this.toString()
			+ " at time = " + t
		);

		// track state of road
		population = population + 1;

		// Bug: later, we can make travel time a function of population

		new ExitEvent( v, this, t + travelTime );
	}

	public String toString() {
		/** Convert a road back to its textual description
		 */
		return  "road "
			+ source.name
			+ ' '
			+ destination.name
			+ ' '
			+ travelTime
		;
	}
}

abstract class Intersection {
	/** Intersections join roads
	 *  @see Road
	 */
	String name;
	LinkedList <Road> outgoing = new LinkedList <Road> ();
	LinkedList <Road> incoming = new LinkedList <Road> ();
	float travelTime;

	// initializer
	public Intersection( Scanner sc ) {
		/** Initialize an interseciton scanning its description from sc
		 */
		name = sc.next();
		if (RoadNetwork.findIntersection( name ) != null) {
			Errors.fatal( "Intersection '" + name + "' redefined" );
		}

		if (!sc.hasNextFloat()) {
			Errors.fatal(
				"Intersection '" + name
				+ "'-- travel time not specified"
			);
		}
		travelTime = sc.nextFloat();

		SyntaxCheck.lineEnd( sc, () -> "Intersection '" + name + "'" );
	}

	public void addIncoming( Road r, String err ) {
		/** Add a road to the incoming list of this intersection.
		 *  This is a default method that subclasses may override.
		 */
		this.incoming.add( r );
	}

	public void addOutgoing( Road r, String err ) {
		/** Add a road to the outgoing list of this intersection.
		 *  This is a default method that subclasses may override.
		 */
		this.outgoing.add( r );
	}

	public abstract void checkCorrectness();
		/** Check if the intersection is legally configured
		 */

	// simulation methods for Intersection

	class ExitEvent extends Simulator.Event {
		/** Generic exit from any intersection, but it
		 *  calls Subclass.exit() when triggered.
		 */
		Vehicle v;
		Intersection i;

		ExitEvent( Vehicle v, Intersection i, float t ) {
			time = t;
			this.v = v;
			this.i = i;
			Simulator.schedule( this );
		}

		void trigger() {
			// We could put the code for r.exit here
			i.exit( v, time );
		}
	}

	public abstract void enter( Vehicle v, float t );
		/** Simulate v entering this intersection at time t.
		 */

	public abstract void exit( Vehicle v, float t );
		/** Simulate v exiting this intersection at time t.
		 */

	// utility methods for Intersection

	public abstract String toString();
		/** Convert an intersection back to its textual description
		 */

} // end of Intersection

class NoStops extends Intersection {
        /** Intersections with neither stop-signs nor stop lights.
         *  @see Intersection
	 */
	boolean occupied = false; // intersection initially unoccupied
	LinkedList <Vehicle> queue = new LinkedList <Vehicle> ();
		// initially an empty queue 

	// initializer
	public NoStops( Scanner sc ) {
		super( sc );
	}

	public void checkCorrectness() {
		/** Check that uncontrolled intersection has at
		 *  least one incoming road and one outgoing road.
		 */
		if (incoming.isEmpty()) {
			Errors.fatal(
				"intersection nostop "
				+ name
				+ " has no incoming roads"
			);
		}
		if ( outgoing.isEmpty()) {
			Errors.fatal(
				"intersection nostop "
				+ name
				+ " has no outgoing roads"
			);
		}
	}

	// simulation methods for uncontrolled Intersection

	public void enter( Vehicle v, float t ){
		/** Simulate v entering this intersection at time t.
		 */
		System.out.println( "Entering " + this.toString()
			+ " at time = " + t
		);

		if (occupied) {
			queue.addLast( v );
		} else {
			occupied = true;
			new ExitEvent( v, this, t + travelTime );
		}
	}

	public void exit( Vehicle v, float t ){
		/** Simulate v exiting this intersection at time t.
		 */
		System.out.println( "Exiting " + this.toString()
			+ " at time = " + t
		);

		Road d = v.pickRoad( outgoing );
		if ( queue.isEmpty() ) {
			occupied = false;
		} else {
			Vehicle v1 = queue.removeFirst();
			new ExitEvent( v1, this, t + travelTime );
		}
		d.enter( v, t ); // enter destination road
	}

	// utility methods for uncontrolled Intersection

	public String toString() {
		/** Convert an intersection back to its textual description
		 */
		return "intersection nostop " + name;
	}
}

class FourWay extends Intersection {
        /** Intersections with stop-signs on every incoming road.
         *  @see Intersection
         */
	boolean occupied = false; // intersection initially unoccupied
	LinkedList <Vehicle> queue[]; // an array of queues, one per incoming

	// initializer
	public FourWay( Scanner sc ) {
		super( sc );
	}

	public void checkCorrectness() {
		/** Check that 4-way stop intersection has at
		 *  least two incoming roads and one outgoing road.
		 *  This also initialize the queues representing stop signs.
		 */
		int size = incoming.size();
		if (size < 2) {
			Errors.fatal(
				"intersection 4way "
				+ name
				+ " has too few incoming roads"
			);
		}
		if ( outgoing.isEmpty()) {
			Errors.fatal(
				"intersection 4way "
				+ name
				+ " has no outgoing roads"
			);
		}

		// Bug: initialize stop sign queues
	}

	public void enter( Vehicle v, float t ) {
		/** Simulate v entering this intersection at time t.
		 */
		// Bug:  Missing body!
		// Bug:  How do I know what stop sign to put the vehicle in?
	}

	public void exit( Vehicle v, float t ) {
		/** Simulate v exiting this intersection at time t.
		 */
		// Bug:  Missing body!
	}

	public String toString() {
		/** Convert an intersection back to its textual description
		 */
		return "intersection 4way " + name;
	}
}

class Source extends Intersection {
        /** Sources create cars and pretend to be a kind of intersection
         *  @see Intersection
         */

	// initializer
	public Source( Scanner sc ) {
		super( sc );
		new ExitEvent( new Vehicle(), this, 0 );
	}

	public void addIncoming( Road r, String err ) {
		/** Override the default addIncoming method
		 *  to prevent adding an incoming road to a traffic source.
		 */
		Errors.fatal( err + "-- road to a source forbidden" );
	}

	public void checkCorrectness() {
		/** Check that traffic source has
		 *  at least one outgoing road.
		 *  There is no need to check the incoming road count
		 *  because addIncoming() checked that.
		 */
		if ( outgoing.isEmpty()) {
			Errors.fatal(
				"intersection source "
				+ name
				+ " has no outgoing roads"
			);
		}
	}

	public void enter( Vehicle v, float t ) {
		/** Simulate v entering this intersection at time t.
		 */
		Errors.fatal(
				"Attempted entry to intersection source "
				+ name
		);
	}

	public void exit( Vehicle v, float t ) {
		/** Simulate v exiting this intersection at time t.
		 */

		System.out.println( "Exiting " + this.toString()
			+ " at time = " + t
		);

		Road d = v.pickRoad( outgoing );
		new Road.EnterEvent( v, d, t );

		// Bug:  Later, make sources create multiple vehicles at
		// random times.
	}

	public String toString() {
		/** Convert an intersection back to its textual description
		 */
		return "intersection source " + name;
	}
}

class Sink extends Intersection {
        /** Sinks consume cars and pretend to be a kind of intersection
         *  @see Intersection
         */

	// initializer
	public Sink( Scanner sc ) {
		super( sc );
	}

	public void addOutgoing( Road r, String err ) {
		/** Override the default addOutgoing method
		 */
		Errors.fatal( err + "-- road from a sink forbidden" );
	}

	public void checkCorrectness() {
		/** Check that traffic sink has
		 *  at least one incoming road.
		 *  There is no need to check here for outgoing roads
		 *  because addOutgoing() checked that.
		 */
		if ( incoming.isEmpty()) {
			Errors.fatal(
				"intersection sink "
				+ name
				+ " has no incoming roads"
			);
		}
	}

	public void enter( Vehicle v, float t ) {
		/** Simulate v entering this intersection at time t.
		 */
		// Bug:  Missing body!
	}

	public void exit( Vehicle v, float t ) {
		/** Simulate v exiting this intersection at time t.
		 */
		Errors.fatal(
				"Attempted exit from intersection sink "
				+ name
		);
	}

	public String toString() {
		/** Convert an intersection back to its textual description
		 */
		return "intersection sink" + name;
	}
}

class PRNG {
	/** Pseudo Random Number Generator for simulation model.
	 *  Class Random does almost the right thing, but we want
	 *  just one global stream and not an unlimited number of streams.
	 */

	// here, we use the class Random from the Java library
	private static Random r = new Random( 1 );
	// Bug:  A constant seed of 1 makes the simulation debugabble
	// Bug:  A constant seed of 1 makes the simulation unrealistic

	static int randInt( int n ) {
		/** Draw an integer in the range 0 <= i < n from the stream.
		 */
		return r.nextInt( n );
	}
}

class Vehicle {
	/** Vehicles travel on roads through intersections
	 *  @see Intersection
	 *  @see Road
	 */
	// Bug: do I need my current location?

	public Road pickRoad( List <Road> roadList ) {
		/** Pick a road in a really stupid way.
		 *  Clearly, later versions could use more
		 *  intelligent algorithms here!!!
		 */
		return roadList.get( PRNG.randInt( roadList.size() ) );
	}
}

public class RoadNetwork {
	/** Top level description of a road network consisting of
         *  some intersections connected by some roads.
	 *  @see Intersection
	 *  @see Road
	 */
	static LinkedList <Intersection> inters
		= new LinkedList <Intersection> ();
	static LinkedList <Road> roads
		= new LinkedList <Road> ();

	static Intersection findIntersection( String s ) {
		/** Given s the name of a particular intersection,
		 *  returns null if that intersection does not exist,
		 *  returns that intersection if it exists.
		 *  @see Intersection
		 */
		// Bug:  Reengineering this to use a hash should be possible
		for (Intersection i: inters) {
			if (i.name.equals( s )) {
				return i;
			}
		}
		return null;
	}

	private static void readNetwork( Scanner sc ) {
		/** Read a road network, scanning its description from sc.
		 */
		while (sc.hasNext()) {
			// until the input file is finished
			String command = sc.next();
			if ("intersection".equals( command )
			||  "i".equals( command )           ) {
				String kind = sc.next();
				if ("nostop".equals(kind)) {
					inters.add( new NoStops( sc ) );
				} else if ("4way".equals(kind)) {
					inters.add( new FourWay( sc ) );
				} else if ("source".equals(kind)) {
					inters.add( new Source( sc ) );
				} else if ("sink".equals(kind)) {
					inters.add( new Sink( sc ) );
				} else {
					Errors.fatal(
						"intersection '"
						+ kind
						+ "' -- unknown type"
					);
				}
				// inters.add( new Intersection( sc, inters ) );
			} else if ("road".equals( command )
			||         "r".equals( command )   ) {
				roads.add( new Road( sc ) );
			} else {
				Errors.fatal(
					"'"
					+ command
					+ "' not a road or intersection"
				);
			}
		}
	}

	private static void checkNetwork() {
		/** Check the correctness of the network.
		 */
		for (Intersection i: inters) {
			i.checkCorrectness();
		}
	}

	private static void writeNetwork() {
		/** Write out a textual description of the entire road network.
		 *  This routine is scaffolding used during development.
		 */
		for (Intersection i: inters) {
			System.out.println( i.toString() );
		}
		for (Road r: roads) {
			System.out.println( r.toString() );
		}
	}

        public static void main(String[] args) {
		/** Create a road network.
		 *  The command line argument names the input file.
		 *  For now, the output is just a reconstruction of the input.
		 */
		if (args.length < 1) {
			Errors.fatal( "Missing filename argument" );
		}
		if (args.length > 1) {
			Errors.fatal( "Extra command-line arguments" );
		}
		try {
		        readNetwork( new Scanner( new File( args[0] )));
			checkNetwork();
			writeNetwork();
			Simulator.run();
		} catch (FileNotFoundException e) {
			Errors.fatal( "Can't open file '" + args[0] + "'" );
		}
        }
}