LLVM API Documentation
00001 //===-- PBQPMath.h - PBQP Vector and Matrix classes ------------*- C++ --*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 00010 #ifndef LLVM_CODEGEN_PBQP_PBQPMATH_H 00011 #define LLVM_CODEGEN_PBQP_PBQPMATH_H 00012 00013 #include <cassert> 00014 #include <algorithm> 00015 #include <functional> 00016 00017 namespace PBQP { 00018 00019 typedef double PBQPNum; 00020 00021 /// \brief PBQP Vector class. 00022 class Vector { 00023 public: 00024 00025 /// \brief Construct a PBQP vector of the given size. 00026 explicit Vector(unsigned length) : 00027 length(length), data(new PBQPNum[length]) { 00028 } 00029 00030 /// \brief Construct a PBQP vector with initializer. 00031 Vector(unsigned length, PBQPNum initVal) : 00032 length(length), data(new PBQPNum[length]) { 00033 std::fill(data, data + length, initVal); 00034 } 00035 00036 /// \brief Copy construct a PBQP vector. 00037 Vector(const Vector &v) : 00038 length(v.length), data(new PBQPNum[length]) { 00039 std::copy(v.data, v.data + length, data); 00040 } 00041 00042 /// \brief Destroy this vector, return its memory. 00043 ~Vector() { delete[] data; } 00044 00045 /// \brief Assignment operator. 00046 Vector& operator=(const Vector &v) { 00047 delete[] data; 00048 length = v.length; 00049 data = new PBQPNum[length]; 00050 std::copy(v.data, v.data + length, data); 00051 return *this; 00052 } 00053 00054 /// \brief Return the length of the vector 00055 unsigned getLength() const { 00056 return length; 00057 } 00058 00059 /// \brief Element access. 00060 PBQPNum& operator[](unsigned index) { 00061 assert(index < length && "Vector element access out of bounds."); 00062 return data[index]; 00063 } 00064 00065 /// \brief Const element access. 00066 const PBQPNum& operator[](unsigned index) const { 00067 assert(index < length && "Vector element access out of bounds."); 00068 return data[index]; 00069 } 00070 00071 /// \brief Add another vector to this one. 00072 Vector& operator+=(const Vector &v) { 00073 assert(length == v.length && "Vector length mismatch."); 00074 std::transform(data, data + length, v.data, data, std::plus<PBQPNum>()); 00075 return *this; 00076 } 00077 00078 /// \brief Subtract another vector from this one. 00079 Vector& operator-=(const Vector &v) { 00080 assert(length == v.length && "Vector length mismatch."); 00081 std::transform(data, data + length, v.data, data, std::minus<PBQPNum>()); 00082 return *this; 00083 } 00084 00085 /// \brief Returns the index of the minimum value in this vector 00086 unsigned minIndex() const { 00087 return std::min_element(data, data + length) - data; 00088 } 00089 00090 private: 00091 unsigned length; 00092 PBQPNum *data; 00093 }; 00094 00095 /// \brief Output a textual representation of the given vector on the given 00096 /// output stream. 00097 template <typename OStream> 00098 OStream& operator<<(OStream &os, const Vector &v) { 00099 assert((v.getLength() != 0) && "Zero-length vector badness."); 00100 00101 os << "[ " << v[0]; 00102 for (unsigned i = 1; i < v.getLength(); ++i) { 00103 os << ", " << v[i]; 00104 } 00105 os << " ]"; 00106 00107 return os; 00108 } 00109 00110 00111 /// \brief PBQP Matrix class 00112 class Matrix { 00113 public: 00114 00115 /// \brief Construct a PBQP Matrix with the given dimensions. 00116 Matrix(unsigned rows, unsigned cols) : 00117 rows(rows), cols(cols), data(new PBQPNum[rows * cols]) { 00118 } 00119 00120 /// \brief Construct a PBQP Matrix with the given dimensions and initial 00121 /// value. 00122 Matrix(unsigned rows, unsigned cols, PBQPNum initVal) : 00123 rows(rows), cols(cols), data(new PBQPNum[rows * cols]) { 00124 std::fill(data, data + (rows * cols), initVal); 00125 } 00126 00127 /// \brief Copy construct a PBQP matrix. 00128 Matrix(const Matrix &m) : 00129 rows(m.rows), cols(m.cols), data(new PBQPNum[rows * cols]) { 00130 std::copy(m.data, m.data + (rows * cols), data); 00131 } 00132 00133 /// \brief Destroy this matrix, return its memory. 00134 ~Matrix() { delete[] data; } 00135 00136 /// \brief Assignment operator. 00137 Matrix& operator=(const Matrix &m) { 00138 delete[] data; 00139 rows = m.rows; cols = m.cols; 00140 data = new PBQPNum[rows * cols]; 00141 std::copy(m.data, m.data + (rows * cols), data); 00142 return *this; 00143 } 00144 00145 /// \brief Return the number of rows in this matrix. 00146 unsigned getRows() const { return rows; } 00147 00148 /// \brief Return the number of cols in this matrix. 00149 unsigned getCols() const { return cols; } 00150 00151 /// \brief Matrix element access. 00152 PBQPNum* operator[](unsigned r) { 00153 assert(r < rows && "Row out of bounds."); 00154 return data + (r * cols); 00155 } 00156 00157 /// \brief Matrix element access. 00158 const PBQPNum* operator[](unsigned r) const { 00159 assert(r < rows && "Row out of bounds."); 00160 return data + (r * cols); 00161 } 00162 00163 /// \brief Returns the given row as a vector. 00164 Vector getRowAsVector(unsigned r) const { 00165 Vector v(cols); 00166 for (unsigned c = 0; c < cols; ++c) 00167 v[c] = (*this)[r][c]; 00168 return v; 00169 } 00170 00171 /// \brief Returns the given column as a vector. 00172 Vector getColAsVector(unsigned c) const { 00173 Vector v(rows); 00174 for (unsigned r = 0; r < rows; ++r) 00175 v[r] = (*this)[r][c]; 00176 return v; 00177 } 00178 00179 /// \brief Reset the matrix to the given value. 00180 Matrix& reset(PBQPNum val = 0) { 00181 std::fill(data, data + (rows * cols), val); 00182 return *this; 00183 } 00184 00185 /// \brief Set a single row of this matrix to the given value. 00186 Matrix& setRow(unsigned r, PBQPNum val) { 00187 assert(r < rows && "Row out of bounds."); 00188 std::fill(data + (r * cols), data + ((r + 1) * cols), val); 00189 return *this; 00190 } 00191 00192 /// \brief Set a single column of this matrix to the given value. 00193 Matrix& setCol(unsigned c, PBQPNum val) { 00194 assert(c < cols && "Column out of bounds."); 00195 for (unsigned r = 0; r < rows; ++r) 00196 (*this)[r][c] = val; 00197 return *this; 00198 } 00199 00200 /// \brief Matrix transpose. 00201 Matrix transpose() const { 00202 Matrix m(cols, rows); 00203 for (unsigned r = 0; r < rows; ++r) 00204 for (unsigned c = 0; c < cols; ++c) 00205 m[c][r] = (*this)[r][c]; 00206 return m; 00207 } 00208 00209 /// \brief Returns the diagonal of the matrix as a vector. 00210 /// 00211 /// Matrix must be square. 00212 Vector diagonalize() const { 00213 assert(rows == cols && "Attempt to diagonalize non-square matrix."); 00214 00215 Vector v(rows); 00216 for (unsigned r = 0; r < rows; ++r) 00217 v[r] = (*this)[r][r]; 00218 return v; 00219 } 00220 00221 /// \brief Add the given matrix to this one. 00222 Matrix& operator+=(const Matrix &m) { 00223 assert(rows == m.rows && cols == m.cols && 00224 "Matrix dimensions mismatch."); 00225 std::transform(data, data + (rows * cols), m.data, data, 00226 std::plus<PBQPNum>()); 00227 return *this; 00228 } 00229 00230 /// \brief Returns the minimum of the given row 00231 PBQPNum getRowMin(unsigned r) const { 00232 assert(r < rows && "Row out of bounds"); 00233 return *std::min_element(data + (r * cols), data + ((r + 1) * cols)); 00234 } 00235 00236 /// \brief Returns the minimum of the given column 00237 PBQPNum getColMin(unsigned c) const { 00238 PBQPNum minElem = (*this)[0][c]; 00239 for (unsigned r = 1; r < rows; ++r) 00240 if ((*this)[r][c] < minElem) minElem = (*this)[r][c]; 00241 return minElem; 00242 } 00243 00244 /// \brief Subtracts the given scalar from the elements of the given row. 00245 Matrix& subFromRow(unsigned r, PBQPNum val) { 00246 assert(r < rows && "Row out of bounds"); 00247 std::transform(data + (r * cols), data + ((r + 1) * cols), 00248 data + (r * cols), 00249 std::bind2nd(std::minus<PBQPNum>(), val)); 00250 return *this; 00251 } 00252 00253 /// \brief Subtracts the given scalar from the elements of the given column. 00254 Matrix& subFromCol(unsigned c, PBQPNum val) { 00255 for (unsigned r = 0; r < rows; ++r) 00256 (*this)[r][c] -= val; 00257 return *this; 00258 } 00259 00260 /// \brief Returns true if this is a zero matrix. 00261 bool isZero() const { 00262 return find_if(data, data + (rows * cols), 00263 std::bind2nd(std::not_equal_to<PBQPNum>(), 0)) == 00264 data + (rows * cols); 00265 } 00266 00267 private: 00268 unsigned rows, cols; 00269 PBQPNum *data; 00270 }; 00271 00272 /// \brief Output a textual representation of the given matrix on the given 00273 /// output stream. 00274 template <typename OStream> 00275 OStream& operator<<(OStream &os, const Matrix &m) { 00276 00277 assert((m.getRows() != 0) && "Zero-row matrix badness."); 00278 00279 for (unsigned i = 0; i < m.getRows(); ++i) { 00280 os << m.getRowAsVector(i); 00281 } 00282 00283 return os; 00284 } 00285 00286 } 00287 00288 #endif // LLVM_CODEGEN_PBQP_PBQPMATH_HPP