1218885Sdim//===------ Math.h - PBQP Vector and Matrix classes -------------*- C++ -*-===// 2218885Sdim// 3218885Sdim// The LLVM Compiler Infrastructure 4218885Sdim// 5218885Sdim// This file is distributed under the University of Illinois Open Source 6218885Sdim// License. See LICENSE.TXT for details. 7218885Sdim// 8218885Sdim//===----------------------------------------------------------------------===// 9218885Sdim 10249423Sdim#ifndef LLVM_CODEGEN_PBQP_MATH_H 11218885Sdim#define LLVM_CODEGEN_PBQP_MATH_H 12218885Sdim 13249423Sdim#include <algorithm> 14218885Sdim#include <cassert> 15218885Sdim#include <functional> 16218885Sdim 17218885Sdimnamespace PBQP { 18218885Sdim 19218885Sdimtypedef float PBQPNum; 20218885Sdim 21218885Sdim/// \brief PBQP Vector class. 22218885Sdimclass Vector { 23218885Sdim public: 24218885Sdim 25218885Sdim /// \brief Construct a PBQP vector of the given size. 26218885Sdim explicit Vector(unsigned length) : 27218885Sdim length(length), data(new PBQPNum[length]) { 28218885Sdim } 29218885Sdim 30218885Sdim /// \brief Construct a PBQP vector with initializer. 31218885Sdim Vector(unsigned length, PBQPNum initVal) : 32218885Sdim length(length), data(new PBQPNum[length]) { 33218885Sdim std::fill(data, data + length, initVal); 34218885Sdim } 35218885Sdim 36218885Sdim /// \brief Copy construct a PBQP vector. 37218885Sdim Vector(const Vector &v) : 38218885Sdim length(v.length), data(new PBQPNum[length]) { 39218885Sdim std::copy(v.data, v.data + length, data); 40218885Sdim } 41218885Sdim 42218885Sdim /// \brief Destroy this vector, return its memory. 43218885Sdim ~Vector() { delete[] data; } 44218885Sdim 45218885Sdim /// \brief Assignment operator. 46218885Sdim Vector& operator=(const Vector &v) { 47218885Sdim delete[] data; 48218885Sdim length = v.length; 49218885Sdim data = new PBQPNum[length]; 50218885Sdim std::copy(v.data, v.data + length, data); 51218885Sdim return *this; 52218885Sdim } 53218885Sdim 54218885Sdim /// \brief Return the length of the vector 55218885Sdim unsigned getLength() const { 56218885Sdim return length; 57218885Sdim } 58218885Sdim 59218885Sdim /// \brief Element access. 60218885Sdim PBQPNum& operator[](unsigned index) { 61218885Sdim assert(index < length && "Vector element access out of bounds."); 62218885Sdim return data[index]; 63218885Sdim } 64218885Sdim 65218885Sdim /// \brief Const element access. 66218885Sdim const PBQPNum& operator[](unsigned index) const { 67218885Sdim assert(index < length && "Vector element access out of bounds."); 68218885Sdim return data[index]; 69218885Sdim } 70218885Sdim 71218885Sdim /// \brief Add another vector to this one. 72218885Sdim Vector& operator+=(const Vector &v) { 73218885Sdim assert(length == v.length && "Vector length mismatch."); 74218885Sdim std::transform(data, data + length, v.data, data, std::plus<PBQPNum>()); 75218885Sdim return *this; 76218885Sdim } 77218885Sdim 78218885Sdim /// \brief Subtract another vector from this one. 79218885Sdim Vector& operator-=(const Vector &v) { 80218885Sdim assert(length == v.length && "Vector length mismatch."); 81218885Sdim std::transform(data, data + length, v.data, data, std::minus<PBQPNum>()); 82218885Sdim return *this; 83218885Sdim } 84218885Sdim 85218885Sdim /// \brief Returns the index of the minimum value in this vector 86218885Sdim unsigned minIndex() const { 87218885Sdim return std::min_element(data, data + length) - data; 88218885Sdim } 89218885Sdim 90218885Sdim private: 91218885Sdim unsigned length; 92218885Sdim PBQPNum *data; 93218885Sdim}; 94218885Sdim 95218885Sdim/// \brief Output a textual representation of the given vector on the given 96218885Sdim/// output stream. 97218885Sdimtemplate <typename OStream> 98218885SdimOStream& operator<<(OStream &os, const Vector &v) { 99218885Sdim assert((v.getLength() != 0) && "Zero-length vector badness."); 100218885Sdim 101218885Sdim os << "[ " << v[0]; 102218885Sdim for (unsigned i = 1; i < v.getLength(); ++i) { 103218885Sdim os << ", " << v[i]; 104218885Sdim } 105218885Sdim os << " ]"; 106218885Sdim 107218885Sdim return os; 108218885Sdim} 109218885Sdim 110218885Sdim 111218885Sdim/// \brief PBQP Matrix class 112218885Sdimclass Matrix { 113218885Sdim public: 114218885Sdim 115218885Sdim /// \brief Construct a PBQP Matrix with the given dimensions. 116218885Sdim Matrix(unsigned rows, unsigned cols) : 117218885Sdim rows(rows), cols(cols), data(new PBQPNum[rows * cols]) { 118218885Sdim } 119218885Sdim 120218885Sdim /// \brief Construct a PBQP Matrix with the given dimensions and initial 121218885Sdim /// value. 122218885Sdim Matrix(unsigned rows, unsigned cols, PBQPNum initVal) : 123218885Sdim rows(rows), cols(cols), data(new PBQPNum[rows * cols]) { 124218885Sdim std::fill(data, data + (rows * cols), initVal); 125218885Sdim } 126218885Sdim 127218885Sdim /// \brief Copy construct a PBQP matrix. 128218885Sdim Matrix(const Matrix &m) : 129218885Sdim rows(m.rows), cols(m.cols), data(new PBQPNum[rows * cols]) { 130218885Sdim std::copy(m.data, m.data + (rows * cols), data); 131218885Sdim } 132218885Sdim 133218885Sdim /// \brief Destroy this matrix, return its memory. 134218885Sdim ~Matrix() { delete[] data; } 135218885Sdim 136218885Sdim /// \brief Assignment operator. 137218885Sdim Matrix& operator=(const Matrix &m) { 138218885Sdim delete[] data; 139218885Sdim rows = m.rows; cols = m.cols; 140218885Sdim data = new PBQPNum[rows * cols]; 141218885Sdim std::copy(m.data, m.data + (rows * cols), data); 142218885Sdim return *this; 143218885Sdim } 144218885Sdim 145218885Sdim /// \brief Return the number of rows in this matrix. 146218885Sdim unsigned getRows() const { return rows; } 147218885Sdim 148218885Sdim /// \brief Return the number of cols in this matrix. 149218885Sdim unsigned getCols() const { return cols; } 150218885Sdim 151218885Sdim /// \brief Matrix element access. 152218885Sdim PBQPNum* operator[](unsigned r) { 153218885Sdim assert(r < rows && "Row out of bounds."); 154218885Sdim return data + (r * cols); 155218885Sdim } 156218885Sdim 157218885Sdim /// \brief Matrix element access. 158218885Sdim const PBQPNum* operator[](unsigned r) const { 159218885Sdim assert(r < rows && "Row out of bounds."); 160218885Sdim return data + (r * cols); 161218885Sdim } 162218885Sdim 163218885Sdim /// \brief Returns the given row as a vector. 164218885Sdim Vector getRowAsVector(unsigned r) const { 165218885Sdim Vector v(cols); 166218885Sdim for (unsigned c = 0; c < cols; ++c) 167218885Sdim v[c] = (*this)[r][c]; 168218885Sdim return v; 169218885Sdim } 170218885Sdim 171218885Sdim /// \brief Returns the given column as a vector. 172218885Sdim Vector getColAsVector(unsigned c) const { 173218885Sdim Vector v(rows); 174218885Sdim for (unsigned r = 0; r < rows; ++r) 175218885Sdim v[r] = (*this)[r][c]; 176218885Sdim return v; 177218885Sdim } 178218885Sdim 179218885Sdim /// \brief Reset the matrix to the given value. 180218885Sdim Matrix& reset(PBQPNum val = 0) { 181218885Sdim std::fill(data, data + (rows * cols), val); 182218885Sdim return *this; 183218885Sdim } 184218885Sdim 185218885Sdim /// \brief Set a single row of this matrix to the given value. 186218885Sdim Matrix& setRow(unsigned r, PBQPNum val) { 187218885Sdim assert(r < rows && "Row out of bounds."); 188218885Sdim std::fill(data + (r * cols), data + ((r + 1) * cols), val); 189218885Sdim return *this; 190218885Sdim } 191218885Sdim 192218885Sdim /// \brief Set a single column of this matrix to the given value. 193218885Sdim Matrix& setCol(unsigned c, PBQPNum val) { 194218885Sdim assert(c < cols && "Column out of bounds."); 195218885Sdim for (unsigned r = 0; r < rows; ++r) 196218885Sdim (*this)[r][c] = val; 197218885Sdim return *this; 198218885Sdim } 199218885Sdim 200218885Sdim /// \brief Matrix transpose. 201218885Sdim Matrix transpose() const { 202218885Sdim Matrix m(cols, rows); 203218885Sdim for (unsigned r = 0; r < rows; ++r) 204218885Sdim for (unsigned c = 0; c < cols; ++c) 205218885Sdim m[c][r] = (*this)[r][c]; 206218885Sdim return m; 207218885Sdim } 208218885Sdim 209218885Sdim /// \brief Returns the diagonal of the matrix as a vector. 210218885Sdim /// 211218885Sdim /// Matrix must be square. 212218885Sdim Vector diagonalize() const { 213218885Sdim assert(rows == cols && "Attempt to diagonalize non-square matrix."); 214218885Sdim 215218885Sdim Vector v(rows); 216218885Sdim for (unsigned r = 0; r < rows; ++r) 217218885Sdim v[r] = (*this)[r][r]; 218218885Sdim return v; 219218885Sdim } 220218885Sdim 221218885Sdim /// \brief Add the given matrix to this one. 222218885Sdim Matrix& operator+=(const Matrix &m) { 223218885Sdim assert(rows == m.rows && cols == m.cols && 224218885Sdim "Matrix dimensions mismatch."); 225218885Sdim std::transform(data, data + (rows * cols), m.data, data, 226218885Sdim std::plus<PBQPNum>()); 227218885Sdim return *this; 228218885Sdim } 229218885Sdim 230218885Sdim /// \brief Returns the minimum of the given row 231218885Sdim PBQPNum getRowMin(unsigned r) const { 232218885Sdim assert(r < rows && "Row out of bounds"); 233218885Sdim return *std::min_element(data + (r * cols), data + ((r + 1) * cols)); 234218885Sdim } 235218885Sdim 236218885Sdim /// \brief Returns the minimum of the given column 237218885Sdim PBQPNum getColMin(unsigned c) const { 238218885Sdim PBQPNum minElem = (*this)[0][c]; 239218885Sdim for (unsigned r = 1; r < rows; ++r) 240218885Sdim if ((*this)[r][c] < minElem) minElem = (*this)[r][c]; 241218885Sdim return minElem; 242218885Sdim } 243218885Sdim 244218885Sdim /// \brief Subtracts the given scalar from the elements of the given row. 245218885Sdim Matrix& subFromRow(unsigned r, PBQPNum val) { 246218885Sdim assert(r < rows && "Row out of bounds"); 247218885Sdim std::transform(data + (r * cols), data + ((r + 1) * cols), 248218885Sdim data + (r * cols), 249218885Sdim std::bind2nd(std::minus<PBQPNum>(), val)); 250218885Sdim return *this; 251218885Sdim } 252218885Sdim 253218885Sdim /// \brief Subtracts the given scalar from the elements of the given column. 254218885Sdim Matrix& subFromCol(unsigned c, PBQPNum val) { 255218885Sdim for (unsigned r = 0; r < rows; ++r) 256218885Sdim (*this)[r][c] -= val; 257218885Sdim return *this; 258218885Sdim } 259218885Sdim 260218885Sdim /// \brief Returns true if this is a zero matrix. 261218885Sdim bool isZero() const { 262218885Sdim return find_if(data, data + (rows * cols), 263218885Sdim std::bind2nd(std::not_equal_to<PBQPNum>(), 0)) == 264218885Sdim data + (rows * cols); 265218885Sdim } 266218885Sdim 267218885Sdim private: 268218885Sdim unsigned rows, cols; 269218885Sdim PBQPNum *data; 270218885Sdim}; 271218885Sdim 272218885Sdim/// \brief Output a textual representation of the given matrix on the given 273218885Sdim/// output stream. 274218885Sdimtemplate <typename OStream> 275218885SdimOStream& operator<<(OStream &os, const Matrix &m) { 276218885Sdim 277218885Sdim assert((m.getRows() != 0) && "Zero-row matrix badness."); 278218885Sdim 279218885Sdim for (unsigned i = 0; i < m.getRows(); ++i) { 280218885Sdim os << m.getRowAsVector(i); 281218885Sdim } 282218885Sdim 283218885Sdim return os; 284218885Sdim} 285218885Sdim 286218885Sdim} 287218885Sdim 288218885Sdim#endif // LLVM_CODEGEN_PBQP_MATH_H 289