Constraint_System_defs.hh

Go to the documentation of this file.

/* Constraint_System 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_Constraint_System_defs_hh
#define PPL_Constraint_System_defs_hh 1

#include "Constraint_System_types.hh"

#include "Linear_System_defs.hh"
#include "Constraint_defs.hh"

#include "Linear_Expression_types.hh"
#include "Generator_types.hh"
#include "Constraint_types.hh"
#include "Congruence_System_types.hh"
#include "Polyhedron_types.hh"
#include "termination_types.hh"
#include <iterator>
#include <iosfwd>
#include <cstddef>

namespace Parma_Polyhedra_Library {

namespace IO_Operators {


std::ostream& operator<<(std::ostream& s, const Constraint_System& cs);

} // namespace IO_Operators

// TODO: Consider removing this.
#ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS

#endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS)
bool operator==(const Constraint_System& x, const Constraint_System& y);

// TODO: Consider removing this.
#ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS

#endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS)
bool operator!=(const Constraint_System& x, const Constraint_System& y);

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

} // namespace Parma_Polyhedra_Library


class Parma_Polyhedra_Library::Constraint_System {
public:
  typedef Constraint row_type;

  static const Representation default_representation = SPARSE;

  explicit Constraint_System(Representation r = default_representation);

  explicit Constraint_System(const Constraint& c,
                             Representation r = default_representation);

  explicit Constraint_System(const Congruence_System& cgs,
                             Representation r = default_representation);


  Constraint_System(const Constraint_System& cs);

  Constraint_System(const Constraint_System& cs, Representation r);

  ~Constraint_System();

  Constraint_System& operator=(const Constraint_System& y);

  Representation representation() const;

  void set_representation(Representation r);

  static dimension_type max_space_dimension();

  dimension_type space_dimension() const;

  void set_space_dimension(dimension_type space_dim);

  bool has_equalities() const;

  bool has_strict_inequalities() const;

  void insert(const Constraint& c);

  static void initialize();

  static void finalize();

  static const Constraint_System& zero_dim_empty();

  typedef Constraint_System_const_iterator const_iterator;

  bool empty() const;

  void clear();

  const_iterator begin() const;

  const_iterator end() const;

  bool OK() const;

  PPL_OUTPUT_DECLARATIONS

  bool ascii_load(std::istream& s);

  memory_size_type total_memory_in_bytes() const;

  memory_size_type external_memory_in_bytes() const;

  void m_swap(Constraint_System& y);

private:
  Linear_System<Constraint> sys;

  static const Constraint_System* zero_dim_empty_p;

  friend class Constraint_System_const_iterator;

  friend bool operator==(const Constraint_System& x,
                         const Constraint_System& y);

  explicit Constraint_System(Topology topol,
                             Representation r = default_representation);

  Constraint_System(Topology topol, dimension_type space_dim,
                    Representation r = default_representation);

  dimension_type num_equalities() const;

  dimension_type num_inequalities() const;

  void simplify();

  bool adjust_topology_and_space_dimension(Topology new_topology,
                                           dimension_type new_space_dim);

  const Constraint& operator[](dimension_type k) const;

  bool satisfies_all_constraints(const Generator& g) const;


  void affine_preimage(Variable v,
                       const Linear_Expression& expr,
                       Coefficient_traits::const_reference denominator);

  void insert_pending(const Constraint& c);

  void add_low_level_constraints();

  Topology topology() const;

  dimension_type num_rows() const;

  bool is_necessarily_closed() const;

  dimension_type num_pending_rows() const;

  dimension_type first_pending_row() const;

  bool is_sorted() const;

  void unset_pending_rows();

  void set_index_first_pending_row(dimension_type i);

  void set_sorted(bool b);


  void remove_row(dimension_type i, bool keep_sorted = false);


  void remove_rows(const std::vector<dimension_type>& indexes);


  void remove_rows(dimension_type first, dimension_type last,
                   bool keep_sorted = false);

  void remove_trailing_rows(dimension_type n);


  void remove_space_dimensions(const Variables_Set& vars);

  void shift_space_dimensions(Variable v, dimension_type n);

  /*
    \param cycle
    A vector representing a cycle of the permutation according to which the
    columns must be rearranged.

    The \p cycle vector represents a cycle of a permutation of space
    dimensions.
    For example, the permutation
    \f$ \{ x_1 \mapsto x_2, x_2 \mapsto x_3, x_3 \mapsto x_1 \}\f$ can be
    represented by the vector containing \f$ x_1, x_2, x_3 \f$.
  */
  void permute_space_dimensions(const std::vector<Variable>& cycle);

  void swap_space_dimensions(Variable v1, Variable v2);

  bool has_no_rows() const;

  void strong_normalize();

  void sort_rows();

  void insert_pending(Constraint& r, Recycle_Input);

  void insert_pending(Constraint_System& r, Recycle_Input);

  void insert(Constraint& r, Recycle_Input);


  void insert(Constraint_System& r, Recycle_Input);

  void insert_pending(const Constraint_System& r);

  void merge_rows_assign(const Constraint_System& y);


  void insert(const Constraint_System& y);


  void mark_as_necessarily_closed();


  void mark_as_not_necessarily_closed();


  dimension_type gauss(dimension_type n_lines_or_equalities);

  void back_substitute(dimension_type n_lines_or_equalities);

  void assign_with_pending(const Constraint_System& y);

  void sort_pending_and_remove_duplicates();

  void sort_and_remove_with_sat(Bit_Matrix& sat);

  bool check_sorted() const;

  dimension_type num_lines_or_equalities() const;


  void add_universe_rows_and_space_dimensions(dimension_type n);

  friend class Polyhedron;
  friend class Termination_Helpers;
};


// NOTE: This is not an inner class of Constraint_System, so Constraint can
// declare that this class is his friend without including this file
// (the .types.hh file suffices).
class Parma_Polyhedra_Library::Constraint_System_const_iterator
  : public std::iterator<std::forward_iterator_tag,
                         Constraint,
                         std::ptrdiff_t,
                         const Constraint*,
                         const Constraint&> {
public:
  Constraint_System_const_iterator();

  Constraint_System_const_iterator(const Constraint_System_const_iterator& y);

  ~Constraint_System_const_iterator();

  Constraint_System_const_iterator&
  operator=(const Constraint_System_const_iterator& y);

  const Constraint& operator*() const;

  const Constraint* operator->() const;

  Constraint_System_const_iterator& operator++();

  Constraint_System_const_iterator operator++(int);

  bool operator==(const Constraint_System_const_iterator& y) const;

  bool operator!=(const Constraint_System_const_iterator& y) const;

private:
  friend class Constraint_System;

  Linear_System<Constraint>::const_iterator i;

  const Linear_System<Constraint>* csp;

  Constraint_System_const_iterator(const Linear_System<Constraint>
                                   ::const_iterator& iter,
                                   const Constraint_System& cs);

  void skip_forward();
};

namespace Parma_Polyhedra_Library {

namespace Implementation {

#ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS
#endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS)
dimension_type
num_constraints(const Constraint_System& cs);

} // namespace Implementation

} // namespace Parma_Polyhedra_Library

// Constraint_System_inlines.hh is not included here on purpose.

#endif // !defined(PPL_Constraint_System_defs_hh)