import kotlinx.atomicfu.*

class DynamicArrayImpl<E> : DynamicArray<E> {
    private class Moved<E>(el: E) {
        val elem = el
    }

    private val core = atomic(Core(INITIAL_CAPACITY))
    private val prepared = atomic<Core?>(null)

    override fun get(index: Int): E {
        val currCore = core.value
        if (index >= currCore.size.value) {
            throw IndexOutOfBoundsException()
        }

        val currElem = currCore.array[index].value!!

        @Suppress("UNCHECKED_CAST")
        return when (currElem) {
            is Moved<*> -> currElem.elem!!
            else -> currElem
        } as E
    }

    override fun put(index: Int, element: E) {
        while (true) {
            val currCore = core.value
            val currSize = currCore.size.value
            if (index >= currSize) {
                throw IndexOutOfBoundsException()
            }

            val currElem = currCore.array[index].value
            if (currElem == null && currCore.array[index].compareAndSet(null, element)) {
                return
            }
        }
    }

    override fun pushBack(element: E) {
        wholeThing@ while (true) {
            val currCore = core.value

            addingToLast@ while (true) {
                val currSize = currCore.size.value
                if (currSize < currCore.array.size) {
                    if (currCore.array[currSize].compareAndSet(null, element)) {
                        currCore.size.getAndIncrement()
                        return
                    } else {
                        val currVal = currCore.array[currSize].value
                        if (currVal is Moved<*>) {
                            // someone else started moving array and stolen this element
                            continue@wholeThing
                        } else {
                            // someone inserted an element here
                            continue@addingToLast
                        }
                    }
                } else { // currSize == currCore.array.size
                    resize(currCore.array.size * 2)
                    continue@wholeThing
                }
            }
        }
    }

    override val size: Int
        get() {
            return core.value.size.value
        }


    private fun resize(wishedCap: Int) {
        while (true) {
            val currCore = core.value
            if (currCore.array.size >= wishedCap) {
                return
            }

            val nextCore = prepared.value
            if (nextCore != null) {
                moveValues(currCore, nextCore)
            } else {
                val createdCore = Core(wishedCap, currCore.array.size)
                if (prepared.compareAndSet(null, createdCore)) {
                    moveValues(currCore, createdCore)
                    return
                }
            }
        }
    }

    private fun moveValues(from: Core, to: Core) {
        val fromArr = from.array
        val toArr = to.array

        for (i in 0 until fromArr.size) {
            val currElem = fromArr[i].value
            fromArr[i].compareAndSet(currElem, Moved(currElem))
            if (currElem != null) {
                toArr[i].compareAndSet(null, currElem)
            }
        }
    }
}

private class Core(capacity: Int, reservedSize: Int = 0) {
    val array = atomicArrayOfNulls<Any>(capacity)
    val size = atomic(reservedSize)
}

private const val INITIAL_CAPACITY = 1 // DO NOT CHANGE ME