a simple navigation lib (can hardly be called one), that can work on any platform/application e.g., CLi, Gui apps.

Navigation.kt

package kotlinplayground

// a simple navigation lib (can hardly be called one), that can work on any platform/application e.g., CLi, Gui apps.
// adaptation to gui applications such as jetpack compose should be fairly simple, given the examples and explanation
// given

/**
 * visualize navigation as a tree made up of branches and leaves (the branches can be considered
 * as leaves because ultimately a branch must contain a leaf and other leaves)
 * So the term branch is used interchangeably with leaf.
 * a branch is a part of the tree, and it contains leaves or even just a leaf;
 * in android, the branch can be a screen containing other screens. The other screens are basically leaves
 * As an example, consider main-screen that has a button that goes to profile-screen
 * the profile-screen is main-screen's child/leaf.
 * Each branch or leaf has unique id. And the leaves will be prioritized
 * in the order of addition, so basically, they will be stacked on top of each other
 * since in android and most ui-systems support stack like navigation.
 * So the most recent leaf/branch will be the one on top of the stack
 */
interface Leaf{
    val screenId:String
    // leaves basically
    val leaves:List<Leaf> get() = listOf()
}

/**
 * Like in any tree, you can start traversing the tree at the top/bottom
 * ideally therefore, it can be breadth first, or depth first
 */
sealed interface NavigationOrder{
    data object BreadthFirst:NavigationOrder
    data object DepthFirst:NavigationOrder
}

/**
 * when we are going through a branch's leaves, the receiver of this function
 * acts the parent of the subsequent leaves/basically the starting point.
 * So we start traversing from [this] all the way down/or all the way up
 */
inline fun Leaf.traverse(navigationOrder: NavigationOrder,crossinline  onLeafVisited:(Leaf)->Unit){
    when(navigationOrder){
        NavigationOrder.BreadthFirst -> {
            // will act as our queue, by removing items at the front then adding them later
            val leafQueue = mutableListOf(this)
            while (leafQueue.isNotEmpty()){
                // de-queue our queue
                val leaf = leafQueue.removeAt(0) // remove first
                // visit leaf
                onLeafVisited(leaf)
                // add leaves that may be present at the removed leaf
                for (foundLeaf in leaf.leaves){
                    leafQueue.add(foundLeaf)
                }
            }
        }
        NavigationOrder.DepthFirst   ->{
            // we need to traverse along one branch/vertex first, then we
            // backtrack and jump to the next available branch
            val stack = mutableListOf(this)
            while (stack.isNotEmpty()){
                // remove the last item on the stack
                val visitedLeaf = stack.removeAt(stack.lastIndex)
                onLeafVisited(visitedLeaf)
                for (i in visitedLeaf.leaves.lastIndex downTo  0){
                    stack.add(visitedLeaf.leaves[i])
                }
            }
        }
    }
}

/**
 * represent a single navigation component (single leaf in the tree) which is basically a screen
 * the single leaf can contain multiple leaves which are its children. In ui-terms, the leaf is a screen and has multiple
 * paths that can be followed as an example consider the following:
 *             main-screen/
 *                     - profile-screen
 *                     - settings-screen
 *                     - ui-screen
 * Initially, the stack component needs to have a screen, just like android's official navigation library,
 * else nothing really will be shown. Then as time goes on you can push/add screens to its.
 * Each added screen will be associated with the parent-screen/leaf. Example, for the main-screen, if we add profile-screen,
 * profile-screen will be associated with main-screen. Thus, the latter, will be parent-screen and the former child-screen
 **/
data class StackComponent(val pathName:String,
                          override val leaves:
                          List<Leaf> = listOf()):Leaf{
    override val screenId: String
        get() = pathName
}
/* push a leaf to the stack component; single-top basically have only that typeof screen */
fun StackComponent.addLeaf(leaf: Leaf?,singleTop:Boolean=true):StackComponent = when{
    // if the leaf to be added is the most recent leaf, don't do anything
    // e.g, when you are navigating to a screen that's already on the stack
    leaf==null -> this
    leaves.lastOrNull()==leaf->this
    singleTop->{
        copy(leaves = leaves.minus(leaf)+leaf)
    }
    else-> copy(leaves = leaves+leaf)
}
/* switches to the specified leaf */
fun StackComponent.switchToLeaf(leaf:Leaf?):StackComponent{
    // we are switching to the current stack, so just return the stack
    // this is done as a check to prevent un-necessary operations
    return when (leaf) {
        null -> this
        leaves.lastOrNull() -> this
        else                ->
        {
            // drop the last leaf (most recent leaf)
            // return a new stack component thus ensuring immutability
            copy(leaves =leaves.dropLast(1)+leaf)
        }
    }
}
// useful when we are popping nodes from stack, so remove the top-node from the stack
// only if our stack's size >1/we are instructed to remove last. E.g.,single-top type of screens
// a perfect example is when the screen is one-time screen like OTP-verification screen, no need to retain it in stack
fun StackComponent.removeLeaf(isRemoveLast:Boolean=false):StackComponent{
    return if (!isRemoveLast && leaves.size==1) { this }
    else copy(leaves = leaves.dropLast(1))
}
// checks if we can remove paths from this screen
fun StackComponent.canPopLeaf() = leaves.size>1
// since this is a stack, the current leaf is the last one
val StackComponent.currentLeaf get() = leaves.lastOrNull()

/*If we are to represent actual paths, we need a way of making the paths carry data/have data.
Additionally, we need a method to match and discern the route-patterns given. A route pattern is a pattern that a path can take.
As an example, if we are in screen1, going to screen2 (that needs an id) can be described as screen1/screen2/1. So that's the path.
In form of pattern, we can say screen1/screen2/{id}. Say, screen 2 required query like arguments like screen1/screen2?name=John,
our pattern would be screen1/screen2?{key}={name}.
So naturally, we will emulate website's path
example. Screen1->settings-screen
                   profile-screen
 screen1 therefore has two paths: screen1/settings-screen and screen1/profile-screen
 Thus, if we need to pass data from screen1 to settings-screen, we can append query-like params to the path
 as so screen1/settings-screen?name=Joe. So in settings-screen, we can get hold of value of name and use it as we like
 also, a screen's path can have arguments like so screen1/profile-screen/1 (just like in web).  The 1 basically represents an argument.

 Consequently, we need two things: a url-matcher that will validate a screen's pattern against a screen path - pattern must be
 compatible to the path; and a url-parser that basically takes in a screen in form of string-path, and gives us a valid and existing
 screen from our stack.
 */

// uri-matchers

/*a route is like a stack component but has arguments/params: a path-name, can take an argument in its path
and can take parameters. It is a basic modification of leaf. So leaf screenId will always be the
routeName */
interface Route:Leaf{
    override val screenId: String
        // supposed to be unique
        get() = routeParams.routeName
    val routeParams:RouteArguments
}

typealias PathArgument = Map<String,String>
typealias QueryParameter= Map<String,List<String>>
data class RouteArguments (
    val routeName:String,
    val pathArgument:PathArgument,
    val queryParameter:QueryParameter)

/* it is supposed to parse a route string into a concrete route/leaf containing the
* path argument, query param */
typealias RouteParser = (routeString:String)->Route?

/* maps the route params i.e., argument and queries into a concrete route type */
typealias RouteMapper = (routeArguments:RouteArguments)->Route
typealias Patterns = List<String>
typealias PathKeys = List<String>

data class RouteMatcherObjects(val pathKeys: PathKeys,val patterns:Patterns, val routeMapper:RouteMapper)
/*when given a pattern like screen-1/profile/{id}?key1=value1, we need to come up with
a concrete route object. So ideally, this matches the url-like route pattern into something concrete*/

typealias RouteMatcher = ()->RouteMatcherObjects

// uri-matcher implementation/logic inspired by @tunjid <_ * _>
fun routeMatcherFrom(urlRoutePattern:String,routeMapper:RouteMapper):RouteMatcher = object:RouteMatcher{
        override fun invoke(): RouteMatcherObjects {
            val pathKeys = mutableListOf<String>()
            // extract path keys such as {id} or {name} from the url-like route pattern
            // our route pattern is something like this /users/{userId}/posts/{postId}, so match all occurrences of {.*?}
            val basicRoutePattern=urlRoutePattern.replace("\\{(.*?)\\}".toRegex()){matchResult ->
                val pathKey=matchResult.value.replace("[{}]".toRegex(), replacement = "")
                // remove the curly braces, and add the path key
                pathKeys+=pathKey
                // replace the curly braces with (.*?)
                "(.*?)"
            }
            // recognize both path-arg and key-value
            val patterns = listOf("$basicRoutePattern\\?(.*?)",basicRoutePattern)
            return RouteMatcherObjects(pathKeys, patterns, routeMapper)
        }
    }

// create a specific route-parser from a list of matchers
fun parseFrom(matchers:List<RouteMatcher>):RouteParser{
    val regexes=matchers.fold(mapOf<Regex,RouteMatcher>()){map,parser->
        // make each valid pattern a regex, which we will use to test the route-strings against our recognized
        // url patterns
        map + parser().patterns.map { Regex(it) to parser}
    }

    return object :RouteParser{
        /* a route string here is a complete url-pattern with arguments e.g., /users/1/posts/2
        * the route-string can match either of the two recognized patterns i.e., /user/1 or /user/1?key=value...*/
        override fun invoke(routeString: String): Route?{
            // return the first valid pattern that can match our route
            val validPattern=regexes.keys.firstOrNull { it.containsMatchIn(routeString) } ?: return null
            // proceed to match the entire routeString against our pattern, if it's a false positive, return null
            // match result here contains a mixture of path args, and query-args
            val matchResult = validPattern.matchEntire(routeString) ?: return null
            // not a false positive, proceed to create the full route by using routeMatcher's routeMapper
            val routeMatcher = regexes.getValue(validPattern)()
            val routeMapper = routeMatcher.routeMapper

            // for the path-args, we construct them using the routeMatcher's path-keys, now the trick lies here, for every
            // route we have patterns that match with it: the pattern can be either route/{pathArgument} or route/{pathArgument}?key=value

            return routeMapper(RouteArguments(pathArgument=routeMatcher.pathKeys
                .zip(matchResult.groupValues.drop(1)) // groupValue's index start at 1 not 0
                .toMap(),
                queryParameter = matchResult.groupValues.lastOrNull()?.queryParams() ?: mapOf(),
                routeName = routeString))
        }
    }
}
// get query params from a string.
private fun String.queryParams(): Map<String, List<String>> {
    val result = mutableMapOf<String, List<String>>()
    val pairs = split("&")
    pairs.forEach { keyValueString ->
        val keyValueArray = keyValueString.split("=")
        if (keyValueArray.size != 2) return@forEach
        val (key, value) = keyValueArray
        result[key] = result.getOrPut(key, ::listOf) + value
    }
    return result
}


fun test(){
    data class WelcomeScreen(override val routeParams: RouteArguments):Route

    fun main(){
        var screenStack = StackComponent("WelcomeScreenStack")
        val welcomeScreenWithIdMatcher=routeMatcherFrom("welcome-screen/{id}"){ WelcomeScreen(routeParams = it) }
        val welcomeScreenWithQueryMatcher = routeMatcherFrom("welcome-screen/{id}?{query}={name}"){WelcomeScreen(routeParams = it)}
        val routeParser=parseFrom(listOf(welcomeScreenWithIdMatcher,welcomeScreenWithQueryMatcher))
        val constructedWelcomeScreenWithId=routeParser("welcome-screen/1")
        val constructedWelcomeScreenWithQuery=routeParser("welcome-screen/1?query=Jack&query=John")
        println("[*] simulating app-start up. Screen is stack is empty>${screenStack.leaves.isEmpty()}")
        println("[*] simulating initial navigation stack population")
        screenStack=screenStack.addLeaf(constructedWelcomeScreenWithId)
            .addLeaf(constructedWelcomeScreenWithQuery)

        println("[*]added screens' route params> ${constructedWelcomeScreenWithId?.routeParams}\n${constructedWelcomeScreenWithQuery?.routeParams}")
        println("[*] our current screen stack has the following screens> ${screenStack.leaves.joinToString("\n")}")
        // should be true
        println("[*] current screen shown is welcome-screen with query> ${screenStack.currentLeaf?.screenId == constructedWelcomeScreenWithQuery?.screenId}")
        // switch to another screen
        println("navigating back to welcome-screen that takes id")

        screenStack=screenStack.switchToLeaf(constructedWelcomeScreenWithId)
        println("[*] now showing welcome-screen that takes id>${screenStack.currentLeaf?.screenId==constructedWelcomeScreenWithId?.screenId}")

        // popping off the screen
        screenStack=screenStack.removeLeaf()
        println(screenStack.leaves.size)
        println("[*] simulating back navigation. Screen popped off and stack only has 1 screen> ${screenStack.leaves}")
        // adding again
        println("[*] simulating forward navigation. Adding screen to our stack again")
        screenStack=screenStack.addLeaf(constructedWelcomeScreenWithId)
        println("[*] current screens in our stack> ${screenStack.leaves}")
    }
}