lib/CodeGen/PBQP/PBQPMath.h

   1 #ifndef LLVM_CODEGEN_PBQP_PBQPMATH_H
   2 #define LLVM_CODEGEN_PBQP_PBQPMATH_H
   3
   4 #include <cassert>
   5 #include <algorithm>
   6 #include <functional>
   7
   8 namespace PBQP {
   9
  10 typedef double PBQPNum;
  11
  12 /// \brief PBQP Vector class.
  13 class Vector {
  14   public:
  15
  16     /// \brief Construct a PBQP vector of the given size.
  17     explicit Vector(unsigned length) :
  18       length(length), data(new PBQPNum[length]) {
  19       }
  20
  21     /// \brief Construct a PBQP vector with initializer.
  22     Vector(unsigned length, PBQPNum initVal) :
  23       length(length), data(new PBQPNum[length]) {
  24         std::fill(data, data + length, initVal);
  25       }
  26
  27     /// \brief Copy construct a PBQP vector.
  28     Vector(const Vector &v) :
  29       length(v.length), data(new PBQPNum[length]) {
  30         std::copy(v.data, v.data + length, data);
  31       }
  32
  33     /// \brief Destroy this vector, return its memory.
  34     ~Vector() { delete[] data; }
  35
  36     /// \brief Assignment operator.
  37     Vector& operator=(const Vector &v) {
  38       delete[] data;
  39       length = v.length;
  40       data = new PBQPNum[length];
  41       std::copy(v.data, v.data + length, data);
  42       return *this;
  43     }
  44
  45     /// \brief Return the length of the vector
  46     unsigned getLength() const throw () {
  47       return length;
  48     }
  49
  50     /// \brief Element access.
  51     PBQPNum& operator[](unsigned index) {
  52       assert(index < length && "Vector element access out of bounds.");
  53       return data[index];
  54     }
  55
  56     /// \brief Const element access.
  57     const PBQPNum& operator[](unsigned index) const {
  58       assert(index < length && "Vector element access out of bounds.");
  59       return data[index];
  60     }
  61
  62     /// \brief Add another vector to this one.
  63     Vector& operator+=(const Vector &v) {
  64       assert(length == v.length && "Vector length mismatch.");
  65       std::transform(data, data + length, v.data, data, std::plus<PBQPNum>());
  66       return *this;
  67     }
  68
  69     /// \brief Subtract another vector from this one.
  70     Vector& operator-=(const Vector &v) {
  71       assert(length == v.length && "Vector length mismatch.");
  72       std::transform(data, data + length, v.data, data, std::minus<PBQPNum>());
  73       return *this;
  74     }
  75
  76     /// \brief Returns the index of the minimum value in this vector
  77     unsigned minIndex() const {
  78       return std::min_element(data, data + length) - data;
  79     }
  80
  81   private:
  82     unsigned length;
  83     PBQPNum *data;
  84 };
  85
  86 /// \brief Output a textual representation of the given vector on the given
  87 ///        output stream.
  88 template <typename OStream>
  89 OStream& operator<<(OStream &os, const Vector &v) {
  90   assert((v.getLength() != 0) && "Zero-length vector badness.");
  91
  92   os << "[ " << v[0];
  93   for (unsigned i = 1; i < v.getLength(); ++i) {
  94     os << ", " << v[i];
  95   }
  96   os << " ]";
  97
  98   return os;
  99 }
 100
 101
 102 /// \brief PBQP Matrix class
 103 class Matrix {
 104   public:
 105
 106     /// \brief Construct a PBQP Matrix with the given dimensions.
 107     Matrix(unsigned rows, unsigned cols) :
 108       rows(rows), cols(cols), data(new PBQPNum[rows * cols]) {
 109     }
 110
 111     /// \brief Construct a PBQP Matrix with the given dimensions and initial
 112     /// value.
 113     Matrix(unsigned rows, unsigned cols, PBQPNum initVal) :
 114       rows(rows), cols(cols), data(new PBQPNum[rows * cols]) {
 115         std::fill(data, data + (rows * cols), initVal);
 116     }
 117
 118     /// \brief Copy construct a PBQP matrix.
 119     Matrix(const Matrix &m) :
 120       rows(m.rows), cols(m.cols), data(new PBQPNum[rows * cols]) {
 121         std::copy(m.data, m.data + (rows * cols), data);
 122     }
 123
 124     /// \brief Destroy this matrix, return its memory.
 125     ~Matrix() { delete[] data; }
 126
 127     /// \brief Assignment operator.
 128     Matrix& operator=(const Matrix &m) {
 129       delete[] data;
 130       rows = m.rows; cols = m.cols;
 131       data = new PBQPNum[rows * cols];
 132       std::copy(m.data, m.data + (rows * cols), data);
 133       return *this;
 134     }
 135
 136     /// \brief Return the number of rows in this matrix.
 137     unsigned getRows() const throw () { return rows; }
 138
 139     /// \brief Return the number of cols in this matrix.
 140     unsigned getCols() const throw () { return cols; }
 141
 142     /// \brief Matrix element access.
 143     PBQPNum* operator[](unsigned r) {
 144       assert(r < rows && "Row out of bounds.");
 145       return data + (r * cols);
 146     }
 147
 148     /// \brief Matrix element access.
 149     const PBQPNum* operator[](unsigned r) const {
 150       assert(r < rows && "Row out of bounds.");
 151       return data + (r * cols);
 152     }
 153
 154     /// \brief Returns the given row as a vector.
 155     Vector getRowAsVector(unsigned r) const {
 156       Vector v(cols);
 157       for (unsigned c = 0; c < cols; ++c)
 158         v[c] = (*this)[r][c];
 159       return v;
 160     }
 161
 162     /// \brief Returns the given column as a vector.
 163     Vector getColAsVector(unsigned c) const {
 164       Vector v(rows);
 165       for (unsigned r = 0; r < rows; ++r)
 166         v[r] = (*this)[r][c];
 167       return v;
 168     }
 169
 170     /// \brief Reset the matrix to the given value.
 171     Matrix& reset(PBQPNum val = 0) {
 172       std::fill(data, data + (rows * cols), val);
 173       return *this;
 174     }
 175
 176     /// \brief Set a single row of this matrix to the given value.
 177     Matrix& setRow(unsigned r, PBQPNum val) {
 178       assert(r < rows && "Row out of bounds.");
 179       std::fill(data + (r * cols), data + ((r + 1) * cols), val);
 180       return *this;
 181     }
 182
 183     /// \brief Set a single column of this matrix to the given value.
 184     Matrix& setCol(unsigned c, PBQPNum val) {
 185       assert(c < cols && "Column out of bounds.");
 186       for (unsigned r = 0; r < rows; ++r)
 187         (*this)[r][c] = val;
 188       return *this;
 189     }
 190
 191     /// \brief Matrix transpose.
 192     Matrix transpose() const {
 193       Matrix m(cols, rows);
 194       for (unsigned r = 0; r < rows; ++r)
 195         for (unsigned c = 0; c < cols; ++c)
 196           m[c][r] = (*this)[r][c];
 197       return m;
 198     }
 199
 200     /// \brief Returns the diagonal of the matrix as a vector.
 201     ///
 202     /// Matrix must be square.
 203     Vector diagonalize() const {
 204       assert(rows == cols && "Attempt to diagonalize non-square matrix.");
 205
 206       Vector v(rows);
 207       for (unsigned r = 0; r < rows; ++r)
 208         v[r] = (*this)[r][r];
 209       return v;
 210     }
 211
 212     /// \brief Add the given matrix to this one.
 213     Matrix& operator+=(const Matrix &m) {
 214       assert(rows == m.rows && cols == m.cols &&
 215           "Matrix dimensions mismatch.");
 216       std::transform(data, data + (rows * cols), m.data, data,
 217           std::plus<PBQPNum>());
 218       return *this;
 219     }
 220
 221     /// \brief Returns the minimum of the given row
 222     PBQPNum getRowMin(unsigned r) const {
 223       assert(r < rows && "Row out of bounds");
 224       return *std::min_element(data + (r * cols), data + ((r + 1) * cols));
 225     }
 226
 227     /// \brief Returns the minimum of the given column
 228     PBQPNum getColMin(unsigned c) const {
 229       PBQPNum minElem = (*this)[0][c];
 230       for (unsigned r = 1; r < rows; ++r)
 231         if ((*this)[r][c] < minElem) minElem = (*this)[r][c];
 232       return minElem;
 233     }
 234
 235     /// \brief Subtracts the given scalar from the elements of the given row.
 236     Matrix& subFromRow(unsigned r, PBQPNum val) {
 237       assert(r < rows && "Row out of bounds");
 238       std::transform(data + (r * cols), data + ((r + 1) * cols),
 239           data + (r * cols),
 240           std::bind2nd(std::minus<PBQPNum>(), val));
 241       return *this;
 242     }
 243
 244     /// \brief Subtracts the given scalar from the elements of the given column.
 245     Matrix& subFromCol(unsigned c, PBQPNum val) {
 246       for (unsigned r = 0; r < rows; ++r)
 247         (*this)[r][c] -= val;
 248       return *this;
 249     }
 250
 251     /// \brief Returns true if this is a zero matrix.
 252     bool isZero() const {
 253       return find_if(data, data + (rows * cols),
 254           std::bind2nd(std::not_equal_to<PBQPNum>(), 0)) ==
 255         data + (rows * cols);
 256     }
 257
 258   private:
 259     unsigned rows, cols;
 260     PBQPNum *data;
 261 };
 262
 263 /// \brief Output a textual representation of the given matrix on the given
 264 ///        output stream.
 265 template <typename OStream>
 266 OStream& operator<<(OStream &os, const Matrix &m) {
 267
 268   assert((m.getRows() != 0) && "Zero-row matrix badness.");
 269
 270   for (unsigned i = 0; i < m.getRows(); ++i) {
 271     os << m.getRowAsVector(i);
 272   }
 273
 274   return os;
 275 }
 276
 277 }
 278
 279 #endif // LLVM_CODEGEN_PBQP_PBQPMATH_HPP