4. Class Definition

Class Definition in Java

We spoke in the abstract about classes of objects in our discussion of modelling a road network or a digital logic circuit. Now, let's talk about implementing these classes in Java. Initially, we'll talk about these classes as pure data. We'll add behavior later.

If we are modelling a road network, we might begin with the following classes:

class Road {
	// indent to here between braces
}

class Intersection {
}

An aside on code format

Note in the above that the closing brace for each block is aligned under the keyword that opened the block, while the opening brace is at the end of the line (except perhaps for a comment). This indenting style is preferred both by our textbook's author (and by me)

There is a matter of style here. Java is perfectly happy if we write this as:

class Road { } class Intersection { }

But that is not very readable once the program gets longer than one line. We could also write it as follows, keeping the opening and closing braces vertically aligned with everything between indented. This style tends to push code onto more lines, pushing code off the bottom of the editing window. The stule the book uses tends to make balancing brackets easy enough without this waste of space.

class Road
    {
	// indent to here between braces
    }

class Intersection
    {
    }

Another question about code format is, how much should you indent. Short indents, for example, 4 spaces, allow deeper nesting than deep indents without adding pressure for longer lines. Tab stops in the Unix world are usually assumed to be every 8 characters, and this is the default supported by web browsers (when displaying preformatted text and .txt files. While you can set the tabs to other spacings, this can cause trouble, so the best bet is probably to leave the tabs at their default of 8 spaces and then, if you want to use shorter tabs, use the space bar and not the tab key.

But, the human mind can only digest a certain amount of complexity before it is overwhelmed. If your program really needs more than 4 or 5 levels of indenting, it may be too complex to understand and perhaps it should be broken up into digestable components.

Similar arguments suggest that long lines are not a good idea. Yes, the 80 column default for terminal windows is directly descended from the fact that punched cards have 80 characters each (a standard dating back to about 1928). But this standard is based on the length of a line of text on a typical page of typing paper, and that, in turn, is based on experience with easy readability. When pages get wider than that, people start using multiple columns of text because it really is difficult to read lines of text that span a wide page. Keep this in mind when you are tempted to simply widen your editing window and write really long lines of code.

Back to the road network

Regardless of how you indent it, the code given above is a framework, but we can store this in a file and start testing immediately. Consider using the file RoadNetwork.java

Of course, we ought to document this file with appropriate commentary, so right up front, we'll add some notes:

// RoadNetwork.java
/**
 * Classes needed to describe a road network
 * @author Douglas Jones
 * @version -1?
 */
class Road {
	/**
	 * Roads are one-way connections between intersections
	 * @see Intersection
 	 */
}

class Intersection {
	/**
	 * Intersections join roads
	 * @see road
 	 */
}

The above commentary uses the javadoc style of comments so that, later, when the program grows huge, we can use the javadoc tool to generate a documentation file from these comments.

Test this, save the file and use the javac command to make sure you have not messed up, then come back and start thinking about the next step. Let's start fleshing out the first class:

// RoadNetwork.java
/**
 * Classes that define the topology of a road network.
 * @author Douglas Jones
 * @version -1?
 */

class Road {
	/** Roads are one-way streets linking intersections
	 *  @see Intersection
	 */
	float travelTime;         //measured in seconds
	Intersection destination; //where the road goes
	// Bug: do I ever need to know what intersection feeds this road
}

Recall that one attribute of each road is the travel time on that road. We added that, and we added a destination for that road. We also added a comment indicating a currently unanswered question: When looking at a road, do we ever need to know where that road came from? We will probably learn this much later, when we start thinking about algorithms.

It is a really good idea to adopt a convention of writing comments in your code to document bugs and other things you don't understand. If you consistently use a word like Bug to mark such comments, you'll have a very easy time seeing where your code still needs work.

An aside on capitalization

The above code fragment illustrates two issues: The first has to do with multiple-word variable names. It might have been nice to call one variable travel time and the other intersection destination, but in Java, you cannot put spaces inside an identifier. Other languages differ. In Fortran (the oldest high-level programming language), spaces are allowed in identifiers. In fact, in Fortran, all spaces are ignored, so they can be added at random.

An alternative to the style used in the code here (and in the textbook) is to use underscore as a space character in identifiers, for example, travel_time. This is a very popular style.

The style used in the text, and here, has been called StudlyCaps as if there is something masculine about squeezing out the spaces and capitalizing the first letter of each word, and also BiCapitalization.

The secnd issue surrounding the use of capital letters is a matter of convention: Here, the first letter of each class name is capitalized, while this is not done for variable names. When you define a new symbol, you can capitalize it any way you want, but conventions can improve readability.

So why aren't the names of built-in classes like int and float capitalized? There are two explanations:

First: We could claim that this is to emphasize the fact that int and float are not quite first-class classes. If a Java object is from a first-class class, it inherits a large number of attributes from the superclass of all classes. This has a high cost. Objects of built-in classes like int and float don't inherit these attributes. They have much more limited semantics in order to allow very efficient execution.

Second: We could give the actual explanation. The type names int and float come from C and C++. Java didn't change things that worked just fine in those older languages.

Back to the road network

We can continue fleshing out our road network by adding comments to the definition of an intersection. We have some problems to solve here: How does one include a set of outgoing roads in a class? How does one create a class that comes in several types -- uncontrolled intersections, intersections where some road has a stop sign, intersections where all incoming roads have stopsigns? Does the intersection even need to know the identities of its incoming roads?

class Intersection {
	/** Intersections join roads
	 *  @see Road
	 */
	// Bug: multiple outgoing roads
	// Bug: multiple incoming roads
	// Bug: multiple types of intersections (uncontrolled, stoplight)
}

Class vehicle has the potential to have attributes like cargo capacity and passenger capacity, but those depend on why we are building the model. Initially, our biggest question about vehicles is, does the vehicle need to know its current location? The answers to these questions depend on how we use the model, but we need to go quite some distance before that matters.

class Vehicle {
	/** Vehicles travel on roads through intersections
	 *  @see Intersection
	 *  @see Road
	 */
	// Bug: what are the relevent attributes of a vehicle?
	// Bug: do I need my current location?
}

Finally, as mentioned in the previous lecture we need to worry about events. At the very least, events represent arrival of vehicles at intersections, but there may be other classes of events such as departure from intersections. Vehicles in an intersection might, for example, block that intersection until they depart.

class Event {
	/** Events mark arrival of vehicles at Intersections
	 *  @see Intersection
	 *  @see Vehicle
	 */
	float time;         //when the vehicle arrives
	Intersection place; //where vehicle will arrive
	// Bug: is this right?  There may be many queues at intersection
	// Bug: how do we know which queue the road leads to?
	// Bug: do vehicles spend time in intersections?
}

The Discrete-Event Simulation Algorithm

The basic discrete-event simulation algorithm has been known since the mid 1960s, and the algorithm applies to just about any discrete event model. The central feature of the model is a data structure, the pending event set. This is, as its name suggests, a set of pending events, that is, events that have been caused by events in the past but have not yet occurred.

The basic operations on the pending event are:

schedule e

The event e is inserted into the pending event set. The event e.time is the time at which the event is scheduled to occur.

e = getNext

The event e is extracted from the pending event set; e.time is less than or equal to the times of all other events in the set, and if other events in the set are scheduled to occur at exactly the same time, the model may be nondeterministic.

Some discrete-event models allow previously scheduled events to be deleted. Some higher level models consider events that extend over time, but we will ignore these. (Events that take time can be modeled by a sequence of instantaneous events, for example, one that starts the high-level event and another that marks its end).

The basic algorithm can be stated in a Java-like language as:

// for all x from the set of initial events
eventSet.schedule( x )
repeat {
	e = eventSet.getNext
	// simulate event e at time e.time
	// this may involve scheduling new events
}

There are two ways to terminate such a simulation: Either one of the initially scheduled events is a "terminate" event marking the end of time, or the model runs until the event set is empty.

In either case, within any iteration of the loop, e.time is the current time, and time lurches forward from event to event in an irregular manner. This is quite different from simulation models in which time advances in uniform-sized ticks; that type of model is more commonly used to deal with systems that are described by differential equations.

Note however that within the simulation of any event, the model may use arbitrarily complex code to predict the times of future events. In extreme cases, this prediction might involve running other simulation models, for example, involving differential equations.