import java.io.File
import java.util.*
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")
    }

    fun str() = "$a $b $w\n"

}

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 save(name : String){
        val f = File(name)
        f.writeText("$size ${data.size}\n")
        data.forEach {
            f.appendText(it.str())
        }
    }

    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){
    val pathData = IntArray(graph.size+1) { -1 }
    val distances = IntArray(graph.size+1) { Int.MAX_VALUE }
    distances[start] = 0

    val pq = PriorityQueue<Pair<Int, Int>>(compareBy { it.second })
    pq.add(Pair(start, 0))

    val t = measureTime {
        while (pq.isNotEmpty()) {
            val (currentVertex, currentDistance) = pq.poll()
            if (currentDistance > distances[currentVertex]) {
                continue
            }
            for (neighbor in graph.neighbours(currentVertex)) {
                val otherVertex = if (neighbor.a == currentVertex) neighbor.b else neighbor.a
                val newDistance = currentDistance + neighbor.w
                if (newDistance < distances[otherVertex]) {
                    distances[otherVertex] = newDistance
                    pq.add(Pair(otherVertex, newDistance))
                    pathData[otherVertex] = currentVertex

                }
            }
        }
    }
    println("time : ${t.inWholeMilliseconds} ms")
    println("time : ${t.inWholeNanoseconds} ns")

    if (distances[end] == Int.MAX_VALUE) {
        println("No path from $start to $end found.")
    } else {
        val path = mutableListOf<Int>()
        var currentVertex = end
        while (currentVertex != -1) {
            path.add(currentVertex)
            currentVertex = pathData[currentVertex]
        }
        path.reverse()
        println("path : ${path.joinToString ("-"){ it.toString() }}")
        println("Shortest distance from vertex $start to vertex $end: ${distances[end]}")
    }
}

fun main() {
    val seed = 0L//Random.nextLong()
    println("seed : $seed")
    val graph = gen(50,10,100..1000,seed)
    graph.save("/tmp/test0.txt")
    walker(graph,1,50)
}