### Programming Exercises

For Chapter 12

THIS PAGE CONTAINS programming exercises based on
material from Chapter 12 of this on-line
Java textbook. Each exercise has a link to a discussion of one possible solution of that
exercise.

**Exercise 12.1:**
In Section 12.2, I mentioned that a
`LinkedList` can be used as a queue by using the
`addLast()` and `removeFirst()` methods to enqueue
and dequeue items. But, if we are going to work with queues,
it's better to have a `Queue` class. The data for the
queue could still be represented as a `LinkedList`,
but the `LinkedList` object would be hidden as a
private instance variable in the `Queue` object.
Use this idea to write a generic `Queue` class for
representing queues of `Objects`. Also write a generic
`Stack` class that uses either a `LinkedList`
or an `ArrayList` to store its data. (Stacks and queues
were introduced in Section 11.3.)

**See the solution!**

**Exercise 12.2:**
In mathematics, several operations are defined on sets.
The union of two sets A and B is a set
that contains all the elements that are in A together with all the
elements that are in B. The intersection
of A and B is the set that contains elements that are in both
A and B. The difference of A and B
is the set that contains all the elements of A *except*
for those elements that are also in B.

Suppose that `A` and `B` are variables of type `set` in
Java. The mathematical operations on `A` and `B` can be computed
using methods from the `Set` interface. In particular:
The set `A.addAll(B)` is the *union* of `A` and `B`;
`A.retainAll(B)` is the *intersection* of `A` and `B`;
and `A.removeAll(B)` is the *difference* of `A` and `B`.
(These operations change the contents of the set `A`, while the mathematical
operations create a new set without changing `A`, but that difference
is not relevant to this exercise.)

For this exercise, you should write a program that can be used as
a "set calculator" for simple operations on sets of non-negative integers.
(Negative integers are not allowed.) A set of such
integers will be represented as a list of integers, separated by commas and, optionally, spaces
and enclosed in square brackets. For example: `[1,2,3]`
or `[17, 42, 9, 53,108]`. The characters
`+`, `*`, and `-` will be used for the union,
intersection, and difference operations. The user of the program will
type in lines of input containing two sets, separated by an operator.
The program should perform the operation and print the resulting set.
Here are some examples:

Input Output
------------------------- -------------------
[1, 2, 3] + [3, 5, 7] [1, 2, 3, 5, 7]
[10,9,8,7] * [2,4,6,8] [8]
[ 5, 10, 15, 20 ] - [ 0, 10, 20 ] [5, 15]

To represent sets of non-negative integers, use `TreeSets` containing
objects belonging to the wrapper class `Integer`. Read the user's
input, create two `TreeSets`, and use the appropriate `TreeSet`
method to perform the requested operation on the two sets.
Your program should be able to read and process any number of lines of
input. If a line contains a syntax error, your program should
not crash. It should report the error and move on to the next
line of input. (Note: To print out a `Set`, `A`,
of `Integers`, you can just say `System.out.println(A)`.
I've chosen the syntax for sets to be the same as that used by the
system for outputting a set.)

**See the solution!**

**Exercise 12.3:**
The fact that Java has a `HashMap` class means that no Java
programmer has to write an implementation of hash tables from
scratch -- unless, of course, you are a computer science student.

Write an implementation of hash tables from scratch. Define the
following methods: `get(key)`, `put(key,value)`,
`remove(key)`, `containsKey(key)`, and `size()`. Do not
use *any* of Java's generic data structures. Assume that both
keys and values are of type `Object`, just as for `HashMaps`.
Every `Object` has a hash code, so at least you don't have to
define your own hash functions. Also, you do *not* have to
worry about increasing the size of the table when it becomes too full.

You should also write a short program to test your solution.

**See the solution!**

**Exercise 12.4:**
A predicate is a boolean-valued function
with one parameter. Some languages use predicates in
generic programming. Java doesn't, but this exercise looks
at how predicates might work in Java.

In Java, we could use "predicate objects" by defining an
interface:

public interface Predicate {
public boolean test(Object obj);
}

The idea is that an object that implements this interface knows
how to "test" objects in some way. Define a class
`Predicates` that contains the following generic methods
for working with predicate objects:

public static void remove(Collection coll, Predicate pred)
// Remove every object, obj, from coll for which
// pred.test(obj) is true.
public static void retain(Collection coll, Predicate pred)
// Remove every object, obj, from coll for which
// pred.test(obj) is false. (That is, retain the
// objects for which the predicate is true.)
public static List collect(Collection coll, Predicate pred)
// Return a List that contains all the objects, obj,
// from the collection, coll, such that pred.test(obj)
// is true.
public static int find(ArrayList list, Predicate pred)
// Return the index of the first item in list
// for which the predicate is true, if any.
// If there is no such item, return -1.

(In C++, methods similar to these are included as a standard
part of the generic programming framework.)

**See the solution!**

**Exercise 12.5:**
One of the examples in Section 12.4 concerns the
problem of making an index for a book. A related problem is making
a concordance for a document. A
concordance lists every word that occurs in the document, and for each
word it gives the line number of every line in the document where
the word occurs. All the subroutines for creating an index
that were presented in Section 12.4 can also be used to create
a concordance. The only real difference is that the integers
in a concordance are line numbers rather than page numbers.

Write a program that can create a concordance. The document should
be read from an input file, and the concordance data should be written
to an output file. The names of the input file and output file should
be specified as command line arguments when the program is run.
You can use the indexing subroutines from Section 12.4, modified to
write the data to a file instead of to `System.out`. You
will also need to make the subroutines `static`. If you need
some help with using files and command-line arguments, you can find an
example in the
sample program WordCount.java,
which was also discussed in Section 12.4.

As you read the file, you want to take each word that you encounter
and add it to the concordance along with the current line number.
Your program will need to keep track of the line number. The end of each line
in the file is marked by the newline character, '\n'. Every time you encounter
this character, add one to the line number. One warning: The method
`in.eof()`, which is defined in the `TextReader`, skips over
end-of-lines. Since you don't want to skip end-of-line characters, you
should not use `in.eof()` -- at least, you should not use it
in the same way that it is used in the program `WordCount.java`.
The function `in.peek()` from the `TextReader` class returns
the nul character '\0' at the end of the file. Use this function
instead of `in.eof()` to test for end-of-file.

Because it is so common, don't include the word "the" in your
concordance. Also, do not include words that have length less than 3.

**See the solution!**

**Exercise 12.6:**
The sample program SimpleParser5.java
from Section 12.4 can handle expressions that contain
variables, numbers, operators, and parentheses. Extend this program so that
it can also handle the standard mathematical functions `sin`, `cos`,
`tan`, `abs`, `sqrt`, and `log`. For example, the program should
be able to evaluate an expression such as `sin(3*x-7)+log(sqrt(y))`,
assuming that the variables `x` and `y` have been given values.

In the original program, a symbol table holds a value for each variable that
has been defined. In your program, you should add another type of symbol to
the table to represent standard functions. You can use objects belonging
to the following class:

class StandardFunction {
// An object of this class represents
// one of the standard functions.
static final int SIN = 0, COS = 1, // Code numbers for each
TAN = 2, ABS = 3, // of the functions.
SQRT = 4, LOG = 5;
int functionCode; // Tells which function this is.
// The value is one of the above codes.
StandardFunction(int code) {
// Constructor creates the standard function specified
// by the given code, which should be one of the
// above code numbers.
functionCode = code;
}
double evaluate(double x) {
// Finds the value of this function for the
// specified parameter value, x.
switch(functionCode) {
case SIN:
return Math.sin(x);
case COS:
return Math.cos(x);
case TAN:
return Math.tan(x);
case ABS:
return Math.abs(x);
case SQRT:
return Math.sqrt(x);
default:
return Math.log(x);
}
}
} // end class StandardFunction

Add a symbol to the symbol table to represent each function.
The key is the name of the function and the value is an object
of type `StandardFunction` that represents the function.
For example:

symbolTable.put("sin", new StandardFunction(StandardFunction.SIN));

In your parser, when you encounter a word, you have to be able to
tell whether it's a variable or a standard function. Look up the
word in the symbol table. If the associated value is non-null
and is of type `Double`, then the word is a variable.
If it is of type `StandardFunction`, then
the word is a function. Remember that you can test the type
of an object using the `instanceof` operator.
For example: `if (obj instanceof Double)`

**See the solution!**