<commit_before>package katas.kotlin.graph

import katas.kotlin.graph.Graph.Node
import katas.kotlin.shouldEqual
import kotlincommon.join
import org.junit.Test
import java.util.*

class Traversal8 {
    @Test fun `depth-first traversal`() {
        "[a]".toGraph().let {
            it.dft("a") shouldEqual "a"
            it.dft("x") shouldEqual ""
        }
        "[a-b]".toGraph().let {
            it.dft("a") shouldEqual "a-b"
            it.dft("b") shouldEqual "b-a"
            it.dft("x") shouldEqual ""
        }
        "[a-b, b-c]".toGraph().let {
            it.dft("a") shouldEqual "a-b-c"
            it.dft("b") shouldEqual "b-a-c"
            it.dft("c") shouldEqual "c-b-a"
            it.dft("x") shouldEqual ""
        }
        // a──b1──c
        // └──b2──┘
        "[a-b1, a-b2, b1-c, b2-c]".toGraph().let {
            it.dft("a") shouldEqual "a-b1-c-b2"
            it.dft("b1") shouldEqual "b1-a-b2-c"
            it.dft("b2") shouldEqual "b2-a-b1-c"
            it.dft("c") shouldEqual "c-b1-a-b2"
        }
    }

    @Test fun `breadth-first traversal`() {
        "[a]".toGraph().let {
            it.bft("a") shouldEqual "a"
            it.bft("x") shouldEqual ""
        }
        "[a-b]".toGraph().let {
            it.bft("a") shouldEqual "a-b"
            it.bft("b") shouldEqual "b-a"
            it.bft("x") shouldEqual ""
        }
        "[a-b, b-c]".toGraph().let {
            it.bft("a") shouldEqual "a-b-c"
            it.bft("b") shouldEqual "b-a-c"
            it.bft("c") shouldEqual "c-b-a"
            it.bft("x") shouldEqual ""
        }
        // a──b1──c
        // └──b2──┘
        "[a-b1, a-b2, b1-c, b2-c]".toGraph().let {
            it.bft("a") shouldEqual "a-b1-b2-c"
            it.bft("b1") shouldEqual "b1-a-c-b2"
            it.bft("b2") shouldEqual "b2-a-c-b1"
            it.bft("c") shouldEqual "c-b1-b2-a"
        }
    }


    private fun <Value, Label> Graph<Value, Label>.dft(value: Value): String {
        return (this.nodes[value] ?: return "").dft().join("-")
    }

    private fun <Value, Label> Graph<Value, Label>.bft(value: Value): String {
        return (this.nodes[value] ?: return "").bft().join("-")
    }

    data class Frame<Value, Label>(val node: Node<Value, Label>, val path: LinkedHashSet<Node<Value, Label>>)

    private fun <Value, Label> Node<Value, Label>.dft(): LinkedHashSet<Node<Value, Label>> {
        val stack = LinkedList<Frame<Value, Label>>()
        stack.add(Frame(this, LinkedHashSet()))
        while (stack.isNotEmpty()) {
            val frame = stack.removeLast()
            if (!frame.path.contains(frame.node)) {
//                stack.add(Frame())
            }
        }
        return stack.remove().path
    }

    private fun <Value, Label> Node<Value, Label>.bft(): LinkedHashSet<Node<Value, Label>> {
        TODO("not implemented")
    }
}<commit_msg>traversal<commit_after>package katas.kotlin.graph

import katas.kotlin.graph.Graph.Node
import katas.kotlin.graph.Traversal8.Frame.Args
import katas.kotlin.graph.Traversal8.Frame.Result
import katas.kotlin.shouldEqual
import kotlincommon.join
import org.junit.Test
import java.util.*

class Traversal8 {
    @Test fun `depth-first traversal`() {
        "[a]".toGraph().let {
            it.dft("a") shouldEqual "a"
            it.dft("x") shouldEqual ""
        }
        "[a-b]".toGraph().let {
            it.dft("a") shouldEqual "a-b"
            it.dft("b") shouldEqual "b-a"
            it.dft("x") shouldEqual ""
        }
        "[a-b, b-c]".toGraph().let {
            it.dft("a") shouldEqual "a-b-c"
            it.dft("b") shouldEqual "b-a-c"
            it.dft("c") shouldEqual "c-b-a"
            it.dft("x") shouldEqual ""
        }
        // a──b1──c
        // └──b2──┘
        "[a-b1, a-b2, b1-c, b2-c]".toGraph().let {
            it.dft("a") shouldEqual "a-b1-c-b2"
            it.dft("b1") shouldEqual "b1-a-b2-c"
            it.dft("b2") shouldEqual "b2-a-b1-c"
            it.dft("c") shouldEqual "c-b1-a-b2"
        }
    }

    @Test fun `breadth-first traversal`() {
        "[a]".toGraph().let {
            it.bft("a") shouldEqual "a"
            it.bft("x") shouldEqual ""
        }
        "[a-b]".toGraph().let {
            it.bft("a") shouldEqual "a-b"
            it.bft("b") shouldEqual "b-a"
            it.bft("x") shouldEqual ""
        }
        "[a-b, b-c]".toGraph().let {
            it.bft("a") shouldEqual "a-b-c"
            it.bft("b") shouldEqual "b-a-c"
            it.bft("c") shouldEqual "c-b-a"
            it.bft("x") shouldEqual ""
        }
        // a──b1──c
        // └──b2──┘
        "[a-b1, a-b2, b1-c, b2-c]".toGraph().let {
            it.bft("a") shouldEqual "a-b1-b2-c"
            it.bft("b1") shouldEqual "b1-a-c-b2"
            it.bft("b2") shouldEqual "b2-a-c-b1"
            it.bft("c") shouldEqual "c-b1-b2-a"
        }
    }


    private fun <Value, Label> Graph<Value, Label>.dft(value: Value): String {
        return (this.nodes[value] ?: return "").dft().join("-")
    }

    private fun <Value, Label> Graph<Value, Label>.bft(value: Value): String {
        return (this.nodes[value] ?: return "").bft().join("-")
    }

    private sealed class Frame<Value, Label> {
        data class Result<Value, Label>(val path: LinkedHashSet<Node<Value, Label>>): Frame<Value, Label>()
        data class Args<Value, Label>(val node: Node<Value, Label>, val result: Result<Value, Label>): Frame<Value, Label>()
    }

    private fun <Value, Label> Node<Value, Label>.dft(): LinkedHashSet<Node<Value, Label>> {
        val stack = LinkedList<Frame<Value, Label>>()
        stack.add(Args(this, Result(LinkedHashSet())))
        while (stack.isNotEmpty()) {
            val args = stack.removeLast() as Args
            args.result.path.add(args.node)
            if (!args.result.path.contains(args.node)) {
//                frame.node.neighbors().forEach { node ->
//                    stack.add(Frame(node, frame.path))
//                }
//            }
            }
        }
        return (stack.removeLast() as Result).path
    }

    private fun <Value, Label> Node<Value, Label>.bft(): LinkedHashSet<Node<Value, Label>> {
        TODO("not implemented")
    }
}
{'fraction_non_alphanumeric': 0.18762057877813504, 'fraction_numerical': 0.010932475884244373, 'mean_word_length': 1.8497480531378836, 'pattern_counts': {'":': 0, '<': 44, '<?xml version=': 0, '>': 45, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6071098', 'n_tokens_mistral': 2264, 'n_tokens_neox': 2242, 'n_words': 394}