#include<iostream>

// Ideas for changing program:
// set a minimum size that the array can be, and will be
// ideas generated during presentation...
// TODO (bryan#1#): Add peek at next node function
// TODO (bryan#1#): Add Function to accept an array size to change the array to. It should verify the new array is big enough
// TODO (bryan#1#): add comments about this functions that are not part of a 'typical queue'
// TODO (bryan#1#): Add try Catch blocks etc... for the errors, instead of just using cout
// TODO (bryan#1#): ?local varible for size increase/decrease amount
// TODO (bryan#1#): Add features from... http://www.cs.duke.edu/csed/ap/subset/doc/ap/Queue.html
// http://www.oracle.com/technetwork/java/javase/documentation/index-137868.html
// #  Tag Comments: @author @version @param @return @deprecated @since @throws @exception @see @serial @serialField @serialData {@link}

// Could be an older version?, dispite the fact that this has '2' in the name, and the other one doesn't (and the version timestamps are the same.
// This one returns a 'T' object on dequeue, while the other one doesn't...

/**
 * Implements a queue using an array
 * @author Bryan Ritter
 * @version 2010-08-27_09:49:54.253980404_                     AM_Fri_Week+34_(-04:00:00EDT)+...
 * updated  2011-09-28_13:57:26.404358783_                     PM_Wed_Week+39_(-04:00:00EDT)
 * to correct some things like the dequeue returning '\0', adding
 * " : arraySize(2), queueSize(0), queueStartPos(0), queueEndPos(0), myQueueAsArray(new T[arraySize])" to "template <typename T> QueueAsArray<T>::QueueAsArray()"
 * etc...
 */

// If you prefer to use namespaces uncomment this next line, and optionally remove any/all 'std::'
//using namespace std;
// --Setup section-------------------------------------------------------------
/** class header for 'QueueAsArray' with an array of type 'T' */
// This assumes T is a type that has 'cout <<' posibilities
template <typename T>
class QueueAsArray
{
    public:
        void enqueue(T);
        //void dequeue(); // TODO (bryan#1#): Should be set up to return a type 'T'
        T dequeue();
        T peekFont();
        QueueAsArray();
        bool isEmpty();
        void displayQueue();
        void displayArray();
        void displayQA(); // 'Q' for Queue, 'A' for Array
    private:
        int arraySize;
        int queueSize;
        int queueStartPos;
        int queueEndPos;
        T* myQueueAsArray; // 'T' is the custom type determined when the object is created
        void increaseArraySize();
        void decreaseArraySize();
};

/** constructor for creating a QueueAsArray */
template <typename T> QueueAsArray<T>::QueueAsArray() : arraySize(2), queueSize(0), queueStartPos(0), queueEndPos(0), myQueueAsArray(new T[arraySize])
{
    arraySize = 2; // default 'arraySize' for new 'QueueAsArray' objects
    queueSize = 0; // there aren't any items in the queue yet for new objects
    queueStartPos = 0; // starting array position for newly added queued items
    queueEndPos = 0; // starting array position for newly removed queued items
    myQueueAsArray = new T[arraySize]; // array holding the values of the queue
    // set up default values for the array
    for(int x=0; x<arraySize; ++x)
    {
        myQueueAsArray[x] = '\0'; // '\0' means NULL
    }
}
template <typename T> bool QueueAsArray<T>::isEmpty()
{
    if(queueSize == 0){
        return true;
    }
    else
    {
        return false;
    }
}

// --Array Size Adjustment section---------------------------------------------
/*
   One way to think about resizing of the array,
   is think of the array as a piece of tape in a loop,
   and the queue as writing on the piece of tape.
   When the tape loop needs to be resized
   it'll be cut at the beginning of queue
   to keep the queue together in order on the resized tape
   (instead of cutting the tape twice, and
    sticking one piece at beginning, and one piece at the other end)
*/

/** this increases the size of the array holding the values of the queue */
template <typename T> void QueueAsArray<T>::increaseArraySize()
{
    T* temp = new T[arraySize*2]; // should match the new 'arraySize' at the end of this function, etc
    for(int x = 0; x < arraySize; ++x)
    {
        temp[x] = myQueueAsArray[(queueStartPos+x)%arraySize]; // when resizing the array, open up old wrap around
    }
    for(int x = arraySize; x < arraySize*2; ++x) // end should match new arraySize at end of function
    {
        temp[x] = '\0'; // sets values to NULL
    }
    queueStartPos = 0; // since the beginning of the queue is 0 now
    queueEndPos = queueSize; //
    arraySize *= 2; // should be the same as the temp array size created at the beginning of this function
    delete myQueueAsArray;
    myQueueAsArray = temp;
}

/** this decreases the size of the array holding the values of the queue */
template <typename T> void QueueAsArray<T>::decreaseArraySize()
{
    T* temp = new T[arraySize/2]; // should match the new 'arraySize' at the end of this function, etc
    for(int x = 0; x < arraySize/2; ++x)
    {
        temp[x] = myQueueAsArray[(queueStartPos+x)%arraySize];// when resizing the array, open up old wrap around
    }
    queueStartPos = 0;
    queueEndPos = queueSize;
    arraySize /= 2; // should be the same as the temp array created at the beginning of this function
    delete myQueueAsArray;
    myQueueAsArray = temp;
}
// --Add or Remove Items-section-----------------------------------------------
/** this adds items into the end of the queue */
template <typename T> void QueueAsArray<T>::enqueue(T x)
{
    if(queueSize >= arraySize)
    {
        increaseArraySize();
    }
    // post increase arraysize if it was needed
    // should have at least one space available at this point
    myQueueAsArray[queueEndPos] = x;
    queueSize++;
    queueEndPos = (queueEndPos+1)%arraySize;
    std::cout << "item " << x << " added" << std::endl;
}

/** this takes items off of the beginning of the equeue */
template <typename T> T QueueAsArray<T>::dequeue() // should be set up to return a type 'T'
{
    if(queueSize <= 0)
    {
        std::cout << "attempt to remove value, when no values exists" << std::endl;
        //return NULL; // Will this work? // gives warning, but below doesn't. warning: converting to non-pointer type 'char' from NULL
        return '\0'; // TODO (bryan#1#): Shouldn't this give an error or warning? incase 'T' isn't a char?
    }
    else
    {
        std::cout << "item " << myQueueAsArray[queueStartPos] << " removed" << std::endl;
        T arrayItem = myQueueAsArray[queueStartPos];
        myQueueAsArray[queueStartPos] = '\0';
        queueSize--;
        queueStartPos = (queueStartPos+1)%arraySize;
        if(queueSize < arraySize/4 && arraySize >= 4) // reduces the array size if queue is less than 1/4 of the array
        {
            decreaseArraySize();
        }
        return arrayItem;
    }
}

/** this takes returns the item at the beginning of the equeue without dequeueing it */
template <typename T> T QueueAsArray<T>::peekFont()
{
        std::cout << "item at the begining of queue is " << myQueueAsArray[queueStartPos];
        return myQueueAsArray[queueStartPos];
}

/** this displays the queue */
template <typename T> void QueueAsArray<T>::displayQueue()
{
    for(int x=0; x < queueSize; ++x)
    {
        std::cout << myQueueAsArray[(queueStartPos+x)%arraySize] << " ";
    }
        std::cout << std::endl;
}

/** this shows the array that holds the queue */
template <typename T> void QueueAsArray<T>::displayArray()
{
    for(int x=0; x < arraySize; ++x)
    {
        if(myQueueAsArray[x]=='\0')
        {
            std::cout << "- ";
        }
        else
        {
            std::cout << myQueueAsArray[x] << " ";
        }
    }
        std::cout << std::endl;
}

/** this shows both the queue and the array that holds it */
template <typename T> void QueueAsArray<T>::displayQA()
{
    displayQueue();
    displayArray();
    std::cout << std::endl;
}
// --Main-section--------------------------------------------------------------
/** tests and shows output */
int main()
{
    // create a pointer to a char QueueAsArray object
    // could replace the two 'char' with two 'int' to see ascii code
    QueueAsArray<char> *mylist = new QueueAsArray<char>;//::QueueAsArray();

    // the following sections test out the new array with known values, and results.

    // tests adding an item to an empty list
    mylist->enqueue('A');
    std::cout << "Should say:" << std::endl;
    std::cout << "A " << std::endl;
    std::cout << "A - " << std::endl;
    std::cout << "says:"<< std::endl;
    mylist->displayQA();

    // tests adding an additional item
    mylist->enqueue('B');
    std::cout << "should say:" << std::endl;
    std::cout << "A B " << std::endl;
    std::cout << "A B " << std::endl;
    std::cout << "says:" << std::endl;
    mylist->displayQA();
    std::cout << "Taking a peek at the front " << mylist->peekFont() << std::endl;

    // tests increasing the array size
    mylist->enqueue('C');
    std::cout << "should say:" << std::endl;
    std::cout << "A B C " << std::endl;
    std::cout << "A B C - " << std::endl;
    std::cout << "says:" << std::endl;
    mylist->displayQA();

    // tests a full array
    mylist->enqueue('D');
    std::cout << "should say:" << std::endl;
    std::cout << "A B C D " << std::endl;
    std::cout << "A B C D " << std::endl;
    std::cout << "says:" << std::endl;
    mylist->displayQA();

    // tests increasing the array size again
    mylist->enqueue('E');
    std::cout << "should say:" << std::endl;
    std::cout << "A B C D E " << std::endl;
    std::cout << "A B C D E - - - " << std::endl;
    std::cout << "says:" << std::endl;
    mylist->displayQA();

    // tests removing an item
    std::cout << "this dequeued " << mylist->dequeue() << std::endl;
    std::cout << "should say:" << std::endl;
    std::cout << "B C D E " << std::endl;
    std::cout << "- B C D E - - - " << std::endl;
    std::cout << "says:" << std::endl;
    mylist->displayQA();

    // tests removing more items
    mylist->dequeue(); // 3 items left
    mylist->dequeue(); // 2 items left 8/4=2
    std::cout << "should say:" << std::endl;
    std::cout << "D E " << std::endl;
    std::cout << "- - - D E - - - " << std::endl;
    std::cout << "says:" << std::endl;
    mylist->displayQA();

    // tests removing yet one more item which will invoke the decreaseArraySize function
    mylist->dequeue(); // 1 items left
    std::cout << "should say:" << std::endl;
    std::cout << "E " << std::endl;
    std::cout << "E - - - " << std::endl;
    std::cout << "says:" << std::endl;
    mylist->displayQA();

    // tests adding an item after decreasing the array size
    mylist->enqueue('F');
    std::cout << "should say:" << std::endl;
    std::cout << "E F " << std::endl;
    std::cout << "E F - - " << std::endl;
    std::cout << "says:" << std::endl;
    mylist->displayQA();

    // tests creating a full array
    mylist->enqueue('G');
    mylist->enqueue('H');
    std::cout << "should say:" << std::endl;
    std::cout << "E F G H " << std::endl;
    std::cout << "E F G H " << std::endl;
    std::cout << "says:" << std::endl;
    mylist->displayQA();

    // tests increasing the array size again
    mylist->enqueue('I');
    std::cout << "should say:" << std::endl;
    std::cout << "E F G H I" << std::endl;
    std::cout << "E F G H I - - - " << std::endl;
    std::cout << "says:" << std::endl;
    mylist->displayQA();

    // tests adding an item after in increase in size
    mylist->enqueue('J');
    std::cout << "should say:" << std::endl;
    std::cout << "E F G H I J" << std::endl;
    std::cout << "E F G H I J - - " << std::endl;
    std::cout << "says:" << std::endl;
    mylist->displayQA();

    // test creating yet another full array
    mylist->enqueue('K');
    mylist->enqueue('L');
    std::cout << "should say:" << std::endl;
    std::cout << "E F G H I J K L " << std::endl;
    std::cout << "E F G H I J K L " << std::endl;
    std::cout << "says:" << std::endl;
    mylist->displayQA();

    // tests removing an item from a full array
    mylist->dequeue();
    std::cout << "should say:" << std::endl;
    std::cout << "F G H I J K L " << std::endl;
    std::cout << "- F G H I J K L " << std::endl;
    std::cout << "says:" << std::endl;
    mylist->displayQA();

    // tests adding to the front of the array
    mylist->enqueue('M');
    std::cout << "should say:" << std::endl;
    std::cout << "F G H I J K L M " << std::endl;
    std::cout << "M F G H I J K L " << std::endl;
    std::cout << "says:" << std::endl;
    mylist->displayQA();

    // one more test at increasing the array size
    mylist->enqueue('N');
    std::cout << "should say:" << std::endl;
    std::cout << "F G H I J K L M N" << std::endl;
    std::cout << "F G H I J K L M N - - - - - - - " << std::endl;
    std::cout << "says:" << std::endl;
    mylist->displayQA();

    // tests removing an item again
    mylist->dequeue();
    std::cout << "should say:" << std::endl;
    std::cout << "G H I J K L M N" << std::endl;
    std::cout << "- G H I J K L M N - - - - - - - " << std::endl;
    std::cout << "says:" << std::endl;
    mylist->displayQA();

    //testing removing all items
    for(int x=0; x<8; ++x)
    {
        //std::cout << x << " "; // show how many removed prior to this one...
        mylist->dequeue();
    }
    std::cout << "should say:" << std::endl;
    std::cout << "" << std::endl;
    std::cout << "- - " << std::endl;
    std::cout << "says:" << std::endl;
    mylist->displayQA();

    // testing trying to remove an item when there aren't any
    mylist->dequeue();
    mylist->dequeue();
    std::cout << "should say:" << std::endl;
    std::cout << "" << std::endl;
    std::cout << "- - " << std::endl;
    std::cout << "says:" << std::endl;
    mylist->displayQA();
    std::cout << "is the array empty? ";
    if (mylist->isEmpty() == false)
    {
        std::cout << "nope!" << std::endl;
    }
    else
    {
        std::cout << "yep!" << std::endl;
    }
    std::cout << std::endl << "main finished executing!";
}