// RoadNetwork.java
/** Road network simulator (or it will become one once it's done)
 *  @author Douglas W. Jones
 *  @version Mar. 24, 2021
 *    This version contains partial code for vehicle creation
 *    and a framework for navigation.  Vehicles navigate at random, but:
 *     the lists of outgoing roads from each intersection is eimpty
 *     until this is fixed, we can't do anything!
 */

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

/** Centralized error reporting tools
 *  error reports are output to System.err (standard error, aka stderr)
 */
abstract class Error {
    private Error() {} // prevent construction of any instances!  Never called!
    private static int errorCount = 0;

    /** Fatal error
     *  @param msg -- the warning message
     *  this never returns, the application is terminated abnormally
     */
    public static void fatal( String msg ) {
	System.err.println( "Error: " + msg );
	System.exit( 1 ); // report failure to the OS (or to the shell)
    }

    /** Non-fatal warning
     *  @param msg -- the warning message
     */
    public static void warn( String msg ) {
	System.err.println( "Warning: " + msg );
	errorCount = errorCount + 1;
    }

    /** If there have been any warnings prior to this call, exit
     */
    public static void exitIfWarnings() {
	if (errorCount > 0) {
	    System.exit( 1 ); // report failure to the OS (or to the shell)
	}
    }
}

/** Support for scanning input files with error reporting
 *  @see Error
 *  @see java.util.Scanner
 *  Ideally, this would be extend class Scanner, but class Scanner is final
 *  Therefore, this is a wrapper class around class Scanner
 */
class MyScanner {
    Scanner sc; // the scanner we are wrapping

    public MyScanner( File f ) throws FileNotFoundException {
	sc = new Scanner( f );
    }

    // methods that we wish we could inhereit from Scanner
    public boolean hasNext() { return sc.hasNext(); }
    public boolean hasNextFloat() { return sc.hasNextFloat(); }
    public String next() { return sc.next(); }

    // patterns that matter here, all will match the empty string
    private static final Pattern delimPat = Pattern.compile( "[ \t\n\r]*" );
    private static final Pattern notNamePat
	= Pattern.compile( "[^A-Za-z]*|" );
    private static final Pattern namePat
	= Pattern.compile( "([A-Za-z][0-9A-Za-z]*)|" );
    private static final Pattern notFloatPat
	= Pattern.compile( "[^-0-9]*|" );
    private static final Pattern floatPat = Pattern.compile(
	"(-|)(([0-9][0-9]*\\.[0-9]*)|([0-9]*\\.[0-9][0-9]*)|([0-9]*))"
    );

    /** tool to defer computation of messages output by methods of MyScanner
     *  To pass a specific message, create a subclass of Message to do it
     */
    public interface Message {
	String myString();
    }

    // new methods added to class Scanner

    /** get the next name from the scanner or complain if missing
     *  Names start with letter then letters or digits up to anything else.
     *  @param defaut  -- return value if there is no next item
     *  @param errorMesage -- the message to complain with
     *  @return the next item or the default
     */
    public String getNextName( String defalt, Message errorMessage ) {
	sc.skip( delimPat );
	String errorText = sc.skip( notNamePat ).match().group();
	String name = sc.skip( namePat ).match().group();

	if (!errorText.isEmpty()) {
	    Error.warn( errorMessage.myString() + " skipped " + errorText );
	}
	if (name.isEmpty()) {
	    Error.warn( errorMessage.myString() );
	    return defalt;
	} else {
	    return name;
	}
    }

    /** get the next float from the scanner or complain if missing
     *  only support 0.0 0. .0 . (no exponent field allowed)
     *  @param defalt  -- return value if there is no next item
     *  @param errorMesage -- the message to complain with
     *  @return the next item or the defalt
     */
    public float getNextFloat( float defalt, Message errorMessage ) {
	sc.skip( delimPat );
	String errorText = sc.skip( notFloatPat ).match().group();
	String text = sc.skip( floatPat ).match().group();

	if (!errorText.isEmpty()) {
	    Error.warn( errorMessage.myString() + " skipped " + errorText );
	}
	if ( text.isEmpty() ) {
	    Error.warn( errorMessage.myString() );
	    return defalt;
	} else {
	    return Float.parseFloat( text );
	    // this will not throw uncheckedException because text is valid
	}
    }

    // patterns for use with the NextLiteral routines
    public static final Pattern beginParen = Pattern.compile( "\\(|" );
    public static final Pattern endParen = Pattern.compile( "\\)|" );
    public static final Pattern dash = Pattern.compile( "-|" );
    public static final Pattern semicolon = Pattern.compile( ";|" );

    /** try to get the next literal from the scanner
     *  @param literal -- the literal to get
     *  @returns true if the literal was present and skipped, false otherwise
     *  The literal parameter must be a pattern that can match the empty string
     *  if the desired literal is not present.
     */
    public boolean tryNextLiteral( Pattern literal ) {
	sc.skip( delimPat ); // allow delimiter before literal!
	String s = sc.skip( literal ).match().group();
	return !s.isEmpty();
    }

    /** get the next literal from the scanner or complain if missing
     *  @param literal -- the literal to get
     *  @param errorMesage -- the message to complain with (lambda expression)
     *  @see tryNextLiteral for the mechanism used.
     */
    public void getNextLiteral( Pattern literal, Message errorMessage ) {
	if ( !tryNextLiteral( literal ) ) {
	    Error.warn( errorMessage.myString() );
	}
    }
}

/** Wrapper extending class Random, turning it into a singleton class
 *  @see Random
 *  Ideally, no user should ever create an instance of Random, all use this!
 *  Users can call MyRandom.stream.anyMethodOfRandom() (or of MyRandom)
 *              or MyRandom.stream().anyMethodOfRandom()
 *  Users can allocate MyRandom myStream = MyRandom.stream;
 *                  or MyRandom myStream = MyRandom.stream();
 *  No matter how they do it, they get the same stream
 */
class MyRandom extends Random {
    public static final MyRandom stream = new MyRandom(); // the only stream;

    // nobody can construct a MyRandom except the above line of code
    private MyRandom() {
	super();
    }

    /* alternative access to stream
     * Returns the only stream
     */
    public static MyRandom stream() {
	return stream;
    }

    // add distributions that weren't built in

    /** exponential distribution
     *  @param mean -- the mean value of the distribution
     *  @return a positive exponentially distributed random value
     */
    public double nextExponential( double mean ) {
	return mean * -Math.log( this.nextDouble() );
    }
}

/** Framework for discrete event simulation
 */
class Simulator {
    private Simulator() {} // prevent construction of instances!  Don't call!

    /** Functional interface for scheduling actions to be done later
     *  Users will generally never mention Action or trigger because
     *  this is used to support lambda expressions passed to schedule().
     */
    public static interface Action {
	void trigger( double time );
    }

    private static class Event {
	public final double time; // when will this event occur
	public final Action act;  // what to do then
	public Event( double t, Action a ) {
	    time = t;
	    act = a;
	}
    }

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

    /** Schedule an event to occur at a future time
     *  @param t, the time of the event
     *  @param a, what to do for that event
     *  example:
     *  <pre>
     *    Simulator.schedule( now+later, (double t)-> whatToDo( then, stuff ) );
     *  </pre>
     */
    public static void schedule( double t, Action a ) {
	eventSet.add( new Event( t, a ) );
    }

    /** Run the simulation
     *  Before running the simulation, schedule the initial events
     *  all of the simulation occurs as side effects of scheduled events
     */
    public static void run() {
	while (!eventSet.isEmpty()) {
	    Event e = eventSet.remove();
	    e.act.trigger( e.time );
	}
    }
}

/** Vehicles drive over roads through intersections
 *  @see Road
 *  @see Intersection
 */
class Vehicle {

    // BUG no known attributes

    private static final MyRandom rand = MyRandom.stream;

    /** The vehicle makes navigation decisions
     *  @param i -- the intersection the vehicle is at
     *  @param r -- the set of available outgoing roads
     *  @return the road it picked
     */
    public Road pickOutgoing( Intersection i, ArrayList<Road> r ) {
	// BUG drivers don't know where they're going, they just turn at random
	return r.get( rand.nextInt( r.size() ) );
    }
}

/** Roads connect intersections
 */
class Road {

    // instance variables
    private final Intersection source;      // road from here
    private final Intersection destination; // road to there
    private final double travelTime;	    // time in seconds

    // static information about all roads
    // BUG:  only public so test code can iterate over it -- alternatives?
    public final static LinkedList<Road> all = new LinkedList<>();

    /** Read a road description and construct it
     *  @param in -- the Scanner from which the road description is read
     */
    public Road( MyScanner in ) {
	final String srcname; // name of source intersection
	final String dstname; // name of destination intersection
	final float travtim;  // temporary travel time

	srcname = in.getNextName( "???", ()-> "road: source missing" );
	dstname = in.getNextName( "???",
	    ()-> "road " + srcname + ": destination missing"
	);

	travtim = in.getNextFloat( 99999F,
	    ()-> "road " + srcname + " " + dstname + ": travel time missing"
	);

	in.getNextLiteral( MyScanner.semicolon,
	    ()-> "road " + srcname + " " + dstname + " " + travtim
			 + ": semicolon missing"
	);

	// BUG:  What about time units?

	if (travtim <= 0.0F) {
	    Error.warn(
		"road " + srcname + " " + dstname + " " + travtim
		+ ": negative travel time?"
	    );
	    travelTime = 99999F;
	} else  {
	    travelTime = travtim;
	}

	// look up the source and destination intersections
	source = Intersection.lookup( srcname );
	if (source == null) {
	    Error.warn(
		"road " + srcname + " " + dstname + " " + travtim
		+ ": undefined source intersection?"
	    );
	}
	destination = Intersection.lookup( dstname );
	if (destination == null) {
	    Error.warn(
		"road " + srcname + " " + dstname + " " + travtim
		+ ": undefined destination intersection?"
	    );
	}

	all.add( this );
    }

    // Behavior for roads

    /** A vehicle enters the road from an intersection
     *  @param time of entry
     *  @param v -- the vehicle
     *  Typically called from intersection
     */
    public void enter( double time, Vehicle v ) {
	Simulator.schedule( time + travelTime, (double t)-> exit( t, v ) );
	// BUG the travel time could have been perturbed with a random element
	// BUG the travel time could have been adjusted for congestion of road
    }

    /** A vehicle exits the road
     */
    private void exit( double time, Vehicle v ) {
	destination.arrive( time, v );
	// BUG does the intersection care what incoming road I entered from?
    }

    // Utility stuff for Road

    /** Reconstruct a string approximation of the text used to create this road
     *  WARNING: Never call this until after a call to Error.exitIfWarnings()
     */
    public String toString() {
	return "road " + source.name + " " + destination.name
	     + " "     + travelTime  + " ;";
    }
}

/** Intersections are connected by roads
 */
class Intersection {
    // instance variables of each intersection
    public final String name;           // the name of the intersection
    private final double traversalTime; // time in seconds

    // BUG: is collection the right class?  Should I pick a subclass?
    private ArrayList<Road> incoming = new ArrayList<>(); // roads to here
    private ArrayList<Road> outgoing = new ArrayList<>(); // roads from here

    boolean occupied = false; // is there a vehicle in this intersection

    // FIFO queue of vehicles waiting or in this intersection, initially empty
    LinkedList<Vehicle> waiting = new LinkedList<>();

    // static data about all the intersections
    // BUG:  only public so test code can iterate over it -- alternatives?
    public final static LinkedList<Intersection> all = new LinkedList<>();

    /** Constructor is needed to set final fields
     *  @param n -- the name of the intersection
     *  @param t -- the traversal time
     */
    protected Intersection( String n, double t ) {
	name = n;
	traversalTime = t;
    }

    /** Factory to Read an intersection description and construct it
     *  @param in -- the Scanner from which the intersection description is read
     *  Note: This does not return the newly allocated object, it merely adds
     *  it to the list of all intersections.
     */
    public static void newOne( MyScanner in ) {
	String n = in.getNextName( "???", ()-> "intersection: name missing" );
	float t = in.getNextFloat(
	    99999F, ()-> "intersection " + n + ": traversal time missing"
	);

	// BUG:  What about time units?

	if (lookup( n ) != null) {
	    Error.warn(
		"intersection " + n + " " + t + ": name redefined?" );
	    // BUG: anything else to do in this case?
	}

	if (!in.tryNextLiteral( MyScanner.semicolon )) {
	    String subclass = in.getNextName( "???",
	       ()-> "intersection " + n + " " + t
		  + ": subclass missing"
	    );

	    if ("stoplight".equals( subclass ) ) {
		all.add( new Stoplight( in, n, t ) );
	    } else if ("source".equals( subclass ) ) {
		all.add( new Source( in, n, t ) );
	    } else {
		Error.warn( "intersection " + n + " " + t + " " + subclass
			  + ": not a kind of intersection" );
		all.add( new Intersection( n, t ) ); // prevents error cascades
	    }

	    in.getNextLiteral( MyScanner.semicolon,
		()-> "intersection " + n + " " + t + ": semicolon missing"
	    );
	} else {
	    all.add( new Intersection( n, t ) );
	}
    }

    // Behavior for intersections

    /** a vehicle arrives at this intersection, usually from a road
     *  @param time the vehicle arrives
     *  @param v the vehicle that arrives
     */
    public void arrive( double time, Vehicle v ) {
	waiting.add(v);
	if (!occupied) {
	    occupied = true;
	    Simulator.schedule(
		time + traversalTime, (double t)-> depart( t )
	    );
	}
    }

    /** a vehicle departs from this intersection
     *  @param time the vehicle arrives
     *  @param v the vehicle that arrives
     */
    public void depart( double time ) {
	Vehicle v = waiting.remove();
	if (waiting.isEmpty()) {
	    occupied = false;
	}
	v.pickOutgoing( this, outgoing ).enter( time, v );
    }

    // Utility stuff for intersections

    public String toString() {
	return "intersection " + name + " " + traversalTime + " ;";
    }

    /** look up an interseciton by name
     *  @param name -- the textual name of the intersetion
     *  @return the Intersection object or null if there is none
     */
    public static Intersection lookup( String name ) {
	for (Intersection i: all) if (i.name.equals( name )) return i;
	return null;
    }
}

/** Sources are a kind of Intersection that generates traffic
 *  Typically, sourcers will represent edge points on the road
 *  network where cars enter from the outside world.
 */
class Source extends Intersection {
    private final double interval; // average inter-arrival time

    /** constructor called only from the factory in class Intersection
     *  @param in the scanner from which the stoplight description is read
     *  @param name the name of the intersection
     *  @param traversalTime the traversal time of that intersection
     *  This code assumes that "intersection name time source" has
     *  already been scanned from the input and that it will scan the
     *  sources period before returning to code that scans the
     *  trailing semicolon.
     */
    protected Source( MyScanner in, String name, float traversalTime ) {
	super( name, traversalTime );
	interval = in.getNextFloat( 999.9F,
	    ()-> this.toString() + " source: interval expected" );
	if (interval <= 0.0) {
	    Error.warn( this.toString() + " source" + interval
		      + ": interval must be positive" );
	}
	Simulator.schedule(
	    MyRandom.stream.nextExponential( interval ),
	    (double t)-> create( t )
	);
    }

    private void create( double time ) {
	Simulator.schedule(
	    time + MyRandom.stream.nextExponential( interval ),
	    (double t)-> create( t )
	);

	this.arrive( time, new Vehicle() );
    }
}

/** Stoplights are a kind of Intersection with distinct behavior
 */
class Stoplight extends Intersection {
    private final double interval; // period of stoplight

    /** constructor called only from the factory in class Intersection
     *  @param in the scanner from which the stoplight description is read
     *  @param name the name of the intersection
     *  @param traversalTime the traversal time of that intersection
     *  This code assumes that "intersection name time stoplight" has
     *  already been scanned from the input and that it will scan the
     *  stop-light's period before returning to code that scans the
     *  trailing semicolon.
     */
    protected Stoplight( MyScanner in, String name, float traversalTime ) {
	super( name, traversalTime );
	interval = in.getNextFloat( 999.9F,
	    ()-> this.toString() + " stoplight: interval expected" );
	if (interval <= 0.0) {
	    Error.warn( this.toString() + " stoplight " + interval
		      + ": interval must be positive" );
	}

	// BUG: eventually, stop-lights ought to do something to traffic?

	Simulator.schedule( MyRandom.stream.nextDouble() * interval,
	    (double t)->lightChange( t )
	);
    }

    private void lightChange( double time ) {
	Simulator.schedule( time + interval, (double t)->lightChange( t ) );
    }
}

public class RoadNetwork {

    /** build a road network model by scanning an input file
     *  @param in -- the scanner used to read the file
     *  Input file contains keywords road and intersection,
     *  details beyond that are handled by the appropriate classes
     */
    private static void buildModel( MyScanner in ) {
	double endOfTime = 0.0;
	while (in.hasNext()) {
	    String keyword = in.getNextName(
		"???", ()-> "intersection: name missing"
	    );
	    if ("intersection".equals( keyword )) {
		Intersection.newOne( in );
	    } else if ("road".equals( keyword )) {
		new Road( in );
	    } else if ("end".equals( keyword )) {
		double et; // effectively final end of time
		et = in.getNextFloat( 0.01F, ()-> "end: time expected" );
		in.getNextLiteral( MyScanner.semicolon,
		    ()-> "end " + et + ": semicolon missing"
		);
		if (et <= 0) {
		    Error.warn( "end " + et + ": non positive end time?" );
		}
		if (endOfTime != 0.0) {
		    Error.warn( "end " + et + ": duplicate end time?" );
		} else {
		    endOfTime = et;
		}
	    } else {
		Error.warn( "not a keyword in the input: " + keyword );
	    }
	}
	if (endOfTime == 0.0) {
	    Error.warn( "end of time not specified" );
	} else {
	    Simulator.schedule( endOfTime, (double t)->System.exit(0) );
	}
	Error.exitIfWarnings(); // if there were warnings, don't try to go on
    }

    /** Print out the road network.
     *  This is intended to help with debugging buildmodel
     */
    private static void printModel() {
	for (Intersection i: Intersection.all) {
	    System.out.println( i.toString() );
	}
	for (Road r: Road.all) {
	    System.out.println( "" + r );
	}
    }

    /** main method mostly concerned with command line arguments
     *  @param args -- the command line arguments
     *  Want just one argument, the file name for model description
     */
    public static void main( String[] args ) {
	// arg[0] should be the name of a file describing a road network
	if (args.length < 1) {
	    Error.fatal( "missing command line argument, a file name" );
	}
	if (args.length > 1) {
	    Error.warn( "extra command line argument: " + args[1] );
	}
	try {
	    buildModel( new MyScanner( new File( args[0] ) ) );
	    // printModel(); // BUG: this is only for debugging
	    Simulator.run();
	} catch ( FileNotFoundException e ) {
	    Error.fatal( "could not open file: " + args[0] );
	}
    }
}