﻿using System;

namespace DataStructures.Array
{
    class Queue<T>
    {
        /// <summary>
        /// Storage of the queue, the backing array
        /// </summary>
        private T[] _storage;

        /// <summary>
        /// Size of the queues array
        /// </summary>
        private int _size = 4;

        /// <summary>
        /// Grow ratio of the backing array
        /// </summary>
        private const int GROW = 2;

        /// <summary>
        /// Number of elements in the queue
        /// </summary>
        public int Count { get; private set; }

        /// <summary>
        /// Tail that points to the dequeable item
        /// </summary>
        private int _tail;
        
        /// <summary>
        /// Initialises a new Queue
        /// </summary>
        public Queue()
        {
            _storage = new T[_size];
        }

        /// <summary>
        /// Pushes the item on the end of the queue
        /// Resizes the internal array if needed
        /// Amortized O(1)
        /// </summary>
        /// <param name="item">Item to enqueue on the queue</param>
        public void Enqueue(T item)
        {
            if (Count == _size)
            {
                _size *= GROW;
                T[] prevArray = _storage;
                _storage = new T[_size];
                System.Array.Copy(prevArray, _tail, _storage, 0, Count - _tail);
                System.Array.Copy(prevArray, 0, _storage, Count - _tail, _tail);
                _tail = 0;
            }
            int begin = (_tail + Count) % _size;
            _storage[begin] = item;
            Count++;
        }

        /// <summary>
        /// Dequeue the item from the end of the queue
        /// O(1)
        /// </summary>
        /// <returns>Item that got dequeued from the queue</returns>
        public T Dequeue()
        {
            if (Count == 0)
                throw new InvalidOperationException();
            T tmp = _storage[_tail];
            Count--;
            _tail = (_tail + 1) % _size;
            return tmp;
        }

        /// <summary>
        /// Peek at the item at the end of the array
        /// O(1)
        /// </summary>
        /// <returns>Item that is next to pop from the stack</returns>
        public T Peek()
        {
            if (Count == 0)
                throw new InvalidOperationException();
            return _storage[_tail];
        }

        /// <summary>
        /// Index on the internal array
        /// Possible: IndexOutOfRangeException
        /// </summary>
        /// <param name="index">Index in the array to change</param>
        /// <returns>Item in the array at the index</returns>
        public T this[int index]
        {
            get
            {
                if (index >= 0 && index < Count)
                {
                    index = (_tail + index) % _size;
                    return _storage[index];
                }
                throw new IndexOutOfRangeException("Queue count: " + Count + " index: " + index);
            }
            set
            {
                if (index >= 0 && index < Count)
                {
                    index = (_tail + index) % _size;
                    _storage[index] = value;
                }
                throw new IndexOutOfRangeException("Queue count: " + Count + " index: " + index);
            }
        }
    }
}