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  friend class VectorComparator;
24public:
25
26  /// \brief Construct a PBQP vector of the given size.
27  explicit Vector(unsigned Length)
28    : Length(Length), Data(new PBQPNum[Length]) {
29    // llvm::dbgs() << "Constructing PBQP::Vector "
30    //              << this << " (length " << Length << ")\n";
31  }
32
33  /// \brief Construct a PBQP vector with initializer.
34  Vector(unsigned Length, PBQPNum InitVal)
35    : Length(Length), Data(new PBQPNum[Length]) {
36    // llvm::dbgs() << "Constructing PBQP::Vector "
37    //              << this << " (length " << Length << ", fill "
38    //              << InitVal << ")\n";
39    std::fill(Data, Data + Length, InitVal);
40  }
41
42  /// \brief Copy construct a PBQP vector.
43  Vector(const Vector &V)
44    : Length(V.Length), Data(new PBQPNum[Length]) {
45    // llvm::dbgs() << "Copy-constructing PBQP::Vector " << this
46    //              << " from PBQP::Vector " << &V << "\n";
47    std::copy(V.Data, V.Data + Length, Data);
48  }
49
50  /// \brief Move construct a PBQP vector.
51  Vector(Vector &&V)
52    : Length(V.Length), Data(V.Data) {
53    V.Length = 0;
54    V.Data = nullptr;
55  }
56
57  /// \brief Destroy this vector, return its memory.
58  ~Vector() {
59    // llvm::dbgs() << "Deleting PBQP::Vector " << this << "\n";
60    delete[] Data;
61  }
62
63  /// \brief Copy-assignment operator.
64  Vector& operator=(const Vector &V) {
65    // llvm::dbgs() << "Assigning to PBQP::Vector " << this
66    //              << " from PBQP::Vector " << &V << "\n";
67    delete[] Data;
68    Length = V.Length;
69    Data = new PBQPNum[Length];
70    std::copy(V.Data, V.Data + Length, Data);
71    return *this;
72  }
73
74  /// \brief Move-assignment operator.
75  Vector& operator=(Vector &&V) {
76    delete[] Data;
77    Length = V.Length;
78    Data = V.Data;
79    V.Length = 0;
80    V.Data = nullptr;
81    return *this;
82  }
83
84  /// \brief Comparison operator.
85  bool operator==(const Vector &V) const {
86    assert(Length != 0 && Data != nullptr && "Invalid vector");
87    if (Length != V.Length)
88      return false;
89    return std::equal(Data, Data + Length, V.Data);
90  }
91
92  /// \brief Return the length of the vector
93  unsigned getLength() const {
94    assert(Length != 0 && Data != nullptr && "Invalid vector");
95    return Length;
96  }
97
98  /// \brief Element access.
99  PBQPNum& operator[](unsigned Index) {
100    assert(Length != 0 && Data != nullptr && "Invalid vector");
101    assert(Index < Length && "Vector element access out of bounds.");
102    return Data[Index];
103  }
104
105  /// \brief Const element access.
106  const PBQPNum& operator[](unsigned Index) const {
107    assert(Length != 0 && Data != nullptr && "Invalid vector");
108    assert(Index < Length && "Vector element access out of bounds.");
109    return Data[Index];
110  }
111
112  /// \brief Add another vector to this one.
113  Vector& operator+=(const Vector &V) {
114    assert(Length != 0 && Data != nullptr && "Invalid vector");
115    assert(Length == V.Length && "Vector length mismatch.");
116    std::transform(Data, Data + Length, V.Data, Data, std::plus<PBQPNum>());
117    return *this;
118  }
119
120  /// \brief Subtract another vector from this one.
121  Vector& operator-=(const Vector &V) {
122    assert(Length != 0 && Data != nullptr && "Invalid vector");
123    assert(Length == V.Length && "Vector length mismatch.");
124    std::transform(Data, Data + Length, V.Data, Data, std::minus<PBQPNum>());
125    return *this;
126  }
127
128  /// \brief Returns the index of the minimum value in this vector
129  unsigned minIndex() const {
130    assert(Length != 0 && Data != nullptr && "Invalid vector");
131    return std::min_element(Data, Data + Length) - Data;
132  }
133
134private:
135  unsigned Length;
136  PBQPNum *Data;
137};
138
139class VectorComparator {
140public:
141  bool operator()(const Vector &A, const Vector &B) {
142    if (A.Length < B.Length)
143      return true;
144    if (B.Length < A.Length)
145      return false;
146    char *AData = reinterpret_cast<char*>(A.Data);
147    char *BData = reinterpret_cast<char*>(B.Data);
148    return std::lexicographical_compare(AData,
149                                        AData + A.Length * sizeof(PBQPNum),
150                                        BData,
151                                        BData + A.Length * sizeof(PBQPNum));
152  }
153};
154
155/// \brief Output a textual representation of the given vector on the given
156///        output stream.
157template <typename OStream>
158OStream& operator<<(OStream &OS, const Vector &V) {
159  assert((V.getLength() != 0) && "Zero-length vector badness.");
160
161  OS << "[ " << V[0];
162  for (unsigned i = 1; i < V.getLength(); ++i)
163    OS << ", " << V[i];
164  OS << " ]";
165
166  return OS;
167}
168
169
170/// \brief PBQP Matrix class
171class Matrix {
172private:
173  friend class MatrixComparator;
174public:
175
176  /// \brief Construct a PBQP Matrix with the given dimensions.
177  Matrix(unsigned Rows, unsigned Cols) :
178    Rows(Rows), Cols(Cols), Data(new PBQPNum[Rows * Cols]) {
179  }
180
181  /// \brief Construct a PBQP Matrix with the given dimensions and initial
182  /// value.
183  Matrix(unsigned Rows, unsigned Cols, PBQPNum InitVal)
184    : Rows(Rows), Cols(Cols), Data(new PBQPNum[Rows * Cols]) {
185    std::fill(Data, Data + (Rows * Cols), InitVal);
186  }
187
188  /// \brief Copy construct a PBQP matrix.
189  Matrix(const Matrix &M)
190    : Rows(M.Rows), Cols(M.Cols), Data(new PBQPNum[Rows * Cols]) {
191    std::copy(M.Data, M.Data + (Rows * Cols), Data);
192  }
193
194  /// \brief Move construct a PBQP matrix.
195  Matrix(Matrix &&M)
196    : Rows(M.Rows), Cols(M.Cols), Data(M.Data) {
197    M.Rows = M.Cols = 0;
198    M.Data = nullptr;
199  }
200
201  /// \brief Destroy this matrix, return its memory.
202  ~Matrix() { delete[] Data; }
203
204  /// \brief Copy-assignment operator.
205  Matrix& operator=(const Matrix &M) {
206    delete[] Data;
207    Rows = M.Rows; Cols = M.Cols;
208    Data = new PBQPNum[Rows * Cols];
209    std::copy(M.Data, M.Data + (Rows * Cols), Data);
210    return *this;
211  }
212
213  /// \brief Move-assignment operator.
214  Matrix& operator=(Matrix &&M) {
215    delete[] Data;
216    Rows = M.Rows;
217    Cols = M.Cols;
218    Data = M.Data;
219    M.Rows = M.Cols = 0;
220    M.Data = nullptr;
221    return *this;
222  }
223
224  /// \brief Comparison operator.
225  bool operator==(const Matrix &M) const {
226    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
227    if (Rows != M.Rows || Cols != M.Cols)
228      return false;
229    return std::equal(Data, Data + (Rows * Cols), M.Data);
230  }
231
232  /// \brief Return the number of rows in this matrix.
233  unsigned getRows() const {
234    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
235    return Rows;
236  }
237
238  /// \brief Return the number of cols in this matrix.
239  unsigned getCols() const {
240    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
241    return Cols;
242  }
243
244  /// \brief Matrix element access.
245  PBQPNum* operator[](unsigned R) {
246    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
247    assert(R < Rows && "Row out of bounds.");
248    return Data + (R * Cols);
249  }
250
251  /// \brief Matrix element access.
252  const PBQPNum* operator[](unsigned R) const {
253    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
254    assert(R < Rows && "Row out of bounds.");
255    return Data + (R * Cols);
256  }
257
258  /// \brief Returns the given row as a vector.
259  Vector getRowAsVector(unsigned R) const {
260    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
261    Vector V(Cols);
262    for (unsigned C = 0; C < Cols; ++C)
263      V[C] = (*this)[R][C];
264    return V;
265  }
266
267  /// \brief Returns the given column as a vector.
268  Vector getColAsVector(unsigned C) const {
269    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
270    Vector V(Rows);
271    for (unsigned R = 0; R < Rows; ++R)
272      V[R] = (*this)[R][C];
273    return V;
274  }
275
276  /// \brief Reset the matrix to the given value.
277  Matrix& reset(PBQPNum Val = 0) {
278    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
279    std::fill(Data, Data + (Rows * Cols), Val);
280    return *this;
281  }
282
283  /// \brief Set a single row of this matrix to the given value.
284  Matrix& setRow(unsigned R, PBQPNum Val) {
285    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
286    assert(R < Rows && "Row out of bounds.");
287    std::fill(Data + (R * Cols), Data + ((R + 1) * Cols), Val);
288    return *this;
289  }
290
291  /// \brief Set a single column of this matrix to the given value.
292  Matrix& setCol(unsigned C, PBQPNum Val) {
293    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
294    assert(C < Cols && "Column out of bounds.");
295    for (unsigned R = 0; R < Rows; ++R)
296      (*this)[R][C] = Val;
297    return *this;
298  }
299
300  /// \brief Matrix transpose.
301  Matrix transpose() const {
302    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
303    Matrix M(Cols, Rows);
304    for (unsigned r = 0; r < Rows; ++r)
305      for (unsigned c = 0; c < Cols; ++c)
306        M[c][r] = (*this)[r][c];
307    return M;
308  }
309
310  /// \brief Returns the diagonal of the matrix as a vector.
311  ///
312  /// Matrix must be square.
313  Vector diagonalize() const {
314    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
315    assert(Rows == Cols && "Attempt to diagonalize non-square matrix.");
316    Vector V(Rows);
317    for (unsigned r = 0; r < Rows; ++r)
318      V[r] = (*this)[r][r];
319    return V;
320  }
321
322  /// \brief Add the given matrix to this one.
323  Matrix& operator+=(const Matrix &M) {
324    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
325    assert(Rows == M.Rows && Cols == M.Cols &&
326           "Matrix dimensions mismatch.");
327    std::transform(Data, Data + (Rows * Cols), M.Data, Data,
328                   std::plus<PBQPNum>());
329    return *this;
330  }
331
332  Matrix operator+(const Matrix &M) {
333    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
334    Matrix Tmp(*this);
335    Tmp += M;
336    return Tmp;
337  }
338
339  /// \brief Returns the minimum of the given row
340  PBQPNum getRowMin(unsigned R) const {
341    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
342    assert(R < Rows && "Row out of bounds");
343    return *std::min_element(Data + (R * Cols), Data + ((R + 1) * Cols));
344  }
345
346  /// \brief Returns the minimum of the given column
347  PBQPNum getColMin(unsigned C) const {
348    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
349    PBQPNum MinElem = (*this)[0][C];
350    for (unsigned R = 1; R < Rows; ++R)
351      if ((*this)[R][C] < MinElem)
352        MinElem = (*this)[R][C];
353    return MinElem;
354  }
355
356  /// \brief Subtracts the given scalar from the elements of the given row.
357  Matrix& subFromRow(unsigned R, PBQPNum Val) {
358    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
359    assert(R < Rows && "Row out of bounds");
360    std::transform(Data + (R * Cols), Data + ((R + 1) * Cols),
361                   Data + (R * Cols),
362                   std::bind2nd(std::minus<PBQPNum>(), Val));
363    return *this;
364  }
365
366  /// \brief Subtracts the given scalar from the elements of the given column.
367  Matrix& subFromCol(unsigned C, PBQPNum Val) {
368    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
369    for (unsigned R = 0; R < Rows; ++R)
370      (*this)[R][C] -= Val;
371    return *this;
372  }
373
374  /// \brief Returns true if this is a zero matrix.
375  bool isZero() const {
376    assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
377    return find_if(Data, Data + (Rows * Cols),
378                   std::bind2nd(std::not_equal_to<PBQPNum>(), 0)) ==
379      Data + (Rows * Cols);
380  }
381
382private:
383  unsigned Rows, Cols;
384  PBQPNum *Data;
385};
386
387class MatrixComparator {
388public:
389  bool operator()(const Matrix &A, const Matrix &B) {
390    if (A.Rows < B.Rows)
391      return true;
392    if (B.Rows < A.Rows)
393      return false;
394    if (A.Cols < B.Cols)
395      return true;
396    if (B.Cols < A.Cols)
397      return false;
398    char *AData = reinterpret_cast<char*>(A.Data);
399    char *BData = reinterpret_cast<char*>(B.Data);
400    return std::lexicographical_compare(
401             AData, AData + (A.Rows * A.Cols * sizeof(PBQPNum)),
402             BData, BData + (A.Rows * A.Cols * sizeof(PBQPNum)));
403  }
404};
405
406/// \brief Output a textual representation of the given matrix on the given
407///        output stream.
408template <typename OStream>
409OStream& operator<<(OStream &OS, const Matrix &M) {
410  assert((M.getRows() != 0) && "Zero-row matrix badness.");
411  for (unsigned i = 0; i < M.getRows(); ++i)
412    OS << M.getRowAsVector(i);
413  return OS;
414}
415
416template <typename Metadata>
417class MDVector : public Vector {
418public:
419  MDVector(const Vector &v) : Vector(v), md(*this) { }
420  MDVector(Vector &&v) : Vector(std::move(v)), md(*this) { }
421  const Metadata& getMetadata() const { return md; }
422private:
423  Metadata md;
424};
425
426template <typename Metadata>
427class MDMatrix : public Matrix {
428public:
429  MDMatrix(const Matrix &m) : Matrix(m), md(*this) { }
430  MDMatrix(Matrix &&m) : Matrix(std::move(m)), md(*this) { }
431  const Metadata& getMetadata() const { return md; }
432private:
433  Metadata md;
434};
435
436}
437
438#endif // LLVM_CODEGEN_PBQP_MATH_H
439