Implications.h

Go to the documentation of this file.

#ifndef TAGCOLL_IMPLICATIONS_H
#define TAGCOLL_IMPLICATIONS_H

/*
 * 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 <wibble/operators.h>
#include <wibble/mixin.h>
#include <tagcoll/coll/simple.h>
#include <map>

namespace tagcoll
{

template <class TAG>
class Implications : public coll::Simple<TAG, TAG>
{
protected:
    std::set<TAG> getDestinations(const TAG& tag, const std::set<TAG>& seen = std::set<TAG>()) const;

    bool reaches(const TAG& tag1, const TAG& tag2, const std::set<TAG>& seen = std::set<TAG>()) const;

public:
    std::set<TAG> expand(const TAG& tag) const
    {
        using namespace wibble::operators;
        return getDestinations(tag) | tag;
    }


    template<typename IN>
    std::set<TAG> expand(const IN& tags) const
    {
        std::set<TAG> res;

        for (typename IN::const_iterator t = tags.begin();
                t != tags.end(); ++t)
        {
            res |= *t;
            res |= expand(*t);
        }

        return res;
    }

    template<typename IN>
    std::set<TAG> compress(const IN& tags) const
    {
        using namespace wibble::operators;

        // Create the union of the expansion sets of each single tag, without the tag
        // tags = tags - this union
        std::set<TAG> initial;
        std::set<TAG> redundant;
        for (typename IN::const_iterator t = tags.begin();
                t != tags.end(); ++t)
        {
            initial.insert(*t);
            std::set<TAG> expanded = expand(*t);
            for (typename std::set<TAG>::const_iterator i = expanded.begin();
                    i != expanded.end(); i++)
                if (*i != *t)
                    redundant.insert(*i);
        }
        return initial - redundant;
    }

    // Remove unnecessary arcs from the dag
    void pack();

    template<typename COLL>
    void addFrom(const COLL& coll)
    {
        std::set<TAG> allTags = coll.getAllTags();
        for (typename std::set<TAG>::const_iterator t = allTags.begin();
                t != allTags.end(); t++)
        {
            typename std::set<TAG> implying = coll.getTagsImplying(*t);
            for (typename std::set<TAG>::const_iterator i = implying.begin();
                    i != implying.end(); ++i)
                insert(wibble::singleton(*i), wibble::singleton(*t));
        }
    }

    // Output the fully expanded implication dag to a TagcollConsumer
    template<typename OUT>
    void outputFull(OUT out) const
    {
        for (typename coll::Simple<TAG, TAG>::const_iterator i = this->begin();
                i != this->end(); ++i)
        {
            std::set<TAG> destinations = getDestinations(i->first);

            if (!destinations.empty())
            {
                *out = make_pair(wibble::singleton(i->first), destinations);
                ++out;
            }
        }
    }
};

template <typename TAG, typename OUT>
class AddImplied : public wibble::mixin::OutputIterator< AddImplied<TAG, OUT> >
{
protected:
    const Implications<TAG>& impls;
    OUT out;

public:
    AddImplied(const Implications<TAG>& impls, const OUT& out)
        : impls(impls), out(out) {}

    template<typename ITEMS, typename TAGS>
    AddImplied<TAG, OUT>& operator=(const std::pair<ITEMS, TAGS>& data)
    {
        *out = make_pair(data.first, impls.expand(data.second));
        ++out;
        return *this;
    }
};

template<typename TAG, typename OUT>
AddImplied<TAG, OUT> addImplied(const Implications<TAG>& impls, const OUT& out)
{
    return AddImplied<TAG, OUT>(impls, out);
}

template <typename TAG, typename OUT>
class RemoveImplied : public wibble::mixin::OutputIterator< RemoveImplied<TAG, OUT> >
{
protected:
    const Implications<TAG>& impls;
    OUT out;

public:
    RemoveImplied(const Implications<TAG>& impls, const OUT& out) 
        : impls(impls), out(out) {}

    template<typename ITEMS, typename TAGS>
    RemoveImplied<TAG, OUT>& operator=(const std::pair<ITEMS, TAGS>& data)
    {
        *out = make_pair(data.first, impls.compress(data.second));
        ++out;
        return *this;
    }
};

template<typename TAG, typename OUT>
RemoveImplied<TAG, OUT> removeImplied(const Implications<TAG>& impls, const OUT& out)
{
    return RemoveImplied<TAG, OUT>(impls, out);
}

};

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

---