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