Iterator is incorrect after remove on Linear Map

[adamretter]

Sorry to report another one... I am not sure if this bug existed before #23 was fixed, or if it is a regression. I suspect it is related though.

Unfortunately after removing from a LinearMap the iterator over the keys of that map produces the wrong keys.

The test below shows that:

1. starting from new Map<>().linear() works as expected
2. but that starting from new LinearMap<>() causes the wrong keys to be returned by iteration after a remove(key).

import io.lacuna.bifurcan.*;
import org.junit.Test;

import java.util.Iterator;

import static org.junit.Assert.*;

public class BifurcanTest {
    @Test
    public void removeFromLinearMap() {
        final IMap<String, String> map = new LinearMap<>();
        removeRemove(map);
    }

    @Test
    public void removeFromMapConvertedToLinear() {
        final IMap<String, String> map = new Map<String, String>().linear();
        removeRemove(map);
    }

    private void removeRemove(final IMap<String, String> map) {
        storeDays(map);

        final IMap<String, String> allDaysMap = map.forked();  // creates DiffMap from LinearMap (when starting with LinearMap)

        final IMap<String, String> withoutWeds = remove(allDaysMap, "We");
        assertSetEquals(Set.of("Su", "Mo", "Tu", "Th", "Fr", "Sa"), withoutWeds.keys());
        assertSetEqualsByIteration(Set.of("Su", "Mo", "Tu", "Th", "Fr", "Sa"), withoutWeds.keys());

        final IMap<String, String> withoutWedsAndTues = remove(withoutWeds, "Tu");
        assertSetEquals(Set.of("Su", "Mo", "Th", "Fr", "Sa"), withoutWedsAndTues.keys());
        assertSetEqualsByIteration(Set.of("Su", "Mo", "Th", "Fr", "Sa"), withoutWedsAndTues.keys());
    }

    private IMap<String, String> remove(final IMap<String, String> immutableMap, final String... keys) {
        assertTrue( !immutableMap.isLinear());

        // create a mutable map
        IMap<String, String> mutableMap = immutableMap.linear();
        assertTrue(mutableMap.isLinear());

        for (final String key: keys) {
            mutableMap = mutableMap.remove(key);

            assertFalse(mutableMap.contains(key));
            assertFalse(mutableMap.keys().contains(key));

            //TODO(AR) the blow assertion fails where it should not - this is because toString also makes use of Iterator! Should be uncommented when the Iterator is fixed...
//            assertEquals(-1, mutableMap.keys().toString().indexOf(key));
        }

        // return an immutable map
        return mutableMap.forked();

    }

    private void storeDays(final IMap<String, String> map) {
        assertTrue(map.isLinear());

        map.put("Su", "Sunday");
        map.put("Mo", "Monday");
        map.put("Tu", "Tuesday");
        map.put("We", "Wednesday");
        map.put("Th", "Thursday");
        map.put("Fr", "Friday");
        map.put("Sa", "Saturday");

        assertSetEquals(Set.of("Su", "Mo", "Tu", "We", "Th", "Fr", "Sa"), map.keys());
    }

    private static <T> void assertSetEquals(final ISet<T> expected, final ISet<T> actual) {
        assertEquals("Expected equal size", expected.size(), actual.size());
        assertTrue(actual.containsAll(expected));
    }

    private static <T> void assertSetEqualsByIteration(final ISet<T> expected, final ISet<T> actual) {
        assertEquals("Expected equal size", expected.size(), actual.size());

        for (final Iterator<T> itActual = actual.iterator(); itActual.hasNext(); ) {
            final T act = itActual.next();
            assertTrue("`actual` has key '" + act + "', but this is not in `expected`!", expected.contains(act));
        }
    }
}

[ztellman]

Hi Adam, thanks for surfacing this. It turns out my generative tests for the Diff* data structures were a little simplistic, and once I improved them a few issues came to light. I've pushed the improved tests and related fixes, and will cut 0.2.0-alpha4 once I've done an overnight run of the generative tests to make sure there aren't any subtle issues kicking around.

[adamretter]

Great stuff, thanks @ztellman :-)

[adamretter]

Thank you very much @ztellman I can confirm that this now works for us in the 0.2.0-alpha4 release.