| Department of Computer Science and Engineering | CSE 130 |
| University of California at San Diego | Spring 2002 |
This assignment is intended to demonstrate differences and similarities
between the C++ and Java languages. For this project you will use
abstract data types (ADTs) and exception-handling features.
Java and C++ are both object-oriented programming languages, so they provide a generalization of ADTs in the form of classes and objects. In order to show that you understand the ADT concept, you should not use all the object-oriented features of these languages. Instead, you should only use a subset that approximates the concept of ADT as described in class, as closely as possible. In your report, you should discuss to what extent ADTs (as opposed to general classes and objects) can be programmed in Java and in C++.
You should use the Java facilities for handling exceptions and for creating pointer-based data structures without explicit pointers. Exceptions are supposed to make defensive programming easier. Java provides exceptions using the primitives try and catch. The lack of explicit pointers is supposed to reduce memory management errors and make automatic garbage collection easier. In your report, you should discuss how you use each of these Java features.
You should not use any C++ features for exception-handling. Based on your experience, in your report, you should discuss how helpful (or not) it is for a programming language to provide special features for exception-handling. The point of the project is to see for yourselves the benefits and drawbacks of exception-handling, so you should not use C++ exceptions in any way.
The assignment is to implement in C++ and Java an abstract data type for the use of Comrade Spock. In a twisted universe Spock is the navigator of the starship Gosplan in the USSSS (Union of Soviet Socialist Solar Systems) fleet. Comrade Spock needs a type of values which are maps of the universe. The universe is a four-dimensional Euclidean hyperspace where the fourth dimension is time. The unit of measure in all four dimensions is the parsec, and the universe is bounded between -1000.0 and +1000.0 parsecs in each dimension. You can assume that velocities are bounded between -1000 and +1000 also.
The ADT you implement is a type where each value of the type represents an entire universe. The ADT must support the following operations:
In the movement simulation, the time step for each ship will be different, depending on its time-velocity relative to the Gosplan. You will need to scale the change in each direction by the ratio between the time-velocity of the ship and the time-velocity of the Gosplan. As an example, say the Gosplan is at location <a,b,c,d> with velocity <1,1,1,1> and a rebel ship is at <e,f,g,h> and velocity <2,3,4,2>. At the next second in the simulation, the Gosplan ends up at <a+1,b+1,c+1,d+1> but the rebel ship ends up at <e+4,f+6,g+8,h+2> because it is moving twice as fast (tv=2) as the Gosplan in time.
If any ship is caught in a loop of wormholes, or if other dangerous
conditions occur, appropriate exceptions should be raised. But think
about the interaction between the ideas of exception-raising and information-hiding.
Test cases will be published on a separate web page.
For this project, the important thing is to understand the fundamentals which the project brings out: exceptions, pure ADTs, C++ vs Java, memory management, etc. Details about the imaginary universe, like wrap-around, order of collision detection, etc. are relatively unimportant.
In Java, Javadoc comments are the usual way the interface is separated from the implementation of an ADT. Since Javadoc only generates HTML files describing the visible (ie non-private) methods and constructors of a class, this can be the way in which you separate the interface from the implementation as required for ADTs. Alternatively, you may define an interface, and then define a class which implements that interface [Brian Buesker]. Even in this case, Javadoc will still be the appropriate interface specification for using ADTs. You can imagine the case where the code is provided in the form of a library (.jar or .class files), in which case Javadoc may be your only interface information [Greg Hamerly].
Purity is an important concept, but not the only important concept in this project. A pure ADT is one whose operations do not modify the values provided by the ADT in a way visible to the user. Therefore, an integer type is a pure ADT because the operations on it (aside from assignment) such as +, -, *, / all produce new values from their arguments, rather than modifying their arguments. Likewise, your Universe ADT should be pure. Whenever you need to update locations of ships, you should create a new Universe. You may share ships between a new Universe and an old Universe, but the visible locations of ships in the old Universe must be unchanged, or else the Universe ADT will not be pure. In general, structure-sharing is good but you must make it invisible to users. In a pure ADT, only the operations available to the user need to be pure. As long as everything looks pure to the user, you can do whatever you want in the ADT implementation.
Your ADT should not
provide any I/O, because I/O is not part of its spec. You should implement
a simple main program that is like a shell:
(1) read a command,
e.g. "advance simulation one second" or "create a random universe"
(2) invoke the appropriate
ADT function
(3) display the
state of the universe
(4) repeat from
(1).
The grader will
use this menu interface to run the test cases. Test cases will be
reasonably straightforward. Correct behavior for them will be covered by
the answers on the message board, and here in the project description.
A wormhole loop is
an infinite cycle of wormholes that would be followed all at one time instant,
with no regular travel in between.
There is no simple
way to detect absolutely all wormhole loops perfectly. Therefore,
you only need to implement a reasonable heuristic. Your heuristic
should (1) be simple and understandable, and (2) detect obvious cases of
wormhole loops successfully. Wormhole loops should be detected as
soon as reasonable, but some delay may be unavoidable. You should
explain your heuristic in your report. Say whether it is sound, and whether
it is complete.
Issues analogous to detecting wormholes often occur in real-world software. For example, exactly when should software signal an exception for a student taking classes at UCSD that overlap in time, or that are retakes, or where prerequisites are not satisfied? How can all these conditions be detected efficiently? When more than one condition is satisfied, which should be signaled? There is no simple good answer to these questions.
In OOP applications,
software objects evolve to follow the changes and interactions of real-world
entities. One of the lessons of this project is that rules that appear
simple describing how real-world entities evolve are often ambiguous and
incomplete. You can make these assumptions:
(1) Time moves forward
for all ships first, then interactions are detected.
(2) Randomness applies
to all four dimensions.
(3) Chain reactions,
like wormhole loops, are possible. These occur immediately, before the
next time step.
You must describe all your work in a well-written report of length at most six pages. Follow the same requirements as for the previous project with regard to the paper. References that you may use are web pages and books. One recommended web page for information's on the Java language is http://java.sun.com/docs/books/tutorial/index.html.
For your report, you should consider and address the following questions, in addition to other issues which arise during the course of your assignment:
Be sure to follow all the rules and guidelines explained in the CSE
130 course
description. Complete academic
honesty is required.
[ghamerly@ghamerly java]$ java -classic Universe > addship 0 0 0 0 1 0 0 1 > addship 0 0 0 0 -1 0 0 1 > step 998 > display number of ships: 2 number of wormholes: 0 All ships: gosplan: [(998, 0, 0, 998) (1, 0, 0, 1)] 1: [(-998, 0, 0, 998) (-1, 0, 0, 1)] All wormholes: > step > display number of ships: 2 number of wormholes: 0 All ships: gosplan: [(999, 0, 0, 999) (1, 0, 0, 1)] 1: [(-999, 0, 0, 999) (-1, 0, 0, 1)] All wormholes: > step > display number of ships: 2 number of wormholes: 0 All ships: gosplan: [(1,000, 0, 0, 1,000) (1, 0, 0, 1)] 1: [(-1,000, 0, 0, 1,000) (-1, 0, 0, 1)] All wormholes: > step > display number of ships: 2 number of wormholes: 0 All ships: gosplan: [(-1,000, 0, 0, -1,000) (1, 0, 0, 1)] 1: [(1,000, 0, 0, -1,000) (-1, 0, 0, 1)] All wormholes: > step 10 > display number of ships: 2 number of wormholes: 0 All ships: gosplan: [(-990, 0, 0, -990) (1, 0, 0, 1)] 1: [(990, 0, 0, -990) (-1, 0, 0, 1)] All wormholes: > quit [ghamerly@ghamerly java]$
[ghamerly@ghamerly java]$ java -classic Universe > addship 0 0 0 0 10 10 -10 1 > addworm 500 500 -500 50 0 0 0 0 > display number of ships: 1 number of wormholes: 1 All ships: gosplan: [(0, 0, 0, 0) (10, 10, -10, 1)] All wormholes: 0: [(500, 500, -500, 50) -> (0, 0, 0, 0)] > step 49 > display number of ships: 1 number of wormholes: 1 All ships: gosplan: [(490, 490, -490, 49) (10, 10, -10, 1)] All wormholes: 0: [(500, 500, -500, 50) -> (0, 0, 0, 0)] > step > display number of ships: 1 number of wormholes: 1 All ships: gosplan: [(0, 0, 0, 0) (10, 10, -10, 1)] All wormholes: 0: [(500, 500, -500, 50) -> (0, 0, 0, 0)] > quit [ghamerly@ghamerly java]$
[ghamerly@ghamerly java]$ java -classic Universe > addship 0 0 0 0 1 0 0 1 > addship 10 0 0 10 1 0 0 -1 > display number of ships: 2 number of wormholes: 0 All ships: gosplan: [(0, 0, 0, 0) (1, 0, 0, 1)] 1: [(10, 0, 0, 10) (1, 0, 0, -1)] All wormholes: > step 4 > display number of ships: 2 number of wormholes: 0 All ships: gosplan: [(4, 0, 0, 4) (1, 0, 0, 1)] 1: [(6, 0, 0, 6) (1, 0, 0, -1)] All wormholes: > step > display number of ships: 2 number of wormholes: 0 All ships: gosplan: [(828.4, -760.8, 868, 626.7) (858.7, -341.3, -87.7, 158.8)] 1: [(-21.5, -45.1, -628.3, 229.8) (-441.6, -866.1, -16.6, -653)] All wormholes: > quit [ghamerly@ghamerly java]$
[ghamerly@ghamerly java]$ java -classic Universe
> addship 0 0 0 0 1 0 0 1
> addworm 10 0 0 10 20 30 40 50
> addworm 20 30 40 50 10 0 0 10
> display
number of ships: 1
number of wormholes: 2
All ships:
gosplan: [(0, 0, 0, 0) (1, 0, 0, 1)]
All wormholes:
0: [(10, 0, 0, 10) -> (20, 30, 40, 50)]
1: [(20, 30, 40, 50) -> (10, 0, 0, 10)]
> step 9
> display
number of ships: 1
number of wormholes: 2
All ships:
gosplan: [(9, 0, 0, 9) (1, 0, 0, 1)]
All wormholes:
0: [(10, 0, 0, 10) -> (20, 30, 40, 50)]
1: [(20, 30, 40, 50) -> (10, 0, 0, 10)]
> step
Caught wormhole loop exception: Ship 0 is in a wormhole loop starting in wormhole 0!
quitting...
[ghamerly@ghamerly java]$