LLVM API Documentation

PBQPMath.h

Go to the documentation of this file.
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