Uso de Mx::Matrix:
 Todo Clases Namespaces Archivos Funciones Variables 'typedefs' Amigas 'defines'
Matrix_Sparse.h
Ir a la documentación de este archivo.
1 // Matrix_Sparse.h Copyright (C) 2004 adolfo@di-mare.com
2 
3 /** \file Matrix_Sparse.h
4  \brief Declaraciones y definiciones para la clase \c Matrix_Sparse.
5 
6  \author Adolfo Di Mare <adolfo@di-mare.com>
7  \date 2004
8 
9  - Why English names??? ==> http://www.di-mare.com/adolfo/binder/c01.htm#sc04
10 */
11 
12 #ifndef Matrix_Sparse_h
13 #define Matrix_Sparse_h
14 
15 #include <cassert> // assert()
16 
17 /// Definido por la biblioteca C++ estándar
18 namespace std {} // Está acá para que Doxygen lo documente
19 
20 /// Matriz chirrisquitica de adolfo@di-mare.com
21 namespace Mx {
22 
23 /** Esta es una clase matriz muy chirrisquitica almacenada como una matriz rala.
24  - La matriz tiene tamaño \c rows() x \c cols().
25  - Se le puede cambiar el tamaño dinámicamente con el método \c reSize().
26  - La clase \c E debe incluir un neutro para la adición, cuyo valor debe poderse
27  obtener invocando el convertidor \c Matrix_Sparse<E>::value_type().
28  - Las operaciones aritméticas "+" "-" "*" deben estar definidas para
29  \c Matrix_Sparse<E>::value_type y debe existir el valor \c Matrix_Sparse<E>::value_type().
30  \see http://www.oonumerics.org/oon/
31 */
32 template <class E>
34 public:
35  /// Tipo del objeto almacenado, similar al nombre usado en STL
36  typedef E value_type;
37  /// Tipo del objeto almacenado, similar al nombre usado en STL
39  /// Tipo del objeto almacenado, similar al nombre usado en STL
40  typedef const value_type& const_reference;
41  /// Tipo del tamaño de un objeto, similar al nombre usado en STL
42  typedef unsigned size_type;
43 public:
44  Matrix_Sparse(unsigned m = 1, unsigned n = 1);
45  Matrix_Sparse(const Matrix_Sparse& o); ///< Constructor de copia
46  /// Matriz escalar de valor \c V.
47  Matrix_Sparse(const value_type V) : m_capacity(0) { reSize(1,1); (*this)(0,0) = V; }
49 public:
50  unsigned rows() const { return m_rows; } ///< Cantidad de filas de la matriz
51  unsigned cols() const { return m_cols; } ///< Cantidad de columnas de la Matriz
52  unsigned size() const { return m_rows * m_cols; } ///< Cantidad de valores almacenados en la matriz
53  unsigned count() const { return size(); } ///< Cantidad de valores almacenados en la matriz
54  /// Cantidad máxima posible de valores diferentes que pueden ser almacenados en la matriz
55  size_type capacity() const { return m_capacity; }
56 public:
57  Matrix_Sparse& operator= (const Matrix_Sparse &o) { return copy(o); } ///< Sinónimo de \c this->copy(o)
58  Matrix_Sparse& copy( const Matrix_Sparse &o );
61 public:
62  /// ¿¿¿ (p == q) ???
63  friend bool operator == (const Matrix_Sparse &p, const Matrix_Sparse &q) { return p.equals(q); }
64  /// ¿¿¿ (p != q) ???
65  friend bool operator != (const Matrix_Sparse &p, const Matrix_Sparse &q) { return !(p==q); }
66  bool equals( const Matrix_Sparse & o ) const; ///< ¿¿¿ (*this==o) ???
67  /// Retorna \c true si \c "o" comparte sus valores con \c "*this"
68  bool same( const Matrix_Sparse & o ) const { return this == &o; }
69 private:
70  void add( const Matrix_Sparse & );
71  void substract( const Matrix_Sparse & );
72  void multiply( const Matrix_Sparse &, const Matrix_Sparse & );
73 public:
75  { Matrix_Sparse Res = A; Res.add(B); return Res; } ///< Retorna \c A+B
77  { Matrix_Sparse Res = A; Res.substract(B); return Res; } ///< Retorna \c A-B
79  { Matrix_Sparse Res; Res.multiply(A, B); return Res; } ///< Retorna \c A*B
80 public:
81  reference operator () (unsigned, unsigned);
82  const_reference operator () (unsigned, unsigned) const;
83 public:
84  void reSize( unsigned, unsigned);
85  void reShape(unsigned, unsigned);
86 public:
87  void setDefault(const E& same);
88  /// Valor almacenado en la mayor parte de la \c Matrix_Sparse
89  const E& getDefault() { return m_same; }
90  /// Ajusta la matriz para que pueda almacenar \c n valores diferentes a \c getDefault().
91  void reserve(size_type _Count);
92  void reSize(unsigned newsize);
93  void clear(); ///< Borra todos los valores de la \c Matrix_Sparse
94 
95  template<class T> friend bool check_ok( const Matrix_Sparse<T>& M );
96  template<class T> friend class test_Matrix_Sparse; ///< Datos de prueba para la clase
97 private:
98  unsigned* m_I; ///< Indice "i" de \c M(i,j) <code>0 <= i < m_capacity</code>
99  unsigned* m_J; ///< Indice "j" de \c M(i,j) <code>0 <= i < m_capacity</code>
100  E * m_val; ///< Valor para \c M(i,j) <code>0 <= i < m_capacity</code>
101  unsigned m_size; ///< Cantidad de valores insertados en los 3 vectores paralelos
102  unsigned m_capacity; ///< Tamaño de los 3 vectores paralelos
103  unsigned m_rows; ///< Cantidad de filas de la matriz
104  unsigned m_cols; ///< Cantidad de columnas de la matris
105  E m_same; ///< Valor almacenado en la mayor parte de la \c Matrix_Sparse
106 }; // Matrix_Sparse
107 
108 /** Verifica la invariante de la clase.
109  - El campo \c m_same indica cuál es el valor que se repite más en toda la matriz.
110  - Usualmente \c same es el neutro aditivo \c value_type().
111  - No existe un constructor explícito para darle a \c m_same su valor inicial, que
112  es siempre inicializado en \c value_type(). Para cambiarlo es necesario invocar
113  el método \c setgetDefault().
114  - Los vectores \c m_I[], \c m_J[] y \c m_val[] son vectores paralelos, todos de
115  longitud \c Matrix_Sparse::m_capacity.
116  - La cantidad máxima de valores diferente que pueden ser almacenados en la matriz
117  es \c Matrix_Sparse::m_capacity.
118  - El largo de estos vectores aumenta cuando se hace referencia a un valor M(i,j)
119  mediante la versión que no es \c const del \c operator()(i,j). O sea, que es
120  ese método el encargado de agregar valores en \c m_val[], pues el operador
121  homónimo \c const operator()(i,j) nunca agrega nada y, como es \c const, en
122  general retorna una referencia constante a \c m_same.
123  - Es posible que la matriz tenga dimensiones nulas, lo que implica que todos los
124  punteros a los vectors paralelos deben ser nulos. Este hecho se marca dándolo
125  el valor \c 0 (cero) al campo \c m_capacity.
126  - En todos los algoritmos, "m" o "m_rows" es la cantidad de filas == \c rows()
127  - En todos los algoritmos, "n" o "m_cols" es la cantidad de columnas == \c cols()
128 
129  \par <em>Rep</em> Modelo de la clase
130 \code
131  ____________________________________
132  / m_capacity \
133  +---+---+---+---+---+---+-..-+---+---+ 0 1 2 3 4 5 6
134  m_I--->| 1 | 3 | 3 |'-'| ... ... |'-'| 0 / - - - - - - - \
135  +---+---+---+---+ ... ... +---+ 1 | - a - - - - - |
136  m_J--->| 1 | 2 | 1 |'-'| ... ... |'-'| 2 | - - - - - - - |
137  +---+---+---+---+ ... ... +---+ 3 | - c b - - - - |
138 m_val-->|'a'|'b'|'c'|'-'| ... ... |'-'| 4 \ - - - - - - - /
139  +---+---+---+---+---+---+-..-+---+---+
140  0 1 2 |
141  m_size--------+ == 3 m_same == '-' m_rows == 5 m_cols == 7
142 \endcode
143  - http://www.di-mare.com/adolfo/binder/c03.htm#k1-Rep
144  \remark
145  Libera al programador de implementar el método \c Ok()
146  - http://www.di-mare.com/adolfo/binder/c04.htm#sc11
147 */
148 template<class T>
149 bool check_ok( const Matrix_Sparse<T>& M ) {
150  if ( M.m_capacity == 0 ) { // m_capacity es el "marcador" que determina el valor de los demás
151  if ( M.m_I != 0 ) {
152  return false; /// - Invariante: <code>(m_capacity == 0) <==> (m_I == 0)</code>
153  }
154  if ( M.m_J != 0 ) {
155  return false; /// - Invariante: <code>(m_capacity == 0) <==> (m_J == 0)</code>
156  }
157  if ( M.m_val != 0 ) {
158  return false; /// - Invariante: <code>(m_capacity == 0) <==> (m_val == 0)</code>
159  }
160  }
161  else {
162  if ( M.m_rows == 0 ) {
163  return false; /// - Invariante: <code>(m_rows == 0) ==> (m_capacity == 0)</code>
164  }
165  if ( M.m_cols == 0 ) {
166  return false; /// - Invariante: <code>(m_cols == 0) ==> (m_capacity == 0)</code>
167  }
168  if ( M.m_I == 0 ) {
169  return false; /// - Invariante: <code>(m_capacity != 0) <==> (m_I != 0)</code>
170  }
171  if ( M.m_J == 0 ) {
172  return false; /// - Invariante: <code>(m_capacity != 0) <==> (m_J != 0)</code>
173  }
174  if ( M.m_val == 0 ) {
175  return false; /// - Invariante: <code>(m_capacity != 0) <==> (m_val != 0)</code>
176  }
177  }
178 
179  if (M.m_rows == 0 || M.m_cols == 0) {
180  if (M.m_rows == 0 && M.m_cols == 0) {
181  // OK ==> los 2 son nulos
182  }
183  else {
184  return false; /// - Invariante: <code>(m_rows == 0) <==> (m_cols == 0)</code>
185  }
186  }
187 
188  if ( M.m_size > M.m_capacity ) {
189  return false; /// - Invariante: <code>( m_size <= m_capacity )</code>
190  }
191  if ( ! check_ok (M.m_same) ) {
192  return false; /// - Invariante: <code>check_ok (m_same)</code>
193  }
194  for (unsigned k=0; k<M.m_size; ++k) {
195  if ( ! ( (0<=M.m_I[k]) && (M.m_I[k]<M.m_rows) ) ) {
196  return false; /// - Invariante: <code>( (0<=m_I[k]) && (m_I[k] < m_rows) ) k = [0..m_size-1]</code>
197  }
198  if ( ! ( (0<=M.m_J[k]) && (M.m_J[k]<M.m_cols) ) ) {
199  return false; /// - Invariante: <code>( (0<=m_J[k]) && (m_J[k] < m_cols) ) k = [0..m_size-1]</code>
200  }
201  if ( ! check_ok( M.m_val[k] ) ) {
202  return false; /// - Invariante: <code>check_ok( m_val[k] )</code>
203  }
204  }
205  return true;
206 }
207 
208 /// Define el escalar que por defecto está en todas las entradas de la \c Matrix_Sparse.
209 /// - Si <code>same != getDefault()</code> la matriz queda vacía.
210 /// - De lo contrario, nada ocurre.
211 template<class E>
212 inline void Matrix_Sparse<E>::setDefault(const E& same) {
213  if ( m_same != same ) {
214  m_same = same;
215  m_size = 0;
216  }
217 }
218 /** \fn template <class E>inline Matrix_Sparse<E>::Matrix_Sparse(const value_type V);
219 
220  \brief Constructor a partir de \c Matrix_Sparse<E>::value_type(V).
221 
222  - La matriz resultante es una matriz escalar, de dimensiones 1x1,
223  y su valor es \c "V"
224 */
225 
226 /** Constructor de vector.
227  - Obtiene suficiente memoria dinámica para almacenas los
228  <code> n * m </code> valores de la matriz.
229  - Si \c "value_type" tiene un constructor de vector, lo
230  usar para inicializar cada uno de los valores de la matriz;
231  de lo contrario, los deja tal cual están en la memoria.
232  - Si \c "value_type" es uno de los tipos escalares básicos,
233  como lo son \c int o \c float, los valores almacenados
234  en la matriz quedan tal cual están y no son inicializados.
235  \pre
236  - <code> m * n > 0 </code>
237  - <code> (m > 0) && (n > 0) </code>
238 */
239 template <class E>
240 inline Matrix_Sparse<E>::Matrix_Sparse(unsigned m, unsigned n) : m_same() {
241  if (m == 0 || n == 0) {
242  m_rows = m_cols = 0;
243  m_val = 0;
244  m_capacity = 0;
245  } else {
246  m_rows = m;
247  m_cols = n;
248 
249  m_capacity = 16; // pues 16 == 2*2*2*2 ...
250  m_I = new size_type [m_capacity];
251  m_J = new size_type [m_capacity];
252  m_val = new value_type[m_capacity];
253  }
254 
255  m_size = 0;
256 // m_same = E(); // Usa el número "cero" como neutro tipo "E"
257 }
258 
259 template <class E>
261  m_capacity = 0; // m_capacity==0 indica que NO se está usando memoria dinámica
262  copy( o ); // assert( this != &o );
263  return; // ... pues ya "o" existe y se está usando para incializar a "*this"
264 /* NOTA
265  Cuando un objeto usa memoria dinámica, copiarlo es un proceso diferente a
266  inicializarlo a partir de otro valor de su misma clase. En otras palabras,
267  el trabajo que hace el constructor CLS::CLS( const CLS& ) es muy diferente
268  al que hace el copiador CLS& operator=( const CLS & ).
269 
270  El truco de programación usado en en esta implementación consiste en "marcar"
271  el valor "m_capacity" para saber si se ha obtenido o no memoria dinámica
272  para los vectores paralelos. La implementación de copy() está hecha de manera
273  que si "m_capacity" es un puntero nulo, en copy() se inicializan correctamente
274  todos los del Rep de Matrix_Sparse. Eso explica por qué la implementación de
275  copy() es un tanto más elaborada que lo que a primera vista pareciera que es
276  necesario.
277 */
278 }
279 
280 /// Destructor
281 template <class E>
283  if (m_capacity != 0) { // sólo devuelve la memoria dinámica que sí ha adquirido
284  delete [] m_I;
285  delete [] m_J; // Retorna la memoria dinámica en uso
286  delete [] m_val;
287  }
288 }
289 
290 template <class E>
291 bool Matrix_Sparse<E>::equals( const Matrix_Sparse & o ) const {
292  if ( this == & o ) {
293  return true;
294  }
295  if (rows() != o.rows() || cols() != o.cols()) {
296  return false;
297  }
298 
299  for (unsigned i=0; i<rows(); i++) {
300  for (unsigned j=0; j<cols(); j++) {
301  if ( (*this)(i,j) != o(i,j) ) {
302  return false;
303  }
304  }
305  }
306  return true;
307 }
308 
309 /** Copia desde \c "o".
310  - Copia todo el valor de \c "o" sobre \c "*this", de forma que el nuevo valor de
311  \c "*this" sea un duplicado exacto del valor de \c "o".
312  - El valor anterior de \c "*this" se pierde.
313  - El objeto \c "o" mantiene su valor anterior.
314  - Luego de la copia, cuando el valor de \c "o" cambia, el de \c "*this" no cambiará,
315  y viceversa, pues la copia es una copia profunda; no es superficial.
316  - Si \c "*this" es \c "o" entonces su valor no cambia.
317  - Después de esta operación siempre ocurre que <code> *this == o </code>.
318 
319  \par Complejidad:
320  O( <code> rows() * cols() </code> )
321 
322  \returns *this
323  \see http://www.di-mare.com/adolfo/binder/c04.htm#sc05
324 */
325 template <class E>
327  if (this == &o) { // evita auto-borrado
328  return *this;
329  }
330  if (o.m_capacity == 0) {
331  if (m_capacity != 0) { // Como copy() puede ser invocado cuando el Rep
332  delete [] m_val; // NO ha sido inicializado, en esta implementación
333  delete [] m_J; // hay que tener cuidado de no usar los otros campos
334  delete [] m_I; // del Rep antes de darles valor.
335  } // - "m_capacity" SI debe tener su valor correcto.
336  m_rows = m_cols = 0;
337  m_val = 0;
338  m_same = o.m_same;
339  m_size = 0; // assert( o.m_size == 0 );
340  m_capacity = 0; // assert( o.m_capacity == 0 );
341  return *this;
342  }
343 
344  // se asegura de que las dos matrices sean del mismo tamaño
345  if (m_capacity != o.m_capacity) { // truco para evitar borrar la memoria dinámica
346  if (m_capacity != 0) { // sólo devuelve la memoria dinámica que sí ha adquirido
347  delete [] m_val;
348  delete [] m_J;
349  delete [] m_I;
350  }
351 
352  m_capacity = o.m_capacity;
353  m_I = new size_type [m_capacity];
354  m_J = new size_type [m_capacity];
355  m_val = new value_type[m_capacity];
356  }
357  m_same = o.m_same;
358  m_size = o.m_size;
359 
360  // como las matrices son del mismo tamaño,
361  // basta copiarlas entrada por entrada.
362  m_rows = o.m_rows;
363  m_cols = o.m_cols;
364  for (unsigned k=0; k<m_size; ++k) {
365  m_I[k] = o.m_I[k];
366  m_J[k] = o.m_J[k];
367  m_val[k] = o.m_val[k];
368  }
369  return *this;
370 }
371 
372 /** Traslada el valor de \c "o" a \c "*this".
373  - El valor anterior de \c "*this" se pierde.
374  - El nuevo valor de \c "*this" es el que \c "o" tuvo.
375  - \c "o" queda en el estado en que lo dejaría \c Erase().
376  - Si \c "*this" es \c "o" entonces su valor no cambia.
377  - En general, después de esta operación casi
378  nunca ocurre que <code> (*this == o) </code>
379 
380  \par Complejidad:
381  O( <code> rows() * cols() </code> )
382 
383  \returns \c *this
384 
385  \see http://www.di-mare.com/adolfo/binder/c04.htm#sc07
386 */
387 template <class E>
389  if (this == &o) { // evita auto-borrado
390  return *this;
391  } else if (o.m_val == 0) {
392  if (m_val != 0) {
393  delete [] m_val;
394  }
395  m_rows = m_cols = 0;
396  m_val = 0;
397  return *this;
398  } else if ( m_val != 0 ) {
399  delete [] m_val;
400  }
401  m_val = o.m_val;
402  m_rows = o.m_rows;
403  m_cols = o.m_cols;
404 
405  o.m_val = 0;
406  o.m_rows = o.m_cols = 0;
407  return *this;
408 }
409 
410 /** Intercambia los valores de \c "*this" y \c "o".
411  - Debido a que algunos métodos retornan copias del valor de \c "*this" en
412  lugar de una referencia, como ocurre con \c Matrix_Sparse::Child(), a veces
413  \c swap() no tiene el resultado esperado por el programador.
414  - Por ejemplo, si se invoca <code> T.Child(i). swap( T.Child(j) ) </code>
415  el resultado no es intercambiar los hijos, sino más bien intercambiar
416  los valores de los sub-árboles temporales \c T.Child(i) y \c T.Child(j).
417  La forma correcta de intercambiar hijos es usar \c Graft().
418 
419  \par Complejidad:
420  O( \c 1 )
421 
422  \returns *this
423 
424  \see http://www.di-mare.com/adolfo/binder/c04.htm#sc08
425 */
426 template <class E>
428  std::swap( this->m_I , o.m_I );
429  std::swap( this->m_J , o.m_J );
430  std::swap( this->m_val , o.m_val );
431  std::swap( this->m_size , o.m_size );
432  std::swap( this->m_capacity , o.m_capacity );
433  std::swap( this->m_rows , o.m_rows );
434  std::swap( this->m_cols , o.m_cols );
435  std::swap( this->m_same , o.m_same );
436  return *this;
437 }
438 
439 /** Le cambia las dimensiones a la matriz.
440  - En algunos casos los valores almacenados en la matriz no quedan
441  todos iguales a \c Matrix_Sparse<E>::value_type().
442  \pre <code> (m > 0) && (n > 0) </code>
443 */
444 template <class E>
445 void Matrix_Sparse<E>::reSize(unsigned m, unsigned n) {
446  // NO hace falta cambiar m_capacity porque lo único que está cambiando
447  // el la dimensión de la matriz
448  if (m != m_rows || n != m_cols) {
449  m_size = 0; // desecha todos los valores anteriores
450  m_rows = m; // cambia las dimensiones de la matriz
451  m_cols = n;
452  }
453 
454  if (m==0 || n==0) {
455  m_rows = 0;
456  m_cols = 0;
457  m_size = 0;
458  if (m_capacity != 0) {
459  m_capacity = 0; // todo esto mantiene la invariante de la clase
460  delete [] m_I; m_I = 0;
461  delete [] m_J; m_J = 0;
462  delete [] m_val; m_val = 0;
463  }
464  }
465  return;
466 
467 #if 0
468 /* NOTA
469  Esta es la antigua especificación de reSize(). Es incorrecta
470  porque presume que el Rep de la matriz es un vector denso en
471  donde están almacenados todos los valores de la matriz:
472 
473  +----------------------------------------------------------+
474  | reSize(): Le cambia las dimensiones a la matriz. |
475  | ======== |
476  | - Si ocurre que (m*n) == rows() * cols() los valores de |
477  | la matriz se mantienen, aunque cambian sus dimensiones.|
478  | - Si (m*n) != rows() * cols() los valores de la matriz |
479  | quedarán inicializados de la misma forma en que los |
480  | inicializaría CERO == Matrix_Sparse<E>::value_type(). |
481  | |
482  | \pre (m > 0) && (n > 0) |
483  +----------------------------------------------------------+
484 
485  En la actual especificación, que ya está corregida, no queda
486  implícita la presunción sobre cómo está organizada internamente
487  la matriz. Por eso, esta nueva especificación sí sirve para una
488  matriz implementada con un vector denso de valores, o para la
489  matriz implementada como una matriz rala.
490 
491  Estos pequeños detalles en algunas ocasiones surgen cuando el
492  programador de una clase introduce mejoras o modificaciones, pues
493  muchas veces es muy difícil o prácticamente imposible predecir
494  todos los pormenores y detalles de una especificación o de una
495  implementación.
496 */
497 
498 /* NOTA
499  Esta es la imnplementación anterior, que debe reacomodar los ínices
500  (i,j) de aquellos valores almacenados en los vectores paralalos para
501  simular que la matriz rala en realidad está almacenada como una
502  matriz densa, dentro de un vector.
503  - Al modificar la especificación de para reSize() ya no hace falta
504  hacer todo este trabajo.
505 
506  NO hace falta cambiar m_capacity porque lo único que está cambiando
507  el la dimensión de la matriz
508 */
509 
510 /* Nota para esta implementación:
511  Este método funciona de una forma similar a reSize() para la matriz implementada con
512  un vector. Para lograr que las clases Matrix<E> y Matrix_Sparse<E> tengan la misma
513  funcionalidad, esta implementación reacomoda los índices de la matriz de manera que
514  las m_rows*m_cols entradas queden reacomodadas como si la implementación usara un
515  vector de dimension m*n. Sin embargo, lo lógico sería eliminar todos los valores
516  de la matriz trocando el ciclo "for(;k;){}" por un eficiente "m_size=0;"
517  - Esto muestra que una especificación que aparenta ser "amplia", como lo es la de
518  Matrix<E>::reSize(n,m), en realidad se queda "corta" si se toma en cuenta que la
519  misma especificación debe servir para varias implementaciones diferentes.
520  - Además, muestra que algunas operaciones sólo tienen sentido para una implementación
521  específica, como ocurre con las operaciones Matrix_Sparse<E>>::getDefault() y su
522  "seteador" Matrix_Sparse<E>>::setgetDefault().
523 */
524  if (m * n == m_rows * m_cols) {
525  m_size = 0; // desecha todos los valores anteriores
526  }
527  else {
528  unsigned row = 0, col = 0;
529  for (unsigned k=0; k<m_size; ++k) {
530  // M(i,j) <==> m_val[ (i * m_cols) + j ] ; // si almacena los valores por filas
531  // M(i,j) <==> m_val[ i + (j * m_rows) ] ; // si almacena los valores por columnas
532 
533  unsigned lineal = (m_I[k] * m_cols) + m_J[k]; // por filas
534  // unsigned lineal = m_I[k] + (m_j[k] * m_rows); // por columnas
535  m_I[k] = lineal / n; // lineal % m;
536  m_J[k] = lineal % n; // lineal / m;
537  }
538  }
539  m_rows = m; // cambia las dimensiones de la matriz
540  m_cols = n;
541 
542 #endif
543 }
544 
545 /** Le ajusta las dimensiones a la matriz.
546  - Si ocurre que <code> (m*n) == rows()*cols() </code> hace
547  lo mismo que haría \c reSize(m,n).
548  - En caso contrario, no hace nada.
549 */
550 template <class E>
551 inline void Matrix_Sparse<E>::reShape(unsigned m, unsigned n) {
552  if ( m * n == m_rows * m_cols ) {
553  reSize(n,m);
554  }
555 }
556 
557 /// Retorna una referencia al elemento [i,j] de la matriz ( \c const ).
558 /// - \c M(i,j) significa lo que en arreglos se denota con \c M[i][j].
559 /// - <code>val = M(i,j); // M(i,j) es un "rvalue" (const)</code>
560 template <class E>
561 inline const E& Matrix_Sparse<E>::operator () (unsigned i, unsigned j) const {
562  assert( "Matrix_Sparse<E>::operator()()" && (i < rows()) );
563  assert( "Matrix_Sparse<E>::operator()()" && (j < cols()) );
564 
565  for (unsigned k=0; k<m_size; k++) {
566  if ( m_I[k] == i ) {
567  if ( m_J[k] == j ) {
568  return m_val[k];
569  }
570  }
571  }
572  return m_same;
573 /* NOTA
574  Como este método es "const", de antemano se sabe que el programador no puede
575  usarlo para modificar el valor de la matriz. Por eso, aunque el valor
576  retornado sea una referencia a valor común por defecto m_same, de antemano
577  el compilador asegura que ese valor no será modificado.
578 
579  Sin embargo, cuando el programador usa el método homónimo operator()(i,j)
580  que no es "const", es posible que el valor retornado sí sea modificado.
581  En ese caso, ya no es correcto retornar una referencia al valor común "m_same".
582  - Por eso, cuando se usa el hace referencia en el otro operator()(i,j) es
583  necesario agregar una entrada en los vectores paralelos en aquellos casos
584  en que no existe un valor diferente a "m_same" para (i,j).
585  - Esto quiere decir que sí es posible que al utilizar la versión modificable
586  de operator()(i,j) quede en el vector "m_val[]" un valor que es igual a
587  "m_same". En el caso peor, podría ocurrir que todos los valores almacenados
588  en el vector "m_val[]" sean todos iguales a "m_same".
589  - Una forma de corregir esta anomalía es "revisar después" si existe un valor
590  en el vector "m_val[]" que es igual a "m_same". Una forma eficiente de
591  hacerlo es mantener el el Rep un puntero "m_last_change" que apunte al
592  último valor "m_val[]" que la versión modificable de operator()(i,j) retornó.
593  En la siguiente invocación a operator()(i,j), se puede verificar si hubo un
594  ese valor anterior fue cambiado de manera que tiene almacenado "m_same".
595 */
596 #if 0
597  // Este código podría ser agregado al principio de operator()(i,j)
598  if (m_last_change != 0) {
599  if ( *m_last_change == m_same ) { // el último uso de op()(i,j) dejó "m_same"
600  if ( m_size == 1 ) { // Elimina los vectores viejos
601  delete [] m_I; m_I = 0;
602  delete [] m_J; m_J = 0;
603  delete [] m_val; m_val = 0;
604  m_capacity = 0;
605  m_size = 0;
606  }
607  else { // intercambia este valor con el último
608  m_size--;
609  unsigned k = (m_last_change - m_val); // índice de "* m_last_change"
610  *m_last_change = m_val[m_size];
611  m_I[k] = m_I[m_size];
612  m_J[k] = m_J[m_size];
613  }
614  }
615  m_last_change = 0;
616  }
617 #endif
618 }
619 /// Retorna una referencia al elemento [i,j] de la matriz.
620 /// - \c M(i,j) significa lo que en arreglos se denota con \c M[i][j].
621 /// - <code>M(i,j) = val; // M(i,j) es un "lvalue" (modificable)</code>
622 template <class E>
623 inline E& Matrix_Sparse<E>::operator() (unsigned i, unsigned j) {
624  assert( "Matrix_Sparse<E>::operator()()" && (i < rows()) );
625  assert( "Matrix_Sparse<E>::operator()()" && (j < cols()) );
626 
627  // Busca al elemento (i,j) en los vectores paralelos
628  for (unsigned k=0; k<m_size; k++) {
629  if ( m_I[k] == i ) {
630  if ( m_J[k] == j ) {
631  // m_last_change = & m_val[k];
632  return m_val[k];
633  }
634  }
635  }
636 
637  assert( (m_size <= m_capacity) && " => Agotado m_val[] Matrix_Sparse<E>::operator()()" );
638  if (m_size == m_capacity) {
639  unsigned new_capacity = m_capacity;
640  if (m_capacity % 16 == 0) {
641  new_capacity += 16;
642  }
643  else {
644  new_capacity /= 16; // Hace que el nuevo tamaño sea divisible por 16
645  new_capacity *= 16;
646  new_capacity += 16;
647  }
648  reSize( new_capacity ); // Agrega 16 porque 16 == 2*2*2*2 ...
649  }
650  // Agrega un nuevo valor modificable en los vectores paralelos
651  m_I[m_size] = i;
652  m_J[m_size] = j;
653  m_val[m_size] = m_same;
654 // m_last_change = & m_val[m_size];
655  return m_val[m_size++];
656 }
657 
658 /// Le cambia el tamaño máximo posible a la matriz.
659 /// - Le aumenta la cantidad de valores diferentes a \c getDefault().
660 /// - No hace nada cuando <code>size() < newsize</code>.
661 template <class E>
662 void Matrix_Sparse<E>::reSize(unsigned newsize) {
663  if ( newsize < m_size ) { // hay más valores en uso que "newsize"
664  // assert((m_size < newsize) && "=>Matrix_Sparse<E>::reSize()" );
665  return;
666  }
667  unsigned * new_I = new unsigned [ newsize ]; // Obtiene los vectores nuevos
668  unsigned * new_J = new unsigned [ newsize ];
669  E * new_val = new E [ newsize ];
670  if (m_capacity > 0) { // Copia los valores en uso
671  for (unsigned k=0; k<m_size; ++k) {
672  new_I[k] = m_I[k];
673  new_J[k] = m_J[k];
674  new_val[k] = m_val[k];
675  }
676  delete [] m_I; // Elimina los vectores viejos
677  delete [] m_J;
678  delete [] m_val;
679  }
680  m_I = new_I; // Instala los vectores nuevos
681  m_J = new_J;
682  m_val = new_val;
683  m_capacity = newsize;
684 }
685 
686 /** Le suma a \c "*this" la matriz \c "O".
687  \pre
688  - \c "*this" y \c "O" deben tener las mismas dimensiones
689  - <code> rows() == O.rows() && cols() == O.cols() </code>
690 
691  \par Complejidad:
692  O( <code> rows() * cols() </code> )
693 
694  \remarks
695  - Esta es la implementación de Matrix_Sparse<E> operator+( Matrix_Sparse<E>&, Matrix_Sparse<E> )
696  - El compilador tiene problemas en compilar un función amiga (<em>"friend"</em>)
697  definida con plantillas si esa función amiga no está definida (implementada)
698  dentro de la declaración de la clase. Para solventar esta deficiencia existe
699  este método que realiza el trabajo, aunque es poco cómodo de usar.
700 */
701 template <class E>
703  // verifica que las dos matrices sean del mismo tamaño
704  assert( "Matrix_Sparse<E>::add()" && (rows() == O.rows()) && (cols() == O.cols()) );
705 
706  // crea una nueva matriz que va a ser la que se devuelve
707  reSize(O.m_rows, O.m_cols);
708 
709  // Como las matrices son del mismo tamaño basta sumarlas entrada por entrada.
710 
711  value_type *pThis = m_val;
712  value_type *pO = & O.m_val[0];
713  value_type *pEND = &m_val[m_cols * m_rows];
714  for ( ; pThis != pEND; ++pThis, ++pO) {
715  *pThis += *pO;
716  }
717  return;
718 }
719 
720 /** Le resta a \c "*this" la matriz \c "O".
721  \pre
722  - \c "*this" y \c "O" deben tener las mismas dimensiones
723  - <code> rows() == O.rows() && cols() == O.cols() </code>
724 
725  \par Complejidad:
726  O( <code> rows() * cols() </code> )
727 
728  \remarks
729  - Esta es la implementación de Matrix_Sparse<E> operator-( Matrix_Sparse<E>&, Matrix_Sparse<E> )
730  - El compilador tiene problemas en compilar un función amiga (<em>"friend"</em>)
731  definida con plantillas si esa función amiga no está definida (implementada)
732  dentro de la declaración de la clase. Para solventar esta deficiencia existe
733  este método que realiza el trabajo, aunque es poco cómodo de usar.
734 */
735 template <class E>
737  // verifica que las dos matrices sean del mismo tamaño
738  assert( "Matrix_Sparse<E>::substract()" && (rows() == O.rows()) && (cols() == O.cols()) );
739 
740  // crea una nueva matriz que va a ser la que se devuelve
741  reSize(O.m_rows, O.m_cols);
742 
743  // Como las matrices son del mismo tamaño basta sumarlas entrada por entrada.
744 
745  value_type *pThis = m_val;
746  value_type *pO = & O.m_val[0];
747  value_type *pEND = &m_val[m_cols * m_rows];
748  for ( ; pThis != pEND; ++pThis, ++pO) {
749  *pThis -= *pO;
750  }
751  return;
752 }
753 
754 /** Calcula la multiplicación <code> A * B </code> y la almacena en \c "*this".
755  - Las dimensiones de \c "*this" se ajustan de manera que:
756  - <code> rows() == A.rows() && cols() == B.cols()</code>
757 
758  \pre
759  - \c "A" y \c "B" deben tener dimensiones compatibles
760  - <code> A.cols() == B.rows() </code>
761  - La multiplicación se hace [Fila x Columna], lo que implica que la cantidad
762  de valores en la filas de \c "A" debe ser igual a la cantidad de columnas de \c "B"
763 
764  \par Complejidad:
765  O( <code> A.cols() * B.cols() * A.cols() * A.capacity() * B.capacity() </code> )
766 
767  \remarks
768  - Esta es la implementación de Matrix_Sparse<E> operator*( Matrix_Sparse<E>&, Matrix_Sparse<E> )
769  - El compilador tiene problemas en compilar un función amiga (<em>"friend"</em>)
770  definida con plantillas si esa función amiga no está definida (implementada)
771  dentro de la declaración de la clase. Para solventar esta deficiencia existe
772  este método que realiza el trabajo, aunque es poco cómodo de usar.
773 */
774 template <class E>
776  // Verifica que las matrices se puedan multiplicar
777  assert( (A.cols() == B.rows()) && " => Matrix_Sparse<E>::multiply()" );
778 
779  reSize( A.rows(), B.cols() );
780  value_type sum;
781  for (unsigned i=0; i<rows(); i++) {
782  for (unsigned j=0; j<cols(); j++) {
783  sum = value_type(); // sum = E(0);
784  for (unsigned k=0; k<A.cols(); k++) {
785  sum = sum + A(i,k) * B(k,j);
786  }
787  // this->(i,j) = sum; // produce un error de compilación
788  // this->operator()(i,j) = sum; // también funciona
789  (*this)(i,j) = sum; // también funciona
790  }
791  }
792  return;
793 }
794 
795 /// Graba en el flujo \c COUT el valor de \c M[][].
796 template <class E>
797 std::ostream& operator<<(std::ostream& COUT, const Matrix_Sparse<E>& M) {
798  COUT << '[' << M.rows() << 'x' << M.cols() << ']' << std::endl;
799  for (unsigned i=0; i < M.rows(); ++i) {
800  for (unsigned j=0; j < M.cols(); ++j) {
801  COUT << " " << M(i,j);
802  }
803  COUT << std::endl;
804  }
805  return COUT;
806 }
807 
808 /// Obtiene del flujo \c CIN el valor para \c M[][].
809 template <class E>
810 std::istream& operator>>(std::istream& CIN, Matrix_Sparse<E>& M) {
811  assert( "This code has not been tested" );
812  unsigned rows,cols;
813  CIN >> rows >> cols;
814  M.reSize(rows,cols);
815  for (unsigned i=0; i<rows; i++) {
816  for (unsigned j=0; j<cols; j++) {
817  CIN >> M(i,j);
818  }
819  }
820  return CIN;
821 }
822 
823 } // namespace Mx
824 
825 // Este [horrible] truco permite "compartir" el mismo archivo Matrix_Lib.h
826 // entre Matrix.h y Matrix_Sparse.h
827 // #define Matrix Matrix_Sparse
828 // #include "Matrix_Lib.h"
829 // #undef Matrix
830 
831 #include "Matrix_Lib.h"
832 
833 #endif // Matrix_Sparse_h
834 // EOF: Matrix_Sparse.h
void substract(const Matrix_Sparse &)
Le resta a &quot;*this&quot; la matriz &quot;O&quot;.
unsigned cols() const
Cantidad de columnas de la Matriz.
Definition: Matrix_Sparse.h:51
friend Matrix_Sparse operator+(const Matrix_Sparse &A, const Matrix_Sparse &B)
Retorna A+B.
Definition: Matrix_Sparse.h:74
reference operator()(unsigned, unsigned)
Retorna una referencia al elemento [i,j] de la matriz.
friend Matrix_Sparse operator-(const Matrix_Sparse &A, const Matrix_Sparse &B)
Retorna A-B.
Definition: Matrix_Sparse.h:76
unsigned m_rows
Cantidad de filas de la matriz.
const value_type & const_reference
Tipo del objeto almacenado, similar al nombre usado en STL.
Definition: Matrix_Sparse.h:40
Matrix_Sparse(unsigned m=1, unsigned n=1)
Constructor de vector.
void setDefault(const E &same)
Define el escalar que por defecto está en todas las entradas de la Matrix_Sparse. ...
Matrix_Sparse(const value_type V)
Matriz escalar de valor V.
Definition: Matrix_Sparse.h:47
Funciones para manipular Matrix_BASE&lt;&gt;.
void reserve(size_type _Count)
Ajusta la matriz para que pueda almacenar n valores diferentes a getDefault().
~Matrix_Sparse()
Destructor.
std::istream & operator>>(std::istream &CIN, Matrix< E > &M)
Obtiene del flujo CIN el valor para M[][].
Definition: Matrix.h:615
bool check_ok(const Matrix< T > &M)
Verifica la invariante de la clase.
Definition: Matrix.h:170
E m_same
Valor almacenado en la mayor parte de la Matrix_Sparse.
unsigned m_cols
Cantidad de columnas de la matris.
friend class test_Matrix_Sparse
Datos de prueba para la clase.
Definition: Matrix_Sparse.h:96
void clear()
Borra todos los valores de la Matrix_Sparse.
value_type & reference
Tipo del objeto almacenado, similar al nombre usado en STL.
Definition: Matrix_Sparse.h:38
Matrix_Sparse & swap(Matrix_Sparse &o)
Intercambia los valores de &quot;*this&quot; y &quot;o&quot;.
unsigned size_type
Tipo del tamaño de un objeto, similar al nombre usado en STL.
Definition: Matrix_Sparse.h:42
unsigned count() const
Cantidad de valores almacenados en la matriz.
Definition: Matrix_Sparse.h:53
unsigned m_capacity
Tamaño de los 3 vectores paralelos.
E value_type
Tipo del objeto almacenado, similar al nombre usado en STL.
Definition: Matrix_Sparse.h:36
void add(const Matrix_Sparse &)
Le suma a &quot;*this&quot; la matriz &quot;O&quot;.
bool equals(const Matrix_Sparse &o) const
¿¿¿ (*this==o) ???
unsigned * m_J
Indice &quot;j&quot; de M(i,j) 0 &lt;= i &lt; m_capacity
Definition: Matrix_Sparse.h:99
size_type capacity() const
Cantidad máxima posible de valores diferentes que pueden ser almacenados en la matriz.
Definition: Matrix_Sparse.h:55
Matrix_Sparse & move(Matrix_Sparse &o)
Traslada el valor de &quot;o&quot; a &quot;*this&quot;.
Matrix_Sparse & copy(const Matrix_Sparse &o)
Copia desde &quot;o&quot;.
unsigned size() const
Cantidad de valores almacenados en la matriz.
Definition: Matrix_Sparse.h:52
friend bool operator!=(const Matrix_Sparse &p, const Matrix_Sparse &q)
¿¿¿ (p != q) ???
Definition: Matrix_Sparse.h:65
E * m_val
Valor para M(i,j) 0 &lt;= i &lt; m_capacity
friend Matrix_Sparse operator*(const Matrix_Sparse &A, const Matrix_Sparse &B)
Retorna A*B.
Definition: Matrix_Sparse.h:78
const E & getDefault()
Valor almacenado en la mayor parte de la Matrix_Sparse.
Definition: Matrix_Sparse.h:89
unsigned * m_I
Indice &quot;i&quot; de M(i,j) 0 &lt;= i &lt; m_capacity
Definition: Matrix_Sparse.h:98
Matrix_Sparse & operator=(const Matrix_Sparse &o)
Sinónimo de this-&gt;copy(o)
Definition: Matrix_Sparse.h:57
void reSize(unsigned, unsigned)
Le cambia las dimensiones a la matriz.
void multiply(const Matrix_Sparse &, const Matrix_Sparse &)
Calcula la multiplicación A * B y la almacena en &quot;*this&quot;.
unsigned rows() const
Cantidad de filas de la matriz.
Definition: Matrix_Sparse.h:50
friend bool operator==(const Matrix_Sparse &p, const Matrix_Sparse &q)
¿¿¿ (p == q) ???
Definition: Matrix_Sparse.h:63
Esta es una clase matriz muy chirrisquitica almacenada como una matriz rala.
Definition: Matrix_Sparse.h:33
unsigned m_size
Cantidad de valores insertados en los 3 vectores paralelos.
void reShape(unsigned, unsigned)
Le ajusta las dimensiones a la matriz.
friend bool check_ok(const Matrix_Sparse< T > &M)
Verifica la invariante de la clase.
bool same(const Matrix_Sparse &o) const
Retorna true si &quot;o&quot; comparte sus valores con &quot;*this&quot;.
Definition: Matrix_Sparse.h:68