# You may have to edit this file to delete header lines produced by # mailers or news systems from this file (all lines before these shell # comments you are currently reading). # Shell archive made by dwjones on Mon 26 Apr 2021 11:56:27 AM CDT # To install this software on a UNIX system: # 1) create a directory (e.g. with the shell command mkdir stuff) # 2) change to that directory (e.g. with the command cd stuff), # 3) direct the remainder of this text to sh (e.g. sh < ../savedmail). # This will make sh create files in the new directory; it will do # nothing else (if you're paranoid, you should scan the following text # to verify this before you follow these directions). Then read README # in the new directory for additional instructions. cat > README <<\xxxxxxxxxx ROAD NETWORK SIMULATOR ====================== Version: Apr 12, 2021 Author: Douglas W. Jones Copyright: Creative Commons Share and Share Alike License 0 (public domain). Disclaimer: If this works for you, great, I take no responsibility for it. Status: This version did pass a minimal test, it compiled and ran with the provided test data. Files in this Project --------------------- * README --- This file * Error.java --- error reporting framework * MyRandom.java --- extension to Java class Random * MyScanner.java --- wrapper pretending to extend Java class Scanner * Simulator.java --- discrete event simulation framework * Vehicle.java --- vehicles in the simulation of traffic flow * Road.java --- roads in the simulation of traffic flow * Intersection.java --- intersections in the simulation of traffic flow * RoadNetwork.java --- the main program for the traffic flow simulator * Makefile --- the Makefile for the traffic simulator * Fuzz.java --- a fuzz test generator (random output) * test --- demonstration input to RoadNetwork * testScript --- out of date test shell script for RoadNetwork Instructions for Building and Testing ------------------------------------- To compile, use this shell command: make --- the road network javac Fuzz.java --- if you need the fuzz tester To clean out the files the compiler created: rm -f *.class To demonstrate or test the compiled code: make demo See Makefile for details Note that testScript has not been maintained for the moste recent version of the road network simulator, but it would be nice to bring it up to date To Do List ---------- * There is no manual for the road network simulator, one would be useful. * The test script needs updating to cover the newer features in the simulator. * There are BUG notices (always capitalized) in the code. xxxxxxxxxx cat > RoadNetwork.java <<\xxxxxxxxxx // RoadNetwork.java /* Road network simulator * @author Douglas W. Jones * @version Mar. 31, 2021 * This working version contains working code for vehicle creation * and a framework for navigation. Vehicles navigate at random, but: * BUG: There is no check that non-sink intersections have outgoing roads */ 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; 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 )) { IntersectionImp.newOne( in ); } else if ("road".equals( keyword )) { new RoadImp( 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] ); } } } xxxxxxxxxx cat > Road.java <<\xxxxxxxxxx // Road.java import java.util.LinkedList; /** Roads connect intersections * @author Douglas W. Jones * @version Mar. 31, 2021 Lifted from RoadNetwork.java of that date */ public interface Road { // static information about all roads // BUG: only public so test code can iterate over it -- alternatives? public final static LinkedList all = new LinkedList<>(); // 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 ); } xxxxxxxxxx cat > Intersection.java <<\xxxxxxxxxx // Intersection.java import java.util.LinkedList; import java.util.ArrayList; /** Intersections are connected by roads * @author Douglas W. Jones * @version Mar. 31, 2021 Lifted from RoadNetwork.java of that date * BUG: There is no check that non-sink intersections have outgoing roads */ public interface Intersection { // static data about all the intersections // BUG: only public so test code can iterate over it -- alternatives? public final static LinkedList all = new LinkedList<>(); /** public getter method for the name field of an intersection. * Interfaces cannot contain fields, so we replace the field with a getter. * @returns the name */ String name(); /** add a road to the list of incoming roads * @param r the road * Called only from constructor for roads. */ void setIncoming( Road r ); /** add a road to the list of outgoing roads * @param r the road * Called only from constructor for roads. */ void setOutgoing( Road r ); /** check to see if an incoming direction is legal * @param d the direction * @param msg the message, passed as a lambda expression */ void checkDirections( int d, MyScanner.Message msg ); // Behavior for intersections /** a vehicle arrives at this intersection, usually from a road * @param time the vehicle arrives * @param v the vehicle that arrives * @param dir the vehicle's arrival direction, ignored here */ void arrive( double time, Vehicle v, int dir ); /** a vehicle departs from this intersection * @param time the vehicle departs */ void depart( double time ); /** 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; } } xxxxxxxxxx cat > Vehicle.java <<\xxxxxxxxxx // Vehicle.java import java.util.ArrayList; /** Vehicles drive over roads through intersections * @see Road * @see Intersection * @author Douglas W. Jones * @version Mar. 31, 2021 Lifted from RoadNetwork.java of that date */ public interface Vehicle { /** 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 */ Road pickOutgoing( Intersection i, ArrayList r ); } xxxxxxxxxx cat > RoadImp.java <<\xxxxxxxxxx // Road.java import java.util.LinkedList; /** Roads connect intersections * @author Douglas W. Jones * @version Mar. 31, 2021 Lifted from RoadNetwork.java of that date */ public class RoadImp implements Road { // instance variables private final Intersection source; // road from here private final Intersection destination; // road to there private final double travelTime; // time in seconds private final int direction; // direction of this road /** Read a road description and construct it * @param in -- the Scanner from which the road description is read */ public RoadImp( 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" ); if (!in.tryNextLiteral( MyScanner.semicolon )) { direction = in.getNextInt( 0, ()-> "road " + srcname + " " + dstname + " " + travtim + ": road direction missing" ); // sanity check on directions done after we get dst intersection! in.getNextLiteral( MyScanner.semicolon, ()-> "road " + srcname + " " + dstname + " " + travtim + " " + direction + ": semicolon missing" ); } else { direction = 0; } // BUG: What about time units? if (travtim <= 0.0F) { Error.warn( "road " + srcname + " " + dstname + " " + travtim + " " + direction + ": 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 + " " + direction + ": undefined source intersection?" ); } else { // tell the intersectio that it is connected source.setOutgoing( this ); } destination = Intersection.lookup( dstname ); if (destination == null) { Error.warn( "road " + srcname + " " + dstname + " " + travtim + " " + direction + ": undefined destination intersection?" ); } else { // tell the intersectio that it is connected destination.setIncoming( this ); destination.checkDirections( direction, ()-> "road " + srcname + " " + dstname + " " + travtim + " " + direction ); } Road.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, direction ); // 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 + " ;"; } } xxxxxxxxxx cat > IntersectionImp.java <<\xxxxxxxxxx // IntersectionImp.java import java.util.LinkedList; import java.util.ArrayList; /** Intersections are connected by roads * @author Douglas W. Jones * @version Mar. 31, 2021 Lifted from RoadNetwork.java of that date * BUG: There is no check that non-sink intersections have outgoing roads */ public class IntersectionImp implements Intersection { // instance variables of each intersection public final String name; // the name of the intersection private final double traversalTime; // time in seconds protected final int directions; // number of incoming directions private ArrayList incoming = new ArrayList<>(); // roads to here private ArrayList 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 waiting = new LinkedList<>(); /** Constructor is needed to set final fields * @param n -- the name of the intersection * @param tt -- the traversal time * @param d -- the number of incoming road directions */ protected IntersectionImp( String n, double tt, int d ) { name = n; traversalTime = tt; directions = d; } /** Getter method for the name field of an intersection. * @returns the name */ public String name() { return name; } /** 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 tt = in.getNextFloat( 99999F, ()-> "intersection " + n + ": traversal time missing" ); // BUG: What about time units? int d = in.getNextInt( 1, ()-> "intersection " + n + " " + tt + ": number of directions missing" ); // sanity checks on fields if (Intersection.lookup( n ) != null) Error.warn( "intersection " + n + " " + tt + " " + d + ": name redefined?" ); if (tt < 0.0F) Error.warn( "intersection " + n + " " + tt + " " + d + ": negative time?" ); if (d < 1) Error.warn( "intersection " + n + " " + tt + " " + d + ": negative directions?" ); if (!in.tryNextLiteral( MyScanner.semicolon )) { String subclass = in.getNextName( "???", ()-> "intersection " + n + " " + tt + " " + d + ": subclass missing" ); if ("stoplight".equals( subclass ) ) { all.add( new Stoplight( in, n, tt, d ) ); } else if ("source".equals( subclass ) ) { all.add( new Source( in, n, tt, d ) ); } else if ("sink".equals( subclass ) ) { all.add( new Sink( in, n, tt, d ) ); } else { Error.warn( "intersection " + n + " " + tt + " " + d + " " + subclass + ": not a kind of intersection" ); all.add( new IntersectionImp( n, tt, d ) ); //stop error cascade } in.getNextLiteral( MyScanner.semicolon, ()-> "intersection " + n + " " + tt + " " + d + ": semicolon missing" ); } else { Intersection.all.add( new IntersectionImp( n, tt, d ) ); } } // Additional tools for constructing the network /** add a road to the list of incoming roads * @param r the road * Called only from constructor for roads. */ public void setIncoming( Road r ) { incoming.add( r ); } /** add a road to the list of outgoing roads * @param r the road * Called only from constructor for roads. */ public void setOutgoing( Road r ) { outgoing.add( r ); } /** check to see if an incoming direction is legal * @param d the direction * @param msg the message, passed as a lambda expression */ public void checkDirections( int d, MyScanner.Message msg ) { if ((d < 0) || (d >= directions)) { Error.warn( msg.myString() + ": direction out of bounds" ); } } // Behavior for intersections /** a vehicle arrives at this intersection, usually from a road * @param time the vehicle arrives * @param v the vehicle that arrives * @param dir the vehicle's arrival direction, ignored here */ public void arrive( double time, Vehicle v, int dir ) { System.out.println( // Debug output, comment out if not debugging v.toString() + " arrived at " + name + " at " + time ); 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 departs */ 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 + " " + directions + ";"; } } /** 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 IntersectionImp { 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 n the name of the intersection * @param tt the traversal time of that intersection * @param d the number of directions of this 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 n, float tt, int d ) { super( n, tt, d ); 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 VehicleImp(), 0 ); } } /** Sinks are a kind of Intersection that consumes traffic * Typically, sinks will represent edge points on the road * network where cars leave to the outside world. */ class Sink extends IntersectionImp { /** constructor called only from the factory in class Intersection * @param in the scanner from which the stoplight description is read * @param n the name of the intersection * @param tt the traversal time of that intersection * @param d the number of directions of this 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 Sink( MyScanner in, String n, float tt, int d ) { super( n, tt, d ); } // Behavior for intersections /** a vehicle arrives at this sink intersection, usually from a road * @param time the vehicle arrives * @param v the vehicle that arrives * @param dir the vehicle's arrival direction, ignored here */ public void arrive( double time, Vehicle v, int dir ) { System.out.println( // Debug output, comment out if not debugging v.toString() +" arrived at "+ name +" at "+ time +" and exiting" ); // conceptually vehicle is crushed and recycled // rely on Java to reclaim vehicles resources // this only works if we don't accidentally retain a handle on v } } /** Stoplights are a kind of Intersection with distinct behavior */ class Stoplight extends IntersectionImp { // set and fixed at initialization private final double interval; // period of stoplight // details that vary during simulation private int direction; // which direction is green right now? class LinkedListVehicle extends LinkedList {} private final LinkedListVehicle[] blocked; // who's waiting for green? // note: class LinkedListVehicle solves a problem that Java has with // arrays of generic types. Adding this stupid class makes Java happy // needed to randomize stop-light direction at startup private static final MyRandom rand = MyRandom.stream; /** constructor called only from the factory in class Intersection * @param in the scanner from which the stoplight description is read * @param n the name of the intersection * @param tt the traversal time of that intersection * @param d the number of directions of this 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 n, float tt, int d ) { super( n, tt, d ); interval = in.getNextFloat( 999.9F, ()-> this.toString() + " stoplight: interval expected" ); if (interval <= 0.0) { Error.warn( this.toString() + " stoplight " + interval + ": interval must be positive" ); } blocked = new LinkedListVehicle[directions]; for (int i = 0; i < directions; i++) { blocked[i] = new LinkedListVehicle(); } direction = rand.nextInt( directions ); Simulator.schedule( MyRandom.stream.nextDouble() * interval, (double t)->lightChange( t ) ); } // Behavior for stop-light intersections private void lightChange( double time ) { Simulator.schedule( time + interval, (double t)->lightChange( t ) ); direction = (direction + 1) % directions; while (!blocked[direction].isEmpty()) { super.arrive( time, blocked[direction].remove(), direction ); } } /** a vehicle arrives at this stop light * @param time the vehicle arrives * @param v the vehicle that arrives * @param dir the vehicle's arrival direction */ public void arrive( double time, Vehicle v, int dir ) { if (direction == dir) { super.arrive( time, v, dir ); } else { System.out.println( // Debug output, comment out if not debugging v.toString() + " blocked at " + name + " at " + time ); blocked[dir].add( v ); // make this vehicle wait! } } } xxxxxxxxxx cat > VehicleImp.java <<\xxxxxxxxxx // Vehicle.java import java.util.ArrayList; /** Vehicles drive over roads through intersections * @see Road * @see Intersection * @author Douglas W. Jones * @version Mar. 31, 2021 Lifted from RoadNetwork.java of that date */ public class VehicleImp implements 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 r ) { // BUG drivers don't know where they're going, they just turn at random return r.get( rand.nextInt( r.size() ) ); } } xxxxxxxxxx cat > MyScanner.java <<\xxxxxxxxxx // MyScanner.java import java.io.File; import java.io.FileNotFoundException; import java.util.Scanner; import java.util.regex.Pattern; /** Support for scanning input files with error reporting * @author Douglas W. Jones * @version Apr. 12, 2021 Better Javadoc Comments * @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 */ public class MyScanner { Scanner sc; // the scanner we are wrapping /** Create a new scanner to read from a particular file * @param f the file to be scanned * @throws FileNotFoundException if the file cannot be opened for reading */ 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 NotIntPat = Pattern.compile( "([^-0-9]*)|" ); private static final Pattern intPat = Pattern.compile( "((-[0-9]|)[0-9]*)" ); 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 an implementation of Message. * Most users will use Messages implicitly by using lambda expressions * in calls to methods of class MyScanner. When a parameter implementing * Message is expected, the actual parameter will typically resemble this: *

     *  ()-> "some string-valued expression" )
     *  
*

A lambda expression is used here instead of a simple string because * in most cases, the string will be an error message constructed by * concatenation of several components. The usual case is that there * is no error, and in that case the concatenations should not be done. * By using a lambda expression, we defer the computation until we are * sure we need 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. *

Typically, errorMessage is passed as a lambda expression, * so a call might look like this: *

     *  String n = getNextName( "?", ()-> context + "name expected?" );
     *  
* @param defalt return value if there is no next item * @param errorMessage 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 integer from the scanner or complain if missing. *

Typically, errorMessage is passed as a lambda expression, * so a call might look like this: *

     *  String n = getNextInt( 0, ()-> "number expected?" + context )
     *  
* @param defalt return value if there is no next integer * @param errorMessage the message to complain with (lambda expression) * @return the next integer or the defalt */ public int getNextInt( int defalt, Message errorMessage ) { // first skip the delimiter, accumulate anything that's not an int String notInt = sc.skip( delimPat ).skip( NotIntPat ).match().group(); // second accumulate the int, if any String text = sc.skip( delimPat ).skip( intPat ).match().group(); if (!notInt.isEmpty()) { // there's something else where an int belonged Error.warn( errorMessage.myString() + ": int expected, skipping " + notInt ); } if (text.isEmpty()) { // missing name Error.warn( errorMessage.myString() ); return defalt; } else { // the name was present and it matches intPat return Integer.parseInt( text ); } } /** Get the next float from the scanner or complain if missing. *

Floating point numbers have the eformat "0.0" "0." or ".0"; this * code does not support exponential notation. *

Typically, errorMessage is passed as a lambda expression, * so a call might look like this: *

     *  String n = getNextFloat( 0.0, ()-> context + "number expected?" );
     *  
* @param defalt return value if there is no next item * @param errorMessage 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 } } /** Pattern for use with tryNextLiteral or getNextLiteral to get ( */ public static final Pattern beginParen = Pattern.compile( "\\(|" ); /** Pattern for use with tryNextLiteral or getNextLiteral to get ) */ public static final Pattern endParen = Pattern.compile( "\\)|" ); /** Pattern for use with tryNextLiteral or getNextLiteral to get - */ public static final Pattern dash = Pattern.compile( "-|" ); /** Pattern for use with tryNextLiteral or getNextLiteral to get ; */ public static final Pattern semicolon = Pattern.compile( ";|" ); /** Try to get the next literal from the scanner. *

Typically, the literal will be one of * beginParen, endParen, dash * or semicolon. These patterns all match the indicate * literal, and for technical reasons, the pattern must also match * the empty string. * @param literal the literal to get * @return true if the literal was present and skipped, false otherwise */ 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. *

Typically, the literal will be one of * beginParen, endParen, dash * or semicolon. These patterns all match the indicate * literal, and for technical reasons, the pattern must also match * the empty string. *

Typically, errorMessage is passed as a lambda expression, * so a call might look like this: *

     *  String n = getNextLiteral( dash, ()-> context + "dash expected" );
     *  
* @param literal the literal to get * @param errorMessage 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() ); } } } xxxxxxxxxx cat > Error.java <<\xxxxxxxxxx /** Centralized error reporting tools *

error reports are output to System.err (standard error, aka stderr) * @author Douglas W. Jones * @version Apr. 12, 2021 Better Javadoc Comments */ public abstract class Error { private Error() {} // prevent construction of any instances! Never called! private static int errorCount = 0; /** Report a fatal error. *

This never returns, the application is terminated abnormally. * @param msg -- the error message */ public static void fatal( String msg ) { System.err.println( "Error: " + msg ); System.exit( 1 ); // report failure to the OS (or to the shell) } /** Report a 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) } } } xxxxxxxxxx cat > MyRandom.java <<\xxxxxxxxxx // MyRandom.java import java.util.Random; /** Wrapper extending class Random, turning it into a singleton class * @see Random * @author Douglas W. Jones * @version Apr. 12, 2021 better Javadoc comments *

Class MyRandom creates exactly one instance of itself and offers * that instance to users through several interaces. * There is only one stream because use of multiple instances of a * pseudo-random-number generator risks creating streams that are correlated. * To avoid this risk, all pseudo-random numbers drawn in any application * should be produced by a single stream. */ public class MyRandom extends Random { /* The stream of pseudo-random values */ 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 of pseudo-random values * MyRandom.stream() and MyRandom.stream are alternative * ways to reference the exact same stream. */ public static MyRandom stream() { return stream; } // add distributions that weren't built in /** Draw a number from the negative 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() ); } } xxxxxxxxxx cat > Simulator.java <<\xxxxxxxxxx // Simulator.java import java.util.PriorityQueue; /** Framework for discrete event simulation * @author Douglas W. Jones * @version Apr. 19, 2021 Better information hiding for reschedule, cancel. */ 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, * when a value implementing this interface is needed, it will usually * take the form of a lambda expression like this: *

     *  (double t)-> someMethod( t, otherParameters )
     *  
*/ public static interface Action { void trigger( double time ); } /** Event is the parent of real events scheduled in the simulator *

Because class RealEvent is private to class * simulator, users cannot access fields or methods of * class event. This protects users from dangerous * errors involving access to fields that should not be touched */ public static class Event {} /** RealEvents scheduled in the simulation framework */ private static class RealEvent extends Event { public double time; // when will this event occur public final Action act; // what to do then public RealEvent( double t, Action a ) { time = t; act = a; } } // the pending event set, holding all scheduled but not triggered events private static final PriorityQueue eventSet = new PriorityQueue<>( ( RealEvent e1, RealEvent e2 )-> Double.compare( e1.time, e2.time ) ); /** Schedule an event to occur at a future time *

Typically, users schedule events using a lambda expression for * the action to be take at the scheduled time, for example: *

     *    Simulator.schedule( now+later, (double t)-> whatToDo( t, stuff ) );
     *  
*

It is important that the time of the event be passed as a lambda * parameter to the action. *

In most cases, the caller will ignore the return value because * this is only needed for events that will be cancelled or rescheduled. * @param t, the time of the event * @param a, what to do for that event * @returns a handle on the scheduled event */ public static Event schedule( double t, Action a ) { RealEvent e = new RealEvent( t, a ); eventSet.add( e ); return e; // the RealEvent is returned as an Event, minus all detail } /** Cancel a previously scheduled event. *

Note that nothing happens if the event being cancelled has * already been simulated or has not been scheduled. * @param e the event to cancel */ public static void cancel( Event e ) { RealEvent re = (RealEvent)e; // This is not free, but it's cheap // only pay this price if we cancel eventSet.remove( re ); } /** Re-schedule a previously scheduled event. *

Note that nothing happens if the event being rescheduled has * already been simulated or has not been scheduled. */ public static void reschedule( Event e, double t ) { RealEvent re = (RealEvent)e; // This is not free, but it's cheap // only pay this price if we reschedule if (eventSet.remove( re )) { re.time = t; eventSet.add( re ); } } /** 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()) { RealEvent e = eventSet.remove(); e.act.trigger( e.time ); } } } xxxxxxxxxx cat > Makefile <<\xxxxxxxxxx # Makefile for the Road Network Simulator # Author: Douglas W. Jones # Version: Apr. 19, 2021 small bug fix # Support for: # make -- make the default target # make RoadNetwork.class -- the default target # Plus the following utilities # make demo -- demonstrate the road network simulator # make clean -- delete all files created by make # make html -- make javadoc web site from simulator code # make shar -- make shell archive from this directory ######## # named categories of files: # Note: When a make target depends on less than the full list # for one of these, the individual files are listed explicitly # in order to fully document the interfile dependencies. # Note: These files are divided into groups according to the layer # they occupy in the structure of the entire program. # The grouping documents the layers, so some groups are named even # though the entire group is never used in what follows. #layer 2 ModelSrc = Road.java Intersection.java Vehicle.java ModelClasses = Road.class Intersection.class Vehicle.class #layer 2a ModelImpSrc = RoadImp.java IntersectionImp.java VehicleImp.java ModelImpClasses = RoadImp.class IntersectionImp.class VehicleImp.class #layer 3 UtilitySrc = MyScanner.java Error.java MyRandom.java Simulator.java UtilityClasses = MyScanner.class Error.class MyRandom.class Simulator.class SimulatorSource = RoadNetwork.java $(ModelSrc) $(ModelImpSrc) $(UtilitySrc) ######## # Layer 1: (default make target) the main program RoadNetwork.class: RoadNetwork.java RoadNetwork.class: Road.class Intersection.class RoadNetwork.class: RoadImp.class IntersectionImp.class RoadNetwork.class: MyScanner.class Error.class Simulator.class javac RoadNetwork.java ######## # Layer 2: core interfaces to classes of the road network model # Note: The interfaces should break (most of) the circular dependencies # We did not break the cycles! # All cycles involve parameters to one class passed down to layer 2a # The only dependencies are on class existence, not on details Road.class: Road.java Road.class: Vehicle.class javac Road.java Intersection.class: Intersection.java Intersection.class: Road.class Vehicle.class Intersection.class: MyScanner.class javac Intersection.java Vehicle.class: Vehicle.java Vehicle.class: Road.class Intersection.class javac Vehicle.java ######## # Layer 2a: core classes of the road network model RoadImp.class: RoadImp.java RoadImp.class: Intersection.class Vehicle.class RoadImp.class: MyScanner.class Error.class Simulator.class javac RoadImp.java IntersectionImp.class: IntersectionImp.java IntersectionImp.class: Road.class Vehicle.class VehicleImp.class IntersectionImp.class: $(UtilityClasses) javac IntersectionImp.java VehicleImp.class: VehicleImp.java VehicleImp.class: Road.class Intersection.class VehicleImp.class: MyRandom.class javac VehicleImp.java ######## # Layer 3: support classes for the road network simulator MyScanner.class: MyScanner.java MyScanner.class: Error.class javac MyScanner.java Error.class: Error.java javac Error.java MyRandom.class: MyRandom.java javac MyRandom.java Simulator.class: Simulator.java javac Simulator.java ######## # utility make commands demo: RoadNetwork.class java RoadNetwork test clean: rm -f *.class rm -f *.html rm -f *.css rm -f *.js rm -f package-list html: $(SimulatorSource) javadoc $(SimulatorSource) shar: README $(SimulatorSource) Makefile Fuzz.java test testScript shar README $(SimulatorSource) Makefile Fuzz.java test testScript > shar xxxxxxxxxx cat > Fuzz.java <<\xxxxxxxxxx import java.util.Random; import java.lang.NumberFormatException; /** Fuzz test generator * output a random length string of gibberish to standard output * this gibberish is in ASCII, the 128 character subset of Unicode * takes 1 command line argument, an integer, * this controls the expected output length. * @author Douglas W. Jones * @version Sept. 18, 2020 */ public class Fuzz { public static void main( String arg[] ) { Random rand = new Random(); int n = 0; // controls length of output if (arg.length != 1) { System.err.println( "argument required -- length of output file" ); System.exit( 1 ); } else try { n = Integer.valueOf( arg[0] ); } catch (NumberFormatException e) { System.err.println( "non numeric argument -- length of output" ); System.exit( 1 ); } while (rand.nextInt(n) > 0) { int nn = rand.nextInt( 1024 ); if (nn < 4) { System.out.print( (char)rand.nextInt( 32 ) ); } else if (nn < 64) { System.out.print( "\n" ); } else { System.out.print( (char)(32 + rand.nextInt( 96 )) ); } } System.out.print( '\n' ); } } xxxxxxxxxx cat > test <<\xxxxxxxxxx intersection A 0.04 1 source 0.05; intersection B 0.1 1; intersection C 0.1 2 stoplight 0.2; intersection D 0.1 1 sink; road A B 0.2; road B C 0.15 0; road A C 0.15 1; road C D 0.15 0; end 1; xxxxxxxxxx cat > testScript <<\xxxxxxxxxx #!/bin/bash # test script for the road network simulator # author Douglas Jones # version Feb. 22, 2021 # test1 java RoadNetwork -- with a missing file name echo "Error: missing command line argument, a file name" > expectedDotErr touch expectedDotOut java RoadNetwork > systemDotOut &> systemDotErr if [ $? -eq 0 ] ; then # program did System.exit( 0 ); echo "test1: java Roadnetwork -- terminated with System.exit( 0 )" else # program did System.exit( !=0 ); diff expectedDotOut systemDotOut if [ $? -ne 0 ] ; then echo "test1: java Roadnetwork -- unexpected normal output" fi diff expectedDotErr systemDotErr if [ $? -ne 0 ] ; then echo "test1: java Roadnetwork -- the wrong error message" fi fi rm expectedDotErr expectedDotOut systemDotErr systemDotOut # test2 java RoadNetwork nonexistant blather -- with a missing file name echo "Warning: extra command line argument: blather" > expectedDotErr echo "Error: could not open file: nonexistant" >> expectedDotErr touch expectedDotOut java RoadNetwork nonexistant blather > systemDotOut &> systemDotErr if [ $? -eq 0 ] ; then # program did System.exit( 0 ); echo "test2: java Roadnetwork -- terminated with System.exit( 0 )" else # program did System.exit( !=0 ); diff expectedDotOut systemDotOut if [ $? -ne 0 ] ; then echo "test2: java Roadnetwork none -- unexpected normal output" fi diff expectedDotErr systemDotErr if [ $? -ne 0 ] ; then echo "test2: java Roadnetwork none -- the wrong error message" fi fi rm expectedDotErr expectedDotOut systemDotErr systemDotOut # test3 java RoadNetwork fuzztest touch expectedDotOut java Fuzz 256 > testinput java RoadNetwork testinput blather > systemDotOut &> systemDotErr if [ $? -eq 0 ] ; then # program did System.exit( 0 ); // the likelihood of this is tiny!! echo "test3: java Roadnetwork fuzz -- terminated with System.exit( 0 )" else # program did System.exit( !=0 ); diff expectedDotOut systemDotOut if [ $? -ne 0 ] ; then echo "test3: java Roadnetwork fuzz -- unexpected normal output" fi grep exception systemDotErr if [ $? -eq 0 ] ; then echo "test3: java Roadnetwork fuzz -- threw an exception" fi fi rm expectedDotOut systemDotErr systemDotOut testinput # test4 java RoadNetwork testfile -- just one word, intersection echo "intersection" > testinput echo "Warning: intersection: name missing" > expectedDotErr echo "Warning: intersection ???: traversal time missing" >> expectedDotErr echo "Warning: intersection ??? 99999.0: subclass missing" >> expectedDotErr echo "Warning: intersection ??? 99999.0 ???: not a kind of intersection" >> expectedDotErr echo "Warning: intersection ??? 99999.0: semicolon missing" >> expectedDotErr touch expectedDotOut java RoadNetwork testinput > systemDotOut &> systemDotErr if [ $? -eq 0 ] ; then # program did System.exit( 0 ); echo "test4: java Roadnetwork -- terminated with System.exit( 0 )" else # program did System.exit( !=0 ); diff expectedDotOut systemDotOut if [ $? -ne 0 ] ; then echo "test4: java Roadnetwork none -- unexpected normal output" fi diff expectedDotErr systemDotErr if [ $? -ne 0 ] ; then echo "test4: java Roadnetwork none -- the wrong error message" fi fi rm expectedDotErr expectedDotOut systemDotErr systemDotOut testinput # test5 java RoadNetwork testfile -- one intersection, defective road echo "intersection A 1.0 ;" > testinput echo "road" >> testinput echo "Warning: road: source missing" > expectedDotErr echo "Warning: road ???: destination missing" >> expectedDotErr echo "Warning: road ??? ???: travel time missing" >> expectedDotErr echo "Warning: road ??? ??? 99999.0: semicolon missing" >> expectedDotErr echo "Warning: road ??? ??? 99999.0: undefined source intersection?" >> expectedDotErr echo "Warning: road ??? ??? 99999.0: undefined destination intersection?" >> expectedDotErr touch expectedDotOut java RoadNetwork testinput > systemDotOut &> systemDotErr if [ $? -eq 0 ] ; then # program did System.exit( 0 ); echo "test5: java Roadnetwork -- terminated with System.exit( 0 )" else # program did System.exit( !=0 ); diff expectedDotOut systemDotOut if [ $? -ne 0 ] ; then echo "test5: java Roadnetwork none -- unexpected normal output" fi diff expectedDotErr systemDotErr if [ $? -ne 0 ] ; then echo "test5: java Roadnetwork none -- the wrong error message" fi fi rm expectedDotErr expectedDotOut systemDotErr systemDotOut testinput # test6 java RoadNetwork testfile -- one intersection, defective road echo "intersection A 1.;" > testinput echo "road A" >> testinput echo "Warning: road A: destination missing" > expectedDotErr echo "Warning: road A ???: travel time missing" >> expectedDotErr echo "Warning: road A ??? 99999.0: semicolon missing" >> expectedDotErr echo "Warning: road A ??? 99999.0: undefined destination intersection?" >> expectedDotErr touch expectedDotOut java RoadNetwork testinput > systemDotOut &> systemDotErr if [ $? -eq 0 ] ; then # program did System.exit( 0 ); echo "test6: java Roadnetwork -- terminated with System.exit( 0 )" else # program did System.exit( !=0 ); diff expectedDotOut systemDotOut if [ $? -ne 0 ] ; then echo "test6: java Roadnetwork none -- unexpected normal output" fi diff expectedDotErr systemDotErr if [ $? -ne 0 ] ; then echo "test6: java Roadnetwork none -- the wrong error message" fi fi rm expectedDotErr expectedDotOut systemDotErr systemDotOut testinput # test7 java RoadNetwork testfile -- one intersection, defective road echo "intersection A 1;" > testinput echo "road A B" >> testinput echo "Warning: road A B: travel time missing" > expectedDotErr echo "Warning: road A B 99999.0: semicolon missing" >> expectedDotErr echo "Warning: road A B 99999.0: undefined destination intersection?" >> expectedDotErr touch expectedDotOut java RoadNetwork testinput > systemDotOut &> systemDotErr if [ $? -eq 0 ] ; then # program did System.exit( 0 ); echo "test7: java Roadnetwork -- terminated with System.exit( 0 )" else # program did System.exit( !=0 ); diff expectedDotOut systemDotOut if [ $? -ne 0 ] ; then echo "test7: java Roadnetwork none -- unexpected normal output" fi diff expectedDotErr systemDotErr if [ $? -ne 0 ] ; then echo "test7: java Roadnetwork none -- the wrong error message" fi fi rm expectedDotErr expectedDotOut systemDotErr systemDotOut testinput # test8 java RoadNetwork testfile -- one intersection, defective subclass echo "intersection A 1 swiggle ;" > testinput echo "Warning: intersection A 1.0 swiggle: not a kind of intersection" > expectedDotErr touch expectedDotOut java RoadNetwork testinput > systemDotOut &> systemDotErr if [ $? -eq 0 ] ; then # program did System.exit( 0 ); echo "test8: java Roadnetwork -- terminated with System.exit( 0 )" else # program did System.exit( !=0 ); diff expectedDotOut systemDotOut if [ $? -ne 0 ] ; then echo "test8: java Roadnetwork none -- unexpected normal output" fi diff expectedDotErr systemDotErr if [ $? -ne 0 ] ; then echo "test8: java Roadnetwork none -- the wrong error message" fi fi rm expectedDotErr expectedDotOut systemDotErr systemDotOut testinput # test9 java RoadNetwork testfile -- one intersection, defective subclass echo "intersection A 1 stoplight;" > testinput echo "Warning: intersection A 1.0 ; stoplight: interval expected skipped ;" > expectedDotErr echo "" >> expectedDotErr echo "Warning: intersection A 1.0 ; stoplight: interval expected" >> expectedDotErr echo "Warning: intersection A 1.0: semicolon missing" >> expectedDotErr touch expectedDotOut java RoadNetwork testinput > systemDotOut &> systemDotErr if [ $? -eq 0 ] ; then # program did System.exit( 0 ); echo "test9: java Roadnetwork -- terminated with System.exit( 0 )" else # program did System.exit( !=0 ); diff expectedDotOut systemDotOut if [ $? -ne 0 ] ; then echo "test9: java Roadnetwork none -- unexpected normal output" fi diff expectedDotErr systemDotErr if [ $? -ne 0 ] ; then echo "test9: java Roadnetwork none -- the wrong error message" fi fi rm expectedDotErr expectedDotOut systemDotErr systemDotOut testinput # test10 java RoadNetwork testfile -- one intersection, defective subclass echo "intersection A 1 stoplight -10;road A A 1;" > testinput echo "Warning: intersection A 1.0 ; stoplight -10.0: interval must be positive" > expectedDotErr touch expectedDotOut java RoadNetwork testinput > systemDotOut &> systemDotErr if [ $? -eq 0 ] ; then # program did System.exit( 0 ); echo "test10: java Roadnetwork -- terminated with System.exit( 0 )" else # program did System.exit( !=0 ); diff expectedDotOut systemDotOut if [ $? -ne 0 ] ; then echo "test10: java Roadnetwork none -- unexpected normal output" fi diff expectedDotErr systemDotErr if [ $? -ne 0 ] ; then echo "test10: java Roadnetwork none -- the wrong error message" fi fi rm expectedDotErr expectedDotOut systemDotErr systemDotOut testinput xxxxxxxxxx