// RoadNetwork.java

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

/** Framework for discrete event simulation
 */
class Simulator {

        public interface Action {
                // actions contain the specific code of each event
                void trigger( float time );
        }

        private static class Event {
                public float time; // the time of this event
                public Action act; // what to do at that time
        }

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

	/** Call schedule to make act happen at time.
	 *  Users typically pass the action as a lambda expression:
	 *  <PRE>
	 *  Simulator.schedule(t,(float time)->method(params,time))
	 *  </PRE>
	 */
        static void schedule( float time, Action act ) {
                Event e = new Event();
                e.time = time;
                e.act = act;
                eventSet.add( e );
        }

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

// Utility classes

/** Error reporting methods
 */
class Errors {
	private static int errorCount = 0;

	static void fatal( String message ) {
		System.err.println( "Fatal error: " + message );
		System.exit( 1 );
	}
	static void warning( String message ) {
		System.err.println( "Error: " + message );
		errorCount = errorCount + 1;
	}
	static boolean anyErrors() {
		return errorCount > 0;
	}
}

/** Randomness
 */
class PRNG {
	public static Random stream = new Random( 1234 );
	// Bug:  The above code may be too deterministic!

	/** Get random value from 0 to n-1
	 */
	public static int fromZeroToN( int n ) {
		int v = stream.nextInt();
		if (v < 0) v = -v;
		return v % n;
	}
}

/** Input scanning support methods
 */
class ScanSupport {
	/** Interface allowing error messages passed as lambda expressions
	 */
	public interface ErrorMessage {
		abstract String myString();
	}

	/** Force there to be a line end here, complain if not
	 */
	static void lineEnd( Scanner sc, ErrorMessage message ) {
		String skip = sc.nextLine();
		if (!"".equals( skip )) {
			// Bug:  do we want to allow comments here
			Errors.warning(
				message.myString() +
				" -- expected a newline"
			);
		}
		// Bug:  what if sc.nextLine() was illegal (illegal state)
	}

	/* really private to nextName */
	private static final Pattern name = Pattern.compile( "[A-Za-z]\\w*" );

	/** Get the next float, or complain if there isn't one
	 */
	static String nextName( Scanner sc, ErrorMessage message ) {
		if (sc.hasNext( name )) {
			return sc.next( name );
		} else {
			Errors.warning(
				message.myString() +
				" -- expected a name"
			);
			return null;
		}
	}

	/** Get the next int, or complain if there isn't one
	 */
	static int nextInt( Scanner sc, ErrorMessage message ) {
		if (sc.hasNextInt()) {
			return sc.nextInt();
		} else {
			Errors.warning(
				message.myString() +
				" -- expected an integer"
			);
			return 99;
		}
	}

	/** Get the next float, or complain if there isn't one
	 */
	static float nextFloat( Scanner sc, ErrorMessage message ) {
		if (sc.hasNextFloat()) {
			return sc.nextFloat();
		} else {
			Errors.warning(
				message.myString() +
				" -- expected a number"
			);
			return 99.99f;
		}
	}
}

// Simulation classes

/** Roads are one-way streets linking intersections
 *  @see Intersection
 */
class Road {
	// default values below for errors involving incompletely defined roads
	private float travelTime = 99.99f;	// measured in seconds
	private Intersection destination = null;// where road goes
	private Intersection source = null;	// where road comes from
	// name of road is source-destination

	// simulation fields
	int waiting = 0;  // count of cars blocked at exit of this road
	// Bug: This could be a queue of cars if we have vehicle objects.

	// initializer
	public Road( Scanner sc, LinkedList <Intersection> inters ) {
		// scan and process one road
		String sourceName = ScanSupport.nextName(
			sc,
			new ScanSupport.ErrorMessage () {
				public String myString() {
					return Road.this.toString();
				}
			}
		);
		String dstName = ScanSupport.nextName(
			sc,
			() -> Road.this.toString()
		);
		source = RoadNetwork.findIntersection( sourceName );
		destination = RoadNetwork.findIntersection( dstName );
		if (source == null) {
			Errors.warning(
				Road.this.toString() +
				" -- source undefined"
			);
			// Note:  Object is created with a null source
		}
		if (destination == null) {
			Errors.warning(
				Road.this.toString() +
				" -- destination undefined"
			);
			// Note:  Object is created with a null destination
		}
		travelTime = ScanSupport.nextFloat(
			sc,
			() -> Road.this.toString()
		);
		ScanSupport.lineEnd(
			sc,
			() -> Road.this.toString()
		);

		// check sanity of field values
		if (travelTime < 0.0f) {
			Errors.warning(
				Road.this.toString() +
				" -- negative travel time?"
			);
		}

		// install this road between its intersections
		if (source != null) source.outgoing.add( this );
		if (destination != null) destination.incoming.add( this );
	}

	void entryEvent( float t ) {
		// A vehicle arrives at the road entrance at time t
		Simulator.schedule(
			t+travelTime,
			(float time)->Road.this.exitEvent( time )
		);
	}

	void exitEvent( float t ) {
		// A vehicle arrives at the end of this road at time t
		if (destination.isBlocked( this )) {
			waiting = waiting + 1;
			// Bug: if vehicles are objects, this is an enqueue
		} else {
			destination.arrivalEvent( t );
		}
	}

	// other methods
	public String toString() {
		return (
			"Road " +
			( source != null ? source.name : "---" ) +
			" " +
			( destination != null ? destination.name : "---" ) +
			" " +
			travelTime
		);
	}
}

/** Intersections join roads
 *  @see Road
 *  @see NoStop
 *  @see StopLight
 *  @see Source
 *  @see Sink
 */
abstract class Intersection {

	/* throw this if an attempt is made to redefine an intersection */
	public class IllegalName extends Exception {}

	String name;

	public LinkedList <Road> outgoing = new LinkedList <Road> ();
	public LinkedList <Road> incoming = new LinkedList <Road> ();
	// stop lights need to know incoming to release waiting cars
	// Bug:  changes to incoming/outgoing forbidden after net is built.

	Road pickRoad() {
		// Bug: This is really dumb, drivers act as if lost!

		return outgoing.get( PRNG.fromZeroToN( outgoing.size() ) );
	}

	// simulatin methods
	abstract void arrivalEvent( float t );
		// vehicle enters this intersection at time t

	abstract boolean isBlocked( Road r );
		// is this intersection blocked from perspective of road r
	
	// other methods
	public abstract String toString();
}

// Subclasses of Intersection

/** Nostop Intersections are trivial, vehicles just zip through
 *  @see Intersection
 */
class NoStop extends Intersection {
	// initializer
	public NoStop( Scanner sc, String name ) throws IllegalName {
		this.name = name;

		// scan and process one intersection
		if (RoadNetwork.findIntersection( name ) != null) {
			Errors.warning( toString() + " -- redefined." );
			throw new IllegalName();
		}
		ScanSupport.lineEnd(
			sc,
			() -> NoStop.this.toString()
		);
	}

	// simulation methods
	void arrivalEvent( float t ) {
		// vehicle enters this intersection at time t
	}

	boolean isBlocked( Road r ) {
		// is this intersection blocked from perspective of road r
		return false;
	}

	// other methods
	public String toString() {
		return (
			"Intersection " +
			( name != null ? name : "---" )
		);
	}
}

/** Stoplight Intersections block all but one entry, rotating with time
 *  @see Intersection
 */
class StopLight extends Intersection {
	float interval = 99.99f; // how long the light stays green in each dir
	int direction = 0;       // the direciton that is currently green

	// initializer
	public StopLight( Scanner sc, String name ) throws IllegalName {
		this.name = name;

		// scan and process one intersection
		if (RoadNetwork.findIntersection( name ) != null) {
			Errors.warning( toString() + " -- redefined." );
			throw new IllegalName();
		}
		interval = ScanSupport.nextFloat(
			sc,
			() -> StopLight.this.toString()
		);
		direction = 0;
		ScanSupport.lineEnd(
			sc,
			() -> StopLight.this.toString()
		);

		// start this stoplight cycling through its incoming roads
		Simulator.schedule(
			0.0f,
			(float time)->StopLight.this.lightChanges( time )
		);
	}

	// simulation methods

	/** A vehicle arrives at this stoplight
	 */
	void arrivalEvent( float t ) {
		this.pickRoad().entryEvent( t );
	}

	/** Is this intersection blocked from perspective of road r
	 */
	boolean isBlocked( Road r ) {
		return incoming.get( direction) != r;
	}

	/** Process cycling through incoming roads at this stoplight
	 */
	private void lightChanges( float t ) {
		direction = direction + 1;
		if (direction >= incoming.size()) direction = 0;
		// Bug:  incoming.size() is expensive and constant for each

		for( int i = 1; i < incoming.get( direction ).waiting; i++ ) {
			this.pickRoad().entryEvent( t );
			// Bug: If vehicles objects exist, we dequeue them
		}
		incoming.get( direction ).waiting = 0;

		Simulator.schedule(
			t + interval,
			(float time)->StopLight.this.lightChanges( time )
		);
	}

	// other methods
	public String toString() {
		return (
			"Intersection " +
			name +
			" Stoplight " +
			interval
		);
	}
}

/** Source Intersections create cars, they should never be destinations
 *  @see Intersection
 */
class Source extends Intersection {
	private int carCount = 99;
	private float arrivalInterval = 99.99f;

	// initializer
	public Source( Scanner sc, String name ) throws IllegalName {
		this.name = name;

		// scan and process one intersection
		if (RoadNetwork.findIntersection( name ) != null) {
			Errors.warning( toString() + " -- redefined." );
			throw new IllegalName();
		}
		carCount = ScanSupport.nextInt(
			sc,
			() -> Source.this.toString()
		);
		arrivalInterval = ScanSupport.nextFloat(
			sc,
			() -> Source.this.toString()
		);
		ScanSupport.lineEnd(
			sc,
			() -> Source.this.toString()
		);

		// check sanity of field values
		if (carCount < 1) {
			Errors.warning(
				Source.this.toString() +
				" -- never produces any cars?"
			);
		}
		if (arrivalInterval < 0.0f) {
			Errors.warning(
				Source.this.toString() +
				" -- negative time interval?"
			);
		}
	
		Simulator.schedule(
			arrivalInterval,
			(float time)->Source.this.arrivalEvent( time )
		);
	}

	// simulation methods
	void arrivalEvent( float t ) {
		// new vehicle arrives at time t

		System.out.println(
			"Creating a car at time " +
			t +
			" at intersection " +
			name
		);

		// Bug: We could create a vehicle object here.
		this.pickRoad().entryEvent( t );

		carCount = carCount - 1;
		if (carCount > 0) {
			Simulator.schedule(
				t + arrivalInterval,
				(float time)->Source.this.arrivalEvent( time )
			);
		}
	}

	boolean isBlocked( Road r ) {
		// is this source blocked from perspective of road r?
		// Bug:  This should never be called.
		return false;
	}

	// other methods
	public String toString() {
		return (
			"Intersection " +
			name +
			" Source " +
			carCount +
			" " +
			arrivalInterval
		);
	}
}

/** Sink Intersections consume cars, they should never be sources
 *  @see Intersection
 */
class Sink extends Intersection {

	// initializer
	public Sink( Scanner sc, String name ) throws IllegalName {
		this.name = name;

		// scan and process one intersection
		if (RoadNetwork.findIntersection( name ) != null) {
			Errors.warning( toString() + " -- redefined." );
			throw new IllegalName();
		}
		ScanSupport.lineEnd(
			sc,
			() -> Sink.this.toString()
		);
	}

	// simulation methods
	void arrivalEvent( float t ) {
		// do nothing!  The car simply dissapears

		System.out.println(
			"Destroying a car at time " +
			t +
			" at intersection " +
			name
		);
	}

	boolean isBlocked( Road r ) {
		// is this intersection blocked from perspective of road r?  No!
		return false;
	}

	// other methods
	public String toString() {
		return (
			"Intersection " +
			name +
			" Sink"
		);
	}
}

/** RoadNetwork is the main class that builds the whole model
 *  @see Road
 *  @see Intersection
 */
public class RoadNetwork {

	// the sets of all roads and all intersections 
	static LinkedList <Road> roads
		= new LinkedList <Road> ();
	static LinkedList <Intersection> inters
		= new LinkedList <Intersection> ();

	/** Look up s in inters, find that Intersection if it exists
	 *  return null if not.
	 */
	public static Intersection findIntersection( String s ) {
		/* special case added because scan-support can return null */
		if (s == null) return null;

		/* search the intersection list */
		for (Intersection i: RoadNetwork.inters) {
			if (i.name.equals(s)) {
				return i;
			}
		}
		return null;
	}

	/* really private to initializeNetwork() */
	private static final Pattern stoplight = Pattern.compile( "stoplight" );
	private static final Pattern source = Pattern.compile( "source" );
	private static final Pattern sink = Pattern.compile( "sink" );

	/** Initialize the road network by scanning its description
	 */
	static void initializeNetwork( Scanner sc ) {
		while (sc.hasNext()) {
			String command = sc.next();
			if (("intersection".equals( command ))
			||  ("i".equals( command ))) {
				String name = ScanSupport.nextName(
					sc,
					() -> "Intersection"
				);

				// What kind of intersection is this?
				try {
					if (sc.hasNext( stoplight )) {
						sc.next( stoplight ); // skip
						inters.add(
						        new StopLight(sc,name)
						);
					} else if (sc.hasNext( source )) {
						sc.next( source ); // skip
						inters.add(
						        new Source(sc,name)
						);
					} else if (sc.hasNext( sink )) {
						sc.next( sink ); // skip keyword
						inters.add(
						        new Sink(sc,name)
						);
					} else {
						inters.add(
							new NoStop(sc,name)
						);
					}
				} catch (Intersection.IllegalName e){}
			} else if (("road".equals( command ))
			||         ("r".equals( command ))) {
				roads.add( new Road( sc, inters ) );
			} else {
				Errors.warning( "unknown command" );
				// Bug:  should we allow comments?
			}
		}
	}

	/** Print out the road network from the data structure
	 */
	static void printNetwork() {
		for (Intersection i:inters) {
			System.out.println( i.toString() );
		}
		for (Road r:roads) {
			System.out.println( r.toString() );
		}
	}

	/** Main program
	 * @see initializeNetwork
	 */
	public static void main(String[] args) {
		if (args.length < 1) {
			Errors.fatal( "missing file name" );
		}
		if (args.length > 1) {
			Errors.fatal( "too many arguments" );
		}
		try {
			initializeNetwork( new Scanner(new File(args[0])) );
		} catch (FileNotFoundException e) {
			Errors.fatal( "file not found: " + args[0] );
		}
		if (Errors.anyErrors()) {
			printNetwork();
		} else {
			Simulator.run();
		}
	}
}