Main Page | Namespace List | Class Hierarchy | Class List | Directories | File List | Namespace Members | Class Members | File Members

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 <tagcoll/Consumer.h>
00027 #include <tagcoll/Filter.h>
00028 
00029 #include <map>
00030 
00031 namespace Tagcoll
00032 {
00033 
00037 template <class TAG>
00038 class Implications : public Consumer<TAG, TAG>
00039 {
00040 protected:
00041     // DAG of arcs: child -> {parents}
00042     typedef std::map< TAG, OpSet<TAG> > impl_t;
00043     impl_t implications;
00044 
00046     OpSet<TAG> getDestinations(const TAG& tag, const OpSet<TAG>& seen = OpSet<TAG>()) const;
00047 
00049     bool reaches(const TAG& tag1, const TAG& tag2, const OpSet<TAG>& seen = OpSet<TAG>()) const;
00050 
00051     virtual void consumeItemUntagged(const TAG& item) {}
00052 
00053     virtual void consumeItem(const TAG& item, const OpSet<TAG>& tags)
00054     {
00055         implications.insert(make_pair(item, tags));
00056     }
00057 
00058 public:
00059     virtual ~Implications() {}
00060     
00062     OpSet<TAG> expand(const TAG& tag) const { return getDestinations(tag) + tag; }
00063 
00064 
00066     OpSet<TAG> expand(const OpSet<TAG>& tags) const
00067     {
00068         OpSet<TAG> res = tags;
00069 
00070         for (typename OpSet<TAG>::const_iterator t = tags.begin();
00071                 t != tags.end(); t++)
00072             res += expand(*t);
00073 
00074         return res;
00075     }
00076 
00078     OpSet<TAG> compress(const OpSet<TAG>& tags) const;
00079 
00080     // Remove unnecessary arcs from the dag
00081     void pack();
00082     
00083     // Output the fully expanded implication dag to a TagcollConsumer
00084     void outputFull(Consumer<TAG, TAG>& consumer) const
00085     {
00086         for (typename impl_t::const_iterator i = implications.begin();
00087                 i != implications.end(); i++)
00088         {
00089             OpSet<TAG> destinations = getDestinations(i->first);
00090 
00091             if (destinations.empty())
00092                 consumer.consume(i->first);
00093             else
00094                 consumer.consume(i->first, destinations);
00095         }
00096     }
00097 
00098     // Output the implication dag to a TagcollConsumer
00099     void output(Consumer<TAG, TAG>& consumer) const
00100     {
00101         for (typename impl_t::const_iterator i = implications.begin();
00102                 i != implications.end(); i++)
00103             if (i->second.empty())
00104                 consumer.consume(i->first);
00105             else
00106                 consumer.consume(i->first, i->second);
00107     }
00108 };
00109 
00113 template <class ITEM, class TAG>
00114 class AddImplied : public Filter<ITEM, TAG>
00115 {
00116 protected:
00117     Implications<TAG> impls;
00118 
00119     virtual void consumeItemUntagged(const ITEM& item) { this->consumer->consume(item); }
00120     virtual void consumeItem(const ITEM& item, const OpSet<TAG>& tags)
00121     {
00122         this->consumer->consume(item, impls.expand(tags));
00123     }
00124     virtual void consumeItemsUntagged(const OpSet<ITEM>& items) { this->consumer->consume(items); }
00125     virtual void consumeItems(const OpSet<ITEM>& items, const OpSet<TAG>& tags)
00126     {
00127         this->consumer->consume(items, impls.expand(tags));
00128     }
00129     
00130 public:
00131     AddImplied() {}
00132     AddImplied(Consumer<ITEM, TAG>& cons) : Filter<ITEM, TAG>(cons) {}
00133     AddImplied(const Implications<TAG>& impls) : impls(impls) {}
00134     AddImplied(Consumer<ITEM, TAG>& cons, const Implications<TAG>& impls) 
00135         : Filter<ITEM, TAG>(cons), impls(impls) {}
00136     virtual ~AddImplied() {}
00137 
00141     Implications<TAG>& implications() { return impls; }
00142 
00146     const Implications<TAG>& implications() const { return impls; }
00147 };
00148 
00152 template <class ITEM, class TAG>
00153 class RemoveImplied : public Filter<ITEM, TAG>
00154 {
00155 protected:
00156     Implications<TAG> impls;
00157 
00158     virtual void consumeItemUntagged(const ITEM& item) { this->consumer->consume(item); }
00159     virtual void consumeItem(const ITEM& item, const OpSet<TAG>& tags)
00160     {
00161         this->consumer->consume(item, impls.compress(tags));
00162     }
00163     virtual void consumeItemsUntagged(const OpSet<ITEM>& items) { this->consumer->consume(items); }
00164     virtual void consumeItems(const OpSet<ITEM>& items, const OpSet<TAG>& tags)
00165     {
00166         this->consumer->consume(items, impls.compress(tags));
00167     }
00168 
00169 public:
00170     RemoveImplied() {}
00171     RemoveImplied(Consumer<ITEM, TAG>& cons) : Filter<ITEM, TAG>(cons) {}
00172     RemoveImplied(const Implications<TAG>& impls) : impls(impls) {}
00173     RemoveImplied(Consumer<ITEM, TAG>& cons, const Implications<TAG>& impls) 
00174         : Filter<ITEM, TAG>(cons), impls(impls) {}
00175     virtual ~RemoveImplied() {}
00176 
00180     Implications<TAG>& implications() { return impls; }
00181 
00185     const Implications<TAG>& implications() const { return impls; }
00186 };
00187 
00188 };
00189 
00190 // vim:set ts=4 sw=4:
00191 #endif

Generated on Wed Sep 21 05:22:09 2005 for libtagcoll by  doxygen 1.4.4