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: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]Java 8 iteration API documentation. Iterable.iterator(), enhanced for support, and Iterator.next() exhaustion contract
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. ThusIn 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
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. HenceKeep 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]Java 8 Double API documentation. isFinite(double)
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. ThusFor 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 isTaking 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. Articles by others on the same topic
There are currently no matching articles.