/*
 * Copyright 2017 Romuald OUATTARA
 *
 *  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.
 */

package com.ouattararomuald.datastructures

/** Simple First-In-First-Out (FIFO) data structures. */
internal class Queue<T> {

  /** Checks whether or not the queue is empty. */
  val isEmpty: Boolean
    get() = size == 0

  /** Returns the number of items currently in the queue. */
  var size: Int = 0
    private set
  /** First item of the queue. */
  private var head: Node<T>? = null
  /** Last item of the queue. */
  private var tail: Node<T>? = null

  /**
   * Returns but does not retrieve the first item of the queue.
   *
   * @return The first item of the queue.
   * @exception UnderflowException If the queue is empty.
   */
  fun peek(): T? {
    if (isEmpty) {
      throw UnderflowException()
    } else {
      return head?.data
    }
  }

  /**
   * Retrieves and returns the first item of the queue.
   *
   * @return The first item of the queue.
   * @exception UnderflowException If the queue is empty.
   */
  fun dequeue(): T? {
    if (isEmpty) {
      throw UnderflowException()
    } else {
      val data = head?.data
      head = head?.next
      if (head == null) {
        tail = null
      }
      size--
      return data
    }
  }

  /**
   * Adds the given item to the end of the queue.
   * @param data Item to add in the queue.
   */
  fun enqueue(data: T) {
    val newNode = Node(data, null)
    if (isEmpty) {
      head = newNode
      tail = head
    } else {
      tail!!.next = newNode
      tail = newNode
    }
    size++
  }

  private data class Node<T>(val data: T, var next: Node<T>?)
}