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

ItemGrouper.h

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

/** \file
 * Group items having the same tagset
 */

/*
 * 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/Collection.h>
#include <tagcoll/OpSet.h>

#include <map>
#include <list>

namespace Tagcoll
{

/**
 * Collection grouping items having the same tagset.
 *
 * The intended usage is mainly for compressing a stream of tags putting items
 * together, for example to have a more compact output when serialising.
 *
 * For most other collection operations, it's even more unefficient than
 * InputMerger.
 *
 * Examples:
 * \code
 * // Serialize the collection, giving the serializer a chance to group
 * // together the items with the same tags
 * void serializeCompact(const Collection<Item, Tag>& coll)
 * {
 *    ItemGrouper<Item, Tag> grouper;
 *    coll.output(grouper);
 *    grouper.output(serializer);
 * }
 *
 * // Serialize the reversed collection, associating to tags the items that
 * // have them in the input.  It also won't output the same item twice, and
 * // it gives the serializer a chance to group together the items with the
 * // same tags
 * void serializeReversed(const Collection<Item, Tag>& coll)
 * {
 *    ItemGrouper<Item, Tag> grouper;
 *    coll.output(grouper);
 *    grouper.outputReversed(serializer);
 * }
 * \endcode
 */
template<class ITEM, class TAG>
00068 class ItemGrouper : public Collection<ITEM, TAG>
{
protected:
      typedef typename std::map<OpSet<TAG>, OpSet<ITEM> > groups_t;

      // tagset -> item group
      groups_t groups;

00076       virtual void consumeItem(const ITEM& item, const OpSet<TAG>& tags)
      {
            groups[tags] += item;
      }
00080       virtual void consumeItems(const OpSet<ITEM>& items, const OpSet<TAG>& tags)
      {
            groups[tags] += items;
      }

00085       virtual OpSet<ITEM> getItemsHavingTag(const TAG& tag) const
      {
            OpSet<ITEM> res;
            for (typename groups_t::const_iterator i = groups.begin();
                        i != groups.end(); i++)
                  if (i->first.contains(tag))
                        res += i->second;
            return res;
      }
00094       virtual OpSet<ITEM> getItemsHavingTags(const OpSet<TAG>& tags) const
      {
            OpSet<ITEM> res;
            for (typename groups_t::const_iterator i = groups.begin();
                        i != groups.end(); i++)
                  if (i->first.contains(tags))
                        res += i->second;
            return res;
      }

00104     virtual OpSet<TAG> getTagsOfItem(const ITEM& item) const
      {
            for (typename groups_t::const_iterator i = groups.begin();
                        i != groups.end(); i++)
                  if (i->second.contains(item))
                        return i->first;
            return OpSet<TAG>();
      }
00112       virtual OpSet<TAG> getTagsOfItems(const OpSet<ITEM>& items) const
      {
            OpSet<TAG> res;
            for (typename groups_t::const_iterator i = groups.begin();
                        i != groups.end(); i++)
            {
                  OpSet<ITEM> found = i->second ^ items;
                  if (!found.empty())
                        res += i->first;
            }
            return res;
      }

      
public:
      virtual ~ItemGrouper() throw () {}

      virtual bool hasItem(const ITEM& item) const
      {
            for (typename groups_t::const_iterator i = groups.begin();
                        i != groups.end(); i++)
                  if (i->second.contains(item))
                        return true;
            return false;
      }
00137       virtual bool hasTag(const TAG& tag) const
      {
            for (typename groups_t::const_iterator i = groups.begin();
                        i != groups.end(); i++)
                  if (i->first.contains(tag))
                        return true;
            return false;
      }

00146       virtual void applyChange(const PatchList<ITEM, TAG>& change)
      {
            OpSet<ITEM> involvedItems;

            // Find out the items that are involved by the patch
            for (typename PatchList<ITEM, TAG>::const_iterator i = change.begin(); i != change.end(); i++)
                  involvedItems += i->first;

            // Take the involved items temporarily out of the collection, and save
            // them together with their patched tagset
            std::map< ITEM, OpSet<TAG> > involved;
            OpSet<ITEM> extraItems = involvedItems;
            std::list< typename groups_t::iterator > toremove;
            for (typename groups_t::iterator i = groups.begin();
                        i != groups.end(); i++)
            {
                  OpSet<ITEM> found = i->second ^ involvedItems;
                  extraItems -= found;
                  if (!found.empty())
                  {
                        i->second -= found;
                        for (typename OpSet<ITEM>::const_iterator j = found.begin();
                                    j != found.end(); j++)
                              involved.insert(make_pair(*j, change.patch(*j, i->first)));
                        if (i->second.empty())
                              toremove.push_back(i);
                  }
            }
            for (typename std::list< typename groups_t::iterator >::const_iterator i = toremove.begin();
                        i != toremove.end(); i++)
                  groups.erase(*i);

            // Also add those tags that have been introduced with the patch
            for (typename OpSet<ITEM>::const_iterator i = extraItems.begin();
                        i != extraItems.end(); i++)
            {
                  typename PatchList<ITEM, TAG>::const_iterator found = change.find(*i);
                  if (found != change.end())
                        involved.insert(make_pair(*i, found->second.getAdded()));
            }
            
            // Reinsert the involved items and their patched tagset
            for (typename std::map< ITEM, OpSet<TAG> >::const_iterator i = involved.begin();
                        i != involved.end(); i++)
                  groups[i->second] += i->first;
      }


00194       virtual OpSet<ITEM> getTaggedItems() const
      {
            OpSet<ITEM> res;
            for (typename groups_t::const_iterator i = groups.begin();
                        i != groups.end(); i++)
                  res += i->second;
            return res;
      }

00203       virtual OpSet<TAG> getAllTags() const
      {
            OpSet<TAG> res;
            for (typename groups_t::const_iterator i = groups.begin();
                        i != groups.end(); i++)
                  res += i->first;
            return res;
      }

00212       virtual OpSet<TAG> getCompanionTags(const OpSet<TAG>& tags) const
      {
            OpSet<TAG> res;
            for (typename groups_t::const_iterator i = groups.begin();
                        i != groups.end(); i++)
                  if (i->first.contains(tags))
                        res += i->first;
            return res - tags;
      }

00222       virtual OpSet<ITEM> getRelatedItems(const OpSet<TAG>& tags, int maxdistance = 1) const
      {
            OpSet<ITEM> packages;

            for (typename groups_t::const_iterator i = groups.begin();
                        i != groups.end(); i++)
            {
                  int dist = tags.distance(i->first);
                  if (dist >= 0 && dist <= maxdistance)
                        packages += i->second;
            }

            return packages;
      }

00237       virtual void output(Consumer<ITEM, TAG>& consumer) const
      {
            for (typename groups_t::const_iterator i = groups.begin();
                        i != groups.end(); i++)
                  if (i->first.empty())
                        consumer.consume(i->second);
                  else
                        consumer.consume(i->second, i->first);
      }

      /**
       * Send the merged data to a consumer, but reversed: the tag become items,
       * and they are tagged with the items that had them
       */
00251       void outputReversed(Consumer<TAG, ITEM>& consumer) const
      {
            for (typename groups_t::const_iterator i = groups.begin();
                        i != groups.end(); i++)
                  consumer.consume(i->first, i->second);
      }

00258       virtual void outputHavingTags(const OpSet<TAG>& tags, Consumer<ITEM, TAG>& consumer) const
      {
            for (typename groups_t::const_iterator i = groups.begin();
                        i != groups.end(); i++)
                  if (i->first.contains(tags))
                        consumer.consume(i->second, i->first);
      }

      /**
       * Remove all the items from this ItemGrouper
       */
00269       void clear() { groups.clear(); }
};

};

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

Generated by  Doxygen 1.6.0   Back to index