1 | // Copyright (C) 2016 The Qt Company Ltd. |
2 | // SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only |
3 | |
4 | #ifndef QSIMPLEX_P_H |
5 | #define QSIMPLEX_P_H |
6 | |
7 | // |
8 | // W A R N I N G |
9 | // ------------- |
10 | // |
11 | // This file is not part of the Qt API. It exists purely as an |
12 | // implementation detail. This header file may change from version to |
13 | // version without notice, or even be removed. |
14 | // |
15 | // We mean it. |
16 | // |
17 | |
18 | #include <QtWidgets/private/qtwidgetsglobal_p.h> |
19 | #include <QtCore/qhash.h> |
20 | #include <QtCore/qstring.h> |
21 | |
22 | QT_REQUIRE_CONFIG(graphicsview); |
23 | |
24 | QT_BEGIN_NAMESPACE |
25 | |
26 | struct QSimplexVariable |
27 | { |
28 | QSimplexVariable() : result(0), index(0) {} |
29 | |
30 | qreal result; |
31 | int index; |
32 | }; |
33 | |
34 | |
35 | /*! |
36 | \internal |
37 | |
38 | Representation of a LP constraint like: |
39 | |
40 | (c1 * X1) + (c2 * X2) + ... = K |
41 | or <= K |
42 | or >= K |
43 | |
44 | Where (ci, Xi) are the pairs in "variables" and K the real "constant". |
45 | */ |
46 | struct QSimplexConstraint |
47 | { |
48 | QSimplexConstraint() : constant(0), ratio(Equal), artificial(nullptr) {} |
49 | |
50 | enum Ratio { |
51 | LessOrEqual = 0, |
52 | Equal, |
53 | MoreOrEqual |
54 | }; |
55 | |
56 | QHash<QSimplexVariable *, qreal> variables; |
57 | qreal constant; |
58 | Ratio ratio; |
59 | |
60 | std::pair<QSimplexVariable *, qreal> helper; |
61 | QSimplexVariable * artificial; |
62 | |
63 | void invert(); |
64 | |
65 | bool isSatisfied() { |
66 | qreal leftHandSide(0); |
67 | |
68 | QHash<QSimplexVariable *, qreal>::const_iterator iter; |
69 | for (iter = variables.constBegin(); iter != variables.constEnd(); ++iter) { |
70 | leftHandSide += iter.value() * iter.key()->result; |
71 | } |
72 | |
73 | Q_ASSERT(constant > 0 || qFuzzyCompare(1, 1 + constant)); |
74 | |
75 | if ((leftHandSide == constant) || qAbs(t: leftHandSide - constant) < 0.0000001) |
76 | return true; |
77 | |
78 | switch (ratio) { |
79 | case LessOrEqual: |
80 | return leftHandSide < constant; |
81 | case MoreOrEqual: |
82 | return leftHandSide > constant; |
83 | default: |
84 | return false; |
85 | } |
86 | } |
87 | |
88 | #ifdef QT_DEBUG |
89 | QString toString() { |
90 | QString result; |
91 | result += QString::fromLatin1(ba: "-- QSimplexConstraint %1 --" ).arg(a: quintptr(this), fieldwidth: 0, base: 16); |
92 | |
93 | QHash<QSimplexVariable *, qreal>::const_iterator iter; |
94 | for (iter = variables.constBegin(); iter != variables.constEnd(); ++iter) { |
95 | result += QString::fromLatin1(ba: " %1 x %2" ).arg(a: iter.value()).arg(a: quintptr(iter.key()), fieldwidth: 0, base: 16); |
96 | } |
97 | |
98 | switch (ratio) { |
99 | case LessOrEqual: |
100 | result += QString::fromLatin1(ba: " (less) <= %1" ).arg(a: constant); |
101 | break; |
102 | case MoreOrEqual: |
103 | result += QString::fromLatin1(ba: " (more) >= %1" ).arg(a: constant); |
104 | break; |
105 | default: |
106 | result += QString::fromLatin1(ba: " (eqal) == %1" ).arg(a: constant); |
107 | } |
108 | |
109 | return result; |
110 | } |
111 | #endif |
112 | }; |
113 | |
114 | class QSimplex |
115 | { |
116 | Q_DISABLE_COPY_MOVE(QSimplex) |
117 | public: |
118 | QSimplex(); |
119 | ~QSimplex(); |
120 | |
121 | qreal solveMin(); |
122 | qreal solveMax(); |
123 | |
124 | bool setConstraints(const QList<QSimplexConstraint *> &constraints); |
125 | void setObjective(QSimplexConstraint *objective); |
126 | |
127 | void dumpMatrix(); |
128 | |
129 | private: |
130 | // Matrix handling |
131 | inline qreal valueAt(int row, int column); |
132 | inline void setValueAt(int row, int column, qreal value); |
133 | void clearRow(int rowIndex); |
134 | void clearColumns(int first, int last); |
135 | void combineRows(int toIndex, int fromIndex, qreal factor); |
136 | |
137 | // Simplex |
138 | bool simplifyConstraints(QList<QSimplexConstraint *> *constraints); |
139 | int findPivotColumn(); |
140 | int pivotRowForColumn(int column); |
141 | void reducedRowEchelon(); |
142 | bool iterate(); |
143 | |
144 | // Helpers |
145 | void clearDataStructures(); |
146 | void solveMaxHelper(); |
147 | enum SolverFactor { Minimum = -1, Maximum = 1 }; |
148 | qreal solver(SolverFactor factor); |
149 | void collectResults(); |
150 | |
151 | QList<QSimplexConstraint *> constraints; |
152 | QList<QSimplexVariable *> variables; |
153 | QSimplexConstraint *objective; |
154 | |
155 | int rows; |
156 | int columns; |
157 | int firstArtificial; |
158 | |
159 | qreal *matrix; |
160 | }; |
161 | |
162 | inline qreal QSimplex::valueAt(int rowIndex, int columnIndex) |
163 | { |
164 | return matrix[rowIndex * columns + columnIndex]; |
165 | } |
166 | |
167 | inline void QSimplex::setValueAt(int rowIndex, int columnIndex, qreal value) |
168 | { |
169 | matrix[rowIndex * columns + columnIndex] = value; |
170 | } |
171 | |
172 | QT_END_NAMESPACE |
173 | |
174 | #endif // QSIMPLEX_P_H |
175 | |