summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--ept/CMakeLists.txt4
-rw-r--r--ept/debtags/coll/TextFormat.cc87
-rw-r--r--ept/debtags/coll/TextFormat.h53
-rw-r--r--ept/debtags/coll/TextFormat.tcc176
-rw-r--r--ept/debtags/coll/base.h333
-rw-r--r--ept/debtags/coll/base.tcc191
-rw-r--r--ept/debtags/coll/fast.cc254
-rw-r--r--ept/debtags/coll/fast.h101
-rw-r--r--ept/debtags/coll/fast.tcc326
-rw-r--r--ept/debtags/coll/set.h7
-rw-r--r--ept/debtags/debtags-test.cc1
-rw-r--r--ept/debtags/debtags.cc18
-rw-r--r--ept/debtags/debtags.h14
-rw-r--r--ept/debtags/vocabulary-test.cc2
14 files changed, 402 insertions, 1165 deletions
diff --git a/ept/CMakeLists.txt b/ept/CMakeLists.txt
index 3d2dadd..f5874bf 100644
--- a/ept/CMakeLists.txt
+++ b/ept/CMakeLists.txt
@@ -8,8 +8,8 @@ list(REMOVE_ITEM src ${tests})
# Find headers
file( GLOB h_top *.h )
file( GLOB h_apt apt/*.h )
-file( GLOB h_debtags debtags/*.h debtags/*.tcc )
-file( GLOB h_debtags_maint debtags/maint/*.h debtags/maint/*.tcc )
+file( GLOB h_debtags debtags/*.h )
+file( GLOB h_debtags_maint debtags/maint/*.h )
file( GLOB h_axi axi/*.h )
file( GLOB h_utils utils/*.h )
diff --git a/ept/debtags/coll/TextFormat.cc b/ept/debtags/coll/TextFormat.cc
index dac5696..98c94f8 100644
--- a/ept/debtags/coll/TextFormat.cc
+++ b/ept/debtags/coll/TextFormat.cc
@@ -19,13 +19,20 @@
*/
#include "TextFormat.h"
+#include "fast.h"
+#include <wibble/exception.h>
+#include <wibble/operators.h>
#include <stdexcept>
#include <system_error>
+#include <set>
using namespace std;
using namespace wibble;
+using namespace wibble::operators;
-namespace tagcoll {
+namespace ept {
+namespace debtags {
+namespace coll {
namespace textformat {
// Parse an element
@@ -156,7 +163,83 @@ int parseElement(FILE* in, const std::string& pathname, string& item)
return EOF;
}
+static void printTagset(const std::set<string>& ts, FILE* out)
+{
+ for (std::set<string>::const_iterator i = ts.begin();
+ i != ts.end(); i++)
+ if (i == ts.begin())
+ {
+ if (fprintf(out, "%s", i->c_str()) < 0)
+ throw wibble::exception::System("writing tagset");
+ }
+ else
+ {
+ if (fprintf(out, ", %s", i->c_str()) < 0)
+ throw wibble::exception::System("writing tagset");
+ }
+}
+
+inline static void outString(const std::string& str, FILE* out, const char* what)
+{
+ if (fwrite(str.data(), str.size(), 1, out) != 1)
+ throw wibble::exception::System(string("writing ") + what);
}
+
+
+// item1, item2, item3: tag1, tag2, tag3
+
+//#define TRACE_PARSE
+void parse(FILE* in, const std::string& pathname, Fast& out)
+{
+ string item;
+
+ std::set<string> itemset;
+ std::set<string> tagset;
+ int sep;
+ enum {ITEMS, TAGS} state = ITEMS;
+ int line = 1;
+ do
+ {
+ sep = parseElement(in, pathname, item);
+
+ if (item.size() != 0)
+ {
+ if (state == ITEMS)
+ itemset |= item;
+ else
+ tagset |= item;
+ }
+
+ switch (sep)
+ {
+ case '\n':
+ line++;
+ case EOF:
+ if (!(itemset.empty() && tagset.empty()))
+ {
+ if (itemset.empty())
+ throw std::runtime_error("no elements before ':' separator");
+ if (tagset.empty())
+ out.insert(itemset, std::set<std::string>());
+ else
+ out.insert(itemset, tagset);
+ }
+ itemset.clear();
+ tagset.clear();
+ state = ITEMS;
+ break;
+ case ':':
+ if (state == TAGS)
+ throw std::runtime_error("separator ':' appears twice");
+ state = TAGS;
+ break;
+ default:
+ break;
+ }
+ } while (sep != EOF);
}
-#include "TextFormat.tcc"
+}
+}
+}
+}
diff --git a/ept/debtags/coll/TextFormat.h b/ept/debtags/coll/TextFormat.h
index 8b4c179..a35f664 100644
--- a/ept/debtags/coll/TextFormat.h
+++ b/ept/debtags/coll/TextFormat.h
@@ -26,53 +26,16 @@
#include <wibble/mixin.h>
#include <wibble/empty.h>
#include <wibble/singleton.h>
-//#include <tagcoll/input/base.h>
#include <cstdio>
//#define TRACE_PARSE
-namespace tagcoll
-{
+namespace ept {
+namespace debtags {
+namespace coll {
+struct Fast;
-namespace textformat
-{
-
-/**
- * TagcollConsumer that serializes its input to an output stream
- *
- * The format of the output is:
- * lines of "comma+space"-separated items, followed by "colon+space",
- * followed by the corresponding "comma+space"-separated tags.
- * Examples:
- * ITEM:
- * ITEM: TAG
- * ITEM: TAG1, TAG2, TAG3
- * ITEM1, ITEM2, ITEM3:
- * ITEM1, ITEM2, ITEM3: TAG1, TAG2, TAG3
- */
-class StdioWriter : public wibble::mixin::OutputIterator<StdioWriter>
-{
-protected:
- FILE* out;
-
-public:
- StdioWriter(FILE* out) : out(out) {}
-
- template<typename Items, typename Tags>
- StdioWriter& operator=(const std::pair<Items, Tags>& data);
-};
-
-class OstreamWriter : public wibble::mixin::OutputIterator<OstreamWriter>
-{
-protected:
- std::ostream& out;
-
-public:
- OstreamWriter(std::ostream& out) : out(out) {}
-
- template<typename Items, typename Tags>
- OstreamWriter& operator=(const std::pair<Items, Tags>& data);
-};
+namespace textformat {
/**
* Parse an element from input
@@ -95,11 +58,11 @@ int parseElement(FILE* in, const std::string& pathname, std::string& item);
* @param out
* An output iterator accepting a std::pair<string, string>
*/
-template<typename OUT>
-void parse(FILE* in, const std::string& pathname, OUT out);
+void parse(FILE* in, const std::string& pathname, Fast& out);
}
}
+}
+}
-// vim:set ts=4 sw=4:
#endif
diff --git a/ept/debtags/coll/TextFormat.tcc b/ept/debtags/coll/TextFormat.tcc
deleted file mode 100644
index 2a153c9..0000000
--- a/ept/debtags/coll/TextFormat.tcc
+++ /dev/null
@@ -1,176 +0,0 @@
-/*
- * Serialize a tagged collection to a text file
- *
- * Copyright (C) 2003--2015 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
- */
-
-#ifndef TAGCOLL_TEXTFORMAT_TCC
-#define TAGCOLL_TEXTFORMAT_TCC
-
-#include <ept/debtags/coll/TextFormat.h>
-//#include <tagcoll/patch.h>
-
-#include <wibble/exception.h>
-#include <wibble/empty.h>
-#include <wibble/operators.h>
-
-#include <ostream>
-
-using namespace std;
-using namespace wibble;
-using namespace wibble::operators;
-
-static void printTagset(const std::set<string>& ts, FILE* out)
-{
- for (std::set<string>::const_iterator i = ts.begin();
- i != ts.end(); i++)
- if (i == ts.begin())
- {
- if (fprintf(out, "%s", i->c_str()) < 0)
- throw wibble::exception::System("writing tagset");
- }
- else
- {
- if (fprintf(out, ", %s", i->c_str()) < 0)
- throw wibble::exception::System("writing tagset");
- }
-}
-
-namespace tagcoll {
-namespace textformat {
-
-inline static void outString(const std::string& str, FILE* out, const char* what)
-{
- if (fwrite(str.data(), str.size(), 1, out) != 1)
- throw wibble::exception::System(string("writing ") + what);
-}
-
-template<typename Items, typename Tags>
-StdioWriter& StdioWriter::operator=(const std::pair<Items, Tags>& data)
-{
- for (typename Items::const_iterator i = data.first.begin();
- i != data.first.end(); ++i)
- {
- if (i != data.first.begin())
- if (fputs(", ", out) == EOF)
- throw wibble::exception::System("writing comma after item");
- outString(*i, out, "item");
- }
- if (data.second.begin() != data.second.end())
- {
- if (fputs(": ", out) == EOF)
- throw wibble::exception::System("writing colon after items");
- for (typename Tags::const_iterator i = data.second.begin();
- i != data.second.end(); ++i)
- {
- if (i != data.second.begin())
- if (fputs(", ", out) == EOF)
- throw wibble::exception::System("writing comma after tag");
- outString(*i, out, "tag");
- }
- }
- if (fputc('\n', out) == EOF)
- throw wibble::exception::System("writing newline after tagset");
- return *this;
-}
-
-template<typename Items, typename Tags>
-OstreamWriter& OstreamWriter::operator=(const std::pair<Items, Tags>& data)
-{
- for (typename Items::const_iterator i = data.first.begin();
- i != data.first.end(); ++i)
- {
- if (i != data.first.begin())
- out << ", ";
- out << *i;
- }
- if (data.second.begin() != data.second.end())
- {
- out << ": ";
- for (typename Tags::const_iterator i = data.second.begin();
- i != data.second.end(); ++i)
- {
- if (i != data.second.begin())
- out << ", ";
- out << *i;
- }
- }
- out << endl;
- return *this;
-}
-
-
-
-// item1, item2, item3: tag1, tag2, tag3
-
-//#define TRACE_PARSE
-template<typename OUT>
-void parse(FILE* in, const std::string& pathname, OUT out)
-{
- string item;
-
- std::set<string> itemset;
- std::set<string> tagset;
- int sep;
- enum {ITEMS, TAGS} state = ITEMS;
- int line = 1;
- do
- {
- sep = parseElement(in, pathname, item);
-
- if (item.size() != 0)
- {
- if (state == ITEMS)
- itemset |= item;
- else
- tagset |= item;
- }
-
- switch (sep)
- {
- case '\n':
- line++;
- case EOF:
- if (!(itemset.empty() && tagset.empty()))
- {
- if (itemset.empty())
- throw std::runtime_error("no elements before ':' separator");
- if (tagset.empty())
- *out = make_pair(itemset, wibble::Empty<std::string>());
- else
- *out = make_pair(itemset, tagset);
- ++out;
- }
- itemset.clear();
- tagset.clear();
- state = ITEMS;
- break;
- case ':':
- if (state == TAGS)
- throw std::runtime_error("separator ':' appears twice");
- state = TAGS;
- break;
- default:
- break;
- }
- } while (sep != EOF);
-}
-
-}
-}
-
-#endif
diff --git a/ept/debtags/coll/base.h b/ept/debtags/coll/base.h
deleted file mode 100644
index 02e59af..0000000
--- a/ept/debtags/coll/base.h
+++ /dev/null
@@ -1,333 +0,0 @@
-#ifndef TAGCOLL_COLL_BASE_H
-#define TAGCOLL_COLL_BASE_H
-
-/** \file
- * Base mixins for tagged collections
- */
-
-/*
- * Copyright (C) 2003,2004,2005,2006 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/mixin.h>
-#include <vector>
-
-namespace std {
-template<typename A, typename B> class pair;
-}
-
-namespace tagcoll {
-namespace coll {
-
-template<typename T>
-class coll_traits;
-
-/**
- * Interface for all collections of tagged items.
- *
- * \note The point of a collection is to track the tags attached to items, and
- * not to store the items themselves. This means that collections are not
- * required to keep track of items with no tags.
- */
-template<typename Self>
-class ReadonlyCollection
-{
- const Self& self() const { return *static_cast<const Self*>(this); }
-
- class CardinalityOrder
- {
- const Self& coll;
- public:
- CardinalityOrder(const Self& coll) : coll(coll) {}
- bool operator()(const typename coll_traits<Self>::tag_type& t1, const typename coll_traits<Self>::tag_type& t2)
- {
- // Returns true if t1 precedes t2, and false otherwise
- return coll.getCardinality(t1) < coll.getCardinality(t2);
- }
- };
-
- class DiscriminanceOrder
- {
- const Self& coll;
- public:
- DiscriminanceOrder(const Self& coll) : coll(coll) {}
- bool operator()(const typename coll_traits<Self>::tag_type& t1, const typename coll_traits<Self>::tag_type& t2)
- {
- // Returns true if t1 precedes t2, and false otherwise
- return coll.getDiscriminance(t1) < coll.getDiscriminance(t2);
- }
- };
-
- template<typename COLL>
- class RelevanceOrder
- {
- const COLL& first;
- const Self& second;
- public:
- RelevanceOrder(const COLL& first, const Self& second)
- : first(first), second(second) {}
- bool operator()(const typename coll_traits<Self>::tag_type& t1, const typename coll_traits<Self>::tag_type& t2);
- };
-
- /**
- * Get the items which are tagged with at least the tag `tag'
- *
- * \return
- * The items found, or an empty set if no items have that tag
- */
- //virtual std::set<ITEM> getItemsHavingTag(const TAG& tag) const = 0;
-
- /**
- * Get the tags attached to an item.
- *
- * \param item
- * The item to query
- * \return
- * The set of tags, or an empty set if the item has no tags or it does
- * not exist.
- */
- //virtual std::set<TAG> getTagsOfItem(const ITEM& item) const = 0;
-
-public:
- /**
- * Check if the collection contains a tag
- *
- * \param tag
- * The tag to look for
- * \return
- * true if the collection contains tag, false otherwise
- */
- bool hasTag(const typename coll_traits<Self>::tag_type& tag) const;
-
- /**
- * Get the tags of item `item'. Return an empty set if `item' does not exist
- */
- //std::set<Self::tag_type> getTags(const typename Self::item_type& item) const = 0;
-
- /**
- * Get all the tags attached to the items in a set.
- *
- * \param items
- * The items to query
- * \return
- * The set of tags, or an empty set if the items have no tags or do not
- * exist.
- */
- template<typename ITEMS>
- typename coll_traits<Self>::tagset_type getTagsOfItems(const ITEMS& items) const;
-
- /**
- * Get the items with tag `tag'. Return an empty set if `tag' does not exist
- */
- //std::set<typename Self::item_type> getItems(const TAG& tag) const { return getItemsHavingTag(tag); }
-
- /**
- * Get the items which are tagged with at least the tags `tags'
- *
- * \return
- * The items found, or an empty set if no items have that tag
- */
- template<typename TAGS>
- typename coll_traits<Self>::itemset_type getItemsHavingTags(const TAGS& tags) const;
-
- /**
- * Get the set of all the items that have tags according to this collection
- */
- //virtual std::set<Self::item_type> getTaggedItems() const = 0;
-
- /**
- * Get the set of all the tags in this collection
- */
- //virtual std::set<Self::tag_type> getAllTags() const = 0;
-
- /**
- * Get all the tags in the collectin, as a vector
- */
- std::vector<typename coll_traits<Self>::tag_type> getAllTagsAsVector() const;
-
- /**
- * Get the cardinality of tag `tag' (that is, the number of items who have it)
- */
- unsigned int getCardinality(const typename coll_traits<Self>::tag_type& tag) const;
-
- /**
- * Return the discriminance value for this tag, that is, the minimum number
- * of packages that would be eliminated by selecting only those tagged with
- * this tag or only those not tagged with this tag.
- */
- unsigned int getDiscriminance(const typename coll_traits<Self>::tag_type& tag) const
- {
- return self().getCardinality(tag) < self().tagCount() - self().getCardinality(tag) ?
- self().getCardinality(tag) :
- self().tagCount() - self().getCardinality(tag);
- }
-
- /**
- * Get the set of all tags in this collection that appear in tagsets
- * containing `tags'
- *
- * Example:
- * \code
- * void refineSelection(const std::set<Tag>& selection)
- * {
- * std::set<Tag> extraTags = collection.getCompanionTags(selection);
- * tagMenu.setAvailableOptions(extraTags);
- * }
- * \endcode
- */
- template<typename TAGS>
- typename coll_traits<Self>::tagset_type getCompanionTags(const TAGS& tags) const;
-
- /**
- * Get the related items at the given maximum distance
- *
- * Examples:
- * \code
- * // Get the items related to a given one, at the given distance
- * std::set<Item> getRelated(const Item& item, int distance)
- * {
- * std::set<Item> res = collection.getRelatedItems(collection.getTags(item), distance);
- * return res - item;
- * }
- *
- * // Get the items related to the given ones, at the given distance
- * std::set<Item> getRelated(const std::set<Item>& items, int distance)
- * {
- * std::set<Item> res = collection.getRelatedItems(collection.getTags(items), distance);
- * return res - items;
- * }
- *
- * // Get the related items, increasing the distance until it finds at
- * // least 'minimum' items
- * std::set<Item> getRelated(const Item& item, int minimum)
- * {
- * std::set<Tag> tags = collection.getTags(item);
- * std::set<Item> res;
- * for (int i = 0; i < tags.size() && res.size() < minimum; i++)
- * res += collection.getRelatedItems(tags, i);
- * return res - item;
- * }
- * \endcode
- */
- template<typename TAGS>
- typename coll_traits<Self>::itemset_type getRelatedItems(const TAGS& tags, int maxdistance = 1) const;
-
- /**
- * Output all the contents of the collection to an output iterator
- */
- template<typename OUT>
- void output(OUT out) const;
-
- /**
- * Send to a consumer all the items which are tagged with at least the
- * given tags
- */
- template<typename TAGS, typename OUT>
- void outputHavingTags(const TAGS& tags, OUT out) const;
-
- /**
- * Get a vector containing all tags in this collection, sorted by
- * increasing cardinality
- */
- std::vector<typename coll_traits<Self>::tag_type> tagsInCardinalityOrder() const;
-
- /**
- * Get a vector containing all tags in this collection, sorted by
- * increasing discriminance value (@see getDiscriminance)
- */
- std::vector<typename coll_traits<Self>::tag_type> tagsInDiscriminanceOrder() const;
-
- /**
- * Get a vector containing all tags in this collection, sorted by
- * increasing relevance to the filtering applied between coll and this
- * collection
- */
- template<typename COLL>
- std::vector<typename coll_traits<Self>::tag_type> tagsInRelevanceOrder(const COLL& coll) const;
-};
-
-
-/**
- * Interface for all collections of tagged items.
- *
- * \note The point of a collection is to track the tags attached to items, and
- * not to store the items themselves. This means that collections are not
- * required to keep track of items with no tags.
- */
-template<typename Self>
-class Collection : public ReadonlyCollection<Self>
-{
-//protected:
- /*
- * Implementation note: to avoid problems with classes implementing only
- * some of the virtual methods, they are given different names. The common
- * 'comsume' methods are just inlined calls to the right virtual functions,
- * and are a way of keeping the unoverridden methods from being hidden.
- */
-
- //void consumeItemUntagged(const ITEM&) {}
- //void consumeItemsUntagged(const std::set<ITEM>&) {}
-
-public:
- //virtual ~Collection() {}
-
- /**
- * Apply a patch to the collection
- *
- * Example:
- * \code
- * void perform(const PatchList<ITEM, TAG>& change)
- * {
- * collection.applyChange(change);
- * undo.push_back(change.getReverse());
- * }
- * \endcode
- */
-// void applyChange(
-// const PatchList<
-// typename coll_traits<Self>::item_type,
-// typename coll_traits<Self>::tag_type>& change);
-};
-
-
-template<typename COLL>
-class Inserter : public wibble::mixin::OutputIterator< Inserter<COLL> >
-{
- COLL& coll;
-
-public:
- Inserter(COLL& coll) : coll(coll) {}
-
- template<typename Items, typename Tags>
- Inserter<COLL>& operator=(const std::pair<Items, Tags>& data)
- {
- coll.insert(data.first, data.second);
- return *this;
- }
-};
-
-template<typename COLL>
-Inserter<COLL> inserter(COLL& target)
-{
- return Inserter<COLL>(target);
-}
-
-}
-}
-
-// vim:set ts=4 sw=4:
-#endif
diff --git a/ept/debtags/coll/base.tcc b/ept/debtags/coll/base.tcc
deleted file mode 100644
index 546a513..0000000
--- a/ept/debtags/coll/base.tcc
+++ /dev/null
@@ -1,191 +0,0 @@
-#ifndef TAGCOLL_COLL_BASE_TCC
-#define TAGCOLL_COLL_BASE_TCC
-
-/** \file
- * Base mixins for tagged collections
- */
-
-/*
- * Copyright (C) 2003,2004,2005,2006 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 <ept/debtags/coll/base.h>
-#include <ept/debtags/coll/set.h>
-#include <algorithm>
-
-namespace tagcoll {
-namespace coll {
-
-template<typename T>
-class coll_traits;
-
-template<typename Self> template<typename COLL>
-bool ReadonlyCollection<Self>::RelevanceOrder<COLL>::operator()(
- const typename coll_traits<Self>::tag_type& t1,
- const typename coll_traits<Self>::tag_type& t2)
-{
- // New cardinality divided by the square root of the old cardinality.
- // The square root is used to downplay the very common tags a bit
- int csub1 = second.getCardinality(t1);
- float cfull1 = first.getCardinality(t1);
- int csub2 = second.getCardinality(t2);
- float cfull2 = first.getCardinality(t2);
- float rel1 = (float)(csub1 * csub1) / cfull1;
- float rel2 = (float)(csub2 * csub2) / cfull2;
-
- return rel1 < rel2;
-// return 10000 * second.getCardinality(t1) / first.getCardinality(t1)
-// < 10000 * second.getCardinality(t2) / first.getCardinality(t2);
-}
-
-
-template<typename Self>
-bool ReadonlyCollection<Self>::hasTag(const typename coll_traits<Self>::tag_type& tag) const
-{
- return !self().getItemsHavingTag(tag).empty();
-}
-
-template<typename Self> template<typename ITEMS>
-typename coll_traits<Self>::tagset_type ReadonlyCollection<Self>::getTagsOfItems(const ITEMS& items) const
-{
- using namespace wibble::operators;
- typename coll_traits<Self>::tagset_type res;
- for (typename ITEMS::const_iterator i = items.begin();
- i != items.end(); i++)
- res |= self().getTagsOfItem(*i);
- return res;
-}
-
-template<typename Self> template<typename TAGS>
-typename coll_traits<Self>::itemset_type ReadonlyCollection<Self>::getItemsHavingTags(const TAGS& tags) const
-{
- using namespace wibble::operators;
- if (tags.empty())
- return typename coll_traits<Self>::itemset_type();
-
- typename TAGS::const_iterator i = tags.begin();
- typename coll_traits<Self>::itemset_type res = self().getItemsHavingTag(*i);
-
- for (++i ; i != tags.end(); ++i)
- res &= self().getItemsHavingTag(*i);
-
- return res;
-}
-
-template<typename Self>
-std::vector<typename coll_traits<Self>::tag_type> ReadonlyCollection<Self>::getAllTagsAsVector() const
-{
- std::set<typename coll_traits<Self>::tag_type> asSet = self().getAllTags();
- std::vector<typename coll_traits<Self>::tag_type> res;
- res.reserve(asSet.size());
- std::copy(asSet.begin(), asSet.end(), back_inserter(res));
- return res;
-}
-
-template<typename Self>
-unsigned int ReadonlyCollection<Self>::getCardinality(const typename coll_traits<Self>::tag_type& tag) const
-{
- return self().getItemsHavingTag(tag).size();
-}
-
-template<typename Self> template<typename TAGS>
-typename coll_traits<Self>::tagset_type ReadonlyCollection<Self>::getCompanionTags(const TAGS& tags) const
-{
- using namespace wibble::operators;
- return self().getTagsOfItems(self().getItemsHavingTags(tags)) - tags;
-}
-
-template<typename Self> template<typename TAGS>
-typename coll_traits<Self>::itemset_type ReadonlyCollection<Self>::getRelatedItems(const TAGS& tags, int maxdistance) const
-{
- using namespace wibble::operators;
-
- typename coll_traits<Self>::itemset_type packages;
- typename coll_traits<Self>::itemset_type res;
-
- // First get a list of packages that have a non-empty intersection with `tags'
- for (typename TAGS::const_iterator i = tags.begin(); i != tags.end(); i++)
- packages |= self().getItemsHavingTag(*i);
-
- // Then keep only those within the given distance
- for (typename coll_traits<Self>::itemset_type::const_iterator i = packages.begin(); i != packages.end(); i++)
- {
- int dist = utils::set_distance(tags, self().getTagsOfItem(*i));
- if (dist >= 0 && dist <= maxdistance)
- res |= *i;
- }
-
- return res;
-}
-
-template<typename Self> template<typename OUT>
-void ReadonlyCollection<Self>::output(OUT out) const
-{
- for (typename Self::const_iterator i = self().begin();
- i != self().end(); ++i)
- {
- *out = make_pair(wibble::singleton(i->first), i->second);
- ++out;
- }
-}
-
-template<typename Self> template<typename TAGS, typename OUT>
-void ReadonlyCollection<Self>::outputHavingTags(const TAGS& tags, OUT out) const
-{
- typename coll_traits<Self>::itemset_type items = self().getItemsHavingTags(tags);
- for (typename coll_traits<Self>::itemset_type::const_iterator i = items.begin();
- i != items.end(); ++i)
- {
- *out = std::make_pair(wibble::singleton(*i), self().getTagsOfItem(*i));
- ++out;
- }
-}
-
-template<typename Self>
-std::vector<typename coll_traits<Self>::tag_type> ReadonlyCollection<Self>::tagsInCardinalityOrder() const
-{
- std::vector<typename coll_traits<Self>::tag_type> res = self().getAllTagsAsVector();
- std::sort(res.begin(), res.end(), CardinalityOrder(self()));
- return res;
-}
-
-template<typename Self>
-std::vector<typename coll_traits<Self>::tag_type> ReadonlyCollection<Self>::tagsInDiscriminanceOrder() const
-{
- std::vector<typename coll_traits<Self>::tag_type> res = self().getAllTagsAsVector();
- std::sort(res.begin(), res.end(), DiscriminanceOrder(self()));
- return res;
-}
-
-/**
- * Get a vector containing all tags in this collection, sorted by
- * increasing relevance to the filtering applied between coll and this
- * collection
- */
-template<typename Self> template<typename COLL>
-std::vector<typename coll_traits<Self>::tag_type> ReadonlyCollection<Self>::tagsInRelevanceOrder(const COLL& coll) const
-{
- std::vector<typename coll_traits<Self>::tag_type> res = self().getAllTagsAsVector();
- std::sort(res.begin(), res.end(), RelevanceOrder<COLL>(coll, self()));
- return res;
-}
-
-}
-}
-
-// vim:set ts=4 sw=4:
-#endif
diff --git a/ept/debtags/coll/fast.cc b/ept/debtags/coll/fast.cc
new file mode 100644
index 0000000..9032bf6
--- /dev/null
+++ b/ept/debtags/coll/fast.cc
@@ -0,0 +1,254 @@
+/*
+ * Fast index for tag data
+ *
+ * Copyright (C) 2005,2006 Enrico Zini <enrico@debian.org>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program 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 General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+
+#include <ept/debtags/coll/fast.h>
+#include <ept/debtags/coll/set.h>
+#include <wibble/operators.h>
+
+using namespace std;
+using namespace wibble::operators;
+
+namespace ept {
+namespace debtags {
+namespace coll {
+
+void Fast::insert(const std::set<std::string>& items, const std::set<std::string>& tags)
+{
+ using namespace wibble::operators;
+
+ if (tags.empty())
+ return;
+
+ for (const auto& i: items)
+ insert(i, tags);
+}
+
+void Fast::insert(const std::string& item, const std::set<std::string>& tags)
+{
+ using namespace wibble::operators;
+
+ if (tags.empty())
+ return;
+
+ auto iter = this->items.find(item);
+ if (iter == this->items.end())
+ this->items.insert(std::make_pair(item, tags));
+ else
+ iter->second |= tags;
+
+ for (typename std::set<std::string>::const_iterator i = tags.begin();
+ i != tags.end(); ++i)
+ {
+ typename std::map< std::string, std::set<std::string> >::iterator iter = this->tags.find(*i);
+ if (iter == this->tags.end())
+ this->tags.insert(std::make_pair(*i, std::set<std::string>() | item));
+ else
+ iter->second |= item;
+ }
+}
+
+void Fast::insert(const std::set<std::string>& items, const std::string& tag)
+{
+ using namespace wibble::operators;
+
+ for (typename std::set<std::string>::const_iterator i = items.begin();
+ i != items.end(); ++i)
+ {
+ typename std::map< std::string, std::set<std::string> >::iterator iter = this->items.find(*i);
+ if (iter == this->items.end())
+ this->items.insert(std::make_pair(*i, std::set<std::string>() | tag));
+ else
+ iter->second |= tag;
+ }
+
+ typename std::map< std::string, std::set<std::string> >::iterator iter = this->tags.find(tag);
+ if (iter == this->tags.end())
+ this->tags.insert(std::make_pair(tag, items));
+ else
+ iter->second |= items;
+}
+
+std::set<std::string> Fast::getItemsHavingTag(const std::string& tag) const
+{
+ typename map<std::string, std::set<std::string> >::const_iterator i = tags.find(tag);
+ if (i != tags.end())
+ return i->second;
+ else
+ return std::set<std::string>();
+}
+
+std::set<std::string> Fast::getItemsHavingTags(const std::set<std::string>& tags) const
+{
+ using namespace wibble::operators;
+ if (tags.empty())
+ return std::set<std::string>();
+
+ auto i = tags.begin();
+ auto res = getItemsHavingTag(*i);
+
+ for (++i ; i != tags.end(); ++i)
+ res &= getItemsHavingTag(*i);
+
+ return res;
+}
+
+
+std::set<std::string> Fast::getTagsOfItem(const std::string& item) const
+{
+ typename map<std::string, std::set<std::string> >::const_iterator i = items.find(item);
+ if (i != items.end())
+ return i->second;
+ else
+ return std::set<std::string>();
+}
+
+std::set<std::string> Fast::getTaggedItems() const
+{
+ std::set<std::string> res;
+ for (typename map<std::string, std::set<std::string> >::const_iterator i = items.begin();
+ i != items.end(); i++)
+ res |= i->first;
+ return res;
+}
+
+std::set<std::string> Fast::getAllTags() const
+{
+ std::set<std::string> res;
+ for (typename map<std::string, std::set<std::string> >::const_iterator i = tags.begin();
+ i != tags.end(); i++)
+ res |= i->first;
+ return res;
+}
+
+std::vector<std::string> Fast::getAllTagsAsVector() const
+{
+ std::vector<std::string> res;
+ for (typename map<std::string, std::set<std::string> >::const_iterator i = tags.begin();
+ i != tags.end(); i++)
+ res.push_back(i->first);
+ return res;
+}
+
+std::set<std::string> Fast::getTagsImplying(const std::string& tag) const
+{
+ // tag1 implies tag2 if the itemset of tag1 is a subset of the itemset of tag2
+ std::set<std::string> res;
+ std::set<std::string> itemsToCheck = getItemsHavingTag(tag);
+ // TODO: choose which one is the most efficient implementation
+#if 0
+ // Roughly:
+ // O(n[pkgs per tag] * log(nitems) * log(n[items per pkg]) + n[tags per item] * n[items per tag])
+ std::set<std::string> tagsToCheck;
+ for (std::set<std::string>::const_iterator i = itemsToCheck.begin();
+ i != itemsToCheck.end(); ++i)
+ tagsToCheck |= getTags(*i);
+ for (std::set<std::string>::const_iterator i = tagsToCheck.begin();
+ i != tagsToCheck.end(); ++i)
+ if (utils::set_contains(itemsToCheck, getItems(*i)))
+ res |= *i;
+#else
+ // O(ntags * n[items per tag])
+ for (typename std::map<std::string, std::set<std::string> >::const_iterator i = tags.begin();
+ i != tags.end(); ++i)
+ if (utils::set_contains(itemsToCheck, getItemsHavingTag(i->first)))
+ res |= i->first;
+#endif
+ return res - tag;
+}
+
+std::set<std::string> Fast::getItemsExactMatch(const std::set<std::string>& tags) const
+{
+ std::set<std::string> res = this->getItemsHavingTags(tags);
+ typename std::set<std::string>::iterator i = res.begin();
+ while (i != res.end())
+ {
+ typename std::map<std::string, std::set<std::string> >::const_iterator t = items.find(*i);
+ if (t != items.end() && t->second != tags)
+ {
+ typename std::set<std::string>::iterator j = i;
+ ++i;
+ res.erase(j);
+ } else
+ ++i;
+ }
+ return res;
+}
+
+std::string Fast::findTagWithMaxCardinality(size_t& card) const
+{
+ card = 0;
+ std::string res = std::string();
+ for (typename std::map<std::string, std::set<std::string> >::const_iterator i = tags.begin();
+ i != tags.end(); ++i)
+ if (i->second.size() > card)
+ {
+ card = i->second.size();
+ res = i->first;
+ }
+ return res;
+}
+
+void Fast::removeTag(const std::string& tag)
+{
+ typename std::map<std::string, std::set<std::string> >::iterator itag = tags.find(tag);
+ for (typename std::set<std::string>::const_iterator iitemset = itag->second.begin();
+ iitemset != itag->second.end(); ++iitemset)
+ {
+ typename std::map<std::string, std::set<std::string> >::iterator iitem = items.find(*iitemset);
+ iitem->second -= tag;
+ if (iitem->second.empty())
+ items.erase(iitem);
+ }
+ tags.erase(itag);
+}
+
+Fast Fast::getChildCollection(const std::string& tag) const
+{
+ Fast res;
+
+ auto itag = tags.find(tag);
+ for (const auto& i: itag->second)
+ {
+ auto iitem = items.find(i);
+ res.insert(i, iitem->second);
+ }
+
+ res.removeTag(tag);
+ return res;
+}
+
+void Fast::removeTagsWithCardinalityLessThan(size_t card)
+{
+ typename std::map<std::string, std::set<std::string> >::const_iterator i = tags.begin();
+ while (i != tags.end())
+ {
+ if (i->second.size() < card)
+ {
+ typename std::map<std::string, std::set<std::string> >::const_iterator j = i;
+ ++i;
+ removeTag(j->first);
+ } else
+ ++i;
+ }
+}
+
+}
+}
+}
diff --git a/ept/debtags/coll/fast.h b/ept/debtags/coll/fast.h
index 7a4c2b8..747cefc 100644
--- a/ept/debtags/coll/fast.h
+++ b/ept/debtags/coll/fast.h
@@ -1,5 +1,5 @@
-#ifndef TAGCOLL_COLL_FAST_H
-#define TAGCOLL_COLL_FAST_H
+#ifndef EPT_DEBTAGS_COLL_FAST_H
+#define EPT_DEBTAGS_COLL_FAST_H
/** \file
* Fast index for tag data
@@ -23,51 +23,38 @@
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*/
-#include <wibble/singleton.h>
-#include <ept/debtags/coll/base.h>
#include <set>
#include <map>
+#include <string>
+#include <vector>
-namespace tagcoll {
-
+namespace ept {
+namespace debtags {
namespace coll {
-template<typename ITEM, typename TAG>
-class Fast;
-
-template<typename ITEM, typename TAG>
-struct coll_traits< Fast<ITEM, TAG> >
-{
- typedef ITEM item_type;
- typedef TAG tag_type;
- typedef std::set<ITEM> itemset_type;
- typedef std::set<TAG> tagset_type;
-};
/**
* In-memory collection with both item->tags and tag->items mappings.
*/
-template<class ITEM, class TAG>
-class Fast : public coll::Collection< Fast<ITEM, TAG> >
+class Fast
{
protected:
- std::map<ITEM, std::set<TAG> > items;
- std::map<TAG, std::set<ITEM> > tags;
+ std::map<std::string, std::set<std::string>> items;
+ std::map<std::string, std::set<std::string>> tags;
#if 0
- virtual void consumeItem(const ITEM& item, const std::set<TAG>& tags);
- virtual void consumeItems(const std::set<ITEM>& items, const std::set<TAG>& tags);
+ virtual void consumeItem(const std::string& item, const std::set<std::string>& tags);
+ virtual void consumeItems(const std::set<std::string>& items, const std::set<std::string>& tags);
- virtual std::set<ITEM> getItemsHavingTag(const TAG& tag) const;
- virtual std::set<TAG> getTagsOfItem(const ITEM& item) const;
+ virtual std::set<std::string> getItemsHavingTag(const std::string& tag) const;
+ virtual std::set<std::string> getTagsOfItem(const std::string& item) const;
#endif
public:
- typedef typename std::map< ITEM, std::set<TAG> >::const_iterator const_iterator;
- typedef typename std::map< ITEM, std::set<TAG> >::iterator iterator;
- typedef typename std::map< ITEM, std::set<TAG> >::value_type value_type;
-
- typedef typename std::map< TAG, std::set<ITEM> >::const_iterator const_tag_iterator;
- typedef typename std::map< TAG, std::set<ITEM> >::iterator tag_iterator;
+ typedef std::map<std::string, std::set<std::string>>::const_iterator const_iterator;
+ typedef std::map<std::string, std::set<std::string>>::iterator iterator;
+ typedef std::map<std::string, std::set<std::string>>::value_type value_type;
+ typedef std::map<std::string, std::set<std::string>>::const_iterator const_tag_iterator;
+ typedef std::map<std::string, std::set<std::string>>::iterator tag_iterator;
const_iterator begin() const { return items.begin(); }
const_iterator end() const { return items.end(); }
@@ -79,60 +66,58 @@ public:
tag_iterator tagBegin() { return tags.begin(); }
tag_iterator tagEnd() { return tags.end(); }
- template<typename ITEMS, typename TAGS>
- void insert(const ITEMS& items, const TAGS& tags);
-
- void insert(const wibble::Singleton<ITEM>& item, const std::set<TAG>& tags);
-
- void insert(const std::set<ITEM>& items, const wibble::Singleton<TAG>& tag);
+ void insert(const std::string& item, const std::set<std::string>& tags);
+ void insert(const std::set<std::string>& items, const std::string& tag);
+ void insert(const std::set<std::string>& items, const std::set<std::string>& tags);
void clear() { items.clear(); tags.clear(); }
- std::set<TAG> getTagsOfItem(const ITEM& item) const;
- std::set<ITEM> getItemsHavingTag(const TAG& tag) const;
+ std::set<std::string> getTagsOfItem(const std::string& item) const;
+ std::set<std::string> getItemsHavingTag(const std::string& tag) const;
+
+ /**
+ * Get the items which are tagged with at least the tags `tags'
+ *
+ * \return
+ * The items found, or an empty set if no items have that tag
+ */
+ std::set<std::string> getItemsHavingTags(const std::set<std::string>& tags) const;
bool empty() const { return items.empty(); }
- bool hasItem(const ITEM& item) const { return items.find(item) != items.end(); }
- bool hasTag(const TAG& tag) const { return tags.find(tag) != tags.end(); }
- std::set<ITEM> getTaggedItems() const;
- std::set<TAG> getAllTags() const;
- std::vector<TAG> getAllTagsAsVector() const;
+ bool hasItem(const std::string& item) const { return items.find(item) != items.end(); }
+ bool hasTag(const std::string& tag) const { return tags.find(tag) != tags.end(); }
+ std::set<std::string> getTaggedItems() const;
+ std::set<std::string> getAllTags() const;
+ std::vector<std::string> getAllTagsAsVector() const;
unsigned int itemCount() const { return items.size(); }
unsigned int tagCount() const { return tags.size(); }
- /**
- * Output all the contents of the reversed collection to an output iterator
- */
- template<typename OUT>
- void outputReversed(OUT out) const;
-
#if 0
- void output(Consumer<ITEM, TAG>& consumer) const;
+ void output(Consumer<std::string, std::string>& consumer) const;
#endif
// tag1 implies tag2 if the itemset of tag1 is a subset of the itemset of
// tag2
- std::set<TAG> getTagsImplying(const TAG& tag) const;
+ std::set<std::string> getTagsImplying(const std::string& tag) const;
// Return the items which have the exact tagset 'tags'
- std::set<ITEM> getItemsExactMatch(const std::set<TAG>& tags) const;
+ std::set<std::string> getItemsExactMatch(const std::set<std::string>& tags) const;
- TAG findTagWithMaxCardinality(size_t& card) const;
+ std::string findTagWithMaxCardinality(size_t& card) const;
/**
* Return the collection with only those items that have this tag, but with
* the given tag removed
*/
- Fast<ITEM, TAG> getChildCollection(const TAG& tag) const;
+ Fast getChildCollection(const std::string& tag) const;
- void removeTag(const TAG& tag);
+ void removeTag(const std::string& tag);
void removeTagsWithCardinalityLessThan(size_t card);
};
}
}
-
-// vim:set ts=4 sw=4:
+}
#endif
diff --git a/ept/debtags/coll/fast.tcc b/ept/debtags/coll/fast.tcc
deleted file mode 100644
index c8731c0..0000000
--- a/ept/debtags/coll/fast.tcc
+++ /dev/null
@@ -1,326 +0,0 @@
-/*
- * Fast index for tag data
- *
- * Copyright (C) 2005,2006 Enrico Zini <enrico@debian.org>
- *
- * This program is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License as published by
- * the Free Software Foundation; either version 2 of the License, or
- * (at your option) any later version.
- *
- * This program 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 General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software
- * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
- */
-
-#ifndef TAGCOLL_COLL_FAST_TCC
-#define TAGCOLL_COLL_FAST_TCC
-
-#include <ept/debtags/coll/fast.h>
-#include <ept/debtags/coll/set.h>
-
-#include <wibble/operators.h>
-
-using namespace std;
-using namespace wibble::operators;
-
-namespace tagcoll {
-namespace coll {
-
-template<class ITEM, class TAG> template<typename ITEMS, typename TAGS>
-void Fast<ITEM, TAG>::insert(const ITEMS& items, const TAGS& tags)
-{
- using namespace wibble::operators;
-
- if (tags.empty())
- return;
-
- for (typename ITEMS::const_iterator i = items.begin();
- i != items.end(); ++i)
- {
- typename std::map< ITEM, std::set<TAG> >::iterator iter = this->items.find(*i);
- if (iter == this->items.end())
- this->items.insert(std::make_pair(*i, std::set<TAG>() | tags));
- else
- iter->second |= tags;
- }
-
- for (typename TAGS::const_iterator i = tags.begin();
- i != tags.end(); ++i)
- {
- typename std::map< TAG, std::set<ITEM> >::iterator iter = this->tags.find(*i);
- if (iter == this->tags.end())
- this->tags.insert(std::make_pair(*i, std::set<ITEM>() | items));
- else
- iter->second |= items;
- }
-}
-
-template<class ITEM, class TAG>
-void Fast<ITEM, TAG>::insert(const wibble::Singleton<ITEM>& item, const std::set<TAG>& tags)
-{
- using namespace wibble::operators;
-
- if (tags.empty())
- return;
-
- typename std::map< ITEM, std::set<TAG> >::iterator iter = this->items.find(*item.begin());
- if (iter == this->items.end())
- this->items.insert(std::make_pair(*item.begin(), tags));
- else
- iter->second |= tags;
-
- for (typename std::set<TAG>::const_iterator i = tags.begin();
- i != tags.end(); ++i)
- {
- typename std::map< TAG, std::set<ITEM> >::iterator iter = this->tags.find(*i);
- if (iter == this->tags.end())
- this->tags.insert(std::make_pair(*i, std::set<ITEM>() | *item.begin()));
- else
- iter->second |= *item.begin();
- }
-}
-
-template<class ITEM, class TAG>
-void Fast<ITEM, TAG>::insert(const std::set<ITEM>& items, const wibble::Singleton<TAG>& tag)
-{
- using namespace wibble::operators;
-
- for (typename std::set<ITEM>::const_iterator i = items.begin();
- i != items.end(); ++i)
- {
- typename std::map< ITEM, std::set<TAG> >::iterator iter = this->items.find(*i);
- if (iter == this->items.end())
- this->items.insert(std::make_pair(*i, std::set<TAG>() | *tag.begin()));
- else
- iter->second |= *tag.begin();
- }
-
- typename std::map< TAG, std::set<ITEM> >::iterator iter = this->tags.find(*tag.begin());
- if (iter == this->tags.end())
- this->tags.insert(std::make_pair(*tag.begin(), items));
- else
- iter->second |= items;
-}
-
-template<class ITEM, class TAG>
-std::set<ITEM> Fast<ITEM, TAG>::getItemsHavingTag(const TAG& tag) const
-{
- typename map<TAG, std::set<ITEM> >::const_iterator i = tags.find(tag);
- if (i != tags.end())
- return i->second;
- else
- return std::set<ITEM>();
-}
-
-template<class ITEM, class TAG>
-std::set<TAG> Fast<ITEM, TAG>::getTagsOfItem(const ITEM& item) const
-{
- typename map<ITEM, std::set<TAG> >::const_iterator i = items.find(item);
- if (i != items.end())
- return i->second;
- else
- return std::set<TAG>();
-}
-
-template<class ITEM, class TAG>
-std::set<ITEM> Fast<ITEM, TAG>::getTaggedItems() const
-{
- std::set<ITEM> res;
- for (typename map<ITEM, std::set<TAG> >::const_iterator i = items.begin();
- i != items.end(); i++)
- res |= i->first;
- return res;
-}
-
-template<class ITEM, class TAG>
-std::set<TAG> Fast<ITEM, TAG>::getAllTags() const
-{
- std::set<TAG> res;
- for (typename map<TAG, std::set<ITEM> >::const_iterator i = tags.begin();
- i != tags.end(); i++)
- res |= i->first;
- return res;
-}
-
-template<class ITEM, class TAG>
-std::vector<TAG> Fast<ITEM, TAG>::getAllTagsAsVector() const
-{
- std::vector<TAG> res;
- for (typename map<TAG, std::set<ITEM> >::const_iterator i = tags.begin();
- i != tags.end(); i++)
- res.push_back(i->first);
- return res;
-}
-
-#if 0
-template<class ITEM, class TAG>
-void Fast<ITEM, TAG>::output(Consumer<ITEM, TAG>& consumer) const
-{
- for (typename map<ITEM, std::set<TAG> >::const_iterator i = items.begin();
- i != items.end(); i++)
- consumer.consume(i->first, i->second);
-}
-#endif
-
-template<class ITEM, class TAG> template<typename OUT>
-void Fast<ITEM, TAG>::outputReversed(OUT out) const
-{
- for (typename std::map<TAG, std::set<ITEM> >::const_iterator i = tags.begin();
- i != tags.end(); ++i)
- {
- *out = make_pair(wibble::singleton(i->first), i->second);
- ++out;
- }
-}
-
-
-template<class ITEM, class TAG>
-std::set<TAG> Fast<ITEM, TAG>::getTagsImplying(const TAG& tag) const
-{
- // tag1 implies tag2 if the itemset of tag1 is a subset of the itemset of tag2
- std::set<TAG> res;
- std::set<ITEM> itemsToCheck = getItemsHavingTag(tag);
- // TODO: choose which one is the most efficient implementation
-#if 0
- // Roughly:
- // O(n[pkgs per tag] * log(nitems) * log(n[items per pkg]) + n[tags per item] * n[items per tag])
- std::set<TAG> tagsToCheck;
- for (std::set<ITEM>::const_iterator i = itemsToCheck.begin();
- i != itemsToCheck.end(); ++i)
- tagsToCheck |= getTags(*i);
- for (std::set<TAG>::const_iterator i = tagsToCheck.begin();
- i != tagsToCheck.end(); ++i)
- if (utils::set_contains(itemsToCheck, getItems(*i)))
- res |= *i;
-#else
- // O(ntags * n[items per tag])
- for (typename std::map<TAG, std::set<ITEM> >::const_iterator i = tags.begin();
- i != tags.end(); ++i)
- if (utils::set_contains(itemsToCheck, getItemsHavingTag(i->first)))
- res |= i->first;
-#endif
- return res - tag;
-}
-
-template<class ITEM, class TAG>
-std::set<ITEM> Fast<ITEM, TAG>::getItemsExactMatch(const std::set<TAG>& tags) const
-{
- std::set<ITEM> res = this->getItemsHavingTags(tags);
- typename std::set<ITEM>::iterator i = res.begin();
- while (i != res.end())
- {
- typename std::map<ITEM, std::set<TAG> >::const_iterator t = items.find(*i);
- if (t != items.end() && t->second != tags)
- {
- typename std::set<ITEM>::iterator j = i;
- ++i;
- res.erase(j);
- } else
- ++i;
- }
- return res;
-}
-
-template<class ITEM, class TAG>
-TAG Fast<ITEM, TAG>::findTagWithMaxCardinality(size_t& card) const
-{
- card = 0;
- TAG res = TAG();
- for (typename std::map<TAG, std::set<ITEM> >::const_iterator i = tags.begin();
- i != tags.end(); ++i)
- if (i->second.size() > card)
- {
- card = i->second.size();
- res = i->first;
- }
- return res;
-}
-
-template<class ITEM, class TAG>
-void Fast<ITEM, TAG>::removeTag(const TAG& tag)
-{
- typename std::map<TAG, std::set<ITEM> >::iterator itag = tags.find(tag);
- for (typename std::set<ITEM>::const_iterator iitemset = itag->second.begin();
- iitemset != itag->second.end(); ++iitemset)
- {
- typename std::map<ITEM, std::set<TAG> >::iterator iitem = items.find(*iitemset);
- iitem->second -= tag;
- if (iitem->second.empty())
- items.erase(iitem);
- }
- tags.erase(itag);
-}
-
-template<class ITEM, class TAG>
-Fast<ITEM, TAG> Fast<ITEM, TAG>::getChildCollection(const TAG& tag) const
-{
- Fast<ITEM, TAG> res;
-
- typename std::map<TAG, std::set<ITEM> >::const_iterator itag = tags.find(tag);
- for (typename std::set<ITEM>::const_iterator i = itag->second.begin();
- i != itag->second.end(); ++i)
- {
- typename std::map<ITEM, std::set<TAG> >::const_iterator iitem = items.find(*i);
- res.insert(wibble::singleton(*i), iitem->second);
- }
-
- res.removeTag(tag);
- return res;
-}
-
-template<class ITEM, class TAG>
-void Fast<ITEM, TAG>::removeTagsWithCardinalityLessThan(size_t card)
-{
- typename std::map<TAG, std::set<ITEM> >::const_iterator i = tags.begin();
- while (i != tags.end())
- {
- if (i->second.size() < card)
- {
- typename std::map<TAG, std::set<ITEM> >::const_iterator j = i;
- ++i;
- removeTag(j->first);
- } else
- ++i;
- }
-}
-
-
-#if 0
-template<class ITEM, class TAG>
-void Fast<ITEM, TAG>::consumeItem(const ITEM& item, const std::set<TAG>& tags)
-{
- // Add the tags to the item
- items[item] |= tags;
-
- // Add the item to the tags
- for (typename std::set<TAG>::const_iterator i = tags.begin(); i != tags.end(); i++)
- this->tags[*i] |= item;
-}
-
-template<class ITEM, class TAG>
-void Fast<ITEM, TAG>::consumeItems(const std::set<ITEM>& items, const std::set<TAG>& tags)
-{
- for (typename std::set<ITEM>::const_iterator i = items.begin(); i != items.end(); i++)
- // Add the tags to the item
- this->items[*i] |= tags;
-
- for (typename std::set<TAG>::const_iterator i = tags.begin(); i != tags.end(); i++)
- // Add the items to the tag
- this->tags[*i] |= items;
-}
-#endif
-
-}
-}
-
-#include <ept/debtags/coll/base.tcc>
-
-#endif
-
-// vim:set ts=4 sw=4:
diff --git a/ept/debtags/coll/set.h b/ept/debtags/coll/set.h
index f78116f..cabd939 100644
--- a/ept/debtags/coll/set.h
+++ b/ept/debtags/coll/set.h
@@ -26,7 +26,9 @@
#include <wibble/operators.h>
#include <set>
-namespace tagcoll {
+namespace ept {
+namespace debtags {
+namespace coll {
namespace utils {
template<typename T>
@@ -83,6 +85,7 @@ bool set_contains(const std::set<T>& set1, const T& item)
}
}
+}
+}
-// vim:set ts=4 sw=4:
#endif
diff --git a/ept/debtags/debtags-test.cc b/ept/debtags/debtags-test.cc
index 3a8fca5..c03d3a2 100644
--- a/ept/debtags/debtags-test.cc
+++ b/ept/debtags/debtags-test.cc
@@ -3,7 +3,6 @@
#include <wibble/operators.h>
#include <cstdio>
-using namespace tagcoll;
using namespace std;
using namespace ept;
using namespace ept::debtags;
diff --git a/ept/debtags/debtags.cc b/ept/debtags/debtags.cc
index b800c77..2fde09b 100644
--- a/ept/debtags/debtags.cc
+++ b/ept/debtags/debtags.cc
@@ -24,26 +24,18 @@
*/
#include <ept/debtags/debtags.h>
-
-//#include <tagcoll/coll/simple.h>
-//#include <tagcoll/input/stdio.h>
#include "coll/TextFormat.h"
-
#include <wibble/sys/fs.h>
#include <wibble/string.h>
-
#include <system_error>
#include <iostream>
#include <sstream>
-
#include <sys/wait.h> // WIFEXITED WEXITSTATUS
#include <sys/types.h> // getpwuid, getuid
#include <pwd.h> // getpwuid
#include <unistd.h> // getuid
-
using namespace std;
-using namespace tagcoll;
using namespace wibble;
namespace ept {
@@ -73,7 +65,7 @@ void Debtags::load(const std::string& pathname)
// Read the collection
try {
- tagcoll::textformat::parse(in, pathname, inserter(*this));
+ coll::textformat::parse(in, pathname, *this);
} catch (...) {
fclose(in);
throw;
@@ -93,11 +85,3 @@ string Debtags::pathname()
}
}
-
-#include "coll/fast.tcc"
-#include "coll/TextFormat.tcc"
-
-// Explicit template instantiations for our stuff
-template class tagcoll::coll::Fast<std::string, std::string>;
-
-// vim:set ts=4 sw=4:
diff --git a/ept/debtags/debtags.h b/ept/debtags/debtags.h
index a23b209..52d9347 100644
--- a/ept/debtags/debtags.h
+++ b/ept/debtags/debtags.h
@@ -26,18 +26,11 @@
#ifndef EPT_DEBTAGS_DEBTAGS_H
#define EPT_DEBTAGS_DEBTAGS_H
-#include <ept/debtags/coll/base.h>
#include <ept/debtags/coll/fast.h>
#include <string>
namespace ept {
namespace debtags {
-class Debtags;
-}
-}
-
-namespace ept {
-namespace debtags {
/**
* Access the on-disk Debtags tag database.
@@ -51,7 +44,7 @@ namespace debtags {
* It is possible to get a reference to the Vocabulary object using the
* vocabulary() method.
*/
-class Debtags : public tagcoll::coll::Fast<std::string, std::string>
+class Debtags : public coll::Fast
{
protected:
// User rc directory to store patches
@@ -63,8 +56,8 @@ protected:
void load(const std::string& pathname);
public:
- typedef tagcoll::coll::Fast<std::string, std::string> coll_type;
- typedef std::pair< std::string, std::set<std::string> > value_type;
+ typedef ept::debtags::coll::Fast coll_type;
+ typedef std::pair< std::string, std::set<std::string> > value_type;
/// Create a Debtags object, reading the system database
Debtags();
@@ -90,7 +83,6 @@ public:
static std::string pathname();
};
-
}
}
diff --git a/ept/debtags/vocabulary-test.cc b/ept/debtags/vocabulary-test.cc
index 51f46f9..682e521 100644
--- a/ept/debtags/vocabulary-test.cc
+++ b/ept/debtags/vocabulary-test.cc
@@ -4,7 +4,7 @@
#include "ept/test.h"
using namespace std;
-using namespace tagcoll::utils;
+using namespace ept::debtags::coll::utils;
using namespace ept::debtags;
using namespace ept::tests;
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-03 17:00:04 +0000