The solutions use the original seven-page paper, including its corrected Question 3.[ref]
An immutable object has no changeable observable state after its object constructor finishes. Two clients may hold references to the same immutable object, but neither can change what the other observes. Thus sharing an immutable object avoids the interference normally associated with reference aliasing: for example, sharing a Java String is safe because a text-changing operation returns another software object rather than modifying that String data type value.
A final reference alone does not establish an immutable object: it prevents reassignment of that reference, but its referent could still be mutable. An immutable object must also protect any reachable mutable state, for instance through defensive copying. With that qualification, the essential answer is
(1)
First determine the width of each column by finding the longest rendered String data type value in it. Independently determine the number of rows as the largest column size. An empty column has width zero. Then traverse rows first and columns second: render a present entry with spaces on the appropriate side, or render an absent entry as an entire column of spaces. Put one separating space between adjacent columns and a newline after each row. In particular, an exhausted column must not shift later entries into its position.
Here is executable Java for the algorithm. Column, defined in part (e), is an ordinary list of Data. The object interface in part (c) supplies the three queries used below. Each query sees stable content during this call; concurrent changes to formatting are outside this contract.
static String replicate(char c, int n) {
    StringBuilder s = new StringBuilder();
    for (int i = 0; i < n; ++i) s.append(c);
    return s.toString();
}

static String printData(List<Column> columns) {
    int[] width = new int[columns.size()];
    int rows = 0;
    for (int c = 0; c < columns.size(); ++c) {
        Column column = columns.get(c);
        rows = Math.max(rows, column.size());
        for (Data d : column)
            width[c] = Math.max(width[c], d.length());
    }
    StringBuilder out = new StringBuilder();
    for (int r = 0; r < rows; ++r) {
        for (int c = 0; c < columns.size(); ++c) {
            if (c != 0) out.append(' ');
            Column column = columns.get(c);
            if (r >= column.size()) {
                out.append(replicate(' ', width[c]));
            } else {
                Data d = column.get(r);
                String text = d.toString();
                String pad = replicate(' ', width[c] - text.length());
                out.append(d.leftJustified() ? text + pad : pad + text);
            }
        }
        out.append('\n');
    }
    return out.toString();
}
The algorithm uses the stipulated fixed-width characters and assumes entries contain no embedded newlines. If the column widths are and , every emitted row has the same width,
(1)
An empty collection, or a collection consisting entirely of empty columns, gives the empty String data type value. Spaces at the end of a short last row are harmless and preserve the rectangular layout.
Use an abstract class to share the unchangeable alignment flag and the rule that the reported length equals the rendered text's length. This small class inheritance hierarchy will also serve the numeric software classes in part (d). The Java interface explicitly declares toString() so that the display contract is visible even though all Java software objects already inherit that object method.
interface Data {
    boolean leftJustified();
    int length();
    String toString();
}

abstract class AbstractData implements Data {
    private final boolean leftj;

    protected AbstractData(boolean leftj) { this.leftj = leftj; }

    public final boolean leftJustified() { return leftj; }
    public final int length() { return toString().length(); }
    public abstract String toString();
}

final class StringData extends AbstractData {
    private final String text;

    public StringData(String s, boolean leftj) {
        super(leftj);
        if (s == null) throw new IllegalArgumentException("null text");
        text = s;
    }

    public String toString() { return text; }
}
There are no setters, and the stored String data type value is an immutable object, so StringData is itself an immutable object. Its object constructor rejects a null reference instead of deferring failure until display. Consequently,
(1)
The UML class diagram separates text shared by every displayable item from numeric formatting shared only by numeric items. A dashed hollow-triangle arrow denotes realization of a Java interface; solid hollow-triangle arrows denote class inheritance. Both kinds of arrow point towards the more general type.
Figure 1.
Data interface realization and inheritance for string, integer and real display items
. Details.
AbstractData owns alignment and computes length from the current rendered text. NumericData adds the minimum digit width. IntegerData and RealData each own their numeric value, while RealData alone owns the minimum number of decimal places. The numeric formatting object methods do not belong on Data: ordinary text has no meaningful setPlaces operation. The design choice is
(1)
Retain Data, AbstractData and StringData from part (c). The following are the additional software classes. Formatting denotes the supplied formatting facility with its two static format overloads; its implementation is expressly not required. These calls preserve the distinction between a minimum width and a maximum width: no stored value is truncated.
abstract class NumericData extends AbstractData {
    private int minDigits = 0;

    protected NumericData(boolean leftj) { super(leftj); }

    public final void setDigits(int n) { minDigits = Math.max(0, n); }
    protected final int digits() { return minDigits; }
}

final class IntegerData extends NumericData {
    private final int value;

    public IntegerData(int n, boolean leftj) {
        super(leftj);
        value = n;
    }

    public String toString() {
        return Formatting.format(value, digits());
    }
}

final class RealData extends NumericData {
    private final double value;
    private int minPlaces = 0;

    public RealData(double d, boolean leftj) {
        super(leftj);
        value = d;
    }

    public void setPlaces(int p) { minPlaces = Math.max(0, p); }

    public String toString() {
        return Formatting.format(value, digits(), minPlaces);
    }
}
Zero is the default minimum, and a nonpositive setting removes that minimum. Formatting a negative value, or a value already longer than the minimum, is delegated to the stated formatter contract. The inherited length() calls the current toString(), so a change to either formatting setting immediately changes the measured column width. For example, after setDigits(3), an IntegerData containing 42 renders 042 and has length 3; after setPlaces(2), a RealData containing 2.7 renders 2.70 and has length at least 4.
Unlike StringData, these numeric software objects are mutable because their displayed state can change. Their numeric values and alignment remain fixed. The useful invariant is
(1)
Use the weekday number as an array index. Before adding dates, add one empty entry to each weekday before start; otherwise the first date in those columns would appear a week too early. For day , the slot number is , whose remainder modulo 7 selects the column. The source's example makes clear that start counts empty weekday cells, rather than individual printed space characters.[ref]
With import java.util.*;, the remaining Java code is:
final class Column extends ArrayList<Data> {
    private static final long serialVersionUID = 1L;
}

static String month(int start, int numDays) {
    if (start < 0 || start >= 7 || numDays < 1 || numDays > 31)
        throw new IllegalArgumentException("invalid month parameters");
    String[] days = {"Su", "Mo", "Tu", "We", "Th", "Fr", "Sa"};
    int ncols = days.length;
    List<Column> output = new ArrayList<Column>(ncols);
    for (int c = 0; c < ncols; ++c) {
        Column column = new Column();
        column.add(new StringData(days[c], true));
        output.add(column);
    }
    for (int c = 0; c < start; ++c)
        output.get(c).add(new StringData("", true));
    for (int d = 1; d <= numDays; ++d) {
        int c = (start + d - 1) % ncols;
        output.get(c).add(new IntegerData(d, false));
    }
    return printData(output);
}
The two-character headers force every column to width two, and right justification aligns one-digit dates with the units digits of two-digit dates. Date appears in data row , below the header. For month(1,30) the visible result is
Su Mo Tu We Th Fr Sa
    1  2  3  4  5  6
 7  8  9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30
The last physical line may also carry spaces for its empty trailing cells. Every physical line ends with a newline. In particular,
(1)
Take the lower coordinate in each direction from the smaller lower bound, and the upper coordinate from the larger upper bound. This gives an axis-aligned bounding box, rather than the generally nonrectangular set union of the two regions. Use defensive copying because the paper's Point has mutable fields.
final class Rect {
    private final Point lowerLeft, upperRight;

    public Rect(Point ll, Point ur) {
        if (ll == null || ur == null)
            throw new IllegalArgumentException("null corner");
        double xl = ll.getX(), yl = ll.getY();
        double xh = ur.getX(), yh = ur.getY();
        if (!Double.isFinite(xl) || !Double.isFinite(yl)
                || !Double.isFinite(xh) || !Double.isFinite(yh)
                || xl > xh || yl > yh)
            throw new IllegalArgumentException("invalid rectangle");
        lowerLeft = new Point(xl, yl);
        upperRight = new Point(xh, yh);
    }

    public Rect Union(Rect r) {
        return new Rect(
            new Point(Math.min(lowerLeft.getX(), r.lowerLeft.getX()),
                      Math.min(lowerLeft.getY(), r.lowerLeft.getY())),
            new Point(Math.max(upperRight.getX(), r.upperRight.getX()),
                      Math.max(upperRight.getY(), r.upperRight.getY())));
    }

    public Point lowerLeft() { return lowerLeft.clone(); }
    public Point upperRight() { return upperRight.clone(); }
}
Any containing rectangle must reach at least as far as each input rectangle in all four coordinate directions. The constructed rectangle reaches exactly those four limits, which proves both containment and minimality:
(1)
The corner accessors return copies, so changing a constructor argument or returned Point cannot alter an existing Rect.
The iterator pattern separates traversal state from the aggregate being traversed. A client asks whether another entry exists, then requests that entry, without knowing whether storage is an array, a linked list or another data structure. Distinct iterators have independent positions in a traversal.
In Java, declare DataList implements Iterable<Point> and provide public Iterator<Point> iterator(). The returned iterator implements hasNext() and next(); exhausted next() throws NoSuchElementException. This also permits an enhanced for (Point p : data) loop.[ref]
Returning points.iterator() directly would permit removal through that iterator and expose mutable stored Point instances. Part (e) instead returns an unmodifiable iterator snapshot containing fresh Point copies. That choice gives stable traversals and prevents representation exposure, with the tradeoff that a traversal does not see subsequent insertions. Thus
(1)
In model-view-controller, the model owns application data and its rules: here it is the ordered DataList with its uniqueness condition on horizontal coordinates. A view renders those data, for example as a line plot or a bar plot. View-specific decisions such as whether to show axes need not change the model. A controller interprets actions such as entering a new sample or selecting a plot style, and requests the appropriate model or view operation.
This separation of concerns permits several views of the same data and allows model operations to be tested without drawing a window. When the model changes, affected views need a notification or another refresh mechanism. The Observer pattern in part (d) supplies one such mechanism, without making the model depend on every concrete view software class. The division is
(1)
In the Observer pattern, an observable subject keeps registered observers behind a shared object interface. After a relevant update, the subject calls that object interface on each observer. Observers can register and unregister independently, and the subject needs no knowledge of their concrete software classes.
For this model-view-controller application, DataList is the subject, while graph views are observers. After a successful insertion, a notification tells each registered view to redraw from the updated model. An invalid insertion leaves the model unchanged and needs no change notification. Calling observers only after restoring the representation invariant prevents views from seeing a half-completed insertion. Hence
(1)
Keep storage private. Find the first entry whose horizontal coordinate is not smaller than the new one. Equality there means that the coordinate is already present; otherwise insertion at that position preserves strict ordering. Reject nonfinite coordinates, since a NaN would make the required comparisons meaningless. This is an explicit finite-coordinate contract for a display application.[ref]
The Observer pattern uses a small callback Java interface. With import java.util.*;, the full implementation is:
interface GraphObserver {
    void changed(DataList source);
}

final class DataList implements Iterable<Point> {
    private final List<Point> points;
    private final List<GraphObserver> observers;

    public DataList() {
        points = new ArrayList<Point>();
        observers = new ArrayList<GraphObserver>();
    }

    public void addObserver(GraphObserver observer) {
        if (observer == null)
            throw new IllegalArgumentException("null observer");
        for (GraphObserver old : observers)
            if (old == observer) return;
        observers.add(observer);
    }

    public void removeObserver(GraphObserver observer) {
        for (int i = 0; i < observers.size(); ++i) {
            if (observers.get(i) == observer) {
                observers.remove(i);
                return;
            }
        }
    }

    public void addPoint(double x, double y) throws Exception {
        if (!Double.isFinite(x) || !Double.isFinite(y))
            throw new Exception("nonfinite coordinate");
        int i = 0;
        while (i < points.size() && points.get(i).getX() < x) ++i;
        if (i < points.size() && points.get(i).getX() == x)
            throw new Exception("duplicate x coordinate");
        points.add(i, new Point(x, y));
        List<GraphObserver> current =
            new ArrayList<GraphObserver>(observers);
        for (GraphObserver observer : current) observer.changed(this);
    }

    public Iterator<Point> iterator() {
        List<Point> snapshot = new ArrayList<Point>(points.size());
        for (Point p : points) snapshot.add(p.clone());
        return Collections.unmodifiableList(snapshot).iterator();
    }
}
This is a sequential implementation. Callback object methods are required to return normally and not reenter addPoint; they may change their registrations. Copying the registration list means such changes affect future notifications, while each observer present at the start of this notification gets exactly one call. Repeated registration of the same observer is ignored by object identity. Both signed zeros compare equal and therefore count as the same horizontal coordinate.
For correctness, all old entries before position i have smaller horizontal coordinates. If an entry at i exists after the duplicate check, it has a strictly larger coordinate. Inserting between these two groups preserves the representation invariant; rejecting a duplicate has no state effect. No client receives a stored mutable Point. Thus
(1)
For each sample, include both its marker and its bar. A bar's lower vertical limit is , including negative bars below the horizontal axis. Its horizontal half-width is , rather than . Its marker extends by in both directions. Therefore that sample's axis-aligned bounding box is
(1)
Taking successive bounding unions includes every sample. Finally unite with to include the stipulated axes. The printed upper-corner formula has one extra closing parenthesis; both the lower-corner formula and the picture confirm the coordinatewise interpretation used here.[ref]
The following commented Java object method may be placed in a graph-view utility software class. It uses Rect from part (a) and one iterator snapshot from part (e).
static Rect barBounds(DataList data, double C, double M) {
    if (!Double.isFinite(C) || !Double.isFinite(M) || C <= 0 || M <= 0)
        throw new IllegalArgumentException("positive finite margins required");
    List<Point> p = new ArrayList<Point>();
    for (Point point : data) p.add(point);
    int n = p.size();
    if (n < 2) throw new IllegalArgumentException("at least two points required");

    // This central square supplies the required minimum axis extents.
    Rect bounds = new Rect(new Point(-M, -M), new Point(M, M));
    for (int i = 0; i < n; ++i) {
        double x = p.get(i).getX(), y = p.get(i).getY();
        double width;
        if (i == 0) {
            width = p.get(1).getX() - x;
        } else if (i == n - 1) {
            width = x - p.get(i - 1).getX();
        } else {
            width = Math.min(x - p.get(i - 1).getX(),
                             p.get(i + 1).getX() - x);
        }
        // Include whichever is wider: marker or half of the bar.
        double half = Math.max(C, width / 2.0);
        // The bar reaches the baseline; the marker reaches y +/- C.
        Rect item = new Rect(new Point(x - half, Math.min(0.0, y - C)),
                             new Point(x + half, Math.max(0.0, y + C)));
        bounds = bounds.Union(item);
    }
    return bounds;
}
This uses the usual assumption that coordinate differences and expanded bounds are representable as finite double values. Rect rejects overflowed bounds; numerical range extension is not part of the requested geometry. As with all floating-point arithmetic, the calculation approximates the corresponding exact real number formulas.
Every side produced by the coordinatewise extrema is required by some bar, marker enclosure or axis extent. The result is therefore the smallest guaranteed rectangle for the specified marker enclosures and axes. If denote the graph-only bounds, the final answer is
(2)
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
(1)
Let brick have positive integer width . Regard its horizontal occupied region as and its vertical occupied region as . 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
(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.
For an integer cell coordinate, occupancy is an existential predicate:
(1)
The first occupied unit cell of brick is at , and its last is at . Thus the required support predicate, with the baseplate explicitly included, is
(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 would incorrectly examine a cell beyond the brick's right end. The potentially infinite baseplate supplies every required support at height zero.[ref]
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
(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.
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 and bricks, generating and comparing their runs has time complexity and additional storage, independent of their widths or the magnitude of their coordinates. This meets the requirement to improve on checking every possible cell:
(1)

Ancestors (8)

  1. 2015
  2. Past exam of the computer science course of the University of Oxford
  3. Computer science course of the University of Oxford
  4. Undergraduate course of the University of Oxford
  5. Course of the University of Oxford
  6. University of Oxford
  7. List of universities
  8. Home

View article source

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.
See all articles in the same topic Create my own version