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