dynamic_arr

import kotlinx.atomicfu.*

class DynamicArrayImpl<E> : DynamicArray<E> {
    interface Node<E> {
        interface WithValue<E> : Node<E> {
            val value: E
        }

        class Normal<E>(override val value: E) : WithValue<E>
        class CopyInProgress<E>(override val value: E) : WithValue<E>
        class CopyComplete<E>() : Node<E>
    }

    private class Core<E>(val capacity: Int) {
        val array = atomicArrayOfNulls<Node<E>>(capacity)
        val next: AtomicRef<Core<E>?> = atomic(null)
        val leftToCopy = atomic(capacity)

        fun getOrCreateNext(): Core<E> {
            val oldValue = next.value
            if (oldValue == null) {
                next.compareAndSet(null, Core(capacity * GROW_FACTOR))
            }
            // CAS should finish with success, in this or other thread
            return next.value!!
        }

    }

    companion object {
        private const val GROW_FACTOR = 2
        private const val INITIAL_CAPACITY = 1 // DO NOT CHANGE ME - OK, NOT CHANGED!
    }

    private val core = atomic(Core<E>(INITIAL_CAPACITY))
    private val sizeVal: AtomicInt = atomic(0)

    override fun get(index: Int): E {
        require(0 <= index && index < sizeVal.value)
        // Yes, we can return value from [Node.CopyInProgress],
        // but let's help other threads to finish copy to new core operation
        return doActionOnNormalNode(index) { _, node -> node.value }
    }

    override fun put(index: Int, element: E) {
        require(0 <= index && index < sizeVal.value)
        doActionOnNormalNode(index) { core, normal ->
            when (core.array[index].compareAndSet(normal, Node.Normal(element))) {
                true -> true // Stop retrying CAS - we're done
                false -> null // CAS failed, retry
            }
        }
    }

    override fun pushBack(element: E) {
        var currentCore = tryRemoveCopiedCores()
        while (true) {
            currentCore = skipCopiedCores(currentCore)
            val currentSize = size

            if (currentSize >= currentCore.capacity) {
                currentCore = buildNextCore(currentCore)
                continue
            }

            if (!currentCore.array[currentSize].compareAndSet(null, Node.Normal(element))) {
                continue
            }
            sizeVal.incrementAndGet()
            return
        }
    }

    override val size: Int
        get() = sizeVal.value

    private fun buildNextCore(fromCore: Core<E>): Core<E> {
        val nextCore = fromCore.getOrCreateNext()

        // Copy elements to new core
        for (i in 0 until fromCore.capacity) {
            // Ignore nulls
            var node = fromCore.array[i].value!!

            // Mark existing core values with "Copy in progress"
            retryMarkAsInProgress@ while (node is Node.Normal) {
                if (fromCore.array[i].compareAndSet(node, Node.CopyInProgress(node.value))) {
                    break@retryMarkAsInProgress
                }
                node = fromCore.array[i].value!!
            }

            // Nothing to do if node already copied
            if (node is Node.CopyComplete) {
                continue
            }

            // If node is marked with "Copy in progress", try to copy it to new core
            val value = (node as Node.WithValue).value
            if (nextCore.array[i].value != null || nextCore.array[i].compareAndSet(null, Node.Normal(value))) {
                // If copy complete, we can release this node in old core
                fromCore.array[i].compareAndSet(node, Node.CopyComplete())
                fromCore.leftToCopy.decrementAndGet()
            }
        }

        return nextCore
    }

    /**
     * Retries to perform [action] on actual `Normal` node on [index],
     * stops iterating when [action] retries non-null value.
     * A short way to find node in the correct core and process it
     */
    private fun <R> doActionOnNormalNode(index: Int, action: (Core<E>, Node.Normal<E>) -> R?): R {
        var currentCore = tryRemoveCopiedCores()

        while (true) {
            currentCore = skipCopiedCores(currentCore)
            if (index >= currentCore.capacity) {
                currentCore = currentCore.next.value!!
                continue
            }

            val node = currentCore.array[index].value ?: continue
            if (node is Node.Normal) {
                return action(currentCore, node) ?: continue
            } else if (node is Node.CopyInProgress) {
                buildNextCore(currentCore)
            } else {
                currentCore = currentCore.next.value!!
            }
        }
    }

    private fun tryRemoveCopiedCores(): Core<E> {
        var currentCore = core.value
        while (currentCore.leftToCopy.value == 0) {
            val nextNode = currentCore.next.value!!
            if (!core.compareAndSet(currentCore, nextNode)) {
                return currentCore
            }
            currentCore = nextNode
        }
        return currentCore
    }

    private fun skipCopiedCores(fromCore: Core<E>): Core<E> {
        var temp = fromCore
        while (temp.leftToCopy.value == 0) {
            temp = temp.next.value!!
        }
        return temp
    }
}