00001 #ifndef TAGCOLL_IMPLICATIONS_H
00002 #define TAGCOLL_IMPLICATIONS_H
00003
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
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
00081
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
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
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
00193 #endif