00001 /* Grid_Certificate class implementation 00002 (non-inline member functions). 00003 Copyright (C) 2001-2006 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 2 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 <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 00053 = gr.space_dimension() + 1 - gr.gen_sys.num_generators(); 00054 } 00055 else { 00056 // Minimize gr congruence system. As in Polyhedron assume 00057 // that gr contains at least one point. 00058 #ifndef NDEBUG 00059 Grid::simplify(gr.con_sys, gr.dim_kinds); 00060 #else 00061 bool contains_points = Grid::simplify(gr.con_sys, gr.dim_kinds); 00062 used(contains_points); // Quiet compiler warning. 00063 assert(contains_points); 00064 #endif 00065 gr.set_congruences_minimized(); 00066 00067 num_proper_congruences = gr.con_sys.num_proper_congruences(); 00068 num_equalities = gr.con_sys.num_equalities(); 00069 } 00070 else { 00071 if (!gr.generators_are_minimized()) { 00072 // Minimize gr generator system. As in Polyhedron assume that 00073 // gr contains at least one point. 00074 Grid::simplify(gr.gen_sys, gr.dim_kinds); 00075 // If gen_sys contained rows before being reduced, it should 00076 // contain at least a single point afterwards. 00077 assert(gr.gen_sys.num_generators() > 0); 00078 gr.set_generators_minimized(); 00079 } 00080 // Calculate number of congruences from generators. 00081 num_proper_congruences 00082 = gr.gen_sys.num_parameters() + 1 /* Integrality cg. */; 00083 num_equalities 00084 = gr.space_dimension() + 1 - gr.gen_sys.num_generators(); 00085 } 00086 } 00087 00088 int 00089 PPL::Grid_Certificate::compare(const Grid_Certificate& y) const { 00090 assert(OK() && y.OK()); 00091 if (num_equalities == y.num_equalities) 00092 if (num_proper_congruences == y.num_proper_congruences) 00093 return 0; 00094 else 00095 return num_proper_congruences > y.num_proper_congruences ? 1 : -1; 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 }