1 /* Grid_Certificate class implementation
2 (non-inline member functions).
3 Copyright (C) 2001-2010 Roberto Bagnara <bagnara@cs.unipr.it>
4 Copyright (C) 2010-2016 BUGSENG srl (http://bugseng.com)
5
6 This file is part of the Parma Polyhedra Library (PPL).
7
8 The PPL is free software; you can redistribute it and/or modify it
9 under the terms of the GNU General Public License as published by the
10 Free Software Foundation; either version 3 of the License, or (at your
11 option) any later version.
12
13 The PPL is distributed in the hope that it will be useful, but WITHOUT
14 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with this program; if not, write to the Free Software Foundation,
20 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02111-1307, USA.
21
22 For the most up-to-date information see the Parma Polyhedra Library
23 site: http://bugseng.com/products/ppl/ . */
24
25 #include "ppl-config.h"
26 #include "Grid_Certificate_defs.hh"
27 #include "Grid_defs.hh"
28 #include "assertions.hh"
29 #include <iostream>
30
31 namespace PPL = Parma_Polyhedra_Library;
32
Grid_Certificate(const Grid & gr)33 PPL::Grid_Certificate::Grid_Certificate(const Grid& gr)
34 : num_equalities(0), num_proper_congruences(0) {
35
36 // As in Polyhedron assume that `gr' contains at least one point.
37 PPL_ASSERT(!gr.marked_empty());
38 if (gr.space_dimension() == 0) {
39 return;
40 }
41 // One of the systems must be in minimal form.
42 if (gr.congruences_are_up_to_date()) {
43 if (gr.congruences_are_minimized()) {
44 num_proper_congruences = gr.con_sys.num_proper_congruences();
45 num_equalities = gr.con_sys.num_equalities();
46 }
47 else {
48 if (gr.generators_are_up_to_date() && gr.generators_are_minimized()) {
49 // Calculate number of congruences from generators.
50 num_proper_congruences
51 = gr.gen_sys.num_parameters() + 1 /* Integrality cg. */;
52 num_equalities = gr.space_dimension() + 1 - gr.gen_sys.num_rows();
53 }
54 else {
55 // Minimize `gr' congruence system. As in Polyhedron assume
56 // that `gr' contains at least one point.
57 Grid& mgr = const_cast<Grid&>(gr);
58 const bool empty = Grid::simplify(mgr.con_sys, mgr.dim_kinds);
59 // Avoid possible compiler warning.
60 PPL_USED(empty);
61 PPL_ASSERT(!empty);
62 mgr.set_congruences_minimized();
63
64 num_proper_congruences = mgr.con_sys.num_proper_congruences();
65 num_equalities = mgr.con_sys.num_equalities();
66 }
67 }
68 }
69 else {
70 if (!gr.generators_are_minimized()) {
71 // Minimize `gr' generator system. As in Polyhedron assume that
72 // `gr' contains at least one point.
73 Grid& mgr = const_cast<Grid&>(gr);
74 Grid::simplify(mgr.gen_sys, mgr.dim_kinds);
75 // If gen_sys contained rows before being reduced, it should
76 // contain at least a single point afterward.
77 PPL_ASSERT(!mgr.gen_sys.empty());
78 mgr.set_generators_minimized();
79 }
80 // Calculate number of congruences from generators.
81 num_proper_congruences
82 = gr.gen_sys.num_parameters() + 1 /* Integrality cg. */;
83 num_equalities
84 = gr.space_dimension() + 1 - gr.gen_sys.num_rows();
85 }
86 }
87
88 int
compare(const Grid_Certificate & y) const89 PPL::Grid_Certificate::compare(const Grid_Certificate& y) const {
90 PPL_ASSERT(OK() && y.OK());
91 if (num_equalities == y.num_equalities) {
92 if (num_proper_congruences == y.num_proper_congruences) {
93 return 0;
94 }
95 else {
96 return (num_proper_congruences > y.num_proper_congruences) ? 1 : -1;
97 }
98 }
99 return (num_equalities > y.num_equalities) ? 1 : -1;
100 }
101
102 int
compare(const Grid & gr) const103 PPL::Grid_Certificate::compare(const Grid& gr) const {
104 const Grid_Certificate gc(gr);
105 return compare(gc);
106 }
107
108 bool
OK() const109 PPL::Grid_Certificate::OK() const {
110 // There is nothing to test.
111 return true;
112 }
113