_K__V_HashMap.TValueView.remove is implemented incorrectly

Issue #25 resolved
Tim Wilson created an issue

Currently implemented as

        public boolean remove( #v# entry ) {
            #v#[] values = _values;
            #k#[] set = _set;

            for ( int i = values.length; i-- > 0; ) {
                if ( ( set[i] != FREE && set[i] != REMOVED ) && entry == values[i] ) {
                    removeAt( i );
                    return true;
                }
            }
            return false;
        }

Should be implemented as

        public boolean remove( #v# entry ) {
            #v#[] values = _values;
            byte[] states = _states;

            for ( int i = values.length; i-- > 0; ) {
                if ( ( states[i] != FREE && states[i] != REMOVED ) && entry == values[i] ) {
                    removeAt( i );
                    return true;
                }
            }
            return false;
        }

Comments (6)

  1. Tim Wilson reporter

    Both of these assertions would fail.

    TLongLongHashMap map = new TLongLongHashMap();
    map.put(2L, 10L);
    boolean removed = map.valueCollection().remove(10L);
    Assert.assertTrue(removed);
    Assert.assertTrue(map.isEmpty());
    
  2. Jean-Yves Tinevez

    Hi all, We would like to confirm the bug on our side. Overtime the key '2' is used in such maps, the valueCollection().remove() method will fail for the value associated with this key. The reasons reported by Tim are correct.

    Here is another JUnit test case.

    @Test
        public void test()
        {
            final TIntIntHashMap map = new TIntIntHashMap( 10, 0.5f, -100000, -2000000 );
    
            map.put( 1, 0 );
            map.put( 2, 5 );
            map.put( 3, 2 );
            map.put( 4, 3 );
    
            final TIntCollection values = map.valueCollection();
            final int initSize = values.size();
    
            final boolean removed0 = values.remove( 5 );
            assertTrue( "Could not remove an existing value.", removed0 );
            assertEquals( "Value collection has not been shrinked by iterator.remove().", initSize - 1, values.size() );
            assertEquals( "Corresponding map has not been shrinked by iterator.remove().", initSize - 1, map.size() );
    
        }
    
  3. Log in to comment