.equals is wrong on TIntLongHashMap

[rjwittams]

This probably affects other maps too.

The problem is the treatment of no entry values, it does not consider all the combinations.

The current impl is :

/** {@inheritDoc} */
    @Override
    public boolean equals( Object other ) {
        if ( ! ( other instanceof TIntLongMap ) ) {
            return false;
        }
        TIntLongMap that = ( TIntLongMap ) other;
        if ( that.size() != this.size() ) {
            return false;
        }
        long[] values = _values;
        byte[] states = _states;
        long this_no_entry_value = getNoEntryValue();
        long that_no_entry_value = that.getNoEntryValue();
        for ( int i = values.length; i-- > 0; ) {
            if ( states[i] == FULL ) {
                int key = _set[i];
                long that_value = that.get( key );
                long this_value = values[i];
                if ( ( this_value != that_value ) &&
                     ( this_value != this_no_entry_value ) &&
                     ( that_value != that_no_entry_value ) ) {
                    return false;
                }
            }
        }
        return true;
    }

A correct impl is:

 /** {@inheritDoc} */
        @Override
        public boolean equals( Object other ) {
            if ( ! ( other instanceof TIntLongMap) ) {
                return false;
            }
            TIntLongMap that = ( TIntLongMap ) other;
            if ( that.size() != this.size() ) {
                return false;
            }
            long[] values = _values;
            byte[] states = _states;
            long this_no_entry_value = getNoEntryValue();
            long that_no_entry_value = that.getNoEntryValue();
            for ( int i = values.length; i-- > 0; ) {
                if ( states[i] == FULL ) {
                    int key = _set[i];
                    long that_value = that.get( key );
                    long this_value = values[i];
                    if ( this_value == this_no_entry_value){
                       if( that_value != that_no_entry_value){
                          return false;
                       }
                    }else if( that_value == that_no_entry_value ) {
                        return false;
                    }else if(  this_value != that_value ){
                        return false;
                    }
                }
            }
            return true;
        }

    }

[Rob Eden]

Do you have a test case handy so I can verify a fix?

[rjwittams]

We found this during upgrade from Trove 2 to Trove 3.

( The remove vs removeAt also caused massive headaches, I think this really should be prominently mentioned... )

Don't have a small test case. The problem should occur with something like ( untested):

TIntLongHashMap map1 = new TIntLongHashMap(); map1.put(1, 0L); map1.put(2, 0L);

TIntLongHashMap map2 = new TIntLongHashMap(); map2.put(1, 1L); map2.put(2, 1L);

map2.equals(map1);

Basically, a map with the same number of keys, a no entry value wll never cause an equals failure

[S]

i suggest that equals ignores no_entry_value and checks for existing keys.

i think this test should pass https://gist.github.com/bitkid/5854451

in templates/gnu/trove/map/hash/_K__V_HashMap.template maybe something like this?

/** {@inheritDoc} */
    @Override
    public boolean equals( Object other ) {
        if ( ! ( other instanceof T#K##V#Map ) ) {
            return false;
        }
        T#K##V#Map that = ( T#K##V#Map ) other;
        if ( that.size() != this.size() ) {
            return false;
        }
        #v#[] values = _values;
        byte[] states = _states;
        for ( int i = values.length; i-- > 0; ) {
            if ( states[i] == FULL ) {
                #k# key = _set[i];
                if (that.containsKey( key )) {
                    #v# that_value = that.get( key );
                    #v# this_value = values[i];
                    if (  this_value != that_value ){
                        return false;
                    }
                } else {
                    return false;
                }
            }
        }
        return true;
    }

[jimdavies]

Whilst this is a separate bug, and I'll leave it as such, this is actually the same bug as #4. Therefore I'll fix it at the same time as #4.

The suggested fixes look correct, but I'll also add tests to make sure that the solutions fix the bug, and that confirm all the error cases.