interface Queue<T> {
    fun isEmpty(): Boolean
    fun enqueue(item: T)
    fun dequeue(): T
}

class CircularQueue<T> : Queue<T> {
    
    // We'll use a mutable list as the underlying data structure,
    // and let it grow when we need to
    private var items: MutableList<T> = mutableListOf()
    private var frontIdx = -1
    private var rearIdx = -1

    override fun isEmpty(): Boolean {
        return frontIdx == -1
    }

    override fun enqueue(item: T) {

        // We'll handle the special case of a currently empty list
        // separately, because the modular arithmetic elsewhere
        // will have issues if size is 0
        if (items.size == 0) {
            items.add(item)
            frontIdx = 0
            rearIdx = 0
        }

        // Otherwise, if the queue is empty but the list has
        // previously had values in it, we'll just restart at 0
        else if (frontIdx == -1) {
            items[0] = item
            frontIdx = 0
            rearIdx = 0
        }
        
        // Otherwise, if the queue is completely full, we need to make room
        // (this occurs when the frontIdx is one space after the rearIdx)
        else if (frontIdx == (rearIdx + 1) % items.size) {
            // Let's start by reorganizing the list to put the front at
            // position 0 (thus allowing us to add at the end)
            if (frontIdx != 0) {
                val newItems = mutableListOf<T>()
                newItems.addAll(items.subList(frontIdx, items.size)) // add from front to end
                newItems.addAll(items.subList(0, rearIdx+1))         // add from start to rear
                items = newItems
                frontIdx = 0
            }

            // Now we can add the new item at the end of the queue
            // (we'll also be able to add future ones easily until
            // a dequeue operation)
            items.add(item)
            rearIdx = items.size - 1 // update rear index given new end
        }

        // Otherwise, there was still room, so this is easy: move the rear
        // position one spot forward and put the item there
        else {
            rearIdx = (rearIdx + 1) % items.size
            items[rearIdx] = item
        }
    }

    override fun dequeue(): T {
        // TODO: write this!
    }

    override fun toString(): String {
        // TODO: how would you write this to print with the right starting point?
        return items.toString()
    }

    fun display() {
        println()

        // If the queue is empty, just print that message
        if (isEmpty()) {
            println("Empty queue")
            return
        }

        // Otherwise, report the front and rear indices and the items themselves
        println("Front index: $frontIdx")
        println("Items: ${toString()}")
        println("Rear index: $rearIdx")        
    }
}

fun main() {
    val q = CircularQueue<String>()
    q.enqueue("A")
    q.enqueue("B")
    q.enqueue("C")
    q.dequeue()
    q.enqueue("D")

    q.display()

    q.dequeue()
    q.dequeue()
    q.dequeue()

    q.display()

    q.enqueue("E")
    q.display()
}