--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/gui/graphicsview/qsimplex_p.h	Mon Jan 11 14:00:40 2010 +0000
@@ -0,0 +1,188 @@
+/****************************************************************************
+**
+** Copyright (C) 2009 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$
+** 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 Technology Preview License Agreement accompanying
+** this package.
+**
+** 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.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** If you have questions regarding the use of this file, please contact
+** Nokia at qt-info@nokia.com.
+**
+**
+**
+**
+**
+**
+**
+**
+** $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;
+    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<QSimplexVariable *, qreal> variables;
+    qreal constant;
+    Ratio ratio;
+
+    QPair<QSimplexVariable *, qreal> helper;
+    QSimplexVariable * artificial;
+
+#ifdef QT_DEBUG
+    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 (qFuzzyCompare(1000 + leftHandSide, 1000 + constant))
+            return true;
+
+        switch (ratio) {
+        case LessOrEqual:
+            return leftHandSide < constant;
+        case MoreOrEqual:
+            return leftHandSide > constant;
+        default:
+            return false;
+        }
+    }
+#endif
+};
+
+class QSimplex
+{
+public:
+    QSimplex();
+    virtual ~QSimplex();
+
+    qreal solveMin();
+    qreal solveMax();
+    QList<QSimplexVariable *> constraintsVariables();
+
+    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
+    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 QList<QSimplexVariable *> 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