/*
 * FiniteArrayQueue.kt
 * 
 * Based on our FiniteArrayStack.kt, but modified to be a queue.
 * Also based on CircularQueue.kt, but using an array.
 * 
 * Does not grow in size.
 */

 /*
 * Queue interface: implements a queue of integers
 */
interface Queue {
    fun isEmpty(): Boolean
    fun enqueue(item: Int)
    fun dequeue(): Int
}

class FiniteArrayQueue(val maxSize: Int) : Queue {
    // Initialize the data storage for our queue (it's finite)
    private val myArray: Array<Int?> = arrayOfNulls<Int>(maxSize)

    // To keep it circular, we'll keep track of head and tail indices
    private var headIdx = -1
    private var tailIdx = -1

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

    fun isFull(): Boolean {
        return headIdx == (tailIdx + 1) % maxSize
    }

    // Add an item to the back of the queue
    override fun enqueue(item: Int) {
        // If the queue is full, fail
        if (isFull()) {
            throw RuntimeException("The queue is full!")
        }

        // If it's empty, just add it at the beginning
        if (headIdx == -1) {
            myArray[0] = item
            headIdx = 0
            tailIdx = 0
        }

        // Otherwise, move the tail position one spot forward
        // and put the item there
        else {
            tailIdx = (tailIdx + 1) % maxSize
            myArray[tailIdx] = item
        }
    }

    override fun dequeue(): Int {
        // We can't remove anything if the queue is currently empty
        if (isEmpty()) {
            throw RuntimeException("Queue is empty!")
        }

        // Grab our item
        val item: Int = myArray[headIdx]!!

        // If there was only one element, we'll need to reset to mark
        // the queue empty after removing it
        if (headIdx == tailIdx) { // only true when one item in queue
            headIdx = -1
            tailIdx = -1
        }

        // Otherwise, we can just move the head position one spot forward
        else {
            headIdx = (headIdx + 1) % maxSize
        }

        return item
    }

    // Return a string representing the queue
    override fun toString(): String {
        // TODO: how would you write this to print with the right starting point?
        return ""
    }
}

// Test out the FiniteArrayStack implementation
fun main() {
    val q = FiniteArrayQueue(4)
    q.enqueue(2025)
    q.enqueue(4)
    q.enqueue(16)
    
    println("Elements present in queue: ")
    println(q)
    
    println("" + q.dequeue() + " dequeued")

    println("Elements present in queue: ")
    println(q)
}