lib/CodeGen/PBQP/PBQPMath.h

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