00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023 #include <ppl-config.h>
00024
00025 #include "Generator_System.defs.hh"
00026 #include "Generator_System.inlines.hh"
00027 #include "Constraint.defs.hh"
00028 #include "Scalar_Products.defs.hh"
00029 #include <cassert>
00030 #include <string>
00031 #include <vector>
00032 #include <iostream>
00033 #include <stdexcept>
00034
00035 namespace PPL = Parma_Polyhedra_Library;
00036
00037 bool
00038 PPL::Generator_System::
00039 adjust_topology_and_space_dimension(const Topology new_topology,
00040 const dimension_type new_space_dim) {
00041 assert(space_dimension() <= new_space_dim);
00042
00043 const dimension_type old_space_dim = space_dimension();
00044 const Topology old_topology = topology();
00045 dimension_type cols_to_be_added = new_space_dim - old_space_dim;
00046
00047
00048 if (has_no_rows()) {
00049 if (num_columns() == 0)
00050 if (new_topology == NECESSARILY_CLOSED) {
00051 add_zero_columns(cols_to_be_added + 1);
00052 set_necessarily_closed();
00053 }
00054 else {
00055 add_zero_columns(cols_to_be_added + 2);
00056 set_not_necessarily_closed();
00057 }
00058 else
00059
00060 if (old_topology != new_topology)
00061 if (new_topology == NECESSARILY_CLOSED) {
00062 switch (cols_to_be_added) {
00063 case 0:
00064 remove_trailing_columns(1);
00065 break;
00066 case 1:
00067
00068 break;
00069 default:
00070 add_zero_columns(cols_to_be_added - 1);
00071 }
00072 set_necessarily_closed();
00073 }
00074 else {
00075
00076
00077 add_zero_columns(cols_to_be_added + 1);
00078 set_not_necessarily_closed();
00079 }
00080 else
00081
00082 if (cols_to_be_added > 0)
00083 add_zero_columns(cols_to_be_added);
00084 assert(OK());
00085 return true;
00086 }
00087
00088
00089 if (cols_to_be_added > 0)
00090 if (old_topology != new_topology)
00091 if (new_topology == NECESSARILY_CLOSED) {
00092
00093
00094
00095
00096 if (has_closure_points())
00097 return false;
00098
00099
00100
00101
00102 Generator_System& gs = *this;
00103 dimension_type num_closure_points = 0;
00104 dimension_type gs_end = gs.num_rows();
00105 for (dimension_type i = 0; i < gs_end; ) {
00106
00107
00108 if (num_closure_points > 0)
00109
00110 std::swap(gs[i], gs[i+num_closure_points]);
00111 if (gs[i].is_closure_point()) {
00112 ++num_closure_points;
00113 --gs_end;
00114 }
00115 else
00116 ++i;
00117 }
00118
00119 if (num_closure_points > 0) {
00120 assert(num_closure_points == num_rows() - gs_end);
00121 erase_to_end(gs_end);
00122 }
00123
00124
00125
00126 remove_trailing_columns(1);
00127 set_necessarily_closed();
00128 normalize();
00129 add_zero_columns(cols_to_be_added);
00130 }
00131 else {
00132
00133
00134
00135
00136 add_zero_columns(cols_to_be_added + 1);
00137 Generator_System& gs = *this;
00138 const dimension_type eps_index = new_space_dim + 1;
00139 for (dimension_type i = num_rows(); i-- > 0; )
00140 gs[i][eps_index] = gs[i][0];
00141 set_not_necessarily_closed();
00142 }
00143 else {
00144
00145 add_zero_columns(cols_to_be_added);
00146
00147
00148 if (old_topology == NOT_NECESSARILY_CLOSED)
00149 swap_columns(old_space_dim + 1, new_space_dim + 1);
00150 }
00151 else
00152
00153 if (old_topology != new_topology) {
00154 if (new_topology == NECESSARILY_CLOSED) {
00155
00156
00157
00158 if (has_closure_points())
00159 return false;
00160
00161 remove_trailing_columns(1);
00162 set_necessarily_closed();
00163 }
00164 else {
00165
00166
00167
00168 add_zero_columns(1);
00169 Generator_System& gs = *this;
00170 const dimension_type eps_index = new_space_dim + 1;
00171 for (dimension_type i = num_rows(); i-- > 0; )
00172 gs[i][eps_index] = gs[i][0];
00173 set_not_necessarily_closed();
00174 }
00175 }
00176
00177 assert(OK());
00178 return true;
00179 }
00180
00181
00182
00183
00184
00185 void
00186 PPL::Generator_System::add_corresponding_closure_points() {
00187 assert(!is_necessarily_closed());
00188
00189
00190 Generator_System& gs = *this;
00191 const dimension_type n_rows = gs.num_rows();
00192 const dimension_type eps_index = gs.num_columns() - 1;
00193 for (dimension_type i = n_rows; i-- > 0; ) {
00194 const Generator& g = gs[i];
00195 if (g[eps_index] > 0) {
00196
00197 Generator cp = g;
00198 cp[eps_index] = 0;
00199
00200 cp.normalize();
00201 gs.add_pending_row(cp);
00202 }
00203 }
00204 assert(OK());
00205 }
00206
00207
00208
00209
00210
00211
00212 void
00213 PPL::Generator_System::add_corresponding_points() {
00214 assert(!is_necessarily_closed());
00215
00216
00217 Generator_System& gs = *this;
00218 const dimension_type n_rows = gs.num_rows();
00219 const dimension_type eps_index = gs.num_columns() - 1;
00220 for (dimension_type i = 0; i < n_rows; i++) {
00221 const Generator& g = gs[i];
00222 if (!g.is_line_or_ray() && g[eps_index] == 0) {
00223
00224
00225 Generator p = g;
00226 p[eps_index] = p[0];
00227 gs.add_pending_row(p);
00228 }
00229 }
00230 assert(OK());
00231 }
00232
00233 bool
00234 PPL::Generator_System::has_closure_points() const {
00235 if (is_necessarily_closed())
00236 return false;
00237
00238 for (Generator_System::const_iterator i = begin(),
00239 this_end = end(); i != this_end; ++i)
00240 if (i->is_closure_point())
00241 return true;
00242 return false;
00243 }
00244
00245 bool
00246 PPL::Generator_System::has_points() const {
00247 const Generator_System& gs = *this;
00248
00249 if (is_necessarily_closed())
00250 for (dimension_type i = num_rows(); i-- > 0; ) {
00251 if (!gs[i].is_line_or_ray())
00252 return true;
00253 }
00254 else {
00255
00256 const dimension_type eps_index = gs.num_columns() - 1;
00257 for (dimension_type i = num_rows(); i-- > 0; )
00258 if (gs[i][eps_index] != 0)
00259 return true;
00260 }
00261 return false;
00262 }
00263
00264 void
00265 PPL::Generator_System::const_iterator::skip_forward() {
00266 const Linear_System::const_iterator gsp_end = gsp->end();
00267 if (i != gsp_end) {
00268 Linear_System::const_iterator i_next = i;
00269 ++i_next;
00270 if (i_next != gsp_end) {
00271 const Generator& cp = static_cast<const Generator&>(*i);
00272 const Generator& p = static_cast<const Generator&>(*i_next);
00273 if (cp.is_closure_point()
00274 && p.is_point()
00275 && cp.is_matching_closure_point(p))
00276 i = i_next;
00277 }
00278 }
00279 }
00280
00281 void
00282 PPL::Generator_System::insert(const Generator& g) {
00283
00284
00285 assert(num_pending_rows() == 0);
00286 if (topology() == g.topology())
00287 Linear_System::insert(g);
00288 else
00289
00290 if (is_necessarily_closed()) {
00291
00292
00293
00294
00295
00296
00297 const dimension_type eps_index = num_columns();
00298 add_zero_columns(1);
00299 Generator_System& gs = *this;
00300 for (dimension_type i = num_rows(); i-- > 0; ) {
00301 Generator& gen = gs[i];
00302 if (!gen.is_line_or_ray())
00303 gen[eps_index] = gen[0];
00304 }
00305 set_not_necessarily_closed();
00306
00307 Linear_System::insert(g);
00308 }
00309 else {
00310
00311
00312
00313 const dimension_type new_size = 2 + std::max(g.space_dimension(),
00314 space_dimension());
00315 Generator tmp_g(g, new_size);
00316
00317
00318
00319 if (!tmp_g.is_line_or_ray())
00320 tmp_g[new_size - 1] = tmp_g[0];
00321 tmp_g.set_not_necessarily_closed();
00322
00323 Linear_System::insert(tmp_g);
00324 }
00325 assert(OK());
00326 }
00327
00328 void
00329 PPL::Generator_System::insert_pending(const Generator& g) {
00330 if (topology() == g.topology())
00331 Linear_System::insert_pending(g);
00332 else
00333
00334 if (is_necessarily_closed()) {
00335
00336
00337
00338
00339
00340
00341 const dimension_type eps_index = num_columns();
00342 add_zero_columns(1);
00343 Generator_System& gs = *this;
00344 for (dimension_type i = num_rows(); i-- > 0; ) {
00345 Generator& gen = gs[i];
00346 if (!gen.is_line_or_ray())
00347 gen[eps_index] = gen[0];
00348 }
00349 set_not_necessarily_closed();
00350
00351 Linear_System::insert_pending(g);
00352 }
00353 else {
00354
00355
00356
00357 const dimension_type new_size = 2 + std::max(g.space_dimension(),
00358 space_dimension());
00359 Generator tmp_g(g, new_size);
00360
00361
00362
00363 if (!tmp_g.is_line_or_ray())
00364 tmp_g[new_size - 1] = tmp_g[0];
00365 tmp_g.set_not_necessarily_closed();
00366
00367 Linear_System::insert_pending(tmp_g);
00368 }
00369 assert(OK());
00370 }
00371
00372 PPL::dimension_type
00373 PPL::Generator_System::num_lines() const {
00374
00375
00376 assert(num_pending_rows() == 0);
00377 const Generator_System& gs = *this;
00378 dimension_type n = 0;
00379
00380
00381 if (is_sorted()) {
00382 dimension_type nrows = num_rows();
00383 for (dimension_type i = 0; i < nrows && gs[i].is_line(); ++i)
00384 ++n;
00385 }
00386 else
00387 for (dimension_type i = num_rows(); i-- > 0 ; )
00388 if (gs[i].is_line())
00389 ++n;
00390 return n;
00391 }
00392
00393 PPL::dimension_type
00394 PPL::Generator_System::num_rays() const {
00395
00396
00397 assert(num_pending_rows() == 0);
00398 const Generator_System& gs = *this;
00399 dimension_type n = 0;
00400
00401
00402
00403 if (is_sorted()) {
00404 for (dimension_type i = num_rows(); i != 0 && gs[--i].is_ray_or_point(); )
00405 if (gs[i].is_line_or_ray())
00406 ++n;
00407 }
00408 else
00409 for (dimension_type i = num_rows(); i-- > 0 ; )
00410 if (gs[i].is_ray())
00411 ++n;
00412 return n;
00413 }
00414
00415 PPL::Poly_Con_Relation
00416 PPL::Generator_System::relation_with(const Constraint& c) const {
00417
00418
00419
00420 assert(space_dimension() >= c.space_dimension());
00421
00422
00423 const dimension_type n_rows = num_rows();
00424 assert(n_rows > 0);
00425 const Generator_System& gs = *this;
00426
00427
00428
00429 Poly_Con_Relation result = Poly_Con_Relation::saturates();
00430
00431 switch (c.type()) {
00432
00433 case Constraint::EQUALITY:
00434 {
00435
00436
00437 result = result && Poly_Con_Relation::is_included();
00438
00439
00440
00441
00442 int first_point_or_nonsaturating_ray_sign = 2;
00443
00444 for (dimension_type i = n_rows; i-- > 0; ) {
00445 const Generator& g = gs[i];
00446 const int sp_sign = Scalar_Products::sign(c, g);
00447
00448
00449
00450 if (sp_sign == 0) {
00451 if (g.is_point()) {
00452 if (first_point_or_nonsaturating_ray_sign == 2)
00453
00454
00455 first_point_or_nonsaturating_ray_sign = 0;
00456 else
00457
00458 if (first_point_or_nonsaturating_ray_sign != 0)
00459 return Poly_Con_Relation::strictly_intersects();
00460 }
00461 }
00462 else
00463
00464 switch (g.type()) {
00465
00466 case Generator::LINE:
00467
00468
00469
00470 return Poly_Con_Relation::strictly_intersects();
00471
00472 case Generator::RAY:
00473 if (first_point_or_nonsaturating_ray_sign == 2) {
00474
00475
00476 first_point_or_nonsaturating_ray_sign = sp_sign;
00477 result = Poly_Con_Relation::is_disjoint();
00478 }
00479 else
00480
00481 if (sp_sign != first_point_or_nonsaturating_ray_sign)
00482 return Poly_Con_Relation::strictly_intersects();
00483 break;
00484
00485 case Generator::POINT:
00486 case Generator::CLOSURE_POINT:
00487
00488
00489 if (first_point_or_nonsaturating_ray_sign == 2) {
00490
00491
00492 first_point_or_nonsaturating_ray_sign = sp_sign;
00493 result = Poly_Con_Relation::is_disjoint();
00494 }
00495 else
00496
00497 if (sp_sign != first_point_or_nonsaturating_ray_sign)
00498 return Poly_Con_Relation::strictly_intersects();
00499 break;
00500 }
00501 }
00502 }
00503 break;
00504
00505 case Constraint::NONSTRICT_INEQUALITY:
00506 {
00507
00508
00509 result = result && Poly_Con_Relation::is_included();
00510
00511
00512
00513 bool first_point_or_nonsaturating_ray = true;
00514
00515 for (dimension_type i = n_rows; i-- > 0; ) {
00516 const Generator& g = gs[i];
00517 const int sp_sign = Scalar_Products::sign(c, g);
00518
00519
00520
00521 if (sp_sign == 0) {
00522 if (g.is_point()) {
00523 if (first_point_or_nonsaturating_ray)
00524
00525
00526 first_point_or_nonsaturating_ray = false;
00527 else
00528
00529 if (result == Poly_Con_Relation::is_disjoint())
00530
00531
00532 return Poly_Con_Relation::strictly_intersects();
00533 }
00534 }
00535 else
00536
00537 switch (g.type()) {
00538
00539 case Generator::LINE:
00540
00541
00542
00543 return Poly_Con_Relation::strictly_intersects();
00544
00545 case Generator::RAY:
00546 if (first_point_or_nonsaturating_ray) {
00547
00548
00549 first_point_or_nonsaturating_ray = false;
00550 result = (sp_sign > 0)
00551 ? Poly_Con_Relation::is_included()
00552 : Poly_Con_Relation::is_disjoint();
00553 }
00554 else {
00555
00556 if ((sp_sign > 0
00557 && result == Poly_Con_Relation::is_disjoint())
00558 || (sp_sign < 0
00559 && result.implies(Poly_Con_Relation::is_included())))
00560
00561
00562
00563
00564
00565 return Poly_Con_Relation::strictly_intersects();
00566 if (sp_sign > 0)
00567
00568
00569
00570 result = Poly_Con_Relation::is_included();
00571 }
00572 break;
00573
00574 case Generator::POINT:
00575 case Generator::CLOSURE_POINT:
00576
00577
00578 if (first_point_or_nonsaturating_ray) {
00579
00580
00581
00582
00583
00584
00585
00586
00587 first_point_or_nonsaturating_ray = false;
00588 if (sp_sign > 0)
00589 result = Poly_Con_Relation::is_included();
00590 else if (sp_sign < 0)
00591 result = Poly_Con_Relation::is_disjoint();
00592 }
00593 else {
00594
00595 if ((sp_sign > 0
00596 && result == Poly_Con_Relation::is_disjoint())
00597 || (sp_sign < 0
00598 && result.implies(Poly_Con_Relation::is_included())))
00599
00600
00601
00602
00603
00604 return Poly_Con_Relation::strictly_intersects();
00605 if (sp_sign > 0)
00606
00607
00608
00609 result = Poly_Con_Relation::is_included();
00610 }
00611 break;
00612 }
00613 }
00614 }
00615 break;
00616
00617 case Constraint::STRICT_INEQUALITY:
00618 {
00619
00620
00621 result = result && Poly_Con_Relation::is_disjoint();
00622
00623
00624
00625 bool first_point_or_nonsaturating_ray = true;
00626 for (dimension_type i = n_rows; i-- > 0; ) {
00627 const Generator& g = gs[i];
00628
00629
00630 const int sp_sign = Scalar_Products::reduced_sign(c, g);
00631
00632
00633
00634 if (sp_sign == 0) {
00635 if (g.is_point()) {
00636 if (first_point_or_nonsaturating_ray)
00637
00638
00639 first_point_or_nonsaturating_ray = false;
00640 else
00641
00642 if (result == Poly_Con_Relation::is_included())
00643 return Poly_Con_Relation::strictly_intersects();
00644 }
00645 }
00646 else
00647
00648 switch (g.type()) {
00649
00650 case Generator::LINE:
00651
00652
00653
00654 return Poly_Con_Relation::strictly_intersects();
00655
00656 case Generator::RAY:
00657 if (first_point_or_nonsaturating_ray) {
00658
00659
00660 first_point_or_nonsaturating_ray = false;
00661 result = (sp_sign > 0)
00662 ? Poly_Con_Relation::is_included()
00663 : Poly_Con_Relation::is_disjoint();
00664 }
00665 else {
00666
00667 if ((sp_sign > 0
00668 && result.implies(Poly_Con_Relation::is_disjoint()))
00669 ||
00670 (sp_sign <= 0
00671 && result == Poly_Con_Relation::is_included()))
00672 return Poly_Con_Relation::strictly_intersects();
00673 if (sp_sign < 0)
00674
00675
00676
00677 result = Poly_Con_Relation::is_disjoint();
00678 }
00679 break;
00680
00681 case Generator::POINT:
00682 case Generator::CLOSURE_POINT:
00683 if (first_point_or_nonsaturating_ray) {
00684
00685
00686
00687
00688
00689
00690
00691
00692 first_point_or_nonsaturating_ray = false;
00693 if (sp_sign > 0)
00694 result = Poly_Con_Relation::is_included();
00695 else if (sp_sign < 0)
00696 result = Poly_Con_Relation::is_disjoint();
00697 }
00698 else {
00699
00700 if ((sp_sign > 0
00701 && result.implies(Poly_Con_Relation::is_disjoint()))
00702 ||
00703 (sp_sign <= 0
00704 && result == Poly_Con_Relation::is_included()))
00705 return Poly_Con_Relation::strictly_intersects();
00706 if (sp_sign < 0)
00707
00708
00709
00710 result = Poly_Con_Relation::is_disjoint();
00711 }
00712 break;
00713 }
00714 }
00715 }
00716 break;
00717 }
00718
00719 return result;
00720 }
00721
00722
00723 bool
00724 PPL::Generator_System::satisfied_by_all_generators(const Constraint& c) const {
00725 assert(c.space_dimension() <= space_dimension());
00726
00727
00728
00729
00730 Topology_Adjusted_Scalar_Product_Sign sps(c);
00731
00732 const Generator_System& gs = *this;
00733 switch (c.type()) {
00734 case Constraint::EQUALITY:
00735
00736 for (dimension_type i = gs.num_rows(); i-- > 0; )
00737 if (sps(c, gs[i]) != 0)
00738 return false;
00739 break;
00740 case Constraint::NONSTRICT_INEQUALITY:
00741
00742
00743 for (dimension_type i = gs.num_rows(); i-- > 0; ) {
00744 const Generator& g = gs[i];
00745 const int sp_sign = sps(c, g);
00746 if (g.is_line()) {
00747 if (sp_sign != 0)
00748 return false;
00749 }
00750 else
00751
00752 if (sp_sign < 0)
00753 return false;
00754 }
00755 break;
00756 case Constraint::STRICT_INEQUALITY:
00757
00758
00759 for (dimension_type i = gs.num_rows(); i-- > 0; ) {
00760 const Generator& g = gs[i];
00761 const int sp_sign = sps(c, g);
00762 switch (g.type()) {
00763 case Generator::POINT:
00764 if (sp_sign <= 0)
00765 return false;
00766 break;
00767 case Generator::LINE:
00768 if (sp_sign != 0)
00769 return false;
00770 break;
00771 default:
00772
00773 if (sp_sign < 0)
00774 return false;
00775 break;
00776 }
00777 }
00778 break;
00779 }
00780
00781 return true;
00782 }
00783
00784
00785 void
00786 PPL::Generator_System
00787 ::affine_image(dimension_type v,
00788 const Linear_Expression& expr,
00789 Coefficient_traits::const_reference denominator) {
00790 Generator_System& x = *this;
00791
00792
00793
00794 assert(v > 0 && v <= x.space_dimension());
00795 assert(expr.space_dimension() <= x.space_dimension());
00796 assert(denominator > 0);
00797
00798 const dimension_type n_columns = x.num_columns();
00799 const dimension_type n_rows = x.num_rows();
00800
00801
00802
00803 TEMP_INTEGER(numerator);
00804 for (dimension_type i = n_rows; i-- > 0; ) {
00805 Generator& row = x[i];
00806 Scalar_Products::assign(numerator, expr, row);
00807 std::swap(numerator, row[v]);
00808 }
00809
00810 if (denominator != 1) {
00811
00812
00813
00814 for (dimension_type i = n_rows; i-- > 0; ) {
00815 Generator& row = x[i];
00816 for (dimension_type j = n_columns; j-- > 0; )
00817 if (j != v)
00818 row[j] *= denominator;
00819 }
00820 }
00821
00822
00823
00824 const bool not_invertible = (v > expr.space_dimension() || expr[v] == 0);
00825 if (not_invertible)
00826 x.remove_invalid_lines_and_rays();
00827
00828
00829 x.strong_normalize();
00830 }
00831
00832 void
00833 PPL::Generator_System::ascii_dump(std::ostream& s) const {
00834 const Generator_System& x = *this;
00835 const dimension_type x_num_rows = x.num_rows();
00836 const dimension_type x_num_columns = x.num_columns();
00837 s << "topology " << (is_necessarily_closed()
00838 ? "NECESSARILY_CLOSED"
00839 : "NOT_NECESSARILY_CLOSED")
00840 << "\n"
00841 << x_num_rows << " x " << x_num_columns << ' '
00842 << (x.is_sorted() ? "(sorted)" : "(not_sorted)")
00843 << "\n"
00844 << "index_first_pending " << x.first_pending_row()
00845 << "\n";
00846 for (dimension_type i = 0; i < x_num_rows; ++i) {
00847 const Generator& g = x[i];
00848 for (dimension_type j = 0; j < x_num_columns; ++j)
00849 s << g[j] << ' ';
00850 switch (g.type()) {
00851 case Generator::LINE:
00852 s << "L";
00853 break;
00854 case Generator::RAY:
00855 s << "R";
00856 break;
00857 case Generator::POINT:
00858 s << "P";
00859 break;
00860 case Generator::CLOSURE_POINT:
00861 s << "C";
00862 break;
00863 }
00864 s << "\n";
00865 }
00866 }
00867
00868 PPL_OUTPUT_DEFINITIONS(Generator_System)
00869
00870 bool
00871 PPL::Generator_System::ascii_load(std::istream& s) {
00872 std::string str;
00873 if (!(s >> str) || str != "topology")
00874 return false;
00875 if (!(s >> str))
00876 return false;
00877 if (str == "NECESSARILY_CLOSED")
00878 set_necessarily_closed();
00879 else {
00880 if (str != "NOT_NECESSARILY_CLOSED")
00881 return false;
00882 set_not_necessarily_closed();
00883 }
00884
00885 dimension_type nrows;
00886 dimension_type ncols;
00887 if (!(s >> nrows))
00888 return false;
00889 if (!(s >> str))
00890 return false;
00891 if (!(s >> ncols))
00892 return false;
00893 resize_no_copy(nrows, ncols);
00894
00895 if (!(s >> str) || (str != "(sorted)" && str != "(not_sorted)"))
00896 return false;
00897 set_sorted(str == "(sorted)");
00898 dimension_type index;
00899 if (!(s >> str) || str != "index_first_pending")
00900 return false;
00901 if (!(s >> index))
00902 return false;
00903 set_index_first_pending_row(index);
00904
00905 Generator_System& x = *this;
00906 for (dimension_type i = 0; i < x.num_rows(); ++i) {
00907 for (dimension_type j = 0; j < x.num_columns(); ++j)
00908 if (!(s >> x[i][j]))
00909 return false;
00910
00911 if (!(s >> str))
00912 return false;
00913 if (str == "L")
00914 x[i].set_is_line();
00915 else
00916 x[i].set_is_ray_or_point();
00917
00918
00919 switch (x[i].type()) {
00920 case Generator::LINE:
00921 if (str == "L")
00922 continue;
00923 break;
00924 case Generator::RAY:
00925 if (str == "R")
00926 continue;
00927 break;
00928 case Generator::POINT:
00929 if (str == "P")
00930 continue;
00931 break;
00932 case Generator::CLOSURE_POINT:
00933 if (str == "C")
00934 continue;
00935 break;
00936 }
00937
00938 return false;
00939 }
00940
00941
00942 assert(OK());
00943 return true;
00944 }
00945
00946 void
00947 PPL::Generator_System::remove_invalid_lines_and_rays() {
00948
00949
00950
00951
00952 Generator_System& gs = *this;
00953 dimension_type n_rows = gs.num_rows();
00954 if (num_pending_rows() == 0) {
00955 for (dimension_type i = n_rows; i-- > 0; ) {
00956 Generator& g = gs[i];
00957 if (g.is_line_or_ray() && g.all_homogeneous_terms_are_zero()) {
00958
00959 --n_rows;
00960 std::swap(g, gs[n_rows]);
00961 gs.set_sorted(false);
00962 }
00963 }
00964 set_index_first_pending_row(n_rows);
00965 }
00966 else {
00967
00968
00969
00970
00971
00972
00973
00974 assert(num_pending_rows() > 0);
00975 dimension_type first_pending = first_pending_row();
00976 for (dimension_type i = first_pending; i-- > 0; ) {
00977 Generator& g = gs[i];
00978 if (g.is_line_or_ray() && g.all_homogeneous_terms_are_zero()) {
00979
00980 --first_pending;
00981 std::swap(g, gs[first_pending]);
00982 gs.set_sorted(false);
00983 }
00984 }
00985 const dimension_type num_invalid_rows
00986 = first_pending_row() - first_pending;
00987 set_index_first_pending_row(first_pending);
00988 for (dimension_type i = 0; i < num_invalid_rows; ++i)
00989 std::swap(gs[n_rows - i], gs[first_pending + i]);
00990 n_rows -= num_invalid_rows;
00991 for (dimension_type i = n_rows; i-- > first_pending; ) {
00992 Generator& g = gs[i];
00993 if (g.is_line_or_ray() && g.all_homogeneous_terms_are_zero()) {
00994
00995 --n_rows;
00996 std::swap(g, gs[n_rows]);
00997 gs.set_sorted(false);
00998 }
00999 }
01000 }
01001 gs.erase_to_end(n_rows);
01002 }
01003
01004 const PPL::Generator_System* PPL::Generator_System::zero_dim_univ_p = 0;
01005
01006 void
01007 PPL::Generator_System::initialize() {
01008 assert(zero_dim_univ_p == 0);
01009 zero_dim_univ_p
01010 = new Generator_System(Generator::zero_dim_point());
01011 }
01012
01013 void
01014 PPL::Generator_System::finalize() {
01015 assert(zero_dim_univ_p != 0);
01016 delete zero_dim_univ_p;
01017 zero_dim_univ_p = 0;
01018 }
01019
01020 bool
01021 PPL::Generator_System::OK() const {
01022
01023
01024
01025 if (!Linear_System::OK(false))
01026 return false;
01027
01028
01029 const Generator_System& x = *this;
01030 for (dimension_type i = num_rows(); i-- > 0; )
01031 if (!x[i].OK())
01032 return false;
01033
01034
01035 return true;
01036 }
01037
01039 std::ostream&
01040 PPL::IO_Operators::operator<<(std::ostream& s, const Generator_System& gs) {
01041 Generator_System::const_iterator i = gs.begin();
01042 const Generator_System::const_iterator gs_end = gs.end();
01043 if (i == gs_end)
01044 return s << "false";
01045 while (true) {
01046 s << *i++;
01047 if (i == gs_end)
01048 return s;
01049 s << ", ";
01050 }
01051 }