Introduction
本次作业是要实现一个StringList，具体是要求练习掌握Interface的编程方法。程序的主干代码已经给出，按照文档补充缺失的部分即可。
Overview
This is a short set of problems using interfaces. You will implement a class
called StringList that uses interfaces for performing various kinds of
processing on streams of text, as well as some sample classes that implement
those interfaces. In all, you’ll implement six classes:
StringList.java
NonCommentLineSelector.java
CommentRemover.java
LetterCollecter.java
LineNumberer.java
LocCounter.java
Note that the file StringListTest.java, found in the default package, will not
compile until you have created stubs for the six required classes.
None of the code is very complex; the purpose is just to get you thinking
about interfaces a bit.
A StringList (not surprisingly) represents a list of strings. (Most likely, in
fact, you’ll use an instance variable of type ArrayList to store the strings
themselves.) The interesting part is in the operations map, filter, and
reduce. These are based on the four interfaces defined in the package api:
Combiner, IntCombiner, Selector, and Transformation. They are all very simple
and have only one method each. You can take a look at the javadoc or sample
code for more details.
public StringList map(Transformation t)
Returns a new StringList obtained by invoking the given Transformation’s apply
method to each string in this StringList. The apply method just takes a string
and returns a (possibly different) string.
public StringList filter(Selector selector)
Returns a new StringList containing only the elements of this StringList for
which the Selector’s select method returns true. The select method just takes
a string and returns true or false.
public String reduce(Combiner combiner, String initialValue)
Returns a string resulting from a reduction operation using the given Combiner
and the given initial value. A Combiner has one method, combine, that takes
two strings and returns a string. The idea of a “reduction” is to initialize
an accumulator variable with the given initial value, and then to iterate over
the list, replacing the accumulator value with the result of combining it with
the next item in the list.
public int reduce(IntCombiner combiner, int initialValue)
Returns an integer resulting from a reduction operation using the given
IntCombiner and the given initial value. Similar to the reduce operation
above, but the accumulated value is an int.
The meaning of the reduce operation may not be obvious. The next section of
this document includes a detailed explanation and examples. You should also
look at the example StringListTest.java. found in the default package of the
sample code.
In addition to the StringList class, you’ll implement some examples of classes
that implement the interfaces in the api package so you can try things out.
These are:
public class NonCommentLineSelector implements Selector
The select method returns true if the given string does not have “//“ as its
first nonwhitespace characters.
public class CommentRemover implements Transformation
The apply method returns a new string in which any text following “//“ is
removed.
public class LineNumberer implements Transformation
The apply method returns a new string with a line number left-justified in the
first five spaces at the beginning of each line. When the LineNumberer is
first constructed, the line number starts at 1; thereafter the number
increases by 1 in each call to apply.
Tip: to format a number num within a 5-space string, use
String.format(“%-5d”, num)
public class LocCounter implements IntCombiner
Given an integer n and a string, the combine method returns n if the string is
a comment line, a blank line, or a line whose only text, other than an end-of-
line comment, is a single curly brace; otherwise the method returns n + 1.
(Using a LocCounter in the reduce method has the general effect of counting
“lines of code” that are actual program statements.)
public class LetterCollector implements Combiner
Given two strings first and second, appends onto first all characters in
second that don’t already occur in first. (Using a LetterCollector in the
reduce method returns a string in which each character occurring in the
strings appears exactly once.) Not case sensitive.
Detailed example: the idea of map, filter, and reduce
Here is a related example using integer arrays to illustrate the main idea of
the map, filter, and reduce operations. Suppose we have a loop that iterates
over an int array and returns a new array, after applying some operation to
each number. For example, here is a loop that multiplies each value in the
array by 2:
public int[] multiplyEverythingByTwo(int[] arr) {
int[] result = new int[arr.length];
for (int i = 0; i < arr.length; i += 1) {
result[i] = 2 * arr[i];
}
return result;
}
—|—
And here is a loop that rounds each value to the nearest multiple of ten:
public int[] roundEverythingToNearestTen(int[] arr) {
int[] result = new int[arr.length];
for (int i = 0; i < arr.length; i += 1) {
int tens = arr[i] / 10;
int rem = arr[i] % 10;
if (rem < 5) {
result[i] = tens;
} else {
// round up
result[i] = tens + 1;
}
}
return result;
}
—|—
The basic structure of both methods is exactly the same: for each number in
the array, get a new number by applying some transformation. It seems like we
should not need two separate methods that are so similar. The method that
iterates over the array does not care what the transformation is, it just
needs to apply it to every element.
We can use an interface to represent the transformation:
interface IntTransformation {
int apply(int num);
}
—|—
Then a general method that applies the transformation to each element of the
array is easy:
public int[] applyTransformation(int[] arr, IntTransformation t) {
int[] result = new int[arr.length];
for (int i = 0; i < arr.length; i += 1) {
result[i] = t.apply(arr[i]);
}
return result;
}
—|—
Now if we want to multiply each element by 2, we just define a class
implementing the IntTransformation interface whose apply method does so:
class MultiplyByTwo implements IntTransformation {
@Override
public int apply(int num) {
return 2 * num;
}
}
—|—
Then call applyTransformation on an array myArray using a MultiplyByTwo
object:
int[] answer = applyTransformation(myArray, new MultiplyByTwo());
—|—
An operation like the applyTransformation is referred to as a map operation.
Some other common patterns are filter and reduce. A filter operation would be
something like “return an array containing just the even numbers”. It is based
on a method that takes an integer and returns a boolean - if the method
returns true, the value is included in the result.
A reduce operation is a bit more interesting. To see what it means, think
about at the operation of adding up the elements:
public int sum(int[] arr) {
int total = 0;
for (int i = 0; i < arr.length; i += 1) {
total = total + arr[i];
}
return total;
}
—|—
and then look at the similar code for finding the maximum:
public int findMax(int[] arr) {
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i += 1) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
—|—
What is happening in both cases is that we start with a specific initial value
(like the total in the sum() method), and then go through the array, updating
that value by combining it with the first element in the array, then the
second element, and so on. In the case of the sum method, we “combine” two
values using addition. In the case of the findMax method, we “combine” two
values by taking the largest one.
As we saw for int-to-int transformations, we can define a simple interface
representing the “combine” operation:
interface Combiner {
int combine(int first, int second);
}
—|—
Then the general method for performing any such operation is:
public int reduce(int[] arr, Combiner combiner, int initialValue) {
int result = initialValue;
for (int i = 0; i < arr.length; i += 1) {
result = combiner.combine(result, arr[i]);
}
return result;
}
—|—
This type of operation is often called “reduce,” since it take a collection of
values and “reduces” them to a single value such as a sum or maximum. Note
that we generally have to provide the desired default or initial value.
The SpecChecker
There is a simple SpecChecker that will check basic spec conformance of class
and method declarations. A second SpecChecker will be posted by Tuesday, April
11. The second one will perform some functional tests and create a zip file.
In the meantime think about how you could test your code yourself. Take a look
at StringListTest.java in the default package of the sample code for some
ideas. Notice that it is easy to write simple test cases for a class such as
(say) CommentRemover, even if you do not have StringList implemented. For
example:
CommentRemover c = new CommentRemover();
String s = c.apply(“before comment// after comment”);
System.out.println(s); // expected “before comment”
—|—
Documentation and style
Since this is a miniassignment, the grading is automated and in most cases we
will not be reading your code. Therefore, there are no specific documentation
and style requirements.
