MutableSet viewa for MutableMap make no sense

1

I am trying to write a custom TreeMap implementation in Kotlin multiplatform. Everything works fine until I encountered the keys(), values() and entries() methods. These must return views that reflect changes in the underlying map. Similar to Javas TreeMap, I want to implement them as lazy initialized anonymous inner classes like so:

override val keys: MutableSet<K> by lazy {
        object : MutableSet<K> {
               ...
            override fun add(element: K): Boolean {
                TODO("This makes no sense?! WHat value should be added to map?")
            }
        }

However, unlike Java, Kotlins MutableMap interface requires these Sets to be MUTABLE as well, with changes made to the views changing the underlying map itself. This is a problem, since it is unclear how MutableSet’s add() which only specifies a key should modify the map (which needs both a key and a value).
This tension needs to be resolved somehow. For values, this problem is even worse for trying to add or remove values because a value might have multiple keys. I think these views really must be read only (unmutable) even for the MutableMap to not break the Map contract. Is the MutableMap (kotlin.collections.MutableMap) “fixed”? Is this something open to discussion? If not, how are these cases supposed to be handled?

You can take a look at the complete implementation here Daniel63656/SortedCollections: Implementation of Sorted Set and Map in Kotlin (github.com).
Only these view methods are missing.

Edit: I noticed that Java throws UnsupportedOperationException in these cases.

2 Likes
2

Yeah I would just do the same in your implementation, tbh. You’re right that it makes no sense for these Views to be modified. I’m guessing it uses MutableSet for compatibility with Java, perhaps.

3

I doesn’t make sense to add values to these views. You can still remove them!

/**
 * Tests confirming the behavior of the built-in `MutableMap` implementations
 */
class MutableMapTests {
    @Test
    fun testKeysAdd() {
        val mutableMap = mutableMapOf(
            1 to "A",
            2 to "B",
            3 to "C",
        )

        assertIs<UnsupportedOperationException>(
            assertFails {
                mutableMap.keys.add(4)
            },
        )
    }

    @Test
    fun testKeysRemove() {
        val mutableMap = mutableMapOf(
            1 to "A",
            2 to "B",
            3 to "C",
        )

        assertTrue(
            mutableMap.keys.remove(2),
        )

        assertEquals(
            expected = mutableMapOf(
                1 to "A",
                3 to "C",
            ),
            actual = mutableMap,
        )
    }

    @Test
    fun testValuesAdd() {
        val mutableMap = mutableMapOf(
            1 to "A",
            2 to "B",
            3 to "C",
        )

        assertIs<UnsupportedOperationException>(
            assertFails {
                mutableMap.values.add("D")
            },
        )
    }

    @Test
    fun testValuesRemove() {
        val mutableMap = mutableMapOf(
            1 to "A",
            2 to "B",
            3 to "C",
        )

        assertTrue(
            mutableMap.values.remove("C"),
        )

        assertEquals(
            expected = mutableMapOf(
                1 to "A",
                2 to "B",
            ),
            actual = mutableMap,
        )
    }

    @Test
    fun testValuesRemove_duplicates() {
        val mutableMap = mutableMapOf(
            1 to "A",
            2 to "B",
            3 to "C",
            4 to "A",
        )

        assertTrue(
            mutableMap.values.remove("A"),
        )

        assertEquals(
            expected = mutableMapOf(
                2 to "B",
                3 to "C",
                4 to "A", // `remove` removes a "a single instance of the specified element"
            ),
            actual = mutableMap,
        )
    }

    @Test
    fun testKeysIterator() {
        val mutableMap = mutableMapOf(
            1 to "A",
            2 to "B",
            3 to "C",
        )

        val iterator = mutableMap.keys.iterator()

        assertEquals(
            expected = 1,
            actual = iterator.next(),
        )

        iterator.remove()

        assertEquals(
            expected = mutableMapOf(
                2 to "B",
                3 to "C",
            ),
            actual = mutableMap,
        )

        assertEquals(
            expected = setOf(2, 3),
            actual = mutableMap.keys,
        )
    }

    @Test
    fun testValuesIterator() {
        val mutableMap = mutableMapOf(
            1 to "A",
            2 to "B",
            3 to "C",
        )

        val iterator = mutableMap.values.iterator()

        assertEquals(
            expected = "A",
            actual = iterator.next(),
        )

        iterator.remove()

        assertEquals(
            expected = mutableMapOf(
                2 to "B",
                3 to "C",
            ),
            actual = mutableMap,
        )

        assertEquals(
            expected = setOf(2, 3),
            actual = mutableMap.keys,
        )
    }

    @Test
    fun testEntriesIteratorRemove() {
        val mutableMap = mutableMapOf(
            1 to "A",
            2 to "B",
            3 to "C",
        )

        val iterator = mutableMap.entries.iterator()

        val firstEntry = iterator.next()

        assertEquals(
            expected = 1,
            actual = firstEntry.key,
        )

        assertEquals(
            expected = "A",
            actual = firstEntry.value,
        )

        iterator.remove()

        assertEquals(
            expected = mutableMapOf(
                2 to "B",
                3 to "C",
            ),
            actual = mutableMap,
        )

        val secondEntry = iterator.next()

        assertEquals(
            expected = 2,
            actual = secondEntry.key,
        )

        assertEquals(
            expected = "B",
            actual = secondEntry.value,
        )

        secondEntry.setValue("B2")

        assertEquals(
            expected = mutableMapOf(
                2 to "B2",
                3 to "C",
            ),
            actual = mutableMap,
        )
    }
}

I’m not judging whether this is a good and/or useful API. It’s definitely under-documented, as I had to rely on these tests to determine the expected behavior. I would assume that this behavior is binding in practice and will not change in any minor version of Kotlin.

4

It’s an extremely surprising coincidence that I found this thread, as I was implementing a TreeMap myself, too. A TreeMap based on an order statistic tree!

What balancing strategy do you use for your implementation? Is it weight-balancing?

I can share the details, if you’d like, as my order statistic tree implementation is quite atypical, being a variant that, strictly speaking, is not a binary search tree at all.