/**************************************************************************** ** ** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). ** Contact: Nokia Corporation (qt-info@nokia.com) ** ** This file is part of the QtGui module of the Qt Toolkit. ** ** $QT_BEGIN_LICENSE:LGPL$ ** No Commercial Usage ** This file contains pre-release code and may not be distributed. ** You may use this file in accordance with the terms and conditions ** contained in the either Technology Preview License Agreement or the ** Beta Release License Agreement. ** ** GNU Lesser General Public License Usage ** Alternatively, 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.0, 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. ** ** If you are unsure which license is appropriate for your use, please ** contact the sales department at http://qt.nokia.com/contact. ** $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 #include QT_BEGIN_NAMESPACE struct QSimplexVariable { QSimplexVariable() : result(0), index(0) {}; qreal result; uint 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 variables; qreal constant; Ratio ratio; QPair helper; QSimplexVariable * artificial; }; class QSimplex { public: QSimplex(); virtual ~QSimplex(); qreal solveMin(); qreal solveMax(); QList constraintsVariables(); void setConstraints(const QList 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 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 constraints; QList variables; QSimplexConstraint *objective; int rows; int columns; int firstArtificial; qreal *matrix; }; inline QList QSimplex::constraintsVariables() { return variables; } 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