1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the HiGHS linear optimization suite */ 4 /* */ 5 /* Written and engineered 2008-2021 at the University of Edinburgh */ 6 /* */ 7 /* Available as open-source under the MIT License */ 8 /* */ 9 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 10 #ifndef HIGHS_DYNAMIC_ROW_MATRIX_H_ 11 #define HIGHS_DYNAMIC_ROW_MATRIX_H_ 12 13 #include <set> 14 #include <utility> 15 #include <vector> 16 17 class HighsDynamicRowMatrix { 18 private: 19 /// vector of index ranges in the index and value arrays of AR for each row 20 std::vector<std::pair<int, int>> ARrange_; 21 22 /// column indices for each nonzero in AR 23 std::vector<int> ARindex_; 24 /// values for each nonzero in AR 25 std::vector<double> ARvalue_; 26 27 std::vector<int> ARrowindex_; 28 std::vector<int> Anext_; 29 std::vector<int> Aprev_; 30 31 /// vector of pointers to the head/tail of the nonzero block list for each 32 /// column 33 std::vector<int> Ahead_; 34 std::vector<int> Atail_; 35 36 /// vector of column sizes 37 38 /// keep an ordered set ofof free spaces in the row arrays so that they can be 39 /// reused efficiently 40 std::set<std::pair<int, int>> freespaces_; 41 42 /// vector of deleted rows so that their indices can be reused 43 std::vector<int> deletedrows_; 44 45 public: 46 std::vector<int> Asize_; 47 HighsDynamicRowMatrix(int ncols); 48 49 /// adds a row to the matrix with the given values and returns its index 50 int addRow(int* Rindex, double* Rvalue, int Rlen); 51 52 /// removes the row with the given index from the matrix, afterwards the index 53 /// can be reused for new rows 54 void removeRow(int rowindex); 55 nonzeroCapacity()56 size_t nonzeroCapacity() const { return ARvalue_.size(); } 57 58 /// replaces a rows values but does not change the support 59 void replaceRowValues(int rowindex, double* Rvalue); 60 61 /// calls the given function object for each entry in the given column. 62 /// The function object should accept the row index as first argument and 63 /// the nonzero value of the column in that row as the second argument. 64 template <typename Func> forEachColumnEntry(int col,Func && f)65 void forEachColumnEntry(int col, Func&& f) const { 66 int iter = Ahead_[col]; 67 68 while (iter != -1) { 69 if (!f(ARrowindex_[iter], ARvalue_[iter])) break; 70 iter = Anext_[iter]; 71 } 72 } 73 getNumRows()74 int getNumRows() const { return ARrange_.size(); } 75 getNumDelRows()76 int getNumDelRows() const { return deletedrows_.size(); } 77 getRowStart(int row)78 int getRowStart(int row) const { return ARrange_[row].first; } 79 getRowEnd(int row)80 int getRowEnd(int row) const { return ARrange_[row].second; } 81 getARindex()82 const int* getARindex() const { return ARindex_.data(); } 83 getARvalue()84 const double* getARvalue() const { return ARvalue_.data(); } 85 }; 86 87 #endif