import java.util.concurrent.*
import java.util.concurrent.atomic.*

class FlatCombiningQueue<E> : Queue<E> {
    private val queue = ArrayDeque<E>() // sequential queue
    private val combinerLock = AtomicBoolean(false) // unlocked initially
    private val tasksForCombiner = AtomicReferenceArray<Any?>(TASKS_FOR_COMBINER_SIZE)

    override fun enqueue(element: E) {
        // TODO: Make this code thread-safe using the flat-combining technique.
        // TODO: 1.  Try to become a combiner by
        // TODO:     changing `combinerLock` from `false` (unlocked) to `true` (locked).
        // TODO: 2a. On success, apply this operation and help others by traversing
        // TODO:     `tasksForCombiner`, performing the announced operations, and
        // TODO:      updating the corresponding cells to `Result`.
        // TODO: 2b. If the lock is already acquired, announce this operation in
        // TODO:     `tasksForCombiner` by replacing a random cell state from
        // TODO:      `null` with the element. Wait until either the cell state
        // TODO:      updates to `Result` (do not forget to clean it in this case),
        // TODO:      or `combinerLock` becomes available to acquire.

        var cellIndex = randomCellIndex()
        var isPut = false
        while (true) {
            if (combinerLock.compareAndSet(false, true)) {
                queue.addLast(element)
                if (isPut) {
                    tasksForCombiner.set(cellIndex, null)
                }
                helpOthers()
                combinerLock.set(false)
                return
            }

            if (!isPut) {
                if (tasksForCombiner.compareAndSet(cellIndex, null, element)) {
                    isPut = true
                } else {
                    cellIndex = randomCellIndex()
                    continue
                }
            }

            if (tasksForCombiner.get(cellIndex) == null) {
                return
            }
        }
    }

    override fun dequeue(): E? {
        // TODO: Make this code thread-safe using the flat-combining technique.
        // TODO: 1.  Try to become a combiner by
        // TODO:     changing `combinerLock` from `false` (unlocked) to `true` (locked).
        // TODO: 2a. On success, apply this operation and help others by traversing
        // TODO:     `tasksForCombiner`, performing the announced operations, and
        // TODO:      updating the corresponding cells to `Result`.
        // TODO: 2b. If the lock is already acquired, announce this operation in
        // TODO:     `tasksForCombiner` by replacing a random cell state from
        // TODO:      `null` with `Dequeue`. Wait until either the cell state
        // TODO:      updates to `Result` (do not forget to clean it in this case),
        // TODO:      or `combinerLock` becomes available to acquire.

        var cellIndex = randomCellIndex()
        var isPut = false
        var element: E? = null
        while (true) {
            if (combinerLock.compareAndSet(false, true)) {
                if (isPut) {
                    val result = tasksForCombiner.getAndSet(cellIndex, null) as? Result<*>
                    if (result != null) {
                        element = result.value as E?
                    } else {
                        element = queue.removeFirstOrNull()
                    }
                } else {
                    element = queue.removeFirstOrNull()
                }
                helpOthers()
                combinerLock.set(false)
                return element
            }

            if (!isPut) {
                if (tasksForCombiner.compareAndSet(cellIndex, null, Dequeue)) {
                    isPut = true
                } else {
                    cellIndex = randomCellIndex()
                    continue
                }
            }

            val result = tasksForCombiner.get(cellIndex) as? Result<*>
            if (isPut && result != null) {
                tasksForCombiner.set(cellIndex, null)
                return result.value as E?
            }
        }
    }

    fun helpOthers() {
        for (i in 0..<tasksForCombiner.length()) {
            if (tasksForCombiner.get(i) == null) {
                continue
            }
            if (tasksForCombiner.compareAndSet(i, Dequeue, Result(queue.firstOrNull()))) {
                queue.removeFirstOrNull()
                continue
            }
            var task = tasksForCombiner.get(i)
            if (task is Result<*>) {
                continue
            }
            queue.addLast(task as E)
            tasksForCombiner.set(i, null)
        }
    }

    private fun randomCellIndex(): Int =
        ThreadLocalRandom.current().nextInt(tasksForCombiner.length())
}

private const val TASKS_FOR_COMBINER_SIZE = 3 // Do not change this constant!

// TODO: Put this token in `tasksForCombiner` for dequeue().
// TODO: enqueue()-s should put the inserting element.
private object Dequeue

// TODO: Put the result wrapped with `Result` when the operation in `tasksForCombiner` is processed.
private class Result<V>(
    val value: V
)