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

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