1/****************************************************************************
2**
3** Copyright (C) 2016 The Qt Company Ltd.
4** Contact: https://www.qt.io/licensing/
5**
6** This file is part of the QtWidgets module of the Qt Toolkit.
7**
8** $QT_BEGIN_LICENSE:LGPL$
9** Commercial License Usage
10** Licensees holding valid commercial Qt licenses may use this file in
11** accordance with the commercial license agreement provided with the
12** Software or, alternatively, in accordance with the terms contained in
13** a written agreement between you and The Qt Company. For licensing terms
14** and conditions see https://www.qt.io/terms-conditions. For further
15** information use the contact form at https://www.qt.io/contact-us.
16**
17** GNU Lesser General Public License Usage
18** Alternatively, this file may be used under the terms of the GNU Lesser
19** General Public License version 3 as published by the Free Software
20** Foundation and appearing in the file LICENSE.LGPL3 included in the
21** packaging of this file. Please review the following information to
22** ensure the GNU Lesser General Public License version 3 requirements
23** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
24**
25** GNU General Public License Usage
26** Alternatively, this file may be used under the terms of the GNU
27** General Public License version 2.0 or (at your option) the GNU General
28** Public license version 3 or any later version approved by the KDE Free
29** Qt Foundation. The licenses are as published by the Free Software
30** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
31** included in the packaging of this file. Please review the following
32** information to ensure the GNU General Public License requirements will
33** be met: https://www.gnu.org/licenses/gpl-2.0.html and
34** https://www.gnu.org/licenses/gpl-3.0.html.
35**
36** $QT_END_LICENSE$
37**
38****************************************************************************/
39
40#ifndef QSIMPLEX_P_H
41#define QSIMPLEX_P_H
42
43//
44// W A R N I N G
45// -------------
46//
47// This file is not part of the Qt API. It exists purely as an
48// implementation detail. This header file may change from version to
49// version without notice, or even be removed.
50//
51// We mean it.
52//
53
54#include <QtWidgets/private/qtwidgetsglobal_p.h>
55#include <QtCore/qhash.h>
56#include <QtCore/qpair.h>
57#include <QtCore/qstring.h>
58
59QT_REQUIRE_CONFIG(graphicsview);
60
61QT_BEGIN_NAMESPACE
62
63struct QSimplexVariable
64{
65 QSimplexVariable() : result(0), index(0) {}
66
67 qreal result;
68 int index;
69};
70
71
72/*!
73 \internal
74
75 Representation of a LP constraint like:
76
77 (c1 * X1) + (c2 * X2) + ... = K
78 or <= K
79 or >= K
80
81 Where (ci, Xi) are the pairs in "variables" and K the real "constant".
82*/
83struct QSimplexConstraint
84{
85 QSimplexConstraint() : constant(0), ratio(Equal), artificial(nullptr) {}
86
87 enum Ratio {
88 LessOrEqual = 0,
89 Equal,
90 MoreOrEqual
91 };
92
93 QHash<QSimplexVariable *, qreal> variables;
94 qreal constant;
95 Ratio ratio;
96
97 QPair<QSimplexVariable *, qreal> helper;
98 QSimplexVariable * artificial;
99
100 void invert();
101
102 bool isSatisfied() {
103 qreal leftHandSide(0);
104
105 QHash<QSimplexVariable *, qreal>::const_iterator iter;
106 for (iter = variables.constBegin(); iter != variables.constEnd(); ++iter) {
107 leftHandSide += iter.value() * iter.key()->result;
108 }
109
110 Q_ASSERT(constant > 0 || qFuzzyCompare(1, 1 + constant));
111
112 if ((leftHandSide == constant) || qAbs(leftHandSide - constant) < 0.0000001)
113 return true;
114
115 switch (ratio) {
116 case LessOrEqual:
117 return leftHandSide < constant;
118 case MoreOrEqual:
119 return leftHandSide > constant;
120 default:
121 return false;
122 }
123 }
124
125#ifdef QT_DEBUG
126 QString toString() {
127 QString result;
128 result += QString::fromLatin1("-- QSimplexConstraint %1 --").arg(quintptr(this), 0, 16);
129
130 QHash<QSimplexVariable *, qreal>::const_iterator iter;
131 for (iter = variables.constBegin(); iter != variables.constEnd(); ++iter) {
132 result += QString::fromLatin1(" %1 x %2").arg(iter.value()).arg(quintptr(iter.key()), 0, 16);
133 }
134
135 switch (ratio) {
136 case LessOrEqual:
137 result += QString::fromLatin1(" (less) <= %1").arg(constant);
138 break;
139 case MoreOrEqual:
140 result += QString::fromLatin1(" (more) >= %1").arg(constant);
141 break;
142 default:
143 result += QString::fromLatin1(" (eqal) == %1").arg(constant);
144 }
145
146 return result;
147 }
148#endif
149};
150
151class QSimplex
152{
153 Q_DISABLE_COPY_MOVE(QSimplex)
154public:
155 QSimplex();
156 ~QSimplex();
157
158 qreal solveMin();
159 qreal solveMax();
160
161 bool setConstraints(const QList<QSimplexConstraint *> &constraints);
162 void setObjective(QSimplexConstraint *objective);
163
164 void dumpMatrix();
165
166private:
167 // Matrix handling
168 inline qreal valueAt(int row, int column);
169 inline void setValueAt(int row, int column, qreal value);
170 void clearRow(int rowIndex);
171 void clearColumns(int first, int last);
172 void combineRows(int toIndex, int fromIndex, qreal factor);
173
174 // Simplex
175 bool simplifyConstraints(QList<QSimplexConstraint *> *constraints);
176 int findPivotColumn();
177 int pivotRowForColumn(int column);
178 void reducedRowEchelon();
179 bool iterate();
180
181 // Helpers
182 void clearDataStructures();
183 void solveMaxHelper();
184 enum SolverFactor { Minimum = -1, Maximum = 1 };
185 qreal solver(SolverFactor factor);
186 void collectResults();
187
188 QList<QSimplexConstraint *> constraints;
189 QList<QSimplexVariable *> variables;
190 QSimplexConstraint *objective;
191
192 int rows;
193 int columns;
194 int firstArtificial;
195
196 qreal *matrix;
197};
198
199inline qreal QSimplex::valueAt(int rowIndex, int columnIndex)
200{
201 return matrix[rowIndex * columns + columnIndex];
202}
203
204inline void QSimplex::setValueAt(int rowIndex, int columnIndex, qreal value)
205{
206 matrix[rowIndex * columns + columnIndex] = value;
207}
208
209QT_END_NAMESPACE
210
211#endif // QSIMPLEX_P_H
212