ConstraintSolver.hpp

Go to the documentation of this file.

//
//  CeresEngine - A game development framework
//
//  Created by Rogiel Sulzbach.
//  Copyright (c) 2018-2023 Rogiel Sulzbach. All rights reserved.
//
 
#pragma once
 
#include "Constraint.hpp"
#include "ConstraintError.hpp"
#include "ConstraintExpression.hpp"
#include "ConstraintVariable.hpp"
 
#include "CeresEngine/Foundation/Container/InitializerList.hpp"
#include "CeresEngine/Foundation/Container/SmallFlatMap.hpp"
#include "CeresEngine/Foundation/Container/Span.hpp"
 
#include <algorithm>
#include <limits>
#include <memory>
#include <vector>
 
namespace CeresEngine::Constraint {
 
    class ConstraintSolver {
        template<typename K, typename V, typename C = std::less<K>, typename A = DefaultAllocator> using MapType = SmallFlatMap<K, V, 0, C, A>;
 
        using SymbolID = UInt64;
 
        class Symbol {
        public:
            using ID = SymbolID;
 
            enum Type {
                Invalid,
                External,
                Slack,
                Error,
                Dummy
            };
 
        private:
            ID mID;
            Type mType;
 
        public:
            Symbol() : mID(0), mType(Invalid) {}
            Symbol(const Type type, const ID id) : mID(id), mType(type) {}
            ~Symbol() = default;
 
        public:
            ID id() const { return mID; }
            Type type() const { return mType; }
 
            friend bool operator<(const Symbol& lhs, const Symbol& rhs) { return lhs.mID < rhs.mID; }
            friend bool operator==(const Symbol& lhs, const Symbol& rhs) { return lhs.mID == rhs.mID; }
        };
 
        class Row {
        public:
            using CellMap = MapType<Symbol, double>;
 
        private:
            CellMap mCells;
            double mConstant;
 
        public:
            Row() : Row(0.0) {}
            Row(const double constant) : mConstant(constant) {}
            Row(const Row& other) = default;
            ~Row() = default;
 
        public:
            [[nodiscard]] const CellMap& getCells() const { return mCells; }
 
            [[nodiscard]] double getConstant() const { return mConstant; }
 
        public:
            double add(double value);
 
            void insert(const Symbol& symbol, double coefficient = 1.0);
 
            void insert(const Row& other, double coefficient = 1.0);
 
            void remove(const Symbol& symbol);
 
            void reverseSign();
 
            void solveFor(const Symbol& symbol);
 
            void solveFor(const Symbol& lhs, const Symbol& rhs);
 
            [[nodiscard]] double coefficientFor(const Symbol& symbol) const;
 
            void substitute(const Symbol& symbol, const Row& row);
        };
 
        struct Tag {
            Symbol marker;
            Symbol other;
        };
 
        struct EditInfo {
            Tag tag;
 
            Constraint constraint;
 
            double constant;
        };
 
        using VarMap = MapType<ConstraintVariable, Symbol>;
        using RowMap = MapType<Symbol, Row*>;
        using ConstaintMap = MapType<Constraint, Tag>;
        using EditMap = MapType<ConstraintVariable, EditInfo>;
 
        struct DualOptimizeGuard {
            explicit DualOptimizeGuard(ConstraintSolver& impl) : mSolver(impl) {}
            ~DualOptimizeGuard() { mSolver.dualOptimize(); }
            ConstraintSolver& mSolver;
        };
 
        ConstaintMap mConstraints;
        RowMap mRows;
        VarMap mVariables;
        EditMap mEditVariables;
 
        Vector<Symbol> mInfeasibleRows;
        UPtr<Row> mObjective;
        UPtr<Row> mArtificial;
        SymbolID mNextID;
 
        bool mAutoSolve = false;
 
    public:
        ConstraintSolver() : mObjective(new Row()), mNextID(1) {}
 
        ConstraintSolver(const ConstraintSolver&) = delete;
        ConstraintSolver& operator=(const ConstraintSolver&) = delete;
        ConstraintSolver(ConstraintSolver&&) = delete;
        ConstraintSolver& operator=(ConstraintSolver&&) = delete;
 
        ~ConstraintSolver() { clearRows(); }
 
    public: // Constraints
        void addConstraint(const Constraint& constraint);
 
        void addConstraints(const Span<const Constraint>& constraints) {
            for(const Constraint& constraint : constraints) {
                addConstraint(constraint);
            }
        }
 
        void addConstraints(const InitializerList<Constraint> constraints) {
            for(const Constraint& constraint : constraints) {
                addConstraint(constraint);
            }
        }
 
        void removeConstraint(const Constraint& constraint);
 
        void removeConstraints(const Span<const Constraint>& constraints) {
            for(const Constraint& constraint : constraints) {
                removeConstraint(constraint);
            }
        }
 
        void removeConstraints(const InitializerList<Constraint> constraints) {
            for(const Constraint& constraint : constraints) {
                removeConstraint(constraint);
            }
        }
 
        [[nodiscard]] bool hasConstraint(const Constraint& constraint) const { return mConstraints.find(constraint) != mConstraints.end(); }
 
    public: // Edit Variables
        void addEditVariable(const ConstraintVariable& variable, const ConstraintStrength& strength);
 
        void removeEditVariable(const ConstraintVariable& variable);
 
        [[nodiscard]] bool hasEditVariable(const ConstraintVariable& variable) const { return mEditVariables.find(variable) != mEditVariables.end(); }
 
        void suggestValue(const ConstraintVariable& variable, double value);
 
    public: // Solving & State
        void updateVariables();
 
        void reset();
 
        void solve();
 
    private:
        struct RowDeleter {
            template<typename T> void operator()(T& pair) { delete pair.second; }
        };
 
        void clearRows() {
            std::for_each(mRows.begin(), mRows.end(), RowDeleter());
            mRows.clear();
        }
 
        [[nodiscard]] Symbol getVarSymbol(const ConstraintVariable& variable);
 
        [[nodiscard]] UPtr<Row> createRow(const Constraint& constraint, Tag& tag);
 
        [[nodiscard]] Symbol chooseSubject(const Row& row, const Tag& tag) const;
 
        [[nodiscard]] bool addWithArtificialVariable(const Row& row);
 
        void substitute(const Symbol& symbol, const Row& row);
 
        void optimize(const Row& objective);
 
        void dualOptimize();
 
        [[nodiscard]] Symbol getEnteringSymbol(const Row& objective) const;
 
        [[nodiscard]] Symbol getDualEnteringSymbol(const Row& row) const;
 
        [[nodiscard]] Symbol anyPivotableSymbol(const Row& row) const;
 
        [[nodiscard]] RowMap::iterator getLeavingRow(const Symbol& entering);
 
        [[nodiscard]] RowMap::iterator getMarkerLeavingRow(const Symbol& marker);
 
        void removeConstraintEffects(const Constraint& cn, const Tag& tag);
 
        void removeMarkerEffects(const Symbol& marker, const ConstraintStrength& strength);
 
        [[nodiscard]] bool allDummies(const Row& row) const;
    };
 
} // namespace CeresEngine::Constraint