Iterator and Visitor

The chain walked a request through an array in sequence: the traversal was flat, one-directional, and the order lived in the array itself. On the route side, the structure to traverse is not flat. A route is a tree of handoff points: hub, regional depot, distribution branch, delivery point. Five independent operations run over this tree — total distance, longest wait, capacity check, label list, total cost — and each operation traverses the tree with its own traversal code.

Two patterns target two separate halves of this situation. Iterator separates traversal from the operation: how the tree is walked is defined in one place, and operations deal only with the nodes they receive. Visitor separates the behavior that varies by node type from the operation: each operation carries one method per type, and the choice of type is made in a single place. The numbers to measure are the number of sites carrying traversal code, the number of files edited when traversal order changes, and the number of errors that surface when a new node type is added.

The Tree and Five Operations

mkdir -p traversal iterator visitor

// tree.mjs — route tree: hub, regional depots, distribution branches, delivery points
const node = (type, name, distance, wait, capacity, children = []) => ({ type, name, distance, wait, capacity, children });

export const ROUTE = node("hub", "MRK", 0, 0, 5000, [
  node("depot", "DPO-A", 120, 4, 1800, [
    node("branch", "SB-A1", 35, 2, 400, [node("point", "NK-A1a", 6, 1, 0), node("point", "NK-A1b", 9, 3, 0)]),
    node("branch", "SB-A2", 48, 5, 900, [node("point", "NK-A2a", 4, 2, 0)]),
  ]),
  node("depot", "DPO-B", 260, 7, 300, [node("branch", "SB-B1", 52, 6, 650, [node("point", "NK-B1a", 11, 4, 0)])]),
]);

In the first version, the five operations carry five separate recursions. Each body knows both what to compute and how to traverse the tree.

// traversal/operations.mjs — five operations, five separate traversals
export function totalDistance(node) {
  let t = node.distance;
  for (const c of node.children) t += totalDistance(c);
  return t;
}

export function longestWait(node) {
  let e = node.wait;
  for (const c of node.children) e = Math.max(e, longestWait(c));
  return e;
}

export function tightCapacity(node) {
  let count = node.type !== "point" && node.capacity < 500 ? 1 : 0;
  for (const c of node.children) count += tightCapacity(c);
  return count;
}

export function labels(node) {
  const prefix = node.type === "hub" ? "H" : node.type === "depot" ? "D" : node.type === "branch" ? "B" : "P";
  let list = [`${prefix}:${node.name}`];
  for (const c of node.children) list = list.concat(labels(c));
  return list;
}

export function cost(node) {
  const factor = node.type === "depot" ? 8 : node.type === "branch" ? 12 : node.type === "point" ? 20 : 0;
  let t = node.distance * factor;
  for (const c of node.children) t += cost(c);
  return t;
}

Separating the Traversal

In the iterator version, traversal lives in a single generator. The operations no longer see the tree; they see a sequence of nodes.

// iterator/traverse.mjs — traversal code lives in one place, yields nodes in depth-first order
export function* traverse(node) {
  yield node;
  for (const c of node.children) yield* traverse(c);
}

// iterator/operations.mjs — five operations, none of them carry traversal code
import { traverse } from "./traverse.mjs";

export function totalDistance(root) {
  let t = 0;
  for (const n of traverse(root)) t += n.distance;
  return t;
}

export function longestWait(root) {
  let e = 0;
  for (const n of traverse(root)) e = Math.max(e, n.wait);
  return e;
}

export function tightCapacity(root) {
  let count = 0;
  for (const n of traverse(root)) {
    switch (n.type) {
      case "depot":
      case "branch":
        count += n.capacity < 500 ? 1 : 0;
        break;
      default:
        break;
    }
  }
  return count;
}

export function labels(root) {
  const list = [];
  for (const n of traverse(root)) {
    switch (n.type) {
      case "hub":
        list.push(`H:${n.name}`);
        break;
      case "depot":
        list.push(`D:${n.name}`);
        break;
      case "branch":
        list.push(`B:${n.name}`);
        break;
      default:
        list.push(`P:${n.name}`);
        break;
    }
  }
  return list;
}

export function cost(root) {
  let t = 0;
  for (const n of traverse(root)) {
    switch (n.type) {
      case "depot":
        t += n.distance * 8;
        break;
      case "branch":
        t += n.distance * 12;
        break;
      case "point":
        t += n.distance * 20;
        break;
      default:
        break;
    }
  }
  return t;
}

Traversal disappeared, but type discrimination is still there: three operations still branch on node.type. Visitor targets these three. The choice of type is moved to a single place, and a missing type is not silently skipped.

// visitor/accept.mjs — the node picks its own type's method, throws if it is missing
export function accept(node, visitor) {
  const method = visitor[node.type];
  if (method === undefined) throw new TypeError(`no visitor method for ${node.type}`);
  return method(node);
}

// visitor/visitors.mjs — each operation carries one method per node type
export const cost = {
  hub: () => 0,
  depot: (n) => n.distance * 8,
  branch: (n) => n.distance * 12,
  point: (n) => n.distance * 20,
};

export const label = {
  hub: (n) => `H:${n.name}`,
  depot: (n) => `D:${n.name}`,
  branch: (n) => `B:${n.name}`,
  point: (n) => `P:${n.name}`,
};

export const tightness = {
  hub: () => 0,
  depot: (n) => (n.capacity < 500 ? 1 : 0),
  branch: (n) => (n.capacity < 500 ? 1 : 0),
  point: () => 0,
};

Equality of the Three Versions

// run.mjs — verifies all three versions produce the same result on the same tree
import { ROUTE } from "./tree.mjs";
import * as traversal from "./traversal/operations.mjs";
import * as iterator from "./iterator/operations.mjs";
import { traverse } from "./iterator/traverse.mjs";
import { accept } from "./visitor/accept.mjs";
import { tightness, label, cost } from "./visitor/visitors.mjs";

const visitAll = (v, combine, start) => {
  let result = start;
  for (const n of traverse(ROUTE)) result = combine(result, accept(n, v));
  return result;
};

const results = {
  traversal: [
    traversal.totalDistance(ROUTE),
    traversal.longestWait(ROUTE),
    traversal.tightCapacity(ROUTE),
    traversal.labels(ROUTE).join(""),
    traversal.cost(ROUTE),
  ],
  iterator: [
    iterator.totalDistance(ROUTE),
    iterator.longestWait(ROUTE),
    iterator.tightCapacity(ROUTE),
    iterator.labels(ROUTE).join(""),
    iterator.cost(ROUTE),
  ],
};
results.visitor = [
  results.iterator[0],
  results.iterator[1],
  visitAll(tightness, (a, b) => a + b, 0),
  visitAll(label, (a, b) => a + b, ""),
  visitAll(cost, (a, b) => a + b, 0),
];

for (const [name, r] of Object.entries(results)) {
  console.log(`${name.padEnd(11)} distance=${r[0]} wait=${r[1]} tight=${r[2]} cost=${r[4]}`);
}
console.log(`labels: ${results.traversal[3]}`);
const distinct = new Set(Object.values(results).map((r) => r.join("|")));
console.log(`distinct result sets = ${distinct.size}`);

traversal   distance=545 wait=7 tight=2 cost=5260
iterator    distance=545 wait=7 tight=2 cost=5260
visitor     distance=545 wait=7 tight=2 cost=5260
labels: H:MRKD:DPO-AB:SB-A1P:NK-A1aP:NK-A1bB:SB-A2P:NK-A2aD:DPO-BB:SB-B1P:NK-B1a
distinct result sets = 1

The distinct result set is one: the three versions produce the same five values, so the comparison is valid.

Traversal Code and Type Discrimination

// count.mjs — bodies carrying traversal code vs. locations that discriminate by type
import { readFileSync, readdirSync } from "node:fs";

const occurrences = (text, pattern) => (text.match(pattern) ?? []).length;

for (const dir of ["traversal", "iterator", "visitor"]) {
  let traversalSites = 0;
  let typeSites = 0;
  for (const f of readdirSync(dir).sort()) {
    const text = readFileSync(`${dir}/${f}`, "utf8").replace(/^\/\/.*$/gm, "");
    traversalSites += occurrences(text, /\.children\b/g);
    typeSites += occurrences(text, /\.type\b|\bswitch\b/g);
  }
  console.log(`${dir.padEnd(11)} sites carrying traversal code=${traversalSites}  sites discriminating by type=${typeSites}`);
}

traversal   sites carrying traversal code=5  sites discriminating by type=7
iterator    sites carrying traversal code=1  sites discriminating by type=6
visitor     sites carrying traversal code=0  sites discriminating by type=2

Five, one, zero. Iterator brought traversal down from five sites to one but did not touch type discrimination: seven sites down to six. Visitor brought type discrimination down to two, and both sites are in the same file. The two patterns clean up two separate axes; neither substitutes for the other.

When Traversal Order Changes

The label list now needs to come out in zone order: nodes at the same level grouped together, which is breadth-first search. In the iterator version, this is a single-file change.

// order.mjs — traversal order switches to breadth-first; only traverse.mjs is edited
import { cpSync, readdirSync, writeFileSync } from "node:fs";
import { ROUTE } from "./tree.mjs";

cpSync("iterator", "iterator-breadth-first", { recursive: true });
writeFileSync(
  "iterator-breadth-first/traverse.mjs",
  `// iterator/traverse.mjs — traversal code lives in one place, yields nodes in breadth-first order
export function* traverse(node) {
  const queue = [node];
  while (queue.length > 0) {
    const n = queue.shift();
    yield n;
    for (const c of n.children) queue.push(c);
  }
}
`,
);

const before = await import("./iterator/operations.mjs");
const after = await import("./iterator-breadth-first/operations.mjs");
console.log(`edited file: iterator=1 (out of ${readdirSync("iterator").length} files)  traversal=5 bodies`);
for (const [name, m] of [["depth-first", before], ["breadth-first", after]]) {
  console.log(`${name.padEnd(14)} distance=${m.totalDistance(ROUTE)} wait=${m.longestWait(ROUTE)} tight=${m.tightCapacity(ROUTE)} cost=${m.cost(ROUTE)}`);
  console.log(`${name.padEnd(14)} labels=${m.labels(ROUTE).join("")}`);
}

edited file: iterator=1 (out of 2 files)  traversal=5 bodies
depth-first    distance=545 wait=7 tight=2 cost=5260
depth-first    labels=H:MRKD:DPO-AB:SB-A1P:NK-A1aP:NK-A1bB:SB-A2P:NK-A2aD:DPO-BB:SB-B1P:NK-B1a
breadth-first  distance=545 wait=7 tight=2 cost=5260
breadth-first  labels=H:MRKD:DPO-AD:DPO-BB:SB-A1B:SB-A2B:SB-B1P:NK-A1aP:NK-A1bP:NK-A2aP:NK-B1a

One file against five bodies. The four operations that do not depend on order kept their result; the label list, which does depend on order, produced the new layout. Making the same change in the traversal version means converting five recursions to a queue loop one by one, because five bodies know the order.

When a New Node Type Is Added

A customs handoff node is added to the tree. The expected behavior is clear: the customs node’s cost coefficient is 15, its label prefix is C, and its capacity check works like the other handoff points.

// new-node-type.mjs — a customs handoff node is added to the tree; the two versions' reactions are counted
import { ROUTE } from "./tree.mjs";
import * as iterator from "./iterator/operations.mjs";
import { traverse } from "./iterator/traverse.mjs";
import { accept } from "./visitor/accept.mjs";
import { tightness, label, cost } from "./visitor/visitors.mjs";

const CUSTOMS = { type: "customs", name: "GMR", distance: 40, wait: 8, capacity: 200, children: [] };
ROUTE.children[1].children.push(CUSTOMS);

const EXPECTED = { tight: 3, cost: 5860, customsLabel: "C:GMR" };

const visitAll = (v, combine, start) => {
  let result = start;
  for (const n of traverse(ROUTE)) result = combine(result, accept(n, v));
  return result;
};

let silentlyWrong = 0;
const it = { tight: iterator.tightCapacity(ROUTE), cost: iterator.cost(ROUTE), label: iterator.labels(ROUTE).join("") };
if (it.tight !== EXPECTED.tight) silentlyWrong += 1;
if (it.cost !== EXPECTED.cost) silentlyWrong += 1;
if (it.label.includes(EXPECTED.customsLabel) === false) silentlyWrong += 1;
console.log(`iterator+switch  tight=${it.tight} (expected ${EXPECTED.tight})  cost=${it.cost} (expected ${EXPECTED.cost})  customs label=${it.label.match(/[A-Z]:GMR/)[0]}`);

let threw = 0;
for (const [name, v, combine, start] of [["tightness", tightness, (a, b) => a + b, 0], ["cost", cost, (a, b) => a + b, 0], ["label", label, (a, b) => a + b, ""]]) {
  try {
    visitAll(v, combine, start);
    console.log(`visitor/${name} completed silently`);
  } catch (e) {
    threw += 1;
    console.log(`visitor/${name.padEnd(9)} ${e.constructor.name}: ${e.message}`);
  }
}

console.log(`operation returning a silently wrong result: iterator+switch=${silentlyWrong}  visitor=0`);
console.log(`operation reporting the missing type: iterator+switch=0  visitor=${threw}`);
console.log(`sites that need editing for the new type: iterator+switch=3 switch bodies  visitor=3 visitor objects`);

iterator+switch  tight=2 (expected 3)  cost=5260 (expected 5860)  customs label=P:GMR
visitor/tightness TypeError: no visitor method for customs
visitor/cost      TypeError: no visitor method for customs
visitor/label     TypeError: no visitor method for customs
operation returning a silently wrong result: iterator+switch=3  visitor=0
operation reporting the missing type: iterator+switch=0  visitor=3
sites that need editing for the new type: iterator+switch=3 switch bodies  visitor=3 visitor objects

Three against zero, and zero against three. The number of sites that need editing is three in both — this is the expression problem established in the Programming Paradigms course, and visitor does not solve it, only decides its direction: a new operation is cheap, a new type is expensive. What the pattern gives is the visibility of that expense. The default branch in the switch body counted customs as a delivery point, undercounted the cost by 600 cents, dropped it from the capacity check, and produced no warning. The visitor version reported the missing method by name in all three operations.

The cost has two items. The first is a call level: reaching a node’s cost requires passing through accept, so the path to the body is one call longer. The second is the cost of a new operation: in the visitor version, a new operation requires writing as many methods as there are node types — four, here. The default branch in a switch body removes this requirement, and brings silence in exchange.

Summary

• Iterator separates traversal from the operation, visitor separates type discrimination from the operation; each cleans up a separate axis and neither substitutes for the other.
• The three versions produced the same five values on the same tree; the distinct result set came out at 1.
• The number of sites carrying traversal code dropped from 5 to 1, and the number of sites discriminating by type dropped from 7 to 2.
• Switching traversal order to breadth-first edited 1 file in the iterator version; the same change requires editing 5 bodies in the traversal version.
• When a new node type was added, the switch-bodied version silently returned the wrong result in 3 operations, and the visitor version reported the missing method in 3 operations; the number of sites that need editing is 3 in both.
• Cost: accept adds one call level, and a new operation requires writing as many methods as there are node types.

Next Step

Visitor applies an operation to every node in the tree; the nodes do not know each other, and all of them are handled in the order traversal gives. On the library’s operator screen, though, the objects know each other directly. The carrier selector, the tariff summary, the discount box, and the delivery-date field keep each other informed: when the carrier changes, the tariff refreshes; when the tariff changes, the discount is recomputed; when the discount changes, the delivery date can update. Each of the four fields imports the other three. The next lesson measures the number of these mutual dependencies, gathers them into a single object and recomputes the same number, and separately counts the cost of storing the editing session’s state without breaking encapsulation.