La Matriz Abstracta no Polimorfica:
 Todo Clases Namespaces Archivos Funciones Variables 'typedefs' Amigas 'defines'
Matrix_Sparse.h
Ir a la documentación de este archivo.
00001 // Matrix_Sparse.h Copyright (C) 2004  adolfo@di-mare.com
00002 
00003 #ifdef Spanish_dox
00004 /** \file  Matrix_Sparse.h
00005     \brief Declaraciones y definiciones para la clase \c Matrix_Sparse<>.
00006     \author Adolfo Di Mare <adolfo@di-mare.com>
00007     \date   2009
00008     - Why English names??? ==> http://www.di-mare.com/adolfo/binder/c01.htm#sc04
00009 */
00010 #endif
00011 #ifdef English_dox
00012 /** \file  Matrix_BASE.h
00013     \brief Declarations and definitiones for class \c Matrix_Sparse<>.
00014     \author Adolfo Di Mare <adolfo@di-mare.com>
00015     \date   2009
00016     - Why English names??? ==> http://www.di-mare.com/adolfo/binder/c01.htm#sc04
00017 */
00018 #endif
00019 
00020 #ifndef   Matrix_Sparse_h
00021 #define   Matrix_Sparse_h
00022 
00023 #include "Matrix_BASE.h"
00024 
00025 #include <cassert> // assert()
00026 
00027 namespace Mx {
00028 
00029 #ifdef Spanish_dox
00030 #endif
00031 #ifdef English_dox
00032 #endif
00033 
00034 #ifdef Spanish_dox
00035 /// Matriz chirrisquitica almacenada como una matriz rala.
00036 #endif
00037 #ifdef English_dox
00038 /// Chirrisquitica matrix stored as a sparse matrix.
00039 #endif
00040 /// \copydetails Matrix_BASE
00041 template <class E>
00042 class Matrix_Sparse : public Matrix_BASE<E> {
00043 public:
00044     Matrix_Sparse(unsigned m = 1, unsigned n = 1);
00045     Matrix_Sparse(const Matrix_Sparse& o);
00046     /// \copydoc Matrix_BASE::Matrix_BASE(const E&)
00047     Matrix_Sparse(const E& V) : m_capacity(0)
00048     { reSize(1,1); (*this)(0,0) = V; }
00049     ~Matrix_Sparse(); ///< Destructor.
00050 public:
00051     unsigned rows()  const { return m_rows; }
00052     unsigned cols()  const { return m_cols; }
00053     unsigned size()  const { return size_Matrix( *this ); }
00054     unsigned count() const { return count_Matrix( *this ); }
00055     unsigned capacity() const { return m_capacity; }
00056 public:
00057     Matrix_Sparse& operator= (const Matrix_Sparse& M) { return copy(M); }
00058     Matrix_Sparse& copy( const Matrix_Sparse& M );
00059     Matrix_Sparse& move( Matrix_Sparse& M );
00060     Matrix_Sparse& swap( Matrix_Sparse& M );
00061     void clear() { return clear_Matrix( *this ); }
00062 public:
00063     bool equals( const Matrix_Sparse & M ) const
00064     { return equals_Matrix( *this , M ); }
00065 public:
00066     E& operator()(unsigned i, unsigned j);
00067     const E& operator()(unsigned i, unsigned j) const;
00068     E& at(unsigned i, unsigned j) // throw (out_of_range);
00069     { return at_Matrix( *this , i,j ); }
00070     const E& at(unsigned i, unsigned j) const
00071     { return at_Matrix( *this , i,j ); }
00072 
00073     void reShape(unsigned m, unsigned n);
00074     void reSize( unsigned m, unsigned n);
00075     void transpose();
00076 
00077     void setDefault(const E& same);
00078     const E& getDefault() { return m_same; }
00079 public:
00080     template <class T> friend bool  check_ok( const Matrix_Sparse<T>& M );
00081     template <class T> friend class test_Matrix; ///< BUnit Test.
00082 private:
00083     /// Ajusta la matriz para que pueda almacenar \c n valores diferentes a \c getDefault().
00084     void reserve(unsigned _Count);
00085     void reSize(unsigned newsize);
00086 private:
00087     unsigned* m_I;   ///< Indice "i" de \c M(i,j) <code>0 <= i < m_capacity</code>
00088     unsigned* m_J;   ///< Indice "j" de \c M(i,j) <code>0 <= i < m_capacity</code>
00089     E       * m_val; ///< Valor para \c M(i,j) <code>0 <= i < m_capacity</code>
00090     unsigned  m_size;   ///< Cantidad de valores insertados en los 3 vectores paralelos
00091     unsigned  m_capacity; ///< Tamaño de los 3 vectores paralelos
00092     unsigned  m_rows; ///< Cantidad de filas de la matriz
00093     unsigned  m_cols; ///< Cantidad de columnas de la matris
00094     E         m_same; ///< Valor almacenado en la mayor parte de la \c Matrix_Sparse
00095 private:
00096     template <class T> friend
00097     void add_Matrix( Matrix_Sparse<T>& Res, const Matrix_Sparse<T>& M );
00098 }; // Matrix_Sparse
00099 
00100 /** Verifica la invariante de la clase.
00101     - El campo \c m_same indica cuál es el valor que se repite más en toda la matriz.
00102     - Usualmente \c same es el neutro aditivo \c value_type().
00103     - No existe un constructor explícito para darle a \c m_same su valor inicial, que
00104       es siempre inicializado en \c value_type(). Para cambiarlo es necesario invocar
00105       el método \c setgetDefault().
00106     - Los vectores \c m_I[], \c m_J[] y \c m_val[] son vectores paralelos, todos de
00107       longitud \c Matrix_Sparse::m_capacity.
00108     - La cantidad máxima de valores diferente que pueden ser almacenados en la matriz
00109       es \c Matrix_Sparse::m_capacity.
00110     - El largo de estos vectores aumenta cuando se hace referencia a un valor M(i,j)
00111       mediante la versión que no es \c const del \c operator()(i,j). O sea, que es
00112       ese método el encargado de agregar valores en \c m_val[], pues el operador
00113       homónimo \c const operator()(i,j) nunca agrega nada y, como es \c const, en
00114       general retorna una referencia constante a \c m_same.
00115     - Es posible que la matriz tenga dimensiones nulas, lo que implica que todos los
00116       punteros a los vectors paralelos deben ser nulos. Este hecho se marca dándolo
00117       el valor \c 0 (cero) al campo \c m_capacity.
00118     - En todos los algoritmos, "m" o "m_rows" es la cantidad de filas == \c rows()
00119     - En todos los algoritmos, "n" o "m_cols" es la cantidad de columnas == \c cols()
00120 
00121     \par <em>Rep</em> Modelo de la clase
00122 \code
00123          ____________________________________
00124         /          m_capacity                \
00125         +---+---+---+---+---+---+-..-+---+---+       0 1 2 3 4 5 6
00126  m_I--->| 1 | 3 | 3 |'-'| ...       ...  |'-'|   0 / - - - - - - - \
00127         +---+---+---+---+ ...       ...  +---+   1 | - a - - - - - |
00128  m_J--->| 1 | 2 | 1 |'-'| ...       ...  |'-'|   2 | - - - - - - - |
00129         +---+---+---+---+ ...       ...  +---+   3 | - c b - - - - |
00130 m_val-->|'a'|'b'|'c'|'-'| ...       ...  |'-'|   4 \ - - - - - - - /
00131         +---+---+---+---+---+---+-..-+---+---+
00132           0   1   2   |
00133         m_size--------+ == 3    m_same == '-'   m_rows == 5  m_cols == 7
00134 \endcode
00135     - http://www.di-mare.com/adolfo/binder/c03.htm#k1-Rep
00136     \remark
00137     Libera al programador de implementar el método \c Ok()
00138     - http://www.di-mare.com/adolfo/binder/c04.htm#sc11
00139 */
00140 template <class T>
00141 bool check_ok( const Matrix_Sparse<T>& M ) {
00142     if ( M.m_capacity == 0 ) { // m_capacity es el "marcador" que determina el valor de los demás
00143         if ( M.m_I != 0 ) {
00144             return false; /// - check_ok(): <code>(m_capacity == 0) <==> (m_I == 0)</code>
00145         }
00146         if ( M.m_J != 0 ) {
00147             return false; /// - check_ok(): <code>(m_capacity == 0) <==> (m_J == 0)</code>
00148         }
00149         if ( M.m_val != 0 ) {
00150             return false; /// - check_ok(): <code>(m_capacity == 0) <==> (m_val == 0)</code>
00151         }
00152     }
00153     else {
00154         if ( M.m_rows == 0 ) {
00155             return false; /// - check_ok(): <code>(m_rows == 0) ==> (m_capacity == 0)</code>
00156         }
00157         if ( M.m_cols == 0 ) {
00158             return false; /// - check_ok(): <code>(m_cols == 0) ==> (m_capacity == 0)</code>
00159         }
00160         if ( M.m_I == 0 ) {
00161             return false; /// - check_ok(): <code>(m_capacity != 0) <==> (m_I != 0)</code>
00162         }
00163         if ( M.m_J == 0 ) {
00164             return false; /// - check_ok(): <code>(m_capacity != 0) <==> (m_J != 0)</code>
00165         }
00166         if ( M.m_val == 0 ) {
00167             return false; /// - check_ok(): <code>(m_capacity != 0) <==> (m_val != 0)</code>
00168         }
00169     }
00170 
00171     if (M.m_rows == 0 || M.m_cols == 0) {
00172         if (M.m_rows == 0 && M.m_cols == 0) {
00173             // OK ==> los 2 son nulos
00174         }
00175         else {
00176             return false;  /// - check_ok(): <code>(m_rows == 0) <==> (m_cols == 0)</code>
00177         }
00178     }
00179 
00180     if ( M.m_size > M.m_capacity ) {
00181         return false; /// - check_ok(): <code>( m_size <= m_capacity )</code>
00182     }
00183     if ( ! check_ok (M.m_same) ) {
00184         return false; /// - check_ok(): <code>check_ok (m_same)</code>
00185     }
00186     for (unsigned k=0; k<M.m_size; ++k) {
00187         if ( ! ( (0<=M.m_I[k]) && (M.m_I[k]<M.m_rows) ) ) {
00188             return false; /// - check_ok(): <code>( (0<=m_I[k]) && (m_I[k] < m_rows) ) k = [0..m_size-1]</code>
00189         }
00190         if ( ! ( (0<=M.m_J[k]) && (M.m_J[k]<M.m_cols) ) ) {
00191             return false; /// - check_ok(): <code>( (0<=m_J[k]) && (m_J[k] < m_cols) ) k = [0..m_size-1]</code>
00192         }
00193         if ( ! check_ok( M.m_val[k] ) ) {
00194             return false; /// - check_ok(): <code>check_ok( m_val[k] )</code>
00195         }
00196     }
00197     return true;
00198 }
00199 
00200 /// Define el escalar que por defecto está en todas las entradas de la \c Matrix_Sparse.
00201 /// - Si <code>same != getDefault()</code> la matriz queda vacía.
00202 /// - De lo contrario, nada ocurre.
00203 template<class E>
00204 inline void Matrix_Sparse<E>::setDefault(const E& same) {
00205     if ( m_same != same ) {
00206         m_same = same;
00207         m_size = 0;
00208     }
00209 }
00210 
00211 /** Constructor de vector.
00212     - Obtiene suficiente memoria dinámica para almacenas los
00213       <code> n * m </code> valores de la matriz.
00214     - Si \c "value_type" tiene un constructor de vector, lo
00215       usar para inicializar cada uno de los valores de la matriz;
00216       de lo contrario, los deja tal cual están en la memoria.
00217     - Si \c "value_type" es uno de los tipos escalares básicos,
00218       como lo son \c int o \c float, los valores almacenados
00219       en la matriz quedan tal cual están y no son inicializados.
00220     \pre
00221      -  <code> m * n > 0  </code>
00222      -  <code> (m > 0) && (n > 0) </code>
00223 */
00224 template <class E>
00225 inline Matrix_Sparse<E>::Matrix_Sparse(unsigned m, unsigned n) : m_same() {
00226     if (m == 0 || n == 0) {
00227         m_rows = m_cols = 0;
00228         m_val = 0;
00229         m_capacity = 0;
00230     } else {
00231         m_rows = m;
00232         m_cols = n;
00233 
00234         m_capacity = 16; // pues 16 == 2*2*2*2 ...
00235         m_I   = new unsigned [m_capacity];
00236         m_J   = new unsigned [m_capacity];
00237         m_val = new E[m_capacity];
00238     }
00239 
00240     m_size = 0;
00241 //  m_same = E(); // Usa el número "cero" como neutro tipo "E"
00242 }
00243 
00244 template <class E>
00245 inline Matrix_Sparse<E>::Matrix_Sparse(const Matrix_Sparse<E>& o) {
00246     m_capacity = 0; // m_capacity==0 indica que NO se está usando memoria dinámica
00247     copy( o );     // assert( this != &o );
00248     return;       // ... pues ya "o" existe y se está usando para incializar a "*this"
00249 /*  NOTA
00250     Cuando un objeto usa memoria dinámica, copiarlo es un proceso diferente a
00251     inicializarlo a partir de otro valor de su misma clase. En otras palabras,
00252     el trabajo que hace el constructor CLS::CLS( const CLS& ) es muy diferente
00253     al que hace el copiador CLS& operator=( const CLS & ).
00254 
00255     El truco de programación usado en en esta implementación consiste en "marcar"
00256     el valor "m_capacity" para saber si se ha obtenido o no memoria dinámica
00257     para los vectores paralelos. La implementación de copy() está hecha de manera
00258     que si "m_capacity" es un puntero nulo, en copy() se inicializan correctamente
00259     todos los del Rep de Matrix_Sparse. Eso explica por qué la implementación de
00260     copy() es un tanto más elaborada que lo que a primera vista pareciera que es
00261     necesario.
00262 */
00263 }
00264 
00265 template <class E>
00266 inline Matrix_Sparse<E>::~Matrix_Sparse() {
00267     if (m_capacity != 0) { // sólo devuelve la memoria dinámica que sí ha adquirido
00268         delete [] m_I;
00269         delete [] m_J; // Retorna la memoria dinámica en uso
00270         delete [] m_val;
00271     }
00272 }
00273 
00274 /** Copia desde \c "o".
00275     - Copia todo el valor de \c "o" sobre \c "*this", de forma que el nuevo valor de
00276       \c "*this" sea un duplicado exacto del valor de \c "o".
00277     - El valor anterior de \c "*this" se pierde.
00278     - El objeto \c "o" mantiene su valor anterior.
00279     - Luego de la copia, cuando el valor de \c "o" cambia, el de \c "*this" no cambiará,
00280       y viceversa, pues la copia es una copia profunda; no es superficial.
00281     - Si \c "*this" es \c "o" entonces su valor no cambia.
00282     - Después de esta operación siempre ocurre que <code> *this == o </code>.
00283 
00284     \par Complejidad:
00285          O( <code>  rows() * cols() </code> )
00286 
00287     \returns *this
00288     \see http://www.di-mare.com/adolfo/binder/c04.htm#sc05
00289 */
00290 template <class E>
00291 Matrix_Sparse<E>& Matrix_Sparse<E>::copy( const Matrix_Sparse<E> &o ) {
00292     if (this == &o) { // evita auto-borrado
00293         return *this;
00294     }
00295     if (o.m_capacity == 0) {
00296         if (m_capacity != 0) { // Como copy() puede ser invocado cuando el Rep
00297             delete [] m_val;   // NO ha sido inicializado, en esta implementación
00298             delete [] m_J;     // hay que tener cuidado de no usar los otros campos
00299             delete [] m_I;     // del Rep antes de darles valor.
00300         }                      // - "m_capacity" SI debe tener su valor correcto.
00301         m_rows = m_cols = 0;
00302         m_val = 0;
00303         m_same = o.m_same;
00304         m_size = 0;       //  assert( o.m_size == 0 );
00305         m_capacity = 0;   //  assert( o.m_capacity == 0 );
00306         return *this;
00307     }
00308 
00309     // se asegura de que las dos matrices sean del mismo tamaño
00310     if (m_capacity != o.m_capacity) { // truco para evitar borrar la memoria dinámica
00311         if (m_capacity != 0) { // sólo devuelve la memoria dinámica que sí ha adquirido
00312             delete [] m_val;
00313             delete [] m_J;
00314             delete [] m_I;
00315         }
00316 
00317         m_capacity = o.m_capacity;
00318         m_I   = new unsigned [m_capacity];
00319         m_J   = new unsigned [m_capacity];
00320         m_val = new typename Matrix_BASE<E>::value_type[m_capacity];
00321     }
00322     m_same = o.m_same;
00323     m_size = o.m_size;
00324 
00325     // como las matrices son del mismo tamaño,
00326     // basta copiarlas entrada por entrada.
00327     m_rows = o.m_rows;
00328     m_cols = o.m_cols;
00329     for (unsigned k=0; k<m_size; ++k) {
00330         m_I[k]   = o.m_I[k];
00331         m_J[k]   = o.m_J[k];
00332         m_val[k] = o.m_val[k];
00333     }
00334     return *this;
00335 }
00336 
00337 /** Traslada el valor de \c "o" a \c "*this".
00338   - El valor anterior de \c "*this" se pierde.
00339   - El nuevo valor de \c "*this" es el que \c "o" tuvo.
00340   - \c "o" queda en el estado en que lo dejaría \c Erase().
00341   - Si \c "*this" es \c "o" entonces su valor no cambia.
00342   - En general, después de esta operación casi
00343     nunca ocurre que <code> (*this == o) </code>
00344 
00345     \par Complejidad:
00346          O( <code>  rows() * cols() </code> )
00347 
00348     \returns \c *this
00349 
00350     \see http://www.di-mare.com/adolfo/binder/c04.htm#sc07
00351 */
00352 template <class E>
00353 Matrix_Sparse<E>& Matrix_Sparse<E>::move( Matrix_Sparse<E> &o ) {
00354     if (this == &o) { // evita auto-borrado
00355         return *this;
00356     } else if (o.m_val == 0) {
00357         if (m_val != 0) {
00358             delete [] m_val;
00359         }
00360         m_rows = m_cols = 0;
00361         m_val = 0;
00362         return *this;
00363     } else if ( m_val != 0 ) {
00364         delete [] m_val;
00365     }
00366     m_val = o.m_val;
00367     m_rows = o.m_rows;
00368     m_cols = o.m_cols;
00369 
00370     o.m_val = 0;
00371     o.m_rows = o.m_cols = 0;
00372     return *this;
00373 }
00374 
00375 /** Intercambia los valores de \c "*this" y \c "o".
00376     - Debido a que algunos métodos retornan copias del valor de \c "*this" en
00377       lugar de una referencia, como ocurre con \c Matrix_Sparse::Child(), a veces
00378       \c swap() no tiene el resultado esperado por el programador.
00379     - Por ejemplo, si se invoca <code> T.Child(i). swap( T.Child(j) ) </code>
00380       el resultado no es intercambiar los hijos, sino más bien intercambiar
00381       los valores de los sub-árboles temporales \c T.Child(i) y \c T.Child(j).
00382       La forma correcta de intercambiar hijos es usar \c Graft().
00383 
00384       \par Complejidad:
00385          O( \c 1 )
00386 
00387     \returns *this
00388 
00389     \see http://www.di-mare.com/adolfo/binder/c04.htm#sc08
00390 */
00391 template <class E>
00392 Matrix_Sparse<E>& Matrix_Sparse<E>::swap( Matrix_Sparse<E> &o ) {
00393     std::swap( this->m_I        , o.m_I        );
00394     std::swap( this->m_J        , o.m_J        );
00395     std::swap( this->m_val      , o.m_val      );
00396     std::swap( this->m_size     , o.m_size     );
00397     std::swap( this->m_capacity , o.m_capacity );
00398     std::swap( this->m_rows     , o.m_rows     );
00399     std::swap( this->m_cols     , o.m_cols     );
00400     std::swap( this->m_same     , o.m_same     );
00401     return *this;
00402 }
00403 
00404 /** Le cambia las dimensiones a la matriz.
00405     - En algunos casos los valores almacenados en la matriz no quedan
00406       todos iguales a \c Matrix_Sparse<E>::value_type().
00407     \pre <code> (m > 0) && (n > 0) </code>
00408 */
00409 template <class E>
00410 void Matrix_Sparse<E>::reSize(unsigned m, unsigned n) {
00411     // NO hace falta cambiar m_capacity porque lo único que está cambiando
00412     // el la dimensión de la matriz
00413     if (m != m_rows || n != m_cols) {
00414         m_size = 0; // desecha todos los valores anteriores
00415         m_rows = m; // cambia las dimensiones de la matriz
00416         m_cols = n;
00417     }
00418 
00419     if (m==0 || n==0) {
00420         m_rows = 0;
00421         m_cols = 0;
00422         m_size = 0;
00423         if (m_capacity != 0) {
00424             m_capacity = 0; // todo esto mantiene la invariante de la clase
00425             delete [] m_I;     m_I = 0;
00426             delete [] m_J;     m_J = 0;
00427             delete [] m_val;   m_val = 0;
00428         }
00429     }
00430     return;
00431 
00432 /*  NOTA
00433     Esta es la antigua especificación de reSize(). Es incorrecta
00434     porque presume que el Rep de la matriz es un vector denso en
00435     donde están almacenados todos los valores de la matriz:
00436 
00437     +----------------------------------------------------------+
00438     | reSize(): Le cambia las dimensiones a la matriz.         |
00439     | ========                                                 |
00440     | - Si ocurre que (m*n) == rows() * cols() los valores de  |
00441     |   la matriz se mantienen, aunque cambian sus dimensiones.|
00442     | - Si (m*n) != rows() * cols() los valores de la matriz   |
00443     |   quedarán inicializados de la misma forma en que los    |
00444     |   inicializaría CERO == Matrix_Sparse<E>::value_type().  |
00445     |                                                          |
00446     | \pre (m > 0) && (n > 0)                                  |
00447     +----------------------------------------------------------+
00448 
00449     En la actual especificación, que ya está corregida, no queda
00450     implícita la presunción sobre cómo está organizada internamente
00451     la matriz. Por eso, esta nueva especificación sí sirve para una
00452     matriz implementada con un vector denso de valores, o para la
00453     matriz implementada como una matriz rala.
00454 
00455     Estos pequeños detalles en algunas ocasiones surgen cuando el
00456     programador de una clase introduce mejoras o modificaciones, pues
00457     muchas veces es muy difícil o prácticamente imposible predecir
00458     todos los pormenores y detalles de una especificación o de una
00459     implementación.
00460 */
00461 
00462 /*  NOTA
00463     Esta es la imnplementación anterior, que debe reacomodar los ínices
00464     (i,j) de aquellos valores almacenados en los vectores paralalos para
00465     simular que la matriz rala en realidad está almacenada como una
00466     matriz densa, dentro de un vector.
00467     - Al modificar la especificación de para reSize() ya no hace falta
00468     hacer todo este trabajo.
00469 
00470     NO hace falta cambiar m_capacity porque lo único que está cambiando
00471     el la dimensión de la matriz
00472 */
00473 
00474 /*  Nota para esta implementación:
00475     Este método funciona de una forma similar a reSize() para la matriz implementada con
00476     un vector. Para lograr que las clases Matrix<E> y Matrix_Sparse<E> tengan la misma
00477     funcionalidad, esta implementación reacomoda los índices de la matriz de manera que
00478     las m_rows*m_cols entradas queden reacomodadas como si la implementación usara un
00479     vector de dimension m*n. Sin embargo, lo lógico sería eliminar todos los valores
00480     de la matriz trocando el ciclo "for(;k;){}" por un eficiente "m_size=0;"
00481     - Esto muestra que una especificación que aparenta ser "amplia", como lo es la de
00482       Matrix<E>::reSize(n,m), en realidad se queda "corta" si se toma en cuenta que la
00483       misma especificación debe servir para varias implementaciones diferentes.
00484     - Además, muestra que algunas operaciones sólo tienen sentido para una implementación
00485       específica, como ocurre con las operaciones Matrix_Sparse<E>>::getDefault() y su
00486       "seteador" Matrix_Sparse<E>>::setgetDefault().
00487 */
00488 #if 0
00489     if (m * n == m_rows * m_cols) {
00490         m_size = 0; // desecha todos los valores anteriores
00491     }
00492     else {
00493         unsigned row = 0, col = 0;
00494         for (unsigned k=0; k<m_size; ++k) {
00495             // M(i,j) <==> m_val[ (i * m_cols) + j ] ; // si almacena los valores por filas
00496             // M(i,j) <==> m_val[ i + (j * m_rows) ] ; // si almacena los valores por columnas
00497 
00498             unsigned lineal = (m_I[k] * m_cols) + m_J[k]; // por filas
00499         //  unsigned lineal = m_I[k] + (m_j[k] * m_rows); // por columnas
00500             m_I[k] = lineal / n; // lineal % m;
00501             m_J[k] = lineal % n; // lineal / m;
00502         }
00503     }
00504     m_rows = m; // cambia las dimensiones de la matriz
00505     m_cols = n;
00506 #endif
00507 }
00508 
00509 /** Le ajusta las dimensiones a la matriz.
00510     - Si ocurre que <code> (m*n) == rows()*cols() </code> hace
00511       lo mismo que haría \c reSize(m,n).
00512     - En caso contrario, no hace nada.
00513 */
00514 template <class E>
00515 inline void Matrix_Sparse<E>::reShape(unsigned m, unsigned n) {
00516     if ( m * n == m_rows * m_cols ) {
00517         reSize(n,m);
00518     }
00519 }
00520 
00521 /// Retorna una referencia al elemento [i,j] de la matriz ( \c const ).
00522 /// - \c M(i,j) significa lo que en arreglos se denota con \c M[i][j].
00523 /// - <code>val = M(i,j); // M(i,j) es un "rvalue" (const)</code>
00524 template <class E>
00525 inline const E& Matrix_Sparse<E>::operator()(unsigned i, unsigned j) const {
00526     assert( "Matrix_Sparse<E>::operator()()" && (i < rows()) );
00527     assert( "Matrix_Sparse<E>::operator()()" && (j < cols()) );
00528 
00529     for (unsigned k=0; k<m_size; k++) {
00530         if ( m_I[k] == i ) {
00531             if ( m_J[k] == j ) {
00532                 return m_val[k];
00533             }
00534         }
00535     }
00536     return m_same;
00537 /*  NOTA
00538     Como este método es "const", de antemano se sabe que el programador no puede
00539     usarlo para modificar el valor de la matriz. Por eso, aunque el valor
00540     retornado sea una referencia a valor común por defecto m_same, de antemano
00541     el compilador asegura que ese valor no será modificado.
00542 
00543     Sin embargo, cuando el programador usa el método homónimo operator()(i,j)
00544     que no es "const", es posible que el valor retornado sí sea modificado.
00545     En ese caso, ya no es correcto retornar una referencia al valor común "m_same".
00546     - Por eso, cuando se usa el hace referencia en el otro operator()(i,j) es
00547       necesario agregar una entrada en los vectores paralelos en aquellos casos
00548       en que no existe un valor diferente a "m_same" para (i,j).
00549     - Esto quiere decir que sí es posible que al utilizar la versión modificable
00550       de operator()(i,j) quede en el vector "m_val[]" un valor que es igual a
00551       "m_same". En el caso peor, podría ocurrir que todos los valores almacenados
00552       en el vector "m_val[]" sean todos iguales a "m_same".
00553     - Una forma de corregir esta anomalía es "revisar después" si existe un valor
00554       en el vector "m_val[]" que es igual a "m_same". Una forma eficiente de
00555       hacerlo es mantener el el Rep un puntero "m_last_change" que apunte al
00556       último valor "m_val[]" que la versión modificable de operator()(i,j) retornó.
00557       En la siguiente invocación a operator()(i,j), se puede verificar si hubo un
00558       ese valor anterior fue cambiado de manera que tiene almacenado "m_same".
00559 */
00560 #if 0
00561     // Este código podría ser agregado al principio de operator()(i,j)
00562     if (m_last_change != 0) {
00563         if ( *m_last_change == m_same ) { // el último uso de op()(i,j) dejó "m_same"
00564             if ( m_size == 1 ) { // Elimina los vectores viejos
00565                 delete [] m_I;    m_I = 0;
00566                 delete [] m_J;    m_J = 0;
00567                 delete [] m_val;  m_val = 0;
00568                 m_capacity = 0;
00569                 m_size     = 0;
00570             }
00571             else { // intercambia este valor con el último
00572                 m_size--;
00573                 unsigned k = (m_last_change - m_val); // índice de "* m_last_change"
00574                 *m_last_change = m_val[m_size];
00575                 m_I[k] = m_I[m_size];
00576                 m_J[k] = m_J[m_size];
00577             }
00578         }
00579         m_last_change = 0;
00580     }
00581 #endif
00582 }
00583 /// Retorna una referencia al elemento [i,j] de la matriz.
00584 /// - \c M(i,j) significa lo que en arreglos se denota con \c M[i][j].
00585 /// - <code>M(i,j) = val; // M(i,j) es un "lvalue" (modificable)</code>
00586 template <class E>
00587 inline E& Matrix_Sparse<E>::operator()(unsigned i, unsigned j) {
00588     assert( "Matrix_Sparse<E>::operator()()" && (i < rows()) );
00589     assert( "Matrix_Sparse<E>::operator()()" && (j < cols()) );
00590 
00591     // Busca al elemento (i,j) en los vectores paralelos
00592     for (unsigned k=0; k<m_size; k++) {
00593         if ( m_I[k] == i ) {
00594             if ( m_J[k] == j ) {
00595             //  m_last_change = & m_val[k];
00596                 return m_val[k];
00597             }
00598         }
00599     }
00600 
00601     assert( (m_size <= m_capacity) && " => Agotado m_val[] Matrix_Sparse<E>::operator()()" );
00602     if (m_size == m_capacity) {
00603         unsigned new_capacity = m_capacity;
00604         if (m_capacity % 16 == 0) {
00605             new_capacity += 16;
00606         }
00607         else {
00608             new_capacity /= 16; // Hace que el nuevo tamaño sea divisible por 16
00609             new_capacity *= 16;
00610             new_capacity += 16;
00611         }
00612         reSize( new_capacity ); // Agrega 16 porque 16 == 2*2*2*2 ...
00613     }
00614     // Agrega un nuevo valor modificable en los vectores paralelos
00615     m_I[m_size] = i;
00616     m_J[m_size] = j;
00617     m_val[m_size] = m_same;
00618 //  m_last_change = & m_val[m_size];
00619     return m_val[m_size++];
00620 }
00621 
00622 /// Le cambia el tamaño máximo posible a la matriz.
00623 /// - Le aumenta la cantidad de valores diferentes a \c getDefault().
00624 /// - No hace nada cuando <code>size() < newsize</code>.
00625 template <class E>
00626 void Matrix_Sparse<E>::reSize(unsigned newsize) {
00627     if ( newsize < m_size ) { // hay más valores en uso que "newsize"
00628         // assert((m_size < newsize) && "=>Matrix_Sparse<E>::reSize()" );
00629         return;
00630     }
00631     unsigned * new_I   = new unsigned [ newsize ]; // Obtiene los vectores nuevos
00632     unsigned * new_J   = new unsigned [ newsize ];
00633     E        * new_val = new E        [ newsize ];
00634     if (m_capacity > 0) { // Copia los valores en uso
00635         for (unsigned k=0; k<m_size; ++k) {
00636             new_I[k]   = m_I[k];
00637             new_J[k]   = m_J[k];
00638             new_val[k] = m_val[k];
00639         }
00640         delete [] m_I;  // Elimina los vectores viejos
00641         delete [] m_J;
00642         delete [] m_val;
00643     }
00644     m_I = new_I;      // Instala los vectores nuevos
00645     m_J = new_J;
00646     m_val = new_val;
00647     m_capacity = newsize;
00648 }
00649 
00650 /// \copydoc Matrix_BASE::add_Matrix()
00651 template <class T>
00652 void add_Matrix( Matrix_Sparse<T>& Res, const Matrix_Sparse<T> & M ) {
00653     // verifica que las dos matrices sean del mismo tamaño
00654     assert( "Matrix_Sparse<E>::add()" && ( Res.rows() == M.rows() ) );
00655     assert( "Matrix_Sparse<E>::add()" && ( Res.cols() == M.cols() ) );
00656 
00657     // Como las matrices son del mismo tamaño basta sumarlas entrada por entrada.
00658 
00659     typename Matrix_BASE<T>::value_type *pRes =   Res.m_val;
00660     typename Matrix_BASE<T>::value_type *pM   = & M.m_val[0];
00661     typename Matrix_BASE<T>::value_type *pEND = & Res.m_val[M.m_cols * M.m_rows];
00662     for ( ; pRes != pEND; ++pRes, ++pM ) {
00663         *pRes += *pM;
00664     }
00665     return;
00666 }
00667 
00668 #if 0
00669 /** Le resta a \c "*this" la matriz \c "O".
00670     \pre
00671     - \c "*this" y \c "O" deben tener las mismas dimensiones
00672     - <code> rows() == O.rows() && cols() == O.cols() </code>
00673 
00674     \par Complejidad:
00675          O( <code> rows() * cols() </code> )
00676 
00677     \remarks
00678     - Esta es la implementación de
00679       Matrix_Sparse<E> operator-( Matrix_Sparse<E>&, Matrix_Sparse<E> )
00680     - El compilador tiene problemas en compilar un función amiga (<em>"friend"</em>)
00681       definida con plantillas si esa función amiga no está definida (implementada)
00682       dentro de la declaración de la clase. Para solventar esta deficiencia existe
00683       esta función amiga que realiza el trabajo, aunque es poco cómoda de usar.
00684 */
00685 /// \copydoc Matrix_BASE::substract()
00686 template <class T>
00687 void substract_Matrix( Matrix_Sparse<T>& Res, const Matrix_Sparse<T> & M ) {
00688     // verifica que las dos matrices sean del mismo tamaño
00689     assert( "Matrix_Sparse<E>::substract()" && ( Res.rows() == M.rows() ) );
00690     assert( "Matrix_Sparse<E>::substract()" && ( Res.cols() == M.cols() ) );
00691 
00692     // Como las matrices son del mismo tamaño basta restarlas entrada por entrada.
00693 
00694     typename Matrix_BASE<T>::value_type *pRes =   Res.m_val;
00695     typename Matrix_BASE<T>::value_type *pM   = & M.m_val[0];
00696     typename Matrix_BASE<T>::value_type *pEND = & Res.m_val[M.m_cols * M.m_rows];
00697     for ( ; pRes != pEND; ++pRes, ++pM ) {
00698         *pRes += *pM;
00699     }
00700     return;
00701 }
00702 #endif
00703 
00704 } // namespace Mx
00705 
00706 #endif // Matrix_Sparse_h
00707 
00708 // EOF: Matrix_Sparse.h