<@U5UU34LPK> <@U10EJRH2L> the purpose of the trie ...

# announcements

[lab]

@karelpeeters @Ruckus the purpose of the trie was for indexing and searching apps in an Android launcher. (The repo is at https://github.com/louisgv/janusLauncher)

I'm refactoring the trie to return a List<AppModel> (AppModel store all necessary info of an Android app). Here's the getLeaves method that I'm testing around with:

class WakeTrieNode (val key: Char?,
                    val value: AppModel?,
                    var isLeaf: Boolean,
                    val children: MutableMap<Char, WakeTrieNode> = mutableMapOf()) {

    fun getLeaves(): List<AppModel>{
        return if (isLeaf && value != null) listOf(value)
        else children.flatMap { child ->
            child.value.getLeaves()
        }
    }
}

Is there a better way to do this? The part where it return listOf(value) seems bad to me.

[karelpeeters]

Why are those things in a trie exactly?

[Ruckus]

You're potentially creating an merging many lists. You may want to benchmark your results to see, but it may be more performant to pass in a mutable list and just append to it.

[karelpeeters]

They're mostly used to store text more compactly, but you're undoing that by having a bunch of maybe not null fields per node.

[karelpeeters]

Now that I think about it they're probably not useful at all with a Node class, they're meant for file storage or more "bare metal" languages.

[lab]

@karelpeeters the key is for trie traversal, the value is to return the AppModel.

[lab]

when searching for a certain app, it uses the key to traverse, which I assume should be fairly fast since it won't be dealing with value.

[karelpeeters]

I'd just have a val apps: List<App>, and then I'd do val results = apps.filter { it.name.startsWith(query) }.

[karelpeeters]

I think this will perform way better then the trie one.

[lab]

@karelpeeters hah, that's exactly what I'm doing actually 😛 https://github.com/louisgv/janusLauncher/blob/master/launcher/app/src/main/java/com/blueberry/lab/januslauncher/MainActivity.kt#L38

[lab]

instead of startsWith I'm using contain

[karelpeeters]

And if you want to improve reaction time while typing you can filter the previous list. And you can even keep a Stack of semi-filtered lists. I'll stop, I'm getting too exited 🙂.

[lab]

performance wise it's pretty good, tho some friends of mine suggest making a trie and see if it could get better

[lab]

@karelpeeters oh that's an awesome idea

[karelpeeters]

contains is probably better indeed, you might even want to look into string metrics: https://en.wikipedia.org/wiki/String_metric.