/* Logic.java * Program to process description of a logic circuit * author Douglas W. Jones * version 2017-10-30 (MP4 solution) * Adapted from Logic.java Version 2017-10-11 (the MP3 solution), * * Class ScanSupport taken from RoadNetwork.java Version 2017-10-25 * Class Simulator taken from RoadNetwork.java Version 2017-10-25 * Class hierarchy for logic gates from the posted solution to HW 8 * * Bug notices in the code indicate unsolved problems */ import java.util.regex.Pattern; import java.util.LinkedList; import java.io.File; import java.io.FileNotFoundException; import java.util.Scanner; import java.util.PriorityQueue; /** Error reporting package * provides standard prefix and behavior for messages */ class Errors { // error messages are counted. private static int errorCount = 0; /** Allow public read-only access to the count of error messages * @return the count */ public static int count() { return errorCount; } /** Report nonfatal errors, output a message and return * @arg message the message to output */ public static void warn( String message ) { System.err.println( "Logic: " + message ); errorCount = errorCount + 1; } /** Report fatal errors, output a message and exit, never to return * @arg message the message to output */ public static void fatal( String message ) { warn( message ); System.exit( 1 ); } } /** Support methods for scanning * @see Errors */ class ScanSupport { // exception thrown to indicate failure public static class NotFound extends Exception {} // patterns needed for scanning private static final Pattern name = Pattern.compile( "[a-zA-Z0-9_]*" ); private static final Pattern intPattern = Pattern.compile( "-?[0-9][0-9]*|"); private static final Pattern floatPattern = Pattern.compile( "-?[0-9][0-9]*\\.?[0-9]*|\\.[0-9][0-9]*|"); private static final Pattern whitespace = Pattern.compile( "[ \t]*" ); // no newlines // interface for passing error messages public static interface Message { public String myString(); } /** Get next name without skipping to next line (unlike sc.Next()) * @param sc the scanner from which end of line is scanned * @param message the context part of the missing name error message * @return the name if there was one. * @throws NotFound if there wasn't one */ public static String nextName( Scanner sc, Message m ) throws NotFound { sc.skip( whitespace ); sc.skip( name ); String s = sc.match().group(); if ("".equals( s )) { Errors.warn( "name expected: " + m.myString() ); sc.nextLine(); throw new NotFound(); } return s; } /** Get next int without skipping to next line (unlike sc.nextInt()) * @param sc the scanner from which end of line is scanned * @param message the message to output if there was no int * @return the value if there was one * @throws NotFound if there wasn't one */ public static int nextInt( Scanner sc, Message m ) throws NotFound { sc.skip( whitespace ); sc.skip( intPattern ); String s = sc.match().group(); if ("".equals( s )) { Errors.warn( "Float expected: " + m.myString() ); sc.nextLine(); throw new NotFound(); } // now, s is guaranteed to hold a legal int return Integer.parseInt( s ); } /** Get next float without skipping to next line (unlike sc.nextFloat()) * @param sc the scanner from which end of line is scanned * @param message the message to output if there was no float * @return the value if there was one * @throws NotFound if there wasn't one */ public static float nextFloat( Scanner sc, Message m ) throws NotFound { sc.skip( whitespace ); sc.skip( floatPattern ); String s = sc.match().group(); if ("".equals( s )) { Errors.warn( "Float expected: " + m.myString() ); sc.nextLine(); throw new NotFound(); } // now, s is guaranteed to hold a legal float return Float.parseFloat( s ); } /** Advance to next line and complain if is junk at the line end * @see Errors * @param sc the scanner from which end of line is scanned * @param message gives a prefix to give context to error messages * This version supports comments starting with -- */ public static void lineEnd( Scanner sc, Message message ) { sc.skip( whitespace ); String lineEnd = sc.nextLine(); if ( (!lineEnd.equals( "" )) && (!lineEnd.startsWith( "--" )) ) { Errors.warn( message.myString() + " followed unexpected by '" + lineEnd + "'" ); } } } /** Framework for discrete event simulation */ class Simulator { /** interface used to allow lambda expressions passed to schedule method * This is a functional interface. * Typically, it will be used from lambda expressions passed to the * schedule method. */ public interface Action { /** trigger the action * @param time gives the time at which the action is triggered */ void trigger( float time ); } private static class Event { public float time; // time of the event public Action act; // the action to perform } private static PriorityQueue eventSet = new PriorityQueue ( (Event e1, Event e2) -> Float.compare( e1.time, e2.time ) ); /** schedule one new event * @param time when an event will occur * @param act the action that will be triggered at that time * Typically, this is called as follows: *
     *  Simulator.schedule( someTime, (float time)->aMethodCall( time ... ) );
     *  
*/ public static void schedule( float time, Action act ) { Event e = new Event(); e.time = time; e.act = act; eventSet.add( e ); } /** main loop that runs the simulation * This must be called after all initial events are scheduled. */ public static void run() { while (!eventSet.isEmpty()) { Event e = eventSet.remove(); e.act.trigger( e.time ); } } } /** Wires join Gates * @see Gate */ class Wire { // constructors may throw this when an error prevents construction public static class ConstructorFailure extends Exception {} // fields of a gate private final float delay; // measured in seconds private final Gate source; // where this wire comes from, never null private final int srcPin; // what pin number of source private final Gate destination; // where this wire goes, never null private final int dstPin; // what pin number of destination // note, wires don't understand pin numbers, only gates do. // note, by convention -1 is an illegal pin number. /** construct a new wire by scanning its description from the source file * @param sc the scanner from which the wire description is scanned * @see ScanSupport for the tools used to access the scanner * @throws ConstructorFailure when a new wire cannot be constructed */ public Wire( Scanner sc ) throws ConstructorFailure { // temporaries used during construction final String sourceName; final String srcPinName; final String dstName; final String dstPinName; // pick off the text fields of the source line try { sourceName = ScanSupport.nextName( sc, ()-> "wire ???" ); srcPinName = ScanSupport.nextName( sc, ()->"wire " + sourceName + " ???" ); dstName = ScanSupport.nextName( sc, ()->"wire " + " " + srcPinName + " ???" ); dstPinName = ScanSupport.nextName( sc, ()->"wire " + " " + srcPinName + " " + dstName + " ???" ); } catch (ScanSupport.NotFound e) { throw new ConstructorFailure(); } source = Logic.findGate( sourceName ); destination = Logic.findGate( dstName ); if (source == null) { Errors.warn( "No such source gate: wire " + sourceName + " " + srcPinName + " " + dstName + " " + dstPinName ); sc.nextLine(); throw new ConstructorFailure(); } if (destination == null) { Errors.warn( "No such destination gate: wire " + sourceName + " " + srcPinName + " " + dstName + " " + dstPinName ); sc.nextLine(); throw new ConstructorFailure(); } // take care of source and destination pins // Bug: This is a start, but in the long run, it might not be right srcPin = source.registerOutput( this, srcPinName ); dstPin = destination.registerInput( this, dstPinName ); // pick off the numeric field of the source line try { delay = ScanSupport.nextFloat( sc, ()->"wire " + sourceName + " " + srcPinName + " " + dstName + " " + dstPinName + " ???" ); } catch (ScanSupport.NotFound e) { throw new ConstructorFailure(); } if (delay < 0.0F) Errors.warn( "Negative delay: " + this.toString() ); ScanSupport.lineEnd( sc, ()->this.toString() ); } /** get textual description of a wire in a form like that used for input * @return the textual form */ public String toString() { return "wire " + source.name + " " + source.outPinName( srcPin ) + " " + destination.name + " " + destination.inPinName( dstPin ) + " " + delay; } // Simulation methods /** Simulate an input change on this wire * @param time tells when this wire's input changes * @param v gives the new value on this wire * schedules an output change event after the wire's delay. * @see outputChangeEvent */ public void inputChangeEvent( float time, boolean v ) { Simulator.schedule( time + delay, (float t) -> outputChangeEvent( t, v ) ); } /** Simulate an output change on this wire * @param time tells when this wire's input changes * @param v gives the new value on this wire * Passes the new value to the input of the gate to which this wire goes. * @see Gate.inputChangeEvent */ private void outputChangeEvent( float time, boolean v ) { destination.inputChangeEvent( time, dstPin, v ); } } // class Wire /** Gates process inputs from Wires and deliver outputs to Wires * @see Wire * @see AndGate * @see OrGate * @see NotGate * @see ConstGate */ abstract class Gate { // constructors may throw this when an error prevents construction public static class ConstructorFailure extends Exception {} // fields of a gate public final String name; // textual name of gate, never null! protected final float delay; // the delay of this gate, in seconds // information about gate connections and logic values is all in subclasses /** Constructor used only from within subclasses of class Gate * @param name used to initialize the final field * @param delay used to initialize the final field */ protected Gate( String name, float delay ) { this.name = name; this.delay = delay; } /** The public use this factory to construct gates * @param sc the scanner from which the gate description is read * @return the newly constructed gate */ public static Gate factory( Scanner sc ) throws ConstructorFailure { // tempraries used while constructing a gate final String name; final String kind; final float delay; final Gate newGate; // scan basic fields of input line try { name = ScanSupport.nextName( sc, ()->"gate ???" ); kind = ScanSupport.nextName( sc, ()->"gate " + name + " ???" ); delay = ScanSupport.nextFloat( sc, ()->"gate " + name + " " + kind + " ???" ); } catch (ScanSupport.NotFound e) { throw new ConstructorFailure(); } // check the fields if (Logic.findGate( name ) != null) { Errors.warn( "Redefinition: gate " + name + " " + kind ); sc.nextLine(); throw new ConstructorFailure(); } if (delay < 0.0F) Errors.warn( "Negative delay: " + "gate " + name + " " + kind + " " + delay // don't throw a failure here, we can build a gate with this error ); // now construct the right kind of gate if ("and".equals( kind )) { newGate = new AndGate( name, delay ); } else if ("or".equals( kind )) { newGate = new OrGate( name, delay ); } else if ("not".equals( kind )) { newGate = new NotGate( name, delay ); } else if ("const".equals( kind )) { newGate = new ConstGate( name, delay ); } else { Errors.warn( "Unknown gate kind: gate " + name + " " + kind ); sc.nextLine(); throw new ConstructorFailure(); } ScanSupport.lineEnd( sc, ()->newGate.toString() ); return newGate; } /** tell the gate that one of its input pins is in use * @param w the wire that is connected * @param pinName * @return corresponding pin number */ public abstract int registerInput( Wire w, String pinName ); /** tell the gate that one of its output pins is in use * @param w the wire that is connected * @param pinName * @return corresponding pin number */ public abstract int registerOutput( Wire w, String pinName ); /** get the name of the input pin, given its number * @param pinNumber * @return pinName */ public abstract String inPinName( int pinNumber ); /** get the name of the output pin, given its number * @param pinNumber * @return pinName */ public abstract String outPinName( int pinNumber ); /** check the sanity of this gate's connections */ public abstract void checkSanity(); // Simulation methods /** simulate the change of one of this gate's inputs * @param time the time when the input changes * @param dstPin the pin that changes * @param v the new logic value */ public abstract void inputChangeEvent( float time, int dstPin, boolean v ); } // abstract class Gate /** Gathers all of the properties common to single-output gates * Specifically, all LogicGates drive a single list of output wires * with a single output value when an OutputChangeEvent occurs. * @see AndGate * @see OrGate * @see NotGate */ abstract class LogicGate extends Gate { // set of all wires out of this gate private LinkedList outgoing = new LinkedList (); // this gate's output value protected boolean value = false; /** The constructor used only from subclasses of LogicGate * @param name used to initialize the final field * @param delay used to initialize the final field */ public LogicGate( String name, float delay ) { super( name, delay ); } /** tell the gate that one of its output pins is in use * @param w the wire that is connected * @param pinName * @return corresponding pin number */ public int registerOutput( Wire w, String pinName ) { if ("out".equals( pinName )) { outgoing.add( w ); return 0; } else { Errors.warn( "Illegal output pin: " + name + " " + pinName ); return -1; } } /** get the name of the output pin, given its number * @param pinNumber * @return pinName */ public String outPinName( int pinNumber ) { if (pinNumber == 0) return "out"; return "???"; } // Simulation methods /** Simulate an output change on this wire * @param time tells when this wire's input changes * Passes the new value to the input of the gate to which this wire goes. * Uses the this.value field to determine the new output value. * Output change events are scheduled (directly or indirectly) by the * input change event of the actual gate object. * @see Gate.inputChangeEvent */ protected void outputChangeEvent( float time ) { System.out.println( "At " + time + " " + toString() + " out " + " changes to " + value ); for (Wire w: outgoing) { w.inputChangeEvent( time, value ); } } } // abstract class LogicGate /** Handles the properties common to logic gates with two inputs * Specifically, all two-input gates have two input wires, in1 an in2. * @see AndGate * @see OrGate * @see LogicGate */ abstract class TwoInputGate extends LogicGate { // usage records for inputs protected boolean in1used = false; protected boolean in2used = false; // Boolean values of inputs protected boolean in1 = false; protected boolean in2 = false; /** The constructor used only from subclasses of TwoInputGate * @param name used to initialize the final field * @param delay used to initialize the final field */ protected TwoInputGate( String name, float delay ) { super( name, delay ); } /** tell the gate that one of its input pins is in use * @param w the wire that is connected * @param pinName * @return corresponding pin number */ public int registerInput( Wire w, String pinName ) { if ("in1".equals( pinName )) { if (in1used) Errors.warn( "Multiple uses of input pin: " + name + " in1" ); in1used = true; return 1; } else if ("in2".equals( pinName )) { if (in2used) Errors.warn( "Multiple uses of input pin: " + name + " in2" ); in2used = true; return 2; } else { Errors.warn( "Illegal input pin: " + name + " " + pinName ); return -1; } } /** get the name of the input pin, given its number * @param pinNumber * @return pinName */ public String inPinName( int pinNumber ) { if (pinNumber == 1) return "in1"; if (pinNumber == 2) return "in2"; return "???"; } /** check the sanity of this gate's connections */ public void checkSanity() { if (!in1used) Errors.warn( "Unused input pin: " + name + " in1" ); if (!in2used) Errors.warn( "Unused input pin: " + name + " in2" ); } // Simulation methods /** update the output value of a gate based on its input values * This is called from inputChangeEvent to delegate the response of the * logic gate to the input change to the actual gate instead of this * abstract class. * @param time the value is updated */ abstract void updateValue( float time ); /** simulate the change of one of this gate's inputs * @param time the time when the input changes * @param dstPin the pin that changes * @param v the new logic value */ public void inputChangeEvent( float time, int dstPin, boolean v ) { if (dstPin == 1) { in1 = v; } else if (dstPin == 2) { in2 = v; } updateValue( time ); } } // abstract class TwoInputGate /** Handles the properties specific to and gates. * @see TwoInputGate * @see LogicGate */ class AndGate extends TwoInputGate { /** The constructor used only from within class Gate * @param name used to initialize the final field * @param delay used to initialize the final field */ public AndGate( String name, float delay ) { super( name, delay ); } /** reconstruct the textual description of this gate * @return the textual description */ public String toString() { return "gate " + name + " and " + delay; } // Simulation methods /** update the output value of a gate based on its input values * @param time the value is updated */ void updateValue( float time ) { boolean newVal = in1 & in2; if (newVal != value) { value = newVal; Simulator.schedule( time + delay, (float t) -> outputChangeEvent( t ) ); } } } // class AndGate /** Handles the properties specific to or gates. * @see TwoInputGate * @see LogicGate */ class OrGate extends TwoInputGate { /** The constructor used only from within class Gate * @param name used to initialize the final field * @param delay used to initialize the final field */ public OrGate( String name, float delay ) { super( name, delay ); } /** reconstruct the textual description of this gate * @return the textual description */ public String toString() { return "gate " + name + " or " + delay; } // Simulation methods /** update the output value of a gate based on its input values * @param time the value is updated */ void updateValue( float time ) { boolean newVal = in1 | in2; if (newVal != value) { value = newVal; Simulator.schedule( time + delay, (float t) -> outputChangeEvent( t ) ); } } } // class OrGate /** Handles the properties specific to not gates. * @see LogicGate */ class NotGate extends LogicGate { // usage records for inputs private boolean inUsed = false; /** The constructor used only from within class Gate * @param name used to initialize the final field * @param delay used to initialize the final field */ public NotGate( String name, float delay ) { super( name, delay ); } /** tell the gate that one of its input pins is in use * @param w the wire that is connected * @param pinName * @return corresponding pin number */ public int registerInput( Wire w, String pinName ) { if ("in".equals( pinName )) { if (inUsed) Errors.warn( "Multiple uses of input pin: " + name + " in" ); inUsed = true; return 0; } else { Errors.warn( "Illegal input pin: " + name + " " + pinName ); return -1; } } /** get the name of the input pin, given its number * @param pinNumber * @return pinName */ public String inPinName( int pinNumber ) { if (pinNumber == 0) return "in"; return "???"; } /** check the sanity of this gate's connections */ public void checkSanity() { if (!inUsed) Errors.warn( "Unused input pin: " + name + " in" ); // this is a good time to launch the simulation value = true; Simulator.schedule( delay, (float t) -> outputChangeEvent( t ) ); } /** reconstruct the textual description of this gate * @return the textual description */ public String toString() { return "gate " + name + " not " + delay; } // Simulation methods /** simulate the change of one of this gate's inputs * @param time the time when the input changes * @param dstPin the pin that changes * @param v the new logic value */ public void inputChangeEvent( float time, int dstPin, boolean v ) { value = !v; Simulator.schedule( time + delay, (float t) -> outputChangeEvent( t ) ); } } // class NotGate /** Handles the properties specific to const gates. */ class ConstGate extends Gate { // set of all wires out of this gate private LinkedList outgoingTrue = new LinkedList (); private LinkedList outgoingFalse = new LinkedList (); /** The constructor used only from within class Gate * @param name used to initialize the final field * @param delay used to initialize the final field */ public ConstGate( String name, float delay ) { super( name, delay ); } /** tell the gate that one of its input pins is in use * @param w the wire that is connected * @param pinName * @return corresponding pin number */ public int registerInput( Wire w, String pinName ) { Errors.warn( "Illegal input pin: " + name + " " + pinName ); return -1; } /** tell the gate that one of its output pins is in use * @param w the wire that is connected * @param pinName * @return corresponding pin number */ public int registerOutput( Wire w, String pinName ) { if ("true".equals( pinName )) { outgoingTrue.add( w ); return 1; } else if ("false".equals( pinName )) { outgoingFalse.add( w ); return 0; } else { Errors.warn( "Illegal output pin: " + name + " " + pinName ); return -1; } } /** get the name of the input pin, given its number * @param pinNumber * @return pinName */ public String inPinName( int pinNumber ) { return "???"; } /** get the name of the output pin, given its number * @param pinNumber * @return pinName */ public String outPinName( int pinNumber ) { if (pinNumber == 0) return "false"; if (pinNumber == 1) return "true"; return "???"; } /** check the sanity of this gate's connections */ public void checkSanity() { // no sanity check; there are no input pins to check // this is a good time to launch the simulation Simulator.schedule( delay, (float t) -> outputChangeEvent( t ) ); } /** reconstruct the textual description of this gate * @return the textual description */ public String toString() { return "gate " + name + " const " + delay; } // Simulation methods /** simulate the change of one of this gate's inputs * @param time the time when the input changes * @param dstPin the pin that changes * @param v the new logic value */ public void inputChangeEvent( float time, int dstPin, boolean v ) { Errors.fatal( "Input should never change: " + toString() ); } private void outputChangeEvent( float time ) { System.out.println( "At " + time + " " + toString() + " true " + " changes to true" ); for (Wire w: outgoingTrue) { w.inputChangeEvent( time, true ); } } } // class ConstGate /** The main class, orchestrates the building and simulation of a logic circuit * Logic circuits consist of a collection of gates connected by wires. * Logic circuits are built using tools in class ScanSupport, with * error reporting using class Errors. * The actual simulation is done by Simulator.run() * @see Simulator * @see Wire * @see Gate * @see ScanSupport * @see Errors */ public class Logic { // the sets of all wires and all gates private static LinkedList wires = new LinkedList (); private static LinkedList gates = new LinkedList (); /** Find a gate by textual name in the set gates * @param s name of a gate * @return the gate named s or null if none */ public static Gate findGate( String s ) { // quick and dirty implementation for (Gate i: gates) { if (i.name.equals( s )) { return i; } } return null; } /** Initialize this logic circuit by scanning its description */ private static void readCircuit( Scanner sc ) { while (sc.hasNext()) { String command = sc.next(); if ("gate".equals( command )) { try { gates.add( Gate.factory( sc ) ); } catch (Gate.ConstructorFailure e) { // do nothing, the constructor already reported the error } } else if ("wire".equals( command )) { try { wires.add( new Wire( sc ) ); } catch (Wire.ConstructorFailure e) { // do nothing, the constructor already reported the error } } else if ("--".equals( command )) { sc.nextLine(); } else { Errors.warn( "unknown command: " + command ); sc.nextLine(); } } } /** Check that a circuit is properly constructed */ private static void sanityCheck() { for (Gate i: gates) i.checkSanity(); // Bug: Are there any sensible sanity checks on wires? } /** Print out the wire network to system.out */ private static void printCircuit() { for (Gate i: gates) { System.out.println( i.toString() ); } for (Wire r: wires) { System.out.println( r.toString() ); } } /** Main program */ public static void main( String[] args ) { if (args.length < 1) { Errors.fatal( "Missing file name argument" ); } else if (args.length > 1) { Errors.fatal( "Too many arguments" ); } else try { readCircuit( new Scanner( new File( args[0] ) ) ); sanityCheck(); if (Errors.count() == 0) Simulator.run(); // note that writeCircuit is no longer called anywhere } catch (FileNotFoundException e) { Errors.fatal( "Can't open the file" ); } } }