LLVM API Documentation

 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Math.h
Go to the documentation of this file.
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 
17 namespace PBQP {
18 
19 typedef float PBQPNum;
20 
21 /// \brief PBQP Vector class.
22 class 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.
97 template <typename OStream>
98 OStream& 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
112 class 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.
274 template <typename OStream>
275 OStream& 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
PBQPNum getRowMin(unsigned r) const
Returns the minimum of the given row.
Definition: Math.h:231
Vector(const Vector &v)
Copy construct a PBQP vector.
Definition: Math.h:37
Vector diagonalize() const
Returns the diagonal of the matrix as a vector.
Definition: Math.h:212
Matrix(unsigned rows, unsigned cols)
Construct a PBQP Matrix with the given dimensions.
Definition: Math.h:116
Matrix & operator+=(const Matrix &m)
Add the given matrix to this one.
Definition: Math.h:222
unsigned getLength() const
Return the length of the vector.
Definition: Math.h:55
bool isZero() const
Returns true if this is a zero matrix.
Definition: Math.h:261
Vector(unsigned length)
Construct a PBQP vector of the given size.
Definition: Math.h:26
unsigned minIndex() const
Returns the index of the minimum value in this vector.
Definition: Math.h:86
unsigned getRows() const
Return the number of rows in this matrix.
Definition: Math.h:146
Matrix & subFromCol(unsigned c, PBQPNum val)
Subtracts the given scalar from the elements of the given column.
Definition: Math.h:254
~Vector()
Destroy this vector, return its memory.
Definition: Math.h:43
Vector & operator=(const Vector &v)
Assignment operator.
Definition: Math.h:46
Matrix & reset(PBQPNum val=0)
Reset the matrix to the given value.
Definition: Math.h:180
PBQPNum getColMin(unsigned c) const
Returns the minimum of the given column.
Definition: Math.h:237
Vector & operator-=(const Vector &v)
Subtract another vector from this one.
Definition: Math.h:79
Matrix & setRow(unsigned r, PBQPNum val)
Set a single row of this matrix to the given value.
Definition: Math.h:186
Matrix & subFromRow(unsigned r, PBQPNum val)
Subtracts the given scalar from the elements of the given row.
Definition: Math.h:245
PBQPNum * operator[](unsigned r)
Matrix element access.
Definition: Math.h:152
~Matrix()
Destroy this matrix, return its memory.
Definition: Math.h:134
PBQPNum & operator[](unsigned index)
Element access.
Definition: Math.h:60
Matrix(unsigned rows, unsigned cols, PBQPNum initVal)
Construct a PBQP Matrix with the given dimensions and initial value.
Definition: Math.h:122
Vector getRowAsVector(unsigned r) const
Returns the given row as a vector.
Definition: Math.h:164
float PBQPNum
Definition: Math.h:19
const PBQPNum & operator[](unsigned index) const
Const element access.
Definition: Math.h:66
const PBQPNum * operator[](unsigned r) const
Matrix element access.
Definition: Math.h:158
Matrix & operator=(const Matrix &m)
Assignment operator.
Definition: Math.h:137
Matrix(const Matrix &m)
Copy construct a PBQP matrix.
Definition: Math.h:128
Matrix & setCol(unsigned c, PBQPNum val)
Set a single column of this matrix to the given value.
Definition: Math.h:193
Matrix transpose() const
Matrix transpose.
Definition: Math.h:201
OStream & operator<<(OStream &os, const Vector &v)
Output a textual representation of the given vector on the given output stream.
Definition: Math.h:98
PBQP Vector class.
Definition: Math.h:22
Vector(unsigned length, PBQPNum initVal)
Construct a PBQP vector with initializer.
Definition: Math.h:31
unsigned getCols() const
Return the number of cols in this matrix.
Definition: Math.h:149
Vector & operator+=(const Vector &v)
Add another vector to this one.
Definition: Math.h:72
PBQP Matrix class.
Definition: Math.h:112
Vector getColAsVector(unsigned c) const
Returns the given column as a vector.
Definition: Math.h:172