00001 /* Grid_Certificate class implementation 00002 (non-inline member functions). 00003 Copyright (C) 2001-2008 Roberto Bagnara <bagnara@cs.unipr.it> 00004 00005 This file is part of the Parma Polyhedra Library (PPL). 00006 00007 The PPL is free software; you can redistribute it and/or modify it 00008 under the terms of the GNU General Public License as published by the 00009 Free Software Foundation; either version 3 of the License, or (at your 00010 option) any later version. 00011 00012 The PPL is distributed in the hope that it will be useful, but WITHOUT 00013 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 00014 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 00015 for more details. 00016 00017 You should have received a copy of the GNU General Public License 00018 along with this program; if not, write to the Free Software Foundation, 00019 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02111-1307, USA. 00020 00021 For the most up-to-date information see the Parma Polyhedra Library 00022 site: http://www.cs.unipr.it/ppl/ . */ 00023 00024 #include <ppl-config.h> 00025 00026 #include "Grid_Certificate.defs.hh" 00027 00028 #include "Grid.defs.hh" 00029 #include <cassert> 00030 #include <iostream> 00031 00032 namespace PPL = Parma_Polyhedra_Library; 00033 00034 PPL::Grid_Certificate::Grid_Certificate(const Grid& cgr) 00035 : num_equalities(0), num_proper_congruences(0) { 00036 Grid& gr = const_cast<Grid&>(cgr); 00037 // As in Polyhedron assume that gr contains at least one point. 00038 assert(!gr.marked_empty()); 00039 if (gr.space_dimension() == 0) 00040 return; 00041 // One of the systems must be in minimal form. 00042 if (gr.congruences_are_up_to_date()) 00043 if (gr.congruences_are_minimized()) { 00044 num_proper_congruences = gr.con_sys.num_proper_congruences(); 00045 num_equalities = gr.con_sys.num_equalities(); 00046 } 00047 else 00048 if (gr.generators_are_up_to_date() && gr.generators_are_minimized()) { 00049 // Calculate number of congruences from generators. 00050 num_proper_congruences 00051 = gr.gen_sys.num_parameters() + 1 /* Integrality cg. */; 00052 num_equalities = gr.space_dimension() + 1 - gr.gen_sys.num_rows(); 00053 } 00054 else { 00055 // Minimize gr congruence system. As in Polyhedron assume 00056 // that gr contains at least one point. 00057 #ifndef NDEBUG 00058 Grid::simplify(gr.con_sys, gr.dim_kinds); 00059 #else 00060 bool contains_points = Grid::simplify(gr.con_sys, gr.dim_kinds); 00061 used(contains_points); // Quiet compiler warning. 00062 assert(contains_points); 00063 #endif 00064 gr.set_congruences_minimized(); 00065 00066 num_proper_congruences = gr.con_sys.num_proper_congruences(); 00067 num_equalities = gr.con_sys.num_equalities(); 00068 } 00069 else { 00070 if (!gr.generators_are_minimized()) { 00071 // Minimize gr generator system. As in Polyhedron assume that 00072 // gr contains at least one point. 00073 Grid::simplify(gr.gen_sys, gr.dim_kinds); 00074 // If gen_sys contained rows before being reduced, it should 00075 // contain at least a single point afterward. 00076 assert(!gr.gen_sys.empty()); 00077 gr.set_generators_minimized(); 00078 } 00079 // Calculate number of congruences from generators. 00080 num_proper_congruences 00081 = gr.gen_sys.num_parameters() + 1 /* Integrality cg. */; 00082 num_equalities 00083 = gr.space_dimension() + 1 - gr.gen_sys.num_rows(); 00084 } 00085 } 00086 00087 int 00088 PPL::Grid_Certificate::compare(const Grid_Certificate& y) const { 00089 assert(OK() && y.OK()); 00090 if (num_equalities == y.num_equalities) { 00091 if (num_proper_congruences == y.num_proper_congruences) 00092 return 0; 00093 else 00094 return num_proper_congruences > y.num_proper_congruences ? 1 : -1; 00095 } 00096 return num_equalities > y.num_equalities ? 1 : -1; 00097 } 00098 00099 int 00100 PPL::Grid_Certificate::compare(const Grid& gr) const { 00101 Grid_Certificate gc(gr); 00102 return compare(gc); 00103 } 00104 00105 bool 00106 PPL::Grid_Certificate::OK() const { 00107 #ifndef NDEBUG 00108 using std::endl; 00109 using std::cerr; 00110 #endif 00111 00112 // All tests passed. 00113 return true; 00114 }