deque.h

Ir a la documentación de este archivo.

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

/** \file  deque.h
    \brief Vector extendible a ambos lados, almacenado en un vector circular.

    \author Adolfo Di Mare <[email protected]>
    \date   2006
*/

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

// using namespace std;
/// Definido por la biblioteca C++ estándar.
namespace std {} // Está acá para que Doxygen lo documente

template <class T> class test_deque;

/** Vector extendible a ambos lados, almacenado en un vector circular.
    - Es posible agregar valores al principio o al final del vector extendible.
    - El tamaño del vector extendible no puede cambiar, pues se establece en el 
      constructor.

    - Why English names??? ==> http://www.di-mare.com/adolfo/binder/c01.htm#sc04
*/
template <class T>
class deque {
public:
    typedef typename T    value_type; ///< Nombre estándar del objeto contenido
    typedef typename T *  pointer;    ///< Nombre estándar del puntero al objeto contenido
    typedef typename T &  reference;  ///< Nombre estándar de la referencia al objeto contenido

    typedef typename const value_type const_value_type; ///< Nombre estándar del objeto contenido \c const
    typedef typename const T *        const_pointer; ///< Nombre estándar del puntero al objeto contenido \c const
    typedef typename const T &        const_reference; ///< Nombre estándar de la referencia al objeto contenido \c const

    typedef typename unsigned size_type;  ///< Nombre estándar del tipo retornado por \c size()

    /// Constructor: Vector extendible con capacidad para almacenar \c "N" valores
    deque( size_type N );
    ~deque() { if (m_vec != 0) { delete [] m_vec; } } ///< Destructor

    /// Retorna \c "true" si el vector extendible está vacía
    bool empty() const { return (size() == 0); }

    /// Cantidad de valores almacenados en el vector extendible.
    size_type size()     const { return m_size; }     
    /// Cantidad máxima de valores que se pueden almacenar en el vector extendible.
    size_type capacity() const { return m_capacity; }

    /// Retorna una referencia al primer valor del vector extendible.
    /// - El primero valor es el que está "al frente" en el vector extendible.
    /// \pre \c !empty()
    /// \see test_deque<T>::test_front()
    value_type& front() { return at_check(m_front); }

    /// Retorna una referencia constante al primer valor del vector extendible.
    /// - El primero valor es el que está "al frente" en el vector extendible.
    /// \pre \c !empty()
    /// \see test_deque<T>::test_front_const()
    const value_type& front() const { return const_cast<deque*>(this)->front(); }
    // const_cast<deque*>(this) hace que "this" ya NO sea un puntero "const".

    /// Retorna una referencia al último valor del vector extendible.
    /// - El úlimo valor es el que está "al final" en el vector extendible.
    /// \pre \c !empty()
    /// \see test_deque<T>::test_back()
    value_type& back() { return at_check(m_front+m_size-1); }

    /// Retorna una referencia constante al último valor del vector extendible.
    /// - El úlimo valor es el que está "al final" en el vector extendible.
    /// \pre \c !empty()
    /// \see test_deque<T>::test_back_const()
    const value_type& back() const { return const_cast<deque*>(this)->back(); }

    /// Acceso al \c "i"-ésimo valor almacenado en el contenedor.
    /// - No levanta ninguna excepción si \c "i" está fuera del rango válido.
    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 "%"
    }
    /// Acceso al \c "i"-ésimo valor almacenado en el contenedor ( \c const ).
    /// - No levanta ninguna excepción si \c "i" está fuera del rango válido.
    value_type& operator[](size_type i) const { return const_cast<deque*>(this)->operator[](i); }

    /// Acceso al \c "i"-ésimo valor almacenado en el contenedor.
    /// - Levanta la excepción \c std::out_of_range si \c "i" está fuera del rango válido.
    value_type& at(size_type i)       { return at_check(m_front+i); }
    /// Acceso al \c "i"-ésimo valor almacenado en el contenedor ( \c const ).
    /// - Levanta la excepción \c std::out_of_range si \c "i" está fuera del rango válido.
    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&); ///< \c "private" evita que el objeto sea copiado

    template <class T> friend class test_deque; ///< Datos de prueba para la clase
private:
    unsigned     m_front;    ///< Indice del primero del vector extendible.
    unsigned     m_size;     ///< Cantidad de valores almacenados en el vector extendible (puede ser cero).
    unsigned     m_capacity; ///< Cantidad máxima de valores que pueden estar almacenados en el vector extendible.
    value_type * m_vec;      ///< Bloque de memoria para para almacenar los \c m_capacity valores que caben en el vector extendible.
};

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
        }
    }
}

/** Acceso al \c "i"-ésimo valor del vector extendible.
    - Si <code>(i=>m_capacity)</code> retorna el valor \c m_vec[i-m_capacity].
    - Verifica que el valor de \c "i" esté en el rango válido.
    - Está implementado de manera que el índice de \c at(m_front+m_size-1)
      siempre esté en el rango válido.
    - Funciona como si los índices que están a partir de \c m_capacity estuvieran en un
      vector, a la par de \c m_vec[].
    - Rango válido para \c "i": <code>[[ m_front ==> m_front + m_size - 1 ]]</code>.
    - Levanta la excepción \c std::out_of_range si \c "i" está fuera del rango válido.
    \code
      m_vec[]       m_capacity==7    
        ||                           
        \/        m_front==<5> <6>   
      +---+---+---+---+---+---+---+    - at_check(<5>) es m_vec[5]
      | 5 | 6 | _ | _ | _ | 3 | 4 |    - at_check(<6>) es m_vec[6]
      +---+---+---+---+---+---+---+    - at_check(<7>) es m_vec[0]
    +-------+               |-------+  - at_check(<8>) es m_vec[1]
    |  #3  #4     m_front---+  #2   |
    |                               |  - Sólo estos accesos son válidos
    +-<-<-----------------------<-<-+  - los demás levantan \c std::out_of_range
                m_size == 4
    \endcode
*/
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()");
    }
}

/// Agrega una copia de \c "val" al final del vector extendible.
/// \pre
/// <code>size() < m_capacity</code>
/// \see test_deque<T>::test_push_back()
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()");
    }
}

/// Agrega una copia de \c "val" al principio del vector extendible.
/// \pre
/// <code>size() < m_capacity</code>
/// \see test_deque<T>::test_push_front()
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()");
    }
}
/// Saca del vector extendible al valor que está al frente.
/// \pre
/// <code>!empty()</code>
/// \see test_deque<T>::test_pop_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()");
    }
}

/// Saca del vector extendible al valor que está al frente.
/// \pre
/// <code>!empty()</code>
/// \see test_deque<T>::test_pop_back()
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
    /// Retorna \c "true" si el vector extendible está llena
    template <class T>
    inline bool deque<T>::full() const {
        return (m_size == m_ capacity);
    }
#endif

/** Verifica la invariante de la clase \c deque<T>.
    - Regresa \c "true" si \c "*this" contiene un valor correcto.
    - Podría retornar \c "true" aún cuando \c "*this" tenga su valor corrupto.
    - Podría no retornar si \c "*this" tiene su valor corrupto.
    - http://www.di-mare.com/adolfo/binder/c04.htm#sc11
    \see deque<T>::ok( )

    \par Rep: Diagrama de la clase
    \code
    +-------------------------------+ +-----------------------------------+
    | m_vec[]                       | |   m_vec[]       m_capacity==7     |
    |   ||                          | |     ||                            |
    |   \/ <1> <2>==m_front    <6>  | |     \/        m_front==<5> <6>    |
    | +---+---+---+---+---+---+---+ | |   +---+---+---+---+---+---+---+   |
    | | _ | _ | 3 | 9 | 5 | 6 | _ | | |   | 5 | 6 | _ | _ | _ | 3 | 9 |   |
    | +---+---+---+---+---+---+---+ | |   +---+---+---+---+---+---+---+   |
    |  <0>      |-----------+       | | +-------+               |-------+ |
    | m_front---+  #2  #3  #4       | | |  #3  #4     m_front---+  #2   | |
    |                               | | |                               | |
    |            m_size == 4        | | +-<-<-----------------------<-<-+ |
    +-------------------------------+ +-----------------------------------+
    \endcode
    - <em>Rep</em>: http://www.di-mare.com/adolfo/binder/c03.htm#k1-Rep

    \par Rep: Descripción en palabras
    - Los valores del vector extendible están almacenados en memoria dinámica,
      consecutivamente, en el vector \c "m_vec[]" cuyo tamaño no puede
      cambiar pues queda definido cómo \c "deque<T>::m_capacity" cuando el
      objeto es construido.
    - El primer valor del vector extendible siempre está almacenado en 
      \c "m_vec[m_front]".
    - El último valor del vector extendible siempre está almacenado en
      \c "m_vec[ (m_front+m_size-1) % m_capacity ]".
    - En el diagrama se muestran 2 formas en que puede estar almacenado el
      valor de una cola <code>Q = [3,9,5,6]</code> con \c "3" al frente y
      \c "6" al final.
    - En esta implementación del vector extendible se usa un vector circular en donde
      los valores están almacenados desde el índice \c "m_front" de \c "m_vec[]".
    - Como siempre el "frente" del vector extendible debe estar "antes" que el "final",
      cuando el valor de \c "m_front" no es \c "0", porque no apunta al
      principio del vector, lo que ocurre es que el vector extendible está almacenado
      llegando al final del vector y luego volviendo al principio
      (<em>wrap-around</em>).
    - La otra forma de almacenar el vector extendible en un vector circular es usar
      los campos \c "m_front" y \c "m_back", pero esta implementación
      tiene el problema de que es necesario desperdiciar uno de los
      campos del vector \c "m_vec[]" pues de otra manera no es posible
      determinar si el vector extendible está lleno o vacío.
*/
template <class T>
bool check_ok( const deque<T>& Q);

/** Verifica la invariante de la clase.
    - Implementación para \c check_ok( const deque<T>& Q ).
    \see check_ok( const deque<T>& Q)

    \remark
    - Desafortunadamente no fue posible lograr que el compilador aceptara
      una implementación directa para \c check_ok( const deque<T>& Q )
    - El ligador (<em>linker</em>) emite el error LNK2019. El truco para
      lidiar con este problema (<em>work arount</em>) es implementar \c ok()
    - Es mejor que \c check_ok() sea una función para evitarle al programador
      usuario la obligación de implementar el método \c ok()
    - http://www.di-mare.com/adolfo/binder/c04.htm#sc11
    - http://www.google.com/search?num=100&as_q=LNK2019+template+c%2B%2B
    - http://search.yahoo.com/search?n=100&p=LNK2019+template+c%2B%2B

*/
template <class T>
bool deque<T>::ok() const {
    if (this == 0) {
        /// - Invariante: ningún objeto puede estar almacenado en la posición nula.
        return false;
    }

    if ( ! (m_capacity > 0) ) {
        /// - Invariante: La capacidad \c m_capacity debe ser mayor que cero.
        return false;
    }
    if ( ! (m_front < m_capacity) ) {
        /// - Invariante: El índice \c m_front no puede exceder \c m_capacity.
        return false;
    }
    if ( ! (m_size <= m_capacity) ) {
        /// - Invariante: El índice \c m_size no puede exceder \c m_capacity.
        return false;
    }
    if ( ! (size() <= m_capacity) ) {
        /// - Invariante: La cantidad de valores almanenados \c size() no puede exceder \c m_capacity.
        return false;
    }
    if ( ! (m_vec != 0) ) {
        /// - Invariante: El vector \c m_vec[] debe existir en memoria dinámica.
        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] ) ) {
            /// - Invariante: Todos los valores almacenados en el contenedor
            ///   deben cumplir con su propia invariante
            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