more/gen/po_map.h Source File

00001 //  Copyright (C) 2001  Petter Urkedal (petter.urkedal@matfys.lth.se)
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_map.h,v 1.1 2002/05/30 18:01:37 petter_urkedal Exp $
00028 
00029 
00030 #ifndef MORE_GEN_PO_MAP_H
00031 #define MORE_GEN_PO_MAP_H
00032 
00033 
00034 #include <more/gen/partial_ordering.h>
00035 #include <more/gen/po_algo.h>
00036 
00037 
00038 namespace more {
00039 namespace gen {
00040 
00041   ///\if bits
00042   namespace bits {
00043     template<typename Pair, typename SubCompare>
00044       struct compare_first_function
00045           : std::binary_function<Pair, Pair, bool>
00046       {
00047           compare_first_function(SubCompare const& cmp)
00048               : m_subcmp(cmp) {}
00049 
00050           bool
00051           operator()(Pair const& x, Pair const& y)
00052           {
00053               return m_subcmp(x.first, y.first);
00054           }
00055 
00056         private:
00057           SubCompare m_subcmp;
00058       };
00059 
00060     template<typename Pair, typename Function>
00061       struct apply_to_first_function
00062           : std::unary_function<Pair, typename Function::result_type>
00063       {
00064           apply_to_first_function(Function const& sub)
00065               : m_sub(sub) {}
00066 
00067           typename Function::result_type
00068           operator()(Pair const& x) { return m_sub(x.first); }
00069 
00070         private:
00071           Function m_sub;
00072       };
00073   }
00074   ///\endif
00075 
00076 
00077   /** A map with paritally ordered keys. */
00078   template<typename Key, typename Data, typename KeyCompare>
00079     struct po_map
00080     {
00081         typedef Key key_type;
00082         typedef Data data_type;
00083         typedef std::pair<key_type, data_type> value_type;
00084 
00085         typedef KeyCompare key_compare;
00086 
00087         struct value_compare
00088             : std::binary_function<value_type, value_type, bool>
00089         {
00090             bool operator()(value_type const& x, value_type const& y) const
00091             {
00092                 return m_key_preceq(x.first, y.first);
00093             }
00094           private:
00095             key_compare m_key_preceq;
00096         };
00097 
00098       private:
00099         typedef partial_ordering<value_type> container;
00100 
00101       public:
00102         typedef typename container::element iterator;
00103         typedef typename container::const_element const_iterator;
00104 
00105         std::pair<iterator, bool> insert(value_type const&);
00106         void erase(iterator it) { m_po.erase(it); }
00107 
00108         iterator min() { return m_po.min(); }
00109         iterator max() { return m_po.max(); }
00110 
00111         const_iterator min() const { return m_po.min(); }
00112         const_iterator max() const { return m_po.max(); }
00113 
00114         template<typename OutputIterator>
00115           void find_supremums(key_type const&, OutputIterator) const;
00116         template<typename OutputIterator>
00117           void find_supremums(key_type const&, OutputIterator);
00118         template<typename OutputIterator>
00119           void find_infimums(key_type const&, OutputIterator) const;
00120         template<typename OutputIterator>
00121           void find_infimums(key_type const&, OutputIterator);
00122 
00123         template<typename Predicate, typename OutputIterator>
00124           void find_supremums_if(Predicate const&, OutputIterator) const;
00125         template<typename Predicate, typename OutputIterator>
00126           void find_supremums_if(Predicate const&, OutputIterator);
00127         template<typename Predicate, typename OutputIterator>
00128           void find_infimums_if(Predicate const&, OutputIterator) const;
00129         template<typename Predicate, typename OutputIterator>
00130           void find_infimums_if(Predicate const&, OutputIterator);
00131 
00132         void debug_dump() { m_po.debug_dump(); }
00133 
00134       private:
00135         container       m_po;
00136         value_compare   m_preceq;
00137     };
00138 
00139 
00140   template<typename Key, typename Data, typename KeyCompare>
00141     std::pair<typename po_map<Key, Data, KeyCompare>::iterator, bool>
00142     po_map<Key, Data, KeyCompare>::insert(value_type const& v)
00143     {
00144         std::list<typename container::element> infs, sups;
00145         find_infimums(v.first, back_inserter(infs));
00146         if (infs.size() == 1 && m_preceq(v, *infs.front()))
00147             return std::pair<iterator, bool>(infs.front(), false);
00148         find_supremums(v.first, back_inserter(sups));
00149 
00150         typename container::element e = m_po.insert(v);
00151 
00152         for (typename std::list<typename container::element>::iterator
00153                  it = infs.begin();
00154              it != infs.end(); ++it)
00155             m_po.constrain_prec(*it, e);
00156         infs.clear();
00157 
00158         for (typename std::list<typename container::element>::iterator
00159                  it = sups.begin();
00160              it != sups.end(); ++it)
00161             m_po.constrain_prec(e, *it);
00162 
00163         return std::pair<iterator, bool>(e, true);
00164     }
00165 
00166   template<typename Key, typename Data, typename KeyCompare>
00167     template<typename OutputIterator>
00168     void
00169     po_map<Key, Data, KeyCompare>::
00170     find_supremums(key_type const& key, OutputIterator it_out) const
00171     {
00172         value_type v(key, data_type());
00173         gen::find_supremums_below(m_po.max(), v, m_preceq, it_out);
00174     }
00175 
00176   template<typename Key, typename Data, typename KeyCompare>
00177     template<typename OutputIterator>
00178     void
00179     po_map<Key, Data, KeyCompare>::
00180     find_supremums(key_type const& key, OutputIterator it_out)
00181     {
00182         value_type v(key, data_type());
00183         gen::find_supremums_below(m_po.max(), v, m_preceq, it_out);
00184     }
00185 
00186   template<typename Key, typename Data, typename KeyCompare>
00187     template<typename OutputIterator>
00188     void
00189     po_map<Key, Data, KeyCompare>::
00190     find_infimums(key_type const& key, OutputIterator it_out) const
00191     {
00192         value_type v(key, data_type());
00193         gen::find_infimums_above(m_po.min(), v, m_preceq, it_out);
00194     }
00195 
00196   template<typename Key, typename Data, typename KeyCompare>
00197     template<typename OutputIterator>
00198     void
00199     po_map<Key, Data, KeyCompare>::
00200     find_infimums(key_type const& key, OutputIterator it_out)
00201     {
00202         value_type v(key, data_type());
00203         gen::find_infimums_above(m_po.min(), v, m_preceq, it_out);
00204     }
00205 
00206 
00207   template<typename Key, typename Data, typename KeyCompare>
00208     template<typename Predicate, typename OutputIterator>
00209     void
00210     po_map<Key, Data, KeyCompare>::
00211     find_supremums_if(Predicate const& pred, OutputIterator it_out) const
00212     {
00213         bits::apply_to_first_function<value_type, Predicate> f(pred);
00214         gen::find_supremums_below_if(m_po.max(), f, it_out);
00215     }
00216 
00217   template<typename Key, typename Data, typename KeyCompare>
00218     template<typename Predicate, typename OutputIterator>
00219     void
00220     po_map<Key, Data, KeyCompare>::
00221     find_supremums_if(Predicate const& pred, OutputIterator it_out)
00222     {
00223         bits::apply_to_first_function<value_type, Predicate> f(pred);
00224         gen::find_supremums_below_if(m_po.max(), f, it_out);
00225     }
00226 
00227   template<typename Key, typename Data, typename KeyCompare>
00228     template<typename Predicate, typename OutputIterator>
00229     void
00230     po_map<Key, Data, KeyCompare>::
00231     find_infimums_if(Predicate const& pred, OutputIterator it_out) const
00232     {
00233         bits::apply_to_first_function<value_type, Predicate> f(pred);
00234         gen::find_infimums_above_if(m_po.min(), f, it_out);
00235     }
00236 
00237   template<typename Key, typename Data, typename KeyCompare>
00238     template<typename Predicate, typename OutputIterator>
00239     void
00240     po_map<Key, Data, KeyCompare>::
00241     find_infimums_if(Predicate const& pred, OutputIterator it_out)
00242     {
00243         bits::apply_to_first_function<value_type, Predicate> f(pred);
00244         gen::find_infimums_above_if(m_po.min(), f, it_out);
00245     }
00246 
00247 
00248 }} // more::gen
00249 
00250 #endif