How can I iterate through nested HashMaps in Kotlin?-CodePudding

I am new to Kotlin, and I am having trouble finding an idiomatic way to translate the snippet of Python below into Kotlin. Let's say that I have a list of words that I am trying to insert into a Trie data structure, represented as nested dictionaries in Python. Terminal nodes in the Trie will be marked simply by adding the key # to that level of the dictionary.

trie = {}
for word in words:
    cur = trie
    for letter in word:
        if letter not in cur:
            cur[letter] = {}
        cur = cur[letter]
    cur['#'] = {}

For the input words: ["test","this","trie"] you would get the following representation:

{'t': {'e': {'s': {'t': {'#': {}}}}, 'h': {'i': {'s': {'#': {}}}}, 'r': {'i': {'e': {'#': {}}}}}}

I have tried the following, in Kotlin:

val trie: MutableMap<Char, MutableMap<Char, Any>> = mutableMapOf()
for (word in words) {
    var cur = trie
    for (letter in word) {
        if (!cur.containsKey(letter)) {
            cur[letter] = mutableMapOf()
        }
        cur = cur[letter]
    }
    cur['#'] = mutableMapOf()
}

However, this gets me the following compilation error:

error: type mismatch: inferred type is MutableMap<Char, Any>? but MutableMap<Char, MutableMap<Char, Any>> was expected
        cur = cur[letter]

I am aware that I could explicitly create Node objects which contain a HashMap pointing to other Nodes to represent the Trie, however I am interested in understanding if there would be a way to represent the Trie as a HashMap of HashMaps in Kotlin as I did above in Python.

CodePudding user response：

Yes, at the cost of all type safety.

Just to emphasize, what you've already pointed out in your question is the correct approach. You should absolutely make a Node dataclass that contains a hashmap pointing to the additional nodes. This is the correct recursive data structure for this job. What follows is the wrong way to solve this problem.

But you asked for an infinitely nested hashmap. We can always store whatever data we want into a HashMap if the value type is Any.

val trie: MutableMap<Char, Any> = mutableMapOf()

Now Kotlin doesn't have nearly enough type information to figure out what our inner maps look like, so we have to add annotations to those.

cur[letter] = mutableMapOf<Char, Any>()

and

cur['#'] = mutableMapOf<Char, Any>()

Finally, when we "zoom in" on a nested map, we'll get an Any. We're just going to quietly cast that to MutableMap<Char, Any>, and nobody will notice.

cur = cur[letter] as MutableMap<Char, Any>

Complete example:

fun main(args: Array<String>) {
  val words = listOf("test", "this", "trie")
  val trie: MutableMap<Char, Any> = mutableMapOf()
  for (word in words) {
    var cur = trie
    for (letter in word) {
      if (!cur.containsKey(letter)) {
        cur[letter] = mutableMapOf<Char, Any>()
      }
      cur = cur[letter] as MutableMap<Char, Any>
    }
    cur['#'] = mutableMapOf<Char, Any>()
  }
  println(trie)
}

CodePudding user response：

Possible interpretation of Silvio's answer as a type safe version:

val words = listOf("test", "this", "trie")

data class Node(
  var char: Char? = null,
  val children: MutableMap<Char, Node> = mutableMapOf()
) {
  override fun toString(): String = children.onEach { it.toString() }.toString()
}

val root = Node()

words.forEach { word ->
  var currentNode = root
  word.forEach { char ->
    if (!currentNode.children.contains(char)) {
      currentNode.children[char] = Node(char)
    }
    currentNode = currentNode.children[char]!!
  }
  currentNode.children['#'] = Node()
}

println(root)

// Output: {t={e={s={t={#={}}}}, h={i={s={#={}}}}, r={i={e={#={}}}}}}