diff options
author | shadchin <shadchin@yandex-team.com> | 2023-12-08 19:08:47 +0300 |
---|---|---|
committer | shadchin <shadchin@yandex-team.com> | 2023-12-08 21:18:32 +0300 |
commit | e3a0c1b6b1dd2cd3d968365fa2b25190ed007be3 (patch) | |
tree | ba2ccd40582e9ef3115419ee6b39d4dc3caf26db /contrib | |
parent | 76de0dedd83a5f085e6a1b7bbe01c08a38a62aab (diff) | |
download | ydb-e3a0c1b6b1dd2cd3d968365fa2b25190ed007be3.tar.gz |
Update kiwisolver to 1.3.2
Diffstat (limited to 'contrib')
21 files changed, 294 insertions, 247 deletions
diff --git a/contrib/python/kiwisolver/py3/.dist-info/METADATA b/contrib/python/kiwisolver/py3/.dist-info/METADATA index 5eb4a95c2d..fe462dc324 100644 --- a/contrib/python/kiwisolver/py3/.dist-info/METADATA +++ b/contrib/python/kiwisolver/py3/.dist-info/METADATA @@ -1,41 +1,48 @@ Metadata-Version: 2.1 Name: kiwisolver -Version: 1.2.0 +Version: 1.3.2 Summary: A fast implementation of the Cassowary constraint solver Home-page: https://github.com/nucleic/kiwi Author: The Nucleic Development Team Author-email: sccolbert@gmail.com License: BSD Platform: UNKNOWN +Classifier: License :: OSI Approved :: BSD License Classifier: Programming Language :: Python Classifier: Programming Language :: Python :: 3 -Classifier: Programming Language :: Python :: 3.6 Classifier: Programming Language :: Python :: 3.7 Classifier: Programming Language :: Python :: 3.8 +Classifier: Programming Language :: Python :: 3.9 +Classifier: Programming Language :: Python :: 3.10 Classifier: Programming Language :: Python :: Implementation :: CPython -Requires-Python: >=3.6 +Classifier: Programming Language :: Python :: Implementation :: PyPy +Requires-Python: >=3.7 +License-File: LICENSE Welcome to Kiwi =============== -.. image:: https://travis-ci.org/nucleic/kiwi.svg?branch=master +.. image:: https://travis-ci.org/nucleic/kiwi.svg?branch=main :target: https://travis-ci.org/nucleic/kiwi -.. image:: https://codecov.io/gh/nucleic/kiwi/branch/master/graph/badge.svg +.. image:: https://github.com/nucleic/kiwi/workflows/Continuous%20Integration/badge.svg + :target: https://github.com/nucleic/kiwi/actions +.. image:: https://github.com/nucleic/kiwi/workflows/Documentation%20building/badge.svg + :target: https://github.com/nucleic/kiwi/actions +.. image:: https://codecov.io/gh/nucleic/kiwi/branch/main/graph/badge.svg :target: https://codecov.io/gh/nucleic/kiwi .. image:: https://readthedocs.org/projects/kiwisolver/badge/?version=latest :target: https://kiwisolver.readthedocs.io/en/latest/?badge=latest :alt: Documentation Status Kiwi is an efficient C++ implementation of the Cassowary constraint solving -algorithm. Kiwi is an implementation of the algorithm based on the seminal -Cassowary paper. It is *not* a refactoring of the original C++ solver. Kiwi -has been designed from the ground up to be lightweight and fast. Kiwi ranges -from 10x to 500x faster than the original Cassowary solver with typical use -cases gaining a 40x improvement. Memory savings are consistently > 5x. +algorithm. Kiwi is an implementation of the algorithm based on the +`seminal Cassowary paper <https://constraints.cs.washington.edu/solvers/cassowary-tochi.pdf>`_. +It is *not* a refactoring of the original C++ solver. Kiwi has been designed +from the ground up to be lightweight and fast. Kiwi ranges from 10x to 500x +faster than the original Cassowary solver with typical usecases gaining a 40x +improvement. Memory savings are consistently > 5x. -In addition to the C++ solver, Kiwi ships with hand-rolled Python bindings. - -The version 1.1.0 of the Python bindings will be the last one to support -Python 2, moving forward support will be limited to Python 3.5+. +In addition to the C++ solver, Kiwi ships with hand-rolled Python bindings for +Python 3.7+. diff --git a/contrib/python/kiwisolver/py3/README.rst b/contrib/python/kiwisolver/py3/README.rst index 98dabebefe..f98b3fb3a2 100644 --- a/contrib/python/kiwisolver/py3/README.rst +++ b/contrib/python/kiwisolver/py3/README.rst @@ -1,22 +1,25 @@ Welcome to Kiwi =============== -.. image:: https://travis-ci.org/nucleic/kiwi.svg?branch=master +.. image:: https://travis-ci.org/nucleic/kiwi.svg?branch=main :target: https://travis-ci.org/nucleic/kiwi -.. image:: https://codecov.io/gh/nucleic/kiwi/branch/master/graph/badge.svg +.. image:: https://github.com/nucleic/kiwi/workflows/Continuous%20Integration/badge.svg + :target: https://github.com/nucleic/kiwi/actions +.. image:: https://github.com/nucleic/kiwi/workflows/Documentation%20building/badge.svg + :target: https://github.com/nucleic/kiwi/actions +.. image:: https://codecov.io/gh/nucleic/kiwi/branch/main/graph/badge.svg :target: https://codecov.io/gh/nucleic/kiwi .. image:: https://readthedocs.org/projects/kiwisolver/badge/?version=latest :target: https://kiwisolver.readthedocs.io/en/latest/?badge=latest :alt: Documentation Status Kiwi is an efficient C++ implementation of the Cassowary constraint solving -algorithm. Kiwi is an implementation of the algorithm based on the seminal -Cassowary paper. It is *not* a refactoring of the original C++ solver. Kiwi -has been designed from the ground up to be lightweight and fast. Kiwi ranges -from 10x to 500x faster than the original Cassowary solver with typical use -cases gaining a 40x improvement. Memory savings are consistently > 5x. +algorithm. Kiwi is an implementation of the algorithm based on the +`seminal Cassowary paper <https://constraints.cs.washington.edu/solvers/cassowary-tochi.pdf>`_. +It is *not* a refactoring of the original C++ solver. Kiwi has been designed +from the ground up to be lightweight and fast. Kiwi ranges from 10x to 500x +faster than the original Cassowary solver with typical usecases gaining a 40x +improvement. Memory savings are consistently > 5x. -In addition to the C++ solver, Kiwi ships with hand-rolled Python bindings. - -The version 1.1.0 of the Python bindings will be the last one to support -Python 2, moving forward support will be limited to Python 3.5+. +In addition to the C++ solver, Kiwi ships with hand-rolled Python bindings for +Python 3.7+. diff --git a/contrib/python/kiwisolver/py3/kiwi/constraint.h b/contrib/python/kiwisolver/py3/kiwi/constraint.h index 9d8322b94d..bc9c415b0b 100644 --- a/contrib/python/kiwisolver/py3/kiwi/constraint.h +++ b/contrib/python/kiwisolver/py3/kiwi/constraint.h @@ -28,7 +28,7 @@ class Constraint { public: - Constraint() : m_data(0) {} + Constraint() = default; Constraint(const Expression &expr, RelationalOperator op, @@ -36,7 +36,11 @@ public: Constraint(const Constraint &other, double strength) : m_data(new ConstraintData(other, strength)) {} - ~Constraint() {} + Constraint(const Constraint &) = default; + + Constraint(Constraint &&) noexcept = default; + + ~Constraint() = default; const Expression &expression() const { @@ -58,16 +62,19 @@ public: return !m_data; } + Constraint& operator=(const Constraint &) = default; + + Constraint& operator=(Constraint &&) noexcept = default; + private: static Expression reduce(const Expression &expr) { std::map<Variable, double> vars; - typedef std::vector<Term>::const_iterator iter_t; - iter_t end = expr.terms().end(); - for (iter_t it = expr.terms().begin(); it != end; ++it) - vars[it->variable()] += it->coefficient(); + for (const auto & term : expr.terms()) + vars[term.variable()] += term.coefficient(); + std::vector<Term> terms(vars.begin(), vars.end()); - return Expression(terms, expr.constant()); + return Expression(std::move(terms), expr.constant()); } class ConstraintData : public SharedData @@ -86,7 +93,7 @@ private: m_strength(strength::clip(strength)), m_op(other.op()) {} - ~ConstraintData() {} + ~ConstraintData() = default; Expression m_expression; double m_strength; diff --git a/contrib/python/kiwisolver/py3/kiwi/debug.h b/contrib/python/kiwisolver/py3/kiwi/debug.h index 0d86091b25..f2b29b4dbe 100644 --- a/contrib/python/kiwisolver/py3/kiwi/debug.h +++ b/contrib/python/kiwisolver/py3/kiwi/debug.h @@ -54,64 +54,51 @@ public: static void dump(const SolverImpl::RowMap &rows, std::ostream &out) { - typedef SolverImpl::RowMap::const_iterator iter_t; - iter_t end = rows.end(); - for (iter_t it = rows.begin(); it != end; ++it) + for (const auto &rowPair : rows) { - dump(it->first, out); + dump(rowPair.first, out); out << " | "; - dump(*it->second, out); + dump(*rowPair.second, out); } } static void dump(const std::vector<Symbol> &symbols, std::ostream &out) { - typedef std::vector<Symbol>::const_iterator iter_t; - iter_t end = symbols.end(); - for (iter_t it = symbols.begin(); it != end; ++it) + for (const auto &symbol : symbols) { - dump(*it, out); + dump(symbol, out); out << std::endl; } } static void dump(const SolverImpl::VarMap &vars, std::ostream &out) { - typedef SolverImpl::VarMap::const_iterator iter_t; - iter_t end = vars.end(); - for (iter_t it = vars.begin(); it != end; ++it) + for (const auto &varPair : vars) { - out << it->first.name() << " = "; - dump(it->second, out); + out << varPair.first.name() << " = "; + dump(varPair.second, out); out << std::endl; } } static void dump(const SolverImpl::CnMap &cns, std::ostream &out) { - typedef SolverImpl::CnMap::const_iterator iter_t; - iter_t end = cns.end(); - for (iter_t it = cns.begin(); it != end; ++it) - dump(it->first, out); + for (const auto &cnPair : cns) + dump(cnPair.first, out); } static void dump(const SolverImpl::EditMap &edits, std::ostream &out) { - typedef SolverImpl::EditMap::const_iterator iter_t; - iter_t end = edits.end(); - for (iter_t it = edits.begin(); it != end; ++it) - out << it->first.name() << std::endl; + for (const auto &editPair : edits) + out << editPair.first.name() << std::endl; } static void dump(const Row &row, std::ostream &out) { - typedef Row::CellMap::const_iterator iter_t; - out << row.constant(); - iter_t end = row.cells().end(); - for (iter_t it = row.cells().begin(); it != end; ++it) + for (const auto &rowPair : row.cells()) { - out << " + " << it->second << " * "; - dump(it->first, out); + out << " + " << rowPair.second << " * "; + dump(rowPair.first, out); } out << std::endl; } @@ -143,13 +130,10 @@ public: static void dump(const Constraint &cn, std::ostream &out) { - typedef std::vector<Term>::const_iterator iter_t; - iter_t begin = cn.expression().terms().begin(); - iter_t end = cn.expression().terms().end(); - for (iter_t it = begin; it != end; ++it) + for (const auto &term : cn.expression().terms()) { - out << it->coefficient() << " * "; - out << it->variable().name() << " + "; + out << term.coefficient() << " * "; + out << term.variable().name() << " + "; } out << cn.expression().constant(); switch (cn.op()) diff --git a/contrib/python/kiwisolver/py3/kiwi/errors.h b/contrib/python/kiwisolver/py3/kiwi/errors.h index eb54560f4e..fd3919f07f 100644 --- a/contrib/python/kiwisolver/py3/kiwi/errors.h +++ b/contrib/python/kiwisolver/py3/kiwi/errors.h @@ -18,11 +18,11 @@ class UnsatisfiableConstraint : public std::exception { public: - UnsatisfiableConstraint(const Constraint &constraint) : m_constraint(constraint) {} + UnsatisfiableConstraint(Constraint constraint) : m_constraint(std::move(constraint)) {} - ~UnsatisfiableConstraint() throw() {} + ~UnsatisfiableConstraint() noexcept {} - const char *what() const throw() + const char *what() const noexcept { return "The constraint can not be satisfied."; } @@ -40,11 +40,11 @@ class UnknownConstraint : public std::exception { public: - UnknownConstraint(const Constraint &constraint) : m_constraint(constraint) {} + UnknownConstraint(Constraint constraint) : m_constraint(std::move(constraint)) {} - ~UnknownConstraint() throw() {} + ~UnknownConstraint() noexcept {} - const char *what() const throw() + const char *what() const noexcept { return "The constraint has not been added to the solver."; } @@ -62,11 +62,11 @@ class DuplicateConstraint : public std::exception { public: - DuplicateConstraint(const Constraint &constraint) : m_constraint(constraint) {} + DuplicateConstraint(Constraint constraint) : m_constraint(std::move(constraint)) {} - ~DuplicateConstraint() throw() {} + ~DuplicateConstraint() noexcept {} - const char *what() const throw() + const char *what() const noexcept { return "The constraint has already been added to the solver."; } @@ -84,11 +84,11 @@ class UnknownEditVariable : public std::exception { public: - UnknownEditVariable(const Variable &variable) : m_variable(variable) {} + UnknownEditVariable(Variable variable) : m_variable(std::move(variable)) {} - ~UnknownEditVariable() throw() {} + ~UnknownEditVariable() noexcept {} - const char *what() const throw() + const char *what() const noexcept { return "The edit variable has not been added to the solver."; } @@ -106,11 +106,11 @@ class DuplicateEditVariable : public std::exception { public: - DuplicateEditVariable(const Variable &variable) : m_variable(variable) {} + DuplicateEditVariable(Variable variable) : m_variable(std::move(variable)) {} - ~DuplicateEditVariable() throw() {} + ~DuplicateEditVariable() noexcept {} - const char *what() const throw() + const char *what() const noexcept { return "The edit variable has already been added to the solver."; } @@ -130,9 +130,9 @@ class BadRequiredStrength : public std::exception public: BadRequiredStrength() {} - ~BadRequiredStrength() throw() {} + ~BadRequiredStrength() noexcept {} - const char *what() const throw() + const char *what() const noexcept { return "A required strength cannot be used in this context."; } @@ -146,11 +146,11 @@ public: InternalSolverError(const char *msg) : m_msg(msg) {} - InternalSolverError(const std::string &msg) : m_msg(msg) {} + InternalSolverError(std::string msg) : m_msg(std::move(msg)) {} - ~InternalSolverError() throw() {} + ~InternalSolverError() noexcept {} - const char *what() const throw() + const char *what() const noexcept { return m_msg.c_str(); } diff --git a/contrib/python/kiwisolver/py3/kiwi/expression.h b/contrib/python/kiwisolver/py3/kiwi/expression.h index e2b5ae6683..20c8fd3e83 100644 --- a/contrib/python/kiwisolver/py3/kiwi/expression.h +++ b/contrib/python/kiwisolver/py3/kiwi/expression.h @@ -20,9 +20,14 @@ public: Expression(const Term &term, double constant = 0.0) : m_terms(1, term), m_constant(constant) {} - Expression(const std::vector<Term> &terms, double constant = 0.0) : m_terms(terms), m_constant(constant) {} + Expression(std::vector<Term> terms, double constant = 0.0) : m_terms(std::move(terms)), m_constant(constant) {} - ~Expression() {} + Expression(const Expression&) = default; + + // Could be marked noexcept but for a bug in the GCC of the manylinux1 image + Expression(Expression&&) = default; + + ~Expression() = default; const std::vector<Term> &terms() const { @@ -36,14 +41,19 @@ public: double value() const { - typedef std::vector<Term>::const_iterator iter_t; double result = m_constant; - iter_t end = m_terms.end(); - for (iter_t it = m_terms.begin(); it != end; ++it) - result += it->value(); + + for (const Term &term : m_terms) + result += term.value(); + return result; } + Expression& operator=(const Expression&) = default; + + // Could be marked noexcept but for a bug in the GCC of the manylinux1 image + Expression& operator=(Expression&&) = default; + private: std::vector<Term> m_terms; double m_constant; diff --git a/contrib/python/kiwisolver/py3/kiwi/row.h b/contrib/python/kiwisolver/py3/kiwi/row.h index 29b25135bb..b7da02fef7 100644 --- a/contrib/python/kiwisolver/py3/kiwi/row.h +++ b/contrib/python/kiwisolver/py3/kiwi/row.h @@ -20,15 +20,15 @@ class Row { public: - typedef MapType<Symbol, double> CellMap; + using CellMap = MapType<Symbol, double>; - Row() : m_constant(0.0) {} + Row() : Row(0.0) {} Row(double constant) : m_constant(constant) {} - Row(const Row &other) : m_cells(other.m_cells), m_constant(other.m_constant) {} + Row(const Row &other) = default; - ~Row() {} + ~Row() = default; const CellMap &cells() const { @@ -72,14 +72,13 @@ public: */ void insert(const Row &other, double coefficient = 1.0) { - typedef CellMap::const_iterator iter_t; m_constant += other.m_constant * coefficient; - iter_t end = other.m_cells.end(); - for (iter_t it = other.m_cells.begin(); it != end; ++it) + + for (const auto & cellPair : other.m_cells) { - double coeff = it->second * coefficient; - if (nearZero(m_cells[it->first] += coeff)) - m_cells.erase(it->first); + double coeff = cellPair.second * coefficient; + if (nearZero(m_cells[cellPair.first] += coeff)) + m_cells.erase(cellPair.first); } } @@ -88,7 +87,7 @@ public: */ void remove(const Symbol &symbol) { - CellMap::iterator it = m_cells.find(symbol); + auto it = m_cells.find(symbol); if (it != m_cells.end()) m_cells.erase(it); } @@ -98,11 +97,9 @@ public: */ void reverseSign() { - typedef CellMap::iterator iter_t; m_constant = -m_constant; - iter_t end = m_cells.end(); - for (iter_t it = m_cells.begin(); it != end; ++it) - it->second = -it->second; + for (auto &cellPair : m_cells) + cellPair.second = -cellPair.second; } /* Solve the row for the given symbol. @@ -118,13 +115,11 @@ public: */ void solveFor(const Symbol &symbol) { - typedef CellMap::iterator iter_t; double coeff = -1.0 / m_cells[symbol]; m_cells.erase(symbol); m_constant *= coeff; - iter_t end = m_cells.end(); - for (iter_t it = m_cells.begin(); it != end; ++it) - it->second *= coeff; + for (auto &cellPair : m_cells) + cellPair.second *= coeff; } /* Solve the row for the given symbols. @@ -168,8 +163,7 @@ public: */ void substitute(const Symbol &symbol, const Row &row) { - typedef CellMap::iterator iter_t; - iter_t it = m_cells.find(symbol); + auto it = m_cells.find(symbol); if (it != m_cells.end()) { double coefficient = it->second; diff --git a/contrib/python/kiwisolver/py3/kiwi/shareddata.h b/contrib/python/kiwisolver/py3/kiwi/shareddata.h index 9b1bc2c012..877bc02929 100644 --- a/contrib/python/kiwisolver/py3/kiwi/shareddata.h +++ b/contrib/python/kiwisolver/py3/kiwi/shareddata.h @@ -7,6 +7,16 @@ |----------------------------------------------------------------------------*/ #pragma once +/* +Implementation note +=================== +SharedDataPtr/SharedData offer the same basic functionality as std::shared_ptr, +but do not use atomic counters under the hood. +Since kiwi operates within a single thread context, atomic counters are not necessary, +especially given the extra CPU cost. +Therefore the use of SharedDataPtr/SharedData is preferred over std::shared_ptr. +*/ + namespace kiwi { @@ -16,12 +26,15 @@ class SharedData public: SharedData() : m_refcount(0) {} - SharedData(const SharedData &other) : m_refcount(0) {} + SharedData(const SharedData &other) = delete; + + SharedData(SharedData&& other) = delete; int m_refcount; -private: - SharedData &operator=(const SharedData &other); + SharedData &operator=(const SharedData &other) = delete; + + SharedData &operator=(SharedData&& other) = delete; }; template <typename T> @@ -29,9 +42,9 @@ class SharedDataPtr { public: - typedef T Type; + using Type = T; - SharedDataPtr() : m_data(0) {} + SharedDataPtr() : m_data(nullptr) {} explicit SharedDataPtr(T *data) : m_data(data) { @@ -108,6 +121,11 @@ public: incref(m_data); } + SharedDataPtr(SharedDataPtr&& other) noexcept : m_data(other.m_data) + { + other.m_data = nullptr; + } + SharedDataPtr<T> &operator=(const SharedDataPtr<T> &other) { if (m_data != other.m_data) @@ -120,6 +138,18 @@ public: return *this; } + SharedDataPtr<T>& operator=(SharedDataPtr<T>&& other) noexcept + { + if (m_data != other.m_data) + { + decref(m_data); + + m_data = other.m_data; + other.m_data = nullptr; + } + return *this; + } + SharedDataPtr<T> &operator=(T *other) { if (m_data != other) diff --git a/contrib/python/kiwisolver/py3/kiwi/solver.h b/contrib/python/kiwisolver/py3/kiwi/solver.h index 678df8ac75..8ff2dbb374 100644 --- a/contrib/python/kiwisolver/py3/kiwi/solver.h +++ b/contrib/python/kiwisolver/py3/kiwi/solver.h @@ -21,9 +21,9 @@ class Solver public: - Solver() {} + Solver() = default; - ~Solver() {} + ~Solver() = default; /* Add a constraint to the solver. diff --git a/contrib/python/kiwisolver/py3/kiwi/solverimpl.h b/contrib/python/kiwisolver/py3/kiwi/solverimpl.h index bb6690aeb8..c1960fcb7e 100644 --- a/contrib/python/kiwisolver/py3/kiwi/solverimpl.h +++ b/contrib/python/kiwisolver/py3/kiwi/solverimpl.h @@ -44,13 +44,13 @@ class SolverImpl double constant; }; - typedef MapType<Variable, Symbol> VarMap; + using VarMap = MapType<Variable, Symbol>; - typedef MapType<Symbol, Row*> RowMap; + using RowMap = MapType<Symbol, Row*>; - typedef MapType<Constraint, Tag> CnMap; + using CnMap = MapType<Constraint, Tag>; - typedef MapType<Variable, EditInfo> EditMap; + using EditMap = MapType<Variable, EditInfo>; struct DualOptimizeGuard { @@ -63,6 +63,10 @@ public: SolverImpl() : m_objective( new Row() ), m_id_tick( 1 ) {} + SolverImpl( const SolverImpl& ) = delete; + + SolverImpl( SolverImpl&& ) = delete; + ~SolverImpl() { clearRows(); } /* Add a constraint to the solver. @@ -138,7 +142,7 @@ public: */ void removeConstraint( const Constraint& constraint ) { - CnMap::iterator cn_it = m_cns.find( constraint ); + auto cn_it = m_cns.find( constraint ); if( cn_it == m_cns.end() ) throw UnknownConstraint( constraint ); @@ -152,7 +156,7 @@ public: // If the marker is basic, simply drop the row. Otherwise, // pivot the marker into the basis and then drop the row. - RowMap::iterator row_it = m_rows.find( tag.marker ); + auto row_it = m_rows.find( tag.marker ); if( row_it != m_rows.end() ) { std::unique_ptr<Row> rowptr( row_it->second ); @@ -224,7 +228,7 @@ public: */ void removeEditVariable( const Variable& variable ) { - EditMap::iterator it = m_edits.find( variable ); + auto it = m_edits.find( variable ); if( it == m_edits.end() ) throw UnknownEditVariable( variable ); removeConstraint( it->second.constraint ); @@ -252,7 +256,7 @@ public: */ void suggestValue( const Variable& variable, double value ) { - EditMap::iterator it = m_edits.find( variable ); + auto it = m_edits.find( variable ); if( it == m_edits.end() ) throw UnknownEditVariable( variable ); @@ -262,7 +266,7 @@ public: info.constant = value; // Check first if the positive error variable is basic. - RowMap::iterator row_it = m_rows.find( info.tag.marker ); + auto row_it = m_rows.find( info.tag.marker ); if( row_it != m_rows.end() ) { if( row_it->second->add( -delta ) < 0.0 ) @@ -280,14 +284,13 @@ public: } // Otherwise update each row where the error variables exist. - RowMap::iterator end = m_rows.end(); - for( row_it = m_rows.begin(); row_it != end; ++row_it ) + for (const auto & rowPair : m_rows) { - double coeff = row_it->second->coefficientFor( info.tag.marker ); + double coeff = rowPair.second->coefficientFor( info.tag.marker ); if( coeff != 0.0 && - row_it->second->add( delta * coeff ) < 0.0 && - row_it->first.type() != Symbol::External ) - m_infeasible_rows.push_back( row_it->first ); + rowPair.second->add( delta * coeff ) < 0.0 && + rowPair.first.type() != Symbol::External ) + m_infeasible_rows.push_back( rowPair.first ); } } @@ -296,14 +299,12 @@ public: */ void updateVariables() { - typedef RowMap::iterator row_iter_t; - typedef VarMap::iterator var_iter_t; - row_iter_t row_end = m_rows.end(); - var_iter_t var_end = m_vars.end(); - for( var_iter_t var_it = m_vars.begin(); var_it != var_end; ++var_it ) + auto row_end = m_rows.end(); + + for (auto &varPair : m_vars) { - Variable& var( const_cast<Variable&>( var_it->first ) ); - row_iter_t row_it = m_rows.find( var_it->second ); + Variable& var = varPair.first; + auto row_it = m_rows.find( varPair.second ); if( row_it == row_end ) var.setValue( 0.0 ); else @@ -332,11 +333,11 @@ public: m_id_tick = 1; } -private: + SolverImpl& operator=( const SolverImpl& ) = delete; - SolverImpl( const SolverImpl& ); + SolverImpl& operator=( SolverImpl&& ) = delete; - SolverImpl& operator=( const SolverImpl& ); +private: struct RowDeleter { @@ -357,7 +358,7 @@ private: */ Symbol getVarSymbol( const Variable& variable ) { - VarMap::iterator it = m_vars.find( variable ); + auto it = m_vars.find( variable ); if( it != m_vars.end() ) return it->second; Symbol symbol( Symbol::External, m_id_tick++ ); @@ -382,24 +383,22 @@ private: for tracking the movement of the constraint in the tableau. */ - Row* createRow( const Constraint& constraint, Tag& tag ) + std::unique_ptr<Row> createRow( const Constraint& constraint, Tag& tag ) { - typedef std::vector<Term>::const_iterator iter_t; const Expression& expr( constraint.expression() ); - Row* row = new Row( expr.constant() ); + std::unique_ptr<Row> row( new Row( expr.constant() ) ); // Substitute the current basic variables into the row. - iter_t end = expr.terms().end(); - for( iter_t it = expr.terms().begin(); it != end; ++it ) + for (const auto &term : expr.terms()) { - if( !nearZero( it->coefficient() ) ) + if( !nearZero( term.coefficient() ) ) { - Symbol symbol( getVarSymbol( it->variable() ) ); - RowMap::const_iterator row_it = m_rows.find( symbol ); + Symbol symbol( getVarSymbol( term.variable() ) ); + auto row_it = m_rows.find( symbol ); if( row_it != m_rows.end() ) - row->insert( *row_it->second, it->coefficient() ); + row->insert( *row_it->second, term.coefficient() ); else - row->insert( symbol, it->coefficient() ); + row->insert( symbol, term.coefficient() ); } } @@ -466,14 +465,12 @@ private: If a subject cannot be found, an invalid symbol will be returned. */ - Symbol chooseSubject( const Row& row, const Tag& tag ) + Symbol chooseSubject( const Row& row, const Tag& tag ) const { - typedef Row::CellMap::const_iterator iter_t; - iter_t end = row.cells().end(); - for( iter_t it = row.cells().begin(); it != end; ++it ) + for (const auto &cellPair : row.cells()) { - if( it->first.type() == Symbol::External ) - return it->first; + if( cellPair.first.type() == Symbol::External ) + return cellPair.first; } if( tag.marker.type() == Symbol::Slack || tag.marker.type() == Symbol::Error ) { @@ -508,7 +505,7 @@ private: // If the artificial variable is not basic, pivot the row so that // it becomes basic. If the row is constant, exit early. - RowMap::iterator it = m_rows.find( art ); + auto it = m_rows.find( art ); if( it != m_rows.end() ) { std::unique_ptr<Row> rowptr( it->second ); @@ -524,9 +521,9 @@ private: } // Remove the artificial variable from the tableau. - RowMap::iterator end = m_rows.end(); - for( it = m_rows.begin(); it != end; ++it ) - it->second->remove( art ); + for (auto &rowPair : m_rows) + rowPair.second->remove(art); + m_objective->remove( art ); return success; } @@ -539,14 +536,12 @@ private: */ void substitute( const Symbol& symbol, const Row& row ) { - typedef RowMap::iterator iter_t; - iter_t end = m_rows.end(); - for( iter_t it = m_rows.begin(); it != end; ++it ) + for( auto& rowPair : m_rows ) { - it->second->substitute( symbol, row ); - if( it->first.type() != Symbol::External && - it->second->constant() < 0.0 ) - m_infeasible_rows.push_back( it->first ); + rowPair.second->substitute( symbol, row ); + if( rowPair.first.type() != Symbol::External && + rowPair.second->constant() < 0.0 ) + m_infeasible_rows.push_back( rowPair.first ); } m_objective->substitute( symbol, row ); if( m_artificial.get() ) @@ -571,7 +566,7 @@ private: Symbol entering( getEnteringSymbol( objective ) ); if( entering.type() == Symbol::Invalid ) return; - RowMap::iterator it = getLeavingRow( entering ); + auto it = getLeavingRow( entering ); if( it == m_rows.end() ) throw InternalSolverError( "The objective is unbounded." ); // pivot the entering symbol into the basis @@ -604,7 +599,7 @@ private: Symbol leaving( m_infeasible_rows.back() ); m_infeasible_rows.pop_back(); - RowMap::iterator it = m_rows.find( leaving ); + auto it = m_rows.find( leaving ); if( it != m_rows.end() && !nearZero( it->second->constant() ) && it->second->constant() < 0.0 ) { @@ -629,14 +624,12 @@ private: invalid symbol is returned. */ - Symbol getEnteringSymbol( const Row& objective ) + Symbol getEnteringSymbol( const Row& objective ) const { - typedef Row::CellMap::const_iterator iter_t; - iter_t end = objective.cells().end(); - for( iter_t it = objective.cells().begin(); it != end; ++it ) + for (const auto &cellPair : objective.cells()) { - if( it->first.type() != Symbol::Dummy && it->second < 0.0 ) - return it->first; + if( cellPair.first.type() != Symbol::Dummy && cellPair.second < 0.0 ) + return cellPair.first; } return Symbol(); } @@ -650,22 +643,20 @@ private: is returned. */ - Symbol getDualEnteringSymbol( const Row& row ) + Symbol getDualEnteringSymbol( const Row& row ) const { - typedef Row::CellMap::const_iterator iter_t; Symbol entering; double ratio = std::numeric_limits<double>::max(); - iter_t end = row.cells().end(); - for( iter_t it = row.cells().begin(); it != end; ++it ) + for (const auto &cellPair : row.cells()) { - if( it->second > 0.0 && it->first.type() != Symbol::Dummy ) + if( cellPair.second > 0.0 && cellPair.first.type() != Symbol::Dummy ) { - double coeff = m_objective->coefficientFor( it->first ); - double r = coeff / it->second; + double coeff = m_objective->coefficientFor( cellPair.first ); + double r = coeff / cellPair.second; if( r < ratio ) { ratio = r; - entering = it->first; + entering = cellPair.first; } } } @@ -677,13 +668,11 @@ private: If no such symbol is present, and Invalid symbol will be returned. */ - Symbol anyPivotableSymbol( const Row& row ) + Symbol anyPivotableSymbol( const Row& row ) const { - typedef Row::CellMap::const_iterator iter_t; - iter_t end = row.cells().end(); - for( iter_t it = row.cells().begin(); it != end; ++it ) + for (const auto &cellPair : row.cells()) { - const Symbol& sym( it->first ); + const Symbol& sym( cellPair.first ); if( sym.type() == Symbol::Slack || sym.type() == Symbol::Error ) return sym; } @@ -700,11 +689,10 @@ private: */ RowMap::iterator getLeavingRow( const Symbol& entering ) { - typedef RowMap::iterator iter_t; double ratio = std::numeric_limits<double>::max(); - iter_t end = m_rows.end(); - iter_t found = m_rows.end(); - for( iter_t it = m_rows.begin(); it != end; ++it ) + auto end = m_rows.end(); + auto found = m_rows.end(); + for( auto it = m_rows.begin(); it != end; ++it ) { if( it->first.type() != Symbol::External ) { @@ -745,14 +733,13 @@ private: RowMap::iterator getMarkerLeavingRow( const Symbol& marker ) { const double dmax = std::numeric_limits<double>::max(); - typedef RowMap::iterator iter_t; double r1 = dmax; double r2 = dmax; - iter_t end = m_rows.end(); - iter_t first = end; - iter_t second = end; - iter_t third = end; - for( iter_t it = m_rows.begin(); it != end; ++it ) + auto end = m_rows.end(); + auto first = end; + auto second = end; + auto third = end; + for( auto it = m_rows.begin(); it != end; ++it ) { double c = it->second->coefficientFor( marker ); if( c == 0.0 ) @@ -803,7 +790,7 @@ private: */ void removeMarkerEffects( const Symbol& marker, double strength ) { - RowMap::iterator row_it = m_rows.find( marker ); + auto row_it = m_rows.find( marker ); if( row_it != m_rows.end() ) m_objective->insert( *row_it->second, -strength ); else @@ -813,13 +800,11 @@ private: /* Test whether a row is composed of all dummy variables. */ - bool allDummies( const Row& row ) + bool allDummies( const Row& row ) const { - typedef Row::CellMap::const_iterator iter_t; - iter_t end = row.cells().end(); - for( iter_t it = row.cells().begin(); it != end; ++it ) + for (const auto &rowPair : row.cells()) { - if( it->first.type() != Symbol::Dummy ) + if( rowPair.first.type() != Symbol::Dummy ) return false; } return true; diff --git a/contrib/python/kiwisolver/py3/kiwi/symbol.h b/contrib/python/kiwisolver/py3/kiwi/symbol.h index ec422ad12d..2c49a5c2f1 100644 --- a/contrib/python/kiwisolver/py3/kiwi/symbol.h +++ b/contrib/python/kiwisolver/py3/kiwi/symbol.h @@ -19,7 +19,7 @@ class Symbol public: - typedef unsigned long long Id; + using Id = unsigned long long; enum Type { @@ -34,7 +34,7 @@ public: Symbol( Type type, Id id ) : m_id( id ), m_type( type ) {} - ~Symbol() {} + ~Symbol() = default; Id id() const { diff --git a/contrib/python/kiwisolver/py3/kiwi/symbolics.h b/contrib/python/kiwisolver/py3/kiwi/symbolics.h index 23eed60f59..c6658600d3 100644 --- a/contrib/python/kiwisolver/py3/kiwi/symbolics.h +++ b/contrib/python/kiwisolver/py3/kiwi/symbolics.h @@ -69,12 +69,11 @@ Expression operator*( const Expression& expression, double coefficient ) { std::vector<Term> terms; terms.reserve( expression.terms().size() ); - typedef std::vector<Term>::const_iterator iter_t; - iter_t begin = expression.terms().begin(); - iter_t end = expression.terms().end(); - for( iter_t it = begin; it != end; ++it ) - terms.push_back( ( *it ) * coefficient ); - return Expression( terms, expression.constant() * coefficient ); + + for (const Term &term : expression.terms()) + terms.push_back(term * coefficient); + + return Expression( std::move(terms), expression.constant() * coefficient ); } @@ -124,7 +123,7 @@ Expression operator+( const Expression& first, const Expression& second ) terms.reserve( first.terms().size() + second.terms().size() ); terms.insert( terms.begin(), first.terms().begin(), first.terms().end() ); terms.insert( terms.end(), second.terms().begin(), second.terms().end() ); - return Expression( terms, first.constant() + second.constant() ); + return Expression( std::move(terms), first.constant() + second.constant() ); } @@ -135,7 +134,7 @@ Expression operator+( const Expression& first, const Term& second ) terms.reserve( first.terms().size() + 1 ); terms.insert( terms.begin(), first.terms().begin(), first.terms().end() ); terms.push_back( second ); - return Expression( terms, first.constant() ); + return Expression( std::move(terms), first.constant() ); } @@ -193,11 +192,7 @@ Expression operator+( const Term& term, const Expression& expression ) inline Expression operator+( const Term& first, const Term& second ) { - std::vector<Term> terms; - terms.reserve( 2 ); - terms.push_back( first ); - terms.push_back( second ); - return Expression( terms ); + return Expression( { first, second } ); } diff --git a/contrib/python/kiwisolver/py3/kiwi/term.h b/contrib/python/kiwisolver/py3/kiwi/term.h index aecfdf06dc..85e00b1b12 100644 --- a/contrib/python/kiwisolver/py3/kiwi/term.h +++ b/contrib/python/kiwisolver/py3/kiwi/term.h @@ -18,14 +18,18 @@ class Term public: - Term( const Variable& variable, double coefficient = 1.0 ) : - m_variable( variable ), m_coefficient( coefficient ) {} + Term( Variable variable, double coefficient = 1.0 ) : + m_variable( std::move(variable) ), m_coefficient( coefficient ) {} // to facilitate efficient map -> vector copies Term( const std::pair<const Variable, double>& pair ) : m_variable( pair.first ), m_coefficient( pair.second ) {} - ~Term() {} + Term(const Term&) = default; + + Term(Term&&) noexcept = default; + + ~Term() = default; const Variable& variable() const { @@ -42,6 +46,10 @@ public: return m_coefficient * m_variable.value(); } + Term& operator=(const Term&) = default; + + Term& operator=(Term&&) noexcept = default; + private: Variable m_variable; diff --git a/contrib/python/kiwisolver/py3/kiwi/variable.h b/contrib/python/kiwisolver/py3/kiwi/variable.h index a4db777069..98d74998fd 100644 --- a/contrib/python/kiwisolver/py3/kiwi/variable.h +++ b/contrib/python/kiwisolver/py3/kiwi/variable.h @@ -20,17 +20,21 @@ public: class Context { public: - Context() {} + Context() = default; virtual ~Context() {} // LCOV_EXCL_LINE }; Variable(Context *context = 0) : m_data(new VariableData("", context)) {} - Variable(const std::string &name, Context *context = 0) : m_data(new VariableData(name, context)) {} + Variable(std::string name, Context *context = 0) : m_data(new VariableData(std::move(name), context)) {} Variable(const char *name, Context *context = 0) : m_data(new VariableData(name, context)) {} - ~Variable() {} + Variable(const Variable&) = default; + + Variable(Variable&&) noexcept = default; + + ~Variable() = default; const std::string &name() const { @@ -73,13 +77,17 @@ public: return m_data == other.m_data; } + Variable& operator=(const Variable&) = default; + + Variable& operator=(Variable&&) noexcept = default; + private: class VariableData : public SharedData { public: - VariableData(const std::string &name, Context *context) : SharedData(), - m_name(name), + VariableData(std::string name, Context *context) : SharedData(), + m_name(std::move(name)), m_context(context), m_value(0.0) {} @@ -88,7 +96,7 @@ private: m_context(context), m_value(0.0) {} - ~VariableData() {} + ~VariableData() = default; std::string m_name; std::unique_ptr<Context> m_context; diff --git a/contrib/python/kiwisolver/py3/kiwi/version.h b/contrib/python/kiwisolver/py3/kiwi/version.h index f6154482ae..233c8de2f1 100644 --- a/contrib/python/kiwisolver/py3/kiwi/version.h +++ b/contrib/python/kiwisolver/py3/kiwi/version.h @@ -8,7 +8,7 @@ #pragma once #define KIWI_MAJOR_VERSION 1 -#define KIWI_MINOR_VERSION 2 -#define KIWI_MICRO_VERSION 0 -#define KIWI_VERSION_HEX 0x010200 -#define KIWI_VERSION "1.2.0" +#define KIWI_MINOR_VERSION 3 +#define KIWI_MICRO_VERSION 1 +#define KIWI_VERSION_HEX 0x010301 +#define KIWI_VERSION "1.3.1" diff --git a/contrib/python/kiwisolver/py3/py/constraint.cpp b/contrib/python/kiwisolver/py3/py/constraint.cpp index e5b516919e..a688b8c1ce 100644 --- a/contrib/python/kiwisolver/py3/py/constraint.cpp +++ b/contrib/python/kiwisolver/py3/py/constraint.cpp @@ -57,6 +57,10 @@ void Constraint_clear(Constraint *self) int Constraint_traverse(Constraint *self, visitproc visit, void *arg) { Py_VISIT(self->expression); +#if PY_VERSION_HEX >= 0x03090000 + // This was not needed before Python 3.9 (Python issue 35810 and 40217) + Py_VISIT(Py_TYPE(self)); +#endif return 0; } diff --git a/contrib/python/kiwisolver/py3/py/expression.cpp b/contrib/python/kiwisolver/py3/py/expression.cpp index 235e463f12..38400483f6 100644 --- a/contrib/python/kiwisolver/py3/py/expression.cpp +++ b/contrib/python/kiwisolver/py3/py/expression.cpp @@ -62,6 +62,10 @@ int Expression_traverse( Expression* self, visitproc visit, void* arg ) { Py_VISIT( self->terms ); +#if PY_VERSION_HEX >= 0x03090000 + // This was not needed before Python 3.9 (Python issue 35810 and 40217) + Py_VISIT(Py_TYPE(self)); +#endif return 0; } @@ -177,8 +181,8 @@ Expression_richcmp( PyObject* first, PyObject* second, int op ) "unsupported operand type(s) for %s: " "'%.100s' and '%.100s'", pyop_str( op ), - first->ob_type->tp_name, - second->ob_type->tp_name + Py_TYPE( first )->tp_name, + Py_TYPE( second )->tp_name ); return 0; } diff --git a/contrib/python/kiwisolver/py3/py/kiwisolver.cpp b/contrib/python/kiwisolver/py3/py/kiwisolver.cpp index d82e67fde2..5a6645cbc5 100644 --- a/contrib/python/kiwisolver/py3/py/kiwisolver.cpp +++ b/contrib/python/kiwisolver/py3/py/kiwisolver.cpp @@ -9,7 +9,7 @@ #include <kiwi/kiwi.h> #include "types.h" -#define PY_KIWI_VERSION "1.2.0" +#define PY_KIWI_VERSION "1.3.2" namespace { diff --git a/contrib/python/kiwisolver/py3/py/term.cpp b/contrib/python/kiwisolver/py3/py/term.cpp index 923e0cf858..35b0a0e0bc 100644 --- a/contrib/python/kiwisolver/py3/py/term.cpp +++ b/contrib/python/kiwisolver/py3/py/term.cpp @@ -56,6 +56,10 @@ int Term_traverse( Term* self, visitproc visit, void* arg ) { Py_VISIT( self->variable ); +#if PY_VERSION_HEX >= 0x03090000 + // This was not needed before Python 3.9 (Python issue 35810 and 40217) + Py_VISIT(Py_TYPE(self)); +#endif return 0; } @@ -155,8 +159,8 @@ Term_richcmp( PyObject* first, PyObject* second, int op ) "unsupported operand type(s) for %s: " "'%.100s' and '%.100s'", pyop_str( op ), - first->ob_type->tp_name, - second->ob_type->tp_name + Py_TYPE( first )->tp_name, + Py_TYPE( second )->tp_name ); return 0; } diff --git a/contrib/python/kiwisolver/py3/py/variable.cpp b/contrib/python/kiwisolver/py3/py/variable.cpp index 1a9c69f8f6..b00f809c32 100644 --- a/contrib/python/kiwisolver/py3/py/variable.cpp +++ b/contrib/python/kiwisolver/py3/py/variable.cpp @@ -68,6 +68,10 @@ int Variable_traverse( Variable* self, visitproc visit, void* arg ) { Py_VISIT( self->context ); +#if PY_VERSION_HEX >= 0x03090000 + // This was not needed before Python 3.9 (Python issue 35810 and 40217) + Py_VISIT(Py_TYPE(self)); +#endif return 0; } @@ -192,8 +196,8 @@ Variable_richcmp( PyObject* first, PyObject* second, int op ) "unsupported operand type(s) for %s: " "'%.100s' and '%.100s'", pyop_str( op ), - first->ob_type->tp_name, - second->ob_type->tp_name + Py_TYPE( first )->tp_name, + Py_TYPE( second )->tp_name ); return 0; } diff --git a/contrib/python/kiwisolver/py3/ya.make b/contrib/python/kiwisolver/py3/ya.make index 3ba8053ef6..8fe468de53 100644 --- a/contrib/python/kiwisolver/py3/ya.make +++ b/contrib/python/kiwisolver/py3/ya.make @@ -2,7 +2,7 @@ PY3_LIBRARY() -VERSION(1.2.0) +VERSION(1.3.2) LICENSE(BSD-3-Clause) |