1 //===------ Math.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_MATH_H 11 #define LLVM_CODEGEN_PBQP_MATH_H 12 13 #include <cassert> 14 #include <algorithm> 15 #include <functional> 16 17 namespace PBQP { 18 19 typedef float 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_MATH_H 289
