import kotlin.random.Random
import kotlin.random.nextInt
import kotlin.time.measureTime

data class Edge(
    val a : Int,
    val b : Int,
    val w : Int
){
    fun print(){
        println("$a -{$w}- $b")
    }
}

class Graph(val size : Int){

    private val data = arrayListOf<Edge>()

    fun add(edge: Edge){
        if(data.find { it.a == edge.a && it.b == edge.b } == null &&
           data.find { it.a == edge.b && it.b == edge.a } == null)
           data.add(edge)
    }

    fun neighbours(i : Int) : List<Edge>{
        val t = data.filter {  it.b == i }.map { Edge(it.b,it.a,it.w) }
        return data.filter { it.a == i  } + t
    }

    fun print(){
        println("size -> $size")
        println("cons -> ${data.size}")
        println("cons : ")
        data.forEach {
            it.print()
        }
    }
}

fun gen(size : Int,poss : Int,weights : IntRange,seed : Long = 0L) : Graph{
    val rand = Random(seed)

    fun newEdge(i : Int) : Edge{
        val dest = rand.nextInt(1..size)
        val w = rand.nextInt(weights)
        return if(dest != i){
            Edge(i,dest,w)
        }else{
            newEdge(i)
        }
    }

    val graph = Graph(size)
    val subList = mutableListOf<Edge>()
    for(i in 1..size) {
        var count = 0
        for (j in 1..size) {
            if(rand.nextInt(1,101) < poss && i != j){
                val w = rand.nextInt(weights)
                subList.add(Edge(i,j,w))
                count++
            }
        }
        if(count == 0){
            subList.add(newEdge(i))
        }
        subList.sortedBy { it.w }.forEach {
            graph.add(it)
        }
        subList.clear()
    }
    return graph
}

fun walker(graph: Graph,start : Int, end : Int){
    println()
    if (start in 0..graph.size && end in 0..graph.size && start != end) {
        val list = mutableListOf<Int>()
        var total = 0
        var curr = start
        var comps = 0
        val t = measureTime {
            while (true) {
                list.add(curr)
                val neighbours = graph.neighbours(curr)
                if (neighbours.isNotEmpty()) {
                    var dist = Int.MAX_VALUE
                    var t = 0
                    for (i in neighbours.indices) {
                        val n = neighbours[i]
                        comps++
                        if(n.b !in list) {
                            if ((n.b == end || n.w < dist) && t != end) {
                                println(" ${n.a} -[${n.w}]- ${n.b} ")
                                t = n.b
                                dist = n.w
                            }else{
                                break
                            }
                        }
                    }
                    curr = t
                    if (dist != Int.MAX_VALUE)
                        total += dist
                }
                if (curr == end) {
                    list.add(end)
                    println("found path")
                    break
                }
            }
            println()
            println(list.joinToString("-") { it.toString() })
            println("distance : $total")
            println("moves : ${list.size - 1}")
            println("comps : $comps")
        }
        println("time : ${t.inWholeMilliseconds} ms")
        println("time : ${t.inWholeNanoseconds} ns")
    } else {
        when (start) {
            end -> println("Error: start == end")
            !in 0..<graph.size -> println("Error: start is out of graph")
            else -> println("Error: end is out of graph")
        }
    }
}

fun main() {
    val seed = 8714362708517061972L//Random.nextLong()
    println("seed : $seed")
    val graph = gen(50,5,100..1000,seed)
    //graph.print()
    walker(graph,1,50)
}