diff options
Diffstat (limited to 'src/widgets/graphicsview/qsimplex_p.h')
| -rw-r--r-- | src/widgets/graphicsview/qsimplex_p.h | 208 |
1 files changed, 208 insertions, 0 deletions
diff --git a/src/widgets/graphicsview/qsimplex_p.h b/src/widgets/graphicsview/qsimplex_p.h new file mode 100644 index 0000000000..3df82c6ccf --- /dev/null +++ b/src/widgets/graphicsview/qsimplex_p.h @@ -0,0 +1,208 @@ +/**************************************************************************** +** +** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies). +** All rights reserved. +** Contact: Nokia Corporation (qt-info@nokia.com) +** +** This file is part of the QtGui module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** GNU Lesser General Public License Usage +** This file may be used under the terms of the GNU Lesser General Public +** License version 2.1 as published by the Free Software Foundation and +** appearing in the file LICENSE.LGPL included in the packaging of this +** file. Please review the following information to ensure the GNU Lesser +** General Public License version 2.1 requirements will be met: +** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +** +** In addition, as a special exception, Nokia gives you certain additional +** rights. These rights are described in the Nokia Qt LGPL Exception +** version 1.1, included in the file LGPL_EXCEPTION.txt in this package. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU General +** Public License version 3.0 as published by the Free Software Foundation +** and appearing in the file LICENSE.GPL included in the packaging of this +** file. Please review the following information to ensure the GNU General +** Public License version 3.0 requirements will be met: +** http://www.gnu.org/copyleft/gpl.html. +** +** Other Usage +** Alternatively, this file may be used in accordance with the terms and +** conditions contained in a signed written agreement between you and Nokia. +** +** +** +** +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#ifndef QSIMPLEX_P_H +#define QSIMPLEX_P_H + +// +// W A R N I N G +// ------------- +// +// This file is not part of the Qt API. It exists purely as an +// implementation detail. This header file may change from version to +// version without notice, or even be removed. +// +// We mean it. +// + +#include <QtCore/qhash.h> +#include <QtCore/qpair.h> + +QT_BEGIN_NAMESPACE + +struct QSimplexVariable +{ + QSimplexVariable() : result(0), index(0) {} + + qreal result; + int index; +}; + + +/*! + \internal + + Representation of a LP constraint like: + + (c1 * X1) + (c2 * X2) + ... = K + or <= K + or >= K + + Where (ci, Xi) are the pairs in "variables" and K the real "constant". +*/ +struct QSimplexConstraint +{ + QSimplexConstraint() : constant(0), ratio(Equal), artificial(0) {} + + enum Ratio { + LessOrEqual = 0, + Equal, + MoreOrEqual + }; + + QHash<QSimplexVariable *, qreal> variables; + qreal constant; + Ratio ratio; + + QPair<QSimplexVariable *, qreal> helper; + QSimplexVariable * artificial; + + void invert(); + + bool isSatisfied() { + qreal leftHandSide(0); + + QHash<QSimplexVariable *, qreal>::const_iterator iter; + for (iter = variables.constBegin(); iter != variables.constEnd(); ++iter) { + leftHandSide += iter.value() * iter.key()->result; + } + + Q_ASSERT(constant > 0 || qFuzzyCompare(1, 1 + constant)); + + if ((leftHandSide == constant) || qAbs(leftHandSide - constant) < 0.0000001) + return true; + + switch (ratio) { + case LessOrEqual: + return leftHandSide < constant; + case MoreOrEqual: + return leftHandSide > constant; + default: + return false; + } + } + +#ifdef QT_DEBUG + QString toString() { + QString result; + result += QString::fromAscii("-- QSimplexConstraint %1 --").arg(quintptr(this), 0, 16); + + QHash<QSimplexVariable *, qreal>::const_iterator iter; + for (iter = variables.constBegin(); iter != variables.constEnd(); ++iter) { + result += QString::fromAscii(" %1 x %2").arg(iter.value()).arg(quintptr(iter.key()), 0, 16); + } + + switch (ratio) { + case LessOrEqual: + result += QString::fromAscii(" (less) <= %1").arg(constant); + break; + case MoreOrEqual: + result += QString::fromAscii(" (more) >= %1").arg(constant); + break; + default: + result += QString::fromAscii(" (eqal) == %1").arg(constant); + } + + return result; + } +#endif +}; + +class QSimplex +{ +public: + QSimplex(); + virtual ~QSimplex(); + + qreal solveMin(); + qreal solveMax(); + + bool setConstraints(const QList<QSimplexConstraint *> constraints); + void setObjective(QSimplexConstraint *objective); + + void dumpMatrix(); + +private: + // Matrix handling + qreal valueAt(int row, int column); + void setValueAt(int row, int column, qreal value); + void clearRow(int rowIndex); + void clearColumns(int first, int last); + void combineRows(int toIndex, int fromIndex, qreal factor); + + // Simplex + bool simplifyConstraints(QList<QSimplexConstraint *> *constraints); + int findPivotColumn(); + int pivotRowForColumn(int column); + void reducedRowEchelon(); + bool iterate(); + + // Helpers + void clearDataStructures(); + void solveMaxHelper(); + enum solverFactor { Minimum = -1, Maximum = 1 }; + qreal solver(solverFactor factor); + void collectResults(); + + QList<QSimplexConstraint *> constraints; + QList<QSimplexVariable *> variables; + QSimplexConstraint *objective; + + int rows; + int columns; + int firstArtificial; + + qreal *matrix; +}; + +inline qreal QSimplex::valueAt(int rowIndex, int columnIndex) +{ + return matrix[rowIndex * columns + columnIndex]; +} + +inline void QSimplex::setValueAt(int rowIndex, int columnIndex, qreal value) +{ + matrix[rowIndex * columns + columnIndex] = value; +} + +QT_END_NAMESPACE + +#endif // QSIMPLEX_P_H |