Loop Patterns (Java Edition)

.jpg

In a presentation about teaching new Java features, I casually mentioned that my textbooks for beginning students include a list of common loop patterns (counting matches, maximum, and so on). After all, students can't realistically be expected to invent them on the spot each time they are needed. Attendees asked me about that list. Here it is.

Beginning students often struggle with writing useful programs. So much of the instruction covers the syntax. Think of loops. Students are taught about while loops, for loops, and do/while loops. When faced with an actual problem to solve, they then ponder which of those loop types they should employ. That's not wrong, but it doesn't get them very far. Which should not be surprising. Imagine trying to speak a foreign language after being taught about nouns, verbs, adjectives, subjects and objects.

That's not how foreign language teaching works these days. Students get plenty of patterns. How to introduce yourself. How to ask for directions. How to express a desire. Sure, the grammar elements are taught as well. But always in the context of getting the job done. That way, when asked “How are you”, you don't have to reinvent the response from first principles.

When I teach loops, of course I teach the syntax. Briefly. And then I move on to the most common loop types. I don't assume that students can discover them on their own. I tediously dissect them. Twice. In the chapter on loops. And again in the chapter on arrays. That way, when a project calls for the maximum value, students hopefully have the algorithm at their fingertips instead of responding with: “By golly, I think I need a for loop.” That's what I casually mentioned in my presentation.

The exact list depends on the course/book/language, but here is a baker's dozen of examples in Java.

In a beginning course, I don't actually spend any effort on the “With API” column. In Java, C++, and Python, the API is rather higgedly-piggedly and not really helpful to students. They should learn the basic algorithms. Just like you learn how to introduce yourself, how to ask for directions, and how to express a desire, when you learn a foreign language.

What's with those toes, by the way? I have such an image next to the “element separators” algorithm in my textbooks. With a caption “To print five elements, you need four separators.”. Once you've seen it, it's very hard to un-see.

In the table below, strings is an ArrayList<String>, in is a Scanner, and values is a partially filled int[]. To try out the code in JShell, start with these definitions:

var strings = new ArrayList<String>(List.of("Mary ate a guava in Java surrounded by lava".split(" ")));
var in = new Scanner("2 3 5 7 11 13 17 19 23"); // Repeat each time the contents is consumed
Loop Patterns
Pattern Pseudocode Example With API
Sum
sum = 0
for each element e
   sum = sum + measure of e
int sum = 0;
for (String e : strings) {
   sum = sum + e.length();
}
int sum = strings.stream()
   .mapToInt(s -> s.length())
   .sum();
Average
sum = 0
for each element e
   sum = sum + measure of e
if number of elements > 0
   average = sum / number of elements
else
   average = 0
int sum = 0;
int count = 0;
while (in.hasNextInt()) {
   int e = in.nextInt();
   sum = sum + e;
   count++;
}
double average = 0;
if (count > 0) {
   average = sum * 1.0 / count;
}

double average = in.tokens()
   .mapToInt(t -> Integer.parseInt(t))
   .average()
   .orElse(0)
Counting matches
count = 0
for each element e
   if e matches
      count++
int count = 0;
for(String e : strings) {
   if (e.contains("ava")) {
      count++;
   }
}
int count = (int) strings.stream()
   .filter(e -> e.contains("ava"))
   .count();
Finding the first match (and optionally its position)
found = false
position = 0
while (not found and there are more elements) {
   e = next element
   if e matches
      found = true
      match = e
   else
      position++
}
boolean found = false;
int position = 0;
String match = null;
while (!found && position < strings.size()) {
   String e = strings.get(position);
   if (e.contains("ava")) {
      found = true;
      match = e;
   } else {
      position++;
   }
}
String match = strings.stream()
   .filter(s -> s.contains("ava"))
   .findFirst()
   .orElse(null);
int position = IntStream.range(0, strings.size())
   .filter(i -> strings.get(i).contains("ava"))
   .findFirst()
   .orElse(-1);

To find the position of an element, use

int position = strings.indexOf("Java");
Finding all matches
result = empty list
for each element e
   if e matches
      add e to result
var result = new ArrayList<String>();
for (String e : strings) {
   if (e.contains("ava")) {
      result.add(e);
   }
}
List<String> matches = strings.stream()
   .filter(e -> e.contains("ava"))
   .toList();
Maximum
largest = first element
for all remaining elements e
   if measure of e > measure of largest
      largest = e
String largest = strings.get(0);
for (int i = 1; i < strings.size(); i++) {
   String e = strings.get(i);
   if (e.length() > largest.length()) {
      largest = e;
   }
}
String largest = strings.stream()
   .max(Comparator.comparing(String::length))
   .get()
Position of the Maximum
largestPosition = 0
for i = 1 to number of elements - 1
   if measure of element at i > measure of
         element at largestPosition
      largestPosition = i
int largestPosition = 0;
for (int i = 1; i < strings.size(); i++) {
   String e = strings.get(i);
   if (strings.get(i).length() > strings.get(
         largestPosition).length()) {
      largestPosition = i;
   }
}
int largestPosition = IntStream.range(0, strings.size())
   .boxed()
   .max((i, j) -> Integer.compare(strings.get(i).length(),
      strings.get(j).length()))
   .get();
Comparing adjacent values
current = first element
for all remaining elements e
  previous = current
  current = e
  Compare previous and current
String current = in.next();
while (in.hasNext()) {
   String previous = current;
   current = in.next();
   if (current.equals(previous)) { 
      System.out.println("Repeated: " + current); 
   }
}
N/A
Element separators
first = true
for each element e
   if first
      first = false
   else
      Append separator
   Append e
String result = "";
boolean first = true;
for (String e : strings) {
   if (first) { first = false; }
   else { result += " | "; }
   result += e;
}
String result = String.join(" | ", strings)
Filling
for i from 0 to number of elements - 1
  element at i = Compute value from i
int[] values = new int[100];
for (int i = 0; i < values.length; i++) {
   values[i] = i * i;
}
currentSize = 100;
int[] values = IntStream.range(0, n)
   .map(i -> i * i).toArray()
Removing the element at a given position
for i from position + 1 to number of elements - 1
   element at i - 1 = element at i
Decrement number of elements
int position = 10;
for (int i = position + 1; i < currentSize; i++) { 
   values[i - 1] = values[i]; 
}
currentSize--;
Partially filled array:
System.arraycopy(values, position + 1, values, position,
   currentSize - position - 1);
currentSize--;
List:
strings.remove(i);
Inserting an element at a given position
if there is room for another element
   Increment number of elements
   for i from number of elements - 1 to position + 1
      element at i = element at i - 1
   element at position = new element
if (currentSize < values.length) {
   currentSize++;
   for (int i = currentSize - 1; i > position; i--) { 
      values[i] = values[i - 1];
   }
   values[position] = newElement;
}
Partially filled array:
if (currentSize < values.length) {
   currentSize++;
   System.arraycopy(values, position, values, position + 1,
      currentSize - position - 1);
   values[position] = newElement;
}
List:
strings.add(i, newElement)
Reading input into an array or list
for each input e
   if there is room in the target
      append e to the target
int currentSize = 0;
while (in.hasNextInt() && currentSize < values.length) { 
   values[currentSize] = in.nextInt();
   currentSize++;
}
int[] values = in.tokens()
   .mapToInt(Integer::parseInt)
   .toArray();

Comments powered by Talkyard.