core/library/structures/matrix.h

   1 #ifndef MATRIX_CLASS
   2 #define MATRIX_CLASS
   3
   4 /*****************************************************************************\
   5 *                                                                             *
   6 *  Name   : matrix                                                            *
   7 *  Author : Chris Koeritz                                                     *
   8 *                                                                             *
   9 *******************************************************************************
  10 * Copyright (c) 1993-$now By Author.  This program is free software; you can  *
  11 * redistribute it and/or modify it under the terms of the GNU General Public  *
  12 * License as published by the Free Software Foundation; either version 2 of   *
  13 * the License or (at your option) any later version.  This is online at:      *
  14 *     http://www.fsf.org/copyleft/gpl.html                                    *
  15 * Please send any updates to: fred@gruntose.com                               *
  16 \*****************************************************************************/
  17
  18 #include <basis/array.h>
  19 #include <basis/astring.h>
  20 #include <basis/functions.h>
  21 #include <basis/guards.h>
  22
  23 namespace structures {
  24
  25 //! Represents a two-dimensional array of objects.
  26 /*!
  27   The indices range from zero to (maximum_value - 1) for rows and columns.
  28 */
  29
  30 template <class contents>
  31 class matrix : protected basis::array<contents>
  32 {
  33 public:
  34   matrix(int rows = 0, int cols = 0, contents *data = NIL);
  35     //!< the "data" array must have at least "rows" * "cols" contents in it.
  36   matrix(const matrix &to_copy);
  37
  38   ~matrix() {}
  39
  40   int rows() const { return _rows; }
  41   int columns() const { return _cols; }
  42
  43   matrix &operator = (const matrix &to_copy);
  44
  45   contents &get(int row, int column);
  46   const contents &get(int row, int column) const;
  47     //!< retrieves the contents from the specified "row" and "column".
  48
  49   bool put(int row, int column, const contents &to_put);
  50     //!< stores "to_put" into the matrix at "row" and "column".
  51
  52   contents *operator[] (int row);
  53     //!< dangerous: indexes by "row" into the underlying contents.
  54     /*!< the result can be used as a pointer to the whole row of data, or it
  55     can be indexed into by column to find a row/column position.  this is
  56     dangerous if one is not careful about ensuring that the column used is
  57     within bounds.  if the "row" parameter is out of bounds, then NIL is
  58     returned. */
  59   const contents *operator[] (int row) const;
  60     //!< dangerous: constant peek into data for "row" in underlying contents.
  61
  62   matrix submatrix(int row, int column, int rows, int columns) const;
  63     //!< returns a submatrix of this one starting at "row" and "column".
  64     /*!< The returned matrix should contain "rows" rows and "columns" columns.
  65     if the size or position are out of bounds, an empty matrix is returned. */
  66   void submatrix(matrix &sub, int row, int column, int rows, int cols) const;
  67     //!< like submatrix() above, but stores into the "sub" parameter.
  68
  69   matrix transpose() const;
  70     //!< provides the transposed form of this matrix.
  71   void transpose(matrix &resultant) const;
  72     //!< stores the transpose of this matrix in "resultant".
  73
  74   basis::array<contents> get_row(int row);
  75     //!< return the vector at the "row", or an empty array if "row" is invalid.
  76   basis::array<contents> get_column(int column);
  77     //!< return the vector at the "column", or an empty array if it's invalid.
  78
  79   bool insert_row(int before_row);
  80     //!< inserts a row before the "before_" parameter.
  81     /*!< all existing data is preserved in the matrix, although it may get
  82     moved over depending on where it's located with respect to "before_row". */
  83   bool insert_column(int before_column);
  84     //!< inserts a column before the "before_" parameter.
  85
  86   void reset(int rows = 0, int columns = 0);
  87     //!< empties the matrix and changes its size.
  88
  89   void redimension(int new_rows, int new_columns);
  90     //!< changes the size to contain "new_rows" by "new_columns" elements.
  91     /*!< data that was held previously stays in the array as long as its row
  92     and column indices are still valid. */
  93
  94   bool zap_row(int row_to_zap);
  95   bool zap_column(int column_to_zap);
  96     //!< removes a row or column from the matrix.
  97     /*!< the matrix becomes one row or column less than before and all data
  98     from the deleted vector is lost. */
  99
 100 private:
 101   int _rows;  //!< number of rows in the matrix.
 102   int _cols;  //!< number of columns in the matrix.
 103
 104   int compute_index(int row, int column) const;
 105     //!< returns the flat index that corresponds to the "row" and "column".
 106 };
 107
 108 //////////////
 109
 110 //! A matrix of integers.
 111 class int_matrix : public matrix<int>
 112 {
 113 public:
 114   int_matrix(int rows = 0, int cols = 0, int *data = NIL)
 115       : matrix<int>(rows, cols, data) {}
 116   int_matrix(const matrix<int> &to_copy) : matrix<int>(to_copy) {}
 117 };
 118
 119 //! A matrix of strings.
 120 class string_matrix : public matrix<basis::astring>
 121 {
 122 public:
 123   string_matrix(int rows = 0, int cols = 0, basis::astring *data = NIL)
 124       : matrix<basis::astring>(rows, cols, data) {}
 125   string_matrix(const matrix<basis::astring> &to_copy) : matrix<basis::astring>(to_copy) {}
 126 };
 127
 128 //! A matrix of double floating point numbers.
 129 class double_matrix : public matrix<double>
 130 {
 131 public:
 132   double_matrix(int rows = 0, int cols = 0, double *data = NIL)
 133       : matrix<double>(rows, cols, data) {}
 134   double_matrix(const matrix<double> &to_copy) : matrix<double>(to_copy) {}
 135 };
 136
 137 //////////////
 138
 139 // implementation for longer methods...
 140
 141 //hmmm: the operations for zapping use extra memory.  they could easily
 142 //      be done as in-place copies.
 143
 144 #undef static_class_name
 145 #define static_class_name() "matrix"
 146   // used in bounds_halt macro.
 147
 148 template <class contents>
 149 matrix<contents>::matrix(int r, int c, contents *dat)
 150 : basis::array<contents>(r*c, dat), _rows(r), _cols(c) {}
 151
 152 template <class contents>
 153 matrix<contents>::matrix(const matrix<contents> &to_copy)
 154 : basis::array<contents>(0), _rows(0), _cols(0)
 155 { *this = to_copy; }
 156
 157 template <class contents>
 158 matrix<contents> &matrix<contents>::operator = (const matrix &to_copy)
 159 {
 160   if (&to_copy == this) return *this;
 161   basis::array<contents>::operator = (to_copy);
 162   _rows = to_copy._rows;
 163   _cols = to_copy._cols;
 164   return *this;
 165 }
 166
 167 template <class contents>
 168 contents *matrix<contents>::operator[] (int r)
 169 { return &basis::array<contents>::operator [] (compute_index(r, 0)); }
 170
 171 template <class contents>
 172 const contents *matrix<contents>::operator[] (int r) const
 173 { return &basis::array<contents>::operator [] (compute_index(r, 0)); }
 174
 175 template <class contents>
 176 const contents &matrix<contents>::get(int r, int c) const
 177 { return basis::array<contents>::get(compute_index(r, c)); }
 178
 179 template <class contents>
 180 contents &matrix<contents>::get(int row, int column)
 181 { return basis::array<contents>::operator [] (compute_index(row, column)); }
 182
 183 template <class contents>
 184 int matrix<contents>::compute_index(int row, int column) const
 185 { return column + row * _cols; }
 186
 187 template <class contents>
 188 void matrix<contents>::reset(int rows_in, int columns_in)
 189 {
 190   if ( (_rows == rows_in) && (_cols == columns_in) ) {
 191     // reuse space, but reset the objects to their initial state.
 192     for (int i = 0; i < basis::array<contents>::length(); i++)
 193       basis::array<contents>::operator [](i) = contents();
 194     return;
 195   }
 196
 197   _rows = 0;
 198   _cols = 0;
 199   basis::array<contents>::reset(0);
 200
 201   this->insert(0, rows_in * columns_in);
 202   _rows = rows_in;
 203   _cols = columns_in;
 204 }
 205
 206 template <class contents>
 207 void matrix<contents>::redimension(int new_rows, int new_columns)
 208 {
 209   if ( (_rows == new_rows) && (_cols == new_columns) ) return;
 210   matrix<contents> new_this(new_rows, new_columns);
 211   for (int r = 0; r < minimum(new_rows, rows()); r++)
 212     for (int c = 0; c < minimum(new_columns, columns()); c++)
 213       new_this[r][c] = (*this)[r][c];
 214   *this = new_this;
 215 }
 216
 217 template <class contents>
 218 bool matrix<contents>::put(int row, int column, const contents &to_put)
 219 {
 220   if ( (row >= rows()) || (column >= columns()) )
 221     return false;
 222   (operator [](row))[column] = to_put;
 223   return true;
 224 }
 225
 226 template <class contents>
 227 matrix<contents> matrix<contents>::submatrix(int row, int column, int rows_in,
 228     int columns_in) const
 229 {
 230   matrix<contents> to_return;
 231   submatrix(to_return, row, column, rows_in, columns_in);
 232   return to_return;
 233 }
 234
 235 template <class contents>
 236 void matrix<contents>::submatrix(matrix<contents> &sub, int row, int column,
 237     int rows_in, int columns_in) const
 238 {
 239   sub.reset();
 240   if ( (row >= rows()) || (row + rows_in >= rows()) ) return;
 241   if ( (column >= columns()) || (column + columns_in >= columns()) ) return;
 242   sub.reset(rows_in, columns_in);
 243   for (int r = row; r < row + rows_in; r++)
 244     for (int c = column; c < column + columns_in; c++)
 245       sub[r - row][c - column] = (*this)[r][c];
 246 }
 247
 248 template <class contents>
 249 matrix<contents> matrix<contents>::transpose() const
 250 {
 251   matrix<contents> to_return;
 252   transpose(to_return);
 253   return to_return;
 254 }
 255
 256 template <class contents>
 257 void matrix<contents>::transpose(matrix<contents> &resultant) const
 258 {
 259   resultant.reset(columns(), rows());
 260   for (int i = 0; i < rows(); i++)
 261     for (int j = 0; j < columns(); j++)
 262       resultant[j][i] = (*this)[i][j];
 263 }
 264
 265 template <class contents>
 266 basis::array<contents> matrix<contents>::get_row(int row)
 267 {
 268   basis::array<contents> to_return;
 269   if (row >= rows()) return to_return;
 270   to_return.reset(columns());
 271   for (int i = 0; i < columns(); i++)
 272     to_return[i] = get(row, i);
 273   return to_return;
 274 }
 275
 276 template <class contents>
 277 basis::array<contents> matrix<contents>::get_column(int column)
 278 {
 279   basis::array<contents> to_return;
 280   if (column >= columns()) return to_return;
 281   to_return.reset(rows());
 282   for (int i = 0; i < rows(); i++)
 283     to_return[i] = get(i, column);
 284   return to_return;
 285 }
 286
 287 template <class contents>
 288 bool matrix<contents>::zap_row(int row_to_zap)
 289 {
 290   FUNCDEF("zap_row");
 291   bounds_halt(row_to_zap, 0, rows() - 1, false);
 292   const int start = compute_index(row_to_zap, 0);
 293   // this is only safe because the indices are stored in row-major order (which
 294   // i hope means the right thing).  in any case, the order is like so:
 295   //   1 2 3 4
 296   //   5 6 7 8
 297   // thus we can whack a whole row contiguously.
 298   basis::array<contents>::zap(start, start + columns() - 1);
 299   _rows--;
 300   return true;
 301 }
 302
 303 template <class contents>
 304 bool matrix<contents>::zap_column(int column_to_zap)
 305 {
 306   FUNCDEF("zap_column");
 307   bounds_halt(column_to_zap, 0, columns() - 1, false);
 308   // this starts at the end, which keeps the indexes meaningful.  otherwise
 309   // the destruction interferes with finding the elements.
 310   for (int r = rows(); r >= 0; r--) {
 311     const int loc = compute_index(r, column_to_zap);
 312     basis::array<contents>::zap(loc, loc);
 313   }
 314   _cols--;
 315   return true;
 316 }
 317
 318 template <class contents>
 319 bool matrix<contents>::insert_row(int position)
 320 {
 321   FUNCDEF("insert_row");
 322   bounds_halt(position, 0, rows(), false);
 323   // see comment in zap_row for reasoning about the below.
 324   basis::array<contents>::insert(compute_index(position, 0), columns());
 325   _rows++;
 326   // clear out those spaces.
 327   for (int c = 0; c < columns(); c++)
 328     put(position, c, contents());
 329   return true;
 330 }
 331
 332 template <class contents>
 333 bool matrix<contents>::insert_column(int position)
 334 {
 335   FUNCDEF("insert_column");
 336   bounds_halt(position, 0, columns(), false);
 337   // similarly to zap_column, we must iterate in reverse.
 338   for (int r = rows(); r >= 0; r--)
 339     basis::array<contents>::insert(compute_index(r, position), 1);
 340   _cols++;
 341   // clear out those spaces.
 342   for (int r = 0; r < rows(); r++)
 343     put(r, position, contents());
 344   return true;
 345 }
 346
 347 #undef static_class_name
 348
 349 } //namespace.
 350
 351 #endif
 352