Milena (Olena): operators.hh Source File

00001 // Copyright (C) 2007, 2008, 2009 EPITA Research and Development Laboratory (LRDE)
00002 //
00003 // This file is part of Olena.
00004 //
00005 // Olena is free software: you can redistribute it and/or modify it under
00006 // the terms of the GNU General Public License as published by the Free
00007 // Software Foundation, version 2 of the License.
00008 //
00009 // Olena is distributed in the hope that it will be useful,
00010 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00011 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00012 // General Public License for more details.
00013 //
00014 // You should have received a copy of the GNU General Public License
00015 // along with Olena.  If not, see <http://www.gnu.org/licenses/>.
00016 //
00017 // As a special exception, you may use this file as part of a free
00018 // software project without restriction.  Specifically, if other files
00019 // instantiate templates or use macros or inline functions from this
00020 // file, or you compile this file and link it with other files to produce
00021 // an executable, this file does not by itself cause the resulting
00022 // executable to be covered by the GNU General Public License.  This
00023 // exception does not however invalidate any other reasons why the
00024 // executable file might be covered by the GNU General Public License.
00025 
00026 #ifndef MLN_CORE_SITE_SET_OPERATORS_HH
00027 # define MLN_CORE_SITE_SET_OPERATORS_HH
00028 
00034 
00035 
00036 # include <algorithm>
00037 # include <mln/core/concept/site_set.hh>
00038 
00039 
00040 
00041 namespace mln
00042 {
00043 
00044   // Forward declarations.
00045   template <typename E> struct Box;
00046   namespace set { template <typename S> unsigned card(const Site_Set<S>& s); }
00047 
00048 
00049   template <typename Sl, typename Sr>
00050   Sl&
00051   operator+=(Site_Set<Sl>& lhs, const Site_Set<Sr>& rhs);
00052 
00053 
00061   template <typename Sl, typename Sr>
00062   bool
00063   operator==(const Site_Set<Sl>& lhs, const Site_Set<Sr>& rhs);
00064 
00065 
00066 
00074   template <typename Sl, typename Sr>
00075   bool
00076   operator<=(const Site_Set<Sl>& lhs, const Site_Set<Sr>& rhs);
00077 
00078 
00079 
00088   template <typename Sl, typename Sr>
00089   bool
00090   operator<(const Site_Set<Sl>& lhs, const Site_Set<Sr>& rhs);
00091 
00092 
00093 
00104   template <typename S>
00105   std::ostream&
00106   operator<<(std::ostream& ostr, const Site_Set<S>& set);
00107 
00108 
00109 
00110 # ifndef MLN_INCLUDE_ONLY
00111 
00112 
00113   namespace internal
00114   {
00115 
00116     template <typename Sl, typename Sr>
00117     inline
00118     std::set< mln_site(Sl), util::ord<mln_site(Sl)> >
00119     sym_diff_std_set(const Site_Set<Sl>& lhs, const Site_Set<Sr>& rhs)
00120     {
00121       typedef mln_site(Sl) P;
00122       mlc_converts_to(mln_psite(Sr), P)::check();
00123       std::set< P, util::ord<P> > sl, sr, sd;
00124       convert::over_load::from_to_(lhs, sl);
00125       convert::over_load::from_to_(rhs, sr);
00126       std::set_symmetric_difference(sl.begin(), sl.end(),
00127                                     sr.begin(), sr.end(),
00128                                     std::inserter(sd, sd.begin()),
00129                                     util::ord<P>());
00130       return sd;
00131     }
00132 
00133     template <typename S>
00134     inline
00135     std::set< mln_site(S), util::ord<mln_site(S)> >
00136     to_std_set(const Site_Set<S>& s)
00137     {
00138       std::set< mln_site(S), util::ord<mln_site(S)> > std_s;
00139       convert::over_load::from_to_(s, std_s);
00140       return std_s;
00141     }
00142 
00143     template <typename Sl, typename Sr>
00144     inline
00145     bool
00146     leq_std_set(const Site_Set<Sl>& lhs, const Site_Set<Sr>& rhs)
00147     {
00148       typedef mln_site(Sl) P;
00149       mlc_converts_to(mln_psite(Sr), P)::check();
00150       std::set< P, util::ord<P> > sl, sr;
00151       convert::over_load::from_to_(lhs, sl);
00152       convert::over_load::from_to_(rhs, sr);
00153       return std::includes(sr.begin(), sr.end(),
00154                            sl.begin(), sl.end(),
00155                            util::ord<P>());
00156     }
00157 
00158 
00159     // card.
00160 
00161     template <typename S>
00162     inline
00163     unsigned set_card_dispatch_(mln::trait::site_set::nsites::any,
00164                                 const S& s)
00165     {
00166       unsigned n = 0;
00167       mln_piter(S) p(s);
00168       for_all(p)
00169         ++n;
00170       return n;
00171     }
00172 
00173     template <typename S>
00174     inline
00175     unsigned set_card_dispatch_(mln::trait::site_set::nsites::known,
00176                                 const S& s)
00177     {
00178       return s.nsites();
00179     }
00180 
00181     template <typename S>
00182     inline
00183     unsigned set_card(const Site_Set<S>& s)
00184     {
00185       return set_card_dispatch_(mln_trait_site_set_nsites(S)(),
00186                                 exact(s));
00187     }
00188 
00189   } // end of namespace mln::internal
00190 
00191 
00192   namespace impl
00193   {
00194 
00195     // Implementations for "operator ==" between site sets.
00196 
00197     template <typename Bl, typename Br>
00198     inline
00199     bool
00200     operator_equal_boxes(const Box<Bl>& lhs_, const Box<Br>& rhs_)
00201     {
00202       const Bl& lhs = exact(lhs_);
00203       const Br& rhs = exact(rhs_);
00204       if (lhs.is_empty() != rhs.is_empty())
00205         return false;
00206       if (lhs.is_empty() && rhs.is_empty())
00207         return true;
00208       return lhs.pmin() == rhs.pmin() && lhs.pmax() == rhs.pmax();
00209     }
00210 
00211     template <typename Sl, typename Sr>
00212     inline
00213     bool
00214     operator_equal_uniques(const Site_Set<Sl>& lhs,
00215                            const Site_Set<Sr>& rhs)
00216     {
00217       if (internal::set_card(lhs) != internal::set_card(rhs))
00218         return false;
00219       return mln::internal::sym_diff_std_set(lhs, rhs).empty();
00220     }
00221 
00222     template <typename Sl, typename Sr>
00223     inline
00224     bool
00225     operator_equal_unique_multiple(const Site_Set<Sl>& lhs,
00226                                    const Site_Set<Sr>& rhs)
00227     {
00228       if (internal::set_card(lhs) != internal::set_card(rhs))
00229         return false;
00230       return mln::internal::to_std_set(lhs) == mln::internal::to_std_set(rhs);
00231     }
00232 
00233     template <typename Sl, typename Sr>
00234     inline
00235     bool
00236     operator_equal_multiples(const Site_Set<Sl>& lhs,
00237                              const Site_Set<Sr>& rhs)
00238     {
00239       // FIXME: Approximate code...
00240       if (internal::set_card(lhs) != internal::set_card(rhs))
00241         return false;
00242       return mln::internal::to_std_set(lhs) == mln::internal::to_std_set(rhs);
00243     }
00244 
00245 
00246     // Implementations for "operator <" between site sets.
00247 
00248     template <typename Bl, typename Br>
00249     inline
00250     bool
00251     operator_less_boxes(const Box<Bl>& lhs_, const Box<Br>& rhs_)
00252     {
00253       const Bl& lhs = exact(lhs_);
00254       const Br& rhs = exact(rhs_);
00255       if (rhs.is_empty())
00256         return false;  // We cannot have "lhs < empty_set".
00257       // From this line, rhs is not empty.
00258       if (lhs.is_empty())
00259         return true;  // We have "empty set < a non empty set".
00260       // From here, both lhs and rhs are not empty.
00261       if (internal::set_card(lhs) >= internal::set_card(rhs))
00262         return false;
00263       return lhs.crop_wrt(rhs) == lhs;
00264     }
00265 
00266     template <typename Sl, typename Sr>
00267     inline
00268     bool
00269     operator_less_uniques(const Site_Set<Sl>& lhs,
00270                           const Site_Set<Sr>& rhs)
00271     {
00272       if (internal::set_card(lhs) >= internal::set_card(rhs))
00273         return false;
00274       return mln::internal::leq_std_set(lhs, rhs);
00275     }
00276 
00277     template <typename Sl, typename Sr>
00278     inline
00279     bool
00280     operator_less_unique_multiple(const Site_Set<Sl>& lhs,
00281                                   const Site_Set<Sr>& rhs)
00282     {
00283       if (internal::set_card(lhs) >= internal::set_card(rhs))
00284         return false;
00285       return mln::internal::leq_std_set(lhs, rhs);
00286     }
00287 
00288     template <typename Sl, typename Sr>
00289     inline
00290     bool
00291     operator_less_multiples(const Site_Set<Sl>& lhs,
00292                              const Site_Set<Sr>& rhs)
00293     {
00294       // FIXME: Approximate code...
00295       if (internal::set_card(lhs) >= internal::set_card(rhs))
00296         return false;
00297       return mln::internal::leq_std_set(lhs, rhs);
00298     }
00299 
00300   } // end of namespace mln::impl
00301 
00302 
00303 
00304 
00305   namespace internal
00306   {
00307 
00308     // Dispatch for "operator ==" between site sets.
00309 
00310     template <typename Sl, typename Sr>
00311     inline
00312     bool
00313     operator_equal_dispatch(trait::site_set::arity::unique,
00314                             const Box<Sl>& lhs,
00315                             trait::site_set::arity::unique,
00316                             const Box<Sr>& rhs)
00317     {
00318       return impl::operator_equal_boxes(lhs, rhs);
00319     }
00320 
00321     template <typename Sl, typename Sr>
00322     inline
00323     bool
00324     operator_equal_dispatch(trait::site_set::arity::unique,
00325                             const Site_Set<Sl>& lhs,
00326                             trait::site_set::arity::unique,
00327                             const Site_Set<Sr>& rhs)
00328     {
00329       return impl::operator_equal_uniques(lhs, rhs);
00330     }
00331 
00332     template <typename Sl, typename Sr>
00333     inline
00334     bool
00335     operator_equal_dispatch(trait::site_set::arity::unique,
00336                             const Site_Set<Sl>& lhs,
00337                             trait::site_set::arity::multiple,
00338                             const Site_Set<Sr>& rhs)
00339     {
00340       return impl::operator_equal_unique_multiple(lhs, rhs);
00341     }
00342 
00343     template <typename Sl, typename Sr>
00344     inline
00345     bool
00346     operator_equal_dispatch(trait::site_set::arity::multiple,
00347                             const Site_Set<Sl>& lhs,
00348                             trait::site_set::arity::unique,
00349                             const Site_Set<Sr>& rhs)
00350     {
00351       return impl::operator_equal_unique_multiple(rhs, lhs);
00352     }
00353 
00354     template <typename Sl, typename Sr>
00355     inline
00356     bool
00357     operator_equal_dispatch(trait::site_set::arity::multiple,
00358                             const Site_Set<Sl>& lhs,
00359                             trait::site_set::arity::multiple,
00360                             const Site_Set<Sr>& rhs)
00361     {
00362       return impl::operator_equal_multiples(lhs, rhs);
00363     }
00364 
00365     template <typename Sl, typename Sr>
00366     inline
00367     bool
00368     operator_equal_dispatch(const Site_Set<Sl>& lhs, const Site_Set<Sr>& rhs)
00369     {
00370       return operator_equal_dispatch(mln_trait_site_set_arity(Sl)(), exact(lhs),
00371                                      mln_trait_site_set_arity(Sr)(), exact(rhs));
00372     }
00373 
00374 
00375     // Dispatch for "operator <" between site sets.
00376 
00377     template <typename Sl, typename Sr>
00378     inline
00379     bool
00380     operator_less_dispatch(trait::site_set::arity::unique,
00381                            const Box<Sl>& lhs,
00382                            trait::site_set::arity::unique,
00383                            const Box<Sr>& rhs)
00384     {
00385       return impl::operator_less_boxes(lhs, rhs);
00386     }
00387 
00388     template <typename Sl, typename Sr>
00389     inline
00390     bool
00391     operator_less_dispatch(trait::site_set::arity::unique,
00392                            const Site_Set<Sl>& lhs,
00393                            trait::site_set::arity::unique,
00394                            const Site_Set<Sr>& rhs)
00395     {
00396       return impl::operator_less_uniques(lhs, rhs);
00397     }
00398 
00399     template <typename Sl, typename Sr>
00400     inline
00401     bool
00402     operator_less_dispatch(trait::site_set::arity::unique,
00403                            const Site_Set<Sl>& lhs,
00404                            trait::site_set::arity::multiple,
00405                            const Site_Set<Sr>& rhs)
00406     {
00407       return impl::operator_less_unique_multiple(lhs, rhs);
00408     }
00409 
00410     template <typename Sl, typename Sr>
00411     inline
00412     bool
00413     operator_less_dispatch(trait::site_set::arity::multiple,
00414                            const Site_Set<Sl>& lhs,
00415                            trait::site_set::arity::unique,
00416                            const Site_Set<Sr>& rhs)
00417     {
00418       return impl::operator_less_unique_multiple(rhs, lhs);
00419     }
00420 
00421     template <typename Sl, typename Sr>
00422     inline
00423     bool
00424     operator_less_dispatch(trait::site_set::arity::multiple,
00425                            const Site_Set<Sl>& lhs,
00426                            trait::site_set::arity::multiple,
00427                            const Site_Set<Sr>& rhs)
00428     {
00429       return impl::operator_less_multiples(lhs, rhs);
00430     }
00431 
00432     template <typename Sl, typename Sr>
00433     inline
00434     bool
00435     operator_less_dispatch(const Site_Set<Sl>& lhs, const Site_Set<Sr>& rhs)
00436     {
00437       return operator_less_dispatch(mln_trait_site_set_arity(Sl)(), exact(lhs),
00438                                     mln_trait_site_set_arity(Sr)(), exact(rhs));
00439     }
00440 
00441   } // end of namespace mln::internal
00442 
00443 
00444   // Operator +=.
00445 
00446   template <typename Sl, typename Sr>
00447   inline
00448   Sl&
00449   operator+=(Site_Set<Sl>& lhs_, const Site_Set<Sr>& rhs)
00450   {
00451     mlc_is( mln_trait_site_set_contents(Sl),
00452             mln::trait::site_set::contents::dynamic )::check();
00453     mlc_equal(mln_site(Sr), typename Sl::i_element)::check();
00454     Sl& lhs = exact(lhs_);
00455     mln_fwd_piter(Sr) p(exact(rhs));
00456     for_all(p)
00457       lhs.insert(p);
00458     return lhs;
00459   }
00460 
00461 
00462   // Operator ==.
00463 
00464   template <typename Sl, typename Sr>
00465   inline
00466   bool
00467   operator==(const Site_Set<Sl>& lhs, const Site_Set<Sr>& rhs)
00468   {
00469     mlc_equal(mln_site(Sl), mln_site(Sr))::check();
00470     return internal::operator_equal_dispatch(lhs, rhs);
00471   }
00472 
00473 
00474   // Operator <.
00475 
00476   template <typename Sl, typename Sr>
00477   inline
00478   bool
00479   operator<(const Site_Set<Sl>& lhs, const Site_Set<Sr>& rhs)
00480   {
00481     mlc_equal(mln_site(Sl), mln_site(Sr))::check();
00482     return internal::operator_less_dispatch(lhs, rhs);
00483   }
00484 
00485 
00486   // Operator <=.
00487 
00488   template <typename Sl, typename Sr>
00489   inline
00490   bool
00491   operator<=(const Site_Set<Sl>& lhs, const Site_Set<Sr>& rhs)
00492   {
00493     mlc_equal(mln_site(Sl), mln_site(Sr))::check();
00494     if (internal::set_card(lhs) > internal::set_card(rhs))
00495       return false;
00496     return lhs < rhs || lhs == rhs;
00497   }
00498 
00499 
00500   // Operator <<.
00501 
00502   template <typename S>
00503   inline
00504   std::ostream&
00505   operator<<(std::ostream& ostr, const Site_Set<S>& set_)
00506   {
00507     const S& set = exact(set_);
00508     ostr << '{';
00509     mln_piter(S) p(set);
00510     for_all(p)
00511       ostr << p;
00512     return ostr << '}';
00513   }
00514 
00515 # endif // ! MLN_INCLUDE_ONLY
00516 
00517 } // end of namespace mln
00518 
00519 
00520 #endif // ! MLN_CORE_SITE_SET_OPERATORS_HH