Logo Search packages:      
Sourcecode: tagcoll version File versions  Download package

Implications.h

Go to the documentation of this file.
#ifndef TAGCOLL_IMPLICATIONS_H
#define TAGCOLL_IMPLICATIONS_H

/** \file
 * Collection of tag implications and a Filter to apply or compress them
 */

/*
 * Copyright (C) 2003,2004,2005  Enrico Zini <enrico@debian.org>
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307  USA
 */

#include <tagcoll/Consumer.h>
#include <tagcoll/Filter.h>

#include <map>

namespace Tagcoll
{

/**
 * List of explicit implications that can be applied to a tagged collection.
 */
template <class TAG>
00038 class Implications : public Consumer<TAG, TAG>
{
protected:
      // DAG of arcs: child -> {parents}
      typedef std::map< TAG, OpSet<TAG> > impl_t;
      impl_t implications;

      /// Get the set of all tags seen when walking through all parent lists
      OpSet<TAG> getDestinations(const TAG& tag, const OpSet<TAG>& seen = OpSet<TAG>()) const;

      /// Return true if tag1 can reach tag2 walking through some path in its parent list
      bool reaches(const TAG& tag1, const TAG& tag2, const OpSet<TAG>& seen = OpSet<TAG>()) const;

00051       virtual void consumeItemUntagged(const TAG& item) {}

00053       virtual void consumeItem(const TAG& item, const OpSet<TAG>& tags)
      {
            implications.insert(make_pair(item, tags));
      }

public:
      virtual ~Implications() {}
      
      /// Expand a single tag
00062       OpSet<TAG> expand(const TAG& tag) const { return getDestinations(tag) + tag; }


      /// Expand a full tagset
00066       OpSet<TAG> expand(const OpSet<TAG>& tags) const
      {
            OpSet<TAG> res = tags;

            for (typename OpSet<TAG>::const_iterator t = tags.begin();
                        t != tags.end(); t++)
                  res += expand(*t);

            return res;
      }

      /// Compress a tagset removing implied tags
      OpSet<TAG> compress(const OpSet<TAG>& tags) const;

      // Remove unnecessary arcs from the dag
      void pack();
      
      // Output the fully expanded implication dag to a TagcollConsumer
      void outputFull(Consumer<TAG, TAG>& consumer) const
      {
            for (typename impl_t::const_iterator i = implications.begin();
                        i != implications.end(); i++)
            {
                  OpSet<TAG> destinations = getDestinations(i->first);

                  if (destinations.empty())
                        consumer.consume(i->first);
                  else
                        consumer.consume(i->first, destinations);
            }
      }

      // Output the implication dag to a TagcollConsumer
      void output(Consumer<TAG, TAG>& consumer) const
      {
            for (typename impl_t::const_iterator i = implications.begin();
                        i != implications.end(); i++)
                  if (i->second.empty())
                        consumer.consume(i->first);
                  else
                        consumer.consume(i->first, i->second);
      }
};

/**
 * Add implied tags to a stream of tagged items
 */
template <class ITEM, class TAG>
00114 class AddImplied : public Filter<ITEM, TAG>
{
protected:
      Implications<TAG> impls;

00119       virtual void consumeItemUntagged(const ITEM& item) { this->consumer->consume(item); }
00120       virtual void consumeItem(const ITEM& item, const OpSet<TAG>& tags)
      {
            this->consumer->consume(item, impls.expand(tags));
      }
00124       virtual void consumeItemsUntagged(const OpSet<ITEM>& items) { this->consumer->consume(items); }
00125       virtual void consumeItems(const OpSet<ITEM>& items, const OpSet<TAG>& tags)
      {
            this->consumer->consume(items, impls.expand(tags));
      }
      
public:
      AddImplied() {}
      AddImplied(Consumer<ITEM, TAG>& cons) : Filter<ITEM, TAG>(cons) {}
      AddImplied(const Implications<TAG>& impls) : impls(impls) {}
      AddImplied(Consumer<ITEM, TAG>& cons, const Implications<TAG>& impls) 
            : Filter<ITEM, TAG>(cons), impls(impls) {}
      virtual ~AddImplied() {}

      /**
       * Access the internal Implication list
       */
00141       Implications<TAG>& implications() { return impls; }

      /**
       * Access the internal Implication list (const version)
       */
00146       const Implications<TAG>& implications() const { return impls; }
};

/**
 * Remove redundant implied tags to a stream of tagged items
 */
template <class ITEM, class TAG>
00153 class RemoveImplied : public Filter<ITEM, TAG>
{
protected:
      Implications<TAG> impls;

00158       virtual void consumeItemUntagged(const ITEM& item) { this->consumer->consume(item); }
00159       virtual void consumeItem(const ITEM& item, const OpSet<TAG>& tags)
      {
            this->consumer->consume(item, impls.compress(tags));
      }
00163       virtual void consumeItemsUntagged(const OpSet<ITEM>& items) { this->consumer->consume(items); }
00164       virtual void consumeItems(const OpSet<ITEM>& items, const OpSet<TAG>& tags)
      {
            this->consumer->consume(items, impls.compress(tags));
      }

public:
      RemoveImplied() {}
      RemoveImplied(Consumer<ITEM, TAG>& cons) : Filter<ITEM, TAG>(cons) {}
      RemoveImplied(const Implications<TAG>& impls) : impls(impls) {}
      RemoveImplied(Consumer<ITEM, TAG>& cons, const Implications<TAG>& impls) 
            : Filter<ITEM, TAG>(cons), impls(impls) {}
      virtual ~RemoveImplied() {}

      /**
       * Access the internal Implication list
       */
00180       Implications<TAG>& implications() { return impls; }

      /**
       * Access the internal Implication list (const version)
       */
00185       const Implications<TAG>& implications() const { return impls; }
};

};

// vim:set ts=4 sw=4:
#endif

Generated by  Doxygen 1.6.0   Back to index