Math.h revision 25e9651afb26a004a9debda42da3f90234cc05e2
14d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima//===-- PBQPMath.h - PBQP Vector and Matrix classes ------------*- C++ --*-===// 24d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima// 34d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima// The LLVM Compiler Infrastructure 44d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima// 54d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima// This file is distributed under the University of Illinois Open Source 64d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima// License. See LICENSE.TXT for details. 74d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima// 84d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima//===----------------------------------------------------------------------===// 94d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima 104d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima#ifndef LLVM_CODEGEN_PBQP_PBQPMATH_H 114d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima#define LLVM_CODEGEN_PBQP_PBQPMATH_H 124d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima 134d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima#include <cassert> 144d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima#include <algorithm> 154d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima#include <functional> 164d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima 174d07f569799aaae0d7fccf8e76386d450664987fJun Nakajimanamespace PBQP { 184d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima 194d07f569799aaae0d7fccf8e76386d450664987fJun Nakajimatypedef double PBQPNum; 204d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima 214d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima/// \brief PBQP Vector class. 224d07f569799aaae0d7fccf8e76386d450664987fJun Nakajimaclass Vector { 234d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima public: 244d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima 254d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima /// \brief Construct a PBQP vector of the given size. 264d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima explicit Vector(unsigned length) : 274d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima length(length), data(new PBQPNum[length]) { 284d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima } 294d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima 304d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima /// \brief Construct a PBQP vector with initializer. 314d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima Vector(unsigned length, PBQPNum initVal) : 324d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima length(length), data(new PBQPNum[length]) { 334d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima std::fill(data, data + length, initVal); 344d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima } 354d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima 364d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima /// \brief Copy construct a PBQP vector. 374d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima Vector(const Vector &v) : 384d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima length(v.length), data(new PBQPNum[length]) { 394d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima std::copy(v.data, v.data + length, data); 404d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima } 414d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima 424d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima /// \brief Destroy this vector, return its memory. 434d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima ~Vector() { delete[] data; } 444d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima 454d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima /// \brief Assignment operator. 464d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima Vector& operator=(const Vector &v) { 474d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima delete[] data; 484d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima length = v.length; 494d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima data = new PBQPNum[length]; 504d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima std::copy(v.data, v.data + length, data); 514d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima return *this; 524d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima } 534d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima 544d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima /// \brief Return the length of the vector 554d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima unsigned getLength() const throw () { 564d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima return length; 574d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima } 584d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima 594d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima /// \brief Element access. 604d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima PBQPNum& operator[](unsigned index) { 614d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima assert(index < length && "Vector element access out of bounds."); 624d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima return data[index]; 634d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima } 644d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima 654d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima /// \brief Const element access. 664d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima const PBQPNum& operator[](unsigned index) const { 674d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima assert(index < length && "Vector element access out of bounds."); 684d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima return data[index]; 694d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima } 704d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima 714d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima /// \brief Add another vector to this one. 724d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima Vector& operator+=(const Vector &v) { 734d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima assert(length == v.length && "Vector length mismatch."); 744d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima std::transform(data, data + length, v.data, data, std::plus<PBQPNum>()); 754d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima return *this; 764d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima } 774d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima 784d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima /// \brief Subtract another vector from this one. 794d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima Vector& operator-=(const Vector &v) { 804d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima assert(length == v.length && "Vector length mismatch."); 814d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima std::transform(data, data + length, v.data, data, std::minus<PBQPNum>()); 824d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima return *this; 834d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima } 844d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima 854d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima /// \brief Returns the index of the minimum value in this vector 864d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima unsigned minIndex() const { 874d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima return std::min_element(data, data + length) - data; 884d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima } 894d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima 904d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima private: 914d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima unsigned length; 924d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima PBQPNum *data; 934d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima}; 944d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima 954d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima/// \brief Output a textual representation of the given vector on the given 964d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima/// output stream. 974d07f569799aaae0d7fccf8e76386d450664987fJun Nakajimatemplate <typename OStream> 984d07f569799aaae0d7fccf8e76386d450664987fJun NakajimaOStream& operator<<(OStream &os, const Vector &v) { 994d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima assert((v.getLength() != 0) && "Zero-length vector badness."); 1004d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima 1014d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima os << "[ " << v[0]; 1024d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima for (unsigned i = 1; i < v.getLength(); ++i) { 1034d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima os << ", " << v[i]; 1044d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima } 1054d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima os << " ]"; 1064d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima 1074d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima return os; 1084d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima} 1094d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima 1104d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima 1114d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima/// \brief PBQP Matrix class 1124d07f569799aaae0d7fccf8e76386d450664987fJun Nakajimaclass Matrix { 1134d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima public: 1144d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima 1154d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima /// \brief Construct a PBQP Matrix with the given dimensions. 1164d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima Matrix(unsigned rows, unsigned cols) : 1174d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima rows(rows), cols(cols), data(new PBQPNum[rows * cols]) { 1184d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima } 1194d07f569799aaae0d7fccf8e76386d450664987fJun Nakajima 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 throw () { return rows; } 147 148 /// \brief Return the number of cols in this matrix. 149 unsigned getCols() const throw () { 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. 274template <typename OStream> 275OStream& 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 289