1 /* BD_Shape class implementation: non-inline functions.
2 Copyright (C) 2001-2010 Roberto Bagnara <bagnara@cs.unipr.it>
3 Copyright (C) 2010-2016 BUGSENG srl (http://bugseng.com)
4
5 This file is part of the Parma Polyhedra Library (PPL).
6
7 The PPL is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 3 of the License, or (at your
10 option) any later version.
11
12 The PPL is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with this program; if not, write to the Free Software Foundation,
19 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02111-1307, USA.
20
21 For the most up-to-date information see the Parma Polyhedra Library
22 site: http://bugseng.com/products/ppl/ . */
23
24 #include "ppl-config.h"
25 #include "BD_Shape_defs.hh"
26
27 namespace PPL = Parma_Polyhedra_Library;
28
29 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS
30 /*! \relates Parma_Polyhedra_Library::BD_Shape */
31 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS)
32 bool
extract_bounded_difference(const Constraint & c,dimension_type & c_num_vars,dimension_type & c_first_var,dimension_type & c_second_var,Coefficient & c_coeff)33 PPL::BD_Shape_Helpers::extract_bounded_difference(const Constraint& c,
34 dimension_type& c_num_vars,
35 dimension_type& c_first_var,
36 dimension_type& c_second_var,
37 Coefficient& c_coeff) {
38 // Check for preconditions.
39 const dimension_type space_dim = c.space_dimension();
40 PPL_ASSERT(c_num_vars == 0 && c_first_var == 0 && c_second_var == 0);
41
42 c_first_var = c.expression().first_nonzero(1, space_dim + 1);
43 if (c_first_var == space_dim + 1) {
44 // All the inhomogeneous coefficients are zero.
45 return true;
46 }
47
48 ++c_num_vars;
49
50 c_second_var = c.expression().first_nonzero(c_first_var + 1, space_dim + 1);
51 if (c_second_var == space_dim + 1) {
52 // c_first_var is the only inhomogeneous coefficient different from zero.
53 c_coeff = -c.expression().get(Variable(c_first_var - 1));
54
55 c_second_var = 0;
56 return true;
57 }
58
59 ++c_num_vars;
60
61 if (!c.expression().all_zeroes(c_second_var + 1, space_dim + 1)) {
62 // The constraint `c' is not a bounded difference.
63 return false;
64 }
65
66 // Make sure that `c' is indeed a bounded difference, i.e., it is of the
67 // form:
68 // a*x - a*y <=/= b.
69 Coefficient_traits::const_reference c0 = c.expression().get(Variable(c_first_var - 1));
70 Coefficient_traits::const_reference c1 = c.expression().get(Variable(c_second_var - 1));
71 if (sgn(c0) == sgn(c1) || c0 != -c1) {
72 // Constraint `c' is not a bounded difference.
73 return false;
74 }
75
76 c_coeff = c1;
77
78 return true;
79 }
80
81 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS
82 /*! \relates Parma_Polyhedra_Library::BD_Shape */
83 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS)
84 void
compute_leader_indices(const std::vector<dimension_type> & predecessor,std::vector<dimension_type> & indices)85 PPL::compute_leader_indices(const std::vector<dimension_type>& predecessor,
86 std::vector<dimension_type>& indices) {
87 // The vector `indices' contains one entry for each equivalence
88 // class, storing the index of the corresponding leader in
89 // increasing order: it is used to avoid repeated tests for leadership.
90 PPL_ASSERT(indices.size() == 0);
91 PPL_ASSERT(0 == predecessor[0]);
92 indices.push_back(0);
93 for (dimension_type i = 1, p_size = predecessor.size(); i != p_size; ++i) {
94 if (i == predecessor[i]) {
95 indices.push_back(i);
96 }
97 }
98 }
99