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

CardinalityStore.h

#ifndef TAGCOLL_CARDINALITYSTORE_H
#define TAGCOLL_CARDINALITYSTORE_H

/* \file
 * In-memory collection keeping a fast-access track of tag cardinalities.
 */

/*
 * 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 <set>
#include <map>
#include <list>


// Definition of tag implication:
//   tag1 is implied by tag2 if all items associated to tag2 are also
//   associated to tag1
// Also said:
//   tag1 implies tag2 if all items associated to tag1 are also associated
//   to tag2

namespace Tagcoll
{

/**
 * In-memory collection keeping a fast-access track of tag cardinalities.
 *
 * This in-memory collection has different computational-complexity behaviour
 * from InputMerger, TDBIndexer or TDBDiskIndex, and can be more or less suited
 * to be used as a collection than the other alternatives, depending on the
 * computational needs of the caller.
 */
template<class ITEM, class TAG>
00052 class CardinalityStore : public Collection<ITEM, TAG>
{
public:
      typedef std::map<OpSet<TAG>, OpSet<ITEM> > tagsets_t;

protected:
      class TagContainer : public std::map<TAG, int>
      {
      public:
            TagContainer() {}
            TagContainer(const TagContainer& tc) : std::map<TAG, int>(tc) {}
            ~TagContainer() {}

            void add(const TAG& tag, int card = 1) throw ();
            void del(const TAG& tag, int card = 1) throw ();
      };

      // Tags in this collection, with their cardinality
      TagContainer tags;
      
      // Tag sets in this collection, with their item set
      tagsets_t tagsets;

      /**
       * Get the list of tags that imply one of the tags in `tags'
       */
      OpSet<TAG> getImplyingOneOf(const OpSet<TAG>& tags) const;

      void consumeItem(const ITEM& item, const OpSet<TAG>& tagset);
      void consumeItems(const OpSet<ITEM>& items, const OpSet<TAG>& tagset);

      virtual OpSet<ITEM> getItemsHavingTag(const TAG& tag) const;
      virtual OpSet<ITEM> getItemsHavingTags(const OpSet<TAG>& tags) const;
      virtual OpSet<TAG> getTagsOfItem(const ITEM& item) const;
      virtual OpSet<TAG> getTagsOfItems(const OpSet<ITEM>& items) const;

      
public:
      CardinalityStore() {}
      virtual ~CardinalityStore() {}

      /** @{
       * Iterators support
       */
00096       typedef typename tagsets_t::const_iterator const_iterator;
      typedef typename tagsets_t::iterator iterator;

      iterator begin() { return tagsets.begin(); }
      iterator end() { return tagsets.end(); }
      const_iterator begin() const { return tagsets.begin(); }
      const_iterator end() const { return tagsets.end(); }
      /** @} */

      /// Get the total number of items in this collection
      int itemCount() const;

      /// Get the number of different tags in this collection
00109       int tagCount() const { return tags.size(); }

      /// Get the number of different tag sets in this collection
00112       int tagsetCount() const { return tagsets.size(); }

      /// Get the set of items with exactly the given tagset
      OpSet<ITEM> getItemsExactMatch(const OpSet<TAG>& ts) const;

      bool hasItem(const ITEM& item) const;
00118       bool hasTag(const TAG& tag) const { return getCardinality(tag) > 0; }

      OpSet<TAG> getAllTags() const;
      OpSet<ITEM> getTaggedItems() const;

      OpSet<TAG> getCompanionTags(const OpSet<TAG>& ts) const;

      /// Get the set of all items in this collection whose tagsets contain `ts'
      OpSet<ITEM> getCompanionItems(const OpSet<TAG>& ts) const;

      /// Get the set of all items in this collection whose tagsets contain `ts'
      std::map< ITEM, OpSet<TAG> > getCompanionItemsAndTagsets(const OpSet<TAG>& ts) const;

      OpSet<ITEM> getRelatedItems(const OpSet<TAG>& ts, int maxdistance = 1) const;

      /// Get the list of tagsets related to the given one, with distance > 0 and <= maxdistance
      std::list< OpSet<TAG> > getRelatedTagsets(const OpSet<TAG>& ts, int maxdistance = 1) const;

      void applyChange(const PatchList<ITEM, TAG>& change);


      /// Return a tagged collection with all tagsets of this one that contain the
      /// tag `tag', but with the tag removed
      CardinalityStore<ITEM, TAG> getChildCollection(const TAG& tag) const;

      /// Return a tagged collection with all tagsets of this one that are
      /// nonempty when stripped by the tag `tag' and all tags that imply it 
      CardinalityStore<ITEM, TAG> getCollectionWithoutTags(const OpSet<TAG>& tag) const;

      /// Return the tagged collection with all tagsets of this one that do not
      /// contain the tag `tag'
      CardinalityStore<ITEM, TAG> getCollectionWithoutTagsetsHaving(const TAG& tag) const;

      /// Return the tagged collection with all tagsets of this one that do not
      /// contain the tags in `tags'
      CardinalityStore<ITEM, TAG> getCollectionWithoutTagsetsHavingAnyOf(const OpSet<TAG>& tag) const;

      /// Return the list of tags that the given tag implies
      OpSet<TAG> getImpliedBy(const TAG& tag) const;
      
      int getCardinality(const TAG& tag) const;

      // Return the tag with maximum cardinality
      TAG findTagWithMaxCardinalityNotIn(const OpSet<TAG>& tags, int* card = 0) const;
            
      // Return a collection where equivalent tags are merged.
      // Equivalent tags are tags which are attached to the same set of items
      // Merging two equivalent tags A and B is done renaming both of them in the
      // tag "A, B"
      void mergeEquivalentTags();

      // Remove all the tags with cardinality less than `card'
      void removeTagsWithCardinalityLessThan(int card);
      
      void output(Consumer<ITEM, TAG>& cons) const;
      void outputHavingTags(const OpSet<TAG>& ts, Consumer<ITEM, TAG>& consumer) const;
};

};

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

Generated by  Doxygen 1.6.0   Back to index