Template Method and Iterator

Code in:JavaC#PythonJavaScript

In short: Template Method keeps the shared skeleton of an algorithm in a base class while subclasses fill in the steps; Iterator hands out elements one by one without showing how they are stored.

Problem

Two reports with the same skeleton

Accounting wants the orders in CSV, and the website wants the same ones in an HTML table. Cancelled orders don't go into the report. Someone wrote the CSV one, and then copied the method for HTML:

static String exportCsv(List<Order> orders) {
    List<String> lines = new ArrayList<>();
    lines.add("order,total");
    double sum = 0;
    for (Order order : orders) {
        if (order.cancelled()) {
            continue;
        }
        lines.add(order.id() + "," + String.format("%.2f", order.total()));
        sum += order.total();
    }
    lines.add("total," + String.format("%.2f", sum));
    return String.join("\n", lines);
}

static String exportHtml(List<Order> orders) {
    List<String> lines = new ArrayList<>();
    lines.add("<table>");
    lines.add("<tr><th>Order</th><th>Total</th></tr>");
    double sum = 0;
    for (Order order : orders) {
        lines.add("<tr><td>" + order.id() + "</td><td>" + String.format("%.2f", order.total()) + "</td></tr>");
        sum += order.total();
    }
    lines.add("<tr><td>Total</td><td>" + String.format("%.2f", sum) + "</td></tr>");
    lines.add("</table>");
    return String.join("\n", lines);
}

List<Order> orders = List.of(
        new Order(1001, 80.00, false),
        new Order(1002, 25.50, false),
        new Order(1003, 40.00, true));
System.out.println(exportCsv(orders));
System.out.println(exportHtml(orders));

Output

order,total
1001,80.00
1002,25.50
total,105.50
<table>
<tr><th>Order</th><th>Total</th></tr>
<tr><td>1001</td><td>80.00</td></tr>
<tr><td>1002</td><td>25.50</td></tr>
<tr><td>1003</td><td>40.00</td></tr>
<tr><td>Total</td><td>145.50</td></tr>
</table>

The two reports show a different total: the CSV says €105.50, and the HTML says €145.50. The rule "cancelled orders don't count" exists only in the first copy. Both copies do the same thing: they open, write a header, go over the orders, write the total and close. Only the lines they write are different. A third format will be a third copy, and the rule will have to be remembered in one more place.

The idea

Template Method: one skeleton, different steps

What doesn't change is the order of the steps and the rules between them: open, header, a row for each order except the cancelled ones, total, close. What changes is what each step looks like.

The skeleton goes into the base class Report, in the method export. At every place where the formats differ, it calls a step: header, row, footer. The subclass writes only the steps. A step that is optional (open and close, which CSV doesn't use) has an empty body in the base class and is called a hook.

This is the Template Method pattern. It has two roles:

• the base class with the skeleton: it decides the order and calls the steps;
• the subclasses: CsvReport and HtmlReport write the steps and call nothing themselves.

See it

The skeleton and the two reports

The skeleton is final: a subclass can't change it. The steps are protected and abstract, except the two hooks with an empty body:

abstract class Report {
    public final String export(List<Order> orders) {
        List<String> lines = new ArrayList<>();
        open(lines);
        header(lines);
        double sum = 0;
        for (Order order : orders) {
            if (order.cancelled()) {
                continue;
            }
            row(lines, order);
            sum += order.total();
        }
        footer(lines, sum);
        close(lines);
        return String.join("\n", lines);
    }

    protected void open(List<String> lines) {
    }

    protected abstract void header(List<String> lines);

    protected abstract void row(List<String> lines, Order order);

    protected abstract void footer(List<String> lines, double sum);

    protected void close(List<String> lines) {
    }
}

The two reports write only their lines. CsvReport doesn't write the hooks, so it uses the empty ones from the base class:

class CsvReport extends Report {
    @Override
    protected void header(List<String> lines) {
        lines.add("order,total");
    }

    @Override
    protected void row(List<String> lines, Order order) {
        lines.add(order.id() + "," + String.format("%.2f", order.total()));
    }

    @Override
    protected void footer(List<String> lines, double sum) {
        lines.add("total," + String.format("%.2f", sum));
    }
}

class HtmlReport extends Report {
    @Override
    protected void open(List<String> lines) {
        lines.add("<table>");
    }

    @Override
    protected void header(List<String> lines) {
        lines.add("<tr><th>Order</th><th>Total</th></tr>");
    }

    @Override
    protected void row(List<String> lines, Order order) {
        lines.add("<tr><td>" + order.id() + "</td><td>" + String.format("%.2f", order.total()) + "</td></tr>");
    }

    @Override
    protected void footer(List<String> lines, double sum) {
        lines.add("<tr><td>Total</td><td>" + String.format("%.2f", sum) + "</td></tr>");
    }

    @Override
    protected void close(List<String> lines) {
        lines.add("</table>");
    }
}

List<Order> orders = List.of(
        new Order(1001, 80.00, false),
        new Order(1002, 25.50, false),
        new Order(1003, 40.00, true));
System.out.println(new CsvReport().export(orders));
System.out.println(new HtmlReport().export(orders));

Output

order,total
1001,80.00
1002,25.50
total,105.50
<table>
<tr><th>Order</th><th>Total</th></tr>
<tr><td>1001</td><td>80.00</td></tr>
<tr><td>1002</td><td>25.50</td></tr>
<tr><td>Total</td><td>105.50</td></tr>
</table>

abstract class Report {
    public final String export(List<Order> orders) {
        List<String> lines = new ArrayList<>();
        open(lines);
        header(lines);
        double sum = 0;
        for (Order order : orders) {
            if (order.cancelled()) {
                continue;
            }
            row(lines, order);
            sum += order.total();
        }
        footer(lines, sum);
        close(lines);
        return String.join("\n", lines);
    }

    protected void open(List<String> lines) {
    }

    protected abstract void header(List<String> lines);

    protected abstract void row(List<String> lines, Order order);

    protected abstract void footer(List<String> lines, double sum);

    protected void close(List<String> lines) {
    }
}

Step by step, in words

1. new CsvReport().export(orders): the skeleton is in Report. It decides the order of the steps.
2. open: CsvReport doesn't write this step, so the empty body from Report runs. Nothing is added.
3. header: the skeleton calls the step, and CsvReport writes its line.
4. row for order 1001: the skeleton calls the step, and CsvReport writes its line.
5. row for order 1002: the skeleton calls the step, and CsvReport writes its line.
6. Order 1003 is cancelled: the skeleton itself skips it with continue. No report has to remember this rule.
7. footer: the skeleton calls the step, and CsvReport writes its line.
8. close: CsvReport doesn't write this step, so the empty body from Report runs. Nothing is added.
9. Now HtmlReport: the same skeleton, other steps.
10. open: the skeleton calls the step, and HtmlReport writes its line.
11. header: the skeleton calls the step, and HtmlReport writes its line.
12. row for order 1001: the skeleton calls the step, and HtmlReport writes its line.
13. row for order 1002: the skeleton calls the step, and HtmlReport writes its line.
14. Order 1003 is cancelled: the skeleton itself skips it with continue. No report has to remember this rule.
15. footer: the skeleton calls the step, and HtmlReport writes its line.
16. close: the skeleton calls the step, and HtmlReport writes its line.
17. Two reports, one skeleton. Both totals are €105.50, because the rule about cancelled orders is in one place.

The total is €105.50 in both reports: the rule about cancelled orders is in the skeleton, in one place.

See it

The skeleton is not touched

A subclass that tries to write its own export doesn't compile:

class QuickCsvReport extends CsvReport {
    @Override
    public String export(List<Order> orders) {
        return "order,total";
    }
}

Error

error: export(List<Order>) in QuickCsvReport cannot override export(List<Order>) in Report
    public String export(List<Order> orders) {
                  ^
  overridden method is final

That's what final does. Without it, the subclass quietly changes the skeleton, and the rule about cancelled orders disappears for that report only.

See it

Without inheritance: the steps as functions

The steps don't have to be methods of a subclass. The skeleton can take them as parameters: the header is text, and the row and the total are functions.

static String export(List<Order> orders, String header, Function<Order, String> row, Function<Double, String> footer) {
    List<String> lines = new ArrayList<>();
    lines.add(header);
    double sum = 0;
    for (Order order : orders) {
        if (order.cancelled()) {
            continue;
        }
        lines.add(row.apply(order));
        sum += order.total();
    }
    lines.add(footer.apply(sum));
    return String.join("\n", lines);
}

System.out.println(export(orders,
        "order,total",
        order -> order.id() + "," + String.format("%.2f", order.total()),
        sum -> "total," + String.format("%.2f", sum)));
System.out.println(export(orders,
        "<table>\n<tr><th>Order</th><th>Total</th></tr>",
        order -> "<tr><td>" + order.id() + "</td><td>" + String.format("%.2f", order.total()) + "</td></tr>",
        sum -> "<tr><td>Total</td><td>" + String.format("%.2f", sum) + "</td></tr>\n</table>"));

Output

order,total
1001,80.00
1002,25.50
total,105.50
<table>
<tr><th>Order</th><th>Total</th></tr>
<tr><td>1001</td><td>80.00</td></tr>
<tr><td>1002</td><td>25.50</td></tr>
<tr><td>Total</td><td>105.50</td></tr>
</table>

The skeleton is still in one place, and cancelled orders still don't count.

This is Strategy for every step: Function<Order, String> instead of an abstract method. It is enough for two or three short steps. A subclass pays off when there are many steps, they share fields, or some are optional, like the hooks open and close.

Problem

Everyone who wants the orders turns the pages

The orders are in a system that gives them in pages: two per request, because a request is slow. Here the source is a list in memory, and every load prints a line, so you can see when it happens:

class OrderSource {
    private final List<Order> orders;

    OrderSource(List<Order> orders) {
        this.orders = orders;
    }

    List<Order> fetchPage(int number) {
        System.out.println("loading page " + number);
        int from = Math.min((number - 1) * 2, orders.size());
        int to = Math.min(from + 2, orders.size());
        return orders.subList(from, to);
    }
}

The report, the email to customers and the export all want every order, and each one turns the pages itself:

int number = 1;
List<Order> page = source.fetchPage(number);
while (!page.isEmpty()) {
    for (Order order : page) {
        System.out.println(order.id());
    }
    number++;
    page = source.fetchPage(number);
}

Output

loading page 1
1001
1002
loading page 2
1003
1004
loading page 3
1005
loading page 4

The code that only wants "each order in turn" knows that there are pages, how they are counted, and that the end is an empty page. The same lines are in three files. When the system moves from page numbers to "a key for the next page", you change all three.

The idea

Iterator: going over things behind a cursor

The caller wants one thing: the next order, while there is one. How to get to it (a list, pages, a file, the network) is someone else's job.

That someone is the cursor: an object that remembers how far it got and answers the question "is there more?" by itself, loading a new page only when the previous one is over. The caller writes an ordinary for-each and doesn't know about the pages.

This is the Iterator pattern. It has two roles:

• the collection: the thing being gone over. It gives a cursor;
• the cursor: remembers the place and gives the next element.

This pattern is built into each of the four languages: for-each works with every object that gives a cursor. In Java the collection is an Iterable, and the cursor is an Iterator with hasNext() and next().

See it

The cursor that loads the pages

Java has no yield, so the cursor is written by hand. hasNext loads the next page only when the current one is used up:

class PageIterator implements Iterator<Order> {
    private final OrderSource source;
    private List<Order> page = List.of();
    private int number = 0;
    private int index = 0;
    private boolean done = false;

    PageIterator(OrderSource source) {
        this.source = source;
    }

    @Override
    public boolean hasNext() {
        if (index == page.size() && !done) {
            number++;
            page = source.fetchPage(number);
            index = 0;
            done = page.isEmpty();
        }
        return index < page.size();
    }

    @Override
    public Order next() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        return page.get(index++);
    }
}

Iterable is the collection: every for-each asks it for a new cursor.

class AllOrders implements Iterable<Order> {
    private final OrderSource source;

    AllOrders(OrderSource source) {
        this.source = source;
    }

    @Override
    public Iterator<Order> iterator() {
        return new PageIterator(source);
    }
}

The caller doesn't know about the pages:

for (Order order : new AllOrders(source)) {
    System.out.println(order.id());
}

Output

loading page 1
1001
1002
loading page 2
1003
1004
loading page 3
1005
loading page 4

class PageIterator implements Iterator<Order> {
    private final OrderSource source;
    private List<Order> page = List.of();
    private int number = 0;
    private int index = 0;
    private boolean done = false;

    PageIterator(OrderSource source) {
        this.source = source;
    }

    @Override
    public boolean hasNext() {
        if (index == page.size() && !done) {
            number++;
            page = source.fetchPage(number);
            index = 0;
            done = page.isEmpty();
        }
        return index < page.size();
    }

    @Override
    public Order next() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        return page.get(index++);
    }
}

for (Order order : new AllOrders(source)) {
    System.out.println(order.id());
}

Step by step, in words

1. The loop asks for the first order. Nothing has been loaded yet.
2. The cursor (PageIterator) has no page yet, so it loads page 1.
3. 1001: the first order from the page goes to the loop, and the loop prints it.
4. 1002: from the same page. Nothing is loaded.
5. The page is over. Only now does the cursor load page 2.
6. 1003 and 1004 from page 2.
7. The border again: page 3.
8. 1005: page 3 has only one order.
9. Page 4 is empty: there are no more orders.
10. The cursor says "no more", and the loop ends. The loop never saw a page.

The output is the same, and counting pages is in one place. When the system changes the way it gives pages, you change the cursor, and the three places that go over the orders aren't touched.

See it

What for-each does inside

for-each is a short way to write this loop with the cursor:

Iterator<Order> it = new AllOrders(source).iterator();
while (it.hasNext()) {
    Order order = it.next();
    System.out.println(order.id());
}

Output

loading page 1
1001
1002
loading page 2
1003
1004
loading page 3
1005
loading page 4

for (Order order : orders) calls orders.iterator() once, and then hasNext() and next() on every step. That's why it works with a list, with AllOrders, and with everything that is Iterable.

Try it

Predict the output

The loop stops after the third order. What does the program print?

int shown = 0;
for (Order order : new AllOrders(source)) {
    System.out.println(order.id());
    shown++;
    if (shown == 3) {
        break;
    }
}

Answer

loading page 1 / 1001 / 1002 / loading page 2 / 1003

loading page 1 / loading page 2 / loading page 3 / loading page 4 / 1001 / 1002 / 1003

loading page 1 / 1001 / 1002 / loading page 2 / 1003 / 1004

Check

Try it

Find the bug

The email to customers first says how many orders there are, and then lists them:

AllOrders orders = new AllOrders(new OrderSource(all));
int count = 0;
for (Order order : orders) {
    count++;
}
System.out.println("Orders: " + count);
for (Order order : orders) {
    System.out.println(order.id());
}

Output

loading page 1
loading page 2
loading page 3
loading page 4
Orders: 5
loading page 1
1001
1002
loading page 2
1003
1004
loading page 3
1005
loading page 4

The numbers come out, but every page is loaded twice, and the source is slow. Which line do you have to change?

Pick the line with the bug.

1AllOrders orders = new AllOrders(new OrderSource(all));2int count = 0;3for (Order order : orders) {4 count++;5}6System.out.println("Orders: " + count);7for (Order order : orders) {8 System.out.println(order.id());9}

Check

The idea

When you don't need them

Template Method has a cost: a base class and inheritance, and inheritance is a tie that is hard to undo. It isn't worth it when:

• there is one format. One method without steps is clearer;
• there are one or two steps. Pass them as lambdas, as in the card "Without inheritance";
• the subclasses want to change the order of the steps too. Then the skeleton isn't shared, and forcing it gives you steps with an if inside.

You don't need your own Iterator when the data is already in a list: it can already be gone over. You write your own when there is something behind it that isn't a collection in memory: pages, a file read line by line, a tree, or an endless sequence (invoice numbers).

Exercise

A report in Markdown

Solve the task in your editor.

Markdown. The documentation site wants the report as a Markdown table. Write MarkdownReport, which writes only the steps. The header is two lines. Report and the other reports are not touched. With the orders from the lesson:

Output

| Order | Total |
|---|---|
| 1001 | 80.00 |
| 1002 | 25.50 |
| **Total** | 105.50 |

More tasks

• Row numbers. The HTML report numbers its rows (<td>1</td>, <td>2</td>), and cancelled orders don't count. Where do you keep the counter: in the skeleton or in HtmlReport?
• The first N. Write a cursor that gives only the first N orders from another cursor. How many pages are loaded for the first three?
• Only the big ones. Go over the orders from the source and give only those over €30, again without the caller knowing about the pages.

Test

Check yourself

1. The shop wants the report in JSON too. What do you write with Template Method?

A new if in export for each formatA copy of the CSV method, and you change itA new subclass of Report that writes the steps; the skeleton isn't touched

2. Why does the open step have an empty body in the base class, while header is abstract?

open is optional (CSV doesn't use it), and a report without a header makes no senseAbstract steps are fasterNo reason, both could be abstract

3. A loop goes over the orders from the slow source and stops with break at the second one. How many pages are loaded?

All of themTwoOne

4. What does for-each call to go over something?

The indexes from 0 to size()The cursor of the object: it asks if there is a next one and takes itA method that returns the whole list at once

Check

Start the lesson over

Related lessons

• Builds on: Lambdas · record, switch and patterns · Design patterns · Strategy
• Tasks on this topic: Design patterns