/*
 * File: deque.h
 * -------------
 * This file exports the <code>Deque</code> class, a collection
 * in which values can be added and removed from the front or back.
 * It combines much of the functionality of a stack and a queue.
 * 
 * @version 2017/11/14
 * - added iterator version checking support
 * @version 2016/09/24
 * - refactored to use collections.h utility functions
 * @version 2016/09/22
 * - added constructor support for std initializer_list usage, such as {1, 2, 3}
 * @version 2016/08/04
 * - fixed operator >> to not throw errors
 * @version 2015/07/05
 * - using global hashing functions rather than global variables
 * @version 2014/10/29
 * - added comparison operators ==, !=, <, etc.
 * @since 2014/10/29
 */

#ifndef _deque_h
#define _deque_h

#include <deque>
#include <initializer_list>
#include "collections.h"
#include "error.h"
#include "hashcode.h"

/*
 * Class: Deque<ValueType>
 * -----------------------
 * This class models a linear structure called a <b><i>deque</i></b>
 * in which values can be added and removed at either end.
 * This discipline allows first-in/first-out (FIFO) and/or
 * last-in/first-out (LIFO) behavior. That is the defining
 * feature of deques.
 */
template <typename ValueType>
class Deque {
public:
    /*
     * Constructor: Deque
     * Usage: Deque<ValueType> deque;
     * ------------------------------
     * Initializes a new empty deque.
     */
    Deque();

    /*
     * Constructor: Deque
     * Usage: Deque<ValueType> queue {1, 2, 3};
     * ----------------------------------------
     * Initializes a new deque that stores the given elements from front-back.
     */
    Deque(std::initializer_list<ValueType> list);

    /*
     * Destructor: ~Deque
     * ------------------
     * Frees any heap storage associated with this deque.
     */
    virtual ~Deque();
    
    /*
     * Method: add
     * Usage: deque.add(value);
     * ------------------------
     * Adds <code>value</code> to the end of the deque.
     * A synonym for the enqueueBack method.
     */
    void add(const ValueType& value);
    void addBack(const ValueType& value);
    void addFront(const ValueType& value);

    /*
     * Method: back
     * Usage: ValueType last = deque.back();
     * -------------------------------------
     * Returns the last value in the deque by reference.
     */
    const ValueType& back() const;

    /*
     * Method: clear
     * Usage: deque.clear();
     * ---------------------
     * Removes all elements from the deque.
     */
    void clear();
    
    /*
     * Method: dequeue
     * Usage: ValueType first = deque.dequeue();
     * -----------------------------------------
     * Removes and returns the first item in the deque.
     * A synonym for the dequeueFront method.
     */
    ValueType dequeue();
    ValueType dequeueBack();
    ValueType dequeueFront();

    /*
     * Method: enqueue
     * Usage: deque.enqueue(value);
     * ----------------------------
     * Adds <code>value</code> to the end of the deque.
     * A synonym for the enqueueBack method.
     */
    void enqueue(const ValueType& value);
    void enqueueBack(const ValueType& value);
    void enqueueFront(const ValueType& value);
    
    /*
     * Method: equals
     * Usage: if (deque.equals(deque2)) ...
     * ------------------------------------
     * Compares two deques for equality.
     * Returns <code>true</code> if this deque contains exactly the same
     * values as the given other deque.
     * Identical in behavior to the == operator.
     */
    bool equals(const Deque<ValueType>& deque2) const;
    
    /*
     * Method: front
     * Usage: ValueType first = deque.front();
     * ---------------------------------------
     * Returns the first value in the deque by reference.
     */
    const ValueType& front() const;

    /*
     * Method: isEmpty
     * Usage: if (deque.isEmpty()) ...
     * -------------------------------
     * Returns <code>true</code> if the deque contains no elements.
     */
    bool isEmpty() const;
    
    /*
     * Method: peek
     * Usage: ValueType first = deque.peek();
     * --------------------------------------
     * Returns the first value in the deque, without removing it.  For
     * compatibility with the STL classes, this method is also exported
     * under the name <code>front</code>, in which case it returns the
     * value by reference.
     * A synonym for the peekFront method.
     */
    const ValueType& peek() const;
    const ValueType& peekBack() const;
    const ValueType& peekFront() const;

    /*
     * Method: remove
     * Usage: ValueType first = deque.remove();
     * ----------------------------------------
     * Removes and returns the first item in the deque.
     * A synonym for the dequeue method.
     */
    ValueType remove();
    ValueType removeBack();
    ValueType removeFront();

    /*
     * Method: size
     * Usage: int n = deque.size();
     * ----------------------------
     * Returns the number of values in the deque.
     */
    int size() const;
    
    /*
     * Returns an STL deque object with the same elements as this Deque.
     */
    std::deque<ValueType> toStlDeque() const;
    
    /*
     * Method: toString
     * Usage: string str = deque.toString();
     * -------------------------------------
     * Converts the deque to a printable string representation.
     */
    std::string toString() const;

    /*
     * Operators: ==, !=, <, >, <=, >=
     * Usage: if (deque1 == deque2) ...
     * Usage: if (deque1 < deque2) ...
     * ...
     * --------------------------------
     * Relational operators to compare two deques.
     * The ==, != operators require that the ValueType has a == operator
     * so that the elements can be tested for equality.
     * The <, >, <=, >= operators require that the ValueType has a < operator
     * so that the elements can be compared pairwise.
     */
    bool operator ==(const Deque& deque2) const;
    bool operator !=(const Deque& deque2) const;
    bool operator <(const Deque& deque2) const;
    bool operator <=(const Deque& deque2) const;
    bool operator >(const Deque& deque2) const;
    bool operator >=(const Deque& deque2) const;

    /* Private section */

    /**********************************************************************/
    /* Note: Everything below this point in the file is logically part    */
    /* of the implementation and should not be of interest to clients.    */
    /**********************************************************************/

    template <typename Collection>
    friend int stanfordcpplib::collections::compare(const Collection& pq1, const Collection& pq2);
    
    template <typename T>
    friend int hashCode(const Deque<T>& s);
    
    template <typename T>
    friend std::ostream& operator <<(std::ostream& os, const Deque<T>& deque);

private:
    /* Instance variables */
    std::deque<ValueType> elements;
    unsigned int m_version;     // structure version for detecting invalid iterators

public:
    /*
     * Iterator support
     * ----------------
     * The classes in the StanfordCPPLib collection implement input
     * iterators so that they work symmetrically with respect to the
     * corresponding STL classes.
     */
    class deque_iterator : public std::deque<ValueType>::iterator {
    public:
        deque_iterator()
                : std::deque<ValueType>::iterator(),
                  dp(nullptr),
                  itr_version(0) {
            // empty
        }

        deque_iterator(const deque_iterator& it)
                : std::deque<ValueType>::iterator(it),
                  dp(it.dp),
                  itr_version(it.itr_version) {
            // empty
        }

        deque_iterator(Deque<ValueType>* dp, const typename std::deque<ValueType>::iterator& it)
                : std::deque<ValueType>::iterator(it),
                  dp(dp),
                  itr_version(dp->version()) {
            // empty
        }

        ValueType& operator *() {
            if (dp) {
                stanfordcpplib::collections::checkVersion(*dp, *this);
            }
            return std::deque<ValueType>::iterator::operator *();   // call super
        }

        ValueType* operator ->() {
            if (dp) {
                stanfordcpplib::collections::checkVersion(*dp, *this);
            }
            return std::deque<ValueType>::iterator::operator ->();   // call super
        }

        unsigned int version() const {
            return itr_version;
        }

    private:
        const Deque* dp;
        unsigned int itr_version;
    };

    class const_deque_iterator : public std::deque<ValueType>::const_iterator {
    public:
        const_deque_iterator()
                : std::deque<ValueType>::const_iterator(),
                  dp(nullptr),
                  itr_version(0) {
            // empty
        }

        const_deque_iterator(const const_deque_iterator& it)
                : std::deque<ValueType>::const_iterator(it),
                  dp(it.dp),
                  itr_version(it.itr_version) {
            // empty
        }

        const_deque_iterator(const Deque<ValueType>* const dp, const typename std::deque<ValueType>::const_iterator& it)
                : std::deque<ValueType>::const_iterator(it),
                  dp(dp),
                  itr_version(dp->version()) {
            // empty
        }

        const ValueType& operator *() {
            if (dp) {
                stanfordcpplib::collections::checkVersion(*dp, *this);
            }
            return std::deque<ValueType>::const_iterator::operator *();   // call super
        }

        const ValueType* operator ->() {
            if (dp) {
                stanfordcpplib::collections::checkVersion(*dp, *this);
            }
            return std::deque<ValueType>::const_iterator::operator ->();   // call super
        }

        unsigned int version() const {
            return itr_version;
        }

    private:
        const Deque* dp;
        unsigned int itr_version;
    };

    /*
     * Returns an iterator positioned at the first element of the deque.
     */
    deque_iterator begin() {
        return deque_iterator(this, elements.begin());
    }

    /*
     * Returns an iterator positioned at the first element of the deque.
     */
    const_deque_iterator begin() const {
        auto itr = elements.begin();
        return const_deque_iterator(this, itr);
    }
    
    /*
     * Returns an iterator positioned at the last element of the deque.
     */
    deque_iterator end() {
        auto itr = elements.end();
        return deque_iterator(this, itr);
    }
    
    /*
     * Returns an iterator positioned at the last element of the deque.
     */
    const_deque_iterator end() const {
        auto itr = elements.end();
        return const_deque_iterator(this, itr);
    }

    /*
     * Returns the internal version of this collection.
     * This is used to check for invalid iterators and issue error messages.
     */
    unsigned int version() const;
};

/*
 * Implementation notes: Deque constructor
 * ---------------------------------------
 * None.
 */
template <typename ValueType>
Deque<ValueType>::Deque()
        : m_version(0) {
    // empty
}

template <typename ValueType>
Deque<ValueType>::Deque(std::initializer_list<ValueType> list)
        : m_version(0) {
    clear();
    for (const ValueType& value : list) {
        add(value);
    }
}

/*
 * Implementation notes: ~Deque destructor
 * ---------------------------------------
 * None.
 */
template <typename ValueType>
Deque<ValueType>::~Deque() {
    // empty
}

template <typename ValueType>
void Deque<ValueType>::add(const ValueType& value) {
    enqueue(value);
}

template <typename ValueType>
void Deque<ValueType>::addBack(const ValueType& value) {
    enqueueBack(value);
}

template <typename ValueType>
void Deque<ValueType>::addFront(const ValueType& value) {
    enqueueFront(value);
}

template <typename ValueType>
const ValueType& Deque<ValueType>::back() const {
    if (isEmpty()) {
        error("Deque::back: Attempting to read back of an empty deque");
    }
    return elements.back();
}

template <typename ValueType>
void Deque<ValueType>::clear() {
    elements.clear();
    m_version++;
}

/*
 * Implementation notes: dequeue, peek
 * -----------------------------------
 * These methods must check for an empty deque and report an error
 * if there is no first element.
 */
template <typename ValueType>
ValueType Deque<ValueType>::dequeue() {
    return dequeueFront();
}

template <typename ValueType>
ValueType Deque<ValueType>::dequeueBack() {
    if (isEmpty()) {
        error("Deque::dequeueBack: Attempting to dequeue from an empty deque");
    }
    ValueType result = elements.back();
    elements.pop_back();
    m_version++;
    return result;
}

template <typename ValueType>
ValueType Deque<ValueType>::dequeueFront() {
    if (isEmpty()) {
        error("Deque::dequeueFront: Attempting to dequeue from an empty deque");
    }
    ValueType result = elements.front();
    elements.pop_front();
    m_version++;
    return result;
}

template <typename ValueType>
void Deque<ValueType>::enqueue(const ValueType& value) {
    enqueueBack(value);
}

template <typename ValueType>
void Deque<ValueType>::enqueueBack(const ValueType& value) {
    elements.push_back(value);
    m_version++;
}

template <typename ValueType>
void Deque<ValueType>::enqueueFront(const ValueType& value) {
    elements.push_front(value);
    m_version++;
}

template <typename ValueType>
bool Deque<ValueType>::equals(const Deque<ValueType>& deque2) const {
    return elements == deque2.elements;
}

template <typename ValueType>
const ValueType& Deque<ValueType>::front() const {
    if (isEmpty()) {
        error("Deque::front: Attempting to read front of an empty deque");
    }
    return elements.front();
}

template <typename ValueType>
bool Deque<ValueType>::isEmpty() const {
    return elements.empty();
}

template <typename ValueType>
const ValueType& Deque<ValueType>::peek() const {
    return peekFront();
}

template <typename ValueType>
const ValueType& Deque<ValueType>::peekBack() const {
    if (isEmpty()) {
        error("Deque::peekBack: Attempting to peek at an empty deque");
    }
    return back();
}

template <typename ValueType>
const ValueType& Deque<ValueType>::peekFront() const {
    if (isEmpty()) {
        error("Deque::peekFront: Attempting to peek at an empty deque");
    }
    return front();
}

template <typename ValueType>
ValueType Deque<ValueType>::remove() {
    return dequeue();
}

template <typename ValueType>
ValueType Deque<ValueType>::removeBack() {
    if (isEmpty()) {
        error("Deque::removeBack: Attempting to remove from an empty deque");
    }
    return dequeueBack();
}

template <typename ValueType>
ValueType Deque<ValueType>::removeFront() {
    if (isEmpty()) {
        error("Deque::removeFront: Attempting to remove from an empty deque");
    }
    return dequeueFront();
}

template <typename ValueType>
int Deque<ValueType>::size() const {
    return elements.size();
}

template <typename ValueType>
std::deque<ValueType> Deque<ValueType>::toStlDeque() const {
    return elements;
}

template <typename ValueType>
std::string Deque<ValueType>::toString() const {
    std::ostringstream os;
    os << *this;
    return os.str();
}

template <typename ValueType>
unsigned int Deque<ValueType>::version() const {
    return m_version;
}

template <typename ValueType>
bool Deque<ValueType>::operator ==(const Deque& deque2) const {
    return equals(deque2);
}

template <typename ValueType>
bool Deque<ValueType>::operator !=(const Deque& deque2) const {
    return !equals(deque2);
}

template <typename ValueType>
bool Deque<ValueType>::operator <(const Deque& deque2) const {
    return stanfordcpplib::collections::compare(*this, deque2) < 0;
}

template <typename ValueType>
bool Deque<ValueType>::operator <=(const Deque& deque2) const {
    return stanfordcpplib::collections::compare(*this, deque2) <= 0;
}

template <typename ValueType>
bool Deque<ValueType>::operator >(const Deque& deque2) const {
    return stanfordcpplib::collections::compare(*this, deque2) > 0;
}

template <typename ValueType>
bool Deque<ValueType>::operator >=(const Deque& deque2) const {
    return stanfordcpplib::collections::compare(*this, deque2) >= 0;
}

template <typename ValueType>
std::ostream& operator <<(std::ostream& os, const Deque<ValueType>& deque) {
    return stanfordcpplib::collections::writeCollection(os, deque);
}

template <typename ValueType>
std::istream& operator >>(std::istream& is, Deque<ValueType>& deque) {
    ValueType element;
    return stanfordcpplib::collections::readCollection(is, deque, element, /* descriptor */ "Deque::operator >>");
}

/*
 * Template hash function for deques.
 * Requires the element type in the deque to have a hashCode function.
 */
template <typename T>
int hashCode(const Deque<T>& deq) {
    return stanfordcpplib::collections::hashCodeCollection(deq);
}

#include "private/init.h"   // ensure that Stanford C++ lib is initialized

#endif // _deque_h
