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