/* RoadNetwork.java
 * Program to process description of a road network
 * author Douglas W. Jones
 * version 2017-10-25
 * incorporates code from version 2017-09-14
 * incorporates code from the posted solution to MP3
 * incorporates code from Lecture 18
 *
 * This code compiles and runs, and it includes output to trace
 * the arrival of vehicles at intersections and entry into roads
 * It is fairly clean and fairly decently commented
 *
 * Bug:  The model never terminates if there are any stoplights
 */

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 {
    private static 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 dstDir;                 // what direction does this enter dst
    // name of a road is source-destination

    /** construct a new road by scanning its description from the source file
     *  @param sc the scanner from which the input is read
     *  @throws ConstructorFailure when it cannot construct a road
     */
    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 );
	dstDir = destination.incoming.size();
	destination.incoming.add( this );

    } // Road constructor

    /** give the road in a form like that used for input
     *  @return the textual road description
     */
    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 ) {
	System.out.println(
	    "Vehicle entered " + this.toString() + " at " + 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, dstDir ) );
    }

} // 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 used by subclasses to initialize final fields
     *  @param name sets the name field
     */
    protected Intersection( String name ) {
	this.name = name;
    }

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

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

	// find out which subclass of intersection is needed
	final String intersectionType;
	try {
	    intersectionType = ScanSupport.nextName(
		sc, ()->"intersection " + name + " ???"
	    );
	} catch (ScanSupport.NotFound e) {
	    throw new ConstructorFailure();
	}

	// construct the desired class of intersection and return it
	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

    /** get the intersection description in a form like that used for input
     *  @return the textual description
     */
    public String toString() {
	// Java bug:  No outsider should ever call this
	//            this cannot be protected because it overrides a default
	//            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
     *  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
 *  @see Intersection
 */
class NoStop extends Intersection {
    private final float delay; // time it takes to traverse the intersection
    private int occupants = 0; // count of vehicles in the intersection
    // Bug:  If vehicles exist, occupants is a queue of vehicles

    /** NoStop intersection constructor
     *  @param sc scanner from which the description is taken
     *  @param name of the intersection the caller already scanned
     *  @throws Intersection.ConstructorFailure if the description is faulty
     */
    NoStop( Scanner sc, String name ) throws Intersection.ConstructorFailure {
	super( name );
	try {
	    delay = ScanSupport.nextFloat(
	        sc, ()->"Floating point delay expected: Intersection "
			+ name + " nostop"
	    );
	} catch (ScanSupport.NotFound e) {
	    throw new ConstructorFailure();
	}
	ScanSupport.lineEnd( sc, ()->this.toString() );
    }

    /** get the intersection description in a form like that used for input
     *  @return the textual description
     */
    public String toString() {
	return  super.toString() + " nostop " + delay;
    }

    // simulation methods

    /** what happens when a vehicle arrives at this NoStop intersection
     *  @param time the vehicle arrives
     *  @param dir the direction it arrives from
     */
    public void arrivalEvent( float time, int dir ) {
	System.out.println(
	    "Vehicle arrived at " + this.toString() + " at " + time
	);

	if (occupants == 0) { // if intersection is clear, vehicle continues
	    Simulator.schedule( time + delay, (float t)->departureEvent( t ) );
        }
	// always add to the population of the intersection
	occupants = occupants + 1;
        // Bug: if vehicle objects exist, enqueue one
    }

    /** what happens when a vehicle departs from this NoStop intersection
     *  @param time the vehicle departs
     */
    public void departureEvent( float time ) {
        // if vehicle objects exist, dequeue one
	occupants = occupants - 1;

	// send the vehicle onward
	this.pickRoad().entryEvent( time );
	// alternately Road r = this.pickRoad();
	// alternately Simulator.schedule( time, (float t)->r.entryEvent( t ) );

	// if others are queued up, let one of them continue
        // Bug: if vehicle objects exist, test queue not empty
	if (occupants > 0) {
	    Simulator.schedule( time + delay, (float t)->departureEvent( t ) );
	}
    }
} // class NoStop

/** Intersection with a stoplight
 *  @see Intersection
 */
class StopLight extends Intersection {
    private int lightDir = 0;  // direction light is green
    private final float lightInterval; // how long it stays green in any dir
    private int[] queues;      // where vehicles wait (just counts of vehicles)
    private final float delay; // time it takes to traverse the intersection
    private int occupants = 0; // count of vehicles in the intersection

    /** StopLight intersection constructor
     *  @param sc scanner from which the description is taken
     *  @param name of the intersection the caller already scanned
     *  @throws Intersection.ConstructorFailure if the description is faulty
     */
    StopLight( Scanner sc, String name )throws Intersection.ConstructorFailure {
	super( name );
	try {
	    delay = ScanSupport.nextFloat(
	        sc, ()->"Floating point delay expected: Intersection "
			+ name + " stoplight"
	    );
	    lightInterval = ScanSupport.nextFloat(
	        sc, ()->"Floating point light interval expected: Intersection "
			+ name + " stoplight " + delay
	    );
	} catch (ScanSupport.NotFound e) {
	    throw new ConstructorFailure();
	}
	ScanSupport.lineEnd( sc, ()->this.toString() );

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

    /** get the intersection description in a form like that used for input
     *  @return the textual description
     */
    public String toString() {
	return  super.toString() + " stoplight " + delay + " " + lightInterval;
    }

    // simulation methods

    /** what happens when the StopLight changes
     *  @param time the light changes
     *  StopLight events form a periodic process that continues forever
     */
    private void lightChangeEvent( float time ) {
	if (queues == null) queues = new int[incoming.size()];
	// change the light direction
	lightDir = lightDir + 1;
	if (lightDir >= incoming.size()) lightDir = 0;
	// could write lightDir = (lightDir + 1) % incoming.size();

	// release the first waiting cars if the intersection is clear
	if ((queues[lightDir] > 0) && (occupants == 0)) {
	    queues[lightDir] = queues[lightDir] - 1;
	    Simulator.schedule( time + delay, (float t)->departureEvent( t ) );
	    occupants = occupants + 1;
	}

	// advance the light change process
	Simulator.schedule(
	    time + lightInterval, (float t)->lightChangeEvent( t )
	);
    }

    /** what happens when a vehicle arrives at this StopLight intersection
     *  @param time the vehicle arrives
     *  @param dir the direction it arrives from
     */
    public void arrivalEvent( float time, int dir ) {
	System.out.println(
	    "Vehicle arrived at " + this.toString() + " at " + time
	);

	if ((dir == lightDir) && (occupants == 0)) { // green and unoccupied
            // car goes straight through green light
	    Simulator.schedule( time + delay, (float t)->departureEvent( t ) );
            occupants = occupants + 1;
	} else { // red or occupied
	    // queue up another car
	    queues[dir] = queues[dir] + 1;
        }
    }

    /** what happens when a vehicle departs from this StopLight intersection
     *  @param time the vehicle departs
     */
    public void departureEvent( float time ) {
        // move the departing vehicle onward
	Road r = this.pickRoad();
	Simulator.schedule( time, (float t)->r.entryEvent( t ) );
        occupants = occupants - 1;

	// if there are more vehicles, schedule the next departure
	// in effect, departure events are a process that drains the queue
	if (queues[lightDir] > 0) {
	    queues[lightDir] = queues[lightDir] - 1;
	    Simulator.schedule( time + delay, (float t)->departureEvent( t ) );
	    occupants = occupants + 1;
	}
    }
}

/** Source Intersection
 *  @see 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()
		// Bug: poorly constructed error message
	    );
	    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

    /** get the intersection description in a form like that used for input
     *  @return the textual description
     */
    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
     */
    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
 *  @see Intersection
 */
class Sink extends Intersection {

    /** Sink intersection constructor
     *  @param sc scanner from which the description is taken
     *  @param name of the intersection the caller already scanned
     */
    Sink( Scanner sc, String name ) {
	super( name );
	ScanSupport.lineEnd( sc, ()->this.toString() );
    }

    /** get the intersection description in a form like that used for input
     *  @return the textual description
     */
    public String toString() {
	return  super.toString() + " sink";
    }

    /** simulate arrival of one vehicle at this sink intersection
     *  @param time When the vehicle arrives
     */
    public void arrivalEvent( float time, int dir ) {
	// Bug: what really goes here?
	System.out.println(
	    "Vehicle arrived at " + this.toString() + " at " + 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

/** RoadNetwork is the main class
 *  @see Road
 *  @see Intersection
 *  @see ScanSupport
 *  @see Errors
 *  @see Simulator
 *  This class builds a road network consisting of Road and Intersection
 *  objects and then runs the simulation using Simulator.run
 */
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) {
		Simulator.run();
	    } else {
		printNetwork();
	    }
        } catch (FileNotFoundException e) {
	    Errors.fatal( "Can't open the file" );
	}
    }
}