/* RoadNetwork.java
 * Program to process description of a road network
 * author Douglas W. Jones
 * version 2017-10-19
 * incorporates code from version 2017-09-14
 * incorporates code from the posted solution to MP3
 * incorporates code from Lecture 17
 * incorporates ideas from Homework 8
 *
 * Source and sink intersections work and are tested, stoplights are not
 * tested, uncontrolled intersections are undeveloped.
 */

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

/** Error reporting package
 *  provides standard prefix and behavior for messages
 */
class Errors {
    // error messages are counted.
    private static int errorCount = 0;

    /** Allow public read-only access to the count of error messages
     * @return the count
     */
    public static int count() {
	return errorCount;
    }

    /** Report nonfatal errors, output a message and return
     * @arg message the message to output
     */
    public static void warn( String message ) {
	System.err.println( "RoadNetwork: " + message );
	errorCount = errorCount + 1;
    }

    /** Report fatal errors, output a message and exit, never to return
     * @arg message the message to output
     */
    public static void fatal( String message ) {
	warn( message );
	System.exit( 1 );
    }
}

/** Support methods for scanning
 * @see Errors
 */
class ScanSupport {
    // exception thrown to indicate failure
    public static class NotFound extends Exception {}

    // patterns needed for scanning
    private static final Pattern name
	= Pattern.compile( "[a-zA-Z0-9_]*" );
    private static final Pattern intPattern
	= Pattern.compile( "-?[0-9][0-9]*|");
    private static final Pattern floatPattern
	= Pattern.compile( "-?[0-9][0-9]*\\.?[0-9]*|\\.[0-9][0-9]*|");
    private static final Pattern whitespace
	= Pattern.compile( "[ \t]*" ); // no newlines

    // interface for passing error messages
    public static interface Message {
	public String myString();
    }

    /** Get next name without skipping to next line (unlike sc.Next())
     *  @param sc the scanner from which end of line is scanned
     *  @param message the context part of the missing name error message
     *  @return the name if there was one.
     *  @throws NotFound if there wasn't one
     */
    public static String nextName( Scanner sc, Message m ) throws NotFound {
	sc.skip( whitespace );
	sc.skip( name );
	String s = sc.match().group();
	if ("".equals( s )) {
	    Errors.warn( "name expected: " + m.myString() );
	    sc.nextLine();
	    throw new NotFound();
	}
	return s;
    }

    /** Get next int without skipping to next line (unlike sc.nextInt())
     *  @param sc the scanner from which end of line is scanned
     *  @param message the message to output if there was no int
     *  @return the value if there was one
     *  @throws NotFound if there wasn't one
     */
    public static int nextInt( Scanner sc, Message m ) throws NotFound {
        sc.skip( whitespace );
        sc.skip( intPattern );
        String s = sc.match().group();
        if ("".equals( s )) {
            Errors.warn( "Float expected: " + m.myString() );
            sc.nextLine();
	    throw new NotFound();
        }
	// now, s is guaranteed to hold a legal int
	return Integer.parseInt( s );
    }

    /** Get next float without skipping to next line (unlike sc.nextFloat())
     *  @param sc the scanner from which end of line is scanned
     *  @param message the message to output if there was no float
     *  @return the value if there was one
     *  @throws NotFound if there wasn't one
     */
    public static float nextFloat( Scanner sc, Message m ) throws NotFound {
        sc.skip( whitespace );
        sc.skip( floatPattern );
        String s = sc.match().group();
        if ("".equals( s )) {
            Errors.warn( "Float expected: " + m.myString() );
            sc.nextLine();
	    throw new NotFound();
        }
	// now, s is guaranteed to hold a legal float
	return Float.parseFloat( s );
    }

    /** Advance to next line and complain if is junk at the line end
     *  @see Errors
     *  @param sc the scanner from which end of line is scanned
     *  @param message gives a prefix to give context to error messages
     *  This version supports comments starting with --
     */
    public static void lineEnd( Scanner sc, Message message ) {
        sc.skip( whitespace );
        String lineEnd = sc.nextLine();
        if ( (!lineEnd.equals( "" ))
        &&   (!lineEnd.startsWith( "--" )) ) {
            Errors.warn(
                message.myString() +
                " followed unexpected by '" + lineEnd + "'"
            );
        }
    }
}

/** Pseudo Random Number Generator
 *  needed to make a single global stream of numbers, hiding Java's failures
 */
class PRNG {
    static private Random stream = new Random( 5 );
    // Bug:  For debugging, use a known seed so errors are reproducable

    /** get a number n where 0 <= n < bound
     *  @param bound
     *  @return n
     */
    public static int fromZeroTo( int bound ) {
	return stream.nextInt( bound );
    }
}

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

    /** interface used to allow lambda expressions passed to schedule method
     */
    public interface Action {
	// actions contain the specific code of an event
	void trigger( float time );
    }

    private static class Event {
	public float time;	// time of the event
	public Action act;	// the action to perform
    }

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

    /** schedule one new event
     *  @param time when an event will occur
     *  @param act the action that will be triggered at that time
     *  Typically, this is called as follows:
     *  <pre>
     *  Simulator.schedule( someTime, (float time)->aMethodCall( time ... ) );
     *  </pre>
     */
    public static void schedule( float time, Action act ) {
	Event e = new Event();
	e.time = time;
	e.act = act;
	eventSet.add( e );
    }

    /** main loop that runs the simulation
     *  This must be called after all initial events are scheduled.
     */
    public static void run() {
	while (!eventSet.isEmpty()) {
	    Event e = eventSet.remove();
	    e.act.trigger( e.time );
	}
    }
}

/** Roads are joined by Intersections and driven over by Vehicles
 *  @see Intersection
 */
class Road {
    // constructors may throw this when an error prevents construction
    public static class ConstructorFailure extends Exception {}

    final float travelTime;           // measured in seconds, always positive
    final Intersection source;        // where this road comes from, never null
    final Intersection destination;   // where this road goes, never null
    final int dir;                    // road direction into dst intersection
    // name of a road is source-destination

    /** construct a new road by scanning its description from the source file
     */
    Road( Scanner sc ) throws ConstructorFailure {
	final String sourceName;
	final String dstName;
	try {
	    sourceName = ScanSupport.nextName(
		sc, ()->"Road ???"
	    );
	    dstName = ScanSupport.nextName(
		sc, ()-> "Road " + sourceName + " ???"
	    );
	} catch (ScanSupport.NotFound e) {
	    throw new ConstructorFailure();
	}

	source = RoadNetwork.findIntersection( sourceName );
	destination = RoadNetwork.findIntersection( dstName );
	if (source == null) {
	    Errors.warn( "No such source intersection: Road "
			+ sourceName + " " + dstName
	    );
	    sc.nextLine();
	    throw new ConstructorFailure();
	}
	if (destination == null) {
	    Errors.warn( "No such destination intersection: Road "
			+ sourceName + " " + dstName
	    );
	    sc.nextLine();
	    throw new ConstructorFailure();
	}

	try {
	    travelTime = ScanSupport.nextFloat(
		sc, ()->"Floating point travel time expected: Road "
			+ sourceName + " " + dstName
	    );
	} catch (ScanSupport.NotFound e) {
	    throw new ConstructorFailure();
	}
	if (travelTime < 0.0F) {
	    Errors.warn( "Negative travel time:" + this.toString() );
	}

	ScanSupport.lineEnd( sc, ()->this.toString() );

	// register this road with its source and destination intersections
	source.outgoing.add( this );
	dir = destination.incoming.size();
	destination.incoming.add( this );

    } // Road constructor

    /** output the road in a form like that used for input
     */
    public String toString() {
	return  "road "
		+ source.name + " "
		+ destination.name + " "
		+ travelTime;
    }

    // simulation methods

    /** what happens when a vehicle enters this road
     *  @param time the vehicle enters
     */
    public void entryEvent( float time ) {
	// after a vehicle enters the road, it exits it travelTime later
	// Bug: could track population to model congestion
	// Bug: could take and pass on a Vehicle parameter
	Simulator.schedule(
	    time + travelTime, (float t)->exitEvent( t )
	);
    }

    /** what happens when a vehicle exits this road
     *  @param time the vehicle exits
     */
    public void exitEvent( float time ) {
	// Bug: could track population to model congestion
	Simulator.schedule( time, (t)->destination.arrivalEvent( t, dir ) );
    }

} // class Road 

/** Intersections pass Vehicles between Roads
 *  @see Road
 *  @see Stoplight
 *  @see NoStop
 */
abstract class Intersection {
    // constructors may throw this when an error prevents construction
    public static class ConstructorFailure extends Exception {}

    final public String name;   // textual name of intersection, never null!

    // set of all roads out of this intersection
    public final LinkedList <Road> outgoing = new LinkedList <Road> ();

    // set of all roads in to this intersection
    public final LinkedList <Road> incoming = new LinkedList <Road> ();

    // constructor to set Intersection's final name
    protected Intersection( String name ) {
	this.name = name;
    }

    /** factory method to create intersections
     *  @param sc the scanner to read intersection description from
     *  @return either a new intersection or null
     */
    public static Intersection newIntersection( Scanner sc )
						throws ConstructorFailure {
	final String name;
	try {
	    name = ScanSupport.nextName( sc, ()->"intersection ???" );
	} catch (ScanSupport.NotFound e) {
	    throw new ConstructorFailure();
	}

	if (RoadNetwork.findIntersection( name ) != null) {
	    Errors.warn( "Intersection redefined: " + name );
	    sc.nextLine();
	    throw new ConstructorFailure();
	}

	final String intersectionType;
	try {
	    intersectionType = ScanSupport.nextName(
		sc, ()->"intersection " + name + " ???"
	    );
	} catch (ScanSupport.NotFound e) {
	    throw new ConstructorFailure();
	}

	if ("nostop".equals( intersectionType )) {
	    return new NoStop( sc, name );
	} else if ("stoplight".equals( intersectionType )) {
	    return new StopLight( sc, name );
	} else if ("source".equals( intersectionType )) {
	    return new Source( sc, name );
	} else if ("sink".equals( intersectionType )) {
	    return new Sink( sc, name );
	} else {
	    Errors.warn( "intersection " + name + " " + intersectionType
			 + ": unknown type: " );
	    sc.nextLine();
	    throw new ConstructorFailure();
	}
    } // newIntersection factory method

    /** output the intersection in a form like that used for input
     */
    public String toString() {
	// Java bug:  No outsider should ever call this
	//            this should only be called from a subclass
	return  "intersection "
		+ name;
    }

    // simulation methods

    /** pick an outgoing road from this intersection
     *  @return the road it picks
     */
    protected Road pickRoad() {
	// Bug:  Perhaps later, it will depend on the vehicle
	// pick a road at random
	int roadNumber = PRNG.fromZeroTo( outgoing.size() );
	return outgoing.get( roadNumber );
    }

    /** simulate a vehicle arriving at this intersection
     *  @param time a vehicle arrives
     *  @param dir a vehicle arrives from
     *  the details depend on the intersection
     */
    public abstract void arrivalEvent( float time, int dir );

    /** simulate a vehicle departs from this intersection
     *  @param time a vehicle departs
     *  the details depend on the intersection
     */
    public abstract void departureEvent( float time );

} // Intersection class

/** Intersection with no control, neither stopsign nor stoplight
 */
class NoStop extends Intersection {
    NoStop( Scanner sc, String name ) {
	super( name );
	ScanSupport.lineEnd( sc, ()->this.toString() );
    }

    public String toString() {
	return  super.toString() + " nostop";
    }

    // simulation methods
    public void arrivalEvent( float time, int dir ) {} // Bug: must write this;
    public void departureEvent( float time ) {}        // Bug: must write this;
}

/** Intersection with a stoplight
 */
class StopLight extends Intersection {
    private int lightDir = 0;
    private final float greenLength;
    private int queues[];

    StopLight( Scanner sc, String name ) throws ConstructorFailure {
	super( name );
	try {
	    greenLength = ScanSupport.nextFloat(
		sc, ()->"Floating point green time expected: stoplight " + name
	    );
	} catch (ScanSupport.NotFound e) {
	    throw new ConstructorFailure();
	}
	ScanSupport.lineEnd( sc, ()->this.toString() );

	// start the light change process
	Simulator.schedule( 0.0f, (float t)->lightChangeEvent( t ) );
    }

    public String toString() {
	return  super.toString() + " stoplight";
    }

    // simulation methods

    private void lightChangeEvent( float time ) {
	if (queues == null) queues = new int[incoming.size()];
	// Bug: is the above really safe; better to do this in sanity check

	// change the state of the light
	lightDir = lightDir + 1;
	if (lightDir > incoming.size()) lightDir = 0;
	// alternatively lightDir = (lightDir + 1) % incoming.size();
	// Bug: incoming.size() should be evaluated just once and saved

	// schedule the departures of waiting vehicles
	while (queues[lightDir] > 0) {
	    queues[lightDir] = queues[lightDir] - 1;
	    Road r = this.pickRoad();
	    Simulator.schedule( time, (float t)->r.entryEvent( t ) );
	    // Bug: this means the vehicle passes through in an instant
	}

	// schedule the next event in this light-change process
	Simulator.schedule(
	    time + greenLength, (float t)->lightChangeEvent( t )
	);
    }

    /** simulate arrival of one vehicle at this sink intersection
     *  @param time When the vehicle arrives
     *  @param dir the vehicle arrives from
     */
    public void arrivalEvent( float time, int dir ) {
	if (dir == lightDir) { // green
	    // simulate the departure of the vehicle from the intersection 
	    Road r = this.pickRoad();
	    Simulator.schedule( time, (float t)->r.entryEvent( t ) );
	    // Bug: this means the vehicle passes through in an instant
	} else { // red
	    // queue up the vehicle
	    queues[lightDir] = queues[lightDir] + 1;
	}
    }

    public void departureEvent( float time ) {}   // Bug: must write this;
}

/** Source Intersection
 */
class Source extends Intersection {
    private final float startTime;          // when source starts producing
    private int numCars;                    // how many vehicles it produces
    private final float departureInterval;  // how long between vehicles

    /** Source Intersection constructor
     *  @param sc the scanner from which the description is read
     *  @param name of this intersection
     *  @throws Intersection.ConstructorFailure if description is bad
     */
    Source( Scanner sc, String name ) throws Intersection.ConstructorFailure {
	super( name );

	// parse and initialize the source description
	try {
	    startTime = ScanSupport.nextFloat(
		sc, ()-> Source.this.toString()
	    );
	    numCars = ScanSupport.nextInt(
		sc, ()-> Source.this.toString()
	    );
	    departureInterval = ScanSupport.nextFloat(
		sc, ()-> Source.this.toString()
	    );
	} catch (ScanSupport.NotFound e) {
	    throw new Intersection.ConstructorFailure();
	}

	// check sanity of the fields
	if (startTime < 0.0f) Errors.warn(
	    "Negative start time: " + this.toString()
	);
	if (numCars <= 0) Errors.warn(
	    "Never produces: " + this.toString()
	);
	if (departureInterval < 0.0f) Errors.warn(
	    "Negative departure interval: " + this.toString()
	);

	ScanSupport.lineEnd( sc, ()->Source.this.toString() );

	// start the simulation of this source
	Simulator.schedule( startTime, (float t)->departureEvent( t ) );

    } // Source constructor

    public String toString() {
	return  super.toString() + " source " + startTime + " "
				 + numCars + " " + departureInterval;
    }

    // Simulation methods

    /** simulate arrival of one vehicle at this source intersection
     *  @param time When the vehicle arrives
     *  @param dir the vehicle arrives from
     */
    public void arrivalEvent( float time, int dir ) {
	Errors.fatal( "Vehicle arrived at: " + this.toString() );
    }

    /** simulate departure of one vehicle from this source intersection
     *  @param time When the vehicle departs
     */
    public void departureEvent( float time ) {
	// simulate the departure
	Road r = this.pickRoad();
	Simulator.schedule( time, (float t)->r.entryEvent( t ) );

	// schedule the departure of the next car, if there is one
	numCars = numCars - 1;
	if (numCars > 0) Simulator.schedule(
	    time + departureInterval, (float t)->departureEvent( t )
	);
    }

} // class Source

/** Sink Intersection
 */
class Sink extends Intersection {

    Sink( Scanner sc, String name ) {
	super( name );
	ScanSupport.lineEnd( sc, ()->this.toString() );
    }

    public String toString() {
	return  super.toString() + " sink";
    }

    /** simulate arrival of one vehicle at this sink intersection
     *  @param time When the vehicle arrives
     *  @param dir the vehicle arrives from
     */
    public void arrivalEvent( float time, int dir ) {
	System.out.println(
	    "Vehicle arrives at " + toString() + " at time " + time
	);
    }

    /** simulate departure of one vehicle from this sink intersection
     *  @param time When the vehicle departs
     */
    public void departureEvent( float time ) {
	Errors.fatal( "Vehicle departed from: " + this.toString() );
    }

} // class Sink

public class RoadNetwork {

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

    /** Find an intersection by textual name in the set inters
     *  @param s name of an intersection
     *  @return the intersection named s or null if none
     */
    public static Intersection findIntersection( String s ) {
	// quick and dirty implementation
	for (Intersection i: inters) {
	    if (i.name.equals( s )) {
		return i;
	    }
	}
	return null;
    }

    /** Initialize this road network by scanning its description
     */ 
    private static void readNetwork( Scanner sc ) {
        while (sc.hasNext()) {
	    String command = sc.next();
	    if ("intersection".equals( command )) {
		try {
		    inters.add( Intersection.newIntersection( sc ) );
		} catch (Intersection.ConstructorFailure e) {
		    // do nothing, the constructor already reported the error
		}
	    } else if ("road".equals( command )) {
		try {
		    roads.add( new Road( sc ) );
		} catch (Road.ConstructorFailure e) {
		    // do nothing, the constructor already reported the error
		}
	    } else if ("--".equals( command )) {
		sc.nextLine();
	    } else {
	        Errors.warn( "unknown command: " + command );
		sc.nextLine();
	    }
	}
    }

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

    /** Main program
     */ 
    public static void main( String[] args ) {
	if (args.length < 1) {
	    Errors.fatal( "Missing file name argument" );
	} else if (args.length > 1) {
	    Errors.fatal( "Too many arguments" );
	} else try {
	    readNetwork( new Scanner( new File( args[0] ) ) );
	    if (Errors.count() == 0) {
		printNetwork();
		Simulator.run();
	    }
        } catch (FileNotFoundException e) {
	    Errors.fatal( "Can't open the file" );
	}
    }
}