Past exam of the computer science course of the University of Oxford / 2015 / Object oriented programming / 3

For primitive values, Java == compares values, subject to the primitive type's rules. For references, == compares object identity: it asks whether the references designate the same software object, or are both null. The equals(Object) object method permits a software class to define value equality. Its inherited Object implementation still uses object identity, so meaningful content comparison requires an appropriate override.^[ref]

For example:

String a = new String("wall");
String b = new String("wall");
boolean sameObject = (a == b);  // false
boolean sameText = a.equals(b); // true

The two allocations have different object identities but equal text. Using separately allocated String data type values avoids relying on literal interning. A null receiver cannot receive an equals call; java.util.Objects.equals(a,b) is a null-safe comparison. An equals implementation should define an equivalence relation and equal software objects must have equal hashCode() results.^[ref] The distinction is

reference == : identity; equals : the class’s declared equality .

(1)

b

 0  0

Solution

 0  0

Let brick

i

have positive integer width

w_{i}

. Regard its horizontal occupied region as

[x_{i}, x_{i} + w_{i})

and its vertical occupied region as

[y_{i}, y_{i} + 1)

. These half-open interval conventions allow adjoining bricks to touch without overlapping. Since the vertical coordinates are integers, two bricks can overlap only when they are on the same row. A suitable predicate is

valid (W) ⟺ \forall i \neq = j, y_{i} \neq = y_{j} \lor x_{i} + w_{i} \leq x_{j} \lor x_{j} + w_{j} \leq x_{i} .

(1)

Positive widths and nonnegative integer heights are the underlying domain conditions for a wall built on the baseplate. Distinct members of the set are compared even if their Brick references happen to be identical: one brick specification can describe several placements. Testing object identity alone would miss two overlapping placements of the same specification.

For example, width-two bricks beginning at 0 and 2 on the same row satisfy the predicate; beginnings at 0 and 1 do not. The non-strict separation inequalities are essential because touching edges are permitted.

c

 0  0

Solution

 0  0

For an integer cell coordinate, occupancy is an existential predicate:

contains (W, x, y) ⟺ \exists i : y = y_{i} \land x_{i} \leq x < x_{i} + w_{i} .

(1)

The first occupied unit cell of brick

i

is at

x_{i}

, and its last is at

x_{i} + w_{i} - 1

. Thus the required support predicate, with the baseplate explicitly included, is

supportive (W) ⟺ \forall i : y_{i} = 0 \lor (y_{i} > 0 \land contains (W, x_{i}, y_{i} - 1) \land contains (W, x_{i} + w_{i} - 1, y_{i} - 1)) .

(2)

For width one, the two support cells coincide. For a wider brick, its middle may bridge an empty gap; the question only requires support beneath its two ends. Checking

x_{i} + w_{i}

would incorrectly examine a cell beyond the brick's right end. The potentially infinite baseplate supplies every required support at height zero.^[ref]

d

 0  0

Solution

 0  0

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

ordered disjoint placements within rows, with every elevated brick supported at both ends .

(1)

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.

e

 0  0

Solution

 0  0

Brick boundaries are not observable in the requested row equality. Two adjacent red width-one bricks must compare equal to one red width-two brick at the same left coordinate. Comparing the underlying placement lists would therefore give the wrong result.

Instead build each row's unique sequence of maximal occupied colour runs: merge adjacent placements exactly when they touch and have equal colours. Gaps remain gaps, and touching different colours remain separate runs. This is a geometric version of run-length encoding, with explicit start and end coordinates. Insert these members inside Row from part (d):

private static final class Run {
    final long x, end;
    final Color colour;

    Run(long x, long end, Color colour) {
        this.x = x;
        this.end = end;
        this.colour = colour;
    }
}

private List<Run> runs() {
    List<Run> result = new ArrayList<Run>();
    for (Placed b : bricks) {
        int last = result.size() - 1;
        if (last >= 0) {
            Run r = result.get(last);
            if (r.end == b.x && r.colour.equals(b.colour)) {
                result.set(last, new Run(r.x, b.end, r.colour));
                continue;
            }
        }
        result.add(new Run(b.x, b.end, b.colour));
    }
    return result;
}

@Override public boolean equals(Object other) {
    if (this == other) return true;
    if (!(other instanceof Row)) return false;
    List<Run> a = runs(), b = ((Row) other).runs();
    if (a.size() != b.size()) return false;
    for (int i = 0; i < a.size(); ++i) {
        Run r = a.get(i), s = b.get(i);
        if (r.x != s.x || r.end != s.end || !r.colour.equals(s.colour))
            return false;
    }
    return true;
}

@Override public int hashCode() {
    int h = 1;
    for (Run r : runs()) {
        h = 31 * h + Long.hashCode(r.x);
        h = 31 * h + Long.hashCode(r.end);
        h = 31 * h + r.colour.hashCode();
    }
    return h;
}

Color.equals compares colour values rather than object identity. Two row snapshots compare their local horizontal content independently of which wall height supplied them. Empty rows compare equal, even if obtained from different walls. The hash code uses the same canonical runs as equals, so alternative brick subdivisions with equal displayed content also have equal hash codes.^[ref]

To prove correctness, observe that a maximal run starts whenever occupancy begins or the colour changes, and ends exactly where that occupancy or colour ceases. Those boundaries are determined by the occupied colour at every coordinate. Thus equal occupied colours give the same runs, and equal runs give equal occupied colours. If rows contain

m

and

n

bricks, generating and comparing their runs has

O (m + n)

time complexity and

O (m + n)

additional storage, independent of their widths or the magnitude of their coordinates. This meets the requirement to improve on checking every possible cell:

row equality ⟺ equal ordered maximal occupied colour runs .

(1)

Past exam of the computer science course of the University of Oxford / 2015 / Object oriented programming / 3

a

Solution

b

Solution

c

Solution

d

Solution

e

Solution

 Ancestors (9)

 Discussion (0) New discussion

 Articles by others on the same topic (0)

Past exam of the computer science course of the University of Oxford / 2015 / Object oriented programming / 3

 Discussion (0)  Subscribe (1) New discussion

 Discussion (0) New discussion