00001 /* Polyhedron class implementation: conversion(). 00002 Copyright (C) 2001-2008 Roberto Bagnara <bagnara@cs.unipr.it> 00003 00004 This file is part of the Parma Polyhedra Library (PPL). 00005 00006 The PPL is free software; you can redistribute it and/or modify it 00007 under the terms of the GNU General Public License as published by the 00008 Free Software Foundation; either version 3 of the License, or (at your 00009 option) any later version. 00010 00011 The PPL is distributed in the hope that it will be useful, but WITHOUT 00012 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 00013 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 00014 for more details. 00015 00016 You should have received a copy of the GNU General Public License 00017 along with this program; if not, write to the Free Software Foundation, 00018 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02111-1307, USA. 00019 00020 For the most up-to-date information see the Parma Polyhedra Library 00021 site: http://www.cs.unipr.it/ppl/ . */ 00022 00023 #include <ppl-config.h> 00024 00025 #include "Linear_Row.defs.hh" 00026 #include "Linear_System.defs.hh" 00027 #include "Bit_Row.defs.hh" 00028 #include "Bit_Matrix.defs.hh" 00029 #include "Polyhedron.defs.hh" 00030 #include "Scalar_Products.defs.hh" 00031 #include "Temp.defs.hh" 00032 #include <cstddef> 00033 #include <climits> 00034 00035 namespace PPL = Parma_Polyhedra_Library; 00036 00037 // True if abandon_expensive_computations should be checked often, 00038 // where the meaning of "often" is as stated in the documentation 00039 // of that variable. 00040 #define REACTIVE_ABANDONING 1 00041 00351 PPL::dimension_type 00352 PPL::Polyhedron::conversion(Linear_System& source, 00353 const dimension_type start, 00354 Linear_System& dest, 00355 Bit_Matrix& sat, 00356 dimension_type num_lines_or_equalities) { 00357 dimension_type source_num_rows = source.num_rows(); 00358 dimension_type dest_num_rows = dest.num_rows(); 00359 const dimension_type source_num_columns = source.num_columns(); 00360 const dimension_type dest_num_columns = dest.num_columns(); 00361 00362 // By construction, the number of columns of `sat' is the same as 00363 // the number of rows of `source'; also, the number of rows of `sat' 00364 // is the same as the number of rows of `dest'. 00365 assert(source_num_rows == sat.num_columns()); 00366 assert(dest_num_rows == sat.num_rows()); 00367 00368 // If `start > 0', then we are converting the pending constraints. 00369 assert(start == 0 || start == source.first_pending_row()); 00370 00371 // During the iteration on the constraints in `source' we may identify 00372 // constraints that are redundant: these have to be removed by swapping 00373 // the rows of `source', taking care not to compromise the sortedness 00374 // of the constraints that still have to be considered. 00375 // To this end, the following counter keeps the number of redundant 00376 // constraints seen so far, to be used as a displacement when swapping rows. 00377 dimension_type source_num_redundant = 0; 00378 00379 TEMP_INTEGER(normalized_sp_i); 00380 TEMP_INTEGER(normalized_sp_o); 00381 00382 // Converting the sub-system of `source' having rows with indexes 00383 // from `start' to the last one (i.e., `source_num_rows' - 1). 00384 for (dimension_type k = start; k < source_num_rows; ) { 00385 00386 // All the `source_num_redundant' redundant constraints identified so far 00387 // have consecutive indices starting from `k'. 00388 if (source_num_redundant > 0) 00389 // Let the next constraint have index `k'. 00390 // There is no need to swap the columns of `sat' (all zeroes). 00391 std::swap(source[k], source[k+source_num_redundant]); 00392 00393 Linear_Row& source_k = source[k]; 00394 00395 // Constraints and generators must have the same dimension, 00396 // otherwise the scalar product below will bomb. 00397 assert(source_num_columns == dest_num_columns); 00398 00399 // `scalar_prod[i]' will contain the scalar product of the 00400 // constraint `source_k' and the generator `dest[i]'. This 00401 // product is 0 if and only if the generator saturates the 00402 // constraint. 00403 DIRTY_TEMP0(std::vector<Coefficient>, scalar_prod); 00404 const int needed_space = dest_num_rows - scalar_prod.size(); 00405 if (needed_space > 0) 00406 scalar_prod.insert(scalar_prod.end(), needed_space, Coefficient_zero()); 00407 // `index_non_zero' will indicate the first generator in `dest' 00408 // that does not saturate the constraint `source_k'. 00409 dimension_type index_non_zero = 0; 00410 for ( ; index_non_zero < dest_num_rows; ++index_non_zero) { 00411 Scalar_Products::assign(scalar_prod[index_non_zero], 00412 source_k, 00413 dest[index_non_zero]); 00414 if (scalar_prod[index_non_zero] != 0) 00415 // The generator does not saturate the constraint. 00416 break; 00417 #if REACTIVE_ABANDONING 00418 // Check if the client has requested abandoning all expensive 00419 // computations. If so, the exception specified by the client 00420 // is thrown now. 00421 maybe_abandon(); 00422 #endif 00423 } 00424 for (dimension_type i = index_non_zero + 1; i < dest_num_rows; ++i) { 00425 Scalar_Products::assign(scalar_prod[i], source_k, dest[i]); 00426 #if REACTIVE_ABANDONING 00427 maybe_abandon(); 00428 #endif 00429 } 00430 00431 // We first treat the case when `index_non_zero' is less than 00432 // `num_lines_or_equalities', i.e., when the generator that 00433 // does not saturate the constraint `source_k' is a line. 00434 // The other case (described later) is when all the lines 00435 // in `dest' (i.e., all the rows having indexes less than 00436 // `num_lines_or_equalities') do saturate the constraint. 00437 00438 if (index_non_zero < num_lines_or_equalities) { 00439 // Since the generator `dest[index_non_zero]' does not saturate 00440 // the constraint `source_k', it can no longer be a line 00441 // (see saturation rule in Section \ref prelims). 00442 // Therefore, we first transform it to a ray. 00443 dest[index_non_zero].set_is_ray_or_point_or_inequality(); 00444 // Of the two possible choices, we select the ray satisfying 00445 // the constraint (namely, the ray whose scalar product 00446 // with the constraint gives a positive result). 00447 if (scalar_prod[index_non_zero] < 0) { 00448 // The ray `dest[index_non_zero]' lies on the wrong half-space: 00449 // we change it to have the opposite direction. 00450 neg_assign(scalar_prod[index_non_zero]); 00451 for (dimension_type j = dest_num_columns; j-- > 0; ) 00452 neg_assign(dest[index_non_zero][j]); 00453 } 00454 // Having changed a line to a ray, we set `dest' to be a 00455 // non-sorted system, we decrement the number of lines of `dest' and, 00456 // if necessary, we move the new ray below all the remaining lines. 00457 dest.set_sorted(false); 00458 --num_lines_or_equalities; 00459 if (index_non_zero != num_lines_or_equalities) { 00460 std::swap(dest[index_non_zero], 00461 dest[num_lines_or_equalities]); 00462 std::swap(scalar_prod[index_non_zero], 00463 scalar_prod[num_lines_or_equalities]); 00464 } 00465 Linear_Row& dest_nle = dest[num_lines_or_equalities]; 00466 00467 // Computing the new lineality space. 00468 // Since each line must lie on the hyper-plane corresponding to 00469 // the constraint `source_k', the scalar product between 00470 // the line and the constraint must be 0. 00471 // This property already holds for the lines having indexes 00472 // between 0 and `index_non_zero' - 1. 00473 // We have to consider the remaining lines, having indexes 00474 // between `index_non_zero' and `num_lines_or_equalities' - 1. 00475 // Each line that does not saturate the constraint has to be 00476 // linearly combined with generator `dest_nle' so that the 00477 // resulting new line saturates the constraint. 00478 // Note that, by Observation 1 above, the resulting new line 00479 // will still saturate all the constraints that were saturated by 00480 // the old line. 00481 00482 Coefficient& scalar_prod_nle = scalar_prod[num_lines_or_equalities]; 00483 for (dimension_type 00484 i = index_non_zero; i < num_lines_or_equalities; ++i) { 00485 if (scalar_prod[i] != 0) { 00486 // The following fragment optimizes the computation of 00487 // 00488 // Coefficient scale = scalar_prod[i]; 00489 // scale.gcd_assign(scalar_prod_nle); 00490 // Coefficient normalized_sp_i = scalar_prod[i] / scale; 00491 // Coefficient normalized_sp_n = scalar_prod_nle / scale; 00492 // for (dimension_type c = dest_num_columns; c-- > 0; ) { 00493 // dest[i][c] *= normalized_sp_n; 00494 // dest[i][c] -= normalized_sp_i * dest_nle[c]; 00495 // } 00496 normalize2(scalar_prod[i], 00497 scalar_prod_nle, 00498 normalized_sp_i, 00499 normalized_sp_o); 00500 Linear_Row& dest_i = dest[i]; 00501 for (dimension_type c = dest_num_columns; c-- > 0; ) { 00502 Coefficient& dest_i_c = dest_i[c]; 00503 dest_i_c *= normalized_sp_o; 00504 sub_mul_assign(dest_i_c, normalized_sp_i, dest_nle[c]); 00505 } 00506 dest_i.strong_normalize(); 00507 scalar_prod[i] = 0; 00508 // `dest' has already been set as non-sorted. 00509 } 00510 } 00511 00512 // Computing the new pointed cone. 00513 // Similarly to what we have done during the computation of 00514 // the lineality space, we consider all the remaining rays 00515 // (having indexes strictly greater than `num_lines_or_equalities') 00516 // that do not saturate the constraint `source_k'. These rays 00517 // are positively combined with the ray `dest_nle' so that the 00518 // resulting new rays saturate the constraint. 00519 for (dimension_type 00520 i = num_lines_or_equalities + 1; i < dest_num_rows; ++i) { 00521 if (scalar_prod[i] != 0) { 00522 // The following fragment optimizes the computation of 00523 // 00524 // Coefficient scale = scalar_prod[i]; 00525 // scale.gcd_assign(scalar_prod_nle); 00526 // Coefficient normalized_sp_i = scalar_prod[i] / scale; 00527 // Coefficient normalized_sp_n = scalar_prod_nle / scale; 00528 // for (dimension_type c = dest_num_columns; c-- > 0; ) { 00529 // dest[i][c] *= normalized_sp_n; 00530 // dest[i][c] -= normalized_sp_i * dest_nle[c]; 00531 // } 00532 normalize2(scalar_prod[i], 00533 scalar_prod_nle, 00534 normalized_sp_i, 00535 normalized_sp_o); 00536 Linear_Row& dest_i = dest[i]; 00537 for (dimension_type c = dest_num_columns; c-- > 0; ) { 00538 Coefficient& dest_i_c = dest_i[c]; 00539 dest_i_c *= normalized_sp_o; 00540 sub_mul_assign(dest_i_c, normalized_sp_i, dest_nle[c]); 00541 } 00542 dest_i.strong_normalize(); 00543 scalar_prod[i] = 0; 00544 // `dest' has already been set as non-sorted. 00545 } 00546 #if REACTIVE_ABANDONING 00547 maybe_abandon(); 00548 #endif 00549 } 00550 // Since the `scalar_prod_nle' is positive (by construction), it 00551 // does not saturate the constraint `source_k'. Therefore, if 00552 // the constraint is an inequality, we set to 1 the 00553 // corresponding element of `sat' ... 00554 Bit_Row& sat_nle = sat[num_lines_or_equalities]; 00555 if (source_k.is_ray_or_point_or_inequality()) 00556 sat_nle.set(k); 00557 // ... otherwise, the constraint is an equality which is 00558 // violated by the generator `dest_nle': the generator has to be 00559 // removed from `dest'. 00560 else { 00561 --dest_num_rows; 00562 std::swap(dest_nle, dest[dest_num_rows]); 00563 std::swap(scalar_prod_nle, scalar_prod[dest_num_rows]); 00564 std::swap(sat_nle, sat[dest_num_rows]); 00565 // `dest' has already been set as non-sorted. 00566 } 00567 // We continue with the next constraint. 00568 ++k; 00569 } 00570 // Here we have `index_non_zero' >= `num_lines_or_equalities', 00571 // so that all the lines in `dest' saturate the constraint `source_k'. 00572 else { 00573 // First, we reorder the generators in `dest' as follows: 00574 // -# all the lines should have indexes between 0 and 00575 // `num_lines_or_equalities' - 1 (this already holds); 00576 // -# all the rays that saturate the constraint should have 00577 // indexes between `num_lines_or_equalities' and 00578 // `lines_or_equal_bound' - 1; these rays form the set Q=. 00579 // -# all the rays that have a positive scalar product with the 00580 // constraint should have indexes between `lines_or_equal_bound' 00581 // and `sup_bound' - 1; these rays form the set Q+. 00582 // -# all the rays that have a negative scalar product with the 00583 // constraint should have indexes between `sup_bound' and 00584 // `dest_num_rows' - 1; these rays form the set Q-. 00585 dimension_type lines_or_equal_bound = num_lines_or_equalities; 00586 dimension_type inf_bound = dest_num_rows; 00587 // While we find saturating generators, we simply increment 00588 // `lines_or_equal_bound'. 00589 while (inf_bound > lines_or_equal_bound 00590 && scalar_prod[lines_or_equal_bound] == 0) 00591 ++lines_or_equal_bound; 00592 dimension_type sup_bound = lines_or_equal_bound; 00593 while (inf_bound > sup_bound) { 00594 const int sp_sign = sgn(scalar_prod[sup_bound]); 00595 if (sp_sign == 0) { 00596 // This generator has to be moved in Q=. 00597 std::swap(dest[sup_bound], dest[lines_or_equal_bound]); 00598 std::swap(scalar_prod[sup_bound], scalar_prod[lines_or_equal_bound]); 00599 std::swap(sat[sup_bound], sat[lines_or_equal_bound]); 00600 ++lines_or_equal_bound; 00601 ++sup_bound; 00602 dest.set_sorted(false); 00603 } 00604 else if (sp_sign < 0) { 00605 // This generator has to be moved in Q-. 00606 --inf_bound; 00607 std::swap(dest[sup_bound], dest[inf_bound]); 00608 std::swap(scalar_prod[sup_bound], scalar_prod[inf_bound]); 00609 std::swap(sat[sup_bound], sat[inf_bound]); 00610 dest.set_sorted(false); 00611 } 00612 else 00613 // sp_sign > 0: this generator has to be moved in Q+. 00614 ++sup_bound; 00615 } 00616 00617 if (sup_bound == dest_num_rows) { 00618 // Here the set Q- is empty. 00619 // If the constraint is an inequality, then all the generators 00620 // in Q= and Q+ satisfy the constraint. The constraint is redundant 00621 // and it can be safely removed from the constraint system. 00622 // This is why the `source' parameter is not declared `const'. 00623 if (source_k.is_ray_or_point_or_inequality()) { 00624 ++source_num_redundant; 00625 --source_num_rows; 00626 // NOTE: we continue with the next cycle of the loop 00627 // without incrementing the index `k', because: 00628 // -# either `k == source_num_rows', and we will exit the loop; 00629 // -# or, having increased `source_num_redundant', we will swap 00630 // in position `k' a constraint that still has to be examined. 00631 } 00632 else { 00633 // The constraint is an equality, so that all the generators 00634 // in Q+ violate it. Since the set Q- is empty, we can simply 00635 // remove from `dest' all the generators of Q+. 00636 dest_num_rows = lines_or_equal_bound; 00637 // We continue with the next constraint. 00638 ++k; 00639 } 00640 } 00641 else { 00642 // The set Q- is not empty, i.e., at least one generator 00643 // violates the constraint `source_k'. 00644 // We have to further distinguish two cases: 00645 if (sup_bound == num_lines_or_equalities) 00646 // The set Q+ is empty, so that all generators that satisfy 00647 // the constraint also saturate it. 00648 // We can simply remove from `dest' all the generators in Q-. 00649 dest_num_rows = sup_bound; 00650 else { 00651 // The sets Q+ and Q- are both non-empty. 00652 // The generators of the new pointed cone are all those satisfying 00653 // the constraint `source_k' plus a set of new rays enjoying 00654 // the following properties: 00655 // -# they lie on the hyper-plane represented by the constraint 00656 // -# they are obtained as a positive combination of two 00657 // adjacent rays, the first taken from Q+ and the second 00658 // taken from Q-. 00659 00660 // The adjacency property is necessary to have an irredundant 00661 // set of new rays (see proposition 2). 00662 const dimension_type bound = dest_num_rows; 00663 00664 // In the following loop, 00665 // `i' runs through the generators in the set Q+ and 00666 // `j' runs through the generators in the set Q-. 00667 for (dimension_type i = lines_or_equal_bound; i < sup_bound; ++i) { 00668 for(dimension_type j = sup_bound; j < bound; ++j) { 00669 // Checking if generators `dest[i]' and `dest[j]' are adjacent. 00670 // If there exist another generator that saturates 00671 // all the constraints saturated by both `dest[i]' and 00672 // `dest[j]', then they are NOT adjacent. 00673 Bit_Row new_satrow; 00674 assert(sat[i].last() == ULONG_MAX || sat[i].last() < k); 00675 assert(sat[j].last() == ULONG_MAX || sat[j].last() < k); 00676 // Being the union of `sat[i]' and `sat[j]', 00677 // `new_satrow' corresponds to a ray that saturates all the 00678 // constraints saturated by both `dest[i]' and `dest[j]'. 00679 set_union(sat[i], sat[j], new_satrow); 00680 00681 // Computing the number of common saturators. 00682 // NOTE: this number has to be less than `k' because 00683 // we are treating the `k'-th constraint. 00684 const dimension_type 00685 num_common_satur = k - new_satrow.count_ones(); 00686 00687 // Even before actually creating the new ray as a 00688 // positive combination of `dest[i]' and `dest[j]', 00689 // we exploit saturation information to check if 00690 // it can be an extremal ray. To this end, we refer 00691 // to the definition of a minimal proper face 00692 // (see comments in Polyhedron.defs.hh): 00693 // an extremal ray saturates at least `n' - `t' - 1 00694 // constraints, where `n' is the dimension of the space 00695 // and `t' is the dimension of the lineality space. 00696 // Since `n == source_num_columns - 1' and 00697 // `t == num_lines_or_equalities', we obtain that 00698 // an extremal ray saturates at least 00699 // `source_num_columns - num_lines_or_equalities - 2' 00700 // constraints. 00701 if (num_common_satur 00702 >= source_num_columns - num_lines_or_equalities - 2) { 00703 // The minimal proper face rule is satisfied. 00704 // Now we actually check for redundancy by computing 00705 // adjacency information. 00706 bool redundant = false; 00707 for (dimension_type 00708 l = num_lines_or_equalities; l < bound; ++l) 00709 if (l != i && l != j 00710 && subset_or_equal(sat[l], new_satrow)) { 00711 // Found another generator saturating all the 00712 // constraints saturated by both `dest[i]' and `dest[j]'. 00713 redundant = true; 00714 break; 00715 } 00716 if (!redundant) { 00717 // Adding the new ray to `dest' and the corresponding 00718 // saturation row to `sat'. 00719 if (dest_num_rows == dest.num_rows()) { 00720 // Make room for one more row. 00721 dest.add_pending_row(Linear_Row::Flags(dest.topology(), 00722 Linear_Row::RAY_OR_POINT_OR_INEQUALITY)); 00723 sat.add_row(new_satrow); 00724 } 00725 else 00726 sat[dest_num_rows] = new_satrow; 00727 Linear_Row& new_row = dest[dest_num_rows]; 00728 // The following fragment optimizes the computation of 00729 // 00730 // Coefficient scale = scalar_prod[i]; 00731 // scale.gcd_assign(scalar_prod[j]); 00732 // Coefficient normalized_sp_i = scalar_prod[i] / scale; 00733 // Coefficient normalized_sp_j = scalar_prod[j] / scale; 00734 // for (dimension_type c = dest_num_columns; c-- > 0; ) { 00735 // new_row[c] = normalized_sp_i * dest[j][c]; 00736 // new_row[c] -= normalized_sp_j * dest[i][c]; 00737 // } 00738 normalize2(scalar_prod[i], 00739 scalar_prod[j], 00740 normalized_sp_i, 00741 normalized_sp_o); 00742 for (dimension_type c = dest_num_columns; c-- > 0; ) { 00743 Coefficient& new_row_c = new_row[c]; 00744 new_row_c = normalized_sp_i * dest[j][c]; 00745 sub_mul_assign(new_row_c, normalized_sp_o, dest[i][c]); 00746 } 00747 new_row.strong_normalize(); 00748 // Since we added a new generator to `dest', 00749 // we also add a new element to `scalar_prod'; 00750 // by construction, the new ray lies on the hyper-plane 00751 // represented by the constraint `source_k'. 00752 // Thus, the added scalar product is 0. 00753 assert(scalar_prod.size() >= dest_num_rows); 00754 if (scalar_prod.size() <= dest_num_rows) 00755 scalar_prod.push_back(Coefficient_zero()); 00756 else 00757 scalar_prod[dest_num_rows] = Coefficient_zero(); 00758 // Increment the number of generators. 00759 ++dest_num_rows; 00760 } 00761 } 00762 } 00763 #if REACTIVE_ABANDONING 00764 maybe_abandon(); 00765 #endif 00766 } 00767 // Now we substitute the rays in Q- (i.e., the rays violating 00768 // the constraint) with the newly added rays. 00769 dimension_type j; 00770 if (source_k.is_ray_or_point_or_inequality()) { 00771 // The constraint is an inequality: 00772 // the violating generators are those in Q-. 00773 j = sup_bound; 00774 // For all the generators in Q+, set to 1 the corresponding 00775 // entry for the constraint `source_k' in the saturation matrix. 00776 for (dimension_type l = lines_or_equal_bound; l < sup_bound; ++l) 00777 sat[l].set(k); 00778 } 00779 else 00780 // The constraint is an equality: 00781 // the violating generators are those in the union of Q+ and Q-. 00782 j = lines_or_equal_bound; 00783 00784 // Swapping the newly added rays 00785 // (index `i' running through `dest_num_rows - 1' down-to `bound') 00786 // with the generators violating the constraint 00787 // (index `j' running through `j' up-to `bound - 1'). 00788 dimension_type i = dest_num_rows; 00789 while (j < bound && i > bound) { 00790 --i; 00791 std::swap(dest[i], dest[j]); 00792 std::swap(scalar_prod[i], scalar_prod[j]); 00793 std::swap(sat[i], sat[j]); 00794 ++j; 00795 dest.set_sorted(false); 00796 } 00797 // Setting the number of generators in `dest': 00798 // - if the number of generators violating the constraint 00799 // is less than or equal to the number of the newly added 00800 // generators, we assign `i' to `dest_num_rows' because 00801 // all generators above this index are significant; 00802 // - otherwise, we assign `j' to `dest_num_rows' because 00803 // all generators below index `j-1' violates the constraint. 00804 dest_num_rows = (j == bound) ? i : j; 00805 } 00806 // We continue with the next constraint. 00807 ++k; 00808 } 00809 } 00810 #if !REACTIVE_ABANDONING 00811 // Check if the client has requested abandoning all expensive 00812 // computations. If so, the exception specified by the client 00813 // is thrown now. 00814 maybe_abandon(); 00815 #endif 00816 } 00817 00818 // We may have identified some redundant constraints in `source', 00819 // which have been swapped at the end of the system. 00820 if (source_num_redundant > 0) { 00821 assert(source_num_redundant == source.num_rows() - source_num_rows); 00822 source.erase_to_end(source_num_rows); 00823 sat.columns_erase_to_end(source_num_rows); 00824 } 00825 // If `start == 0', then `source' was sorted and remained so. 00826 // If otherwise `start > 0', then the two sub-system made by the 00827 // non-pending rows and the pending rows, respectively, were both sorted. 00828 // Thus, the overall system is sorted if and only if either 00829 // `start == source_num_rows' (i.e., the second sub-system is empty) 00830 // or the row ordering holds for the two rows at the boundary between 00831 // the two sub-systems. 00832 if (start > 0 && start < source_num_rows) 00833 source.set_sorted(compare(source[start - 1], source[start]) <= 0); 00834 // There are no longer pending constraints in `source'. 00835 source.unset_pending_rows(); 00836 00837 // We may have identified some redundant rays in `dest', 00838 // which have been swapped at the end of the system. 00839 if (dest_num_rows < dest.num_rows()) { 00840 dest.erase_to_end(dest_num_rows); 00841 // Be careful: we might have erased some of the non-pending rows. 00842 if (dest.first_pending_row() > dest_num_rows) 00843 dest.unset_pending_rows(); 00844 sat.rows_erase_to_end(dest_num_rows); 00845 } 00846 if (dest.is_sorted()) 00847 // If the non-pending generators in `dest' are still declared to be 00848 // sorted, then we have to also check for the sortedness of the 00849 // pending generators. 00850 for (dimension_type i = dest.first_pending_row(); i < dest_num_rows; ++i) 00851 if (compare(dest[i - 1], dest[i]) > 0) { 00852 dest.set_sorted(false); 00853 break; 00854 } 00855 // There are no pending generators in `dest'. 00856 dest.unset_pending_rows(); 00857 00858 return num_lines_or_equalities; 00859 }