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 <algorithm>
14#include <cassert>
15#include <functional>
16
17namespace PBQP {
18
19typedef float PBQPNum;
20
21/// \brief PBQP Vector class.
22class 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.
97template <typename OStream>
98OStream& 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
112class 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.
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_MATH_H
289