Linear_Expression_Impl_defs.hh

Go to the documentation of this file.

/* Linear_Expression_Impl 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_Impl_defs_hh
#define PPL_Linear_Expression_Impl_defs_hh 1

#include "Linear_Expression_Impl_types.hh"
#include "Linear_Expression_Interface_defs.hh"
#include "Coefficient_defs.hh"
#include "Variable_defs.hh"
#include "Variables_Set_defs.hh"
#include "Dense_Row_defs.hh"
#include "Sparse_Row_defs.hh"
#include <cstddef>

namespace Parma_Polyhedra_Library {

namespace IO_Operators {

#ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS

#endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS)
template <typename Row>
std::ostream&
operator<<(std::ostream& s, const Linear_Expression_Impl<Row>& e);

} // namespace IO_Operators

} // namespace Parma_Polyhedra_Library

#ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS

#endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS)
template <typename Row>
class Parma_Polyhedra_Library::Linear_Expression_Impl
  : public Linear_Expression_Interface {
public:
  Linear_Expression_Impl();

  Linear_Expression_Impl(const Linear_Expression_Impl& e);

  template <typename Row2>
  Linear_Expression_Impl(const Linear_Expression_Impl<Row2>& e);

  Linear_Expression_Impl(const Linear_Expression_Interface& e);

  virtual ~Linear_Expression_Impl();

  virtual bool OK() const;

  explicit Linear_Expression_Impl(Coefficient_traits::const_reference n);


  Linear_Expression_Impl(Variable v);

  virtual Representation representation() const;


  class const_iterator: public const_iterator_interface {
  public:
    explicit const_iterator(const Row& row, dimension_type i);

    virtual const_iterator_interface* clone() const;

    virtual void operator++();

    virtual void operator--();

    virtual reference operator*() const;


    virtual Variable variable() const;


    virtual bool operator==(const const_iterator_interface& x) const;

  private:

    void skip_zeroes_forward();
    void skip_zeroes_backward();

    const Row* row;
    typename Row::const_iterator itr;
  };

  virtual const_iterator_interface* begin() const;

  virtual const_iterator_interface* end() const;

  virtual const_iterator_interface* lower_bound(Variable v) const;

  static dimension_type max_space_dimension();

  virtual dimension_type space_dimension() const;

  virtual void set_space_dimension(dimension_type n);

  virtual Coefficient_traits::const_reference coefficient(Variable v) const;

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

  virtual Coefficient_traits::const_reference inhomogeneous_term() const;

  virtual void set_inhomogeneous_term(Coefficient_traits::const_reference n);


  virtual void linear_combine(const Linear_Expression_Interface& y, Variable v);

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

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

  virtual void swap_space_dimensions(Variable v1, Variable v2);


  virtual void remove_space_dimensions(const Variables_Set& vars);

  virtual void shift_space_dimensions(Variable v, dimension_type n);


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

  virtual bool is_zero() const;

  virtual bool all_homogeneous_terms_are_zero() const;

  virtual memory_size_type total_memory_in_bytes() const;

  virtual memory_size_type external_memory_in_bytes() const;

  virtual void ascii_dump(std::ostream& s) const;

  virtual bool ascii_load(std::istream& s);

  Linear_Expression_Impl(const Linear_Expression_Interface& e,
                         dimension_type space_dim);

  virtual bool is_equal_to(const Linear_Expression_Interface& x) const;


  virtual void normalize();

  virtual void sign_normalize();

  virtual void negate(dimension_type first, dimension_type last);

  virtual Linear_Expression_Impl&
  operator+=(Coefficient_traits::const_reference n);
  virtual Linear_Expression_Impl&
  operator-=(Coefficient_traits::const_reference n);


  virtual int compare(const Linear_Expression_Interface& y) const;

  virtual Linear_Expression_Impl&
  operator+=(const Linear_Expression_Interface& e2);
  virtual Linear_Expression_Impl& operator+=(const Variable v);
  virtual Linear_Expression_Impl&
  operator-=(const Linear_Expression_Interface& e2);
  virtual Linear_Expression_Impl& operator-=(const Variable v);
  virtual Linear_Expression_Impl&
  operator*=(Coefficient_traits::const_reference n);
  virtual Linear_Expression_Impl&
  operator/=(Coefficient_traits::const_reference n);

  virtual void negate();

  virtual Linear_Expression_Impl&
  add_mul_assign(Coefficient_traits::const_reference n, const Variable v);

  virtual Linear_Expression_Impl&
  sub_mul_assign(Coefficient_traits::const_reference n, const Variable v);

  virtual void add_mul_assign(Coefficient_traits::const_reference factor,
                              const Linear_Expression_Interface& e2);

  virtual void sub_mul_assign(Coefficient_traits::const_reference factor,
                              const Linear_Expression_Interface& e2);

  virtual void print(std::ostream& s) const;

  virtual bool all_zeroes(const Variables_Set& vars) const;

  virtual bool have_a_common_variable(const Linear_Expression_Interface& x,
                                      Variable first, Variable last) 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.
  virtual 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.
  virtual 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.
  virtual bool all_zeroes(dimension_type start, dimension_type end) 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.
  virtual dimension_type num_zeroes(dimension_type start, dimension_type end) 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.
  virtual Coefficient gcd(dimension_type start, dimension_type end) 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.
  virtual void exact_div_assign(Coefficient_traits::const_reference c,
                                dimension_type start, dimension_type end);

  // 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.
  virtual void mul_assign(Coefficient_traits::const_reference n,
                          dimension_type start, dimension_type end);

  // 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.

  virtual void
  linear_combine(const Linear_Expression_Interface& y, dimension_type i);

  // 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.
  virtual void linear_combine(const Linear_Expression_Interface& y,
                              Coefficient_traits::const_reference c1,
                              Coefficient_traits::const_reference c2,
                              dimension_type start, dimension_type end);

  // 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.
  virtual void linear_combine_lax(const Linear_Expression_Interface& y,
                                  Coefficient_traits::const_reference c1,
                                  Coefficient_traits::const_reference c2,
                                  dimension_type start, dimension_type end);

  // 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.
  virtual dimension_type last_nonzero() 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.
  virtual bool
  all_zeroes_except(const Variables_Set& vars,
                    dimension_type start, dimension_type end) 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.
  virtual void
  scalar_product_assign(Coefficient& result,
                        const Linear_Expression_Interface& y,
                        dimension_type start, dimension_type end) 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.
  virtual int
  scalar_product_sign(const Linear_Expression_Interface& y,
                      dimension_type start, dimension_type end) 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.
  virtual dimension_type
  first_nonzero(dimension_type first, dimension_type last) 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.
  virtual dimension_type
  last_nonzero(dimension_type first, dimension_type last) 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.
  virtual void has_a_free_dimension_helper(std::set<dimension_type>& x) 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.
  virtual bool is_equal_to(const Linear_Expression_Interface& x,
                           dimension_type start, dimension_type end) 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.
  virtual bool is_equal_to(const Linear_Expression_Interface& x,
                           Coefficient_traits::const_reference c1,
                           Coefficient_traits::const_reference c2,
                           dimension_type start, dimension_type end) const;

  // NOTE: This method is public, but it is not exposed in
  // Linear_Expression, so that it can be used internally in the PPL,
  // by friends of Linear_Expression.
  virtual void get_row(Dense_Row& r) const;

  // NOTE: This method is public, but it is not exposed in
  // Linear_Expression, so that it can be used internally in the PPL,
  // by friends of Linear_Expression.
  virtual void get_row(Sparse_Row& r) const;


  Linear_Expression_Impl(dimension_type space_dim, bool);


  template <typename Row2>
  void linear_combine(const Linear_Expression_Impl<Row2>& y, Variable v);

  template <typename Row2>
  void linear_combine(const Linear_Expression_Impl<Row2>& y,
                      Coefficient_traits::const_reference c1,
                      Coefficient_traits::const_reference c2);

  template <typename Row2>
  void linear_combine_lax(const Linear_Expression_Impl<Row2>& y,
                          Coefficient_traits::const_reference c1,
                          Coefficient_traits::const_reference c2);

  template <typename Row2>
  bool is_equal_to(const Linear_Expression_Impl<Row2>& x) const;

  template <typename Row2>
  Linear_Expression_Impl& operator+=(const Linear_Expression_Impl<Row2>& e2);
  template <typename Row2>
  Linear_Expression_Impl& operator-=(const Linear_Expression_Impl<Row2>& e2);

  template <typename Row2>
  Linear_Expression_Impl&
  sub_mul_assign(Coefficient_traits::const_reference n,
                 const Linear_Expression_Impl<Row2>& y,
                 dimension_type start, dimension_type end);

  template <typename Row2>
  void add_mul_assign(Coefficient_traits::const_reference factor,
                      const Linear_Expression_Impl<Row2>& e2);

  template <typename Row2>
  void sub_mul_assign(Coefficient_traits::const_reference factor,
                      const Linear_Expression_Impl<Row2>& e2);


  template <typename Row2>
  void linear_combine(const Linear_Expression_Impl<Row2>& y, dimension_type i);

  template <typename Row2>
  void linear_combine(const Linear_Expression_Impl<Row2>& y,
                      Coefficient_traits::const_reference c1,
                      Coefficient_traits::const_reference c2,
                      dimension_type start, dimension_type end);

  template <typename Row2>
  void linear_combine_lax(const Linear_Expression_Impl<Row2>& y,
                          Coefficient_traits::const_reference c1,
                          Coefficient_traits::const_reference c2,
                          dimension_type start, dimension_type end);


  template <typename Row2>
  int compare(const Linear_Expression_Impl<Row2>& y) const;

  template <typename Row2>
  void
  scalar_product_assign(Coefficient& result,
                        const Linear_Expression_Impl<Row2>& y,
                        dimension_type start, dimension_type end) const;

  template <typename Row2>
  int scalar_product_sign(const Linear_Expression_Impl<Row2>& y,
                          dimension_type start, dimension_type end) const;

  template <typename Row2>
  bool is_equal_to(const Linear_Expression_Impl<Row2>& x,
                   dimension_type start, dimension_type end) const;

  template <typename Row2>
  bool is_equal_to(const Linear_Expression_Impl<Row2>& x,
                   Coefficient_traits::const_reference c1,
                   Coefficient_traits::const_reference c2,
                   dimension_type start, dimension_type end) const;

  template <typename Row2>
  bool have_a_common_variable(const Linear_Expression_Impl<Row2>& x,
                              Variable first, Variable last) const;

private:

  void construct(const Linear_Expression_Interface& e);
  void construct(const Linear_Expression_Interface& e,
                 dimension_type space_dim);

  template <typename Row2>
  void construct(const Linear_Expression_Impl<Row2>& e);
  template <typename Row2>
  void construct(const Linear_Expression_Impl<Row2>& e,
                 dimension_type space_dim);

  Row row;

  template <typename Row2>
  friend class Linear_Expression_Impl;

}; // class Parma_Polyhedra_Library::Linear_Expression_Impl


namespace Parma_Polyhedra_Library {

// NOTE: declaring explicit specializations.

template <>
bool
Linear_Expression_Impl<Dense_Row>::OK() const;
template <>
bool
Linear_Expression_Impl<Sparse_Row>::OK() const;

template <>
bool
Linear_Expression_Impl<Dense_Row>::all_homogeneous_terms_are_zero() const;
template <>
bool
Linear_Expression_Impl<Sparse_Row>::all_homogeneous_terms_are_zero() const;

template <>
bool
Linear_Expression_Impl<Dense_Row>::all_zeroes(dimension_type start,
                                              dimension_type end) const;
template <>
bool
Linear_Expression_Impl<Sparse_Row>::all_zeroes(dimension_type start,
                                               dimension_type end) const;

template <>
bool
Linear_Expression_Impl<Dense_Row>
::all_zeroes(const Variables_Set& vars) const;
template <>
bool
Linear_Expression_Impl<Sparse_Row>
::all_zeroes(const Variables_Set& vars) const;

template <>
bool
Linear_Expression_Impl<Dense_Row>
::all_zeroes_except(const Variables_Set& vars,
                    dimension_type start, dimension_type end) const;
template <>
bool
Linear_Expression_Impl<Sparse_Row>
::all_zeroes_except(const Variables_Set& vars,
                    dimension_type start, dimension_type end) const;

template <>
dimension_type
Linear_Expression_Impl<Dense_Row>
::first_nonzero(dimension_type first, dimension_type last) const;
template <>
dimension_type
Linear_Expression_Impl<Sparse_Row>
::first_nonzero(dimension_type first, dimension_type last) const;

template <>
Coefficient
Linear_Expression_Impl<Dense_Row>::gcd(dimension_type start,
                                       dimension_type end) const;
template <>
Coefficient
Linear_Expression_Impl<Sparse_Row>::gcd(dimension_type start,
                                        dimension_type end) const;

template <>
void
Linear_Expression_Impl<Dense_Row>
::has_a_free_dimension_helper(std::set<dimension_type>& x) const;
template <>
void
Linear_Expression_Impl<Sparse_Row>
::has_a_free_dimension_helper(std::set<dimension_type>& x) const;

template <>
template <>
bool
Linear_Expression_Impl<Dense_Row>
::have_a_common_variable(const Linear_Expression_Impl<Dense_Row>& y,
                         Variable first, Variable last) const;
template <>
template <>
bool
Linear_Expression_Impl<Dense_Row>
::have_a_common_variable(const Linear_Expression_Impl<Sparse_Row>& y,
                         Variable first, Variable last) const;
template <>
template <>
bool
Linear_Expression_Impl<Sparse_Row>
::have_a_common_variable(const Linear_Expression_Impl<Dense_Row>& y,
                         Variable first, Variable last) const;
template <>
template <>
bool
Linear_Expression_Impl<Sparse_Row>
::have_a_common_variable(const Linear_Expression_Impl<Sparse_Row>& y,
                         Variable first, Variable last) const;

template <>
bool
Linear_Expression_Impl<Dense_Row>::is_zero() const;
template <>
bool
Linear_Expression_Impl<Sparse_Row>::is_zero() const;

template <>
dimension_type
Linear_Expression_Impl<Dense_Row>::last_nonzero() const;
template <>
dimension_type
Linear_Expression_Impl<Sparse_Row>::last_nonzero() const;

template <>
dimension_type
Linear_Expression_Impl<Dense_Row>
::last_nonzero(dimension_type first, dimension_type last) const;
template <>
dimension_type
Linear_Expression_Impl<Sparse_Row>
::last_nonzero(dimension_type first, dimension_type last) const;

template <>
dimension_type
Linear_Expression_Impl<Dense_Row>::num_zeroes(dimension_type start,
                                              dimension_type end) const;
template <>
dimension_type
Linear_Expression_Impl<Sparse_Row>::num_zeroes(dimension_type start,
                                               dimension_type end) const;

template <>
void
Linear_Expression_Impl<Dense_Row>
::remove_space_dimensions(const Variables_Set& vars);
template <>
void
Linear_Expression_Impl<Sparse_Row>
::remove_space_dimensions(const Variables_Set& vars);

template <>
Representation
Linear_Expression_Impl<Dense_Row>::representation() const;
template <>
Representation
Linear_Expression_Impl<Sparse_Row>::representation() const;

template <>
void
Linear_Expression_Impl<Dense_Row>::const_iterator::skip_zeroes_backward();
template <>
void
Linear_Expression_Impl<Sparse_Row>::const_iterator::skip_zeroes_backward();

template <>
void
Linear_Expression_Impl<Dense_Row>::const_iterator::skip_zeroes_forward();
template <>
void
Linear_Expression_Impl<Sparse_Row>::const_iterator::skip_zeroes_forward();

} // namespace Parma_Polyhedra_Library


#include "Linear_Expression_Impl_inlines.hh"
#include "Linear_Expression_Impl_templates.hh"

#endif // !defined(PPL_Linear_Expression_Impl_defs_hh)