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;
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*/
46struct 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
114class QSimplex
115{
116 Q_DISABLE_COPY_MOVE(QSimplex)
117public:
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
129private:
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
162inline qreal QSimplex::valueAt(int rowIndex, int columnIndex)
163{
164 return matrix[rowIndex * columns + columnIndex];
165}
166
167inline void QSimplex::setValueAt(int rowIndex, int columnIndex, qreal value)
168{
169 matrix[rowIndex * columns + columnIndex] = value;
170}
171
172QT_END_NAMESPACE
173
174#endif // QSIMPLEX_P_H
175

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