Light on Java

Simpler inheritance diagrams

2011-10-27T12:07:00.000+01:00

Two equality groups

Partial separation

Turkish Cat Selçuk

2011-05-26T12:30:00.000+01:00

How to code multiple dispatch in standard Java

2009-12-19T16:15:00.034Z

This posting continues the theme of multiple dispatch related to the binary method problem and shows a basic double dispatch implementation in standard Java. An appropriate method for computing whether two Shape objects overlap is selected based on runtime argument type. More Shape classes can be added without modifying existing code for shapes (rectangle, square, circle, ect.) already written. Doing it with a drop-through instanceof list is contrasted with low-overhead selection by argument type from an array of methods.

Multiple and predicate dispatching

Single, dynamic dispatching is used by OOP languages to call a designated method based on the runtime type of an object currently at a reference. When the language also features static (compile time) type checking the object's actual type will generally be either the nominal type of the reference or a subclass of that type. In either case, if the object does not have a method matching the static signature of the called method a compile time or runtime error results. For applications written using so called managed-code an exception is thrown at runtime. Using native code languages that do not provide this level of implicit type checking during execution, the error may vary from the method operating on spurious data to uncontrolled execution and possible program termination by the operating system.

In a language that features static type checking and whatever the actual mechanism involved, we can model single dispatching by giving all objects a reference to a table of methods for their class. The compiler stores the table offset of any particular method and when a call against a reference nominally to an object of a particular class is encountered, code is generated to retrieve the entry point for the method from the table. In the model a base class and each subclass has its own table - perhaps not the case as implemented. Overriding a method in a subclass the base-class method is replaced by the subclass method in the subclass' table. If a nominal superclass reference cites a subclass object at runtime, the subclass overridden method entry point is got from the table and this method is executed.

Multiple dispatch extends this method selection mechanism to include the runtime type of method arguments. Extending the model: single dispatching in a statically type-checked environment requires a single method selection table with one dimension. Without static checking an additional dimension is needed related to runtime type. Multiple dispatch requires a table with as many additional dimensions as there are arguments significant to the selection process. The table can be implemented as one per class or one per base class and there can be a table for each multi-method or a single combined table with other tables referenced by its elements.

To prove the concept we will look at implementing a single-method table for a method with a single significant argument in addition to object type. This implementation can be extended to include additional multi-methods by introducing additional tables.

Predicate dispatch extends the multiple dispatch concept by allowing the runtime values of arguments and logical relationships between types and/or values to be significant for method selection. In OOP languages the multiple dispatch and predicate concepts are quite blurred. A reference can cite an object of its nominal class or a subtype and the value of a reference is the object it refers to, one value of which is its type. Ability to include logical selection statements that deal with type and/or other values appears to be the distinguishing factor.

Implementing multiple dispatch

There are a number of possibilities. To do multiple dispatch according to the book we are going to have to use the java.lang.reflect package. If you haven't tried any of this stuff already to get an idea of what it entails you can Google 'Java Reflection' and have a look at some of Sun's postings.

For a more low level view Dennis Sosnoski's articles on IBM developerWorks go down into the world of bytecode and beyond, up to replacing reflection with runtime code generation.

As Dennis shows, using standard reflection is slow, very slow. Reflection may have a use for class initialization but what we are going to look at here is somthing far simpler and more akin to a native code approach - a DIY method table. A great advantage of implementing the table in Java is that it is pretty well guaranteed to be robust but there a number of difficulties to be overcome - methods not being a first-class data type for one.

The binary method problem

A binary method is a method that operates on two or more objects of the same type. It has at least two arguments, perhaps one implicit - the reference to the current instance, the other the same type or to a related class. Suppose we write a base class with a binary method, how can we allow for this method being overridden in a way that works for instances of any subclass including those that have not yet been written and without changing code in the base class?

Using instanceof and typecasting is one way, discussed briefly later, but what is needed is something more akin to overriding methods but related to argument types as well as the instance type. So, how can you override a method substituting covariant arguments that can be used straight off with no typecasts? Without too much difficulty it turns out.

In their paper presenting MultiJava, a Java extension supporting open classes and multiple dispatch, the authors cite the example of a Shape class with subclasses Rectangle, Circle etc. Shape has a binary method intersect(Shape) that returns true if two shapes overlap. I am going to nick this example in a slightly modified form to show how we can implement multiple dispatch in bog standard code. The methodology is kept simple and easy to explain. Perhaps a more generalized solution could be posted later but currently it is worth noting that open classes and multiple dispatch are strongly related to not implementing the Visitor design pattern, enough said!

Using double dispatch

First let's firm up what we are trying to achieve. In Shape nothing is known about rules for checking subclass intersection but in the first subclass, Rectangle say, we can write a method intersect(Rectangle).

Using single dispatching we would override intersect(Shape) from the base class:

    @Override public boolean intersect(Shape argument) {
        if (argument instanceof Rectangle)
            return intersect((Rectangle)argument);
        return argument.intersect(this);
    }

In fact this is programmed double dispatching. If the current class does not have a method to compute intersection with the actual type of the argument, argument.intersect(this) is called to get the result: the method called depends on the argument type. Under this scheme each new subclass includes methods to compute intersection with an instance of itself and all the types that have already been written.

This approach is fine: new shapes can be added as required without recoding any existing shapes and there is no problem with the kind of objections often made to using instanceof selection. The only drawback is that if a class does not implement a method to handle intersection for all the other classes written to date, after an instance of one of those other classes calls its intersect() the subsequent call to argument.intersect(this) gets unterminated recursion and stack overflow. An unavoidable fact of life, but things do not look quite so good when we get up to ten or twelve shapes:

    @Override public boolean intersect(Shape argument) {
        if (argument instanceof Rectangle)
            return intersect((Rectangle)argument);
        if (argument instanceof Square)
            return intersect((Square)argument);
        if (argument instanceof Circle)
            return intersect((Circle)argument);
        if (argument instanceof Triangle)
            return intersect((Triangle)argument);

        //..........................

        return argument.intersect(this);
    }

If this sort of thing is considered an 'anathema to Object Oriented Design' for unary methods why should it be OK for binary methods?

Apart from the call to argument.intersect(this) there is really no element of multiple dispatching in the intersect(Shape) method. Case selection using instanceof or even a more efficient isA construct [here] does not qualify. Multiple dispatching supplies immediate direction of execution to an appropriate method based on argument type. What is needed is a way of calling the required intersect(type) method directly.

Initially we need to map type to the required offset in a table of methods and the least complicated way of doing it is to provide each class with an a property mtOffset() : method table offset - the offset of references to methods with an argument of that class' type in one or more method tables.

The Shape base class

Let's see how this works out in the abstract base class Shape:

public abstract class Shape {

    public static final int MAX_SHAPES = 10;

    protected static int classMTOffset;

    protected static int getOffset() {
        return classMTOffset++;
    }

    protected abstract int mtOffset();

For simplicity the maximum number of shape classes that can be written is the constant MAX_SHAPES. It looks probable that the only way to make the size of the multi-method table fit runtime requirements exactly is to give it a nominal initial size and then expand it if required. For the moment we skip this complication. The method getOffset() is called by each subclass in turn when the class is initialized. getOffset() returns the value of the classMTOffset variable which is also incremented. Subclasses then implement the abstract mtOffset() method to return the value got during initialization.

Now we come to the base type for intersect() methods:

    protected static abstract class Intersect
                                <T extends Shape, S  extends Shape> {

        abstract boolean intersect(T a, S b) ;

     // abstract boolean contains(T a, S b, int tolerance); // possibly
    }

No first-class method type in Java so methods are implemented in nested classes. I am going to call these types Method Classes. There are pros and cons. A big pro is that any number of methods can be defined in a single class. An intersect(Shape) multimethod only requires a single sub-method but we could include a method contains(T, S) returning true if the S type shape fits entirely within T type shape for example, or similar overloaded methods with additional arguments, a tolerance factor maybe.

The characteristic shared by all intersect(T a, S b) methods as overridden in Intersect subclasses is that they all have two arguments that are covariant with Shape. Argument type is constrained by the declaration of the generic parameters to be a Shape or a subclass. Constraint is optional but shows the intention. IntersectRectangle for example is declared as:

     protected static class IntersectRectangle
                            extends Intersect<Rectangle, Rectangle> {

         @Override public boolean intersect(Rectangle t, Rectangle r) {
             //..............
         }
     }

The important factor is that declaring Intersect as a generic class allows intersect(T, S) to be overridden in this way. If for example, we write

    Intersect ref = new IntersectRectangle();
    Boolean b = ref.intersect(t, s);

the method called is intersect(Rectangle t, Rectangle r). Not a typecast in sight but the danger is that any subclass instance can be passed as an argument and passing the wrong kind gets a runtime error. We can design around this problem but a con is that this for the enclosing-class object must be passed as an argument. Of course it gets passed anyway. The dot before a method call can be seen as passing the reference that precedes it.

In this implementation method classes are static nested classes rather than inner classes. Inner classes would be nice: the method body has implicit access to outer-class fields but, because every instance of an inner class carries a reference to the outer-class instance that created it, every outer-class object would need its own method table. Even worse, the execution cost of creating this table is added to the construction cost for every instance. Here a single table is used located in Shape:

 
    protected static Intersect[][] intersectTable =
                                     new Intersect[MAX_SHAPES][];

The table has two dimensions one for each argument type. If a method has more arguments subject to multiple dispatch the table is implemented with that number of dimensions. The array of method classes for each class is added to the table when the class is initialized. The index of a method-class array depends on the value of mtOffset() for the class, which results from class initialization order and is arbitrary.

The method-class array for all classes is the same size irrespective of how many Intersect descendants the class implements. If a method to suite a particular combination of arguments is not present the corresponding element will be null, a characteristic used implementing the intersect(Shape) method:

    public boolean intersect(Shape s) {
        if (this == s) return true;

        // get method table offsets for the two types
        int thisMTO = this.mtOffset();
        int sMTO = s.mtOffset();

        // thisMTO indexes the table for the current class of object
        // sMTO the offset for a method to process the argument's type
        if (intersectTable[thisMTO][sMTO] != null) {

            // this object has a method so call it
            return intersectTable[thisMTO][sMTO].intersect(this, s);
        }

        // otherwise call the argument's method
        return intersectTable[sMTO][thisMTO].intersect(s, this);
    }

}  // end of Shape

There is no possibility that the wrong method is called - it is selected programmatically rather than by some scatterbrained programmer ;).

The same strategy shown for instanceof method selection is used to allow additional subclasses to be written: if a null element is found in the current instance's table it does not have a method. It is assumed that the argument implements a suitable method but if it does not a null pointer exception will be thrown rather than stack overflow: still an error but a more traceable result.

Implementing a Rectangle class

MT_OFFSET is initialized by calling Shape.getOffset() and this class' entry in the multy-method table is done by Rectangle.initMT().

public class Rectangle extends Shape {
    public static final int MT_OFFSET = getOffset();
    public static final boolean CLASS_INITIALIZED = initMT();

    private static boolean initMT() {
        intersectTable[MT_OFFSET] = new Intersect[MAX_SHAPES];
        intersectTable[MT_OFFSET][MT_OFFSET] = new IntersectRectangle();
        return true;
    }

    @Override protected int mtOffset() {
        return MT_OFFSET;
    }

    public final int top, left, width, height, right, bottom;

    public Rectangle(int left, int top, int width, int height) {
        this.left = left;
        this.top = top;
        this.width = width;
        this.height = height;
        right = left + width;
        bottom = top + height;
    }

    public static class IntersectRectangle
            extends Intersect<Rectangle, Rectangle> {

        @Override public boolean intersect(Rectangle t, Rectangle r) {

            return (t.right > r.left && t.left < r.right &&
                    t.bottom > r.top && t.top < r.bottom);
        }
    }

    @Override public String toString() {

        return left + ", " + top + ", " + width + ", " + height;
    }
}

A new vector of sub-method references is created at the MT_OFFSET for this class. The class only declares a single sub-method of the intersect(Shape, Shape) multi-method leaving other entries in the vector blank. The implemented method is selected by the inherited intersect(Shape) method when this is a Rectangle and its argument is also a Rectangle.

Implementing other shapes

Each new Shape implements sub-methods of intersect(Shape, Shape) to compare instances of the class with the instances of that class and other shapes implemented to date. Square declares two sub-methods:

public class Square extends Shape {

    public static final int MT_OFFSET = getOffset();
    public static final boolean CLASS_INITIALIZED = initMT();

    static boolean initMT() {
        intersectTable[MT_OFFSET] = new Intersect[MAX_SHAPES];
        intersectTable[MT_OFFSET][Rectangle.MT_OFFSET] =
            new IntersectRectangle();
        intersectTable[MT_OFFSET][MT_OFFSET] =
            new IntersectSquare();
        return true;
    }

    @Override protected int mtOffset() {
        return MT_OFFSET;
    }

    public final int top, left, side, right, bottom;

    public Square(int left, int top, int side) {
        this.left = left;
        this.top = top;
        this.side = side;
        right = left + side;
        bottom = top + side;
    }

    static class IntersectSquare extends Intersect<Square, Square> {

        @Override public boolean intersect(Square t, Square s) {
            return (t.right > s.left && t.left < s.right &&
                    t.bottom > s.top && t.top < s.bottom);
        }
    }

    static class IntersectRectangle extends Intersect<Square, Rectangle> {

        @Override public boolean intersect(Square t, Rectangle r) {
            return (t.right > r.left && t.left < r.right &&
                    t.bottom > r.top && t.top < r.bottom);
        }
    }

    @Override public String toString() {

        return left + ", " + top + ", " + side;
    }
}

Circle has three intersect() sub-methods:

public class Circle extends Shape {

    public static final int MT_OFFSET = getOffset();
    public static final boolean CLASS_INITIALIZED = initMT();

    static boolean initMT() {
        intersectTable[MT_OFFSET] = new Intersect[MAX_SHAPES];
        intersectTable[MT_OFFSET][Rectangle.MT_OFFSET] =
            new IntersectRectangle();
        intersectTable[MT_OFFSET][Square.MT_OFFSET] =
            new IntersectSquare();
        intersectTable[MT_OFFSET][MT_OFFSET] = new IntersectCircle();
        return true;
    }

    @Override protected int mtOffset() {
        return MT_OFFSET;
    }

    public final int left, top, radius, cx, cy ;

    public Circle(int left, int top, int radius) {
        this.left = left;
        this.top = top;
        this.radius = radius;
        cx = left + radius;
        cy = top + radius;
    }

    static class IntersectCircle extends Intersect<Circle, Circle>{
        @Override public boolean intersect(Circle t, Circle c) {
            int dx = c.cx - t.cx;
            int dy = c.cy - t.cy;
            double distance = Math.sqrt(dx*dx + dy*dy);
            return (distance < t.radius + c.radius);
        }
    }

    static class IntersectRectangle extends Intersect<Circle, Rectangle>{

        @Override public boolean intersect(Circle t, Rectangle r) {
            return t.intRect(r.left, r.top, r.right, r.bottom);
        }
    }

    static class IntersectSquare extends Intersect<Circle, Square>{

        @Override public boolean intersect(Circle t, Square s) {
            return t.intRect(s.left, s.top, s.right, s.bottom);
        }
    }

    @Override public String toString() {
        return left + ", " + top + ", " + radius;
    }

    private int distance(int x, int y) {
        int dx = cx - x;
        int dy = cy - y;
        return (int)Math.sqrt(dx*dx + dy*dy);
    }

    private boolean intRect(int left, int top, int right, int bottom) {
        int lr = left - radius;
        int rr = right + radius;
        int tr = top - radius;
        int br = bottom + radius;
        if (cx <= lr || cx >= rr || cy <= tr || cy >= br)
            return false;
        if (cx <= left) {
            if (cy <= top)
                return distance(left, top) < radius;
            if (cy >= bottom)
                return distance(left, bottom) < radius;
        } else if (cx >= right) {
            if (cy <= top)
                return distance(right, top) < radius;
            if (cy >= bottom)
                return distance(right, bottom) < radius;
        }
        return true;
    }
}

Testing it out

First sketch some shapes and modify the test function from the implementing equals() article then code main to compare the shapes.

By the way, I make no claims that the intersect algorithms are efficient or even correct: Let's see how this works out in the abstract base class Shape:

public class TestIntersect {

    public static void interPrint(Shape a, Shape b) {
        String ac = a.getClass().getCanonicalName();
        if (ac == null)
            ac = "?";
        else
            ac = ac.substring(ac.indexOf('.') + 1);
        String bc = b.getClass().getCanonicalName();
        if (bc == null)
            bc = "?";
        else
            bc = bc.substring(bc.indexOf('.') + 1);
        System.out.println(ac + " " + a.toString() + " a intersect() " +
               bc + " " + b.toString() + " b is " + a.intersect(b));
        System.out.println("aoff: " + a.mtOffset() + " boff: " +
           b.mtOffset()+ ", " + bc + " b intersect() " + ac + " a is " +
           b.intersect(a) );
    }

    public static void main(String[] args) {
        Square square1 = new Square(10, 10, 40);
        Circle circle1 = new Circle(30, 30, 20);
        Rectangle rect1 = new Rectangle(40, 40, 20, 80);
        interPrint(square1, circle1);
        interPrint(circle1, rect1);
        interPrint(square1, rect1);
        System.out.println();
        Square square2 = new Square(60, 120, 40);
        Circle circle2 = new Circle(94, 85, 20);
        Rectangle rect2 = new Rectangle(103, 5, 20, 80);
        interPrint(square2, rect1);
        interPrint(square2, circle2);
        interPrint(circle2, rect2);
        interPrint(square2, rect2);
    }
}

Works O.K. Note that the Square's mtOffset() is zero because it is initialized first. Changing instance construction order in main() will change these values but functionality is not affected.

Square 10, 10, 40 a intersect() Circle 30, 30, 20 b is true
aoff: 0, boff: 2. Circle intersect() Square is true
Circle 30, 30, 20 a intersect() Rectangle 40, 40, 20, 80 b is true
aoff: 2, boff: 1. Rectangle intersect() Circle is true
Square 10, 10, 40 a intersect() Rectangle 40, 40, 20, 80 b is true
aoff: 0, boff: 1. Rectangle intersect() Square is true

Square 60, 120, 40 a intersect() Rectangle 40, 40, 20, 80 b is false
aoff: 0, boff: 1. Rectangle intersect() Square is false
Square 60, 120, 40 a intersect() Circle 94, 85, 20 b is false
aoff: 0, boff: 2. Circle intersect() Square is false
Circle 94, 85, 20 a intersect() Rectangle 103, 5, 20, 80 b is false
aoff: 2, boff: 1. Rectangle intersect() Circle is false
Square 60, 120, 40 a intersect() Rectangle 103, 5, 20, 80 b is false
aoff: 0, boff: 1. Rectangle intersect() Square is false

Summary

Generic nested classes provide a way of declaring methods capable of multiple dispatch selection in standard Java. Without performance testing and as-is the technique looks faster than selection from a list of isA statements.

Test

2009-12-10T16:50:00.017Z

Decided on this syntax highlighter. Needed some typeface tweaking but has the great advantage that text can be copied without the line numbers if anyone would like to try some of my crazy code.

public class Customer {

    private String firstName;
    private String lastName;
    private Date birthday;
    private String street;
    private String city;
    private String zipcode;

    // follows the Eclipse generated result - two nulls are equal, but a
    // couple of trivial static functions can take out many lines of code
    public static boolean eqFields (Object a, Object b) {
        if (a != null)
            return a.equals(b);
        else
            return (b == null);
    }

    protected boolean equalFields(Customer rhs) {
        return eqFields(firstName, rhs.firstName) &&
               eqFields(lastName, rhs.lastName) &&
               eqFields(birthday, rhs.birthday) &&
               eqFields(city, rhs.city) &&
               eqFields(zipcode, rhs.zipcode);
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        return (obj instanceof CustomerOrg &&
                ((Customer)obj).equalFields(this));
    }

    public static int hash(Object obj) {
        return ((obj == null) ? 0 : obj.hashCode());
    }

    @Override
    public int hashCode() {
        int result = 21 + hash(birthday);
        result = result * 31 + hash(city);
        result = result * 31 + hash(firstName);
        result = result * 31 + hash(lastName);
        result = result * 31 + hash(street);
        return result * 31 + hash(zipcode);
    }
}

The dangers of overloading

2009-12-06T20:57:00.023Z

Posted the equals(Object) solution from my last blog on the artima discussion for this topic. As a contributor demonstrated, if the protected field comparison methods are called from outside an instance some very strange results can be produced. The answer is of course that protected methods should not be called from outside a class even if Java's same-package rule permits access. Default access gives plenty of scope for any required kludge without ignoring this last vestige of encapsulation.

These strange results should certainly discourage giving these methods public access or overloading an equals() with the class name, as seen in at least one published implementation. As things stand it is still quite possible to get the protected methods to return a symmetrical false when comparing the same object. All down to overloading, substitution and the aforementioned weak encapsulation but worth a look.

The first thing to do is write a Point base and a ColoredPoint subclass, as in the artima article, but use the new equals() implementation rather canEqual. In the base-class field comparison is factored of to fEquals(Point) and equals(Object) calls the received object's version of fEquals.


public class Point {

    private final int x;
    private final int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    // accessors are optional for this discussion

    @Override public boolean equals(Object obj) {
        return (obj instanceof Point &&
                ((Point)obj).fEquals(this) );
    }

    protected boolean fEquals(Point obj) {
        return (this.x == obj.x && this.y == obj.y);
    }


    @Override public int hashCode() {
        return (41 * (41 + getX()) + getY());
    }
}

Point can now be subclassed without overriding equals() and instances of all types will provide symmetry when compared for equality. ColouredPoint overrides equals() and overrides fEquals(Point) to return false - the required return comparing a ColoredPoint with a Point.


public class ColoredPoint extends Point {

    private final Color color;

    public ColoredPoint(int x, int y, Color color) {
        super(x, y);
        this.color = color;
    }

    // ....................

    @Override public boolean equals(Object obj) {
        return (obj instanceof ColoredPoint &&
                    ((ColoredPoint)obj).fEquals(this));
    }

    @Override protected boolean fEquals(Point obj) {
        return false;
    }

    protected boolean fEquals(ColoredPoint obj) {
        return (this.color.equals(obj.color) && super.fEquals(obj));
    }

    @Override public int hashCode() {
        return (41 * super.hashCode() + color.hashCode());
    }
}

ColoredPoint gets a fEquals(ColoredPoint) overloading and again equals() calls the received object's version. Using this technique we can write as many Point and ColoredPoint subclasses as we like that do or do not override equals().

To show two references to the same object giving a symmetrical false the same ColoredPoint is assigned to a Point reference and a ColoredPoint reference:


 public static void main(String[] args) {
     Point p1  = new Point(1, 1);
     ColoredPoint cp1 = new ColoredPoint(1, 1, Color.PINK);
     Point p2  = cp1;

First do a check that equals(Object) is working O.K. Of the following the first two pairs should return symmetric false comparing a Point with a ColoredPoint. The last pair should get a symmetric true comparing the same ColoredPoint. A same-object check has not been put in equals so the full field comparison is done:


     System.out.println("p1.equals(p2) is " + (p1.equals(p2)));
     System.out.println("p2.equals(p1) is " + (p2.equals(p1)));
     System.out.println("p1.equals(cp1) is " + (p1.equals(cp1)));
     System.out.println("cp1.equals(p1) is " + cp1.equals(p1)));
     System.out.println("p2.equals(cp1) is " + (p2.equals(cp1)));
     System.out.println("cp1.equals(p2) is " + (cp1.equals(p2))+ "\n");

Output is:

p1.equals(p2) is false
p2.equals(p1) is false
p1.equals(cp1) is false
cp1.equals(p1) is false
p2.equals(cp1) is true
cp1.equals(p2) is true

Everything works as expected but now the overloaded fEquals() methods are tested:


     System.out.println("p1.fEquals(p2) is " + (p1.fEquals(p2)));
     System.out.println("p2.fEquals(p1) is " + (p2.fEquals(p1)) + "\n");

The p1 reference is a Point type that references a Point so Point's fEquals is called and the x, y fields are compared: true expected. The ClouredPoint argument referenced by p2 at runtime has no effect at compile or runtime. Runtime argument type never has any effect on which method gets called.

For the second comparison the p2 reference is also a Point type. The compile time call is to fEquals(Point) but p2 references a ColoredPoint and its overriden version of fEquals(Point) is called at runtime: false expected, this method always returns false.

Output is:

p1.fEquals(p2) is true
p2.fEquals(p1) is false

The next two comparisons behave in a similar way:


     System.out.println("p1.fEquals(cp1) is " + (p1.fEquals(cp1)));
     System.out.println("cp1.fEquals(p1) is " + (cp1.fEquals(p1)) + "\n");

p1.fEquals(cp1) behavior is the same as p1.fEquals(p2), true expected. In cp1.fEquals(p1) gets a call to ColoredPoint's version of fEquals(Point): always false.

Output is:

p1.fEquals(cp1) is true
cp1.fEquals(p1) is false

The second result is obvious but now the references to the same ColoredPoint are compared:


     System.out.println("p2.fEquals(cp1) is " + (p2.fEquals(cp1)));
     System.out.println("cp1.fEquals(p2) is " + (cp1.fEquals(p2)));
}

gets:

p2.fEquals(cp1) is false
cp1.fEquals(p2) is false

cp1.fEquals(p2) is false is particularly unintuitive unless we remember that the runtime type of an argument has no effect on which method gets called - ever, unless said method is an exception handler that is.

The binary method problem

Elsewhere multiple and predicate dispatching add another dimension to overridden methods by making the argument type/s direct execution to an appropriate method. A Java extension that supports predicate dispatching is [here] with a covering paper [pdf].

One thing that multiple dispatching is good at is solving the binary method problem but at least a limited solution is possible in standard Java. Suppose we write a base class that has a method with an argument referencing an instance of the class or a same type array argument: a binary method. How can we allow for this method being overridden so that it works for instances and arguments of any subclass including those that have not yet been written and without changing code in the base class? The equals() implementation is a special case solution to the binary method problem using programmed double dispatching.

Diverse identifiers

Overloading is simply a convenience that saves having to think up a new method name. It forms the basis of operator overloading but may not be appropriate when methods are subject to being overridden in a subclass. Overloading adds nothing to functionality and as shown above can get unwanted side effects when an overloaded method is overridden. Maybe we need to consider whether this kind of polymorphism is generally helpful or whether it only adds ambiguity in some and perhaps in many cases - not for the compiler of course but when trying to interpret someone else's code or our own at a later time.

There is no reason why fEquals should not be given different identifiers in different classes, pointEquals(Point) and coloredPointEquals(ColoredPoint) for example. On the other hand doing this gets another common OOP problem: linkedColoredPointEquals(something) - huge identifiers that wrap code onto the next line. When implementing equals() there is never any scope for calling the protected method against a reference with an inappropriate nominal type. Perhaps all that is needed to provide better clarity is a more explicit overloaded method name, equalFields(...), for example.

Overriding equals(Object): an optimally correct solution

2009-11-29T14:31:00.054Z

Overriding Object's apparently innocuous equals(Object) method can be a source of difficulties. The first problem is that there appears to be no single implementation that meets all requirements. The second problem is the way that HashMap, the prime suspect for causing errors if the letter of the equals() specification is not met, uses equality to maintain its structure.

When equals() is overridden the initial requirement is to ensure that the Object in equals(Object) belongs to a class that is comparable with the current object. Two different implementations can be found in publications from authorities on the subject. They have some utility but both cause problems if implemented outside their limited applicable usage. Neither can provide a correct implementation of equals() for all inheritance requirements in a class hierarchy. A third published implementation can supply an equals() with correct behaviour in the two most commonly required cases but brings a considerable execution overhead when equals() is overridden in a subclass.

A simple equals() configuration is described that allows a class to have any of the three possible equality relationships with its super classes. For the two most commonly required relationships modifying the standard equals() implementation found in Java library classes to provide correct behaviour is trivial, simply a matter of factoring-off field comparisons to a separate method. Overriding equals() in a subclass is similarly trivial. If no modification to equality is required the new class can be derived without any additional coding related to equals() functionality. The approach brings almost no penalty for execution efficiency and additional coding is minimal.

Background

Overriding equals() allows a different view of object equality from Object's same-object implementation to be introduced. Used with hashCode(), equals() also provides the basis for object inclusion, exclusion and retrieval from a HashMap, a fast storage and retrieval structure appropriate for many applications.

Making an overridden equals() work according to plan brings two requirements: a well defined set of objects that the new method applies to and compliance with the so called equals() contract - in fact a definition of the required equality relationship between all objects. Its requirements are reflexivity, symmetry, transitivity, consistency and that a comparison with a null should always return false. These properties define an equality relationship found generally in most applications outside of quantum mechanics and we are on fairly safe ground.

An exceptionally lucid expose of the equals() contract and discussion of problems with published equals() implementations can be found at

http://www.angelikalanger.com/Articles/JavaSolutions/SecretsOfEquals/Equals.html

The problem identified

The equals() problem occurs anywhere we want to derive a subclass that has a concrete superclass other than Object, for which equals() has already been overridden and add some fields that are significant when computing subclass equality.

Figure 1 A moot choice

As shown in Figure 1 - ClassA, we would probably like to inherit from an existing class getting all its methods and functionality without writing any code, taking advantage of normal OOP provision for code reuse. The requirement to override equals() may prevent this course because the standard equals() implementation found in many Java library classes does not work in this situation.

To get a better understanding of the problem we can formalize this requirement of an object model that makes object equality other than basic identity a property of all objects as:

The first code reuse requirement: ability to derive a class that declares zero or more new significant fields and is not a member of its superclass comparison set.

It is apparent there are four possible requirements and this statement covers two of them. The remaining two are:

Second code reuse requirement: ability to derive a class that declares no new significant fields and is a member of its superclass comparison set.

Third code reuse requirement: ability to derive a class that declares new significant fields and is a member of its superclass comparison set.

We now need a definition for comparison set.

A comparison-set model

A comparison set is a set of classes having a root class for which instances of the root and some but possibly not all of its subclasses are compared for equality using significant fields declared or present in the root. For completeness we must also say that significant fields declared in a subclass may also figure in a comparison but this is an unusual condition satisfying the third code reuse requirement. When an object is compared with an object of a class not in its comparison set equals() is unable to make a meaningful comparison and must always return false.

Figure 2 sketches a class hierarchy with classes in a comparison set coloured green. Other classes are not in the green set and supply a potential root for other comparison sets.

Figure 2 A comparison set

A class that is a descendant of Object and does not override equals() is in a comparison set with Object as its root. The particular contract of Object's equals() - no two objects are equal, makes the standard implementation viable for overriding equals() in a direct subclass, A in Figure 2, but not in a sub classes B & C of a class in a derived comparison set. The standard implementation meets the first code reuse requirement in a class with no superclasses that have used it to override equals(), elsewhere it fails.

The Figure illustrates two important properties of comparison sets. Firstly, all classes in the set are descendants of a single root. The equals() implemented in the root must include a condition that determines whether the argument in equals(Object) is a member of the set of comparable objects for which a field comparison should be done or whether it is of another kind for which equals() should return false.

The 'standard' equals() implementation

The standard implementation employs instanceof the-root to exclude objects not in the comparison set. The instanceof statement can appear in a number of different guises, as illustrated using a class that declares a value field with an overloaded == operator:

    @Override public boolean equals(Object obj) {
        return obj instanceof Root &&
            value == ((Root) obj).value;
    }

    @Override public boolean equals(Object obj) {
        if (obj instanceof Root) {
            return (value == ((Root) obj).value);
        }
        return false;
    }

    @Override public boolean equals(Object obj) {
        if (this == obj) return true;
        if (! (obj instanceof Root)) return false;
        return (value == ((Root) obj).value);
    }

All configurations exclude instances of any class that is not a descendant of Root from field comparison and return false. The same-object check shown in the third configuration is of course optional and can be used in any implementation.

Which brings us to the second property of comparison sets and the problem with the standard equals() implementation: not all classes that are descendants of the Root are members of the same comparison set. The instanceof condition succeeds for instances of all subclasses irrespective of new fields. A superclass object can be found equal to a subclass object if fields declared in the superclass are equal to inherited fields in the subclass. Presenting the same superclass object to an overridden equals() in the subclass its instanceof will reject the superclass object and return false.

    @Override public boolean equals(Object obj) {
        if (obj instanceof Subclass) {
            Subclass sco = (Subclass) obj;
            return ( .......... );
        }
        return false;
    }

The symmetry requirement of object equality is broken and in the first case no proper equality assessment has been done making the result a nonsense.

There are of course occasions when we want to derive a class from a superclass without overriding equals(): the second code reuse requirement. A subclass might introduce a next field for example, a reference to an instance of the subclass so that a linked list of objects can be constructed. The standard implementation meets the second requirement. It fails when presented with a subclass instance that uses new fields to check equality and is not in the comparison set. It does not enable us to implement ClassA in Figure 1. Can an additional or modified condition be introduced to exclude instances of these classes from field comparison?

equals() using class comparison

Another commonly seen equals() implementation compares the runtime Class reference of the two objects to determine comparison set membership:

obj != null && obj.getClass == this.getClass

replaces obj instanceof Root in the condition. It could be used to derive Figure 1 - ClassA if used in the existing and new classes but does not allow any further subclasses that belong to one or other comparison set to be derived. All objects that are not of the same class are excluded and equals() returns false for these objects.

This means that superclass objects are excluded from subclass superclass comparisons and get a false return. If anything this characteristic is more dangerous in use than the instanceof problem. When equals() is not overridden in a subclass its functionality is modified by proxy to get a constant false return for superclass objects. A person who derives the subclass and has not modified equals() may be left unaware of this side effect until the application fails at a later time. A class comparison equals() implementation meets the first code reuse requirement. It cannot meet the second.

The third code reuse requirement

Not surprisingly, overriding equals() from a concrete superclass is seldom seen in Java code but there is one pertinent and frequently quoted example: java.sql.Timestamp. This class is a java.util.Date subclass that overrides equals to include a nanos field. Comparing a Date with a Timestamp returns true if the dates match irrespective of the value of nanos. Comparing a Timestamp with a Date always returns false even with matching dates: 'because the nanos component of a date is unknown.'

If equals() was overridden in both classes using the implementation proposed here there would be an open choice as to whether to make both comparisons return false or to allow a Timestamp to be equal to a Date if and only if its nanos field was zero (or any other single value). The methodology also allows a Timestamp to have symmetrical equality with a Date if dates match or if a Timestamp is within 500,000 nanos of a Date but these options break the equals() specification requirement for transitivity while the zero nanos option does not.

Here the valid option where a Timestamp with a zero nanos field may be equal to a Date supplies an example of a third possible equality relationship between a sub and superclass and the third if seldom needed code reuse requirement.

Alternatives to the standard implementation

An alternative to producing a flawed equals() in a subclass using the standard or class comparison implementations is to use composition, as illustrated by Figure 1 - ClassB. Using composition to implement structural elements of a program or even a data type where it fits well is one thing. Being forced to use it to implement equals() is something else. Do this and we can be faced with another set of no-win choices: write a lot of methods that do nothing except call composed object methods or include a method that returns the composed object - a possible solution if the object is immutable, otherwise doing this is likely to cause more problems that it solves. There may still be a problem even when the returned object is a clone - the clone does not reflect legitimate modifications to the original.

The standard equals() implementation used in library classes leaves no satisfactory alternative to composition when equals() is overridden but otherwise it is not a desirable alternative.

Taking on board the fact that neither of the commonly used implementations work satisfactorily an artima article posts a working solution for overriding equals() to get two of the code reuse requirements identified above:

http://www.artima.com/lejava/articles/equality.html

The third code reuse requirement is seldom needed and is therefore relatively unimportant but a problem with this implementation is that it uses a canEqual(Object) method that introduces an additional instanceof check and execution overhead for all calls to equals() even when comparing same-class objects. Consequently it cannot be seen as an optimal replacement for the standard implementation that can be put in place as a matter of course to allow subclasses to be derived at a later time.

Another downside is that the basic cost of a call doubles for an overridden equals in a subclass: super equals() is called to get superclass field comparison involving a second call to canEqual() and duplicate instanceof tests. The primary indication for using hashed storage is to provide fast access making this implementation not ideal for specific use even when the requirement to override equals() is known in advance.

The artima article shows a way forward and that a solution is possible but additional requirements to be addressed here are to devise an equals() implementation with a minimal code footprint and execution overhead that can be used as a matter of course in any class that overrides equals(). The implementation must allow fully working subclasses to be derived in all three cases where they may be required to meet OOP standards for code reuse.

We have now identified the requirements that an optimal equals() implementation must meet and can assess how the proposed alternative stands up.

Devising a solution

Figure 3 shows an inheritance structure containing four comparison sets.

Figure 3 Green, red, yellow and blue comparison sets

Here we consider a base class that is a concrete subclass of Object. Using an abstract base has only minor implications and then only if it declares significant fields. The simplest possible class will supply examples: one with a single integer field is used. The number of fields or even a complete audit of the current state of a data structure as used by HashMap has no bearing on the problem. This class is called GreenBase in the diagram and is the root of a green comparison set.

With the exception of ZGreen, GreenBase descendants in the green comparison set do not override equals(). They introduce no new fields that figure in comparison and are comparable using the equals() inherited from GreenBase. They can of course introduce other fields, the one on the left could be a LinkedGreen with a field referencing the next object in a list.

Implementing these classes requires that the equals() implementation satisfies the second requirement for code reuse: ability to derive a class that declares no new significant fields and is a member of its superclass comparison set. From the Figure we can see that there is a secondary requirement - that the condition used to determine comparison set membership should include all possible descendants of the base on all branches.

The standard implementation satisfies both these requirements using instanceof the-base but now we come to the apparently conflicting code reuse requirement: ability to derive a class that declares zero or more new significant fields and is not a member of its superclass comparison set. The equals() in GreenBase inherited by green subclasses can do an initial assessment for comparison set membership using instanceof or some similar isA condition but if it is going to make provision for derived comparison sets it must exclude instances of RedBase, YellowBase and BlueBase that supply the base class for new sets. All these classes are also GreenBase subclasses and instances will pass the initial assessment.

This problem raised the question as to what additional isA or class comparison check could be put in equals() to exclude instances on the same or a different branch from the root. After some thought and deciphering of the contracts of various Class methods it was decided that there wasn't one. We could perhaps give all comparable objects an additional property, say Class comparisonBase() or a similar final field, but doing this adds additional coding and additional logic in equals().

Otherwise only the received object can do the necessary checks but it was also found that when the decision on membership was passed to that object checking ancestry was no longer a requirement. The same is true when the received object's class has the third equality relationship, ZGreen in Figure 3, but as discussed below an additional isA check is then required.

The following sections assess how this implementation fairs with regard to the criteria for minimum code size and effect on execution efficiency over the standard implementation.

Minimizing the code footprint

The requirement here was to develop an implementation that was altogether trivial to code and required a minimum of extra coding over the standard equals(). GreenBase supplies a standard where differences are not overwhelmed by other code when the two implementations are shown side by side:

Excluding braces from the calculation the difference amounts to the two extra lines of code used by the fEquals(GreenBase) method. The field comparison method can have any name even equals(GreenBase) but it is suggested that standardizing the name to fEquals will facilitate use of this implementation and that fEquals should be overloaded when equals() is overridden in descendants to maintain consistency in use.

The extra coding is nothing compared with the complication of using composition to get a subclass equivalent and the chore of writing many do-nothing methods in a real life situation.

Minimizing the overhead

In GreenBase the equals() implementation introduces the smallest possible overhead above the standard, only the cost of calling fEquals(). The initial task is to exclude equals(Object) arguments that are instances of any class not a GreenBase or a subclass. The instanceof operator includes a check that the argument is not null and provides an economical solution:

public class GreenBase
{
    private final  int value;

    public GreenBase(int value) {
        this.value = value;
    }

    public int getValue() {
         return value;
    }

    @Override public boolean equals(Object obj) {
        return obj instanceof GreenBase &&
                ((GreenBase) obj).fEquals(this);
    }

    protected boolean fEquals(GreenBase obj) {
         return  ( value == obj.value );
    }

    @Override public int hashCode() {
        return 21 + value;
    }

}

Having determined that the equals(Object) argument is a GreenBase or a subclass and therefore a type that has an fEquals(GreenBase) method the next step is to call the argument's version passing a reference to the current object. This call is the only addition to the overhead for an implementation with field comparison done inline.

The decision on equality is passed to the received object. It is already known that the object is a GreenBase or a subclass. If the object's class is a member of the same comparison set it will have the same version of fEquals(GreenBase), which does the field comparison and returns the result, otherwise an overridden version simply returns false.

Deriving a new comparison set

RedBase introduces a new significant field, is not comparable with a GreenBase or instances of any green subclass and forms the root of the red comparison set:

public class RedBase extends GreenBase
{
    private final  long x;

    public RedBase(int value, long x) {
        super (value);
        this.x = x;
    }

    public long getX() {
         return x;
    }

    @Override public boolean equals(Object obj) {
        return obj instanceof RedBase &&
            ((RedBase) obj).fEquals(this);
    }

    protected boolean fEquals(RedBase obj) {
        return (x == obj.x && super.fEquals(obj));
    }

    @Override protected boolean fEquals(GreenBase obj) {
        return false;
    }

    @Override public int hashCode() {
        return super.hashCode() * 31 + (int) (x ^ (x >>> 32));
    }

}

RedBase overrides equals() with a new instanceof condition excluding instances of GreenBase and its other subclasses and calls a new fEquals(RedBase) overloading of the field comparison method on the received object. fEquals(GreenBase) is overridden to return false.

When a RedBase equals() receives a GreenBase or an instance of any of its other subclasses, including those that may have override equals(), the instanceof RedBase condition fails and false is returned. When the equals() in a GreenBase or another subclass is passed a RedBase either its overriden instanceof fails − it is a member of another derived comaprison set, or it is a member of the GreenBase comparison set and calls the object's overridden version of fEquals(GreenBase). Either case gets a symmetric false result for the two comparisons − exactly what is required.

Implementing classes that form the root of the other two comparison sets shown in Figure 3 follows the same pattern. BlueBase for example, inherits RedBase's constant false fEquals(GreenBase). It will override fEquals(RedBase) to return a constant false and implement a new fEquals overloading to deal with objects in the blue comparison set.

The logic is completely straightforward, but now we move on to implementing the unusual equality relationship where a class declares a new field that is used for comparison with instances of the same class and its subclasses but comparison with a superclass and other subclasses in the comparison set is permitted.

Equality of the third kind

ZGreen introduces a z field that is significant for equality. Comparison with instances of GreenBase and all other classes in the green comparison set is allowed.

The only circumstance where doing this makes any sense is if GreenBase is seen as supplying some kind of default z. If z is a string the default might be "" or null. If it is an integer it could be zero but the default can be any value from the range, yes even 42 is a possible candidate for an integer default. No approximate or wildcard value is permitted for the default or transitivity will no longer apply.

A default of zero seems to make a little sense so ZGreen is implemented with an integer z field and all other objects in the green comparison set are seen as having z == 0:

public class ZGreen extends GreenBase
{
   private final  int z;

    public ZGreen(int value, int z) {
        super (value);
        this.z = z;
    }

    public int getZ() {
         return z;
    }


    @Override public boolean equals(Object obj) {
        if (obj instanceof GreenBase) {
            if (obj instanceof ZGreen)
                return ((ZGreen) obj).fEquals(this);
            return (z == 0 && ((GreenBase) obj).fEquals(this));
        }
        return false;
    }

    protected boolean fEquals(ZGreen obj) {
        return (z == obj.z && super.fEquals(obj));
    }

    @Override protected boolean fEquals(GreenBase obj) {
        return z == 0 && super.fEquals(obj);
    }
}

In GreenBase the first instanceof condition admits objects that are GreenBase or a subclass and false is returned for any other object. Here a second grouping of the comparison set is made to include instances of ZGreen and its subclasses using a second instanceof comparison. Other objects that may or may not belong to the green comparison set are treated separately.

ZGreen arguments are dealt with by calling the object's fEquals(ZGreen). For other types, a check for the default z value is made and if this succeeds the object's fEquals(GreenBase) is called. The local fEquals(GreenBase) is overridden to deal with direct calls from other objects in the comparison set when their equals() receives a ZGreen argument. Other GreenBase subclass objects will not be calling fEquals(GreenBase) because a ZGreen will fail their initial instanceof condition.

hashCode() is not overridden - the inherited version returns a value based on the inherited value field so that GreenBase and ZGreen objects with a matching value both have the same hashcode.

Implementing an isA comparison

In ZGreen the second instanceof comparison includes a redundant check that the Object argument is not null. It can be eliminated by substituting an isA comparison using the Class method isInstance(Object).

    @Override public boolean equals(Object obj) {
        if (obj instanceof GreenBase) {

            // if obj isA ZGreen
            if (ZGreen.class.isInstance(obj))
                return ((ZGreen) obj).fEquals(this);
            return (z == 0 && ((GreenBase) obj).fEquals(this));
        }
        return false;
    }

Interpreting the meaning of Class' isInstance() method is quite brain numbing. One trick is to correct the English in your head to what it actually means - 'obj.getClass().hasInstance(this)' for example. Another trick is to read the statement right to left: this isInstance obj.getClass(). Failing these you can put your own isA() method in the base class - the only con is execution efficiency:

public boolean isA(Object obj) {
        if (obj == null) return false;      // optional check here - may be better done by caller
        return obj.getClass().isInstance(this);
    }

Summary

The equals() implementation shown here produces a correct comparison that complies with the equals() meta-contract for all of the three possible equality relationships that a subclass can have with a superclass. Analysis using the comparison-set model demonstrates that there are only three such relationships that equals() needs to support.

It is suggested that any additional overhead from calling a factored-off field comparison method is insignificant in most cases and that the ability to produce subclasses with a fully functional overridden equals(), allowing OOP code reuse without employing composition indicates that this implementation should be used as a matter of course when coding any class that overrides equals().

There are other related topics that may be addressed in a later posting: using an abstract superclass, the HashMap put(K, V) gotcha and implications of the Liskov Substitution Principle. Currently all that needs to be said on the LSP is that the second Liskov and Wing paper excludes relationships between objects from general discussion but groups this aspect with other 'safety properties (nothing bad happens)'. Certainly the LSP does not appear to address anything beyond Object's view of equality. It is down to us to make sure 'nothing bad happens' when equals() is overridden but it will certainly help if the implementation used works in the first place.

Barbara Liskov, Jeannette M Wing - A Behavioral Notion of Subtyping - ACM 1994

Test listing:

public class TestEquals {

    public static void eqPrint(Object a, Object b) {
        String ac = a.getClass().getCanonicalName();
        if (ac == null) ac = "?"; else ac = 
            ac.substring(ac.indexOf('.') + 1);
        String bc = b.getClass().getCanonicalName();
        if (bc == null) bc = "?"; else bc = 
            bc.substring(bc.indexOf('.') + 1);
        System.out.println(ac + " a equals() " + bc + " b: " +
            a.equals(b));
        System.out.println(bc + " b equals() " + ac + " a: " + 
            b.equals(a));
        System.out.println("Hashcodes are equal: " +
                              (a.hashCode() == b.hashCode()));
    }
    public static void nl() {System.out.println();}
    public static void main(String[] args) {
        Object a = new GreenBase(42);
        eqPrint(a, "");                     // false - false
        eqPrint(a, new GreenBase(42));      // true  - true
        eqPrint(a, new GreenSubA(42));      // true  - true
        eqPrint(a, new GreenSubA(41));      // false - false
        Object b = new GreenBase(42) {
            String s = "local class";
        };
        eqPrint(a, b);                      // true  - true
        nl();
        a = new GreenSubA(42);
        eqPrint(a, new GreenSubA(42));      // true - true
        eqPrint(a, new GreenSubB(42));      // true - true
        nl();
        a = new RedBase(42, 7);
        eqPrint(a, new RedBase(42, 7));     // true  - true
        eqPrint(a, new RedBase(41, 7));     // false - false
        eqPrint(a, new GreenBase(42));      // false - false
        eqPrint(a, new GreenSubA(42));      // false - false
        nl();
        a = new ZGreen(42, 0);
        eqPrint(a, new GreenBase(42));      // true  - true
        eqPrint(a, new GreenSubA(42));      // true  - true
        eqPrint(a, new ZGreenSubA(42, 0));  // true  - true
        eqPrint(a, new GreenSubA(41));      // false - false
        eqPrint(a, new RedBase(42, 0));     // false - false
        eqPrint(a, new RedSubA(42, 0));     // false - false
    }

    public static class GreenBase {

        private final int value;

        public GreenBase(int value) {
            this.value = value;
        }

        public int getValue() {
            return value;
        }

        @Override public boolean equals(Object obj) {
            return obj instanceof GreenBase &&
                    ((GreenBase) obj).fEquals(this);
        }
        protected boolean fEquals(GreenBase obj) {
            return (value == obj.value);
        }
        @Override public int hashCode() {
            return 21 + value;
        }
    }

    public static class GreenSubA extends GreenBase {
        GreenSubA next;
        public GreenSubA(int value) {
            super (value);
        }
    }
    public static class GreenSubB extends GreenBase {
        GreenSubB next;
        public GreenSubB(int value) {
            super (value);
        }
    }

    public static class RedBase extends GreenBase {

        private final long x;

        public RedBase(int value, long x) {
            super(value);
            this.x = x;
        }

        public long getX() {
            return x;
        }

        @Override public boolean equals(Object obj) {
            return obj instanceof RedBase &&
                    ((RedBase) obj).fEquals(this);
        }
        protected boolean fEquals(RedBase obj) {
            return (x == obj.x && super.fEquals(obj));
        }
        @Override protected boolean fEquals(GreenBase obj) {
            return false;
        }
        @Override public int hashCode() {
            return super.hashCode() * 31 + (int) (x ^ (x >>> 32));
        }
    }

    public static class RedSubA extends RedBase {
        RedSubA next;
        public RedSubA(int value, long x) {
            super(value, x);
        }
    }

    public static class ZGreen extends GreenBase {

        private final int z;

        public ZGreen(int value, int z) {
            super(value);
            this.z = z;
        }

        public int getZ() {
            return z;
        }

        @Override public boolean equals(Object obj) {
            if (obj instanceof GreenBase) {
                if (obj instanceof ZGreen) {
                    return ((ZGreen) obj).fEquals(this);
                }
                return (z == 0 && ((GreenBase) obj).fEquals(this));
            }
            return false;
        }
        protected boolean fEquals(ZGreen obj) {
            return (z == obj.z && super.fEquals(obj));
        }
        @Override protected boolean fEquals(GreenBase obj) {
            return z == 0 && super.fEquals(obj);
        }
    }

    public static class ZGreenSubA extends ZGreen {
        ZGreenSubA next;
        public ZGreenSubA(int value, int z) {
            super(value, z);
        }
    }
}

Using Processing in NetBeans (6.5)

2009-06-22T14:14:00.011+01:00

Boyd mentioned passing a reference to the current PApplet to separate classes from a Processing app. For anyone who has not yet tried combining Processing and NetBeans, points I have noted are here - there may be better alternatives. This post shows an example that implements a clipboard Copy and Paste subsystem. The code can be used in any processing application. Three variants are discussed: implementation as an inner class in a NetBeans (or PDE) environment, as a separate class in NetBeans and, using the resulting .jar from the Processing IDE (PDE). Initially a NetBeans Processing application is needed.

Creating a NetBeans Processing app.

1) In NetBeans make a New project, say 'Processing Template', with Create Main Class say 'processing.ProcessingApp'. (if you change the package name in the wizard, the package is created OK but the package processing; statement may be missing from the listing: just type it in)

2) Right click on the Libraries node in the project tree: Add JAR/folder, navigate to the folder where Processing core.jar is located, ...\processing-1.0.2-expert\ processing-1.0.2-expert\lib on my system. Select 'core.jar', and Open.

3) Modify the class ProcessingApp as shown:


package processing;

import processing.core.*;

/**
 *
 * @author Martin Humby
 */
public class ProcessingApp  extends PApplet {

   public static void main(String[] args) {
      PApplet.main(new String[]{"processing.ProcessingApp"});
   }

   // Code that can optionally be copied to and compiled from the PDE goes here.
   // The PDE only requires explicit import of packages it does not import
   // implicitly: import java.awt.datatransfer and java.awt.image for the example 
   // below. Duplicating implicit imports is OK, for the standard imports
   // that is. The PDE does not like public void setup() { } - delete public

} // end of ProcessingApp

Note that the string literal in main() must match the package name and class name. If you use Copy, Paste - Refactor to get a version copy and want to be able to run the copy, refactor does not modify the string and the new package and/or class-name must be changed by hand (otherwise the copy runs the current version of the original - confusing!).

To get a slightly more convenient way of accessing the library path to core.jar, select Tools - Libraries from the NetBeans menu bar. New Library, Library Name: 'Processing', Library Type: Class Libraries. Make sure Processing is selected in the Libraries tree and do Add JAR/Folder as in 2) above. Now right click the Libraries node for the project select Add Library. Scroll down the list of Global Libraries and select Processing.

Making the outline shown above a module template or plugin that can be installed into the IDE appears to have disadvantages. Seems to me the easiest way to keep a framework for Processing apps. handy is simply to save the outline as a standard project. Open the outline and use right-click Copy from the project node to get and rename a new project complete with the core.jar path already set up. You can of course include other Processing libraries with the outline.

Passing an explicit PApplet

An inner class that might be factored off to a separate class is a Clipboard Copy and Paste subsystem. Hiding its implementation means passing the current PApplet instance to its Copy and Paste functions. Writing subsystem access methods and the inner class as static ensures a separate class can be got with minimum modifications. Here the static keyword excludes passing an implicit this reference to the inner class: same situation as in a separate class. A difference is that enclosing class static fields remain accessible without qualification. Need to put this in if a straight transfer is going to work, (g.format == PApplet.ARGB) for example, or add such qualifications later.

To try this approach Copy the 'Processing Template' as a new project say 'Processing Clipboard' and modify the class ProcessingApp as shown. You can of course use Refactor to rename the class if you wish and modify the string in main() to suit.


package processing;

import java.awt.*;
import processing.core.*;
import java.awt.datatransfer.*;
import java.awt.image.BufferedImage;
import java.io.IOException;

/**
 *
 * @author Martin Humby
 */
public class ProcessingApp extends PApplet {

   public static void main(String[] args) {
      PApplet.main(new String[]{"processing.ProcessingApp"});
   }

   static final int WIDTH = 500;
   static final int PANEL_HT = 160;
   static final int HEIGHT = PANEL_HT + 500;
   static final int DRAWING_HEIGHT = HEIGHT - PANEL_HT;
   static final int PANEL_TOP = DRAWING_HEIGHT;

   public void setup() {
      size(WIDTH, HEIGHT);
      background(255);

      // include a panel below drawing area
      fill(128);
      rect(0, PANEL_TOP, WIDTH - 1, PANEL_HT - 1);
   }

   // draw() is required to get keyboard monitoring apparently
   public void draw() {
   }

   public void keyReleased() {
      // CTRL+C: Copy to Clipboard
      if (key == 3) {
         copyImageToClipboard(0, 0, width, height - PANEL_HT, this);
      }

      // CTRL+V: Paste Clipboard
      if (key == 22) {
         PImage img = getClipboardImage(this);
         if (img == null)
            return; // not an image on clipboard

         // blank drawing area if required
         background(255);

         // paste image centred on area above panel
         int w = img.width;
         int h = img.height;
         int dx = (width - w) / 2;
         int dy = (height - PANEL_HT - h) / 2;
         image(img, dx, dy);

         // restore the panel area
         fill(128);
         rect(0, PANEL_TOP, WIDTH - 1, PANEL_HT - 1);
      }
   }

   /////////////////////////////////////////////////////////////////////////////
   //
   //  COPY AND PASTE SUBSYSTEM
   //

   /**
    * Clipboard copy and paste: the following references were used
    * http://processing.org/hacks/hacks:clipboard
    * http://www.devx.com/Java/Article/22326/0/page/1  et seq.
    *
    */

   public static void copyImageToClipboard(int top, int left, int width,
         int height, PApplet p) {

      // could pass this.g directly but passing this for both functions gets
      // consistency in use
      PGraphics g = p.g;

      // g is needed to get format
      BufferedImage bImage = new BufferedImage(width, height, 
            (g.format == PApplet.ARGB) ?
                         BufferedImage.TYPE_INT_ARGB : BufferedImage.TYPE_INT_RGB);
      g.loadPixels();

      // some explicit identifiers clarify setRGB() usage:
      // setRGB(bImageX, bImageY, bothW, bothH, source[], srcOffset, sourceW);
      bImage.setRGB(0, 0, width, height, g.pixels, left + top * g.width, g.width);

      TransferablePImage imageSelection = new TransferablePImage(bImage);
      Toolkit.getDefaultToolkit().
              getSystemClipboard().setContents(imageSelection, null);
   }

   // return a PImage rather than an awt.Image
   public static PImage getClipboardImage(PApplet p) {

      Transferable t =
              Toolkit.getDefaultToolkit().getSystemClipboard().getContents(null);
      try {
         if (t != null && t.isDataFlavorSupported(DataFlavor.imageFlavor)) {
            BufferedImage bimg = (BufferedImage)
                t.getTransferData(DataFlavor.imageFlavor);
            int w = bimg.getWidth();
            int h = bimg.getHeight();

            // make it ARGB to be on the safe side - makes no difference
            // unless clipboard image has some tranparency could be?
            PImage pImg = p.createImage(w, h, PApplet.ARGB);
            pImg.loadPixels();
            bimg.getRGB(0, 0, w, h, pImg.pixels, 0, w);
            pImg.updatePixels();
            return pImg;
         }
      } catch (UnsupportedFlavorException e) {
      } catch (IOException e) {
      }
      return null;
   }

   static class TransferablePImage implements Transferable {

      // the class-name makes more sense as a separate class
      private Image image;  // an awt.Image

      public TransferablePImage(Image image) {
         this.image = image;
      }

      public Object getTransferData(DataFlavor flavor)
              throws UnsupportedFlavorException {
         if (!flavor.equals(DataFlavor.imageFlavor)) {
            throw new UnsupportedFlavorException(flavor);
         }
         return image;
      }

      public boolean isDataFlavorSupported(DataFlavor flavor) {
         return flavor.equals(DataFlavor.imageFlavor);
      }

      public DataFlavor[] getTransferDataFlavors() {
         // in some cases there may be more than one flavour?
         return new DataFlavor[]{DataFlavor.imageFlavor};
      }
   }
} // end of ProcessingApp

To test it open say Paint and load an image. Copy a selection smaller than 500 x 500, and paste to the Processing app. Copy and paste it back to Paint - the white border now surrounds the pasted area.

Factoring off the Clipboard Subsystem

It is optional whether a separate TransferablePImage class is put in a new package but doing this will make life easier if you want to use it from the Processing IDE. Right click Source Packages - New - Java Package, 'utilities' then
utilities - New - Java Class - 'TransferablePImage'.

Copy the inner class to the new file and modify it copying the subsystem interface methods as static class methods:


package utilities;

import java.awt.*;
import java.awt.datatransfer.*;
import java.awt.image.BufferedImage;
import java.io.IOException;
import processing.core.*;

/**
 * Copy or paste Processing PImage to / from system clipboard
 *
 * @author Martin Humby
 */
public class TransferablePImage  implements Transferable{

   private Image image;

   public TransferablePImage(Image image) {
      this.image = image;
   }

   // static methods now part of class
   
   public static void copyImageToClipboard(int top, int left, int  width,
         int height, PApplet p) {

        ... body as inner class

   }

   public static PImage getClipboardImage(PApplet p) {

        ... body as inner class

   }
   
   ... other methods as inner class
}

To test the new class make a copy of ProcessingApp, say ProcessingApp1, using copy and paste to the processing package. Do not forget to change the class name in the string literal! Add import utilities.TransferablePImage; Delete the COPY AND PASTE SUBSYSTEM. Modify lines that call Copy and Paste to:


TransferablePImage.copyImageToClipboard(0, 0, width, height - PANEL_HT, this);

PImage img = TransferablePImage.getClipboardImage(this);

Optionally delete ProcessingApp1 imports that are no longer used and proceed as before.

Using TransferablePImage from the PDE

Create a new NetBeans project 'processing utilities' with Create Main Class unchecked. Fix up the libraries path to core.jar. Copy and Paste the utilities package from its current location to the new project's Source Packages node. Build the project: the location of the resulting processing_utilities.jar file is shown in the NetBeans Output window.

Make a new folder called maybe 'jars'. A good place could be in the default My Docments\Processing folder. Copy the processing_utilities.jar file to the new folder. Open the Processing IDE and make a new Sketch. Copy in the code from ProcessingApp1.java from after the main() method. Do not include the last curly bracket that belongs to the enclosing class. Delete public from the setup() method.

From the PDE menu bar select Sketch - Add File... navigate to the 'jars' folder and open processing_utilities.jar. The IDE reports 'One file added to the sketch.' No import statement is required and putting one in gets a compilation error. Run the sketch - the result should be identical to the NetBeans version. You can of course include several other classes in processing_utilities.

For more on this subject see http://dev.processing.org/libraries/

Summary

Most code that compiles in the Processing IDE will compile in NetBeans with a PApplet wrapper and fixed up imports. There are a few exceptions. The non-Java color data type is an integer and needs changing to int. A second minor but annoying problem is the fact that Java has the default type for floating point as double. Processing makes the type implied but overflow checked on compile (neither check for values effectively zero apparently).

Processing: float h = 4.13566733e-15; Java: float h = 4.13566733e-15f; Compiler simplicity maybe but after inserting a few dozen 'f's you begin to wonder whether it generates float g = 42; as a promotion. Java of course insists that PApplet methods that get overridden have the same public access as in PApplet but adding this is trivial.

Similarly, most code that will compile in NetBeans compiles in the PDE. To avoid problems particularly when there are errors in the code, delete public access for setup(). Processing is perfectly happy with anonymous classes, which may save a few lines of code here and there. Currently generics are not supported. A pity. I like Java generics. They seem to fit nicely with the object model without providing a sledgehammer capability for wholesale obfuscation. Of course, this opinion may be a reaction to an excess of _traits and spiky brackets elsewhere but generics could be useful to reduce code size in some applications. A set of minimalistic controls managed and drawn by Processing for example:

There is little problem implementing a tiny control management subsystem using a state machine: there are less than a dozen states for a complete set and some can be excluded - no drag and drop for example. Similarly, a single Control type with action and graphics closures, implemented as classes and assigned to its attributes on a mix and match basis, keeps coding to a minimum. Controls manage themselves for radio-button selection and which control gets input (focus). Problems come up when programmatic access to a control is needed - to modify text in controls that show drawing status and size for example.

Arguably this is the wrong way to do it. Perhaps closures should monitor status in the wider environment of the enclosing PApplet but doing this means that controls that can otherwise be entirely passive require a specific action closure or active graphic to do the monitoring. A single line of code, in the draw() function say, can modify a passive control. Alternatively a new closure class is required to implement monitoring.

Control action and graphic attributes are coresponding base classes. Access to a specific attribute means either retaining a reference to the control and casting attributes to their actual type or retaining a reference to the attribute itself. Neither way is ideal as far as code size and clarity goes. Generics can do the casting once for a control reference and all specific attribute types are then accessible directly through that reference. There must be other situations where using generics from the PDE could be useful.

Chunk 37 Outline

2009-04-28T12:28:00.001+01:00

Next step to apply abstraction and functional approach to drawing lines with special properties.

Characteristics of line: start, end points and path between. Anything can happen along line as random or other factors are applied to it.

Underlying path across a grid of pixels and problems drawing it: Bresenham's algorithm.

Abstracting error-value checking to a closure - simple implementation, optimization.

Writing a function to draw a line between any two points, any width with a colour gradient along its length: needs end points of lines normal to conceptual underlying line.

Writing another closure to return maximum-width end-points of lines at points along underlying length. Problem: filling in missing pixels between adjacent lines due to jagged profile when they offset along underlying line.

Program draws colour gradient lines.

Applying similar closure approach to diverse grids: circular and random spaced grid using array.

PROGRAM 3D grid and thistle-down blob drawn with colour grad lines, moves along its length.

Mostly code: say 48 hours work, 2 weeks max. Time to post code on blogger????

In Search of Processings Lost

2009-04-09T20:26:00.007+01:00

As you may have noticed, Processing programs that use random() and/or noise() and do not set the seed for these functions before they are called, create a different output for each run. The run that gets the superb effect is lost forever but setting seeds always gets the same old effect as the last time. To retain random creation and the capability of recreating a successful run it would nice if the value of seeds could be read at the beginning of a run and stored for future reference. Unfortunately this is not possible - the underlying Java Random class sets seed randomly from its () constructor and does not include a method for retrieving a value that can be used with setSeed().

A workaround is to generate a value for seed using a similar procedure to Random's, record it, and then pass it to a seed setter:


void setup() {
   size(WIDTH, HEIGHT);
   long seed = 8682522807148013L + System.nanoTime();
   System.out.println(seed);
   randomSeed(seed);
   doDrawing();
}

output: 8702777365341749

If this run turns out to be the great one change setup() to


void setup() {
   size(WIDTH, HEIGHT);
//      long seed = 8682522807148013L + System.nanoTime();
//      System.out.println(seed);
   randomSeed(8702777365341749L);
   doDrawing();
}

identical graphic output is recreated. Otherwise, just continue with the original setup() version and hope for the best. The same seed generation method is appropriate for noiseSeed(). The seed calculation shown will avoid holes in the total sequence of values returned by nextLong() - if such exist and affect the 48 bit seed used by Random that is.

Drawing with Lines

2009-03-26T21:19:00.013Z

This Chapter examines the nature of lines and how they can be used to create art using the line drawing facilities provided by Processing. Initially we look at the broadest possible description of a line and then get down to the nitty-gritty of making a program produce a required result by drawing lines.

Not all lines are straight. A geodesic, the shortest distance between two points on the surface of the Earth, is a curve. Add random noise to a line and it can take on an aspect of a lightning strike, flickering flames, a rough sea, rain falling on a lake and other representations of chaotic behaviour or liquid flow according to the frequencies present in the noise. Any kind of line, straight, curved or distorted, can suggest an edge, a boundary or a link between two locations.

Alternatively we may want a simplified view where the purity of straight lines or the intersections of many lines are used to represent underlying curvature or some more complex shape. A grid of lines can define a two or three dimensional space where equal spacing represents the world as we see it but other spacings can give the effect of non-linearity. We can show distances and dimensions that would otherwise be too small or too large to see. We can also employ the additional dimensions of light, colour, hardness, discontinuity (dots and dashes) and blur to achieve the effect we want.

There are few straight lines in nature and even fewer orthogonal straight lines. A straight line has its own special significance when used representationally. An icon of human-kind one might say.

Satelight image of the nazca lines
from Wikimedia Commons NASA/GSFC/MITI/ERSDAC/JAROS, and U.S./Japan ASTER Science Team

The Line Drawing Functions

2009-03-26T18:39:00.019Z

Having got to grips with coordinates, setting colours and suchlike you will probably find line drawing relatively simple. Unlike some less enlightened environments Processing has only a single line drawing function and three line attribute setters.

The line() function

Line(), is overloaded for drawing in 2D and in 3D. A line function with four arguments draws a line on the picture plane, the screen for current purposes.

   line(x1, y1, x2, y2)

draws a line from the point (x1, y1) to (x2, y2).

To draw in 3D we must first setup a 3D drawing environment. Two 3D environments are available and as detailed in XXXX they are invoked by passing an extra argument to the function that sets the window size at the start of the program. You can use either

  size(x, y, P3D);   or   size(x, y, OPENGL);

size() can also be called with a P2D argument to get faster 2D drawing than the default JAVA2D environment provides: size(x, y, P2D). At the time of writing P2D did not support all the facilities of the default mode for line drawing. Try its effect using the simple line drawing program we come to in a moment and check the line drawing and attribute setter functions on the Processing website for current details.

With a 3D environment in place use:

  line(x1, y1, z1, x2, y2, z2);

to draw a line between points (1) and (2) in three dimensional space. The extra coordinates z1 and z2 are the distances of points behind the picture plane. Their depth back from the front face of the screen is another way of thinking about it. If a line is located behind the picture plane and/or tilted in the depth dimension, it will be shown shorter than its length drawn flat on the screen.

The line() functions accept floating point values and can be called with floating point or integer coordinates. Fractional values are rounded to the nearest pixel but casting arguments to integer can be sometimes be useful to smooth jagged parallel line endings e.g:

   line(floatX1, floatY1, (int)floatX2, (int)floatY2); // smooth endings at X2, Y2

Line attribute setters

Three functions set the 'style' of the line that will be drawn by the next and subsequent calls to line(). The effect of calling any one of these functions remains in place until the same function is called again. To be able to revert to a previous value we need to make sure the old values are stored. Line style setters and many other functions that modify the drawing environment have a corresponding variable in the current instance of the Processing application interface, called 'g'. To store the current line colour, for example, we can write

  int oldColour =  g.strokeColor.

Accessing variables using 'dot' notation is discussed later, particularly in Chapter ZZ: Object Oriented Programming. To revert to the old colour write

  stroke(oldColour);

The facility to store and to revert to old settings allows a section of code or a function to draw using settings applicable to the task in hand and restore old settings afterwards - an aid to abstraction discussed later in this Chapter in connection with parametric graphics.

The stroke() line colour setter accepts the same colour and alpha opacity values as the other Processing colour setters detailed earlier in XXXXX. Two other setters affect line drawing: strokeWeight() sets line thickness, strokeCap() the shape or relative location of the end of a line. The program in Listing CC.1 demonstrates the effect of the line style setters.


      /* set window size and drawing environment */

   // declaring constants static final makes sure they 
   // cannot be altered by mistake later in the program
   static final int WIDTH = 200;  
   static final int HEIGHT = 200; 
   static final int OS = 20; // lines offset from edges 

   void setup() { 
      // size(WIDTH, HEIGHT, P2D); 
      // PD2 mode not fully functional in Processing 1.0.2
      // so use: 
      size(WIDTH, HEIGHT);
   }

   /* draw in continuous mode */
   void draw() {
      // fill the window with charcoal grey
      background(0.25 * 255);
       
      /* draw a 45 deg line top-right to bottom-left */
      // set line colour to greyscale white 
      stroke(255);
      // set line width to 12 pixels
      strokeWeight(15);
      // make the ends of the line squared off
      strokeCap(SQUARE); 
      // draw the line
      line(WIDTH - 2*OS, 2*OS, 2*OS, HEIGHT - 2*OS);
      
      /* draw two lines same length, parallel to it */
      // rounded ends
      strokeCap(ROUND);
      
      /* draw a red line 20 pixels wide above */
      strokeWeight(23);
      stroke(255, 0, 0);  // colour red
      line(WIDTH - 3*OS, OS, OS, HEIGHT - 3*OS);
      
      /* draw a green line 20 pixels wide below */
      stroke(0, 255, 0);  // colour green
      line(WIDTH - OS, 3*OS, 3*OS, HEIGHT - OS);
      
      /* draw a blue line 50% opaque, width 20,  
         top-left to the mouse cursor */
      stroke(25, 25, 255, 255 / 2);  
      strokeWeight(25);
      // extend line past cursor point
      strokeCap(PROJECT); 
      line(30, 30, mouseX, mouseY);
   }

Listing CC.1

Figure CC.2 Listing CC.1 running.

Running the program note the effect of the attribute setter functions strokeWeight() and strokeCap() for changing line thickness and the shape or relative location of the end of a line as shown in Figure CC.1. Use the mouse to move the blue line over the other lines and note alpha transparency generally and where the lines intersect. Graphics behind an area of transparent colour may appear lighter or darker according to relative brightness values. Try changing the blue line to white, stroke(255, 255, 255, 255 / 2); colours behind are now lightened.

Parametric Grids

2009-03-26T18:27:00.006Z

The effect of drawing a single line tends to be minimal and it is more likely that many lines will be needed to produce a required effect. In this section we look at a strategy for doing this that extends the repetition facility provided by loops.

Another name for arguments is parameters and parametric graphics is a common feature of vector graphics applications. Using this approach a drawing task is abstracted (taken out) from the main part of the program and done by passing arguments to a function that draws the graphic. Many similar objects can be drawn with different sizes, locations, colours, and other properties determined by values passed to arguments.

Initially we experiment with parametric grids and to do this with a minimum of work the initial step is to set up a basic grid drawing program for testing them out. Optionally the basic structure can be extended to produce actual drawings that include grids. Listing CC.2 shows the outline:


  /* set window size and drawing environment */

  static final int WIDTH = 900; 
  static final int HEIGHT = 600; 

  void setup() {
     size(WIDTH, HEIGHT); // default environment
     doDrawing();
  }
 
  /* draw the drawing */
 
  void doDrawing() {
     // charcole grey background, again!
     background(0.25 * 255);
     // white grid lines
     stroke(255);
     // one pixel wide
     strokeWeight(1);
    
     // draw a grid with number of cells xCells * yCells
     int xCells = 13;
     int yCells = 19;
     drawGrid(0, 0, WIDTH, HEIGHT, xCells, yCells, true);
    
  }

  void drawGrid(int left, int top, int width, int height, int  xCells,
        int yCells, boolean drawOutline){
    
  }

Listing CC.2

As it stands the outline will compile and run but does nothing except opening a window with a grey background. Sections of functionality will be factored off using calls to drawGrid()to draw as many different grids as we require. Such power should be used carefully so the first thing is to decide exactly what we want a drawGrid() function to do and make sure all drawGrids variations we write do just that.

Arguments left and top are where the top-left corner of the grid will be positioned. Width and height specify the size of the grid in pixels, xCells and yCells the number of areas the grid is divided into in the horizontal and vertical directions respectively. Cells are to be made to fit the grid exactly by distributing any odd pixels evenly across cell widths and heights. If draw outline is passed true a one pixel wide line is to be drawn around the grid within the size given. All this sounds complicated but is actually very easy when we divide up the work using functions.

Drawing grids in 2D

2009-03-26T17:01:00.026Z

The code for a 2D drawGrid() can be something like this:


void drawGrid(int left, int top, int width, int height, int  xCells,
              int yCells, boolean drawOutline){

   // precondition for drawing the grid
   if (width <= 0 || height <= 0) return;
         
   // compute the coordinates of the rightmost an bottom pixels
   int right = left + width - 1;
   int bottom = top + height - 1;

   // draw the grid
   drawVertGrid(left, top, right, bottom, width, xCells);
   drawHorzGrid(left, top, right, bottom, height, yCells);

   if (drawOutline){
      // save current line width
      float curWeight = g.strokeWeight;
      // draw outline with a line 1 pixel wide
      strokeWeight(1);
      line(left, top, right, top);
      line(right, top, right, bottom);
      line(right, bottom, left, bottom);
      line(left, bottom, left, top);
      // restore line width
      strokeWeight(curWeight);
   }
}

Listing CC.3

Preconditions for execution

Writing functions it is wise to check that all possible values passed as arguments can be dealt with by the code in the function body. What happens, for example, if drawGrid() is called with zero or negative dimensions passed to width and/or height?

If we see there is a problem a number of options are available. In this case a fully justifiable option is to simply ignore it. We are not trying to create a flawless machine and an emergent property of a program may turn out to be a spectacular work of art. On the other hand, if the code simply does not work a lot of time can be wasted trying to track down the bug.

Another option is to pass the problem on to other functions. Perhaps the grid will be drawn with all or part of it off the screen. This eventuality can be passed on for line() to deal with.

The third option is to write code at the start of the function that checks input is within range. These checks are known as preconditions: execution of other code in the function body is conditional on the checks being passed. There are three ways of dealing with a failed precondition: the function can return immediately to the caller; likewise but it returns a Boolean or some other value indicating success or failure; alternatively an error condition can be created. Java error conditions are dealt with by throwing and catching exception objects, certainly beyond the scope of this Chapter. For drawing grids a simple conditional return statement is appropriate:

      if (width <= 0 || height <= 0) return;

Note that other problems such as zero or negative numbers of cells are passed on to the grid-line drawing functions.

Minimizing coding

Another useful strategy is to avoid writing code that does the same thing more than once. This makes the code run faster but more importantly can make it shorter and easier to read. We are going to draw numerous lines from the left to the right of the grid and from its top to the bottom so compute right and bottom before doing anything else:

      int right = left + width - 1;
      int bottom = top + height - 1;

The next task is to draw the gridlines, done by two functions:

      drawVertGrid(left, top, width, bottom, xCells, constrain);
      drawHorzGrid(left, top, right, height, yCells, constrain);

Finally a one pixel wide outline is drawn around the grid if this option is set having first saved the current line thickness, as shown in Listing CC.3. Drawing the outline, and in calls to the drawing functions, the values of right and bottom computed on entry save numerous calculations.

So, you may be thinking, if working out this stuff early is such a good thing why not do it in the doDrawing() function, pass these values to drawGrid()and maybe make some savings in other functions called from doDrawing()? There are a few reasons for not doing this but the most important relates to abstraction. Working in doDrawing() we should not have to consider the needs of drawGrid() or any other functions called, only what they can do to get the drawing done in terms of the size, shape and location of the objects drawn.

Drawing uniform cells

The tasks to be done by the grid-line drawing functions are: check preconditions, compute cell size, initialise the drawing position to the first grid line and finally, loop while the drawing position is less than the last pixel, drawing each grid line and incrementing position by cell size. Coding these tasks to draw vertical grid lines gets:


void drawVertGrid(int left, int top, int right, int bottom, int width,
                  int xCells){

   // precondition: if negative or zero cells exit now
   if (xCells <= 0) return;

   // compute cell width
   float cellWidth = (float)width / xCells;

   if (cellWidth < 1)
     cellWidth = 1:

   for (float x = left + cellWidth; x < right; x += cellWidth){

     // x is the x-coordinate of the vertical line drawn in the window
     line(x, top, x, bottom);
   }
}

There are two points to watch out for computing cellWidth. The first one is division by zero. Java and Processing allow division by zero for floating point calculations without throwing a fit but an INFINITY result is usually best avoided (do it with integers and a divide by zero exception is thrown). In this case a zero divisor has already been excluded by the precondition: xCells must be greater than zero. Negative and zero values for width were excluded by drawGrid() making certain that cellWidth is positive. If cellWidth was zero or negative adding it to x in the loop would never make x equal to or greater than right and the loop would not exit.

Writing mission critical software - perhaps designed to avoid crashing our lauch vehicle in a nearby swamp or bringing a spacecraft to a perfect landing two miles below the surface - it would be wise to do similar checks in both the caller and the called function. As things stand a single check will do nicely. Excluding a negative value for xCells in drawVertGrid() rather than drawGrid() includes the option that other versions of drawVertGrid() will process such values to get a particular visual effect.

The second point is that Java’s multipurpose division operator returns an integer result when both operands are integers. The drawGrid() specification requires that cells fit the grid. To make this work, cell dimensions need to be floating point values so that when added together fractions of a pixel periodically add up to a whole one. The integer argument width is typecast to(float) getting a floating point result complete with any fractional part. Lastly, if cellWidth is purely fractional, the entire grid will consist of minutely overlapping lines and may take a while to draw. In this case cell width is set to unity.

The drawing loop

Using a for loop keeps lines of code to a minimum. You will recollect that the format of a for loop is generally:


for (initialize loop variable;
   condition for entering or re-entering the loop;
      action to be done at the end of each pass through the loop){

// stuff to be done in the loop goes here

} // end of the loop

At the start of the loop a line at the left of the grid is not required so the loop variable x is declared and initialised to draw the first line at left + cellWidth . Declaring the loop variable in the loop declaration makes it accessible only within the loop, a safety advantage over a while loop in many cases because its value after exit can be somewhat obscure.

Java for loops are not the simple counting loops seen in some other languages. Basically a for loop provides a concise way of writing a while loop by filling in the items inside the round brackets. Ideally the condition for entry or re-entry should specify a range of loop variable values that allows access to the loop - not a single value that when reached by incrementing or decrementing the variable terminates looping: loop while x != right; x += cellWidth, for example. Using an inequality exit condition there is a danger that x will be initialized greater than right permitting unplanned entry or that, due to a fractional initial value and/or an increment greater than or smaller than unity, x steps over an assumed exit value. Result: the loop loops-for-ever. The condition x < right avoids these problems.

The last part of the for loop declaration is executed after each pass through the loop. Here it adds cellWidth to the loop variable using the shorthand += operator to take it to the coordinate of the next grid line (approximately). In this case 'stuff to be done in the loop' is simply to draw the current line going top to bottom. The function that draws horizontal grid lines is similar:


void drawHorzGrid(int left, int top, int right, int bottom, int height,
                  int yCells){

   // precondition: if negative or zero cells exit now
   if (yCells <= 0) return;

   // compute cell height
   float cellHeight = (float)height / yCells;
   if (cellHeight < 1)
      cellHeight = 1;

   for (float y = top + cellHeight; y < bottom; y += cellHeight){

      // y is the y-coordinate of the horizontal line drawn in the window
      line(left, y, right, y);
   }
}

Drawing some grids

2009-03-26T16:18:00.016Z

All done! Make a separate copy of Listing CC.2 by starting a new sketch and pasting the code into the window. Replace the dummy drawGrid() stub with the one in Listing CC.3, type in the drawVertGrid() and drawHorzGrid() functions, save the file with a name of your choice and run the program.
Try changing the number of cells in either or both directions by altering the variables shown in Listing CC.2, make the grid larger or smaller in either or both directions, change its left, top origin and so on. If you only want grid lines running in one direction pass zero for cells in that direction. Optionally, put additional calls in the Listing CC.2 code to draw several grids in different locations, perhaps with different colours and opacities using loops to change line style for calls to drawGrid(). Figure CC.3 shows an example.

Figure CC.3 Effects produced by drawing multiple and overlapping grids.

Drawing unequal cell sizes

Grid line spacing can follow any rule: logarithmic, quadratic, cubic, Fibonacci, etc. or can be random. Another version of drawVertGrid() draws grid lines with logarithmic spacing:


void drawVertGrid(int left, int top, int right, int bottom, int width,
                  int xCells){

   if ( xCells <= 0 ) return;

   int m = xCells + 1;
   float logCells = log(m);
   for (int i = 2; i <= m; i++) {
     int x = left + round(log(i)/logCells * width);
     line(x, top, x, bottom);
   }
}

In this case the loop variable is an integer and values from 2 to m are submitted to the computation to get offsets from the grid's left coordinate. Working out line intervals relies on logm(x) = log(x) / log (m). Log(1) is zero, the grid's left origin, so m is (numCells + 1). Alternatively you may wish to ignore these facts and just look at the nice dynamic that logarithmic spacing gets for any number of lines drawn across the face of a grid.

Figure CC.4
Logarithmic and Circular Grid parametrics.

Using a rule more complex than logarithmic the easiest way to make cell sizes follow the drawGrid() specification for a specified number of cells with an exact fit to the grid is to compute relative sizes and store them them in an array. If predetermined relative sizes are needed to give an effect these values can be assigned when the array is created. The drawing loop simply uses the ratio between the sum of the sizes in the array and the dimension of the grid to work out line positions. Doing this needs slightly more code that the grid-line drawing functions we have investigated at so far and we can return to this variation later.

Posting Computer art and graphics section

2009-03-26T14:45:00.002Z

Having wasted hours pasting text and graphics into the Blogger editor only to have have all the formatting collapse into bold italic decided to post Chunk 36 in bits.
Will do this starting from the last section and blog title as headings.

Sorting Blog

2009-03-16T17:25:00.008Z

Time to try posting something more substantial. Here is one prepared earlier.

This article discusses the merits and otherwise of comparison sorting algorithms in general use based on timings and comparison count data. It was found that performance of a fully optimized quicksort degraded when faced with so called median of three killer data compared with random ordered data but not to the extent that might have been expected. Mergesort was able to sort data with this configuration substantially faster than random data out performing all other algorithms tested and was only marginally slower than quicksort on random data. As noted elsewhere mergesort has an advantage over quicksort when there is any relationship between the key used to obtain an existing ordering and the required key and it is suggested that its additional space requirement is unlikely to be a problem where memory is not at an absolute premium. Mergesort sorts a 1,024,000 item list with a median of three killer configuration in less than 1/3 the time taken by a library function apparently engineered to deal with this type of data and appears to be a median of three killer-Killer.

Comparison Sorting: The State of the Art

One of the problems I have set myself currently is to implement an algorithm to comparison sort a list of random ordered data faster than quicksort. That difficulty comes from a Delphi Magazine article [1] where I suggested that it could be done. This blog reports findings from the article and examines relative performance of quicksort and mergesort to prepare for a look at sorting algorithms written in Java. You never know, something might just drop out.

The main points of the Delphi article were that memory usage was no longer the critical factor it had once been for general sorting on PCs and workstations and that mergesort was the algorithm of choice for sorting certain large data sets. Naturally the scenario under consideration related to Delphi where heap management did not include compaction and the machine stack provided a low overhead location for a buffer, mostly irrelevant to Java but not so the other findings. A library class TList came with a Sort method that accepted a comparison function and used a concise but unoptimized version of quicksort. TList exposes its underlying dynamically allocated array as a read property so that any sorting method can be applied to it.

Mergesort beats quicksort even when carrying the full key . . .

The article quoted a case where a list in StaffNumber within Name order was extracted from a database and sorted - StaffNumber within Name within DepartmentNumber. Numbers were integers and Name was a single-word string. Actual surnames from the UK were used, occurrence weighted based on some token occurrence data. As a stable sort, mergesort could re-sort the list on a single key. Around an 80% sort time reduction was found: mergesort on DepartmentNumber only vs. quicksort on the full key.
An interesting point that came to light was that mergesort still showed better performance even when the full key was used by both algorithms. As conjectured at the time and since confirmed, mergesort's stable characteristic reduced the number of times nested keys were accessed to decide a comparison. Timings for these unoptimized sorting algorithms running on a current desktop machine, maximum department size 500, are:

Mergesort can beat quicksort hands down for many sorting tasks but for a data set with existing ordering unrelated to the required key quicksort has the edge.

Mergesort vs. Quicksort

Mergesort and quicksort are the current algorithms of choice for in-memory comparison sorting. They both divide the list to be sorted into sublists and this approach makes adaption for multiprocessing relatively simple. Quicksort, devised by C.A.R. (Tony) Hoare [2] uses relocation of elements above or below a partition value, initially for the complete list and subsequently for each partitioned sublist. Mergersort, sometimes said to be based on an idea proposed by John von Neumann, uses repeated binary division of the list into sublists, sorts small sublists and merges adjacent sorted sublist pairs.

Quicksort works in place and requires little additional storage but is not stable: relative locations of same key elements are modified. Stable variants of quicksort need storage areas outside the list and using a buffer smaller than the complete list will likely get worse performance than mergesort. Mergesort is inherently stable but an implementation that provides efficiency approximating to quicksort needs a buffer to store items during a merge. Merging with minimum element relocations and therefore best efficiency requires a buffer half the size of the complete list.

Quicksort Nemeses

Quicksort has an average time complexity of O(n log n): on average it will take 2n ln(n) comparisons to sort a list. But, if the heuristic for choosing a partition value or 'pivot' is to use the first element of the list, basic quicksort will use minimum (n² – n) / 2 comparisons to sort a reverse order list or to check that an in-order list does not need any elements moving. This is O( n² ) 'quadratic' complexity, characteristic of the most basic sorting algorithms. Sorting 10000 elements in reverse order takes around 49,995,000 comparisons as opposed to the 184,207 average. An obvious solution is not to use the first element. Why not the middle element for example? The problem with setting the partition value in this way is that there will always be some list arrangements that get quadratic complexity.

Various schemes have been proposed to select a good pivot, including random selection. The more complex a selection scheme the higher its overhead is likely to be and it is hard if not impossible to show that a particular scheme will get complete immunity for all possible input configurations. Median of three selection carries a low-overhead and appears to get superior partitioning for a wide range of list configurations [3]. Three elements are selected, generally the first middle and last element, compared and/or sorted. The median supplies the partition value. The quicksort that I need to beat in the Faster Than Quicksort game uses median of three engineered to get an average overhead of less than one comparison per sublist.

In 1997 David Musser presented an analysis [4] that showed there were a significant number of list configurations that would drive a median of three selection quicksort quadratic: 'Median of Three Killers'. His remedy was to make the sorting algorithm monitor its recursion depth introspectively and if a preset depth was exceeded revert to a guaranteed O(n log n) sort, heapsort or perhaps mergesort. The dual mode algorithm was to be called 'introsort'. More recently it has been suggested that engineered median of three killers could be used to bring down a web-server in a denial of service attack. The current C++ STL sort method is an introsort implementation that reverts to heapsort making it easy to include an example of this approach in a test application, maybe. Ralph Unden [5] has posted a Java class that outputs lists of median of three killer integer values and his paper provides further explanation of the problem with a minimum of mathematical analysis.

Relative Performance

Time taken to sort a list results from the data item comparisons and assignments used together with the amount of supporting processing carried out. Supporting processing includes computation of factors relating to the current list, updating indices, function calls and so on. Counting comparisons etc. gets a platform independent indication of performance but doing this can only be indicative. Suppose that swapping two items is done using a register as a temporary location for example, does this count as two assignments or three? Processing will take about 2/3 of the time needed to swap the items with one item stored temporarily in a buffer. Changes to the ratio of comparison cost to assignment cost and the effect of CPU cache misses are other factors.

The method preferred here is to show actual timings taken under the rules of the Faster Than Quicksort game, which I think give a realistic assessment of relative performance at least for native code on the PC. These rules are simple and designed to make tests relate to working with records and objects rather than lists of numbers. The dynamic is different because even basic comparisons take substantially longer than assignments.

The rules are: Sorting is to be done using a comparison function so that complex keys can substituted. The list holds references to data objects with at least a 32 byte memory footprint so that substantial portions of the in memory arrangement are not covered by a single CPU cache line. Object memory location must not have any sequential relationship with sorted list location. Armed with the timings we can then try to find out what went wrong using comparison counts and other statistics.

Algorithm Timings

Table 1 shows timings for sorting random order lists on a single integer key in milliseconds rounded to 3 decimal places. The rel. columns are performance relative to the fastest (tail call optimized) tcoQuicksort figures in the first column. The test machine is a fairly typical desktop: dual core Pentium® at 3.3GHz, 2GB RAM. For each list size, sortings for 50 different lists, 25 generated using a Random() function and reversing the order of the list, are timed. Each timing uses an initial pass which is discarded and between 5 and 10 timed passes, fewer passes being used for larger lists (no worries, the test application does all this not me). The figure shown is the average but the maximum and minimum times were also recorded, any marked discrepancy leading to retesting to confirm or reject the initial timing.

Results were pretty much as expected. On random data all the sorting methods do considerably better than O(n log2 n) would suggest. No doubt other list configurations would restore the balance. The penalty for using full recursion over tail call optimization is quite small maximizing at 9% for a 4000 item list.

Stable quicksort with its huge list-size buffer finally creeps ahead of its rivals for the largest list. It seems likely that this effect results from separate location of items equal to the partition element by this implementation, excluding them from the sublists passed to the next level. Random generation puts a proportion of records with equal keys in all the lists and for a large list their number may become significant. The maximum key value used is size – 1, hopefully getting a similar proportion of same keys for all list sizes. An in-place quicksort can be implemented to provide separate location and exclusion [6] but some additional overhead is inevitable.

The timings shown are probably a bit unfair on mergesort. Currently the problem is not lack of merge optimizations but may be the assembly language block-move routine used to deal with out of order sublists, still the same as for the Delphi Magazine article. It was always quite crude but changes to CPU architecture since P III have made it even less suitable. Java sort functions use mergesort with a list sized buffer and it will be interesting to see whether performance can be improved using current optimizations and a half-size buffer.

The data for unoptimized TList.Sort shows that optimization is always worthwhile for random data particularly for smaller list sizes. Processing an in-order or reverse order list, Sort fairs better because the partition element is not swapped out to reduce partitioned elements by one. The effect of leaving the partition element in place, a design decision made in [6], needs further investigation.

Timings for the C++ STL sort() function are not shown. It was clearly going to be impossible to get sort() from the current version of the STL to compile on the author's system without far more work than time available permitted, if at all. Data obtained using sort() from the template library supplied with Borland Developer Studio 2006 was so far out of kilter with other timings that it was felt that some effect other than the quality of the algorithm must be responsible. This is a pity because a comparison of timed performance on median of three killer lists would have been informative. As a substitute numbers of calls to the comparison function provide a stand in.

Median of Three Killers

Results are show in Table 2. The four left-hand columns show calls for lists of random data. Comparisons for median of three killer configurations are on the right.

Killer configurations have an adverse effect on tcoQuicksort and TList.Sort. The quicksort used by TList.Sort shows almost quadratic behaviour, a bit unfair seeing the implementation tested uses a middle element pivot not median of three. The effect on tcoQuicksort approximately doubles the number of comparisons needed to sort a list of the same size. The fully recursive version suffers the same fate: its implementation is identical except for the tail call optimization. Taking list size to the next level, sorting a list with 2,048,000 elements tcoQuicksort uses 47,299,055 comparisons on random data and 106,537,288 comparisons on a killer sequence. The ratio remains approximately constant and is not quadratic. Mergesort and the library sort() use fewer comparisons on a killer configuration than on random data, mergesort drastically so. Actual timings showed mergesort sorting the list on an integer key in better than 1/3 the time taken by the library function, tallying with the ratio of comparisons used, and this margin is of course even more substantial for a complex key.

Conclusions

Quicksort provides fast sorting of randomly ordered data but can be affected adversely by certain data configurations. Optimizations may contain this problem for certain configurations or aggravate it for others. For the reason given tcoQuicksort uses around 66 million comparisons to sort a two million item list in reverse order as opposed to about 40 million used by TList.Sort.

Mergesort is a better all-rounder and can sort data ordered with an existing relationship to the required key faster than quicksort. Apparently it is also a Median of Three Killer-Killer! It may be possible to improve performance of the implementation tested here by writing a better block move routine but, because items located at opposite ends of the list to that required are moved late, mergesort can never surpass quicksort for sorting random ordered data.

It seems likely that best proofing against adverse data combined with best sorting speed can be achieved using a tail call optimized quicksort that checks for out of balance partitioning after the initial call and subsequently. An immediate switch to mergesort would reap the benefit of its superior efficiency on killer and other adverse configurations. A mergesort buffer can be allocated on the machine stack at any time during processing: a buffer only relates to a single recursion level and space beyond the stack pointer can be used by the merge routine on the way back to the root of the merge tree. The allocation overhead is minimal, ideally only a matter of checking stack headroom. When there is insufficient headroom to to allocate an optimum size buffer an alternative merging routine that uses available space can be called. If a language does not provide intrinsics for efficient stack allocation perhaps it should do so.

The downside of using two algorithms is that code size is increased. It may be that double sorting time on some data configurations for large lists is acceptable using an optimized quicksort. Alternatively random selection of median of three elements might provide a simple alternative. A local randomization scheme need not be elaborate, say setting the initial seed using a value from the current machine clock and a linear congruential generator on a smallish prime. This approach needs further investigation.

References:

[1] Martin Humby. Buffered Sorting and Stack Buffers. Delphi Magazine Issue 113: January 2005.
[2] C. A. R. Hoare, Quicksort. Computer Journal Vol 5 (1): 10-15. 1962.
[3] Robert Sedgewick, Implementing Quicksort Programs, Communications of the ACM Vol 21(10) 847–857 October 1978.
[4] David R Musser, Introspective Sorting and Selection Algorithms, Computer Science Department, Rensselaer Polytechnic Institute, Troy, NY 12180, U.S.A. 1997.
[5] Ralph Unden, > here < and Implementierung und Untersuchung des introspektiven Sortieralgorithmus Introsort, Berufsakademie Stuttgart - Fachrichtung Informationstechnik, student paper April 2007
[6] Jon L Bently, M Douglas McIlroy: Engineering a Sort Function. Software – Practice and Experience, Vol. 32(11), 1249-1265 November 1993.

No Chance!

2009-03-16T14:52:00.000Z

No chance! - of it working that is. Still get the blank page. With the XML stuff in the code, looks like another 'impedance mismatch' to me. In this case between the XHTML and Blogger's blog engine rather than an application trying to talk to some geriatric DBMS. To paraphrase James May: "Microspeak - Impedance mismatch, English - Cobblers!".

The fact that it works in Preview but not otherwise takes this into the really annoying category but got more important things to do than mess around with it. Found a stretchy version of Minima with the offer of replacing the title bar with a graphic. Computer generated sun, chaotic trees - seems appropriate maybe? What do you think?

Changing Column Widths

2009-03-14T21:52:00.001Z

Don't intend to access this blog from my mobile or would probably have signed up to Twitter so decided to change the column widths to something more reasonable. Clicked on 'Customise' (My dictionary spells it Customize but what can you expect) Edit HTML. Copy the code for Minima, change some numbers, copy it back, click on Preview and . . . Perfect! Just what I wanted! Nearly fell off chair, but then: View Blog: nothing, nix, nil, a blank page.

Go back do it again, scratch head, get a cup of tea. Some time later . . . eventually get an error page: 'This blog does not have any posts. Please add at least one post in order to preview.' Well, they asked for one so here it is. Will it work now? Wouldn't put any money on it!