Linear_Expression_defs.hh

Go to the documentation of this file.

/* Linear_Expression class declaration.
   Copyright (C) 2001-2010 Roberto Bagnara <bagnara@cs.unipr.it>
   Copyright (C) 2010-2016 BUGSENG srl (http://bugseng.com)

This file is part of the Parma Polyhedra Library (PPL).

The PPL is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by the
Free Software Foundation; either version 3 of the License, or (at your
option) any later version.

The PPL is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software Foundation,
Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02111-1307, USA.

For the most up-to-date information see the Parma Polyhedra Library
site: http://bugseng.com/products/ppl/ . */

#ifndef PPL_Linear_Expression_defs_hh
#define PPL_Linear_Expression_defs_hh 1

#include "Linear_Expression_types.hh"

#include "Constraint_types.hh"
#include "Generator_types.hh"
#include "Congruence_types.hh"
#include "Grid_Generator_types.hh"
#include "Linear_System_types.hh"
#include "Constraint_System_types.hh"
#include "Congruence_System_types.hh"
#include "Coefficient_types.hh"
#include "Polyhedron_types.hh"
#include "Grid_types.hh"
#include "PIP_Problem_types.hh"
#include "BHRZ03_Certificate_types.hh"
#include "Scalar_Products_types.hh"
#include "MIP_Problem_types.hh"
#include "Box_types.hh"
#include "BD_Shape_types.hh"
#include "Octagonal_Shape_types.hh"
#include "termination_types.hh"

#include "Expression_Adapter_defs.hh"
#include "Expression_Hide_Inhomo_types.hh"
#include "Expression_Hide_Last_types.hh"

#include "Linear_Expression_Interface_defs.hh"
#include "Variable_defs.hh"
#include <cstddef>

namespace Parma_Polyhedra_Library {

// Put them in the namespace here to declare them friend later.


Linear_Expression
operator+(const Linear_Expression& e1, const Linear_Expression& e2);


Linear_Expression
operator+(Variable v, Variable w);


Linear_Expression
operator+(Variable v, const Linear_Expression& e);


Linear_Expression
operator+(const Linear_Expression& e, Variable v);


Linear_Expression
operator+(Coefficient_traits::const_reference n, const Linear_Expression& e);


Linear_Expression
operator+(const Linear_Expression& e, Coefficient_traits::const_reference n);


Linear_Expression
operator+(const Linear_Expression& e);


Linear_Expression
operator-(const Linear_Expression& e);


Linear_Expression
operator-(const Linear_Expression& e1, const Linear_Expression& e2);


Linear_Expression
operator-(Variable v, Variable w);


Linear_Expression
operator-(Variable v, const Linear_Expression& e);


Linear_Expression
operator-(const Linear_Expression& e, Variable v);


Linear_Expression
operator-(Coefficient_traits::const_reference n, const Linear_Expression& e);


Linear_Expression
operator-(const Linear_Expression& e, Coefficient_traits::const_reference n);


Linear_Expression
operator*(Coefficient_traits::const_reference n, const Linear_Expression& e);


Linear_Expression
operator*(const Linear_Expression& e, Coefficient_traits::const_reference n);


Linear_Expression&
operator+=(Linear_Expression& e1, const Linear_Expression& e2);


Linear_Expression&
operator+=(Linear_Expression& e, Variable v);


Linear_Expression&
operator+=(Linear_Expression& e, Coefficient_traits::const_reference n);


Linear_Expression&
operator-=(Linear_Expression& e1, const Linear_Expression& e2);


Linear_Expression&
operator-=(Linear_Expression& e, Variable v);


Linear_Expression&
operator-=(Linear_Expression& e, Coefficient_traits::const_reference n);


Linear_Expression&
operator*=(Linear_Expression& e, Coefficient_traits::const_reference n);


Linear_Expression&
operator/=(Linear_Expression& e, Coefficient_traits::const_reference n);


void
neg_assign(Linear_Expression& e);


Linear_Expression&
add_mul_assign(Linear_Expression& e,
               Coefficient_traits::const_reference n, Variable v);


void add_mul_assign(Linear_Expression& e1,
                    Coefficient_traits::const_reference factor,
                    const Linear_Expression& e2);


void sub_mul_assign(Linear_Expression& e1,
                    Coefficient_traits::const_reference factor,
                    const Linear_Expression& e2);


Linear_Expression&
sub_mul_assign(Linear_Expression& e,
               Coefficient_traits::const_reference n, Variable v);

#ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS

#endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS)
int compare(const Linear_Expression& x, const Linear_Expression& y);

namespace IO_Operators {


std::ostream& operator<<(std::ostream& s, const Linear_Expression& e);

} // namespace IO_Operators

} // namespace Parma_Polyhedra_Library


class Parma_Polyhedra_Library::Linear_Expression {
public:
  static const Representation default_representation = SPARSE;

  explicit Linear_Expression(Representation r = default_representation);

  Linear_Expression(const Linear_Expression& e);

  Linear_Expression(const Linear_Expression& e, Representation r);

  // Queried by expression adapters.
  typedef const Linear_Expression& const_reference;
  typedef Linear_Expression raw_type;

  template <typename LE_Adapter>
  explicit
  Linear_Expression(const LE_Adapter& e,
                    typename
                    Enable_If<Is_Same_Or_Derived<Expression_Adapter_Base,
                                                 LE_Adapter>::value,
                              void*>::type = 0);

  template <typename LE_Adapter>
  Linear_Expression(const LE_Adapter& e,
                    Representation r,
                    typename
                    Enable_If<Is_Same_Or_Derived<Expression_Adapter_Base,
                                                 LE_Adapter>::value,
                              void*>::type = 0);

  template <typename LE_Adapter>
  explicit
  Linear_Expression(const LE_Adapter& e,
                    dimension_type space_dim,
                    typename
                    Enable_If<Is_Same_Or_Derived<Expression_Adapter_Base,
                                                 LE_Adapter>::value,
                              void*>::type = 0);

  template <typename LE_Adapter>
  Linear_Expression(const LE_Adapter& e,
                    dimension_type space_dim,
                    Representation r,
                    typename
                    Enable_If<Is_Same_Or_Derived<Expression_Adapter_Base,
                                                 LE_Adapter>::value,
                              void*>::type = 0);

  Linear_Expression& operator=(const Linear_Expression& e);

  ~Linear_Expression();

  explicit Linear_Expression(Coefficient_traits::const_reference n,
                             Representation r = default_representation);


  Linear_Expression(Variable v, Representation r = default_representation);

  Representation representation() const;

  void set_representation(Representation r);


  class const_iterator {
  private:
  public:
    typedef std::bidirectional_iterator_tag iterator_category;
    typedef const Coefficient value_type;
    typedef std::ptrdiff_t difference_type;
    typedef value_type* pointer;
    typedef Coefficient_traits::const_reference reference;


    explicit const_iterator();


    const_iterator(const const_iterator& i);

    ~const_iterator();


    void m_swap(const_iterator& i);


    const_iterator& operator=(const const_iterator& i);


    const_iterator& operator++();


    const_iterator& operator--();

    reference operator*() const;


    Variable variable() const;


    bool operator==(const const_iterator& i) const;


    bool operator!=(const const_iterator& i) const;

  private:
    const_iterator(Linear_Expression_Interface::const_iterator_interface* i);

    Linear_Expression_Interface::const_iterator_interface* itr;

    friend class Linear_Expression;
  };

  const_iterator begin() const;

  const_iterator end() const;

  const_iterator lower_bound(Variable v) const;

  static dimension_type max_space_dimension();

  dimension_type space_dimension() const;

  void set_space_dimension(dimension_type n);

  Coefficient_traits::const_reference coefficient(Variable v) const;

  void set_coefficient(Variable v,
                       Coefficient_traits::const_reference n);

  Coefficient_traits::const_reference inhomogeneous_term() const;

  void set_inhomogeneous_term(Coefficient_traits::const_reference n);


  void linear_combine(const Linear_Expression& y, Variable v);

  void linear_combine(const Linear_Expression& y,
                      Coefficient_traits::const_reference c1,
                      Coefficient_traits::const_reference c2);

  void linear_combine_lax(const Linear_Expression& y,
                          Coefficient_traits::const_reference c1,
                          Coefficient_traits::const_reference c2);

  void swap_space_dimensions(Variable v1, Variable v2);


  void remove_space_dimensions(const Variables_Set& vars);

  void shift_space_dimensions(Variable v, dimension_type n);


  void permute_space_dimensions(const std::vector<Variable>& cycle);

  bool is_zero() const;

  bool all_homogeneous_terms_are_zero() const;

  static void initialize();

  static void finalize();

  static const Linear_Expression& zero();

  memory_size_type total_memory_in_bytes() const;

  memory_size_type external_memory_in_bytes() const;

  bool OK() const;

  PPL_OUTPUT_DECLARATIONS

  bool ascii_load(std::istream& s);

  void m_swap(Linear_Expression& y);

  Linear_Expression(const Linear_Expression& e, dimension_type space_dim);

  Linear_Expression(const Linear_Expression& e, dimension_type space_dim,
                    Representation r);

  bool is_equal_to(const Linear_Expression& x) const;


  void normalize();

  void sign_normalize();

  bool all_zeroes(const Variables_Set& vars) const;

private:
  static const Linear_Expression* zero_p;

  Linear_Expression_Interface* impl;


  Linear_Expression(dimension_type space_dim, bool,
                    Representation r = default_representation);

  // NOTE: This method is public, but it's not exposed in Linear_Expression,
  // so that it can be used internally in the PPL, by friends of
  // Linear_Expression.
  Coefficient_traits::const_reference get(dimension_type i) const;

  // NOTE: This method is public, but it's not exposed in Linear_Expression,
  // so that it can be used internally in the PPL, by friends of
  // Linear_Expression.
  void set(dimension_type i, Coefficient_traits::const_reference n);

  // NOTE: This method is public, but it's not exposed in Linear_Expression,
  // so that it can be used internally in the PPL, by friends of
  // Linear_Expression.
  Coefficient_traits::const_reference get(Variable v) const;

  // NOTE: This method is public, but it's not exposed in Linear_Expression,
  // so that it can be used internally in the PPL, by friends of
  // Linear_Expression.
  void set(Variable v, Coefficient_traits::const_reference n);

  bool all_zeroes(dimension_type start, dimension_type end) const;

  dimension_type num_zeroes(dimension_type start, dimension_type end) const;

  Coefficient gcd(dimension_type start, dimension_type end) const;

  void exact_div_assign(Coefficient_traits::const_reference c,
                        dimension_type start, dimension_type end);


  void linear_combine(const Linear_Expression& y, dimension_type i);

  void linear_combine(const Linear_Expression& y,
                      Coefficient_traits::const_reference c1,
                      Coefficient_traits::const_reference c2,
                      dimension_type start, dimension_type end);

  void linear_combine_lax(const Linear_Expression& y,
                          Coefficient_traits::const_reference c1,
                          Coefficient_traits::const_reference c2,
                          dimension_type start, dimension_type end);

  void mul_assign(Coefficient_traits::const_reference n,
                  dimension_type start, dimension_type end);

  dimension_type last_nonzero() const;

  dimension_type last_nonzero(dimension_type first, dimension_type last) const;

  dimension_type first_nonzero(dimension_type first, dimension_type last) const;

  bool all_zeroes_except(const Variables_Set& vars,
                         dimension_type start, dimension_type end) const;

  void scalar_product_assign(Coefficient& result,
                             const Linear_Expression& y) const;

  void scalar_product_assign(Coefficient& result, const Linear_Expression& y,
                             dimension_type start, dimension_type end) const;

  int scalar_product_sign(const Linear_Expression& y) const;

  int scalar_product_sign(const Linear_Expression& y,
                          dimension_type start, dimension_type end) const;

  void has_a_free_dimension_helper(std::set<dimension_type>& x) const;

  bool is_equal_to(const Linear_Expression& x,
                   dimension_type start, dimension_type end) const;

  bool is_equal_to(const Linear_Expression& x,
                   Coefficient_traits::const_reference c1,
                   Coefficient_traits::const_reference c2,
                   dimension_type start, dimension_type end) const;

  void get_row(Dense_Row& r) const;

  void get_row(Sparse_Row& r) const;

  bool have_a_common_variable(const Linear_Expression& x,
                              Variable first, Variable last) const;

  void negate(dimension_type first, dimension_type last);

  template <typename Row>
  friend class Linear_Expression_Impl;

  // NOTE: The following classes are friends of Linear_Expression in order
  // to access its private methods.
  // Since they are *not* friend of Linear_Expression_Impl, they can only
  // access its public methods so they cannot break the class invariant of
  // Linear_Expression_Impl.
  friend class Grid;
  friend class Congruence;
  friend class Polyhedron;
  friend class PIP_Tree_Node;
  friend class Grid_Generator;
  friend class Generator;
  friend class Constraint;
  friend class Constraint_System;
  friend class PIP_Problem;
  friend class BHRZ03_Certificate;
  friend class Scalar_Products;
  friend class MIP_Problem;
  friend class Box_Helpers;
  friend class Congruence_System;
  friend class BD_Shape_Helpers;
  friend class Octagonal_Shape_Helper;
  friend class Termination_Helpers;
  template <typename T>
  friend class BD_Shape;
  template <typename T>
  friend class Octagonal_Shape;
  template <typename T>
  friend class Linear_System;
  template <typename T>
  friend class Box;
  template <typename T>
  friend class Expression_Adapter;
  template <typename T>
  friend class Expression_Hide_Inhomo;
  template <typename T>
  friend class Expression_Hide_Last;

  friend Linear_Expression
  operator+(const Linear_Expression& e1, const Linear_Expression& e2);
  friend Linear_Expression
  operator+(Coefficient_traits::const_reference n, const Linear_Expression& e);
  friend Linear_Expression
  operator+(const Linear_Expression& e, Coefficient_traits::const_reference n);
  friend Linear_Expression
  operator+(Variable v, const Linear_Expression& e);
  friend Linear_Expression
  operator+(Variable v, Variable w);

  friend Linear_Expression
  operator-(const Linear_Expression& e);

  friend Linear_Expression
  operator-(const Linear_Expression& e1, const Linear_Expression& e2);
  friend Linear_Expression
  operator-(Variable v, Variable w);
  friend Linear_Expression
  operator-(Coefficient_traits::const_reference n, const Linear_Expression& e);
  friend Linear_Expression
  operator-(const Linear_Expression& e, Coefficient_traits::const_reference n);
  friend Linear_Expression
  operator-(Variable v, const Linear_Expression& e);
  friend Linear_Expression
  operator-(const Linear_Expression& e, Variable v);

  friend Linear_Expression
  operator*(Coefficient_traits::const_reference n, const Linear_Expression& e);
  friend Linear_Expression
  operator*(const Linear_Expression& e, Coefficient_traits::const_reference n);

  friend Linear_Expression&
  operator+=(Linear_Expression& e1, const Linear_Expression& e2);
  friend Linear_Expression&
  operator+=(Linear_Expression& e, Variable v);
  friend Linear_Expression&
  operator+=(Linear_Expression& e, Coefficient_traits::const_reference n);

  friend Linear_Expression&
  operator-=(Linear_Expression& e1, const Linear_Expression& e2);
  friend Linear_Expression&
  operator-=(Linear_Expression& e, Variable v);
  friend Linear_Expression&
  operator-=(Linear_Expression& e, Coefficient_traits::const_reference n);

  friend Linear_Expression&
  operator*=(Linear_Expression& e, Coefficient_traits::const_reference n);
  friend Linear_Expression&
  operator/=(Linear_Expression& e, Coefficient_traits::const_reference n);

  friend void
  neg_assign(Linear_Expression& e);

  friend Linear_Expression&
  add_mul_assign(Linear_Expression& e,
                 Coefficient_traits::const_reference n, Variable v);
  friend Linear_Expression&
  sub_mul_assign(Linear_Expression& e,
                 Coefficient_traits::const_reference n, Variable v);

  friend void
  add_mul_assign(Linear_Expression& e1,
                 Coefficient_traits::const_reference factor,
                 const Linear_Expression& e2);
  friend void
  sub_mul_assign(Linear_Expression& e1,
                 Coefficient_traits::const_reference factor,
                 const Linear_Expression& e2);

  friend int
  compare(const Linear_Expression& x, const Linear_Expression& y);

  friend std::ostream&
  Parma_Polyhedra_Library::IO_Operators
  ::operator<<(std::ostream& s, const Linear_Expression& e);
};

namespace Parma_Polyhedra_Library {


void swap(Linear_Expression& x, Linear_Expression& y);


void swap(Linear_Expression::const_iterator& x,
          Linear_Expression::const_iterator& y);

} // namespace Parma_Polyhedra_Library

#include "Linear_Expression_inlines.hh"

#endif // !defined(PPL_Linear_Expression_defs_hh)