00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023 #ifndef PPL_Partially_Reduced_Product_defs_hh
00024 #define PPL_Partially_Reduced_Product_defs_hh 1
00025
00026 #include "Partially_Reduced_Product.types.hh"
00027 #include "globals.types.hh"
00028 #include "globals.defs.hh"
00029 #include "Constraint.types.hh"
00030 #include "Generator.types.hh"
00031 #include "Congruence.types.hh"
00032 #include "Grid_Generator.types.hh"
00033 #include "Constraint_System.types.hh"
00034 #include "Generator_System.types.hh"
00035 #include "Congruence_System.types.hh"
00036 #include "Grid_Generator_System.types.hh"
00037 #include "Poly_Con_Relation.defs.hh"
00038 #include "Poly_Gen_Relation.defs.hh"
00039 #include "Variables_Set.types.hh"
00040
00041 namespace Parma_Polyhedra_Library {
00042
00043 namespace IO_Operators {
00044
00046
00050 template <typename D1, typename D2, typename R>
00051 std::ostream&
00052 operator<<(std::ostream& s, const Partially_Reduced_Product<D1, D2, R>& dp);
00053
00054 }
00055
00064 template <typename D1, typename D2, typename R>
00065 bool operator==(const Partially_Reduced_Product<D1, D2, R>& x,
00066 const Partially_Reduced_Product<D1, D2, R>& y);
00067
00076 template <typename D1, typename D2, typename R>
00077 bool operator!=(const Partially_Reduced_Product<D1, D2, R>& x,
00078 const Partially_Reduced_Product<D1, D2, R>& y);
00079
00080 }
00081
00082
00091 template <typename D1, typename D2>
00092 class Parma_Polyhedra_Library::Smash_Reduction {
00093 public:
00095 Smash_Reduction();
00096
00110 void product_reduce(D1& d1, D2& d2);
00111
00113 ~Smash_Reduction();
00114 };
00115
00125 template <typename D1, typename D2>
00126 class Parma_Polyhedra_Library::Constraints_Reduction {
00127 public:
00129 Constraints_Reduction();
00130
00153 void product_reduce(D1& d1, D2& d2);
00154
00156 ~Constraints_Reduction();
00157 };
00158
00166 template <typename D1, typename D2>
00167 class Parma_Polyhedra_Library::No_Reduction {
00168 public:
00170 No_Reduction();
00171
00177 void product_reduce(D1& d1, D2& d2);
00178
00180 ~No_Reduction();
00181 };
00182
00184
00295 template <typename D1, typename D2, typename R>
00296 class Parma_Polyhedra_Library::Partially_Reduced_Product {
00297 public:
00302 static dimension_type max_space_dimension();
00303
00305
00316 explicit Partially_Reduced_Product(dimension_type num_dimensions = 0,
00317 Degenerate_Element kind = UNIVERSE);
00318
00320
00330 explicit Partially_Reduced_Product(const Congruence_System& cgs);
00331
00333
00344 explicit Partially_Reduced_Product(Congruence_System& cgs);
00345
00347
00357 explicit Partially_Reduced_Product(const Constraint_System& cs);
00358
00360
00370 explicit Partially_Reduced_Product(Constraint_System& cs);
00371
00373
00390 explicit
00391 Partially_Reduced_Product(const C_Polyhedron& ph,
00392 Complexity_Class complexity = ANY_COMPLEXITY);
00393
00395
00412 explicit
00413 Partially_Reduced_Product(const NNC_Polyhedron& ph,
00414 Complexity_Class complexity = ANY_COMPLEXITY);
00415
00417
00431 explicit
00432 Partially_Reduced_Product(const Grid& gr,
00433 Complexity_Class complexity = ANY_COMPLEXITY);
00434
00436
00450 template <typename Interval>
00451 Partially_Reduced_Product(const Box<Interval>& box,
00452 Complexity_Class complexity = ANY_COMPLEXITY);
00453
00455
00469 template <typename U>
00470 Partially_Reduced_Product(const BD_Shape<U>& bd,
00471 Complexity_Class complexity = ANY_COMPLEXITY);
00472
00474
00488 template <typename U>
00489 Partially_Reduced_Product(const Octagonal_Shape<U>& os,
00490 Complexity_Class complexity = ANY_COMPLEXITY);
00491
00493 Partially_Reduced_Product(const Partially_Reduced_Product& y,
00494 Complexity_Class complexity = ANY_COMPLEXITY);
00495
00497
00500 template <typename E1, typename E2, typename S>
00501 explicit
00502 Partially_Reduced_Product(const Partially_Reduced_Product<E1, E2, S>& y,
00503 Complexity_Class complexity = ANY_COMPLEXITY);
00504
00509 Partially_Reduced_Product& operator=(const Partially_Reduced_Product& y);
00510
00512
00513
00515 dimension_type space_dimension() const;
00516
00523 dimension_type affine_dimension() const;
00524
00526 const D1& domain1() const;
00527
00529 const D2& domain2() const;
00530
00532 Constraint_System constraints() const;
00533
00538 Constraint_System minimized_constraints() const;
00539
00541 Congruence_System congruences() const;
00542
00547 Congruence_System minimized_congruences() const;
00548
00550
00551
00552
00553
00554
00555
00556
00557
00558
00559
00560
00561
00562
00563
00564
00565
00566
00567
00568
00569 Poly_Con_Relation relation_with(const Constraint& c) const;
00570
00572
00573
00574
00575
00576 Poly_Con_Relation relation_with(const Congruence& cg) const;
00577
00579
00580
00581
00582
00583
00584
00585
00586
00587
00588
00589
00590 Poly_Gen_Relation relation_with(const Generator& g) const;
00591
00596 bool is_empty() const;
00597
00602 bool is_universe() const;
00603
00608 bool is_topologically_closed() const;
00609
00617 bool is_disjoint_from(const Partially_Reduced_Product& y) const;
00618
00623 bool is_discrete() const;
00624
00629 bool is_bounded() const;
00630
00638 bool constrains(Variable var) const;
00639
00641
00647 bool bounds_from_above(const Linear_Expression& expr) const;
00648
00650
00656 bool bounds_from_below(const Linear_Expression& expr) const;
00657
00682 bool maximize(const Linear_Expression& expr,
00683 Coefficient& sup_n, Coefficient& sup_d, bool& maximum) const;
00684
00713 bool maximize(const Linear_Expression& expr,
00714 Coefficient& sup_n, Coefficient& sup_d, bool& maximum,
00715 Generator& point) const;
00716
00741 bool minimize(const Linear_Expression& expr,
00742 Coefficient& inf_n, Coefficient& inf_d, bool& minimum) const;
00743
00772 bool minimize(const Linear_Expression& expr,
00773 Coefficient& inf_n, Coefficient& inf_d, bool& minimum,
00774 Generator& point) const;
00775
00783 bool contains(const Partially_Reduced_Product& y) const;
00784
00792 bool strictly_contains(const Partially_Reduced_Product& y) const;
00793
00795 bool OK() const;
00796
00798
00800
00801
00803
00807 void add_constraint(const Constraint& c);
00808
00818 void refine_with_constraint(const Constraint& c);
00819
00821
00826 void add_congruence(const Congruence& cg);
00827
00837 void refine_with_congruence(const Congruence& cg);
00838
00840
00847 void add_congruences(const Congruence_System& cgs);
00848
00858 void refine_with_congruences(const Congruence_System& cgs);
00859
00861
00872 void add_recycled_congruences(Congruence_System& cgs);
00873
00875
00882 void add_constraints(const Constraint_System& cs);
00883
00893 void refine_with_constraints(const Constraint_System& cs);
00894
00896
00907 void add_recycled_constraints(Constraint_System& cs);
00908
00919 void unconstrain(Variable var);
00920
00933 void unconstrain(const Variables_Set& to_be_unconstrained);
00934
00941 void intersection_assign(const Partially_Reduced_Product& y);
00942
00950 void upper_bound_assign(const Partially_Reduced_Product& y);
00951
00961 bool upper_bound_assign_if_exact(const Partially_Reduced_Product& y);
00962
00970 void difference_assign(const Partially_Reduced_Product& y);
00971
00994 void affine_image(Variable var,
00995 const Linear_Expression& expr,
00996 Coefficient_traits::const_reference denominator
00997 = Coefficient_one());
00998
01019 void affine_preimage(Variable var,
01020 const Linear_Expression& expr,
01021 Coefficient_traits::const_reference denominator
01022 = Coefficient_one());
01023
01051 void generalized_affine_image(Variable var,
01052 Relation_Symbol relsym,
01053 const Linear_Expression& expr,
01054 Coefficient_traits::const_reference denominator
01055 = Coefficient_one());
01056
01084 void
01085 generalized_affine_preimage(Variable var,
01086 Relation_Symbol relsym,
01087 const Linear_Expression& expr,
01088 Coefficient_traits::const_reference denominator
01089 = Coefficient_one());
01090
01112 void generalized_affine_image(const Linear_Expression& lhs,
01113 Relation_Symbol relsym,
01114 const Linear_Expression& rhs);
01115
01137 void generalized_affine_preimage(const Linear_Expression& lhs,
01138 Relation_Symbol relsym,
01139 const Linear_Expression& rhs);
01140
01167 void bounded_affine_image(Variable var,
01168 const Linear_Expression& lb_expr,
01169 const Linear_Expression& ub_expr,
01170 Coefficient_traits::const_reference denominator
01171 = Coefficient_one());
01172
01199 void bounded_affine_preimage(Variable var,
01200 const Linear_Expression& lb_expr,
01201 const Linear_Expression& ub_expr,
01202 Coefficient_traits::const_reference denominator
01203 = Coefficient_one());
01204
01213 void time_elapse_assign(const Partially_Reduced_Product& y);
01214
01216 void topological_closure_assign();
01217
01218
01219
01220
01221
01222
01242 void widening_assign(const Partially_Reduced_Product& y,
01243 unsigned* tp = NULL);
01244
01246
01248
01249
01261 void add_space_dimensions_and_embed(dimension_type m);
01262
01274 void add_space_dimensions_and_project(dimension_type m);
01275
01286 void concatenate_assign(const Partially_Reduced_Product& y);
01287
01289
01298 void remove_space_dimensions(const Variables_Set& to_be_removed);
01299
01308 void remove_higher_space_dimensions(dimension_type new_dimension);
01309
01358 template <typename Partial_Function>
01359 void map_space_dimensions(const Partial_Function& pfunc);
01360
01362
01384 void expand_space_dimension(Variable var, dimension_type m);
01385
01387
01410 void fold_space_dimensions(const Variables_Set& to_be_folded, Variable var);
01411
01413
01414 friend bool operator==<>(const Partially_Reduced_Product<D1, D2, R>& x,
01415 const Partially_Reduced_Product<D1, D2, R>& y);
01416
01417 friend std::ostream&
01418 Parma_Polyhedra_Library::IO_Operators::
01419 operator<<<>(std::ostream& s, const Partially_Reduced_Product<D1, D2, R>& dp);
01420
01422
01423
01425 ~Partially_Reduced_Product();
01426
01431 void swap(Partially_Reduced_Product& y);
01432
01433 PPL_OUTPUT_DECLARATIONS
01434
01435 #ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS
01436
01441 #endif // defined(PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS)
01442 bool ascii_load(std::istream& s);
01443
01445 memory_size_type total_memory_in_bytes() const;
01446
01448 memory_size_type external_memory_in_bytes() const;
01449
01456 int32_t hash_code() const;
01457
01459
01461
01462
01463
01464
01465
01466 bool reduce() const;
01467
01468 protected:
01470 typedef D1 Domain1;
01471
01473 typedef D2 Domain2;
01474
01476 D1 d1;
01477
01479 D2 d2;
01480
01481 protected:
01483 void clear_reduced_flag() const;
01484
01486 void set_reduced_flag() const;
01487
01489 bool is_reduced() const;
01490
01495 bool reduced;
01496 };
01497
01498 namespace Parma_Polyhedra_Library {
01499
01508 template <typename D1, typename D2>
01509 class Domain_Product {
01510 public:
01511 typedef Partially_Reduced_Product<D1, D2, No_Reduction<D1, D2> >
01512 Direct_Product;
01513
01514 typedef Partially_Reduced_Product<D1, D2, Smash_Reduction<D1, D2> >
01515 Smash_Product;
01516
01517 typedef Partially_Reduced_Product<D1, D2, Constraints_Reduction<D1, D2> >
01518 Constraints_Product;
01519 };
01520
01521 }
01522
01523 namespace std {
01524
01526
01527 template <typename D1, typename D2, typename R>
01528 void swap(Parma_Polyhedra_Library::Partially_Reduced_Product<D1, D2, R>& x,
01529 Parma_Polyhedra_Library::Partially_Reduced_Product<D1, D2, R>& y);
01530
01531 }
01532
01533 #include "Partially_Reduced_Product.inlines.hh"
01534
01535 #endif // !defined(PPL_Partially_Reduced_Product_defs_hh)