The metricsink from tarsiswt

No title

Hello,

I'd like to draw your attention to the current implementation of the AbstractFlowSet implementation and its subclasses wrt to the equals/hashCode contract. I've encountered several issues:

Violation of the hashCode contract (equal objects must have the same hashCode).
For example, take the following snippet:

ArraySparseSet ars1 = new ArraySparseSet();
ars1.add("a");
ars1.add("b");

ArraySparseSet ars2 = new ArraySparseSet();
ars2.add("b");
ars2.add("a");

System.out.println(ars1.equals(ars2)); // true
System.out.println(ars1.hashCode() == ars2.hashCode()); // false; violates the hashCode contract

AbstractFlowSet also accepts intertype equality, but fails to comply to the hashCode contract:

ArrayPackedSet aps = new ArrayPackedSet(new CollectionFlowUniverse<String>(Arrays.asList("a","b")));
aps.add("b");
aps.add("a");

System.out.println(ars1.equals(aps)); // true
System.out.println(ars1.hashCode() == aps.hashCode()); // false; violates the hashCode contract

This happens because the hashCode is calculated based on the iteration order, whereas the equals checks for equality independent of order.

One way to fix this could be to relax the hashCode implementation below:

public int hashCode() {
    final int PRIME = 31;
    int result = 1;
    Iterator iter = iterator();
    while(iter.hasNext()) {
        Object o = iter.next();
        result = PRIME * result + o.hashCode();
    }
    return result;
}

to something like:

public int hashCode() {
    int result = 1;
    Iterator iter = iterator();
    while(iter.hasNext()) {
        Object o = iter.next();
        result += o.hashCode();
    }
    return result;
}

One consequence of allowing intertype equality (like the comparisson between ArrayPackedSet and ArraySparseSet above) is that it is very hard to comply with the simmetry clause of the equals contract:

ToppedSet ts1 = new ToppedSet(ars1);
System.out.println(ts1.equals(ars1)); // false
System.out.println(ars1.equals(ts1)); // true; violates the simmetry clause of the equals contract.

And also to comply with the transitivity clause. Suppose the following class:

class MyFlowSet extends ArraySparseSet {
    private int myState = 0;

    public void setState(int state) {
        myState = state;
    }

    @Override
    public boolean equals(Object otherFlow) {
        if (otherFlow instanceof MyFlowSet) {
            MyFlowSet other = (MyFlowSet) otherFlow;
            if (other.numElements != this.numElements || other.myState != this.myState)
                return false;

            for(int i = 0; i < this.numElements; i++)
                if(!other.contains(this.elements[i]))
                    return false;
            return true;    
        }

        return super.equals(otherFlow);
    }

    @Override
    public List toList() {
        return super.toList();
    }
}

Because intertype equality is allowed, the following case can emerge:

MyFlowSet mfs1 = new MyFlowSet();
mfs1.add("a");
mfs1.add("b");

MyFlowSet mfs2 = new MyFlowSet();
mfs2.add("a");
mfs2.add("b");
mfs2.setState(1);

System.out.println(mfs1.equals(ars1)); // true
System.out.println(mfs2.equals(ars1)); // true
System.out.println(mfs1.equals(mfs2)); // false; violates the transitivity clause of the equals contract

I believe that many of these issues could be avoided by separating the object equality from the "content equality", maybe using the EquivTo interface and adjusting the fixed point algorithm, or by disallowing intertype equality. Both of these alternatives will most likely break backwards compatibility wth existing code.

tarsiswt / metricsink Goto Github PK

metricsink's People

Contributors

Watchers

metricsink's Issues

No title

Recommend Projects

React

Vue.js

Typescript

TensorFlow

Django

Laravel

D3

Recommend Topics

javascript

web

server

Machine learning

Visualization

Game

Recommend Org

Facebook

Microsoft

Google

Alibaba

D3

Tencent