Logical Circuit

[maxbummber]

I was proposed a project that sounds like this.

Consider a set of logical gates like AND, OR, XOR or NOT. Allow for building any logical circuit by connecting such gates.

Provide input (0/1) to a number of gates and collect the results at the output of some of the gates.

Be able to read the description of the circuit from a file.

Has anyone done anything of this kind? What would you do, how would you start/shape this problem? I am looking for any help as much as possible, open to hints and solutions, anything is helpful. Trying to pass my subject so it is of great importance to me.

Thanks.

[maxbummber]

I have to build some classes/interfaces allowing to model such circuits.
After that, you have to simulate the flow of the input signals to the end nodes and eventually to collect the results on some output connectors.
It is not about writing a program to evaluate logical propositions like p&q|r&!p or to write truth tables. Rather you have some signals flowing through connectors and processed at the level of each logical gate.

[bguild]

That sounds like a fun project. I would have a GateBuilder class and a Wire class.

The Wire class is most important because it would hold everything together and everything depends upon it. It would have a state which would be true or false (or ON and OFF if you prefer), and there would be a setter and a getter for that state. It would also have a list of GateListeners that would be notified whenever the state changes because of a call to the setter. The setter might also throw an exception if it is called while GateListeners are being notified because that would mean there is a cycle in your gates.

Then GateFactory would look something like this:

public abstract class GateBuilder {
    public abstract void buildGate(String type, List<Wire> input, List<Wire> output);
}

Each time buildGate is called it constructs some gate object that is a GateListener that listens to the input wires and sets the output wires according to the values of the input wires. GateBuilder never returns any of the gate objects that it creates, but they aren't needed as long as you have the wires which you can set to provide input to the circuit and read to get the output from the circuit. It throws an exception if it gets a type that's not one of the gates it recognizes, like AND, OR, NOT, etc., or if the gate it being given too many or two few input or output wires.

Then you can write a readGates(GateBuilder builder, Reader in) method that reads gates from a file in a format something like:

[IN] A, B
A, B [AND] AB
A, B [OR] A+B
AB [NOT] nAB
A+B, nAB [AND] out
out [OUT]

You have a comma-separated list of input wires before the gate name, then the gate name in [], then a comma-separated list of output wires after the gate name. You can use a java.util.Map<String,Wire> to keep track of which wires go with which names. I'm assuming that input to the circuit would be provided from the user using a gate called IN and output would be displayed by a gate called OUT, but that could be handled in other ways.

Extending the project slightly you could add a defineGate(String name) method to GateBuilder and have it take all the previously built gates and wires and destroy them, and at the same time create a new gate type with the given name which acts like a copy of all those previous gates and connects its input to the output of IN and connects its output to the input of OUT. Then if you add a special line to your file format that triggers a defineGate call, you can have an input file that not only describes a circuit of logic gates, but can also define its own logic gates and create much more complicated circuits.

[bguild]

On second thought, I would rename GateListener to WireListener since it is really listening to wires, and I would rename GateBuilder to CircuitBuilder since it is really building circuits. I would also have an interface like this:

public interface LogicCircuit {
    public List<Wire> inputWires();
    public List<Wire> outputWires();
    public LogicCircuit copyCircuit(List<Wire> input, List<Wire> output);
}

The copyCircuit method is just for being able to reuse the same circuit in more than one place, if you want that. Then you could define CircuitBuilder something like:

public abstract class CircuitBuilder {
    public abstract void addGate(String typeName, List<Wire> input, List<Wire> output);
    public abstract void clearGates();
    public abstract LogicCircuit getCircuit();
    public abstract void defineGateType(String typeName, LogicCircuit implementation);
}

The defineGateType method allows you to define new gate types or redefine old ones based on a given implementation circuit and clearGates allows you to remove all the gates you have previously added to the current circuit.

While reading in the input file you should probably keep count of how many times a wire is used as a gate output and report an error if any wire is used more than once.

[maxbummber]

Thank you so far, I would have another question. If you were to add them to packages, what would you structure them into?

I was also given some help which looks like this. Is this in any way helpful with what you've been suggesting me?

Created the class called Jack which attached to ports on gates (a port is just an int which is the index in the inputs/outputs array), and then "wires" are just a bijectional map from Jacks to Jacks. Then the Gates notify their listeners when their output changed, and the circuit would register itself as a listener every time a gate was added to the circuit.

public abstract class Gate {   
    protected Jack[] inputs;
    protected Jack[] outputs;

    public Gate(int numInputs, int numOutputs) {
        inputs = new Jack[numInputs];
        outputs = new Jack[numOutputs];
        // Now instantiate a Jack for each cell in both arrays
    }

    // This is now protected, because I had it called whenever an input changed automatically
    protected abstract void evaluate();
}


public class AndGate extends Gate {

    public AndGate() {
        super(2, 1);
    }

    public AndGate(numInputs) {
        super(numInputs, 1);
    }

    @override
    public void evaluate() {
        // Loop through inputs as you would expect
    }
}


public class Circuit implements GateListener {
    private final Set<Gate> gates = new HashSet<..>();
    // A BiMap is like a map, but both fields ("keys" and "values" are unique).
    // It is not in the Java util, you can implement it using two normal Maps, or I used
    // Google's Guava library
    private final BiMap<Jack, Jack> wires = HashBiMap.create(); 

    public void addGate(...) {

    }

    // removeGate()


    public void addWire(Jack outputJack, Jack inputJack) {
        // Check the Jacks are valid, unused, etc.

    wires.put(outputJack, inputJack);
    }

    @Override
    public void gateOutputChanged(Gate gate) {
        // This is where you do the propagation for signals
        // What you put in here depends on how complicated the circuits
        // you build are allowed to be
        // If you assume the circuit is acyclic (so no Flip-Flops, for instance)
        // then you can do propagation in this thread. Otherwise you probably
        // want to spawn a new thread to propagate signals, and include a 
        // 'propagation delay'

        // Assuming acyclic circuits, you could just loop through the gates
        // output jacks, check for wires from them, and set the corresponding
        // input jack
    }
}

[bguild]

The first thing I notice is that the BiMap is a bit odd. Why go to the trouble of getting one from a nonstandard library or making one yourself when all you really want is an ordinary java.util.Map? When you receive a getOutputChanged notification the only propagation that you'd be doing would be from changed output jacks to whatever input jacks they connect to.

But of course an output jack can connect to more than one input jack. That makes me think that your BiMap should really be a Map<Jack,Set<Jack>>. It's not clear how connecting one output to multiple inputs is intended to work otherwise.

It's also not clear who will be calling gateOutputChanged. I see no method for adding listeners to Gate. Another thing missing from Gate is whatever calls evaluate. At least we know that it is called from somewhere in Gate because it is protected, but that just emphasizes that something important is missing. Seeing an interface for Jack would probably explain everything.

For my previous ideas I had forgotten that logic gates can sometimes have cycles. If a cycle were to cause a conflicting state where a wire should be both on and off, then that could lead to a stack overflow of repeated WireListener notifications. That can be resolved by detecting the conflict and throwing an exception early, but then you don't get any results from the circuit. You could also allow a slight delay between setting a new value to a wire and actually changing the value of the wire, but that doesn't require multithreading the way the comment in your code suggests.

I would create a class something like this:

public final class PropagationHeartBeat {
    private final List<Wire> queue = new ArrayList<Wire>();
    public void add(Wire wire) { queue.add(wire); }
    public void propagate(){
        // Copy the queue so we can safely iterate while the original queue is modified
        final List<Wire> wires = new ArrayList<Wire>(queue);
        // Calling propagate on the wires will refill the queue so empty it now
        queue.clear();
        for(Wire w: wires) w.propagate();
    }
    public boolean isDone() {
        // When the queue it empty that means no wires want to change
        // so it is time to read the outputs of the circuit.
        return queue.isEmpty();
    }
    public void propagateUntilDone(int maxCycles) {
        while(!isDone() && maxCycles > 0) {
            propagate();
            maxCycles--;
        }
    }
}

Then I would implement a Wire class like this:

public final class Wire {
    private final List<WireListener> listeners = new ArrayList<WireListener>();
    private final PropagationHeartBeat beater;
    private boolean currentValue;
    private boolean nextValue;
    private boolean isWaiting; // Keep track of whether we are in the beater queue
    public Wire(boolean value, PropagationHeartBeat beater) {
        currentValue = value;
        nextValue = value;
        // Notify all listeners of a change when each wire gets its first value
        // There might be a better way to get things started, but this should work
        beater.add(this);
        isWaiting = true;
    }
    public boolean get() { return currentValue; }
    public void set(boolean value) {
        if(nextValue != value) {
            nextValue = value;
            if(!isWaiting) beater.add(this);
            isWaiting = true;
        }
    }
    public void propagate() {
        isWaiting = false; // No longer in the propagate queue
        if(nextValue != currentValue) {
            currentValue = nextValue;
            // Listeners may put us back in the propagate queue by calling set
            for(WireListener l: listeners) l.wireChanged(this);
        }
    }
}

All of this is just a rough idea. Consider it pseudocode and implement it as you like with careful testing. The point is that all in the same thread you can setup your wires and gates, then call propagateUntilDone, and when that returns your output wires should be ready for reading.

Because a call to set doesn't lead to a call to wireChanged on the same stack, there is no danger of a stack overflow and the propagation of values through the circuit proceeds in an orderly manner, step-by-step. I think it is easier this way, going wire-by-wire rather than going gate-by-gate, and you would still end up with all of the outputs of each gate being set before any other gate gets to read any of those outputs.

My preference is against having a Gate class at all. It really doesn't seem to add anything useful. All I need are AndGate, OrGate, NotGate, etc., and each of them is a WireListener which is all it needs to react when its inputs change.

Regarding packages, I would put the Wire, the PropagationHeartBeat, and the CircuitBuilder and all of that fundamental stuff in one package. I would probably also put the readGates method in that package somewhere, since they all seem natural to use together. That would be package A, and then I would create a package B that would contain my implementation of CircuitBuilder, including all of my gate classes. That works out nicely because package B would depend upon package A, but package A could be reused somewhere else without package B and with an entirely different set of gate implementations. Please choose better names for your packages.

[maxbummber]

When it comes to gate classes, what methods should I to use over there? I also created a class called Input where I added the readGates(GateBuilder builder, Reader in), is this a good idea? And as far as the output is concerned, can I just create a class Output that has a method that redirects the result into a file?

The interface LogicCircuit shouldn't it be implemented by the classes Wire and CircuitBuilder or only by the Input, Ouput and CircuitBuilder ? One more thing, when you said you'd add CircuitBuilder to package A you were refering to the interface right?

Thanks a lot.

[bguild]

Every method needs to be a member of some class. Whether Input is a good class for readGates depends on the nature of Input.

Writing a circuit to a file isn't nearly as easy as reading a circuit from a file. When reading from a file it is natural for wires to have names that are meaningful to the person who typed the file. When writing to a file, you are forced to use a file format that doesn't rely upon meaningful names for wires, since it is very difficult to generate meaningful names. You may want to give up on the file being human-readable and just use a java.io.DataOutputStream and a java.util.Map<Wire,Integer> to give each wire a number.

If you want to get ambitious you might try creating a file format that represents a circuit using some sort of ASCII art for the connections between gates instead of naming wires. It would still be much easier to read in circuits than to write them out, but at least algorithms exist for drawing planar graphs.

You are correct that when I said that Wire, PropagationHeartBeat, and CircuitBuilder should all be in the same package I meant only the actual CircuitBuilder interface, not any of the implementations of CircuitBuilder. My favorite way to choose which classes go in which packages is to imagine someone who only wants part of my project, so I design packages which can be removed from my project and used independently as much as possible.

Naturally packages will use each other, and if package B needs package A that is unfortunate but inevitable. Even so, we can make effort to distribute classes between packages so that each package uses as few other packages as possible, so if someone wants package B they will also need package A, but no other packages. Most of all, if package B needs package A, make sure that package A doesn't need package B, because otherwise you will always need both if you need either one, and if you make changes to one it will probably cause changes to both. Two packages that use each other are practically one package, and the same is true for any cycle, such as if package A uses package B, and B uses C, and C uses A. All of the classes from A, B, and C would be just as well lumped together in one large package.

Another rule that I like is that when I have two packages like mypackage and mypackage.subpackage, then mypackage uses mypackage.subpackage and mypackage.subpackage never uses mypackage. It seems natural that way because if someone were to take mypackage out of my project, mypackage.subpackage would naturally come with it because it is in the same directory as the rest of mypackage. And of course mypackage.subpackage doesn't use mypackage because that would be a cycle. On the other hand, the Java standard libraries don't follow this rule, so use your own judgement.

So I noticed that Wire, PropagationHeartBeat, CircuitBuilder, and the readGates method all work together closely, but they never use any of the classes that implement gates or the class that implements CircuitBuilder, so it seems a natural place to break the project into two packages. Whenever you have a certain set of classes that will never use another set of classes it's worth considering putting those two sets into separate packages somehow.

[maxbummber]

Yes, I understand what you're saying about the inpout and output . As far as the gates methods are concerned, what could I specify in there? the AndGate,OrGate classes etc. As well as that, regarding the interface, shouldn't I connect the other classes to it or only input and output and copyCircuit? For example say.. CircuitBuilder implements LogicCircuit, items like that.

public interface LogicCircuit {
    public List<Wire> inputWires();
    public List<Wire> outputWires();
    public LogicCircuit copyCircuit(List<Wire> input, List<Wire> output);
}