more/gen/po_algo.h Source File

00001 //  Copyright (C) 2001--2002  Petter Urkedal
00002 //
00003 //  This file is free software; you can redistribute it and/or modify
00004 //  it under the terms of the GNU General Public License as published by
00005 //  the Free Software Foundation; either version 2 of the License, or
00006 //  (at your option) any later version.
00007 //
00008 //  This file is distributed in the hope that it will be useful,
00009 //  but WITHOUT ANY WARRANTY; without even the implied warranty of
00010 //  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00011 //  GNU General Public License for more details.
00012 //
00013 //  You should have received a copy of the GNU General Public License
00014 //  along with this program; if not, write to the Free Software
00015 //  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00016 //
00017 //  As a special exception, you may use this file as part of a free
00018 //  software library 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
00021 //  produce an executable, this file does not by itself cause the
00022 //  resulting executable to be covered by the GNU General Public
00023 //  License.  This exception does not however invalidate any other
00024 //  reasons why the executable file might be covered by the GNU General
00025 //  Public License.
00026 //
00027 //  $Id: po_algo.h,v 1.2 2002/08/24 13:59:13 petter_urkedal Exp $
00028 
00029 
00030 #ifndef MORE_GEN_PO_ALGO_H
00031 #define MORE_GEN_PO_ALGO_H
00032 
00033 
00034 namespace more {
00035 namespace gen {
00036 
00037   /** Return true if \a e is the maximum element of its ordering. */
00038   template<typename Element>
00039     inline bool
00040     is_max_element(Element e)
00041     {
00042         return e.supremums_begin() == e.supremums_end();
00043     }
00044 
00045   /** Return true if \a e is the minimum element of its ordering. */
00046   template<typename Element>
00047     inline bool
00048     is_min_element(Element e)
00049     {
00050         return e.infimums_begin() == e.infimums_end();
00051     }
00052 
00053 
00054   //
00055   //  Copy ranges of elements
00056   //
00057   ///\if bits
00058   template<typename Element, typename OutputIterator>
00059     bool
00060     _copy_open_range(Element e_low, Element e_high, OutputIterator it_out)
00061     {
00062         if (e_low.is_cached())
00063             return e_low.cache().as_bool;
00064         e_low.set_cached();
00065         bool is_reachable = false;
00066         for (typename Element::supremum_iterator it = e_low.supremums_begin();
00067              it != e_low.supremums_end(); ++it) {
00068             if (*it == e_high)
00069                 is_reachable = true;
00070             else if (_copy_open_range((Element)*it, e_high, it_out)) {
00071                 is_reachable = true;
00072                 *it_out = *it, ++it_out;
00073             }
00074         }
00075         return e_low.cache().as_bool = is_reachable;
00076     }
00077   ///\endif
00078 
00079   /** Copy elements in (\a e_low, \a e_high) to \a it_out. */
00080   template<typename Element, typename OutputIterator>
00081     bool
00082     copy_open_range(Element e_low, Element e_high, OutputIterator it_out)
00083     {
00084         check_range(e_low, e_high);
00085         e_low.clear_cache();
00086         return e_low == e_high || _copy_open_range(e_low, e_high, it_out);
00087     }
00088 
00089   /** Copy elements in [\a e_low, \a e_high] to \a it_out. */
00090   template<typename Element, typename OutputIterator>
00091     bool
00092     copy_closed_range(Element e_low, Element e_high, OutputIterator it_out)
00093     {
00094         if (e_low == e_high) {
00095             *it_out = e_low, ++it_out;
00096             return true;
00097         }
00098         check_range(e_low, e_high);
00099         e_low.clear_cache();
00100         if (_copy_open_range(e_low, e_high, it_out)) {
00101             *it_out = e_low, ++it_out;
00102             *it_out = e_high, ++it_out;
00103             return true;
00104         }
00105         return false;
00106     }
00107 
00108   /** Copy elements if [\a e_low, \a e_high) to \a it_out. */
00109   template<typename Element, typename OutputIterator>
00110     bool
00111     copy_left_range(Element e_low, Element e_high, OutputIterator it_out)
00112     {
00113         if (e_low == e_high) return true;
00114         check_range(e_low, e_high);
00115         e_low.clear_cache();
00116         if (_copy_open_range(e_low, e_high, it_out)) {
00117             *it_out = e_low, ++it_out;
00118             return true;
00119         }
00120         return false;
00121     }
00122 
00123   /** Copy elements in (\a e_low, \a e_high] to \a it_out. */
00124   template<typename Element, typename OutputIterator>
00125     bool
00126     copy_right_range(Element e_low, Element e_high, OutputIterator it_out)
00127     {
00128         if (e_low == e_high) return true;
00129         check_range(e_low, e_high);
00130         e_low.clear_cache();
00131         if (_copy_open_range(e_low, e_high, it_out)) {
00132             *it_out = e_high, ++it_out;
00133             return true;
00134         }
00135         return false;
00136     }
00137 
00138 
00139 
00140   //
00141   // Finding supremums and infimums of values ordered by an external
00142   // predicate relative to values in the container.
00143   //
00144   ///\if bits
00145   template<typename Element, typename Predicate, typename OutputIterator>
00146     bool
00147     _find_infimums(Element e_low,
00148                    Predicate pred, OutputIterator it_out)
00149     {
00150         if (e_low.is_cached())
00151             return e_low.cache().as_bool;
00152         e_low.set_cached();
00153         if (is_max_element(e_low)
00154             || !is_min_element(e_low) && !pred(*e_low))
00155             return e_low.cache().as_bool = false;
00156         bool found = false;
00157         for (typename Element::supremum_iterator
00158                  it_sup = e_low.supremums_begin();
00159              it_sup != e_low.supremums_end(); ++it_sup) {
00160             if (_find_infimums(Element(*it_sup), pred,
00161                                it_out))
00162                 found = true;
00163         }
00164         if (!found)
00165             *it_out = e_low, ++it_out;
00166         return e_low.cache().as_bool = true;
00167     }
00168 
00169   template<typename Element, typename Predicate, typename OutputIterator>
00170     bool
00171     _find_supremums(Element e_high,
00172                     Predicate pred, OutputIterator it_out)
00173     {
00174         if (e_high.is_cached())
00175             return e_high.cache().as_bool;
00176         e_high.set_cached();
00177         if (is_min_element(e_high)
00178             || !is_max_element(e_high) && !pred(*e_high))
00179             return e_high.cache().as_bool = false;
00180         bool found = false;
00181         for (typename Element::infimum_iterator
00182                  it_inf = e_high.infimums_begin();
00183              it_inf != e_high.infimums_end(); ++it_inf) {
00184             if (_find_supremums(Element(*it_inf), pred,
00185                                 it_out))
00186                 found = true;
00187         }
00188         if (!found)
00189             *it_out = e_high, ++it_out;
00190         return e_high.cache().as_bool = true;
00191     }
00192   ///\endif
00193 
00194   /** find infimums of \a value according to \a preceq in the node
00195       set from \a e_low and upwards. */
00196   template< typename Element, typename Value, typename PrecEqPredicate,
00197             typename OutputIterator >
00198     void
00199     find_infimums(Element e_low, Value const& value,
00200                   PrecEqPredicate preceq, OutputIterator it_out)
00201     {
00202         e_low.clear_cache();
00203         _find_infimums(e_low, std::bind2nd(preceq, value), it_out);
00204     }
00205 
00206   /** Find infimums of \a value according to \a preceq in the node set
00207       above (excluding) \a e_low. */
00208   template< typename Element, typename Value, typename PrecEqPredicate,
00209             typename OutputIterator >
00210     void
00211     find_infimums_above(Element e_low, Value const& value,
00212                         PrecEqPredicate preceq, OutputIterator it_out)
00213     {
00214         e_low.clear_cache();
00215         for (typename Element::supremum_iterator it
00216                  = e_low.supremums_begin(); it != e_low.supremums_end(); ++it)
00217             _find_infimums(Element(*it), std::bind2nd(preceq, value), it_out);
00218     }
00219 
00220   /** find supremums of \a value according to \a preceq in the node
00221       set from \a e_high and downwards. */
00222   template< typename Element, typename Value, typename PrecEqPredicate,
00223             typename OutputIterator >
00224     void
00225     find_supremums(Element e_high, Value const& value,
00226                    PrecEqPredicate preceq, OutputIterator it_out)
00227     {
00228         e_high.clear_cache();
00229         _find_supremums(e_high, std::bind1st(preceq, value), it_out);
00230     }
00231 
00232   /** Find supremums of \a value according to \a preceq in the node
00233       set below (excluding) \a e_high. */
00234   template< typename Element, typename Value, typename PrecEqPredicate,
00235             typename OutputIterator >
00236     void
00237     find_supremums_below(Element e_high, Value const& value,
00238                          PrecEqPredicate preceq, OutputIterator it_out)
00239     {
00240         e_high.clear_cache();
00241         for (typename Element::infimum_iterator it
00242                  = e_high.infimums_begin(); it != e_high.infimums_end(); ++it)
00243             _find_supremums(Element(*it), std::bind1st(preceq, value), it_out);
00244     }
00245 
00246 
00247 
00248   template<typename Element, typename Predicate, typename OutputIterator>
00249     void
00250     find_infimums_if(Element e_low, Predicate const& pred,
00251                      OutputIterator it_out)
00252     {
00253         e_low.clear_cache();
00254         _find_infimums(e_low, pred, it_out);
00255     }
00256 
00257   template<typename Element, typename Predicate, typename OutputIterator>
00258     void
00259     find_supremums_if(Element e_high, Predicate const& pred,
00260                       OutputIterator it_out)
00261     {
00262         e_high.clear_cache();
00263         _find_supremums(e_high, pred, it_out);
00264     }
00265 
00266 
00267   template<typename Element, typename Predicate, typename OutputIterator>
00268     void
00269     find_infimums_above_if(Element e_low, Predicate const& pred,
00270                            OutputIterator it_out)
00271     {
00272         e_low.clear_cache();
00273         for (typename Element::supremum_iterator it
00274                  = e_low.supremums_begin(); it != e_low.supremums_end(); ++it)
00275             _find_infimums(Element(*it), pred, it_out);
00276     }
00277 
00278   template<typename Element, typename Predicate, typename OutputIterator>
00279     void
00280     find_supremums_below_if(Element e_high, Predicate const& pred,
00281                             OutputIterator it_out)
00282     {
00283         e_high.clear_cache();
00284         for (typename Element::infimum_iterator it
00285                  = e_high.infimums_begin(); it != e_high.infimums_end(); ++it)
00286             _find_supremums(Element(*it), pred, it_out);
00287     }
00288 
00289 }} // more::gen
00290 
00291 #endif