Java Tutorials Part-3

 Drawing Lines

The awt contains several graphics primitives. Rectangles are one and we've pretty much beaten them into the ground in the previous section. Lines are another. Within a graphics context there is one key line drawing method, drawLine(int x1, int y1, int x2, int y2). This method draws a straight line between the point (x1, y1) and the point (x2, y2). Here's a simple applet that draws a line diagonally across the applet frame:
import java.applet.Applet;
import java.awt.*;

public class SimpleLine extends Applet {

int AppletHeight, AppletWidth;

public void init() {
Dimension d = size();
AppletHeight = d.height;
AppletWidth = d.width;
}

public void paint(Graphics g) {
g.drawLine(0, 0, AppletWidth, AppletHeight);
}

}
Graphing Functions
We're now going to demonstrate the use of the drawLine() method to draw considerably non-straight figures. It is shown in advanced calculus that any reasonably well-behaved (should that be differentiable?) function can be approximated arbitrarily well by straight lines where quantities like &well-behaved" and "arbitrarily are precisely defined. I'll spare you the details of the mathematical proof, but I will demonstrate its probability to you by producing an applet that does a very good job of graphing any function you care to throw at it. As usual we'll develop it in pieces rather than just throwing it all out at once.

We begin with the skeleton applet. We'll need to add some code to the paint method of the applet to make it draw something. Let's begin by drawing a sine wave from the left hand side of the image to the right hand side. Here's the complete program:
import java.applet.*;
import java.awt.*;
public class GraphApplet extends Applet {

int x0, xN, y0, yN;

public void init() {
// How big is the applet?
Dimension d = size();
x0 = 0;
xN = d.width-1;
y0=0;
yN=d.height-1;
}
public void paint(Graphics g) {

for (int x = x0; x <> g.drawLine(x,(int) (yN*Math.sin(x)),x+1, (int) (yN*Math.sin(x+1)));
}

}
}
The meat of this applet is in the for loop of the paint method.
for (int x = x0; x <> g.drawLine(x,(int) (yN*Math.sin(x)),x+1, (int) (yN*Math.sin(x+1)));
}
Here we loop across every x pixel of the applet. At each one we calculate the sine of that pixel. We also calculate the sine of the next pixel. This gives us two 2-D points and we draw a line between them. Since the sine of a real number is always between one and negative one, we scale the y value by yN. Finally we cast the y values to ints since sines are fundamentally floating point values but drawLine requires ints.

This applet runs but it's got a lot of problems. All of them can be related to two factors:

Sines are floating point operations. To do a really useful graphing applet we need to be able to use floating point numbers.

The coordinate system of an applet counts from (0,0) at the upper left hand corner to the right and down. The standard Cartesian coordinate system we expect graphs to use counts from (0,0) in the lower left hand corner to the right and up. The origin can be moved in both systems, for instance to the center of the applet, but we still need to transform between the y down and the y up coordinates.

There are a number of ways we can resolve this. The key to all of them, however, is to separate the data from the display. Since we are graphing more or less well behaved mathematical functions, we can assume that our data is completely described by a rectangle in Cartesian space within which we wish to plot a function. The display, on the other hand, is described by a rectangle of discrete points of fixed size and width. We need to be able to calculate in the general Cartesian plane and display in the particular applet window.

We'll need a method that will convert a point in the applet window into a point in the Cartesian plane, and one that will convert it back. Here it is:
import java.applet.*;
import java.awt.*;
public class GraphApplet extends Applet {

int x0, xN, y0, yN;
double xmin, xmax, ymin, ymax;
int AppletHeight, AppletWidth;

public void init() {
// How big is the applet?
Dimension d = size();
AppletHeight = d.height;
AppletWidth = d.width;
x0 = 0;
xN = AppletWidth-1;
y0=0;
yN=AppletHeight-1;
xmin = -10.0;
xmax = 10.0;
ymin = -1.0;
ymax = 1.0;
}
public void paint(Graphics g) {
double x1,y1,x2,y2;
int i, j1, j2;

j1 = yvalue(0);
for (i = 0; i <> j2 = yvalue(i+1);
g.drawLine(i, j1 ,i+1, j2);
j1 = j2;
}

}
private int yvalue(int ivalue) {
// Given the xpoint we're given calculate the Cartesian equivalent
double x, y;
int jvalue;
x = (ivalue * (xmax - xmin)/(AppletWidth - 1)) + xmin;
// Take the sine of that x
y = Math.sin(x);
// Scale y into window coordinates
jvalue = (int) ((y - ymin)*(AppletHeight - 1)/(ymax - ymin));
// Switch jvalue from cartesian coordinates to computer graphics coordinates
jvalue = AppletHeight - jvalue;
return jvalue;
}


}
Run this applet. Isn't that a much nicer looking sine wave? There are still a number of things we can add to make this a more complete applet though. The most important would be to add some parameters so that we can define the size of the applet in HTML. The following modification of the init and paint methods looks for xmin, xmax, ymin, and ymax to be specified via parameters. However for robustness if the author of the HTML forgets to specify them we supply some reasonable default values.
import java.applet.*;
import java.awt.*;
public class GraphApplet extends Applet {

int x0, xN, y0, yN;
double xmin, xmax, ymin, ymax;
int AppletHeight, AppletWidth;

public void init() {
String ParamString;
// How big is the applet?
Dimension d = size();
AppletHeight = d.height;
AppletWidth = d.width;
x0 = 0;
xN = AppletWidth-1;
y0=0;
yN=AppletHeight-1;

ParamString = getParameter("xmin");
if (ParamString != null) {
xmin = Double.valueOf(ParamString).doubleValue();
}
else {
xmin = -1.0;
}
ParamString = getParameter("xmax");
if (ParamString != null) {
xmax = Double.valueOf(ParamString).doubleValue();
}
else {
xmax = 1.0;
}
ParamString = getParameter("ymax");
if (ParamString != null) {
ymax = Double.valueOf(ParamString).doubleValue();
}
else {
ymax = 1.0;
}
ParamString = getParameter("ymin");
if (ParamString != null) {
ymin = Double.valueOf(ParamString).doubleValue();
}
else {
ymin = -1.0;
}
}

public void paint(Graphics g) {
double x1,y1,x2,y2;
int i, j1, j2;

j1 = yvalue(0);
for (i = 0; i <> j2 = yvalue(i+1);
g.drawLine(i, j1 ,i+1, j2);
j1 = j2;
}

}
private int yvalue(int ivalue) {
// Given the xpoint we're given calculate the Cartesian equivalent
double x, y;
int jvalue;
x = (ivalue * (xmax - xmin)/(AppletWidth - 1)) + xmin;
// Take the sine of that x
y = Math.sin(x);
// Scale y into window coordinates
jvalue = (int) ((y - ymin)*(AppletHeight - 1)/(ymax - ymin));
// Switch jvalue from cartesian coordinates to computer graphics coordinates
jvalue = AppletHeight - jvalue;
return jvalue;
}
}
Now we can adjust the range over which we graph without modifying our code!

So far we've only graphed sine functions. It should be obvious how to modify the code to graph cosines or many other kinds of functions. However what if we want to define the function at runtime?

Exercises
Add labeled coordinate axes to the graph.

Our graph method handled mathematical functions. How would you need to change it and what features would you add to make it suitable for plotting discrete experimental data?

An infinite set that with zero length
We're now going to use Java to implement some classic examples of fractal geometry. We'll do three of these. We begin with a one-dimensional set with an infinite number of points that covers zero length. Then we'll investigate the Koch snowflake. Finally in the next chapter we'll delve into the most famous fractal of all, the Mandelbrot set.

The middle third set is defined by starting with all the real numbers between zero and one inclusive. Then we cut out the middle third of that set (exclusive of the endpoints). i.e. everything between one third and two thirds exclusive.

Next we cut the middle third of the two line segments that remain, i.e. everything between one ninth and two ninths and between seven ninths and eight ninths. We continue this process indefinitely.

Was that confusing? Good. A picture is worth a thousand words and a good Java program is worth a thousand pictures. We now proceed to show you a Java program that draws successive pictures to demonstrate the middle third set.

import java.applet.Applet;
import java.awt.*;
import java.util.Vector;

public class MiddleThird extends Applet {

int AppletWidth;
int AppletHeight;

Vector endpoints = new Vector();

public void init() {
Dimension d = size();
AppletHeight = d.height;
AppletWidth = d.width;
endpoints.addElement(new Float(0.0f));
endpoints.addElement(new Float(1.0f));
}

public void paint(Graphics g) {
float x1, x2;
Float tempFloat;
for (int i = 0; i <> // draw the lines
for (int j=0; j <> tempFloat = (Float) endpoints.elementAt(j);
x1 = tempFloat.floatValue();
tempFloat = (Float) endpoints.elementAt(j+1);
x2 = tempFloat.floatValue();
g.drawLine( Math.round(x1*AppletWidth), i, Math.round(x2*AppletWidth), i);
}
//remove the middle third of the lines
CutSegments();
// Now check to see if we've exceeded the resolution of our screen
tempFloat = (Float) endpoints.elementAt(0);
x1 = tempFloat.floatValue();
tempFloat = (Float) endpoints.elementAt(1);
x2 = tempFloat.floatValue();
if (Math.round(x1*AppletWidth) == Math.round(x2*AppletWidth)) break;
}
}

private void CutSegments() {

int index = 0;
float gap;
float x1, x2;
Float tempFloat1, tempFloat2;
int stop = endpoints.size();
for (int i=0; i <> CutMiddleThird(index, index+1);
index += 4;
}
}
private void CutMiddleThird(int left, int right) {

float gap;
float x1, x2;
Float tempFloat1, tempFloat2;
tempFloat1 = (Float) endpoints.elementAt(left);
tempFloat2 = (Float) endpoints.elementAt(right);
gap = tempFloat2.floatValue() - tempFloat1.floatValue();
x1 = tempFloat1.floatValue() + gap/3.0f;
x2 = tempFloat2.floatValue() - gap/3.0f;
endpoints.insertElementAt(new Float(x2), right);
endpoints.insertElementAt(new Float(x1), right);
}

}
Compile and load this applet. Is that clearer? Of course this isn't a perfect representation of the middle third set since we have to deal with points of finite size rather than with genuine mathematical points. Depending on how large a window you give your applet, you will probably only see about six to twelve iterations before we need to start working with fractional pixels.

Flying Lines
The next example is harder to describe than it is to code. Like Mondrian it runs in an infinite loop but it's a little more than random images. Compile the following code, run it and then look over the code to see if you can understand the algorithm.
//Bounce lines around in a box

import java.applet.Applet;
import java.awt.*;
public class FlyingLines extends Applet {

int NUM_LINES = 25;
int gDeltaTop=3, gDeltaBottom=3;
int gDeltaLeft=2, gDeltaRight=6;
int AppletWidth, AppletHeight;
int gLines[][] = new int[NUM_LINES][4];

public void init() {

AppletWidth = size().width;
AppletHeight = size().height;

}
public void start() {
gLines[0][0] = Randomize(AppletWidth);
gLines[0][1] = Randomize(AppletHeight);
gLines[0][2] = Randomize(AppletWidth);
gLines[0][3] = Randomize(AppletHeight);
for (int i=1; i <> LineCopy(i, i-1);
RecalcLine(i);
}
repaint();
}

public void paint(Graphics g) {

while (true) {
for (int i=NUM_LINES - 1; i > 0; i--) {
LineCopy(i, i-1);
}
RecalcLine(0);
g.setColor(Color.black);
g.drawLine(gLines[0][0], gLines[0][1], gLines[0][2], gLines[0][3]);
g.setColor(getBackground());
g.drawLine(gLines[NUM_LINES-1][0], gLines[NUM_LINES-1][1],
gLines[NUM_LINES-1][2], gLines[NUM_LINES-1][3]);
}
}

private void LineCopy (int to, int from) {

for (int i = 0; i <> gLines[to][i] = gLines[from][i];
}

}

public int Randomize( int range ) {
double rawResult;

rawResult = Math.random();
return (int) (rawResult * range);

}

private void RecalcLine( int i ) {

gLines[i][1] += gDeltaTop;
if ((gLines[i][1] <> AppletHeight)) {
gDeltaTop *= -1;
gLines[i][1] += 2*gDeltaTop;
}

gLines[i][3] += gDeltaBottom;
if ( (gLines[i][3] <> AppletHeight) ) {
gDeltaBottom *= -1;
gLines[i][3] += 2*gDeltaBottom;
}

gLines[i][0] += gDeltaLeft;
if ( (gLines[i][0] <> AppletWidth) ) {
gDeltaLeft *= -1;
gLines[i][0] += 2*gDeltaLeft;
}

gLines[i][2] += gDeltaRight;
if ( (gLines[i][2] <> AppletWidth) ) {
gDeltaRight *= -1;
gLines[i][2] += 2*gDeltaRight;
}
} //RecalcLine ends here

} // FlyingLines ends here
Taking Action: Threads
Depending on your operating system and Java-enabled browser you may have noticed that the Mondrian and Flying Line programs tended to hog your CPU. On Windows NT HotJava stopped responding to my commands several thousand iterations into Mondrian, and I had to kill it from the Task List.

The paint loops in both Mondrian and FlyingLines are ideal for a thread, a separate stream of execution that takes place simultaneously and independently of everything else that might be happening (like responding to the programmer's insistence to "Quit!, Damnit!"). Without threads an entire program can be held up by one CPU intensive task or, as in Flying Lines, one infinite loop, intentional or otherwise.

As a general rule all CPU intensive tasks should be placed in their own threads. Here's one way to do it.
//Draw infinitely many random rectangles

import java.applet.Applet;
import java.awt.*;

public class ThreadedMondrian extends Applet implements Runnable {

int RectHeight, RectWidth, RectTop, RectLeft, AppletWidth, AppletHeight;
Color RectColor;
Thread kicker = null;
int pause;
public void init() {

Dimension d = size();
AppletHeight = d.height;
AppletWidth = d.width;
repaint();
}

public void paint(Graphics g) {
g.setColor(Color.black);
g.drawRect(0, 0, AppletWidth-1, AppletHeight-1);
for (int i=0; i <> RandomRect();
g.setColor(RectColor);
g.fillRect(RectLeft, RectTop, RectWidth-1, RectHeight-1);
}
}
public void run() {
Thread.currentThread().setPriority(Thread.MIN_PRIORITY);

while (true) { // infinite loop
repaint();
try {
Thread.sleep(100);
}
catch (Exception e) {
}
}
}

public void start() {
if (kicker == null) {
kicker = new Thread(this);
kicker.start();
}
}

public void stop() {
kicker = null;
}

public void RandomRect() {
RectTop = Randomize(AppletHeight);
RectLeft = Randomize(AppletWidth);
RectHeight= Randomize(AppletHeight - RectTop);
RectWidth = Randomize(AppletWidth - RectLeft);
RectColor = new Color(Randomize(255),Randomize(255),Randomize(255));
}

private int Randomize(int range)
{
double rawResult;

rawResult = Math.random();
return (int) (rawResult * range);

}

}

We added four key things to Mondrian to make it threaded and a lot more CPU friendly.

We specified that our applet implements Runnable.
We added a run method.
We added a start method.
We added a stop method.

Let's look at them in more detail:
Our applet implements Runnable

Run Method
Start Method
Stop Method

Here's a threaded version of Flying Lines.

//Bounce lines around in a box

import java.applet.Applet;
import java.awt.*;
public class FlyingLines extends Applet implements Runnable {

int NUM_LINES = 25;
int gDeltaTop=3, gDeltaBottom=3;
int gDeltaLeft=2, gDeltaRight=6;
int AppletWidth, AppletHeight;
int gLines[][] = new int[NUM_LINES][4];

public void init() {

AppletWidth = size().width;
AppletHeight = size().height;

}
public void start() {
gLines[0][0] = Randomize(AppletWidth);
gLines[0][1] = Randomize(AppletHeight);
gLines[0][2] = Randomize(AppletWidth);
gLines[0][3] = Randomize(AppletHeight);
for (int i=1; i <> LineCopy(i, i-1);
RecalcLine(i);
}
repaint();
Thread t = new Thread(this);
t.start();
}

public void run () {
Thread.currentThread().setPriority(Thread.MIN_PRIORITY);
while (true) {
for (int i=NUM_LINES - 1; i > 0; i--) {
LineCopy(i, i-1);
}
RecalcLine(0);
System.out.println(gLines[0][0] + ", " + gLines[0][1] + "," + gLines[0][2] + ", " + gLines[0][3]);
repaint();
try {
Thread.currentThread().sleep(10);
}
catch (Exception e) {
}
}
}

public void paint(Graphics g) {

for (int i=0; i <> g.drawLine(gLines[i][0], gLines[i][1], gLines[i][2], gLines[i][3]);
}
}

private void LineCopy (int to, int from) {

for (int i = 0; i <> gLines[to][i] = gLines[from][i];
}

}

public int Randomize( int range ) {
double rawResult;

rawResult = Math.random();
return (int) (rawResult * range);

}

private void RecalcLine( int i ) {

gLines[i][1] += gDeltaTop;
if ((gLines[i][1] <> AppletHeight)) {
gDeltaTop *= -1;
gLines[i][1] += 2*gDeltaTop;
}

gLines[i][3] += gDeltaBottom;
if ( (gLines[i][3] <> AppletHeight) ) {
gDeltaBottom *= -1;
gLines[i][3] += 2*gDeltaBottom;
}

gLines[i][0] += gDeltaLeft;
if ( (gLines[i][0] <> AppletWidth) ) {
gDeltaLeft *= -1;
gLines[i][0] += 2*gDeltaLeft;
}

gLines[i][2] += gDeltaRight;
if ( (gLines[i][2] <> AppletWidth) ) {
gDeltaRight *= -1;
gLines[i][2] += 2*gDeltaRight;
}
} //RecalcLine ends here

} // FlyingLines ends here
Bozo Sort

Some of the first compelling Java demos were graphical illustrations of several sorting methods including quick sort, bubble sort and bidirectional bubblesort intended to show off the threading capabilities of Java. That's nice, but those methods eventually succeed within our lifetime. For an applet that truly puts threading to good use consider the following bozo sort. In bozo sort the same collection of differently sized sticks is thrown up in the air. If they land in sorted order, the algorithm stops. Otherwise we throw all the sticks in the air again. This algorithm runs in about O(N!) time where N is the number of sticks. It takes effectively infinite time for more than a dozen or so sticks. It's a horrible algorithm but a really great opportunity for threading.

class BozoSortAlgorithm extends SortAlgorithm {

void sort(int a[]) {
boolean sorted = false;
while (!sorted) {
int index1 = Randomize(a.length);
int index2 = Randomize(a.length);
int temp = a[index2];
a[index2] = a[index1];
a[index1] = temp;
// Is a[] sorted?
sorted = true;
for (int i = 1; i <> if (a[i-1] > a[i]) {
sorted = false;
break;
} // end if
} // end for
} // end while
} // end sort
private int Randomize( int range ) {

double rawResult;
rawResult = Math.random();
return (int) (rawResult * range);

}
} // end BozoSortAlgorithm

To actually run this you'll also need the SortItem and SortAlgorithm classes from Sun.
Interaction: Mouse and Keyboard Input

You now have the tools to draw a lot of really cool animations and images on your web pages. This alone puts you leaps and bounds beyond the average web page designer. Still that's only half the point of applets. The other half is interaction with the user. Your applets can accept input from the user and respond to them. For the first time a web surfer can move beyond mere browsing to genuine participation.
Mouse Input: Java Doodle

Here's a simple applet that lets you doodle with the mouse on an applet.
import java.applet.Applet;
import java.awt.*;
import java.util.Vector;

public class JavaDoodle extends Applet {

Vector points = new Vector();

public void paint(Graphics g) {
int x1, y1, x2, y2;
Point tempPoint;
if (points.size() > 1) {
tempPoint = (Point) points.elementAt(0);
x1 = tempPoint.x;
y1 = tempPoint.y;
for (int i = 1; i <> tempPoint = (Point) points.elementAt(i);
x2 = tempPoint.x;
y2 = tempPoint.y;
g.drawLine(x1, y1, x2, y2);
x1 = x2;
y1 = y2;
} // end for
} // end if
}
public boolean mouseDown(Event e, int x, int y) {
points.addElement(new Point(x, y));
return true;
}

public boolean mouseDrag(Event e, int x, int y) {
points.addElement(new Point(x, y));
repaint();
return true;
}

public boolean mouseUp(Event e, int x, int y) {
points.addElement(new Point(x, y));
repaint();
return true;
}



}
Exercises
Revise the applet so that it doesn't draw a line between the point where the mouse button was released and the point where it was pressed again.
Keyboard Input: TypeWriter
Here's a simple applet that uses the keyDown method to let you type some text.

import java.applet.Applet;
import java.awt.Event;
import java.awt.Graphics;

public class typewriter extends Applet {

int numcols = 80;
int numrows = 25;
int row = 0;
int col = 0;
char page[][] = new char[numrows][];

public void init() {

for (int i = 0; i <> page[i] = new char[numcols];
}
for (int i = 0; i <> for (int j = 0; j <> page[i][j] = '\0';
}
}

}
public boolean keyDown(Event e, int key) {
char c = (char) key;

switch (key) {
case Event.HOME:
row = 0;
col = 0;
break;
case Event.END:
row = numrows-1;
col = numcols-1;
break;
case Event.UP:
if (row > 0) row--;
break;
case Event.DOWN:
if (row <> break;
case Event.LEFT:
if (col > 0) col--;
else if (col == 0 && row > 0) {
row--;
col=numcols-1;
}
break;
case Event.RIGHT:
if (col <> else if (col == numcols-1 && row <> row++;
col=0;
}
break;
default:
if (c == '\n' || c == '\r') {
row++;
col = 0;
}
else if (row <> if (col >= numcols) {
col = 0;
row++;
}
page[row][col] = c;
col++;
}
else { // row >= numrows
col++;
}
}
repaint();
return true;
}


public void paint(Graphics g) {

for (int i=0; i <> String tempString = new String(page[i]);
g.drawString(tempString, 5, 15*(i+1));
}
}

}
Part 4: Objects, Classes, Methods, and Interfaces
What is Object Oriented Programming?

Object Oriented Programming is the programming buzzword of the 90's. Everyone and everything advertises their products as object-oriented. But what does object oriented mean? To understand why object oriented programming is so revolutionary, let's take a brief glance back at the history of computing.
The History of Programming

Programming has always been guided by various methodologies. In the early days of computers, computer memories were quite small. Programs had to be loaded in by toggling switches on a panel. In these days it was possible for a programmer to keep track of every memory location and every machine instruction in his or her head. Since computer memories were so small (often just a few hundred bytes) and the machines so slow, program efficiency was the primary concern. Any program was acceptable as long as it worked. Algorithms were very closely tied to the capabilities of the specific machine they ran on. This is called machine language programming. The toggling of individual memory locations (by switch or other means) is called a first-generation language, and we're being very liberal with the definition of language. In a first generation language there is almost no abstraction.

As computers grew in power and memory, it was no longer possible for a programmer to keep track of what was happening at every location in the machine's physical memory. Card readers and assembly language were invented to make programming more feasible. In assembly language the programmer uses mnemonic codes like MOV to represent particular bit sequences. These codes mapped directly to individual instructions on the CPU, and memory was still addressed directly. One code meant exactly one CPU instruction. (More modern assembly languages don't always map as directly to the CPU as the older ones did.) Algorithmically The philosophy of "Use whatever works" continued.

Assembly language was still a bear to deal with, especially as related to arrays and storage in memory. Therefore the first high-level programming language, Fortran, was invented to spare programmers from the pains of dealing with keeping track of the location of their variables in memory. (It's interesting to note that this lesson has had to be learned again and again and again. The buggiest parts of C and C++ programs result from programmers being allowed to access arbitrary bytes of memory. Java has wisely removed this capability. 99 times out of a 100 you don't need it. A large part of training a C or C++ programmer to use Java, consists of convincing them of this fact.). Fortran was the first example of a third-generation language. In a third generation language you tell the computer the algorithms and data structures it should use to calculate the results you want; but you use more abstract logical and mathematical operators rather than directly manipulating addresses in memory and CPU instructions. In a third generation language, statements represent several machine instructions. Which instructions they represent may even depend on their context.

These languages may be compiled or interpreted. In either case your program code needs to be translated into equivalent machine instructions. This level of abstraction made considerably more powerful algorithms and data structures possible.

Java is a very advanced third generation language. Most of the other computer languages you're probably familiar with, Fortran, Basic, C, C++, Cobol, Pascal, as well as most of the one's you're not familiar with (AppleScript, Frontier, Eiffel, Modula-3, ADA, PL/I, etc.) are also third-generation languages (or 3GL's for short).

When third generation languages were invented, they were supposed to make computers so easy to use even the CEO could write programs. This turned out not to be true. Fourth generation languages (or 4GL's for short) moved the abstraction level a step higher. In these languages you tell the computer what results you want rather telling it how to calculate those results. For instance you would ask for the total sales for the year, without specifying the loops necessary to sum all the sales of all the salespeople. SQL is the most popular fourth generation language.

Of all these languages there's no question that 3GL's have been the most successful by almost any measure. A number of different styles of 3GL programming and programming languages have sprung up, most learning from the experience and mistakes of its predecessors. Fortran (and its cousin Basic) were the first. They shared with assembly language an attitude of "Whatever works, no matter how ugly." They had limited flow control (essentially for loops and goto statements) and one data structure, the array. All variables were global and it was impossible to hide one part of the program from any other. Although it was possible to write maintainable, legible code in these languages, few people did.

Pascal and C were the next widely successful languages. They made possible a style of programming known as structured programming. Structured programming languages have many different flow control constructs (switch statements, while loops, and more) as well as tools for more complicated data structures (structs, records and pointers). Goto is deprecated in structured programming though not eliminated entirely. (It is still necessary for some error handling.) Finally they have subroutines with local variables that are capable of splitting the code into more manageable and understandable chunks. These languages proved more capable of writing larger, more maintainable programs. However they too began to bog down when faced with the need to share code among programmers and to write very large (greater than 50,000 line) programs.

Some of the above history may sound a little funny to those of you with experience in the languages I'm discussing. After all Basic has subroutines and local variables, doesn't it? The fact is successful computer languages have continued to evolve. Fortran now has pointers so it can create more complicated data structures. Basic has while loops. Cobol has objects. And on some architectures like Alpha/VMS the assembly language bears little to no resemblance to the underlying machine architecture. These features were not parts of the first versions of the language, however. And despite these improvements the modern versions of these languages are their parents children. Basic and Fortran programmers still often produce spaghetti code. Assembly language is quick to run but long to program. C is obfuscated beyond the comprehension of mere mortals.

The third generation of 3GL's (3.3 GL's) began to take hold in the late 80's. These were the object oriented languages. Although object oriented languages had been around since the late 1960's, it wasn't until the late 80's that computer hardware became fast enough and memory cheap enough to support them. (Object oriented programming is not a panacea. It exacts a speed penalty over plain vanilla C or Fortran code, and often requires twice as much memory.)

Object oriented languages (OOP for short) included all the features of structured programming and added still more powerful ways to organize algorithms and data structures. There are three key features of OOP languages: encapsulation, polymorphism and inheritance. All of them are tied to the notion of a class.
Classes and Objects

The primary distinguishing feature of OOP languages is the class. A class is a data structure that can associate the methods which act on an object with the object itself. In pre-OOP languages methods and data were separate. In OOP languages they are all part of classes.

Programming languages provide a number of simple data types like int, float and String. However very often the data you want to work with may not be simple ints, floats or Strings. Classes let programmers define their own more complicated data types.

For instance let's suppose your program needs to keep a database of web sites. For each site you have a name, a URL, and a description. In traditional programming languages you'd have three different String variables for each web site. With a class you combine these into one package like so:
class website {

String name;
String url;
String description;

}

These variables (name, url and description) are called the members of the class. They tell you what a class is and what its properties are. They are the nouns of the class.

In our web site database we will have many thousands of websites. Each specific web site is an object. The definition of a web site though, which we gave above, is a class. This is a very important distinction. A class defines what an object is, but it is not itself an object. An object is a specific instance of a class. Thus when we create a new object we say we are instantiating the object. Each class exists only once in a program, but there can be many thousands of objects that are instances of that class.

To instantiate an object in Java we use the new operator. Here's how we'd create a new web site:

website x = new website();
Once we've got a website we want to know something about it. To get at the member variables of the website we can use the . operator. Website has three member variables, name, url and description, so x has three member variables as well, x.name, x.url and x.description. We can use these just like we'd use any other String variables. For instance:

website x = new website();
x.name = "Cafe Au Lait";
x.url = "http://metalab.unc.edu/javafaq/";
x.description = "Really cool!";
System.out.println(x.name + " at " + x.url + " is " + x.description);
Methods
Data types aren't much use unless you can do things with them. For this purpose classes have methods. Members say what a class is. Methods say what a class does. For instance our website class might have a method to print its data. If so that would look like this:
class website {

String name;
String url;
String description;
print() {
System.out.println(name + " at " + url + " is " + description);
}

}
Outside the website method we call the print method just like we referenced the member variables, using the name of the particular object we want to print and the . operator.

website x = new website();
x.name = "Cafe Au Lait";
x.url = "http://metalab.unc.edu/javafaq/";
x.description = "Really cool!";
x.print();
Notice that within the website class we don't need to use x.name or x.url. name and url are sufficient. That's because the print method must be called by a specific instance of the website class, and this instance knows what its data is. Or, another way of looking at it, the every object has its own print method.

The print() method is completely enclosed within the website class. All methods in Java must belong to a class. Unlike C++ programs, Java programs cannot have a method hanging around in global space that does everything you forgot to do in your classes.

Constructors
The first method most classes need is a constructor. A constructor creates a new instance of the class. It initializes all the variables and does any work necessary to prepare the class to be used. In the line website x = new website(); website() is a constructor. If no constructor exists Java provides a default one, but it's better to make sure you have your own. You make a constructor by writing a public method that has the same name as the class. Thus our website constructor is called website(). Here's a revised website class with a constructor that initializes all the members to null Strings.
class website {

String name;
String url;
String description;
public website() {
name = "";
url = "";
description = "";
}

}
Better yet, we should create a constructor that accepts three Strings as arguments and uses those to initialize the member variables like so:
class website {

String name;
String url;
String description;
public website(String n, String u, String d) {
name = n;
url = u;
description = d;
}

}
We'd use this like so:

website x = new website("Cafe Au Lait", "http://metalab.unc.edu/javafaq/", "Really cool!");
x.print();
This fits in well with the goal of keeping code relevant to the proper functioning of a class within the class.

However what if sometimes when we want to create a web site we know the URL, name, and description, and sometimes we don't? Best of all, let's use both!
class website {

String name;
String url;
String description;
public website(String n, String u, String d) {
name = n;
url = u;
description = d;
}

public website() {
name = "";
url = "";
description = "";
}

}
This is called method overloading or polymorphism. Polymorphism is a feature of object oriented languages that lets one name refer to different methods depending on context. The important context is typically the number and type of arguments to the method. In this case we use the first version of the method if we have three String arguments and the second version if we don't have any arguments.

If you have one or two or four String arguments to the constructor, or arguments that aren't Strings, then the compiler generates an error because it doesn't have a method whose signature matches the requested method call.

toString Methods
Print methods are common in some languages but most Java programs operate differently. You can use System.out.println() to print any object. However for good results your class should have a toString() method that formats the objects data in a sensible way and returns a String. Here's how we'd implement it in the website example:
public class ClassTest {

public static void main(String args[]) {
website x = new website("Cafe Au Lait", "http://metalab.unc.edu/javafaq/", "Really cool!");
System.out.println(x);
}

}


class website {

String name;
String url;
String description;
public website(String n, String u, String d) {
name = n;
url = u;
description = d;
}

public website() {
name = "";
url = "";
description = "";
}
public String toString() {
return (name + " at " + url + " is " + description);
}

}
Some Advocacy
Unfortunately the object oriented language that took hold was C++. Among much fitter contenders for object languages, notably Smalltalk, C++ had the unique advantage of being downward compatible with the C programmers were already familiar with. Unfortunately this advantage had the huge side effect of forcing C++ to accept all of C's obfuscated macros, pointer arithmetic, and now redundant structs. The baggage imposed on C++ by the need to be compatible with C went a long way toward wiping out the advantage of object oriented programming.

Java is the latest and possibly the greatest third generation programming language. Here I need to explain why Java is a better OOP language than C++.

A Non-Trivial Examples: Complex Numbers
As mentioned in Chapter 2 one of the features needed for serious scientific computation is complex numbers. Unfortunately no popular computer language other than Fortran provides them as a built-in data type. (Actually this is such a common and useful example and was used by so many textbooks that it was recently added to the C++ standard library which makes it far less useful as an example. Fortunately, however, Java has not yet been around long enough to have all its really useful examples coopted into the standard library.) Let's see how we might implement them in Java. From the standpoint of a data type you really don't need much. Mathematically a complex number is composed of a real part u and an imaginary part v. We can create such a class in the following way:
public class ComplexNumber extends Object {

public double u;
public double v;

}
While this is sufficient to encompass all the data that one needs in a complex number it's not a very good example of object-oriented programming. To actually do anything with this number we have to know exactly how the data structure is defined. If we change the data structure, for instance by defining a complex number in terms of it's magnitude r and its argument theta instead of by its real and imaginary components we have to change all the code that depends on it.

We also have to write code to explicitly add the numbers, multiply them or do anything else we might need to do with complex numbers. If we need to add complex numbers in more than one place, then we need to write the addition code again, or, at the very least, copy and paste it.

A better implementation of a complex number class will shield us from the exact storage of the data, i.e. x and y vs. r and theta. It will also provide methods that let us perform any operation we might need to perform on or with a complex number.

Before writing code we need to ask ourselves what we'll do with a complex number. Most objects first require a constructor, a method that is called when you create a new complex number. A more complicated object may also require a destructor method that's called when you get rid of an object; but since this is a fairly simple object, we'll let Java's built-in garbage collection take care of that for us.

Since these are complex numbers it's not unlikely that we'll need to add them, subtract them, multiply them and divide them. We'll also want to be able to access their real and imaginary parts as well as their absolute values and arguments. The following class does all that.

//
public class Complex extends Object {

private double u;
private double v;

Complex (double x, double y) {

u=x;
v=y;

}

public double Real () {

return u;

}

public double Imaginary () {

return v;

}

public double Magnitude () {

return Math.sqrt(u*u + v*v);

}

public double Arg () {

return Math.atan2(v, u);

}

// Add z to w; i.e. w += z
public Complex Plus (Complex z) {

return new Complex(u + z.u, v + z.v);

}

// Subtract z from w
public Complex Minus (Complex z) {

return new Complex(u - z.u, v - z.v);

}

public Complex Times (Complex z) {

return new Complex(u*z.u - v*z.v, u*z.v + v*z.u);
}


// divide w by z
public Complex DivideBy (Complex z) {

double rz = z.Magnitude();

return new Complex((u * z.u + v * z.v)/(rz*rz),(v * z.u - u * z.v)/(rz*rz));

}

}

Notice especially that u and v are now private. They cannot be accessed by external code even if we want them to be.

The use of one of these methods will look like the following. Add the following ComplexExamples class to the Complex.java file and compile. Then run ComplexExamples in the usual way by typing java ComplexExamples.
//Complex Arithmetic Examples
class ComplexExamples {

public static void main (String args[]) {
Complex u, v, w, z;

u = new Complex(1,2);
System.out.println("u: " + u.Real() + " + " + u.Imaginary() + "i");
v = new Complex(3,-4.5);
System.out.println("v: " + v.Real() + " + " + v.Imaginary() + "i");
// Add u + v;
z=u.Plus(v);
System.out.println("u + v: "+ z.Real() + " + " + z.Imaginary() + "i");
// Add v + u;
z=v.Plus(u);
System.out.println("v + u: "+ z.Real() + " + " + z.Imaginary() + "i");

z=u.Minus(v);
System.out.println("u - v: "+ z.Real() + " + " + z.Imaginary() + "i");
z=v.Minus(u);
System.out.println("v - u: "+ z.Real() + " + " + z.Imaginary() + "i");

z=u.Times(v);
System.out.println("u * v: "+ z.Real() + " + " + z.Imaginary() + "i");
z=v.Times(u);
System.out.println("v * u: "+ z.Real() + " + " + z.Imaginary() + "i");

z=u.DivideBy(v);
System.out.println("u / v: "+ z.Real() + " + " + z.Imaginary() + "i");
z=v.DivideBy(u);
System.out.println("v / u: "+ z.Real() + " + " + z.Imaginary() + "i");

}

}
Exercises
What happens if we try to add a complex number to itself? e.g.


z = u.Add(u);
How about if we multiply, divide or subtract? e.g.


z = u.Multiply(u);
z = u.Divide(u);
z = u.Minus(u);
Rewrite the Complex class so that it stores its data as r and theta rather than u and v. Be sure to be careful at zero.
Add PlusEqual, MinusEqual, DivideEqual and MultiplyEqual methods to the Complex class that mimic the behavior of the +=, -=, *= and /= operators.
Add an equality method to the Complex class that tests whether two complex numbers are equal and returns a boolean.
For math whizzes only: Explain why it would not be a good idea to add less than or greater than methods to the Complex class.
For math whizzes only: Add a logarithm method to the Complex number class. Pick the branch between zero and 2pi.
For math whizzes only: Add a power method to the complex number class. This is straightforward for real powers. For a real challenge allow arbitrary complex powers. Be sure to consider how you'll deal with branch cuts.
toString Methods
Our printing in the last program was quite stilted because we needed to break a complex number into its real and imaginary parts, print them, and then put it all back together again. Wouldn't it be nice if we could just write:

System.out.println(u);

instead? It turns out we can. All objects have a toString method which is inherited from the Object class. However the default toString() method isn't very useful so we want to override it with one of our own creation that handles the conversion to complex numbers. Add the following method to the Complex class:
public String toString() {
if (v >= 0) return (String.valueOf(u) + " + " + String.valueOf(v) + "i");
else return (String.valueOf(u) + " - " + String.valueOf(-v) + "i");
}

You should also modify the ComplexExamples class as follows:


class ComplexExamples {

public static void main (String args[]) {
Complex u, v, z;

u = new Complex(1,2);
System.out.println("u: " + u);
v = new Complex(3,-4.5);
System.out.println("v: " + v);
// Add u + v;
z=u.Plus(v);
System.out.println("u + v: " + z);
// Add v + u;
z=v.Plus(u);
System.out.println("v + u: " + z);


z=u.Minus(v);
System.out.println("u - v: " + z);
z=v.Minus(u);
System.out.println("v - u: " + z);

z=u.Times(v);
System.out.println("u * v: " + z);
z=v.Times(u);
System.out.println("v * u: "+ z);

z=u.DivideBy(v);
System.out.println("u / v: " + z);
z=v.DivideBy(u);
System.out.println("v / u: " + z);

}
}

That's about an order of magnitude easier to understand and to write.
Polymorphism

So far our methods just do arithmetic on two complex numbers. It's not uncommon to want to multiply a complex number by a real number. To add this capability to our class we'll add the following method:
public Complex Times (double x) {

return new Complex(u*x, v*x);
}

Here's a simple test program for your new method:

class RealComplex {

public static void main (String args[]) {
Complex v, z;
double x = 5.1;


v = new Complex(3,-4.5);
System.out.println("v: " + v);
System.out.println("x: " + x);


z=v.Times(x);
System.out.println("v * x: " + z);


}
}

The astute among you may be saying to hold on here, we've redefined the Times method. Now how can we multiply two complex numbers? However there's really no problem. The compiler notices that the arguments of the two methods named Times (not the same as the arguments of the two complex numbers but unfortunately the terminology fails us here) are different. One multiplies two complex numbers, the other multiplies a real number and a complex number. The compiler is smart enough to figure out which version of Times to use when. This is called method overloading or polymorphism.

In some object-oriented languages like C++ you can not only overload methods but even operators like + and =. However while this makes numeric classes like complex numbers easier to work with, it tends to lead to unreadable and unmaintainable code for non-numeric classes. Therefore Java's designers elected not to add this feature to the language. As you can see from our example, with a little forethought you really don't lose very much without operator overloading.

Exercises
Add a method to the Complex class that adds a real number to a complex number and returns a complex number.
Add methods for subtracting a real number from a complex number and for subtracting a complex number from a real. Be careful since subtraction, unlike addition, is not commutative.
Add methods for dividing a real by a complex number and for dividing a complex number by a real. Be careful since division, unlike multiplication, is not commutative.
Scope: Calling the Complex Class From External Classes

Until now we've stored almost every program in a single file. This becomes unwieldy as programs grow large. It becomes impossible to manage when more than one person is working on a program. It also loses out on one of the key benefits of OOP, code reusability. As long as all the code for a program is stored in one file, you can't reuse code except by cut and paste, just like in a non-object oriented language.

There has been some code that hasn't resided in our source files. Remember all those import statements at the top of every file? What they do is pull in prewritten and precompiled code from various locations so we can use it in our programs. You can do the same thing with classes you write. However to do this you do need to be aware of several conventions and restrictions.
No file should contain more than one public class. This means that our Hello World, Goodbye World example is no longer valid because each of the classes was public.
All files should have the same name as their single public class followed by the extension ".java".
Source code files should be stored in the same directory as their compiled .class file. This is so the Java compiler can find the appropriate definitions and interfaces for a class when the class is referred to in a different file.
Source code and .class files should be in a directory that's part of the $CLASSPATH environment variable.
We'll demonstrate this by splitting the example of the previous sections into two separate files, each of which contains one class. Begin by creating a file that contains the Complex class. (Your complex file may be a little different depending on how you answered the exercises in the previous sections.) Save this file as Complex.java.

Next save the examples from the previous exercises in a separate file called ComplexExamples.java in the same directory as Complex.java. Now compile both files and run Complex Examples.java.
The Mandelbrot Set

The Mandelbrot set is a classic application of complex arithmetic. It is the example of a fractal set.

Here and in the future we are going to try to separate the mathematical definition of our data from its display on the screen. In fact we won't even add the screen display till the second iteration of the program.

Our data structure will be a two dimensional array, each element of which represents a fixed point in the complex plane. The array is defined by the value of the lower left point, the gap between points and the number of pixels in the x and y directions. Thus given that element (0,0) of the array matches the complex point (x0,y0), each point is separated by a value gap, we know that element i,j of the array represents the point (x0 + i*gap, y0 + j*gap) in the complex plane. Since we know this by position of the array element alone we dont' need to store this value in the array.

What will we store in each element of this array? We'll calculate a number to go there in the following fashion. Let z = 0 + 0i and let c be the position of that array element in complex space. calculate z = z*z + c and iterate as follows up to 200 times:
for (i=0; i <> z = z.Times(z) + c;
}

The Mandelbrot set is composed of those elements which, no matter how long we do this, never approach infinity. Since infinity can take a mighty long time to approach, it's fortunate that a fairly elementary theorem in complex variable theory guarantees that any number whose magnitude ever exceeds two in this iterative scheme will become as large as one might wish. (i.e. They asymptotically approach infinity.) Therefore once a number exceeds two we can break out of the loop and say definitively that this number is not in the Mandelbrot set.

Unfortunately there's no guarantee that just because an element doesn't reach 2 in two hundred iterations it might not reach two on the two hundredth and first iteration or the two thousandth or the two millionth. However most numbers that don't prove they're not in the Mandelbrot Set by the two hundredth iteration are reasonably likely to be in it.

Here's how the code will work. First we'll select the lower left hand corner of our rectangle in complex space, the size of the gap between the points and the number of points in each dimension. For a specific example we can choose the square bordered on the lower left by (-2,-2) and on the upper right by (2,2). To keep initial computations manageable we'll break this up into an array of 101 by 101 elements which implies a gap size of 0.05.

Once this array is created we'll loop through it and fill each element with a Boolean value, true if the element is probably in the Mandelbrot Set (doesn't pass two in two hundred iterations) and false if it's not (does pass two and thus go to infinity). Here's the code:

class MandelApp {

public static void main(String args[]) {

int xdim = 101;
int ydim = 101;
double xstart = -2.0;
double ystart = -2.0;
boolean Mandel[][] = new boolean[xdim][ydim];
double gap = 0.05;
int max_iterations = 200;
int i,j,k;
Complex z, c;

for (i=0; i <> for (j=0; j <>
c = new Complex(xstart + i*gap ,ystart + j*gap);
z = new Complex(0.0, 0.0);
k=0;
while (z.Magnitude() <> z = z.Times(z);
z = z.Plus(c);
k++;
}
if (z.Magnitude() <> Mandel[i][j] = true;
}
else Mandel[i][j] = false;
}
}
}
}
Drawing the Mandelbrot Set

To make this interesting we want to actually draw pictures of the Mandelbrot Set. To do this we'll move the actual calculation into a thread in an applet and then draw the results into a bitmap. Here's the code:
import java.applet.Applet;
import java.awt.*;

public class Mandelbrot extends Applet {

int xdim;
int ydim;
double xstart = -2.0;
double ystart = -1.25;
int Mandel[][];
double gap = 0.05;
int max_iterations = 256;

public void paint(Graphics g) {
int i,j,k;
Complex z, c;
xdim = size().width;
ydim = size().height;
gap = 2.5/ydim;
Mandel = new int[xdim][ydim];
for (i=0; i <> for (j=0; j <> c = new Complex(xstart + i*gap, ystart + j*gap);
z = new Complex(0.0, 0.0);
for (k = 0; z.Magnitude() <> z = z.Times(z);
z = z.Plus(c);
}
g.setColor(selectColor(k));
g.fillRect(i, j, 1, 1);
}
}
}
protected Color selectColor (int num_iterations) {
if (num_iterations > max_iterations) return Color.black;
else if (num_iterations > 9*max_iterations/10) return Color.darkGray;
else if (num_iterations > 8*max_iterations/10) return Color.gray;
else if (num_iterations > 7*max_iterations/10) return Color.magenta;
else if (num_iterations > 6*max_iterations/10) return Color.cyan;
else if (num_iterations > 5*max_iterations/10) return Color.blue;
else if (num_iterations > 4*max_iterations/10) return Color.green;
else if (num_iterations > 3*max_iterations/10) return Color.yellow;
else if (num_iterations > 2*max_iterations/10) return Color.orange;
else if (num_iterations > 1*max_iterations/10) return Color.red;
else return Color.white;
}

}

This program is minimal. It should really create an ImageProducer which draws the Mandelbrot set. There are also a lot of additions that could be made to the parameters to allow for zooming in on particular regions. In fact you could even implement this as a Canvas in an applet with various controls to select the area of interest.