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
22QT_REQUIRE_CONFIG(graphicsview);
23
24QT_BEGIN_NAMESPACE
25
26struct QSimplexVariable
27{
28 QSimplexVariable() : result(0), index(0) {}
29
30 qreal result;
31 int index;
32protected:
33 QT_DECLARE_RO5_SMF_AS_DEFAULTED(QSimplexVariable)
34};
35
36// "pure" QSimplexVariable without the protected destructor
37struct QConcreteSimplexVariable final : QSimplexVariable
38{
39};
40
41/*!
42 \internal
43
44 Representation of a LP constraint like:
45
46 (c1 * X1) + (c2 * X2) + ... = K
47 or <= K
48 or >= K
49
50 Where (ci, Xi) are the pairs in "variables" and K the real "constant".
51*/
52struct QSimplexConstraint final
53{
54 Q_DISABLE_COPY_MOVE(QSimplexConstraint)
55
56 QSimplexConstraint() : constant(0), ratio(Equal), artificial(nullptr) {}
57
58 enum Ratio {
59 LessOrEqual = 0,
60 Equal,
61 MoreOrEqual
62 };
63
64 QHash<QSimplexVariable *, qreal> variables;
65 qreal constant;
66 Ratio ratio;
67
68 std::pair<QConcreteSimplexVariable *, qreal> helper;
69 QConcreteSimplexVariable *artificial;
70
71 void invert();
72
73 bool isSatisfied() {
74 qreal leftHandSide(0);
75
76 for (auto iter = variables.cbegin(); iter != variables.cend(); ++iter) {
77 leftHandSide += iter.value() * iter.key()->result;
78 }
79
80 Q_ASSERT(constant > 0 || qFuzzyCompare(1, 1 + constant));
81
82 if ((leftHandSide == constant) || qAbs(t: leftHandSide - constant) < 0.0000001)
83 return true;
84
85 switch (ratio) {
86 case LessOrEqual:
87 return leftHandSide < constant;
88 case MoreOrEqual:
89 return leftHandSide > constant;
90 default:
91 return false;
92 }
93 }
94
95#ifdef QT_DEBUG
96 QString toString() {
97 QString result;
98 result += QString::fromLatin1(ba: "-- QSimplexConstraint %1 --").arg(a: quintptr(this), fieldWidth: 0, base: 16);
99
100 for (auto iter = variables.cbegin(); iter != variables.cend(); ++iter) {
101 result += QString::fromLatin1(ba: " %1 x %2").arg(a: iter.value()).arg(a: quintptr(iter.key()), fieldWidth: 0, base: 16);
102 }
103
104 switch (ratio) {
105 case LessOrEqual:
106 result += QString::fromLatin1(ba: " (less) <= %1").arg(a: constant);
107 break;
108 case MoreOrEqual:
109 result += QString::fromLatin1(ba: " (more) >= %1").arg(a: constant);
110 break;
111 default:
112 result += QString::fromLatin1(ba: " (eqal) == %1").arg(a: constant);
113 }
114
115 return result;
116 }
117#endif
118};
119
120class QSimplex final
121{
122 Q_DISABLE_COPY_MOVE(QSimplex)
123public:
124 QSimplex();
125 ~QSimplex();
126
127 qreal solveMin();
128 qreal solveMax();
129
130 bool setConstraints(const QList<QSimplexConstraint *> &constraints);
131 void setObjective(QSimplexConstraint *objective);
132
133 void dumpMatrix();
134
135private:
136 // Matrix handling
137 inline qreal valueAt(int row, int column);
138 inline void setValueAt(int row, int column, qreal value);
139 void clearRow(int rowIndex);
140 void clearColumns(int first, int last);
141 void combineRows(int toIndex, int fromIndex, qreal factor);
142
143 // Simplex
144 bool simplifyConstraints(QList<QSimplexConstraint *> *constraints);
145 int findPivotColumn();
146 int pivotRowForColumn(int column);
147 void reducedRowEchelon();
148 bool iterate();
149
150 // Helpers
151 void clearDataStructures();
152 void solveMaxHelper();
153 enum SolverFactor { Minimum = -1, Maximum = 1 };
154 qreal solver(SolverFactor factor);
155 void collectResults();
156
157 QList<QSimplexConstraint *> constraints;
158 QList<QSimplexVariable *> variables;
159 QSimplexConstraint *objective;
160
161 int rows;
162 int columns;
163 int firstArtificial;
164
165 qreal *matrix;
166};
167
168inline qreal QSimplex::valueAt(int rowIndex, int columnIndex)
169{
170 return matrix[rowIndex * columns + columnIndex];
171}
172
173inline void QSimplex::setValueAt(int rowIndex, int columnIndex, qreal value)
174{
175 matrix[rowIndex * columns + columnIndex] = value;
176}
177
178QT_END_NAMESPACE
179
180#endif // QSIMPLEX_P_H
181

source code of qtbase/src/widgets/graphicsview/qsimplex_p.h