package dijkstra

import kotlinx.atomicfu.atomic
import java.lang.Math.abs
import java.util.*
import java.util.Collections.swap
import java.util.concurrent.Phaser
import java.util.concurrent.locks.ReentrantLock
import kotlin.Comparator
import kotlin.collections.ArrayList
import kotlin.collections.RandomAccess
import kotlin.concurrent.thread

private val NODE_DISTANCE_COMPARATOR = Comparator<Node> { o1, o2 -> Integer.compare(o1!!.distance, o2!!.distance) }

// Returns `Integer.MAX_VALUE` if a path has not been found.

class MyQueue(workers: Int, comparator: Comparator<Node> ){
    val workers : Int
    val queueSzie = atomic(0)
    val sizeLock : ReentrantLock
    val arr  = IntArray(workers)
    val myList : List<Int>

    val qu : ArrayList<PriorityQueue<Node>> = ArrayList()
    val loksStatus : ArrayList<ReentrantLock> = ArrayList()
    init{
        this.workers = workers
        for(i in 0..workers -1){
            arr[i] = i
        }
        myList = arr.toList()
        sizeLock = ReentrantLock()
        for (i in 1..this.workers) {
            qu.add(PriorityQueue(1, comparator))
            loksStatus.add(ReentrantLock())
        }
    }

    fun pop(): Node? {
        var i = 0
        var deletedSomethink : Boolean = false
        var ans : Node = Node()
        while (!isEmpty()){

            i = abs(Random().nextInt()) % workers
            if (loksStatus[i].tryLock()) {
                try {
                    if (qu[i].size > 0) {
                        ans = qu[i].remove()
                        deletedSomethink = true
                        queueSzie.decrementAndGet()
                    }
                } finally {
                    loksStatus[i].unlock()
                }
            }
            if (deletedSomethink)
                return ans
        }

        return null
    }

    fun add(x : Node){
        var i = 0
        var flag = true
        while (flag){
            i = abs(Random().nextInt()) % workers
            if (loksStatus[i].tryLock()) {
                try {
                    queueSzie.incrementAndGet()
                    qu[i].add(x)
                    flag = false
                } finally {
                    loksStatus[i].unlock()

                }
            }
        }
    }

    fun isEmpty() : Boolean {
        var result : Boolean
        result = true
        if(queueSzie.value > 0) {
            result = false
        }
        return result
    }
}

fun shortestPathParallel(start: Node) {
    val workers = Runtime.getRuntime().availableProcessors()
    //val workers = 1



    start.distance = 0
    // Create a priority (by distance) queue and add the start node into it
    //val q = PriorityQueue(workers, NODE_DISTANCE_COMPARATOR) // TODO replace me with a multi-queue based PQ!
    val q = MyQueue(workers, NODE_DISTANCE_COMPARATOR)
    q.add(start)
    // Run worker threads and wait until the total work is done
    val onFinish = Phaser(workers + 1) // `arrive()` should be invoked at the end by each worker
    repeat(workers) {
        thread {
            while (!q.isEmpty()) {
                val cur: Node? = q.pop()
                if (cur == null) {
                    continue
                }
                for (e in cur.outgoingEdges) {
                    while (true) {
                        val olde = e.to.distance
                        val oldcur = cur.distance
                        if(olde > oldcur + e.weight) {
                            if (e.to.casDistance(olde, oldcur + e.weight)) {
                                q.add(e.to)
                                break
                            }
                            continue
                        }
                        break
                    }
                }
            }
            // TODO Write the required algorithm here,
            // TODO break from this loop when there is no more node to process.
            // TODO Be careful, "empty queue" != "all nodes are processed".
            onFinish.arrive()
        }
    }
    onFinish.arriveAndAwaitAdvance()
}