Alas! The evil Space Demon Yrrab has begun his assault on Earth. In his cold, calculating mind, he can imagine no greater threat to his war machine than humanity's computers. All of our military equipment is controlled by computers. All of the coordination between military units depends on computers. Likewise, the social disruption caused by the failure of the Internet, banking computers, and all the other computers we rely upon in our daily lives will make humanity that much more vulnerable to the Yrrab's attack.
Knowing this, the Space Demons have labored long in their filthy underground laboratories to develop the Silicon Disruption Array, an astounding feat of military applied science. One blast of the SDA is sufficient to fuse all the computers on Earth into useless chunks of inert silicon.
What was that? Oh, horror of horrors! Yrrab has used the SDA before we could stop him. The Earth is doomed! Except... somehow you are reading this webpage. It seems that nuclear engineers working at Purdue University have erected a short distance force field capable of blocking its effects. This means that you, hearty CS190M student, are one of the few people on Earth with a functioning computer. It is your duty to help us rebuild Earth's computational powers as soon as possible.
In order to get Earth's computers back in production, we need a system to test circuits made up of logic gates, and that's the goal of this project. This project is made up of two major parts. In the first part, you have to write 11 classes, each of which can be a component in a logic circuit. These components are:
ComponentTrueFalseInputUnaryOperatorNotOutputBinaryOperatorAndOrXorAs you can see, these components form a class hierarchy intended to help you reuse code through inheritance. We'll give more information about how you should implement these classes in the next section.
The second part of this project is a program which will read in some information from the keyboard about which circuit to simulate and then actually simulate the circuit to see what its output is. This program will create an array of logic circuit components, connect them together, and then query any Output objects to get their output. Again, we will give more details about how this is done in the next section.
Here is a UML class diagram showing the relationship that the classes in your program should have.
Below is a detailed explanation of each component. Creating some of these classes requires a working knowledge of logical operations. If you need a refresher, here are the Wikipedia pages for the operations NOT, AND, OR, and XOR.
Each component in the system will be represented by an object which is a subclass of the Component class described below. However, each of these components also has a value associated with it. These values are either TRUE, FALSE, or UNKNOWN. An enum is a class designed just to hold constant values of this kind. In this project, these three values are kept in an enum called Value.
We have provided the source code for the Value enumerated constant in a file called Value.java to help you. To download it, click here.
The base class for all other circuit components is the Component class. Each Component class contains a private member name of type String, a constructor, an accessor to allow the outside world to read the name, and a toString() method. Component is an abstract class, meaning that it only serves as a template for other classes. It is impossible to create an object of type Component. The Component class contains an abstract method getValue() that returns a Value object giving the current value of the Component.
We provide the source code for the Component class in a file called Component.java to help you. To download it, click here.
The True class is a subclass of Component that returns the TRUE value whenever its getValue() method is invoked. An appropriate constructor should set its name to "TRUE".
The False class is a subclass of Component that returns the FALSE value whenever its getValue() method is invoked. An appropriate constructor should set its name to "FALSE".
The Input class is a subclass of Component that has a private member of type Value and a mutator method setValue() to change the value. By using the setValue() method, objects of the Input class can be set to particular input values.
The UnaryOperator class is a subclass of Input that has a private member of type Component which is the input to the unary operator. This class has accessor and mutator methods for this member.
The Not class is a subclass of UnaryOperator. When its getValue() method is invoked, it returns the value which is the logical negation of the value it gets from its input Component (or UNKNOWN if the value is UNKNOWN). An appropriate constructor should set its name to "NOT".
The Output class is a subclass of UnaryOperator. When its getValue() method is invoked, it returns the value it gets from its input Component without changing it.
The BinaryOperator class is a subclass of Component that has private members operand1 and operand2, both of type Component. This class has an accessor and a mutator methods for both of its members.
The And class is a subclass of BinaryOperator. When its getValue() method is invoked, it returns the value which is the result of a logical AND between the values it gets from its members operand1 and operand2 (or UNKNOWN if either value is UNKNOWN). An appropriate constructor should set its name to "AND".
The Or class is a subclass of BinaryOperator. When its getValue() method is invoked, it returns the value which is the result of a logical OR between the values it gets from its members operand1 and operand2 (or UNKNOWN if either value is UNKNOWN). An appropriate constructor should set its name to "OR".
The Xor class is a subclass of BinaryOperator. When its getValue() method is invoked, it returns the value which is the result of a logical XOR between the values it gets from its members operand1 and operand2 (or UNKNOWN if either value is UNKNOWN). An appropriate constructor should set its name to "XOR".
The driver program CircuitBuilder should read from stdin the specification for a logic circuit (which does not contain loops), build the circuit from its components, and then print its outputs to stdout.
To do this, you will need to read a description of a circuit in a particular way. This input has two parts: the components and the connections.
The first information you will be given about your components is the number of components to be entered, just a simple int. Using this number, you'll be able to make an array big enough to hold the components. Since we haven't covered arrays in depth, the code to do so might look like this:
Component[] array = new Component[number];
Once you have created the array to hold the components, you need to populate it with the right components. As you read the input, the Strings "AND", "OR", "XOR", "NOT", "TRUE", and "FALSE" correspond to logic gates of the appropriate kinds that should be created at the next open spot in the array.
Input and Output objects are a little more complex. We want to number Output objects, and so their format will be:
OUTPUT integer
where integer is some unique integer. We want to both number Input objects and give them a value, and so their format will be:
INPUT integer value
where integer is some unique integer and value is TRUE, FALSE, or UNKNOWN.
Once we have created the components and stored them in the array, we need to connect various gates together. The next part of the input will consist of lists of integers. The first integer given will be the index of an object in the array that is a binary operator or a unary operator. If the object is a unary operator, a single integer will follow, giving the component the unary operator is applied to. If the object is a binary operator, two integers will follow, giving the two components that the binary operator is connecting together.
For example, in the following line:
4 3 2
The object at index 4, presumably a binary operator of some kind, is being connected such that the objects at indexes 3 and 2 are its inputs.
Now that you know the rules for input, let's look at an example:
7 INPUT 1 TRUE INPUT 2 FALSE INPUT 3 TRUE AND XOR NOT OUTPUT 1 3 0 1 4 3 2 5 4 6 5
The first integer tells the program that 7 gates will be created. Then, the next 7 lines give the information needed to fill a 7-element array with 3 Input objects, an And object, an Xor object, a Not object, and an Output object.
The next line shows that the AND gate (index 3) is connected to the first and second inputs (indexes 0 and 1). The line after that shows that the XOR gate (index 4) is connected to the output of the AND gate (index 3) and the third input (index 2). The following line shows that the NOT gate (index 5) is connected to the output of the XOR gate (index 4). Finally, the last line shows that the only output (index 6) is connected to the output of the XOR gate (index 5).
You will want to use the Scanner method hasNextInt() to see if you have any more connection input to read.
Once your code has created all the components and connected them together, you need to find the output. This step is much easier than it seems. All you have to do is search through the array of components, and, every time you find an Output object, you call its toString() method and print the answer.
The Output object will call its getValue() method which will in turn call the getValue() method of its input gate, which will call the getValue() method of its input gates, and so on. Provided that you've written all the getValue() methods correctly in all the classes, the answer will pop out.
For the example input given above, the output should be:
OUTPUT 1: FALSE
For this program, you should test a number of different circuits. Although you only know how to read input from the keyboard, this program is not really designed for manual entry. So, to work with the design of the program and keep your hands from getting sore, you should use something called input redirection. Essentially, you can take any file and make it appear to another program that it is being entered by hand. To do this, you use the < operator as follows:
java CircuitBuilder < input.txtUsing this syntax, whatever data is in input.txt will be sent to the program CircuitBuilder as if it were being entered by hand.
Because you have an array of type Component which really holds objects that are subclasses of Component, it will be useful to see, at runtime, what the real type of an object is. To do so, there are two techniques in Java, the instanceof operator and the getClass() method.
To use the instanceof operator, you can test an object against a particular class anywhere you would use a boolean condition. For example, the code:
if( array[i] instanceof BinaryOperator ) { . . . }
This if-statement is true whenever array[i] is of type BinaryOperator or is one of its subclasses.
If you want to be a little more specific about an object being a certain type and not just one of its subclasses, you can use the getClass() method like so:
if( array[i].getClass() == Output.class ) {
.
.
.
}
Using this method, you can compare the class of the object to the static member of the class you want to check against.
You have to create a lot of classes for this project, but you shouldn't write much code. Each class should only be 10 or 15 lines, and even the CircuitBuilder driver code is not long. One major point of using inheritance is increase code reuse. If you find yourself writing long code, reconsider your strategy.
This project takes thought and time. Make sure you start early. Contact your TA's if you have any problems. They are there to help you. If your needs are less urgent, the newsgroup is a great place to exchange ideas. Remember to consult your text. Google is a marvelous resource as well. Plenty of office hours are available and are listed on the main course page.
When you have tested your code and are satisfied with the results, you will need to turn in the project directory which includes all 13 Java source files. Make sure you run and test your code from the command line. DrJava does not easily support the input redirection discussed above.
To turn in your project, navigate to the directory containing your source files. Then type the following command:
turnin -v -c cs190m -p project1 *.java
You can submit your code as many times as you want. Submit early and often.
You must write 10 original classes containing one of the circuit components. Each class is worth 5 points if correctly written.
You can earn up to 10 points for correctly processing input.
Taking the input and correctly constructing the circuit is worth 20 points.
Correct simulation of circuits is worth 10 points.
One of the goals for this project is to establish good coding style. Look to the book and online guides about coding style. Variables should be clearly named. Comments should be used when code is unclear. Every Java file should have a comment header at the top giving your name, the course, the project, the date, and a short explanation of the class(es) in the file.
Note: Submissions which do not compile will automatically score 0 points.
As always, be sure to uphold the high standards of academic honesty required by this course. Failure to do so can lead to consequences as dire as failing the course and expulsion from the school. If you have any questions about whether or not a given action is allowed, please ask your instructor or TA.