/*
 * Copyright 2019 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

@file:OptIn(InternalComposeApi::class)
package androidx.compose.runtime

import androidx.compose.runtime.tooling.CompositionData
import kotlin.math.max
import kotlin.math.min
import androidx.compose.runtime.tooling.CompositionGroup

// Nomenclature -
// Address      - an absolute offset into the array ignoring its gap. See Index below.
// Anchor       - an encoding of Index that allows it to not need to be updated when groups or slots
//                are inserted or deleted. An anchor is positive if the Index it is tracking is
//                before the gap and negative if it is after the gap. If the Anchor is negative, it
//                records its distance from the end of the array. If slots or groups are inserted or
//                deleted this distance doesn't change but the index it represents automatically
//                reflects the deleted or inserted groups or slots. Anchors only need to be updated
//                if they track indexes whose group or slot Address moves when the gap moves.
//                The term anchor is used not only for the Anchor class but for the parent anchor
//                and data anchors in the group fields which are also anchors but not Anchor
//                instances.
// Aux          - auxiliary data that can be associated with a node and set independent of groups
//                slots. This is used, for example, by the composer to record CompositionLocal
//                maps as the map is not known at the when the group starts, only when the map is
//                calculated after using an arbitrary number of slots.
// Data         - the portion of the slot array associated with the group that contains the slots as
//                well as the ObjectKey, Node, and Aux if present. The slots for a group are after
//                the optional fixed group data.
// Group fields - a set of 5 contiguous integer elements in the groups array aligned at 5
//                containing the key, node count, group size parent anchor and an anchor to the
//                group data and flags to indicate if the group is a node, has Aux or has an
//                ObjectKey. There are a set of extension methods used to access the group fields.
// Group        - a contiguous range in the groups array. The groups is an inlined array of group
//                fields. The group fields for a group and all of its children's fields comprise
//                a group. A groups describes how to interpret the slot array. Groups have an
//                integer key, and optional object key, node and aux and a 0 or more slots.
//                Groups form a tree where the child groups are immediately after the group
//                fields for the group. This data structure favors a linear scan of the children.
//                Random access is expensive unless it is through a group anchor.
// Index        - the logical index of a group or slot in its array. The index doesn't change when
//                the gap moves. See Address and Anchor above. The index and address of a group
//                or slot are identical if the gap is at the end of the buffer. This is taken
//                advantage of in the SlotReader.
// Key          - an Int value used as a key by the composer.
// Node         - a value of a node group that can be set independently of the slots of the group.
//                This is, for example, where the LayoutNode is stored by the slot table when
//                emitting using the UIEmitter.
// ObjectKey    - an object that can be used by the composer as part of a groups key. The key()
//                composable, for example, produces an ObjectKey. Using the key composable
//                function, for example, produces an ObjectKey value.
// Slot         - and element in the slot array. Slots are managed by and addressed through a group.
//                Slots are allocated in the slots array and are stored in order of their respective
//                groups.

// All fields and variables referring to an array index are assumed to be Index values, not Address
// values, unless explicitly ending in Address.

// For simplicity and efficiency of the reader, the gaps are always moved to the end resulting in
// Index and Address being identical in a reader.

// The public API refers only to Index values. Address values are internal.

internal class SlotTable : CompositionData, Iterable<CompositionGroup> {
    /**
     * An array to store group information that is stored as groups of [Group_Fields_Size]
     * elements of the array. The [groups] array can be thought of as an array of an inline
     * struct.
     */
    var groups = IntArray(0)
        private set

    /**
     * The number of groups contained in [groups].
     */
    var groupsSize = 0
        private set

    /**
     * An array that stores the slots for a group. The slot elements for a group start at the
     * offset returned by [dataAnchor] of [groups] and continue to the next group's slots or to
     * [slotsSize] for the last group. When in a writer the [dataAnchor] is an anchor instead of
     * an index as [slots] might contain a gap.
     */
    var slots = Array<Any?>(0) { null }
        private set

    /**
     * The number of slots used in [slots].
     */
    var slotsSize = 0
        private set

    /**
     * Tracks the number of active readers. A SlotTable can have multiple readers but only one
     * writer.
     */
    private var readers = 0

    /**
     * Tracks whether there is an active writer.
     */
    internal var writer = false
        private set

    /**
     * An internal version that is incremented whenever a writer is created. This is used to
     * detect when an iterator created by [CompositionData] is invalid.
     */
    internal var version = 0

    /**
     * A list of currently active anchors.
     */
    internal var anchors: ArrayList<Anchor> = arrayListOf()

    /**
     * Returns true if the slot table is empty
     */
    override val isEmpty get() = groupsSize == 0

    /**
     * Read the slot table in [block]. Any number of readers can be created but a slot table cannot
     * be read while it is being written to.
     *
     * @see SlotReader
     */
    inline fun <T> read(block: (reader: SlotReader) -> T): T = openReader()
        .let { reader ->
            try {
                block(reader)
            } finally {
                reader.close()
            }
        }

    /**
     * Write to the slot table in [block]. Only one writer can be created for a slot table at a
     * time and all readers must be closed an do readers can be created while the slot table is
     * being written to.
     *
     * @see SlotWriter
     */
    inline fun <T> write(block: (writer: SlotWriter) -> T): T = openWriter()
        .let { writer ->
            try {
                block(writer)
            } finally {
                writer.close()
            }
        }

    /**
     * Open a reader. Any number of readers can be created but a slot table cannot be read while
     * it is being written to.
     *
     * @see SlotReader
     */
    fun openReader(): SlotReader {
        if (writer) error("Cannot read while a writer is pending")
        readers++
        return SlotReader(table = this)
    }

    /**
     * Open a writer. Only one writer can be created for a slot table at a time and all readers
     * must be closed an do readers can be created while the slot table is being written to.
     *
     * @see SlotWriter
     */
    fun openWriter(): SlotWriter {
        check(!writer) { "Cannot start a writer when another writer is pending" }
        check(readers <= 0) { "Cannot start a writer when a reader is pending" }
        writer = true
        version++
        return SlotWriter(this)
    }

    /**
     * Return the group index for [anchor]. This [SlotTable] is assumed to own [anchor] but that
     * is not validated. If [anchor] is not owned by this [SlotTable] the result is undefined.
     * If a [SlotWriter] is open the [SlotWriter.anchorIndex] must be called instead as [anchor]
     * might be affected by the modifications being performed by the [SlotWriter].
     */
    fun anchorIndex(anchor: Anchor): Int {
        check(!writer) { "Use active SlotWriter to determine anchor location instead" }
        require(anchor.valid) { "Anchor refers to a group that was removed" }
        return anchor.location
    }

    /**
     * Returns true if [anchor] is owned by this [SlotTable] or false if it is owned by a
     * different [SlotTable] or no longer part of this table (e.g. it was moved or the group it
     * was an anchor for was removed).
     */
    fun ownsAnchor(anchor: Anchor): Boolean {
        return anchor.valid && anchors.search(anchor.location, groupsSize).let {
            it >= 0 && anchors[it] == anchor
        }
    }

    /**
     * Close [reader].
     */
    internal fun close(reader: SlotReader) {
        require(reader.table === this && readers > 0) { "Unexpected reader close()" }
        readers--
    }

    /**
     * Close [writer] and adopt the slot arrays returned. The [SlotTable] is invalid until
     * [SlotWriter.close] is called as the [SlotWriter] is modifying [groups] and [slots]
     * directly and will only make copies of the arrays if the slot table grows.
     */
    internal fun close(
        writer: SlotWriter,
        groups: IntArray,
        groupsSize: Int,
        slots: Array<Any?>,
        slotsSize: Int,
        anchors: ArrayList<Anchor>
    ) {
        require(writer.table === this && this.writer) { "Unexpected writer close()" }
        this.writer = false
        setTo(groups, groupsSize, slots, slotsSize, anchors)
    }

    /**
     * Used internally by [SlotWriter.moveFrom] to swap arrays with a slot table target
     * [SlotTable] is empty.
     */
    internal fun setTo(
        groups: IntArray,
        groupsSize: Int,
        slots: Array<Any?>,
        slotsSize: Int,
        anchors: ArrayList<Anchor>
    ) {
        // Adopt the slots from the writer
        this.groups = groups
        this.groupsSize = groupsSize
        this.slots = slots
        this.slotsSize = slotsSize
        this.anchors = anchors
    }

    /**
     * A debugging aid to validate the internal structure of the slot table. Throws an exception
     * if the slot table is not in the expected shape.
     */
    fun verifyWellFormed() {
        // If the check passes Address and Index are identical so there is no need for
        // indexToAddress conversions.
        var current = 0
        fun validateGroup(parent: Int, parentEnd: Int): Int {
            val group = current++
            val parentIndex = groups.parentAnchor(group)
            check(parentIndex == parent) {
                "Invalid parent index detected at $group, expected parent index to be $parent " +
                    "found $parentIndex"
            }
            val end = group + groups.groupSize(group)
            check(end <= groupsSize) { "A group extends past the end of the table at $group" }
            check(end <= parentEnd) { "A group extends past its parent group at $group" }

            val dataStart = groups.dataAnchor(group)
            val dataEnd = if (group >= groupsSize - 1) slotsSize else groups.dataAnchor(group + 1)
            check(dataEnd <= slots.size) {
                "Slots for $group extend past the end of the slot table"
            }
            check(dataStart <= dataEnd) {
                "Invalid data anchor at $group"
            }
            val slotStart = groups.slotAnchor(group)
            check(slotStart <= dataEnd) {
                "Slots start out of range at $group"
            }
            val minSlotsNeeded = (if (groups.isNode(group)) 1 else 0) +
                (if (groups.hasObjectKey(group)) 1 else 0) +
                (if (groups.hasAux(group)) 1 else 0)
            check(dataEnd - dataStart >= minSlotsNeeded) {
                "Not enough slots added for group $group"
            }
            val isNode = groups.isNode(group)
            check(!isNode || slots[groups.nodeIndex(group)] != null) {
                "No node recorded for a node group at $group"
            }
            var nodeCount = 0
            while (current < end) {
                nodeCount += validateGroup(group, end)
            }
            val expectedNodeCount = groups.nodeCount(group)
            val expectedSlotCount = groups.groupSize(group)
            check(expectedNodeCount == nodeCount) {
                "Incorrect node count detected at $group, " +
                    "expected $expectedNodeCount, received $nodeCount"
            }
            val actualSlotCount = current - group
            check(expectedSlotCount == actualSlotCount) {
                "Incorrect slot count detected at $group, expected $expectedSlotCount, received " +
                    "$actualSlotCount"
            }

            return if (isNode) 1 else nodeCount
        }

        if (groupsSize > 0) {
            while (current < groupsSize) {
                validateGroup(-1, current + groups.groupSize(current))
            }
            check(current == groupsSize) {
                "Incomplete group at root $current expected to be $groupsSize"
            }
        }

        // Verify anchors are well-formed
        var lastLocation = -1
        for (anchor in anchors) {
            val location = anchor.toIndexFor(this)
            require(location in 0..groupsSize) { "Location out of bound" }
            require(lastLocation < location) { "Anchor is out of order" }
            lastLocation = location
        }
    }

    /**
     * A debugging aid that renders the slot table as a string. [toString] is avoided as this is
     * potentially a very expensive operation for large slot tables and calling it in the
     * debugger should never be implicit.
     */
    @Suppress("unused")
    fun asString(): String {
        return if (writer) super.toString() else
            buildString {
                append(super.toString())
                append('\n')
                val groupsSize = groupsSize
                if (groupsSize > 0) {
                    var current = 0
                    while (current < groupsSize) {
                        current += emitGroup(current, 0)
                    }
                } else
                    append("<EMPTY>")
            }
    }

    /**
     * A helper function used by [asString] to render a particular group.
     */
    private fun StringBuilder.emitGroup(index: Int, level: Int): Int {
        repeat(level) { append(' ') }
        append("Group(")
        append(index)
        append(") key=")
        append(groups.key(index))
        fun dataIndex(index: Int) =
            if (index >= groupsSize) slotsSize else groups.dataAnchor(index)

        val groupSize = groups.groupSize(index)
        append(", nodes=")
        append(groups.nodeCount(index))
        append(", size=")
        append(groupSize)
        val dataStart = dataIndex(index)
        val dataEnd = dataIndex(index + 1)
        if (dataStart in 0..dataEnd && dataEnd <= slotsSize) {
            if (groups.hasObjectKey(index)) {
                append(" objectKey=${slots[groups.objectKeyIndex(index)]}")
            }
            if (groups.isNode(index)) {
                append(" node=${slots[groups.nodeIndex(index)]}")
            }
            if (groups.hasAux(index)) {
                append(" aux=${slots[groups.auxIndex(index)]}")
            }
            val slotStart = groups.slotAnchor(index)
            if (slotStart < dataEnd) {
                append(", slots=[")
                append(slotStart)
                append(": ")
                for (dataIndex in slotStart until dataEnd) {
                    if (dataIndex != slotStart) append(", ")
                    append(slots[dataIndex].toString())
                }
                append("]")
            }
        } else {
            append(", *invalid data offsets $dataStart-$dataEnd*")
        }
        append('\n')
        var current = index + 1
        val end = index + groupSize
        while (current < end) {
            current += emitGroup(current, level + 1)
        }
        return groupSize
    }

    /**
     * A debugging aid to list all the keys [key] values in the [groups] array.
     */
    @Suppress("unused")
    private fun keys() = groups.keys(groupsSize * Group_Fields_Size)

    /**
     * A debugging aid to list all the [nodeCount] values in the [groups] array.
     */
    @Suppress("unused")
    private fun nodes() = groups.nodeCounts(groupsSize * Group_Fields_Size)

    /**
     * A debugging aid to list all the [parentAnchor] values in the [groups] array.
     */
    @Suppress("unused")
    private fun parentIndexes() = groups.parentAnchors(groupsSize * Group_Fields_Size)

    /**
     * A debugging aid to list all the indexes into the [slots] array from the [groups] array.
     */
    @Suppress("unused")
    private fun dataIndexes() = groups.dataAnchors(groupsSize * Group_Fields_Size)

    /**
     * A debugging aid to list the [groupsSize] of all the groups in [groups].
     */
    @Suppress("unused")
    private fun groupSizes() = groups.groupSizes(groupsSize * Group_Fields_Size)

    @Suppress("unused")
    internal fun slotsOf(group: Int): List<Any?> {
        val start = groups.dataAnchor(group)
        val end = if (group + 1 < groupsSize) groups.dataAnchor(group + 1) else slots.size
        return slots.toList().subList(start, end)
    }

    override val compositionGroups: Iterable<CompositionGroup> get() = this

    override fun iterator(): Iterator<CompositionGroup> =
        GroupIterator(this, 0, groupsSize)
}

/**
 * An [Anchor] tracks a groups as its index changes due to other groups being inserted and
 * removed before it. If the group the [Anchor] is tracking is removed, directly or indirectly,
 * [valid] will return false. The current index of the group can be determined by passing either
 * the [SlotTable] or [SlotWriter] to [toIndexFor]. If a [SlotWriter] is active, it must be used
 * instead of the [SlotTable] as the anchor index could have shifted due to operations performed
 * on the writer.
 */
internal class Anchor(loc: Int) {
    internal var location: Int = loc
    val valid get() = location != Int.MIN_VALUE
    fun toIndexFor(slots: SlotTable) = slots.anchorIndex(this)
    fun toIndexFor(writer: SlotWriter) = writer.anchorIndex(this)
}

/**
 * A reader of a slot table. See [SlotTable]
 */
internal class SlotReader(
    /**
     * The table for whom this is a reader.
     */
    internal val table: SlotTable
) {

    /**
     * A copy of the [SlotTable.groups] array to avoid having indirect through [table].
     */
    private val groups: IntArray = table.groups

    /**
     * A copy of [SlotTable.groupsSize] to avoid having to indirect through [table].
     */
    private val groupsSize: Int = table.groupsSize

    /**
     * A copy of [SlotTable.slots] to avoid having to indirect through [table].
     */
    private val slots: Array<Any?> = table.slots

    /**
     * A Copy of [SlotTable.slotsSize] to avoid having to indirect through [table].
     */
    private val slotsSize: Int = table.slotsSize

    /**
     * The current group that will be started with [startGroup] or skipped with [skipGroup].
     */
    var currentGroup = 0
        private set

    /**
     * The end of the [parent] group.
     */
    var currentEnd = groupsSize
        private set

    /**
     * The parent of the [currentGroup] group which is the last group started with [startGroup].
     */
    var parent = -1
        private set

    /**
     * The number of times [beginEmpty] has been called.
     */
    private var emptyCount = 0

    /**
     * The current slot of [parent]. This slot will be the next slot returned by [next] unless it
     * is equal ot [currentSlotEnd].
     */
    private var currentSlot = 0

    /**
     * The current end slot of [parent].
     */
    private var currentSlotEnd = 0

    /**
     * Return the total number of groups in the slot table.
     */
    val size: Int get() = groupsSize

    /**
     * Return the current slot of the group whose value will be returned by calling [next].
     */
    val slot: Int get() = currentSlot - groups.slotAnchor(parent)

    /**
     * Return the parent index of [index].
     */
    fun parent(index: Int) = groups.parentAnchor(index)

    /**
     * Determine if the slot is start of a node.
     */
    val isNode: Boolean get() = groups.isNode(currentGroup)

    /**
     * Determine if the group at [index] is a node.
     */
    fun isNode(index: Int) = groups.isNode(index)

    /**
     * The number of nodes managed by the current group. For node groups, this is the list of the
     * children nodes.
     */
    val nodeCount: Int get() = groups.nodeCount(currentGroup)

    /**
     * Return the number of nodes for the group at [index].
     */
    fun nodeCount(index: Int) = groups.nodeCount(index)

    /**
     * Return the node at [index] if [index] is a node group else null.
     */
    fun node(index: Int): Any? = if (groups.isNode(index)) groups.node(index) else null

    /**
     * Determine if the reader is at the end of a group and an [endGroup] is expected.
     */
    val isGroupEnd get() = inEmpty || currentGroup == currentEnd

    /**
     * Determine if a [beginEmpty] has been called.
     */
    val inEmpty get() = emptyCount > 0

    /**
     * Get the size of the group at [currentGroup].
     */
    val groupSize get() = groups.groupSize(currentGroup)

    /**
     * Get the size of the group at [index]. Will throw an exception if [index] is not a group
     * start.
     */
    fun groupSize(index: Int) = groups.groupSize(index)

    /**
     * Get location the end of the currently started group.
     */
    val groupEnd get() = currentEnd

    /**
     * Get location of the end of the group at [index].
     */
    fun groupEnd(index: Int) = index + groups.groupSize(index)

    /**
     * Get the key of the current group. Returns 0 if the [currentGroup] is not a group.
     */
    val groupKey
        get() = if (currentGroup < currentEnd) {
            groups.key(currentGroup)
        } else 0

    /**
     * Get the key of the group at [index].
     */
    fun groupKey(index: Int) = groups.key(index)

    /**
     * The group slot index is the index into the current groups slots that will be updated by
     * read by [next].
     */
    val groupSlotIndex get() = currentSlot - groups.slotAnchor(parent)

    /**
     * Determine if the group at [index] has an object key
     */
    fun hasObjectKey(index: Int) = groups.hasObjectKey(index)

    /**
     * Get the object key for the current group or null if no key was provide
     */
    val groupObjectKey get() =
        if (currentGroup < currentEnd) groups.objectKey(currentGroup) else null

    /**
     * Get the object key at [index].
     */
    fun groupObjectKey(index: Int) = groups.objectKey(index)

    /**
     * Get the current group aux data.
     */
    val groupAux get() = if (currentGroup < currentEnd) groups.aux(currentGroup) else 0

    /**
     * Get the aux data for the group at [index]
     */
    fun groupAux(index: Int) = groups.aux(index)

    /**
     * Get the node associated with the group if there is one.
     */
    val groupNode get() = if (currentGroup < currentEnd) groups.node(currentGroup) else null

    /**
     * Get the group key at [anchor]. This return 0 if the anchor is not valid.
     */
    fun groupKey(anchor: Anchor) = if (anchor.valid) groups.key(table.anchorIndex(anchor)) else 0

    /**
     * Return the number of nodes where emitted into the current group.
     */
    val parentNodes: Int get() = if (parent >= 0) groups.nodeCount(parent) else 0

    /**
     * Return the index of the parent group of the given group
     */
    fun parentOf(index: Int): Int {
        @Suppress("ConvertTwoComparisonsToRangeCheck")
        require(index >= 0 && index < groupsSize) { "Invalid group index $index" }
        return groups.parentAnchor(index)
    }

    /**
     * Return the number of slots allocated to the [currentGroup] group.
     */
    val groupSlotCount: Int get() {
        val current = currentGroup
        val start = groups.slotAnchor(current)
        val next = current + 1
        val end = if (next < groupsSize) groups.dataAnchor(next) else slotsSize
        return end - start
    }

    /**
     * Get the value stored at [index] in the parent group's slot.
     */
    fun get(index: Int) = (currentSlot + index).let { slotIndex ->
        if (slotIndex < currentSlotEnd) slots[slotIndex] else Composer.Empty
    }

    /**
     * Get the value of the group's slot at [index] for the [currentGroup] group.
     */
    fun groupGet(index: Int): Any? {
        val current = currentGroup
        val start = groups.slotAnchor(current)
        val next = current + 1
        val end = if (next < groupsSize) groups.dataAnchor(next) else slotsSize
        val address = start + index
        return if (address < end) slots[address] else Composer.Empty
    }

    /**
     * Get the value of the slot at [currentGroup] or [Composer.Empty] if at then end of a group.
     * During empty mode this value is always [Composer.Empty] which is the value a newly inserted
     * slot.
     */
    fun next(): Any? {
        if (emptyCount > 0 || currentSlot >= currentSlotEnd) return Composer.Empty
        return slots[currentSlot++]
    }

    /**
     * Begin reporting empty for all calls to next() or get(). beginEmpty() can be nested and must
     * be called with a balanced number of endEmpty()
     */
    fun beginEmpty() {
        emptyCount++
    }

    /**
     * End reporting [Composer.Empty] for calls to [next] and [get],
     */
    fun endEmpty() {
        require(emptyCount > 0) { "Unbalanced begin/end empty" }
        emptyCount--
    }

    /**
     * Close the slot reader. After all [SlotReader]s have been closed the [SlotTable] a
     * [SlotWriter] can be created.
     */
    fun close() = table.close(this)

    /**
     * Start a group.
     */
    fun startGroup() {
        if (emptyCount <= 0) {
            require(groups.parentAnchor(currentGroup) == parent) { "Invalid slot table detected" }
            parent = currentGroup
            currentEnd = currentGroup + groups.groupSize(currentGroup)
            val current = currentGroup++
            currentSlot = groups.slotAnchor(current)
            currentSlotEnd = if (current >= groupsSize - 1)
                slotsSize else
                groups.dataAnchor(current + 1)
        }
    }

    /**
     * Start a group and validate it is a node group
     */
    fun startNode() {
        if (emptyCount <= 0) {
            require(groups.isNode(currentGroup)) { "Expected a node group" }
            startGroup()
        }
    }

    /**
     *  Skip a group. Must be called at the start of a group.
     */
    fun skipGroup(): Int {
        require(emptyCount == 0) { "Cannot skip while in an empty region" }
        val count = if (groups.isNode(currentGroup)) 1 else groups.nodeCount(currentGroup)
        currentGroup += groups.groupSize(currentGroup)
        return count
    }

    /**
     * Skip to the end of the current group.
     */
    fun skipToGroupEnd() {
        require(emptyCount == 0) { "Cannot skip the enclosing group while in an empty region" }
        currentGroup = currentEnd
    }

    /**
     * Reposition the read to the group at [index].
     */
    fun reposition(index: Int) {
        require(emptyCount == 0) { "Cannot reposition while in an empty region" }
        currentGroup = index
        val parent = if (index < groupsSize) groups.parentAnchor(index) else -1
        this.parent = parent
        if (parent < 0)
            this.currentEnd = groupsSize
        else
            this.currentEnd = parent + groups.groupSize(parent)
        this.currentSlot = 0
        this.currentSlotEnd = 0
    }

    /**
     * Restore the parent to a parent of the current group.
     */
    fun restoreParent(index: Int) {
        val newCurrentEnd = index + groups.groupSize(index)
        val current = currentGroup
        @Suppress("ConvertTwoComparisonsToRangeCheck")
        require(current >= index && current <= newCurrentEnd) {
            "Index $index is not a parent of $current"
        }
        this.parent = index
        this.currentEnd = newCurrentEnd
        this.currentSlot = 0
        this.currentSlotEnd = 0
    }

    /**
     * End the current group. Must be called after the corresponding [startGroup].
     */
    fun endGroup() {
        if (emptyCount == 0) {
            require(currentGroup == currentEnd) { "endGroup() not called at the end of a group" }
            val parent = groups.parentAnchor(parent)
            this.parent = parent
            currentEnd = if (parent < 0)
                groupsSize
            else
                parent + groups.groupSize(parent)
        }
    }

    /**
     * Extract the keys from this point to the end of the group. The current is left unaffected.
     * Must be called inside a group.
     */
    fun extractKeys(): MutableList<KeyInfo> {
        val result = mutableListOf<KeyInfo>()
        if (emptyCount > 0) return result
        var index = 0
        var childIndex = currentGroup
        while (childIndex < currentEnd) {
            result.add(
                KeyInfo(
                    groups.key(childIndex),
                    groups.objectKey(childIndex),
                    childIndex,
                    if (groups.isNode(childIndex)) 1 else groups.nodeCount(childIndex),
                    index++
                )
            )
            childIndex += groups.groupSize(childIndex)
        }
        return result
    }

    /**
     * Create an anchor to the current reader location or [index].
     */
    fun anchor(index: Int = currentGroup) = table.anchors.getOrAdd(index, groupsSize) {
        Anchor(index)
    }

    private fun IntArray.node(index: Int) = if (isNode(index)) {
        slots[nodeIndex(index)]
    } else Composer.Empty
    private fun IntArray.aux(index: Int) = if (hasAux(index)) {
        slots[auxIndex(index)]
    } else Composer.Empty
    private fun IntArray.objectKey(index: Int) = if (hasObjectKey(index)) {
        slots[objectKeyIndex(index)]
    } else null
}

/**
 * Information about groups and their keys.
 */
@InternalComposeApi
class KeyInfo internal constructor(
    /**
     * The group key.
     */
    val key: Int,

    /**
     * The object key for the group
     */
    val objectKey: Any?,

    /**
     * The location of the group.
     */
    val location: Int,

    /**
     * The number of nodes in the group. If the group is a node this is always 1.
     */
    val nodes: Int,

    /**
     * The index of the key info in the list returned by extractKeys
     */
    val index: Int
)

/**
 * The writer for a slot table. See [SlotTable] for details.
 */
internal class SlotWriter(
    /**
     * The [SlotTable] for whom this is writer.
     */
    internal val table: SlotTable
) {
    /**
     * The gap buffer for groups. This might change as groups are inserted and the array needs to
     * be expanded to account groups. The current valid groups occupy 0 until [groupGapStart]
     * followed [groupGapStart] + [groupGapLen] until groups.size where [groupGapStart]
     * until [groupGapStart] + [groupGapLen] is the gap.
     */
    private var groups: IntArray = table.groups

    /**
     * The gap buffer for the slots. This might change as slots are inserted an and the array
     * needs to be expanded to account for the new slots. The current valid slots occupy 0 until
     * [slotsGapStart] and [slotsGapStart] + [slotsGapLen] until slots.size where [slotsGapStart]
     * until [slotsGapStart] + [slotsGapLen] is the gap.
     */
    private var slots: Array<Any?> = table.slots

    /**
     * A copy of the [SlotWriter.anchors] to avoid having to index through [table].
     */
    private var anchors: ArrayList<Anchor> = table.anchors

    /**
     * Group index of the start of the gap in the groups array.
     */
    private var groupGapStart: Int = table.groupsSize

    /**
     * The number of groups in the gap in the groups array.
     */
    private var groupGapLen: Int = groups.size / Group_Fields_Size - table.groupsSize

    /**
     * The index end of the current group.
     */
    private var currentGroupEnd = table.groupsSize

    /**
     * The location of the [slots] array that contains the data for the [parent] group.
     */
    private var currentSlot = 0

    /**
     * The location of the index in [slots] after the slots for the [parent] group.
     */
    private var currentSlotEnd = 0

    /**
     * The is the index of gap in the [slots] array.
     */
    private var slotsGapStart: Int = table.slotsSize

    /**
     * The number of slots in the gop in the [slots] array.
     */
    private var slotsGapLen: Int = slots.size - table.slotsSize

    /**
     * The owner of the gap is the first group that has a end relative index.
     */
    private var slotsGapOwner = table.groupsSize

    /**
     * The number of times [beginInsert] has been called.
     */
    private var insertCount = 0

    /**
     * The number of nodes in the current group. Used to track when nodes are being added and
     * removed in the [parent] group. Once [endGroup] is called, if the nodes count has changed,
     * the containing groups are updated until a node group is encountered.
     */
    private var nodeCount = 0

    /**
     * A stack of the groups that have been explicitly started. A group can be implicitly started
     * by using [seek] to seek to indirect child and calling [startGroup] on that child. The
     * groups implicitly started groups will be updated when the [endGroup] is called for the
     * indirect child group.
     */
    private val startStack = IntStack()

    /**
     * A stack of the [currentGroupEnd] corresponding with the group is [startStack]. As groups
     * are ended by calling [endGroup], the size of the group might have changed. This stack is a
     * stack of enc group anchors where will reflect the group size change when it is restored by
     * calling [restoreCurrentGroupEnd].
     */
    private val endStack = IntStack()

    /**
     * This a count of the [nodeCount] of the explicitly started groups.
     */
    private val nodeCountStack = IntStack()

    /**
     * The current group that will be started by [startGroup] or skipped by [skipGroup]
     */
    var currentGroup = 0
        private set

    /**
     * True if at the end of a group and an [endGroup] is expected.
     */
    val isGroupEnd get() = currentGroup == currentGroupEnd

    /**
     * Return true if the current slot starts a node. A node is a kind of group so this will
     * return true for isGroup as well.
     */
    val isNode get() =
        currentGroup < currentGroupEnd && groups.isNode(groupIndexToAddress(currentGroup))

    /**
     * Return the key for the group at [index].
     */
    fun groupKey(index: Int): Int = groups.key(groupIndexToAddress(index))

    /**
     * Return the object key for the group at [index], if it has one, or null if not.
     */
    fun groupObjectKey(index: Int): Any? {
        val address = groupIndexToAddress(index)
        return if (groups.hasObjectKey(address)) slots[groups.objectKeyIndex(address)] else null
    }

    /**
     * Return the size of the group at [index].
     */
    fun groupSize(index: Int): Int = groups.groupSize(groupIndexToAddress(index))

    /**
     * Return the aux of the group at [index].
     */
    fun groupAux(index: Int): Any? {
        val address = groupIndexToAddress(index)
        return if (groups.hasAux(address)) slots[groups.auxIndex(address)] else Composer.Empty
    }

    /**
     * Return the node at [index] if [index] is a node group or null.
     */
    fun node(index: Int): Any? {
        val address = groupIndexToAddress(index)
        return if (groups.isNode(address))
            slots[dataIndexToDataAddress(groups.nodeIndex(address))]
        else null
    }

    /**
     * Return the node at [anchor] if it is a node group or null.
     */
    fun node(anchor: Anchor) = node(anchor.toIndexFor(this))

    /**
     * Return the index of the nearest group that contains [currentGroup].
     */
    var parent: Int = -1
        private set

    /**
     * Return the index of the parent for the group at [index].
     */
    fun parent(index: Int) = groups.parent(index)

    /**
     * Return the index of the parent for the group referenced by [anchor]. If the anchor is not
     * valid it returns -1.
     */
    fun parent(anchor: Anchor) = if (anchor.valid) groups.parent(anchorIndex(anchor)) else -1

    /**
     * True if the writer has been closed
     */
    var closed = false
        private set

    /**
     * Close the writer
     */
    fun close() {
        closed = true
        // Ensure, for readers, there is no gap
        moveGroupGapTo(size)
        moveSlotGapTo(slots.size - slotsGapLen, groupGapStart)
        table.close(
            writer = this,
            groups = groups,
            groupsSize = groupGapStart,
            slots = slots,
            slotsSize = slotsGapStart,
            anchors = anchors
        )
    }

    /**
     * Set the value of the next slot. Returns the previous value of the slot or [Composer.Empty]
     * is being inserted.
     */
    fun update(value: Any?): Any? {
        val result = skip()
        set(value)
        return result
    }

    /**
     * Updates the data for the current data group.
     */
    fun updateAux(value: Any?) {
        val address = groupIndexToAddress(currentGroup)
        check(groups.hasAux(address)) {
            "Updating the data of a group that was not created with a data slot"
        }
        slots[dataIndexToDataAddress(groups.auxIndex(address))] = value
    }

    /**
     * Updates the node for the current node group to [value].
     */
    fun updateNode(value: Any?) = updateNodeOfGroup(currentGroup, value)

    /**
     * Update the node of a the group at [anchor] to [value].
     */
    fun updateNode(anchor: Anchor, value: Any?) = updateNodeOfGroup(anchor.toIndexFor(this), value)

    /**
     * Updates the node of the parent group.
     */
    fun updateParentNode(value: Any?) = updateNodeOfGroup(parent, value)

    /**
     * Set the value at the groups current data slot
     */
    fun set(value: Any?) {
        check(currentSlot <= currentSlotEnd) {
            "Writing to an invalid slot"
        }
        slots[dataIndexToDataAddress(currentSlot - 1)] = value
    }

    /**
     * Set the group's slot at [index] to [value]. Returns the previous value.
     */
    fun set(index: Int, value: Any?): Any? {
        val address = groupIndexToAddress(currentGroup)
        val slotsStart = groups.slotIndex(address)
        val slotsEnd = groups.dataIndex(groupIndexToAddress(currentGroup + 1))
        val slotsIndex = slotsStart + index
        @Suppress("ConvertTwoComparisonsToRangeCheck")
        check(slotsIndex >= slotsStart && slotsIndex < slotsEnd) {
            "Write to an invalid slot index $index for group $currentGroup"
        }
        val slotAddress = dataIndexToDataAddress(slotsIndex)
        val result = slots[slotAddress]
        slots[slotAddress] = value
        return result
    }

    /**
     * Skip the current slot without updating. If the slot table is inserting then and
     * [Composer.Empty] slot is added and [skip] return [Composer.Empty].
     */
    fun skip(): Any? {
        if (insertCount > 0) {
            insertSlots(1, parent)
        }
        return slots[dataIndexToDataAddress(currentSlot++)]
    }

    /**
     * Advance [currentGroup] by [amount]. The [currentGroup] group cannot be advanced outside the
     * currently started [parent].
     */
    fun advanceBy(amount: Int) {
        require(amount >= 0) { "Cannot seek backwards" }
        check(insertCount <= 0) { "Cannot call seek() while inserting" }
        val index = currentGroup + amount
        @Suppress("ConvertTwoComparisonsToRangeCheck")
        check(index >= parent && index <= currentGroupEnd) {
            "Cannot seek outside the current group ($parent-$currentGroupEnd)"
        }
        this.currentGroup = index
        val newSlot = groups.dataIndex(groupIndexToAddress(index))
        this.currentSlot = newSlot
        this.currentSlotEnd = newSlot
    }

    /**
     * Seek the current location to [anchor]. The [anchor] must be an anchor to a possibly
     * indirect child of [parent].
     */
    fun seek(anchor: Anchor) = advanceBy(anchor.toIndexFor(this) - currentGroup)

    /**
     * Skip to the end of the current group.
     */
    fun skipToGroupEnd() {
        val newGroup = currentGroupEnd
        currentGroup = newGroup
        currentSlot = groups.dataIndex(groupIndexToAddress(newGroup))
    }

    /**
     * Begin inserting at the current location. beginInsert() can be nested and must be called with
     * a balanced number of endInsert()
     */
    fun beginInsert() {
        if (insertCount++ == 0) {
            saveCurrentGroupEnd()
        }
    }

    /**
     * Ends inserting.
     */
    fun endInsert() {
        check(insertCount > 0) { "Unbalanced begin/end insert" }
        if (--insertCount == 0) {
            check(nodeCountStack.size == startStack.size) {
                "startGroup/endGroup mismatch while inserting"
            }
            restoreCurrentGroupEnd()
        }
    }

    /**
     * Enter the group at current without changing it. Requires not currently inserting.
     */
    fun startGroup() {
        require(insertCount == 0) { "Key must be supplied when inserting" }
        startGroup(key = 0, objectKey = Composer.Empty, isNode = false, aux = Composer.Empty)
    }

    /**
     * Start a group with a integer key
     */
    fun startGroup(key: Int) = startGroup(key, Composer.Empty, isNode = false, aux = Composer.Empty)

    /**
     * Start a group with a data key
     */
    fun startGroup(key: Int, dataKey: Any?) = startGroup(
        key,
        dataKey,
        isNode = false,
        aux = Composer.Empty
    )

    /**
     * Start a node.
     */
    fun startNode(key: Any?) = startGroup(NodeKey, key, isNode = true, aux = Composer.Empty)

    /**
     * Start a node
     */
    fun startNode(key: Any?, node: Any?) = startGroup(NodeKey, key, isNode = true, aux = node)

    /**
     * Start a data group.
     */
    fun startData(key: Int, objectKey: Any?, aux: Any?) = startGroup(
        key,
        objectKey,
        isNode = false,
        aux = aux
    )

    /**
     * Start a data group.
     */
    fun startData(key: Int, aux: Any?) = startGroup(key, Composer.Empty, isNode = false, aux = aux)

    private fun startGroup(key: Int, objectKey: Any?, isNode: Boolean, aux: Any?) {
        val inserting = insertCount > 0
        nodeCountStack.push(nodeCount)

        currentGroupEnd = if (inserting) {
            insertGroups(1)
            val current = currentGroup
            val currentAddress = groupIndexToAddress(current)
            val hasObjectKey = objectKey !== Composer.Empty
            val hasAux = !isNode && aux !== Composer.Empty
            groups.initGroup(
                address = currentAddress,
                key = key,
                isNode = isNode,
                hasDataKey = hasObjectKey,
                hasData = hasAux,
                parentAnchor = parent,
                dataAnchor = currentSlot
            )
            currentSlotEnd = currentSlot

            val dataSlotsNeeded = (if (isNode) 1 else 0) +
                (if (hasObjectKey) 1 else 0) +
                (if (hasAux) 1 else 0)
            if (dataSlotsNeeded > 0) {
                insertSlots(dataSlotsNeeded, current)
                val slots = slots
                var currentSlot = currentSlot
                if (isNode) slots[currentSlot++] = aux
                if (hasObjectKey) slots[currentSlot++] = objectKey
                if (hasAux) slots[currentSlot++] = aux
                this.currentSlot = currentSlot
            }
            nodeCount = 0
            val newCurrent = current + 1
            this.parent = current
            this.currentGroup = newCurrent
            newCurrent
        } else {
            val previousParent = parent
            startStack.push(previousParent)
            saveCurrentGroupEnd()
            val currentGroup = currentGroup
            val currentGroupAddress = groupIndexToAddress(currentGroup)
            if (aux != Composer.Empty) {
                if (isNode)
                    updateNode(aux)
                else
                    updateAux(aux)
            }
            currentSlot = groups.slotIndex(currentGroupAddress)
            currentSlotEnd = groups.dataIndex(
                groupIndexToAddress(this.currentGroup + 1)
            )
            nodeCount = groups.nodeCount(currentGroupAddress)

            this.parent = currentGroup
            this.currentGroup = currentGroup + 1
            currentGroup + groups.groupSize(currentGroupAddress)
        }
    }

    /**
     * End the current group. Must be called after the corresponding startGroup().
     */
    fun endGroup(): Int {
        val inserting = insertCount > 0
        val currentGroup = currentGroup
        val currentGroupEnd = currentGroupEnd

        val groupIndex = parent
        val groupAddress = groupIndexToAddress(groupIndex)
        val newNodes = nodeCount
        val newGroupSize = currentGroup - groupIndex
        val isNode = groups.isNode(groupAddress)
        if (inserting) {
            groups.updateGroupSize(groupAddress, newGroupSize)
            groups.updateNodeCount(groupAddress, newNodes)
            nodeCount = nodeCountStack.pop() + if (isNode) 1 else newNodes
            parent = groups.parent(groupIndex)
        } else {
            require(currentGroup == currentGroupEnd) {
                "Expected to be at the end of a group"
            }
            // Update group length
            val oldGroupSize = groups.groupSize(groupAddress)
            val oldNodes = groups.nodeCount(groupAddress)
            groups.updateGroupSize(groupAddress, newGroupSize)
            groups.updateNodeCount(groupAddress, newNodes)
            val newParent = startStack.pop()
            restoreCurrentGroupEnd()
            this.parent = newParent
            val groupParent = groups.parent(groupIndex)
            nodeCount = nodeCountStack.pop()
            if (groupParent == newParent) {
                // The parent group was started we just need to update the node count.
                nodeCount += if (isNode) 0 else newNodes - oldNodes
            } else {
                // If we are closing a group for which startGroup was called after calling
                // seek(). startGroup allows the indirect children to be started. If the group
                // has changed size or the number of nodes it contains the groups between the
                // group being closed and the group that is currently open need to be adjusted.
                // This allows the caller to avoid the overhead of needing to start and end the
                // groups explicitly.
                val groupSizeDelta = newGroupSize - oldGroupSize
                var nodesDelta = if (isNode) 0 else newNodes - oldNodes
                if (groupSizeDelta != 0 || nodesDelta != 0) {
                    var current = groupParent
                    while (
                        current != 0 &&
                        current != newParent &&
                        (nodesDelta != 0 || groupSizeDelta != 0)
                    ) {
                        val currentAddress = groupIndexToAddress(current)
                        if (groupSizeDelta != 0) {
                            val newSize = groups.groupSize(currentAddress) + groupSizeDelta
                            groups.updateGroupSize(currentAddress, newSize)
                        }
                        if (nodesDelta != 0) {
                            groups.updateNodeCount(
                                currentAddress,
                                groups.nodeCount(currentAddress) + nodesDelta
                            )
                        }
                        if (groups.isNode(currentAddress)) nodesDelta = 0
                        current = groups.parent(current)
                    }
                }
                nodeCount += nodesDelta
            }
        }
        return newNodes
    }

    /**
     * If the start of a group was skipped using [skip], calling [ensureStarted] puts the writer
     * into the same state as if [startGroup] or [startNode] was called on the group starting at
     * [index]. If, after starting, the group, [currentGroup] is not a the end of the group or
     * [currentGroup] is not at the start of a group for which [index] is not location the parent
     * group, an exception is thrown.
     *
     * Calling [ensureStarted] implies that an [endGroup] should be called once the end of the
     * group is reached.
     */
    fun ensureStarted(index: Int) {
        require(insertCount <= 0) { "Cannot call ensureStarted() while inserting" }
        val parent = parent
        if (parent != index) {
            // The new parent a child of the current group.
            @Suppress("ConvertTwoComparisonsToRangeCheck")
            require(index >= parent && index < currentGroupEnd) {
                "Started group must be a subgroup of the group at $parent"
            }

            val oldCurrent = currentGroup
            val oldCurrentSlot = currentSlot
            val oldCurrentSlotEnd = currentSlotEnd
            currentGroup = index
            startGroup()
            currentGroup = oldCurrent
            currentSlot = oldCurrentSlot
            currentSlotEnd = oldCurrentSlotEnd
        }
    }

    fun ensureStarted(anchor: Anchor) = ensureStarted(anchor.toIndexFor(this))

    /**
     *  Skip the current group. Returns the number of nodes skipped by skipping the group.
     */
    fun skipGroup(): Int {
        val groupAddress = groupIndexToAddress(currentGroup)
        val newGroup = currentGroup + groups.groupSize(groupAddress)
        this.currentGroup = newGroup
        this.currentSlot = groups.dataIndex(groupIndexToAddress(newGroup))
        return if (groups.isNode(groupAddress)) 1 else groups.nodeCount(groupAddress)
    }

    /**
     * Remove the current group. Returns if any anchors were in the group removed.
     */
    fun removeGroup(): Boolean {
        require(insertCount == 0) { "Cannot remove group while inserting" }
        val oldGroup = currentGroup
        val oldSlot = currentSlot
        val count = skipGroup()
        val anchorsRemoved = removeGroups(oldGroup, currentGroup - oldGroup)
        removeSlots(oldSlot, currentSlot - oldSlot, oldGroup - 1)
        currentGroup = oldGroup
        currentSlot = oldSlot
        nodeCount -= count
        return anchorsRemoved
    }

    /**
     * Returns an iterator for all the slots of group and all the children of the group.
     */
    fun groupSlots(): Iterator<Any?> {
        val start = groups.dataIndex(groupIndexToAddress(currentGroup))
        val end = groups.dataIndex(
            groupIndexToAddress(currentGroup + groupSize(currentGroup))
        )
        return object : Iterator<Any?> {
            var current = start
            override fun hasNext(): Boolean = current < end
            override fun next(): Any? =
                if (hasNext()) slots[dataIndexToDataAddress(current++)] else null
        }
    }

    /**
     * Move the group at [offset] groups after [currentGroup] to be in front of [currentGroup].
     * After this completes, the moved group will be the current group. [offset] must less than the
     * number of groups after the [currentGroup] left in the [parent] group.
     */
    fun moveGroup(offset: Int) {
        require(insertCount == 0) { "Cannot move a group while inserting" }
        require(offset >= 0) { "Parameter offset is out of bounds" }
        if (offset == 0) return
        val current = currentGroup
        val parent = parent
        val parentEnd = currentGroupEnd

        // Find the group to move
        var count = offset
        var groupToMove = current
        while (count > 0) {
            groupToMove += groups.groupSize(
                address = groupIndexToAddress(groupToMove)
            )
            require(groupToMove <= parentEnd) { "Parameter offset is out of bounds" }
            count--
        }

        val moveLen = groups.groupSize(
            address = groupIndexToAddress(groupToMove)
        )
        val currentSlot = currentSlot
        val dataStart = groups.dataIndex(groupIndexToAddress(groupToMove))
        val dataEnd = groups.dataIndex(
            address = groupIndexToAddress(
                index = groupToMove + moveLen
            )
        )
        val moveDataLen = dataEnd - dataStart

        // The order of operations is important here. Moving a block in the array requires,
        //
        //   1) inserting space for the block
        //   2) copying the block
        //   3) deleting the previous block
        //
        // Inserting into a gap buffer requires moving the gap to the location of the insert and
        // then shrinking the gap. Moving the gap in the slot table requires updating all anchors
        // in the group table that refer to locations that changed by the gap move. For this to
        // work correctly, the groups must be in a valid state. That requires that the slot table
        // must be inserted into first so there are no transitory constraint violations in the
        // groups (that is, there are no invalid, duplicate or out of order anchors). Conversely,
        // removing slots also involves moving the gap requiring the groups to be valid so the
        // slots must be removed after the groups that reference the old locations are removed.
        // So the order of operations when moving groups is,
        //
        //  1) insert space for the slots at the destination (must be first)
        //  2) insert space for the groups at the destination
        //  3) copy the groups to their new location
        //  4) copy the slots to their new location
        //  5) fix-up the moved group anchors to refer to the new slot locations
        //  6) update any anchors in the group being moved
        //  7) remove the old groups
        //  8) fix parent anchors
        //  9) remove the old slots (must be last)

        // 1) insert space for the slots at the destination (must be first)
        insertSlots(moveDataLen, max(currentGroup - 1, 0))

        //  2) insert space for the groups at the destination
        insertGroups(moveLen)

        //  3) copy the groups to their new location
        val groups = groups
        val moveLocationAddress = groupIndexToAddress(groupToMove + moveLen)
        val moveLocationOffset = moveLocationAddress * Group_Fields_Size
        val currentAddress = groupIndexToAddress(current)
        groups.copyInto(
            destination = groups,
            destinationOffset = currentAddress * Group_Fields_Size,
            startIndex = moveLocationOffset,
            endIndex = moveLocationOffset + moveLen * Group_Fields_Size
        )

        //  4) copy the slots to their new location
        if (moveDataLen > 0) {
            val slots = slots
            slots.copyInto(
                destination = slots,
                destinationOffset = currentSlot,
                startIndex = dataIndexToDataAddress(dataStart + moveDataLen),
                endIndex = dataIndexToDataAddress(dataEnd + moveDataLen)
            )
        }
        //  5) fix-up the moved group anchors to refer to the new slot locations
        val dataMoveDistance = (dataStart + moveDataLen) - currentSlot
        val slotsGapStart = slotsGapStart
        val slotsGapLen = slotsGapLen
        val slotsCapacity = slots.size
        val slotsGapOwner = slotsGapOwner
        for (group in current until current + moveLen) {
            val groupAddress = groupIndexToAddress(group)
            val oldIndex = groups.dataIndex(groupAddress)
            val newIndex = oldIndex - dataMoveDistance
            val newAnchor = dataIndexToDataAnchor(
                index = newIndex,
                gapStart = if (slotsGapOwner < groupAddress) 0 else slotsGapStart,
                gapLen = slotsGapLen,
                capacity = slotsCapacity
            )
            groups.updateDataIndex(groupAddress, newAnchor)
        }

        //  6) update any anchors in the group being moved
        moveAnchors(groupToMove + moveLen, current, moveLen)

        //  7) remove the old groups
        val anchorsRemoved = removeGroups(groupToMove + moveLen, moveLen)
        check(!anchorsRemoved) { "Unexpectedly removed anchors" }

        //  8) fix parent anchors
        fixParentAnchorsFor(parent, currentGroupEnd, current)

        //  9) remove the old slots (must be last)
        if (moveDataLen > 0) {
            removeSlots(dataStart + moveDataLen, moveDataLen, groupToMove + moveLen - 1)
        }
    }

    /**
     * Move (insert and then delete) the group at [index] from [slots]. All anchors in the range
     * (including [index]) are moved to the slot table for which this is a reader.
     *
     * It is required that the writer be inserting.
     *
     * @return a list of the anchors that were moved
     */
    fun moveFrom(table: SlotTable, index: Int): List<Anchor> {
        require(insertCount > 0)

        if (index == 0 && currentGroup == 0 && this.table.groupsSize == 0) {
            // Special case for moving the entire slot table into an empty table. This case occurs
            // during initial composition.
            val myGroups = groups
            val mySlots = slots
            val myAnchors = anchors
            val groups = table.groups
            val groupsSize = table.groupsSize
            val slots = table.slots
            val slotsSize = table.slotsSize
            this.groups = groups
            this.slots = slots
            this.anchors = table.anchors
            this.groupGapStart = groupsSize
            this.groupGapLen = groups.size / Group_Fields_Size - groupsSize
            this.slotsGapStart = slotsSize
            this.slotsGapLen = slots.size - slotsSize
            this.slotsGapOwner = groupsSize

            table.setTo(myGroups, 0, mySlots, 0, myAnchors)
            return this.anchors
        }

        return table.write { tableWriter ->
            val groupsToMove = tableWriter.groupSize(index)
            val sourceGroupsEnd = index + groupsToMove
            val sourceSlotsStart = tableWriter.dataIndex(index)
            val sourceSlotsEnd = tableWriter.dataIndex(sourceGroupsEnd)
            val slotsToMove = sourceSlotsEnd - sourceSlotsStart

            // Make room in the slot table
            insertGroups(groupsToMove)
            insertSlots(slotsToMove, currentGroup)

            // Copy the groups and slots
            val groups = groups
            val currentGroup = currentGroup
            tableWriter.groups.copyInto(
                destination = groups,
                destinationOffset = currentGroup * Group_Fields_Size,
                startIndex = index * Group_Fields_Size,
                endIndex = sourceGroupsEnd * Group_Fields_Size
            )
            val slots = slots
            val currentSlot = currentSlot
            tableWriter.slots.copyInto(
                destination = slots,
                destinationOffset = currentSlot,
                startIndex = sourceSlotsStart,
                endIndex = sourceSlotsEnd
            )

            // Fix the parent anchors and data anchors. This would read better as two loops but
            // conflating the loops has better locality of reference.
            groups.updateParentAnchor(currentGroup, parent)
            val parentDelta = currentGroup - index
            val moveEnd = currentGroup + groupsToMove
            val dataIndexDelta = currentSlot - groups.dataIndex(currentGroup)
            var slotsGapOwner = slotsGapOwner
            val slotsGapLen = slotsGapLen
            val slotsCapacity = slots.size
            for (groupAddress in currentGroup until moveEnd) {
                // Update the parent anchor, the first group has already been set.
                if (groupAddress != currentGroup) {
                    val previousParent = groups.parentAnchor(groupAddress)
                    groups.updateParentAnchor(groupAddress, previousParent + parentDelta)
                }

                val newDataIndex = groups.dataIndex(groupAddress) + dataIndexDelta
                val newDataAnchor = dataIndexToDataAnchor(
                    newDataIndex,
                    // Ensure that if the slotGapOwner is below groupAddress we get an end relative
                    // anchor
                    if (slotsGapOwner < groupAddress) 0 else slotsGapStart,
                    slotsGapLen,
                    slotsCapacity
                )

                // Update the data index
                groups.updateDataAnchor(groupAddress, newDataAnchor)

                // Move the slotGapOwner if necessary
                if (groupAddress == slotsGapOwner) slotsGapOwner++
            }
            this.slotsGapOwner = slotsGapOwner

            // Extract the anchors in range
            val startAnchors = table.anchors.locationOf(index, table.groupsSize)
            val endAnchors = table.anchors.locationOf(sourceGroupsEnd, table.groupsSize)
            val anchors = if (startAnchors < endAnchors) {
                val sourceAnchors = table.anchors
                val anchors = ArrayList<Anchor>(endAnchors - startAnchors)

                // update the anchor locations to their new location
                val anchorDelta = currentGroup - index
                for (anchorIndex in startAnchors until endAnchors) {
                    val sourceAnchor = sourceAnchors[anchorIndex]
                    sourceAnchor.location += anchorDelta
                    anchors.add(sourceAnchor)
                }

                // Insert them into the new table
                val insertLocation = this.anchors.locationOf(this.currentGroup, size)
                this.table.anchors.addAll(insertLocation, anchors)

                // Remove them from the old table
                sourceAnchors.subList(startAnchors, endAnchors).clear()

                anchors
            } else emptyList()

            // Remove the group using the sequence the writer expects when removing a group, that
            // is the root group and the group's parent group must be correctly started and ended
            // when it is not a root group.
            val parentGroup = tableWriter.parent(index)
            if (parentGroup >= 0) {
                // If we are not a root group then we are removing from a group so ensure the
                // root group is started and then seek to the parent group and start it.
                tableWriter.startGroup()
                tableWriter.advanceBy(parentGroup - tableWriter.currentGroup)
                tableWriter.startGroup()
            }
            tableWriter.advanceBy(index - tableWriter.currentGroup)
            val anchorsRemoved = tableWriter.removeGroup()
            if (parentGroup >= 0) {
                tableWriter.skipToGroupEnd()
                tableWriter.endGroup()
                tableWriter.skipToGroupEnd()
                tableWriter.endGroup()
            }

            // Ensure we correctly transplanted the correct groups.
            check(!anchorsRemoved) { "Unexpectedly removed anchors" }

            // Update the node count.
            nodeCount += groups.nodeCount(currentGroup)

            // Move current passed the insert
            this.currentGroup = currentGroup + groupsToMove
            this.currentSlot = currentSlot + slotsToMove
            anchors
        }
    }

    /**
     * Allocate an anchor to the current group or [index].
     */
    fun anchor(index: Int = currentGroup): Anchor = anchors.getOrAdd(index, size) {
        Anchor(if (index <= groupGapStart) index else -(size - index))
    }

    /**
     * Return the current anchor location while changing the slot table.
     */
    fun anchorIndex(anchor: Anchor) = anchor.location.let { if (it < 0) size + it else it }

    override fun toString(): String {
        return "SlotWriter(current = $currentGroup end=$currentGroupEnd size = $size " +
            "gap=$groupGapStart-${groupGapStart + groupGapLen})"
    }

    /**
     * Save [currentGroupEnd] to [endStack].
     */
    private fun saveCurrentGroupEnd() {
        // Record the end location as relative to the end of the slot table so when we pop it
        // back off again all inserts and removes that happened while a child group was open
        // are already reflected into its value.
        endStack.push(capacity - groupGapLen - currentGroupEnd)
    }

    /**
     * Restore [currentGroupEnd] from [endStack].
     */
    private fun restoreCurrentGroupEnd(): Int {
        val newGroupEnd = (capacity - groupGapLen) - endStack.pop()
        currentGroupEnd = newGroupEnd
        return newGroupEnd
    }

    /**
     * As groups move their parent anchors need to be updated. This recursively updates the
     * parent anchors [parent] starting at [firstChild] and ending at [endGroup]. These are
     * passed as a parameter to as the [groups] does not contain the current values for [parent]
     * yet.
     */
    private fun fixParentAnchorsFor(parent: Int, endGroup: Int, firstChild: Int) {
        val parentAnchor = parentIndexToAnchor(parent, groupGapStart)
        var child = firstChild
        while (child < endGroup) {
            groups.updateParentAnchor(groupIndexToAddress(child), parentAnchor)
            val childEnd = child + groups.groupSize(groupIndexToAddress(child))
            fixParentAnchorsFor(child, childEnd, child + 1)
            child = childEnd
        }
    }

    /**
     * Move the gap in [groups] to [index].
     */
    private fun moveGroupGapTo(index: Int) {
        val gapLen = groupGapLen
        val gapStart = groupGapStart
        if (gapStart != index) {
            if (anchors.isNotEmpty()) updateAnchors(gapStart, index)
            if (gapLen > 0) {
                val groups = groups
                // Here physical is used to mean an index of the actual first int of the group in the
                // array as opposed ot the logical address which is in groups of Group_Field_Size
                // integers. IntArray.copyInto expects physical indexes.
                val groupPhysicalAddress = index * Group_Fields_Size
                val groupPhysicalGapLen = gapLen * Group_Fields_Size
                val groupPhysicalGapStart = gapStart * Group_Fields_Size
                if (index < gapStart) {
                    groups.copyInto(
                        destination = groups,
                        destinationOffset = groupPhysicalAddress + groupPhysicalGapLen,
                        startIndex = groupPhysicalAddress,
                        endIndex = groupPhysicalGapStart
                    )
                } else {
                    groups.copyInto(
                        destination = groups,
                        destinationOffset = groupPhysicalGapStart,
                        startIndex = groupPhysicalGapStart + groupPhysicalGapLen,
                        endIndex = groupPhysicalAddress + groupPhysicalGapLen
                    )
                }
            }

            // Gap has moved so the anchor for the groups that moved have changed so the parent
            // anchors that refer to these groups must be updated.
            var groupAddress = if (index < gapStart) index + gapLen else gapStart
            val capacity = capacity
            check(groupAddress < capacity)
            while (groupAddress < capacity) {
                val oldAnchor = groups.parentAnchor(groupAddress)
                val oldIndex = parentAnchorToIndex(oldAnchor)
                val newAnchor = parentIndexToAnchor(oldIndex, index)
                if (newAnchor != oldAnchor) {
                    groups.updateParentAnchor(groupAddress, newAnchor)
                }
                groupAddress++
                if (groupAddress == index) groupAddress += gapLen
            }
        }
        this.groupGapStart = index
    }

    /**
     * Move the gap in [slots] to [index] where [group] is expected to receive any new slots added.
     */
    private fun moveSlotGapTo(index: Int, group: Int) {
        val gapLen = slotsGapLen
        val gapStart = slotsGapStart
        val slotsGapOwner = slotsGapOwner
        if (gapStart != index) {
            val slots = slots
            if (index < gapStart) {
                // move the gap down to index by shifting the data up.
                slots.copyInto(
                    destination = slots,
                    destinationOffset = index + gapLen,
                    startIndex = index,
                    endIndex = gapStart
                )
            } else {
                // Shift the data down, leaving the gap at index
                slots.copyInto(
                    destination = slots,
                    destinationOffset = gapStart,
                    startIndex = gapStart + gapLen,
                    endIndex = index + gapLen
                )
            }

            // Clear the gap in the data array
            slots.fill(null, index, index + gapLen)
        }

        // Update the data anchors affected by the move
        val newSlotsGapOwner = min(group + 1, size)
        if (slotsGapOwner != newSlotsGapOwner) {
            val slotsSize = slots.size - gapLen
            if (newSlotsGapOwner < slotsGapOwner) {
                var updateAddress = groupIndexToAddress(newSlotsGapOwner)
                val stopUpdateAddress = groupIndexToAddress(slotsGapOwner)
                val groupGapStart = groupGapStart
                while (updateAddress < stopUpdateAddress) {
                    val anchor = groups.dataAnchor(updateAddress)
                    check(anchor >= 0) {
                        "Unexpected anchor value, expected a positive anchor"
                    }
                    groups.updateDataAnchor(updateAddress, -(slotsSize - anchor + 1))
                    updateAddress++
                    if (updateAddress == groupGapStart) updateAddress += groupGapLen
                }
            } else {
                var updateAddress = groupIndexToAddress(slotsGapOwner)
                val stopUpdateAddress = groupIndexToAddress(newSlotsGapOwner)
                while (updateAddress < stopUpdateAddress) {
                    val anchor = groups.dataAnchor(updateAddress)
                    check(anchor < 0) {
                        "Unexpected anchor value, expected a negative anchor"
                    }
                    groups.updateDataAnchor(updateAddress, slotsSize + anchor + 1)
                    updateAddress++
                    if (updateAddress == groupGapStart) updateAddress += groupGapLen
                }
            }
            this.slotsGapOwner = newSlotsGapOwner
        }
        this.slotsGapStart = index
    }

    /**
     * Insert [size] number of groups in front of [currentGroup]. These groups are implicitly a
     * child of [parent].
     */
    private fun insertGroups(size: Int) {
        if (size > 0) {
            val currentGroup = currentGroup
            moveGroupGapTo(currentGroup)
            val gapStart = groupGapStart
            var gapLen = groupGapLen
            val oldCapacity = groups.size / Group_Fields_Size
            val oldSize = oldCapacity - gapLen
            if (gapLen < size) {
                // Create a bigger gap
                val groups = groups

                // Double the size of the array, but at least MinGrowthSize and >= size
                val newCapacity = max(
                    max(oldCapacity * 2, oldSize + size),
                    MinGroupGrowthSize
                )
                val newGroups = IntArray(newCapacity * Group_Fields_Size)
                val newGapLen = newCapacity - oldSize
                val oldGapEndAddress = gapStart + gapLen
                val newGapEndAddress = gapStart + newGapLen

                // Copy the old arrays into the new arrays
                groups.copyInto(
                    destination = newGroups,
                    destinationOffset = 0,
                    startIndex = 0,
                    endIndex = gapStart * Group_Fields_Size
                )
                groups.copyInto(
                    destination = newGroups,
                    destinationOffset = newGapEndAddress * Group_Fields_Size,
                    startIndex = oldGapEndAddress * Group_Fields_Size,
                    endIndex = oldCapacity * Group_Fields_Size
                )

                // Update the gap and slots
                this.groups = newGroups
                gapLen = newGapLen
            }

            // Move the currentGroupEnd to account for inserted groups.
            val currentEnd = currentGroupEnd
            if (currentEnd >= gapStart) this.currentGroupEnd = currentEnd + size

            // Update the gap start and length
            this.groupGapStart = gapStart + size
            this.groupGapLen = gapLen - size

            // Replicate the current group data index to the new slots
            val index = if (oldSize > 0) dataIndex(currentGroup + size) else 0

            // If the slotGapOwner is before the current location ensure we get end relative offsets
            val anchor = dataIndexToDataAnchor(
                index,
                if (slotsGapOwner < gapStart) 0 else slotsGapStart,
                slotsGapLen,
                slots.size
            )
            for (groupAddress in gapStart until gapStart + size) {
                groups.updateDataAnchor(groupAddress, anchor)
            }
            val slotsGapOwner = slotsGapOwner
            if (slotsGapOwner >= gapStart) {
                this.slotsGapOwner = slotsGapOwner + size
            }
        }
    }

    /**
     * Insert room into the slot table. This is performed by first moving the gap to [currentSlot]
     * and then reducing the gap [size] slots. If the gap is smaller than [size] the gap is grown
     * to at least accommodate [size] slots. The new slots are associated with [group].
     */
    private fun insertSlots(size: Int, group: Int) {
        if (size > 0) {
            moveSlotGapTo(currentSlot, group)
            val gapStart = slotsGapStart
            var gapLen = slotsGapLen
            if (gapLen < size) {
                val slots = slots

                // Create a bigger gap
                val oldCapacity = slots.size
                val oldSize = oldCapacity - gapLen

                // Double the size of the array, but at least MinGrowthSize and >= size
                val newCapacity = max(
                    max(oldCapacity * 2, oldSize + size),
                    MinSlotsGrowthSize
                )
                val newData = Array<Any?>(newCapacity) { null }
                val newGapLen = newCapacity - oldSize
                val oldGapEndAddress = gapStart + gapLen
                val newGapEndAddress = gapStart + newGapLen

                // Copy the old arrays into the new arrays
                slots.copyInto(
                    destination = newData,
                    destinationOffset = 0,
                    startIndex = 0,
                    endIndex = gapStart
                )
                slots.copyInto(
                    destination = newData,
                    destinationOffset = newGapEndAddress,
                    startIndex = oldGapEndAddress,
                    endIndex = oldCapacity
                )

                // Update the gap and slots
                this.slots = newData
                gapLen = newGapLen
            }
            val currentDataEnd = currentSlotEnd
            if (currentDataEnd >= gapStart) this.currentSlotEnd = currentDataEnd + size
            this.slotsGapStart = gapStart + size
            this.slotsGapLen = gapLen - size
        }
    }

    /**
     * Remove [len] group from [start].
     */
    private fun removeGroups(start: Int, len: Int): Boolean {
        return if (len > 0) {
            var anchorsRemoved = false
            val anchors = anchors

            // Move the gap to start of the removal and grow the gap
            moveGroupGapTo(start)
            if (anchors.isNotEmpty()) anchorsRemoved = removeAnchors(start, len)
            groupGapStart = start
            val previousGapLen = groupGapLen
            val newGapLen = previousGapLen + len
            groupGapLen = newGapLen

            // Adjust the gap owner if necessary.
            val slotsGapOwner = slotsGapOwner
            if (slotsGapOwner > start) {
                this.slotsGapOwner = slotsGapOwner - len
            }
            if (currentGroupEnd >= groupGapStart) currentGroupEnd -= len
            anchorsRemoved
        } else false
    }

    /**
     * Remove [len] slots from [start].
     */
    private fun removeSlots(start: Int, len: Int, group: Int) {
        if (len > 0) {
            val gapLen = slotsGapLen
            val removeEnd = start + len
            moveSlotGapTo(removeEnd, group)
            slotsGapStart = start
            slotsGapLen = gapLen + len
            slots.fill(null, start, start + len)
            val currentDataEnd = currentSlotEnd
            if (currentDataEnd >= start) this.currentSlotEnd = currentDataEnd - len
        }
    }

    /**
     * A helper function to update the number of nodes in a group.
     */
    private fun updateNodeOfGroup(index: Int, value: Any?) {
        val address = groupIndexToAddress(index)
        check(address < groups.size && groups.isNode(address)) {
            "Updating the node of a group at $index that was not created with as a node group"
        }
        slots[dataIndexToDataAddress(groups.nodeIndex(address))] = value
    }

    /**
     * A helper function to update the anchors as the gap in [groups] moves.
     */
    private fun updateAnchors(previousGapStart: Int, newGapStart: Int) {
        val gapLen = groupGapLen
        val size = capacity - gapLen
        if (previousGapStart < newGapStart) {
            // Gap is moving up
            // All anchors between the new gap and the old gap switch to be anchored to the
            // front of the table instead of the end.
            var index = anchors.locationOf(previousGapStart, size)
            while (index < anchors.size) {
                val anchor = anchors[index]
                val location = anchor.location
                if (location < 0) {
                    val newLocation = size + location
                    if (newLocation < newGapStart) {
                        anchor.location = size + location
                        index++
                    } else break
                } else break
            }
        } else {
            // Gap is moving down. All anchors between newGapStart and previousGapStart need now
            // to be anchored to the end of the table instead of the front of the table.
            var index = anchors.locationOf(newGapStart, size)
            while (index < anchors.size) {
                val anchor = anchors[index]
                val location = anchor.location
                if (location >= 0) {
                    anchor.location = -(size - location)
                    index++
                } else break
            }
        }
    }

    /**
     * A helper function to remove the anchors for groups that are removed.
     */
    private fun removeAnchors(gapStart: Int, size: Int): Boolean {
        val gapLen = groupGapLen
        val removeEnd = gapStart + size
        val groupsSize = capacity - gapLen
        var index = anchors.locationOf(gapStart + size, groupsSize).let {
            if (it >= anchors.size) it - 1 else it
        }
        var removeAnchorEnd = 0
        var removeAnchorStart = index + 1
        while (index >= 0) {
            val anchor = anchors[index]
            val location = anchorIndex(anchor)
            if (location >= gapStart) {
                if (location < removeEnd) {
                    anchor.location = Int.MIN_VALUE
                    removeAnchorStart = index
                    if (removeAnchorEnd == 0) removeAnchorEnd = index + 1
                }
                index--
            } else break
        }
        return (removeAnchorStart < removeAnchorEnd).also {
            if (it) anchors.subList(removeAnchorStart, removeAnchorEnd).clear()
        }
    }

    /**
     * A helper function to update anchors for groups that have moved.
     */
    private fun moveAnchors(originalLocation: Int, newLocation: Int, size: Int) {
        val end = originalLocation + size
        val groupsSize = this.size

        // Remove all the anchors in range from the original location
        val index = anchors.locationOf(originalLocation, groupsSize)
        val removedAnchors = mutableListOf<Anchor>()
        if (index >= 0) {
            while (index < anchors.size) {
                val anchor = anchors[index]
                val location = anchorIndex(anchor)
                @Suppress("ConvertTwoComparisonsToRangeCheck")
                if (location >= originalLocation && location < end) {
                    removedAnchors.add(anchor)
                    anchors.removeAt(index)
                } else break
            }
        }

        // Insert the anchors into there new location
        val moveDelta = newLocation - originalLocation
        for (anchor in removedAnchors) {
            val anchorIndex = anchorIndex(anchor)
            val newAnchorIndex = anchorIndex + moveDelta
            if (newAnchorIndex >= groupGapStart) {
                anchor.location = -(groupsSize - newAnchorIndex)
            } else {
                anchor.location = newAnchorIndex
            }
            val insertIndex = anchors.locationOf(newAnchorIndex, groupsSize)
            anchors.add(insertIndex, anchor)
        }
    }

    /**
     * A debugging aid that emits [groups] as a string.
     */
    @Suppress("unused")
    fun groupsAsString(): String = buildString {
        for (index in 0 until size) {
            groupAsString(index)
            append('\n')
        }
    }

    /**
     * A debugging aid that emits a group as a string into a string builder.
     */
    private fun StringBuilder.groupAsString(index: Int) {
        val address = groupIndexToAddress(index)
        append("Group(")
        if (index < 10) append(' ')
        if (index < 100) append(' ')
        if (index < 1000) append(' ')
        append(index)
        append('#')
        append(groups.groupSize(address))
        append('^')
        append(parentAnchorToIndex(groups.parentAnchor(address)))
        append(": key=")
        append(groups.key(address))
        append(", nodes=")
        append(groups.nodeCount(address))
        append(", dataAnchor=")
        append(groups.dataAnchor(address))
        append(", parentAnchor=")
        append(groups.parentAnchor(address))
        append(")")
    }

    internal fun verifyDataAnchors() {
        var previousDataIndex = 0
        val owner = slotsGapOwner
        var ownerFound = false
        val slotsSize = slots.size - slotsGapLen
        for (index in 0 until size) {
            val address = groupIndexToAddress(index)
            val dataAnchor = groups.dataAnchor(address)
            val dataIndex = groups.dataIndex(address)
            check(dataIndex >= previousDataIndex) {
                "Data index out of order at $index, previous = $previousDataIndex, current = " +
                    "$dataIndex"
            }
            check(dataIndex <= slotsSize) {
                "Data index, $dataIndex, out of bound at $index"
            }
            if (dataAnchor < 0 && !ownerFound) {
                check(owner == index) {
                    "Expected the slot gap owner to be $owner found gap at $index"
                }
                ownerFound = true
            }
            previousDataIndex = dataIndex
        }
    }

    @Suppress("unused")
    internal fun verifyParentAnchors() {
        val gapStart = groupGapStart
        val gapLen = groupGapLen
        val capacity = capacity
        for (groupAddress in 0 until gapStart) {
            val parentAnchor = groups.parentAnchor(groupAddress)
            check(parentAnchor > parentAnchorPivot) {
                "Expected a start relative anchor at $groupAddress"
            }
        }
        for (groupAddress in gapStart + gapLen until capacity) {
            val parentAnchor = groups.parentAnchor(groupAddress)
            val parentIndex = parentAnchorToIndex(parentAnchor)
            if (parentIndex < gapStart) {
                check(parentAnchor > parentAnchorPivot) {
                    "Expected a start relative anchor at $groupAddress"
                }
            } else {
                check(parentAnchor <= parentAnchorPivot) {
                    "Expected an end relative anchor at $groupAddress"
                }
            }
        }
    }

    internal val size get() = capacity - groupGapLen
    private val capacity get() = groups.size / Group_Fields_Size

    private fun groupIndexToAddress(index: Int) =
        if (index < groupGapStart) index else index + groupGapLen

    private fun dataIndexToDataAddress(dataIndex: Int) =
        if (dataIndex < slotsGapStart) dataIndex else dataIndex + slotsGapLen

    private fun IntArray.parent(index: Int) =
        parentAnchorToIndex(parentAnchor(groupIndexToAddress(index)))

    private fun dataIndex(index: Int) = groups.dataIndex(groupIndexToAddress(index))

    private fun IntArray.dataIndex(address: Int) =
        if (address >= capacity) slots.size - slotsGapLen
        else dataAnchorToDataIndex(dataAnchor(address), slotsGapLen, slots.size)

    private fun IntArray.slotIndex(address: Int) =
        if (address >= capacity) slots.size - slotsGapLen
        else dataAnchorToDataIndex(slotAnchor(address), slotsGapLen, slots.size)

    private fun IntArray.updateDataIndex(address: Int, dataIndex: Int) {
        updateDataAnchor(
            address,
            dataIndexToDataAnchor(dataIndex, slotsGapStart, slotsGapLen, slots.size)
        )
    }

    private fun IntArray.nodeIndex(address: Int) = dataIndex(address)
    private fun IntArray.auxIndex(address: Int) =
        dataIndex(address) + countOneBits(groupInfo(address) shr (Aux_Shift + 1))

    @Suppress("unused")
    private fun IntArray.dataIndexes() = groups.dataAnchors().let {
        it.slice(0 until groupGapStart) +
            it.slice(groupGapStart + groupGapLen until (size / Group_Fields_Size))
    }.map { anchor -> dataAnchorToDataIndex(anchor, slotsGapLen, slots.size) }

    @Suppress("unused")
    private fun keys() = groups.keys().filterIndexed { index, _ ->
        index < groupGapStart || index >= groupGapStart + groupGapLen
    }

    private fun dataIndexToDataAnchor(index: Int, gapStart: Int, gapLen: Int, capacity: Int) =
        if (index > gapStart) -((capacity - gapLen) - index + 1) else index

    private fun dataAnchorToDataIndex(anchor: Int, gapLen: Int, capacity: Int) =
        if (anchor < 0) (capacity - gapLen) + anchor + 1 else anchor

    private fun parentIndexToAnchor(index: Int, gapStart: Int) =
        if (index < gapStart) index else -(size - index - parentAnchorPivot)

    private fun parentAnchorToIndex(index: Int) =
        if (index > parentAnchorPivot) index else size + index - parentAnchorPivot
}

private class GroupIterator(
    val table: SlotTable,
    start: Int,
    val end: Int
) : Iterator<CompositionGroup> {
    private var index = start
    private val version = table.version

    init {
        if (table.writer) throw ConcurrentModificationException()
    }

    override fun hasNext() = index < end

    override fun next(): CompositionGroup {
        validateRead()
        val group = index
        index += table.groups.groupSize(group)
        return object : CompositionGroup, Iterable<CompositionGroup> {
            override val isEmpty: Boolean get() = table.groups.groupSize(group) == 0

            override val key: Any
                get() = if (table.groups.hasObjectKey(group))
                    table.slots[table.groups.objectKeyIndex(group)]!!
                else table.groups.key(group)

            override val sourceInfo: String?
                get() = if (table.groups.hasAux(group))
                    table.slots[table.groups.auxIndex(group)] as? String
                else null

            override val node: Any?
                get() = if (table.groups.isNode(group))
                    table.slots[table.groups.nodeIndex(group)] else
                    null

            override val data: Iterable<Any?> get() {
                val start = table.groups.dataAnchor(group)
                val end = if (group + 1 < table.groupsSize)
                    table.groups.dataAnchor(group + 1) else table.slotsSize
                return object : Iterable<Any?>, Iterator<Any?> {
                    var index = start
                    override fun iterator(): Iterator<Any?> = this
                    override fun hasNext(): Boolean = index < end
                    override fun next(): Any? =
                        (
                            if (index >= 0 && index < table.slots.size)
                                table.slots[index]
                            else null
                            ).also { index++ }
                }
            }

            override val compositionGroups: Iterable<CompositionGroup> get() = this

            override fun iterator(): Iterator<CompositionGroup> {
                validateRead()
                return GroupIterator(
                    table,
                    group + 1,
                    group + table.groups.groupSize(group)
                )
            }
        }
    }

    private fun validateRead() {
        if (table.version != version) {
            throw ConcurrentModificationException()
        }
    }
}

// Parent -1 is reserved to be the root parent index so the anchor must pivot on -2.
private const val parentAnchorPivot = -2

// Group layout
//  0             | 1             | 2             | 3             | 4             |
//  Key           | Group info    | Parent anchor | Size          | Data anchor   |
private const val Key_Offset = 0
private const val GroupInfo_Offset = 1
private const val ParentAnchor_Offset = 2
private const val Size_Offset = 3
private const val DataAnchor_Offset = 4
private const val Group_Fields_Size = 5

// Key is the key parameter passed into startGroup

// Group info is laid out as follows,
// 31 30 29 28_27 26 25 24_23 22 21 20_19 18 17 16__15 14 13 12_11 10 09 08_07 06 05 04_03 02 01 00
// 0  n  ks ds r |                                node count                                       |
// where n is set when the group represents a node
// where ks is whether the group has a data key slot
// where ds is whether the group has a group data slot
// where r is always 0 (future use)

// Parent anchor is a group anchor to the parent, as the group gap is moved this value is updated to
// refer to the parent.

// Slot count is the total number of group slots, including itself, occupied by the group.

// Data anchor is an anchor to the group data. The value is positive if it is before the data gap
// and it is negative if it is after the data gap. As gaps are moved, these values are updated.

// Masks and flags
private const val NodeBit_Mask = 0b0100_0000_0000_0000__0000_0000_0000_0000
private const val ObjectKey_Mask = 0b0010_0000_0000_0000__0000_0000_0000_0000
private const val ObjectKey_Shift = 29
private const val Aux_Mask = 0b0001_0000_0000_0000__0000_0000_0000_0000
private const val Aux_Shift = 28
private const val Slots_Shift = Aux_Shift
private const val NodeCount_Mask = 0b0000_0111_1111_1111__1111_1111_1111_1111

// Special values

// The minimum number of groups to allocate the group table
private const val MinGroupGrowthSize = 32

// The minimum number of data slots to allocate in the data slot table
private const val MinSlotsGrowthSize = 32

// The key to used for nodes
private const val NodeKey = 125

private fun IntArray.groupInfo(address: Int): Int =
    this[address * Group_Fields_Size + GroupInfo_Offset]
private fun IntArray.isNode(address: Int) =
    this[address * Group_Fields_Size + GroupInfo_Offset] and NodeBit_Mask != 0
private fun IntArray.nodeIndex(address: Int) = this[address * Group_Fields_Size + DataAnchor_Offset]
private fun IntArray.hasObjectKey(address: Int) =
    this[address * Group_Fields_Size + GroupInfo_Offset] and ObjectKey_Mask != 0
private fun IntArray.objectKeyIndex(address: Int) = (address * Group_Fields_Size).let { slot ->
    this[slot + DataAnchor_Offset] +
        countOneBits(this[slot + GroupInfo_Offset] shr (ObjectKey_Shift + 1))
}
private fun IntArray.hasAux(address: Int) =
    this[address * Group_Fields_Size + GroupInfo_Offset] and Aux_Mask != 0
private fun IntArray.auxIndex(address: Int) = (address * Group_Fields_Size).let { slot ->
    if (slot >= size) size
    else this[slot + DataAnchor_Offset] +
        countOneBits(this[slot + GroupInfo_Offset] shr (Aux_Shift + 1))
}
private fun IntArray.slotAnchor(address: Int) = (address * Group_Fields_Size).let { slot ->
    this[slot + DataAnchor_Offset] +
        countOneBits(this[slot + GroupInfo_Offset] shr Slots_Shift)
}

// Count the 1 bits of value less than 8
private fun countOneBits(value: Int) = when (value) {
    0 -> 0
    1 -> 1
    2 -> 1
    3 -> 2
    4 -> 1
    5 -> 2
    6 -> 2
    else -> 3
}

// Key access
private fun IntArray.key(address: Int) = this[address * Group_Fields_Size]
private fun IntArray.keys(len: Int = size) =
    slice(Key_Offset until len step Group_Fields_Size)

// Node count access
private fun IntArray.nodeCount(address: Int) =
    this[address * Group_Fields_Size + GroupInfo_Offset] and NodeCount_Mask
private fun IntArray.updateNodeCount(address: Int, value: Int) {
    @Suppress("ConvertTwoComparisonsToRangeCheck")
    require(value >= 0 && value < NodeCount_Mask)
    this[address * Group_Fields_Size + GroupInfo_Offset] =
        (this[address * Group_Fields_Size + GroupInfo_Offset] and NodeCount_Mask.inv()) or value
}
private fun IntArray.nodeCounts(len: Int = size) =
    slice(GroupInfo_Offset until len step Group_Fields_Size)
        .map { it and NodeCount_Mask }

// Parent anchor
private fun IntArray.parentAnchor(address: Int) =
    this[address * Group_Fields_Size + ParentAnchor_Offset]
private fun IntArray.updateParentAnchor(address: Int, value: Int) {
    this[address * Group_Fields_Size + ParentAnchor_Offset] = value
}
private fun IntArray.parentAnchors(len: Int = size) =
    slice(ParentAnchor_Offset until len step Group_Fields_Size)

// Slot count access
private fun IntArray.groupSize(address: Int) = this[address * Group_Fields_Size + Size_Offset]
private fun IntArray.updateGroupSize(address: Int, value: Int) {
    require(value >= 0)
    this[address * Group_Fields_Size + Size_Offset] = value
}

private fun IntArray.slice(indices: Iterable<Int>): List<Int> {
    val list = mutableListOf<Int>()
    for (index in indices) {
        list.add(get(index))
    }
    return list
}

@Suppress("unused")
private fun IntArray.groupSizes(len: Int = size) =
    slice(Size_Offset until len step Group_Fields_Size)

// Data anchor access
private fun IntArray.dataAnchor(address: Int) =
    this[address * Group_Fields_Size + DataAnchor_Offset]

private fun IntArray.updateDataAnchor(address: Int, anchor: Int) {
    this[address * Group_Fields_Size + DataAnchor_Offset] = anchor
}

private fun IntArray.dataAnchors(len: Int = size) =
    slice(DataAnchor_Offset until len step Group_Fields_Size)

// Update data
private fun IntArray.initGroup(
    address: Int,
    key: Int,
    isNode: Boolean,
    hasDataKey: Boolean,
    hasData: Boolean,
    parentAnchor: Int,
    dataAnchor: Int
) {
    val nodeBit = if (isNode) NodeBit_Mask else 0
    val dataKeyBit = if (hasDataKey) ObjectKey_Mask else 0
    val dataBit = if (hasData) Aux_Mask else 0
    val arrayIndex = address * Group_Fields_Size
    this[arrayIndex + Key_Offset] = key
    this[arrayIndex + GroupInfo_Offset] = nodeBit or dataKeyBit or dataBit
    this[arrayIndex + ParentAnchor_Offset] = parentAnchor
    this[arrayIndex + Size_Offset] = 0
    this[arrayIndex + DataAnchor_Offset] = dataAnchor
}

private inline fun ArrayList<Anchor>.getOrAdd(
    index: Int,
    effectiveSize: Int,
    block: () -> Anchor
): Anchor {
    val location = search(index, effectiveSize)
    return if (location < 0) {
        val anchor = block()
        add(-(location + 1), anchor)
        anchor
    } else get(location)
}

/**
 * This is inlined here instead to avoid allocating a lambda for the compare when this is used.
 */
private fun ArrayList<Anchor>.search(location: Int, effectiveSize: Int): Int {
    var low = 0
    var high = size - 1

    while (low <= high) {
        val mid = (low + high).ushr(1) // safe from overflows
        val midVal = get(mid).location.let { if (it < 0) effectiveSize + it else it }
        val cmp = midVal.compareTo(location)

        when {
            cmp < 0 -> low = mid + 1
            cmp > 0 -> high = mid - 1
            else -> return mid // key found
        }
    }
    return -(low + 1) // key not found
}

/**
 * A wrapper on [search] that always returns an index in to [this] even if [index] is not in the
 * array list.
 */
private fun ArrayList<Anchor>.locationOf(index: Int, effectiveSize: Int) =
    search(index, effectiveSize).let { if (it >= 0) it else -(it + 1) }