Matrix_List.h

Ir a la documentación de este archivo.

// Matrix_List.h Copyright (C) 2009  adolfo@di-mare.com

#ifdef Spanish_dox
/** \file  Matrix_List.h
    \brief Declaraciones y definiciones para la clase \c Matrix_List<>.
    \author Adolfo Di Mare <adolfo@di-mare.com>
    \date   2004
    - Why English names??? ==> http://www.di-mare.com/adolfo/binder/c01.htm#sc04
*/
#endif
#ifdef English_dox
/** \file  Matrix_List.h
    \brief Declarations and definitiones for class \c Matrix_List<>.
    \author Adolfo Di Mare <adolfo@di-mare.com>
    \date   2004
    - Why English names??? ==> http://www.di-mare.com/adolfo/binder/c01.htm#sc04
*/
#endif

#include "Matrix_BASE.h"

#include <list>
#include <vector>

namespace Mx {

template <class E>
class Matrix_List_ColVal {
    template <class T> friend class Matrix_List;
private:
    unsigned m_col;
    E        m_val;
private:
    /// Constructor.
    Matrix_List_ColVal( unsigned col , const E& val )
        : m_col( col ) , m_val( val ) { }
public:
    ~Matrix_List_ColVal() { } //< Destructor.
};

#ifdef Spanish_dox
/** \class Matrix_List_ColVal
    \brief Clase privada para implementar la lista de valores de cada fila.
    \var   Matrix_List_ColVal::m_col;
    \brief Columna del valor almacenado en la matriz.
    \var   Matrix_List_ColVal::m_val;
    \brief Valor almacenado en la matriz.
*/
#endif
#ifdef English_dox
/** \class Matrix_List_ColVal
    \brief Private class used to implement the list of values for each row.
    \var   Matrix_List_ColVal::m_col
    \brief Column o the value stored in the matrix.
    \var   Matrix_List_ColVal::m_val
    \brief Value stored in the matrix.
*/
#endif


#ifdef Spanish_dox
/// Matriz muy chirrisquitica almacenada como matriz rala implementada con listas.
#endif
#ifdef English_dox
/// Chirrisquitica matrix stored as a sparse matrix implemented with lists.
#endif
/// \copydetails Matrix_BASE
template <class E>
class Matrix_List : public Matrix_BASE<E> {
public:
    Matrix_List(unsigned m = 1, unsigned n = 1);
    Matrix_List(const Matrix_List& o);
    /// \copydoc Matrix_BASE::Matrix_BASE(const E&)
    Matrix_List(const E& V)
        : Matrix_BASE<E>() , m_same()
        { reSize(1,1); (*this)(0,0) = V; }
    ~Matrix_List(); ///< Destructor.
public:
    unsigned rows()  const { return static_cast<unsigned>(m_VL.size()); }
    unsigned cols()  const { return m_cols; }
    unsigned size()  const { return rows() * m_cols; }
    unsigned count() const { return size(); }
    unsigned capacity() const { return size(); }
public:
    Matrix_List& operator= (const Matrix_List &o) { return copy(o); }
    Matrix_List& copy( const Matrix_List &o );
    Matrix_List& move( Matrix_List &o );
    Matrix_List& swap( Matrix_List &o );
    void clear();
public:
    bool equals( const Matrix_List & o ) const;
public:
    E& operator()(unsigned, unsigned);
    const E& operator()(unsigned, unsigned) const;
    E& at(unsigned i, unsigned j) { return at_Matrix(*this,i,j); }
    const E& at(unsigned i, unsigned j) const { return at_Matrix(*this,i,j); }

    void reShape(unsigned m, unsigned n);
    void reSize( unsigned m, unsigned n);
    void transpose();

    void setDefault(const E& same);
    const E& getDefault();
public:
    template <class T> friend bool  check_ok( const Matrix_List<T>& M );
    template <class T> friend class test_Matrix; ///< BUnit test.
private:
    std::vector< std::list < Matrix_List_ColVal< E > > > m_VL; // filas
    unsigned  m_cols; // # cols
    E         m_same; // valor por defecto
private:
    void reserve(unsigned n);
    void reSize(unsigned newsize);
}; // Matrix_List

#ifdef Spanish_dox
/**
    \var     Matrix_List::m_VL;
    \brief   Vector en donde están almacenados los valores de la lista de columnas.

    \var     Matrix_List::m_cols;
    \brief   Cantidad de columnas de la matriz.

    \var     Matrix_List::m_same;
    \brief   Valor almacenado en la mayor parte de la \c Matrix_List.
*/
#endif
#ifdef English_dox
/**
    \var     Matrix_List::m_VL;
    \brief   Vector where the column list values are stored.
    \var     Matrix_List::m_cols;
    \brief   Number of columns in the matrix.
    \var     Matrix_List::m_same;
    \brief   Most common value stored in the \c Matrix_List.
*/
#endif

#ifdef Spanish_dox
/** \copydoc check_ok_Matrix(const MAT&)
    \brief   Verifica la invariante de la clase.

    - El campo \c m_same indica cuál es el valor que se repite más en toda la matriz.
    - Usualmente \c m_same es el neutro aditivo \c value_type().
    - No existe un constructor explícito para darle a \c m_same su valor inicial, que
      es siempre inicializado en \c value_type(). Para cambiarlo es necesario invocar
      el método \c setgetDefault().
    - El vector \c m_VL[] contiene las listas de valores almacenados en la matriz.
      Cualquiera de estas listas puede estar vacía; aún todas pueden ser listas vacías.
    - La cantidad de columnas de la matriz es el valor fijo es \c m_cols.
    - El largo de las listas de valores cambia cuando se hace referencia a un valor M(i,j)
      mediante la versión que no es \c const del \c operator()(i,j). O sea, que es
      ese método el encargado de agregar valores en \c m_VL[], pues el operador
      homónimo \c const operator()(i,j) nunca agrega nada y, como es \c const, en
      general retorna una referencia constante a \c m_same.
    - Es posible que la matriz tenga dimensiones nulas, lo que implica que el vector
      \c m_VL[] está vacío.
    - No hace falta alacenar la cantidad de valores de la matriz porque se siempre es
      \c m_VL.size().
      el valor \c 0 (cero) al campo \c m_capacity.

    \par <em>Rep</em> Modelo de la clase
\code
m_VL<list<>>  _______
    +---+    /       \
  0 | *-|---| 1 , 'a' |
    +---+    \_______/                      0 1 2 3 4 5 6
  1 | ? |   M(0,1)=='a'                 0 / - a - - - - - \
    +---+                               1 | - - - - - - - |
  2 | ? |     _______       _______     2 | - - - - - - - |
    +---+    /       \     /       \    3 | - c - - - b - |
  3 | *-|---| 5 , 'b' |---| 1 , 'c' |   4 \ - - - - - - - /
    +---+    \_______/     \_______/
  4 | ? |   M(3,5)=='b'   M(3,1)=='c'
    +---+
        m_same == '-'    rows() == m_VL.size()  m_cols == 7
\endcode
    - http://www.di-mare.com/adolfo/binder/c03.htm#k1-Rep
    \remark
    Libera al programador de implementar el método \c Ok()
    - http://www.di-mare.com/adolfo/binder/c04.htm#sc11
*/
#endif
#ifdef English_dox
#endif
template<class T>
bool check_ok( const Matrix_List<T>& M ) {
    if ( ! check_ok_Matrix( M )  ) {
        return false;
    }
    if ( M.m_cols == 0 ) { // m_cols es el "marcador" que determina el valor de los demás
        if ( ! M.m_VL.empty() ) {
            return false; /// - check_ok(): <code>(m_cols == 0) <==> (m_VL.empty())</code>
        }
    }

    if ( ! check_ok( M.m_same ) ) {
        return false; /// - check_ok(): <code>check_ok( M.m_same )</code>
    }
    return true;
}


#ifdef Spanish_dox
/**
    \fn    Matrix_List::reserve(unsigned);
    \brief Ajusta la matriz para que pueda almacenar al menos
           \n valores diferentes a \c getDefault().
*/
#endif
#ifdef English_dox
/**
    \fn    Matrix_List::reserve(unsigned);
    \brief Adjust the matrix so that it can store at least
           \n values different than \c getDefault().
*/
#endif

/// \copydoc Matrix_BASE::Matrix_BASE(unsigned,unsigned)
template <class E>
Matrix_List<E>::Matrix_List(unsigned m, unsigned n)
    : m_VL(), m_cols(n), m_same()
{
    if (m == 0 || n == 0) {
        m_cols = 0;
    }
    else {
        reSize(m,n);
    }
//  m_same = E(); // Usa el número "cero" como neutro tipo "E"
}

/// \copydoc Matrix_BASE::Matrix_BASE(const Matrix_BASE&)
template <class E>
inline Matrix_List<E>::Matrix_List(const Matrix_List<E>& o) {
    copy( o );
    return;
}

template <class E>
inline Matrix_List<E>::~Matrix_List() { }

/// \copydoc Matrix_BASE::equals()
template <class E>
inline bool Matrix_List<E>::equals( const Matrix_List & o ) const {
    return equals_Matrix( *this, o );
}

/// \copydoc Matrix_BASE::copy()
template <class E>
Matrix_List<E>& Matrix_List<E>::copy( const Matrix_List<E> &o ) {
    if (this == &o) { // evita auto-borrado
        return *this;
    }
    this->m_VL   = o.m_VL;
    this->m_cols = o.m_cols;
    this->m_same = o.m_same;
    return *this;
}

/// \copydoc Matrix_BASE::move()
template <class E>
Matrix_List<E>& Matrix_List<E>::move( Matrix_List<E> &o ) {
    if (this == &o) { // evita auto-borrado
        return *this;
    }
    if ( m_VL.size() != o.m_VL.size() ) {
        m_VL.clear();
        m_VL.resize( o.m_VL.size() );
    }
    assert( m_VL.size() == o.m_VL.size() );
    for ( int i=0; i<m_VL.size(); ++i ) {
        this->m_VL[i].clear();
        this->m_VL[i].splice( m_VL[i].begin(), o.m_VL[i] );
    }
    this->m_cols = o.m_cols;
    this->m_same = o.m_same;
    return *this;
}

/// \copydoc Matrix_BASE::swap()
template <class E>
Matrix_List<E>& Matrix_List<E>::swap( Matrix_List<E> &o ) {
    std::swap( this->m_VL   , o.m_VL   );
    std::swap( this->m_cols , o.m_cols );
    std::swap( this->m_same , o.m_same );
    return *this;
}

/// \copydoc Matrix_BASE::clear()
template <class E>
void Matrix_List<E>::clear() {
    m_VL.clear();
    m_VL.push_back( std::list < Matrix_List_ColVal< E > >() );
    m_cols = 1;
    m_same = E(); // typename Matrix_BASE::value_type();
}

/// \copydoc Matrix_BASE::reSize()
template <class E>
void Matrix_List<E>::reSize(unsigned m, unsigned n) {
    unsigned rows = m_VL.size();
    if ( m > rows ) {
        std::vector< std::list < Matrix_List_ColVal< E > > > TMP(m);
        // TMP.resize(m);
        for ( unsigned i=0 ; i<rows ; ++i ) { // recuerda filas
            TMP[i].splice( TMP[i].begin(), this->m_VL[i] );
        }
        this->m_VL.resize(m); // reinstala las filas anteriores
        for ( unsigned i=0 ; i<rows ; ++i ) {
            this->m_VL[i].splice( this->m_VL[i].begin() , TMP[i] );
        }
    }
    else if ( m < rows ) { // desecha las filas restantes
        this->m_VL.resize(m);
    }
        assert( m_VL.size() == m );
    if ( n < m_cols ) { // desecha valores en columnas mayores a "n"
        rows = m_VL.size();
        for ( unsigned i=0 ; i<rows ; ++i ) {
            typedef typename std::list < Matrix_List_ColVal< E > >::iterator ITR;
            ITR it = this->m_VL[i].begin();
            while ( it != this->m_VL[i].end() ) {
                if ( it->m_col >= n ) {
                    it = this->m_VL[i].erase( it );
                }
                else {
                    ++it;
                }
            }
        }
    }
    m_cols = n;
    return;
}

/// \copydoc Matrix_BASE::reShape()
template <class E>
void Matrix_List<E>::reShape(unsigned m, unsigned n) {
    if ( m * n == m_VL.size() * m_cols ) {
        reSize(n,m);
    }
}

/// \copydoc Matrix_BASE::operator()(unsigned,unsigned) const
template <class E>
inline const E& Matrix_List<E>::operator()(unsigned i, unsigned j) const {
    assert( "Matrix_List<E>::operator()()" && (i < rows()) );
    assert( "Matrix_List<E>::operator()()" && (j < cols()) );

    typedef typename std::list < Matrix_List_ColVal< E > >::const_iterator ITR;
    ITR it = this->m_VL[i].begin();
    while ( it != this->m_VL[i].end() ) {
        if ( it->m_col == j ) {
            break;
        }
        ++it;
    }
    if ( it == this->m_VL[i].end() ) {
        return m_same;
    }
    else {
        return it->m_val;
    }

/*  NOTA
    Como este método es "const", de antemano se sabe que el programador no puede
    usarlo para modificar el valor de la matriz. Por eso, aunque el valor
    retornado sea una referencia a valor común por defecto m_same, de antemano
    el compilador asegura que ese valor no será modificado.

    Sin embargo, cuando el programador usa el método homónimo \c operator()(i,j)
    que no es \c "const", es posible que el valor retornado sí sea modificado.
    En ese caso, ya no es correcto retornar una referencia al valor común \c "m_same".
    - Por eso, cuando se usa el hace referencia en el otro \c operator()(i,j) es
      necesario agregar una entrada en los vectores paralelos en aquellos casos
      en que no existe un valor diferente a \c "m_same" para \c (i,j).
    - Esto quiere decir que sí es posible que al utilizar la versión modificable
      de \c operator()(i,j) quede en el vector "m_VL[]" un valor que es igual a
      "m_same". En el caso peor, podría ocurrir que todos los valores almacenados
      en el vector \c "m_VL[]" sean todos iguales a \c "m_same".
    - Una forma de corregir esta anomalía es "revisar después" si existe un valor
      en el vector \c "m_VL[]" que es igual a "m_same". Una forma eficiente de
      hacerlo es mantener el el Rep un puntero "m_last_change" que apunte al
      último valor \c "m_VL[]" que la versión modificable de \c operator()(i,j) retornó.
      En la siguiente invocación a \c operator()(i,j), se puede verificar si hubo un
      ese valor anterior fue cambiado de manera que tiene almacenado \c "m_same".
*/
}

/// \copydoc Matrix_BASE::operator()(unsigned,unsigned)
template <class E>
inline E& Matrix_List<E>::operator()(unsigned i, unsigned j) {
    assert( "Matrix_List<E>::operator()()" && (i < rows()) );
    assert( "Matrix_List<E>::operator()()" && (j < cols()) );

    // Busca al elemento M(i,j)
    typedef typename std::list < Matrix_List_ColVal< E > >::iterator ITR;
    ITR it = this->m_VL[i].begin();
    while ( it != this->m_VL[i].end() ) {
        if ( it->m_col == j ) {
            break;
        }
        ++it;
    }
    if ( it == this->m_VL[i].end() ) { // lo agrega porque no estaba
        this->m_VL[i].push_front( Matrix_List_ColVal< E >(j,m_same) );
        it = this->m_VL[i].begin();
    }
    return it->m_val;
}

/// \copydoc Matrix_BASE::getDefault()
template<class E>
inline const E& Matrix_List<E>::getDefault() {
    return m_same;
}

/// \copydoc Matrix_BASE::setDefault()
template<class E>
inline void Matrix_List<E>::setDefault(const E& same) {
    if ( m_same != same ) {
        clear();
        m_same = same;
    }
}

} // namespace Mx

#ifndef   Matrix_List_h
#define   Matrix_List_h   // Evita la inclusión múltiple

#ifdef Spanish_dox
   /// \c "Doxygen: Documentación en español"
    #define Spanish_dox "Doxygen: Documentación en español"
   /// \def   Matrix_List_h
   /// \brief Evita la inclusión múltiple.
#endif
#ifdef English_dox
   /// "Doxygen: English documentation"
    #define   English_dox   "Doxygen: English documentation"
   /// \def   Matrix_List_h
   /// \brief Avoids multiple inclusion.
#endif

#endif // Matrix_List_h

// EOF: Matrix_List.h