.equals is wrong on TIntLongHashMap

Issue #20 new
rjwittams
created an issue

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;
        }

    }

Comments (6)

  1. rjwittams reporter

    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

  2. Sascha

    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;
        }
    
  3. Log in to comment