deque.h

Go to the documentation of this file.

// deque.h      (C) 2006 [email protected]

#include <exception> // std::length_error && std::bad_alloc
#include <iostream>  // cin && cout

// using namespace std;
namespace std {} // Está acá para que Doxygen lo documente

template <class T> class test_deque;

template <class T>
class deque {
public:
    typedef typename T    value_type; 
    typedef typename T *  pointer;    
    typedef typename T &  reference;  

    typedef typename const value_type const_value_type; 
    typedef typename const T *        const_pointer; 
    typedef typename const T &        const_reference; 

    typedef typename unsigned size_type;  

    deque( size_type N );
    ~deque() { if (m_vec != 0) { delete [] m_vec; } } 

    bool empty() const { return (size() == 0); }

    size_type size()     const { return m_size; }     
    size_type capacity() const { return m_capacity; }

    value_type& front() { return at_check(m_front); }

    const value_type& front() const { return const_cast<deque*>(this)->front(); }
    // const_cast<deque*>(this) hace que "this" ya NO sea un puntero "const".

    value_type& back() { return at_check(m_front+m_size-1); }

    const value_type& back() const { return const_cast<deque*>(this)->back(); }

    value_type& operator[](size_type i) {
        size_type  i_real = m_front + i;
        i_real = ( i_real < m_capacity ? i_real : i_real - m_capacity );
        return m_vec[ i_real ]; // uso "+" y "-" que es más eficiente que "%"
    }
    value_type& operator[](size_type i) const { return const_cast<deque*>(this)->operator[](i); }

    value_type& at(size_type i)       { return at_check(m_front+i); }
    value_type& at(size_type i) const { return const_cast<deque*>(this)->at(i); }

    void push_front( const value_type& val );
    void push_back(  const value_type& val );
    void pop_front();
    void pop_back();

    template <class T> friend std::istream& operator>>( std::istream& CIN,        deque<T>& Q);
    template <class T> friend std::ostream& operator<<( std::ostream& COUT, const deque<T>& Q);
private:
    bool ok() const;
    inline friend bool check_ok( const deque<T>& Q) { return Q.ok(); }
    value_type& at_check(size_type i);
    explicit deque(const deque&); 

    template <class T> friend class test_deque; 
private:
    unsigned     m_front;    
    unsigned     m_size;     
    unsigned     m_capacity; 
    value_type * m_vec;      
};

template <class T>
deque<T>::deque( size_type N ) : m_front(0), m_size(0), m_capacity(0), m_vec(0) {
    if (N == 0) {
        throw std::length_error("deque<T>::deque(0)");
    }
    else {
        try {
            m_capacity = N;
            m_vec = new value_type [ m_capacity ];
        }
        catch (std::bad_alloc) {
            throw; // new[] tira std::bad_alloc si ya no hay memoria
        }
    }
}

template <class T>
T& deque<T>::at_check(size_type i) {
    // uso "+" y "-" que es más eficiente que "%"
    size_type i_real = ( i < m_capacity ? i : i - m_capacity );
    if ( (m_front <= i) && (i < m_front + m_size) ) {
        return m_vec[i_real];
    }
    else {
        throw std::out_of_range("deque<T>::at()");
    }
}

template <class T>
void deque<T>::push_back(const value_type& val) {
    if (m_size < m_capacity) {
        size_type i_real = m_front + m_size;
        i_real = (i_real < m_capacity ? i_real : i_real - m_capacity);
        m_vec[i_real] = val;
        m_size++;
    }
    else {
        throw std::out_of_range("deque<T>::push_back()");
    }
}

template <class T>
void deque<T>::push_front(const value_type& val) {
    if (m_size < m_capacity) {
        m_front = ( m_front>0 ? m_front-1 : m_capacity-1 );
        m_vec[m_front] = val;
        m_size++;
    }
    else {
        throw std::out_of_range("deque<T>::push_front()");
    }
}
template <class T>
inline void deque<T>::pop_front() {
    if (m_size > 0) {
    //  unsigned temp = m_front;
        m_front++;
        m_size--;
        if (m_front >= m_capacity) {
            m_front = 0;
        }
    //  return m_vec[temp];
    }
    else {
        throw std::out_of_range("deque<T>::pop_front()");
    }
}

template <class T>
inline void deque<T>::pop_back() {
    if (m_size > 0) {
        m_size--;
    }
    else {
        throw std::out_of_range("deque<T>::pop_front()");
    }
}

#if 0

    template <class T>
    inline bool deque<T>::full() const {
        return (m_size == m_ capacity);
    }
#endif

template <class T>
bool check_ok( const deque<T>& Q);

template <class T>
bool deque<T>::ok() const {
    if (this == 0) {
        return false;
    }

    if ( ! (m_capacity > 0) ) {
        return false;
    }
    if ( ! (m_front < m_capacity) ) {
        return false;
    }
    if ( ! (m_size <= m_capacity) ) {
        return false;
    }
    if ( ! (size() <= m_capacity) ) {
        return false;
    }
    if ( ! (m_vec != 0) ) {
        return false;
    }

    // Declaración previa del verificador del objeto contenido
    // - Con este se le quita trabajo al programador cliente de la clase
    //   pues deberá implementar \c check_ok( const T& ) sólo en el caso
    //   de que utilice \c check_ok() para \c deque<T> .
    // - En otras palabras: el programador cliente está obligado a implementar
    //   este método sólo si invoca \c check_ok( const deque<T>& ).
    // - Por eso es preferible que \c check_ok() sea una función y no un método.
    bool check_ok( const deque<T>::value_type & );

    for (unsigned i=0; i<m_capacity; ++i) {
        if ( ! check_ok( m_vec[i] ) ) {
            return false;
        }
    }
    return true;
/*  NOTA: VC++ v7 .net
    La documentación del compilador pide que check_ok( const deque<T>& ) sea declarado
    dentro de la plantilla deque<T> como una función "friend" de la siguiente forma:
        template <class T> friend bool check_ok( const deque<T>& Q);

    Desafortunadamente, el compilador produce un error interno si check_ok() es una
    función. Por eso, en esta implementación se usa el método deque<T>::ok(), el que
    sí es aceptado por el compilador. Para evitar una pequeña degradación en la
    eficiencia, la función check_ok() queda definida dentro de la clase como una
    función "inline", que el compilador compila sin dar problemas.

    A primera vista parece inocuo exigir que quien use deque<T> esté obligado a 
    implementar el método T::ok(), pero en la práctica eso es contraproducente por
    2 razones:
    - Algunos "tipos" en C++ no son clases, como "int" o "float", por lo que no
      es posible definirles su método ok().
    - Para un programador cliente es incómodo agregar un método que no piensa usar
      Por eso, si el programador cliente invoca check_ok( const deque<T>& ) deberá
      implementar check_ok( const T& ), pero de otra forma ni siquiera tiene que
      enterarse de que check_ok() existe.
*/
}

// EOF: deque.h

---

Hosted by www.Geocities.ws