Word Dictionary using a Trie Structure

TestTrieDictionary.kt

import org.junit.jupiter.api.Assertions.assertEquals
import org.junit.jupiter.api.Test

class TestTrieDictionary {

    @Test
    fun `inserts and finds words properly`() {
        val dict = TrieDictionary()
        val words = listOf<String>(
                "app",
                "apple",
                "a",
                "cat",
                "catalogue",
                "camp",
                "campy"
        )
        words.forEach { word -> dict.insert(word) }
        assertEquals(false, dict.search("application"))
        assertEquals(false, dict.search("appl"))
        assertEquals(true, dict.search("app"))
        assertEquals(true, dict.search("apple"))
        assertEquals(true, dict.search("a"))
        assertEquals(false, dict.search("catal"))
        assertEquals(false, dict.search("cats"))
        assertEquals(true, dict.search("camp"))
        assertEquals(true, dict.search("campy"))
        assertEquals(false, dict.search("camps"))
        assertEquals(false, dict.search(""))
    }

    @Test
    fun `matches intermediate terminals correctly`() {
        val dict = TrieDictionary()
        val words = listOf<String>(
                "app",
                "apple",
                "a",
                "cat",
                "catalogue",
                "camp",
                "campy"
        )
        words.forEach { word -> dict.insert(word) }
        val indexes = dict.findMatchingIndexes("apple")
        assertEquals(listOf(0, 2, 4), indexes)
        assertEquals(listOf(2, 8), dict.findMatchingIndexes("catalogued"))
        assertEquals(listOf<Int>(), dict.findMatchingIndexes("zebra"))
        assertEquals(listOf<Int>(), dict.findMatchingIndexes(""))
    }

}

TrieDictionary.kt

class TrieDictionary {

    data class Node(
            val terminal: Boolean = false, // this Node terminates a word
            val children: MutableMap<Char, Node> = mutableMapOf<Char, Node>()
    )

    private val rootNode = Node()

    fun insert(word: String) = insert(word, rootNode)

    private fun insert(word: String, node: Node) {
        val isTerminal = word.length == 1
        var charNode = node.children.computeIfAbsent(word[0]) { char ->
            Node(isTerminal)
        }
        if (isTerminal && !charNode.terminal) {
            charNode = Node(isTerminal, charNode.children)
            node.children.put(word[0], charNode)
        }
        if (!isTerminal) {
            insert(word.substring(1), charNode)
        }
    }

    fun search(word: String): Boolean = search(word, rootNode)

    private fun search(word: String, node: Node): Boolean {
        if (word.length == 0) return false
        return node.children.get(word[0])?.let { charNode ->
            (word.length == 1 && charNode.terminal) || search(word.substring(1), charNode)
        } ?: false
    }

    fun findMatchingIndexes(word: String): List<Int> = findMatchingIndexes(word, rootNode, 0, listOf<Int>())

    private fun findMatchingIndexes(word: String, node: Node, index: Int, matches: List<Int>): List<Int> {
        if (word.length == 0) return matches
        return node.children.get(word[0])?.let { charNode ->
            val newMatches = if (charNode.terminal) matches + listOf<Int>(index) else matches
            findMatchingIndexes(word.substring(1), charNode, 1 + index, newMatches)
        } ?: matches
    }

}

This is based on https://gist.github.com/prettymuchbryce/3719435