Implications.h

Go to the documentation of this file.
00001 #ifndef TAGCOLL_IMPLICATIONS_H
00002 #define TAGCOLL_IMPLICATIONS_H
00003 
00008 /*
00009  * Copyright (C) 2003,2004,2005  Enrico Zini <enrico@debian.org>
00010  *
00011  * This library is free software; you can redistribute it and/or
00012  * modify it under the terms of the GNU Lesser General Public
00013  * License as published by the Free Software Foundation; either
00014  * version 2.1 of the License, or (at your option) any later version.
00015  *
00016  * This library is distributed in the hope that it will be useful,
00017  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00018  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00019  * Lesser General Public License for more details.
00020  *
00021  * You should have received a copy of the GNU Lesser General Public
00022  * License along with this library; if not, write to the Free Software
00023  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307  USA
00024  */
00025 
00026 #include <wibble/operators.h>
00027 #include <wibble/mixin.h>
00028 #include <tagcoll/coll/simple.h>
00029 #include <map>
00030 
00031 namespace tagcoll
00032 {
00033 
00039 template <class TAG>
00040 class Implications : public coll::Simple<TAG, TAG>
00041 {
00042 protected:
00044     std::set<TAG> getDestinations(const TAG& tag, const std::set<TAG>& seen = std::set<TAG>()) const;
00045 
00047     bool reaches(const TAG& tag1, const TAG& tag2, const std::set<TAG>& seen = std::set<TAG>()) const;
00048 
00049 public:
00051     std::set<TAG> expand(const TAG& tag) const
00052     {
00053         using namespace wibble::operators;
00054         return getDestinations(tag) | tag;
00055     }
00056 
00057 
00059     template<typename IN>
00060     std::set<TAG> expand(const IN& tags) const
00061     {
00062         std::set<TAG> res;
00063 
00064         for (typename IN::const_iterator t = tags.begin();
00065                 t != tags.end(); ++t)
00066         {
00067             res |= *t;
00068             res |= expand(*t);
00069         }
00070 
00071         return res;
00072     }
00073 
00075     template<typename IN>
00076     std::set<TAG> compress(const IN& tags) const
00077     {
00078         using namespace wibble::operators;
00079 
00080         // Create the union of the expansion sets of each single tag, without the tag
00081         // tags = tags - this union
00082         std::set<TAG> initial;
00083         std::set<TAG> redundant;
00084         for (typename IN::const_iterator t = tags.begin();
00085                 t != tags.end(); ++t)
00086         {
00087             initial.insert(*t);
00088             std::set<TAG> expanded = expand(*t);
00089             for (typename std::set<TAG>::const_iterator i = expanded.begin();
00090                     i != expanded.end(); i++)
00091                 if (*i != *t)
00092                     redundant.insert(*i);
00093         }
00094         return initial - redundant;
00095     }
00096 
00097     // Remove unnecessary arcs from the dag
00098     void pack();
00099 
00100     template<typename COLL>
00101     void addFrom(const COLL& coll)
00102     {
00103         std::set<TAG> allTags = coll.getAllTags();
00104         for (typename std::set<TAG>::const_iterator t = allTags.begin();
00105                 t != allTags.end(); t++)
00106         {
00107             typename std::set<TAG> implying = coll.getTagsImplying(*t);
00108             for (typename std::set<TAG>::const_iterator i = implying.begin();
00109                     i != implying.end(); ++i)
00110                 insert(wibble::singleton(*i), wibble::singleton(*t));
00111         }
00112     }
00113 
00114     // Output the fully expanded implication dag to a TagcollConsumer
00115     template<typename OUT>
00116     void outputFull(OUT out) const
00117     {
00118         for (typename coll::Simple<TAG, TAG>::const_iterator i = this->begin();
00119                 i != this->end(); ++i)
00120         {
00121             std::set<TAG> destinations = getDestinations(i->first);
00122 
00123             if (!destinations.empty())
00124             {
00125                 *out = make_pair(wibble::singleton(i->first), destinations);
00126                 ++out;
00127             }
00128         }
00129     }
00130 };
00131 
00135 template <typename TAG, typename OUT>
00136 class AddImplied : public wibble::mixin::OutputIterator< AddImplied<TAG, OUT> >
00137 {
00138 protected:
00139     const Implications<TAG>& impls;
00140     OUT out;
00141 
00142 public:
00143     AddImplied(const Implications<TAG>& impls, const OUT& out)
00144         : impls(impls), out(out) {}
00145 
00146     template<typename ITEMS, typename TAGS>
00147     AddImplied<TAG, OUT>& operator=(const std::pair<ITEMS, TAGS>& data)
00148     {
00149         *out = make_pair(data.first, impls.expand(data.second));
00150         ++out;
00151         return *this;
00152     }
00153 };
00154 
00155 template<typename TAG, typename OUT>
00156 AddImplied<TAG, OUT> addImplied(const Implications<TAG>& impls, const OUT& out)
00157 {
00158     return AddImplied<TAG, OUT>(impls, out);
00159 }
00160 
00164 template <typename TAG, typename OUT>
00165 class RemoveImplied : public wibble::mixin::OutputIterator< RemoveImplied<TAG, OUT> >
00166 {
00167 protected:
00168     const Implications<TAG>& impls;
00169     OUT out;
00170 
00171 public:
00172     RemoveImplied(const Implications<TAG>& impls, const OUT& out) 
00173         : impls(impls), out(out) {}
00174 
00175     template<typename ITEMS, typename TAGS>
00176     RemoveImplied<TAG, OUT>& operator=(const std::pair<ITEMS, TAGS>& data)
00177     {
00178         *out = make_pair(data.first, impls.compress(data.second));
00179         ++out;
00180         return *this;
00181     }
00182 };
00183 
00184 template<typename TAG, typename OUT>
00185 RemoveImplied<TAG, OUT> removeImplied(const Implications<TAG>& impls, const OUT& out)
00186 {
00187     return RemoveImplied<TAG, OUT>(impls, out);
00188 }
00189 
00190 };
00191 
00192 // vim:set ts=4 sw=4:
00193 #endif

Generated on Fri Feb 8 10:50:41 2008 for libtagcoll by  doxygen 1.5.4