// RoadNetwork.java
/**
 * Classes that define the topology of a road network.
 * @author Douglas Jones
 * @version MP1?
 */

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 {
        /** Framework for discrete event simulation.
         */

        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 )
        );

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

interface ByName {
        /** Framework to fake up Call by Name parameter passing.
         */
        String s();
                /** object of class ByName can return a string.
                  */
}

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
         */
        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 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;

                Simulator.schedule(
                        t + travelTime,
                        (float time)->this.exit( v, time )
                );
        }

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

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

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

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

        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

        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;
                        Simulator.schedule(
                                t + travelTime,
                                (float time)->this.exit( v, time )
                        );
                }
        }

        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();
                        Simulator.schedule(
                                t + travelTime,
                                (float time)->this.exit( v1, time )
                        );
                }
                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 );
                Simulator.schedule( // the first car leaves here immediately
                        0,
                        (float time)->this.exit(
                                new Vehicle(),
                                time
                        )
                );
        }

        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 );
                Simulator.schedule(
                        t,
                        (float time)->d.enter( v, time )
                );

                // 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() ) );
        }
}

class Event {
        /** Events mark arrival of vehicles at Intersections.
         *  @see Intersection
         *  @see Vehicle
         */
        float time;         //when the vehicle arrives
        Intersection place; //where vehicle arrives
        // Bug: is this right?  There may be many queues at intersection
        // Bug: how do we know which queue the road leads to?
}

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] + "'" );
                }
        }
}