= Solution
Represent a wall by a <list> of rows indexed by height. Within each row keep brick placements sorted by their left coordinate, with disjoint occupied <half-open intervals>. The public `Brick` in the paper is a mutable input specification; internal placements snapshot its width and colour, so later client edits cannot invalidate an existing wall. Empty intermediate rows cannot occur in a supportive wall with occupied rows above them.
The following <Java> uses `import java.util.*;` and `import java.awt.Color;`. Keep the source's `Brick` input <software class>. All other representation types are private nested <software classes> of `Wall`, which prevents clients from inserting directly into a row. The `row(int y)` query returns a detached row for the equality operation in part (e).
``
final class Wall {
private static final class Placed {
final long x, end;
final Color colour;
Placed(long x, int width, Color colour) {
this.x = x;
this.end = x + width;
this.colour = colour;
}
}
private static final class Row {
private final List<Placed> bricks = new ArrayList<Placed>();
boolean contains(long x) {
for (Placed b : bricks) {
if (x < b.x) return false;
if (x < b.end) return true;
}
return false;
}
boolean canInsert(Placed b) {
for (Placed old : bricks)
if (b.x < old.end && old.x < b.end) return false;
return true;
}
void insert(Placed b) {
int i = 0;
while (i < bricks.size() && bricks.get(i).x < b.x) ++i;
bricks.add(i, b);
}
Row copy() {
Row r = new Row();
r.bricks.addAll(bricks);
return r;
}
// Insert the equality members from part (e) here.
}
private final List<Row> rows = new ArrayList<Row>();
public void addBrick(Brick b, int x, int y) throws Exception {
if (b == null || b.col == null || b.width <= 0 || y < 0)
throw new Exception("invalid brick or height");
// Snapshot mutable input. Long arithmetic protects x + width.
int width = b.width;
Color colour = new Color(b.col.getRGB(), true);
Placed placed = new Placed((long) x, width, colour);
if (y > rows.size()) throw new Exception("unsupported height");
Row target = y == rows.size() ? new Row() : rows.get(y);
if (!target.canInsert(placed)) throw new Exception("overlap");
if (y > 0) {
Row below = rows.get(y - 1);
if (!below.contains(placed.x) || !below.contains(placed.end - 1))
throw new Exception("unsupported end");
}
// All checks precede the first modification of this wall.
target.insert(placed);
if (y == rows.size()) rows.add(target);
}
public boolean contains(int x, int y) {
return y >= 0 && y < rows.size() && rows.get(y).contains((long) x);
}
public Object row(int y) {
if (y < 0) throw new IllegalArgumentException("negative row");
return y < rows.size() ? rows.get(y).copy() : new Row();
}
}
``
Here `Placed` instances and their captured `Color` values are <immutable objects>, so copying a row's outer <list> suffices to create a detached snapshot. Returning its static type as `Object` exposes just the equality operation needed below, without exposing a mutable row <API>. A fuller application could instead return an immutable row-view <object interface>.
The empty <list> represents a valid supportive wall. A rejected insertion performs no wall update. On success, the overlap test establishes validity in the target row; all other rows are unchanged. The support checks establish support for the new brick; adding material cannot remove support from old bricks. Appending a row only at the current height count keeps the row representation contiguous. <Integer overflow> in a right endpoint is prevented by converting the horizontal coordinate to `long` before adding the positive `int` width. For instance, a brick at `Integer.MAX_VALUE` can still have a mathematically meaningful right endpoint.
The resulting <representation invariant> is
$$
\boxed{\text{ordered disjoint placements within rows, with every elevated brick supported at both ends}.}
$$
This is a sequential <API>; concurrent mutation of an input `Brick` during the call is outside its contract. Coordinate magnitude does not determine the storage used: storage is proportional to the number of placements and occupied rows.
Back to article page
