1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
|
/* Grid_Certificate class implementation
(non-inline member functions).
Copyright (C) 2001-2010 Roberto Bagnara <bagnara@cs.unipr.it>
Copyright (C) 2010-2011 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://www.cs.unipr.it/ppl/ . */
#include <ppl-config.h>
#include "Grid_Certificate.defs.hh"
#include "Grid.defs.hh"
#include "assert.hh"
#include <iostream>
namespace PPL = Parma_Polyhedra_Library;
PPL::Grid_Certificate::Grid_Certificate(const Grid& cgr)
: num_equalities(0), num_proper_congruences(0) {
Grid& gr = const_cast<Grid&>(cgr);
// As in Polyhedron assume that gr contains at least one point.
PPL_ASSERT(!gr.marked_empty());
if (gr.space_dimension() == 0)
return;
// One of the systems must be in minimal form.
if (gr.congruences_are_up_to_date())
if (gr.congruences_are_minimized()) {
num_proper_congruences = gr.con_sys.num_proper_congruences();
num_equalities = gr.con_sys.num_equalities();
}
else
if (gr.generators_are_up_to_date() && gr.generators_are_minimized()) {
// Calculate number of congruences from generators.
num_proper_congruences
= gr.gen_sys.num_parameters() + 1 /* Integrality cg. */;
num_equalities = gr.space_dimension() + 1 - gr.gen_sys.num_rows();
}
else {
// Minimize gr congruence system. As in Polyhedron assume
// that gr contains at least one point.
#ifndef NDEBUG
Grid::simplify(gr.con_sys, gr.dim_kinds);
#else
bool contains_points = Grid::simplify(gr.con_sys, gr.dim_kinds);
used(contains_points); // Quiet compiler warning.
PPL_ASSERT(contains_points);
#endif
gr.set_congruences_minimized();
num_proper_congruences = gr.con_sys.num_proper_congruences();
num_equalities = gr.con_sys.num_equalities();
}
else {
if (!gr.generators_are_minimized()) {
// Minimize gr generator system. As in Polyhedron assume that
// gr contains at least one point.
Grid::simplify(gr.gen_sys, gr.dim_kinds);
// If gen_sys contained rows before being reduced, it should
// contain at least a single point afterward.
PPL_ASSERT(!gr.gen_sys.empty());
gr.set_generators_minimized();
}
// Calculate number of congruences from generators.
num_proper_congruences
= gr.gen_sys.num_parameters() + 1 /* Integrality cg. */;
num_equalities
= gr.space_dimension() + 1 - gr.gen_sys.num_rows();
}
}
int
PPL::Grid_Certificate::compare(const Grid_Certificate& y) const {
PPL_ASSERT(OK() && y.OK());
if (num_equalities == y.num_equalities) {
if (num_proper_congruences == y.num_proper_congruences)
return 0;
else
return num_proper_congruences > y.num_proper_congruences ? 1 : -1;
}
return num_equalities > y.num_equalities ? 1 : -1;
}
int
PPL::Grid_Certificate::compare(const Grid& gr) const {
Grid_Certificate gc(gr);
return compare(gc);
}
bool
PPL::Grid_Certificate::OK() const {
#ifndef NDEBUG
using std::endl;
using std::cerr;
#endif
// All tests passed.
return true;
}
|
