The GroupIndex Template Library

---

GroupIndex.h

#ifndef DEF_GROUPINDEX
#define DEF_GROUPINDEX
#pragma warning( disable : 4786 )        
#pragma message("Compiling the GroupIndex template library...")
#include "util.h"
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <map>
#include <set>
#include <string>
#ifdef VISUALC_INCLUDES
#include <direct.h>
#else
#include <unistd.h>
#include <mingw/stdlib.h>
#endif
//#include "DefaultGListCompression.h"


namespace groupindex
{

// Wie schön, dass es Präprozessor gibt:
// Damit können wir nämlich unter VisualC UND gcc (->ANSI) kompilieren!
#ifdef VISUALC_INCLUDES
 #ifndef ANSI_BRACES
  #define ANSI_BRACES
 #endif
 #ifndef ANSI_TYPENAME
  #define ANSI_TYPENAME
 #endif
#else
 #ifndef ANSI_BRACES
  #define ANSI_BRACES <>
 #endif
 #ifndef ANSI_TYPENAME
  #define ANSI_TYPENAME typename
 #endif
#endif

#include <iostream>
#include <fstream>
#include "DefaultRepresentation.h"


#ifndef TIME
#include <time.h>
#define TIME
#endif

#ifdef set
#undef set
#endif
#include <set>

//--------------------------------
#ifndef MISMATCHLIST
#include "MismatchList.h"
#endif
//--------------------------------


typedef std::map<std::string, int> NameToIndexMap;
typedef NameToIndexMap::value_type NameToIndexEntry;

typedef std::map<int, std::string> IndexToNameMap;
typedef IndexToNameMap::value_type IndexToNameEntry;

//**********************************************************************************
//  Igitt - Makros!
//**********************************************************************************

#define min(a, b)  (((a) < (b)) ? (a) : (b))

//**********************************************************************************

// Zunächst einige Worte zum Geleit für die doxygen-Doku:
/*
\mainpageOUT Die GroupIndex - Template-Library

\section introduction I. Einführung

Das Indexierungssystem \c GroupIndex ist eine generische Programmierbibliothek zum
Erstellen von inhaltsbasierten Indexierungssystemen.
\c GroupIndex nutzt an vielen Stellen das Konzept der Templates der Programmierprache C++.
Um mit Hilfe von \c GroupIndex Indexierungsysteme zu
erstellen, ist es unumgänglich, gewisse zugrundeliegende Ideen zu kennen, 
die in den folgenden Abschnitten erläutert werden.

\section group_and_set_classes II. Gruppen- und Mengenklassen

Eine zentrale Rolle im \c GroupIndex - System spielen die sogenannten
\em Gruppenklassen und \em Mengenklassen. Wie die Benennungen dieser Klassen nahelegen,
übernehmen die Instanzen dieser Klassen die Rolle von Elementen einer \em Gruppe resp. einer
\em Menge - und zwar im mathematischen Sinne. Für jeden Index, der die \c GroupIndex - Template-Library
verwendet, muss jeweils eine Gruppen- und eine Mengenklasse
implementiert werden. Worin Rolle dieser Klassen genau besteht und wie sich dies
in den jeweiligen Klassendeklarationen wiederspiegelt, soll im folgenden Abschnitt erläutert werden.

\subsection from_structures_to_classes II.1 Von mathematischen Strukturen zu C++-Klassen

Die Grundidee des \c GroupIndex - Systems besteht darin, dass mathematische Strukturen 
in Form von Klassen der Programmiersprache C++ implementiert werden. Die Implementierung
einer mathematischen Struktur soll nun anhand einer relativ simplen Struktur, nämlich
einer \em Gruppe demonstriert werden. Eine Gruppe ist eine Menge \em G mit einer Verknüpfung * 
: \em G x G -> G, wobei \em G und * gewisse \em Axiome erfüllen; so gilt für alle 
Elemente \em a, \em b und \em c aus \em G
\li * ist assoziativ, d.h. (\em a * \em b) * \em c = \em a * (\em b * \em c)
\li Es existiert ein neutrales Element 1, d.h. 1 * \em a = \em a
\li Zu jedem \em a existiert ein Inverses \em d mit \em a * \em d = 1.

Diese Axiome lassen sich nun übertragen auf C++-Klassen. An die Stelle der Gruppe \em G
rückt nun eine \em Gruppenklasse \c Group. Eine \em Instanz von \c Group entspricht
dann einem \em Element von \em G . An Stelle der aus der Mathematik gewohnten
Sprechweise "g sei Element von \em G " kann also in C++ geschreiben werden als

\code 
 Group g;
\endcode

An die Stelle der Verknüpfung * der Gruppe \em G rückt ein C++-Operator:

\code 
 Group operator*(const Group& a, const Group& b);
\endcode

Das geforderte inverse Element zu einem Gruppenelement \em g - das üblicherweise als
\c g^(-1) geschrieben wird - lässt sich ebenfalls in einen Operator übertragen. So erhält
man das Inverse zu einer Instanz der Gruppenklasse \c Group durch den unären Operator

\code 
 Group& operator!(Group& g);
\endcode

Das neutrale Element lässt sich implementieren durch einen Zuweisungsoperator der Gestalt 
 \code 
 Group& Group::operator=(int i)
 {
   if (i==1)
       ...;
 }
\endcode
Damit erhält man das neutrale Element der Gruppe (bzw. "die neutrale Instanz" der Gruppenklasse) durch
die Zuweisung
\code 
 Group g;
 g = 1;
\endcode


Die übrigen Gruppenaxiome werden implizit erfüllt - durch eine korrekte Implementierung 
der Operatoren.

\subsection groupindex_group_class II.2 Gruppenklassen

Eine Gruppenklasse für die \c GroupIndex - Klassen wird in Anlehnung an das im vorigen Abschnitt
beschriebene Konzept implementiert; in einigen Details weicht das Konzept der Gruppenklasse
von der zuvor beschriebenen Idee ab:
\li An Stelle des \c operator*() wird der Operator \c Group::operator*=(const \c Group& \c g) verwendet.
\li Der Invertierungsoperator \c Group::operator!() invertiert das \c this - Objekt und liefert
    das \c this - Objekt als Ergebnis zurück. Es wird also \em kein neues Objekt erzeugt,
    welches das Inverse enthält. Beispielsweise haben die folgenden Codezeilen zur Folge,
    dass \c g und \c h dasselbe Gruppenelement beinhalten:
    \code 
 Group g,h;
 ...
 h = !g;
    \endcode
    Um die Wirkung zu erzielen, dass \c g das Inverse von \c h enthält, kann der folgende
    Programmcode verwendet werden:
    \code 
 Group g,h;
 ...
 h = g;
 !h;
    \endcode
\li Die Operatoren

Da zur Anwendung der \c GroupIndex - Klassen immer eine Gruppe benötigt wird, die auf einer Menge operiert,
muss auch die Struktur einer \em Gruppenoperation implementiert werden. Dazu benötigt die
Gruppenklasse ein Überladen des *= - Operators:
\code 
 Set& Group::operator*=(Set& s) const;
\endcode
Die Codezeilen
\code
 Group g;
 Set s_1, s_2;
 ...
 s_2 = s_1;
 g *= s_2;
\endcode
haben dann im mathematischen Sinne die Bedeutung \em s_2 = \em g*s_1 , d.h. das Gruppenelement \em g
operiert auf dem Mengenelement \em s_1.

In Zusammenhang mit der Gruppenoperation benötigen die \c GroupIndex - Klassen auch eine
Funktion zur \em Repräsentantenberechnung. Diese muss durch eine (im globalen namespace sichtbare) Funktion
\code
 void getRepresentation(const Set& m, Group& g_m, Set& r_m);
\endcode
implementiert werden. Diese Methode liefert zur Eingabe \c m jeweils ein Gruppen- und ein 
Mengenelement \c g_m bzw. \c r_m, so dass 
\code
 m == (g_m *= r_m)
\endcode
gilt. \c r_m muss dabei aus Element eines Repräsentantensystems \em R - einer 
geeigneten Teilmenge der \em G - Menge \em M - sein. 
Algebraisch gesehen berechnet \c getRepresentation also ein Gruppenelement, welches
ein beliebiges Mengenelement auf seinen Repräsentanten abbildet sowie den zugehörigen
Repräsentanten:

 \em m = \em g_m \em r_m

Für die algebraischen Einzelheiten sei hier auf die entsprechende Literatur verwiesen.

Zusätzlich zu den mathematisch relevanten Operatoren und Funktionen benötigt die Gruppenklasse noch einige
programmiertechnisch notwendigen Funktionen:
\li Konstruktoren und Destruktor
\li Stream-Operatoren \c operator<<() und \c operator>>() zum Lesen und Schreiben in Dateien
\li die Vergleichsoperatoren \c operator==() \c operator!=() (siehe dazu auch nachfolgende 
Bemerkung zu Vergleichsoperatoren)
\li durch den Operator 
\code 
 bool operator<(const Group& g, const Group& h)
\endcode
muss eine totale Ordnung auf den Instanzen der Gruppenklasse implementiert sein.
\li die Methode 
\code 
 int Group::size(); \endcode
gibt an, weiviele Bytes vom \c operator<<() in einen \c ofstream geschriben werden.
Falls alle Instanzen der Klasse gleich viel Platz belegen, kann diese Methode
auch als \c static implementiert werden.

Eine vollständige Deklaration einer abstrakten Gruppenklasse folgt im übernächsten Abschnitt;
zunächst werden die Funktionen der Mengenklasse näher beschrieben.

\em Bemerkungen \em zu \em Vergleichsoperatoren \c operator==() \em und \c operator!=()

Die Vergleichsoperatoren \c operator==() \c operator!=() müssen \em beide implementiert werden,
da sie zu Vergleichen in unterschiedlichen Situationen verwendet werden:
Der \c operator==() wird beim Indexaufbau verwendet und sollte die angegebenen Objekte auf exakte Gleichheit prüfen. Der
\c operator!=() hingegen wird bei der Suche verwendet; bei Bedarf kann der Ungleich-Operator 
auch dann ein \c false zurückliefern, wenn die beiden zu vergleichenden Objekte
ähnlich -- aber nicht exakt gleich -- sind. Dadurch wird eine einfache Form der Fehlertoleranz erlaubt;
allerdings verliert die Suche u.U. wichtige Eigenschaften, so z.B. die Assoziativität
der Schnittmengenbildung. Die naheliegenste Form, den \c operator!=() zu implementieren ist
natürlich ein 
\code
bool myGroup::operator!=(const myGroup& cmp)
{
   return !((*this)==g2);
}
\endcode
sofern nicht die oben erwähnte Form der Fehlertoleranz bei der Suche
gewünscht ist.

\subsection groupindex_set_class II.3 Mengenklassen

Die Instanzen einer Menge benötigen in den \c GroupIndex - Klassen keine weiteren 
Funktion im mathematischen Sinne - die Gruppenoperation und die Repräsentanenberechnung
werden bereits ausserhalb der Mengenklasse implementiert.

Es verbleiben die programmiertechnisch notwendigen Methoden, die in einer Mengenklasse zu
implementieren sind. Dazu gehören - fast identisch mit den Funktionen der Gruppenklasse:
\li Konstruktoren und Destruktor
\li Stream-Operatoren \c operator<<() und \c operator>>() zum Lesen und Schreiben in Dateien
\li ein Vergleichsoperator \c operator==()
\li durch den Operator 
\code 
 bool operator<(const Group& g, const Group& h)
\endcode
muss eine totale Ordnung auf den Instanzen der Gruppenklasse implementiert sein. Es sei angemerkt, dass
es hinreichend ist, wenn die durch diesen Operator gegebene Ordnung auf den Repräsentanten, die von
\c getRepresentation() berechnet werden, eine totale Ordnung ist.
\li die Methode 
\code 
 int Set::size(); \endcode
gibt an, wieviele Bytes vom \c operator<<() in einen \c ofstream geschrieben werden.
Falls alle Instanzen der Klasse gleich viel Platz belegen, kann diese Methode
auch als \c static implementiert werden.

In den meisten Fällen wird es sinnvoll sein, die zur Mengenklasse gehörige Gruppenklasse als \c friend
zu deklarieren.

\subsection abstract_goup_and_set_class II.4 Abstrakte Klassen für Gruppen- und Mengenklassen

Die folgenden Klassendeklarationen sind abstrakte Musterklassen für Gruppen- und 
Mengenklassen. Es ist theoretisch möglich, durch Ableiten von den Klassen \c AbstractGroup 
und \c AbstractSet und Implementieren der virtuellen Methoden konkrete Gruppen- und 
Mengenklassen zu erstellen. Es empfiehlt sich aber, \em nicht von diesen Klassen abzuleiten 
und von der Verwendung virtueller Methoden abzusehen, da deren Verwendung mit 
Effizienzeinbußen verbunden ist.

Statt dessen können Gruppen- und Mengenklasse als Basisklassen implementiert werden, 
und zwar so,
dass alle hier beschriebenen Methoden und Operatoren in diesen Klassen 
(möglichst nicht-virtuell) implementiert sind.
Unter Umständen lohnt es sich sogar, die Verknüpfungen der Gruppe und der Gruppenoperation
\c inline zu deklarieren.

\code
 class AbstractGroup
 {
 public:

    virtual bool operator==(Group&);
    virtual bool operator!=(Group&);
    virtual bool operator<(Group&);

    friend std::ofstream& operator<<(std::ofstream&, const Group&);
    friend std::ifstream& operator>>(std::ifstream&, const Group&);

    virtual Group();
    virtual Group(const Group&);
    virtual ~Group();

    virtual int size();
        
    virtual Group& operator!();
    virtual Group& operator*=(Group&);
    virtual Set& operator*=(Set&);
      
 };

\endcode

\code
 class AbstractSet
 {

 friend class AbstractGroup;

 public:

    virtual bool operator==(Set&);
    virtual bool operator<(Set&);

    friend std::ofstream& operator<<(std::ofstream&, const Set&);
    friend std::ifstream& operator>>(std::ifstream&, const Set&);

    virtual Set();
    virtual Set(const Set&);
    virtual ~Set();

    virtual int size();
        
 };

\endcode

\section how_to_implement III. Vorgehensweise zum Implementieren eines Index

Um ein Indexierungssystem mit der \c GroupIndex - Template-Library zu erstellen, sind
i.A. vier Schritte notwendig:
<ol>
<li> Identifizieren der Gruppenoperation, die dem zu erstellenden Index zugrunde liegt,
<li> Implementieren der entsprechenden Gruppen- und Mengenklasse,
<li> Auswahl geeigneter Container-Klassen
<li> Auswahl geeigneter Klassen für Repräsentantensystem und für invertierte Listen.
</ol>

\subsection index_impl_subsect1 III.1 Identifizieren der Gruppenoperation
Eine Erläterung des erstgenannten Punktes liegt "beyond the scope" dieser Dokumentation
(die sich auf programmiertechnische Aspekte beschränkt). 


\subsection index_impl_subsect2 III.2 Implementieren von Gruppen- und Mengenklasse
Ist die Menge mit der darauf operierenden Gruppe identifiziert, so sind für den
entsprechenden Index genau zwei Klassen
zu implementieren: eine Gruppen- und eine Mengenklasse, die wie im vorigen Abschnitt
erläutert implementiert werden müssen. Ist die der Mengenklasse zugrundeliegende Menge
nicht diskret, so ist evtl. eine geeignete Diskretisierung zu wählen; bei nicht-diskreten 
Gruppen empfiehlt es sich u.U. unscharfe Schnittmengenbildung zu verwenden. Dies erfordert bei der 
Implementierung zusätzlich einen Index-Operator für die Gruppenklasse (mehr dazu inder 
Dokumentation der Klasse \c groupindex::IntervalIntersectionGList ). Bei der Implementierung
von \c getRepresentation() gilt es zu beachten, dass ggf. Container mit den benötigten
Eigenschaften zum Speichern von (Fuzzy-) Repräsentanten und Stabilisator verwendet werden; 
Eine nähere Beschreibung dieser Container folgt im nächsten Abschnitt.

\subsection index_impl_subsect3 III.3 Auswahl von Container-Klassen
Die vom \c GroupIndex verwendeten Container werden in gesonderten Klassen deklariert:
Alle Container, die Mengenelemente enthalten, werden in einer Mengen-Container-Klasse
deklariert, und alle Container, die Gruppenelemente enthalten, werden in einer Gruppen-Container-Klasse
deklariert. Diese beiden Klassen - Mengen-Container-Klasse und Gruppen-Container-Klasse - werden
der Klasse \c groupindex::GroupIndex als Template-Parameter übergeben.
Folgende Eigenschaften der zugrundeliegenden Gruppenoperation bzw. Anforderungen
an den zu erstellenden Index erfordern spezielle Container-Klassen:

  \li Bei nicht-regulären Gruppenoperationen besteht der Stabilisator aus mehreren Elementen. 
  Deshalb muss ein Gruppen-Container verwendet werden, welcher mehrere Gruppenelemente verwaltet. Es empfiehlt sich, die
  Klasse
  \code
 groupindex::nonregular_group_container<Group, GList>
  \endcode
  zu verwenden.Die Methode \c getRepresentation muss dann folgende Parameter verwenden:
\code
 void getRepresentation(const Set& m, std::list<Group>& g_m, Set& r_m);
\endcode

  \li Zur Fuzzy-Suche wird nicht \em ein Repräsentant berechnet, sondern eine Menge von Repräsentanten.
  Dies erfordert einen Mengen-Container, welcher einen geeigneter Container zur Verfügung stellt. Dazu
  gibt es die Template Klasse
  \code
 groupindex::fuzzy_set_container<Group, GList>
  \endcode
Auch die Fuzzy-Suche erfordert eine Anpassung der Parameter von \c getRepresentation :
\code
 void getRepresentation(const Set& m, Group& g_m, std::list<Set>& r_m);
\endcode

\li Die Kombination aus Fuzzy-Suche und nicht-regulären Gruppenoperationen ist ebenfalls zulässig, indem
sowohl \c fuzzy_set_container als auch \c nonregular_group_container verwendet werden.
\c getRepresentation verwendet dann die Parameter
\code
 void getRepresentation(const Set& m, std::list<Group>& g_m, std::list<Set>& r_m);
\endcode

\subsection index_impl_subsect4 III.4 Auswahl von Klassen für Repräsentantensystem und für invertierte Listen
Abhängig von den Eigenschaften der Gruppenoperation sollten unterschiedliche Klassen
zum Verwalten invertierter Listen verwendet werden (zur Verwaltung von Repräsentanten
existiert z.Z. nur die Klasse \c groupindex::DefaultRepresentation). 
Für invertierte Liste stehen folgende Klassen zur Verfügung:
\li \c groupindex::GInvertedList<Group> für exakte Schnittmengenbildung,
\li \c groupindex::IntervalIntersectionGList<Group, numeric, Dim> für unscharfe Schnittmengenbildung sowie
\li \c groupindex::CompressedGInvertedList<Group> (für komprimierte Indexe bei Gruppen, deren Verknüpfung die zur Indexierung 
verwendete Ordnung der Gruppenelemente erhält. In der aktuellen Version ist dieser Listentyp nicht funktionsfähig.)

Alle Listentypen unterstützen Fuzzy- und Mismatch-Suche. Bei der \c groupindex::IntervalIntersectionGList müssen neben der 
Gruppenklasse zusätzlich noch die Template-Parameter \c numeric und \c Dim angegeben werden. Deren Bedeutung liegt 
darin, dass die Gruppenklasse den Index-Operator \c operator[] mit Rückgabetyp \c numeric überlädt, um die Gruppe in einen
geeigneten (kontinuierlichen) Vektorraum einzubetten:
\code
 numeric Group::operator[](int)
\endcode
Jedes Gruppenelement \c g liefert also für \c g[0],g[1],...g[Dim-1] einen Wert vom Typ numeric.
Der Typ \c numeric muss volle Artihmetik unterstützen, d.h. Addition, Subtraktion, Multiplikation und Division.
Oft genügt ein Typ vom Wert \c double oder \c float , denkbar ist aber auch, den Typ 
\c real aus der Bibliothek Leda zu verwenden. Weitere Details und Bedingnungen an die Gruppenklasse finden sich in der 
Dokumentation der \c IntervalIntersectionGList .

\section intro_examples IV. Beispiele
\warning Beispiele z.T. noch nicht getestet! -am 17.12.2001

In diesem Abschnitt werden einige Beispiele für die Auswahl von Containern und Listenklassen zur Umsetzung
eines Indexierungsystems gegeben. Es werden lediglich die C++-Typdeklarationen angegeben, keine detaillierten
Implementierungen der Gruppen- und Mengenklassen. Gruppen- bzw. Mengenklasse werden stets als \c myGroup bzw.
\c mySet angegeben.

Alle \c typedefs bis auf die Deklaration des Typs \c myIndex sind lediglich Hilfsdeklarationen, um
die Definitionen übersichtlicher zu gestalten. Zum weiteren Gebrauch im Indexierungssystem
werden ausschließlich Instanzen der Klasse \c myIndex benötigt.

\subsection example1 IV.1 Beispiel 1: Reguläre Gruppenoperation ohne Fuzzy-Suche mit exakter Schnittmengenberechnung

\code
 typedef GInvertedList < myGroup  > myGList;
 typedef DefaultRepresentation < 
            mySet, 
            myGroup, 
            myGList 
         > myRepresentation;
 typedef GroupIndex <
            mySet, 
            myGroup, 
            myRepresentation, 
            myGList 
         > myIndex;
\endcode

\subsection example2 IV.2 Beispiel 2: Reguläre Gruppenoperation ohne Fuzzy-Suche mit unscharfer Schnittmengenberechnung

\code
 typedef IntervalIntersectionGList < myGroup , 7 , double > myGList;
 typedef DefaultRepresentation <
            mySet, 
            myGroup, 
            myGList 
         > myRepresentation;
 typedef GroupIndex <
            mySet, 
            myGroup, 
            myRepresentation, 
            myGList 
         > myIndex;
\endcode

\subsection example3 IV.3 Beispiel 3: Nicht-reguläre Gruppenoperation ohne Fuzzy-Suche mit unscharfer Schnittmengenberechnung

\code
 typedef nonregular_group_container < myGroup > my_group_container;
 typedef default_set_container < mySet > my_set_container;
 typedef IntervalIntersectionGList < myGroup , 7 , double > myGList;
 typedef DefaultRepresentation <
            mySet, 
            myGroup, 
            myGList, 
            my_group_container, 
            my_set_container 
         > myRepresentation;
 typedef GroupIndex < 
            mySet, 
            myGroup, 
            myRepresentation, 
            myGList,
            my_group_container, 
            my_set_container 
         > myIndex;
\endcode

\subsection example4 IV.4 Beispiel 4: Nicht-reguläre Gruppenoperation mit Fuzzy-Suche mit unscharfer Schnittmengenberechnung

\code
 typedef nonregular_group_container < myGroup > my_group_container;
 typedef fuzzy_set_container < mySet > my_set_container;
 typedef IntervalIntersectionGList < myGroup , 7 , double > myGList;
 typedef DefaultRepresentation <
            mySet, 
            myGroup, 
            myGList, 
            my_group_container, 
            my_set_container 
         > myRepresentation;
 typedef GroupIndex < 
            mySet, 
            myGroup, 
            myRepresentation, 
            myGList,
            my_group_container, 
            my_set_container 
         > myIndex;
\endcode

\section intro_commandline V. Erzeugen simpler Benutzer-Schnittstellen mit Hilfe der Template-Klasse IndexCommandLine

Die Template-Klassen für Repräasentantensystem, invertierte Listen und Indexe stellen
lediglich ein Index-Objekt zur Verfügung, mit dem durch Aufruf der Methoden eines 
Index-Objektes die Funktionen eines Indexierungssystems (Einfügen, Suchen und Löschen)
ausgeführt werden können. Um diese Funktionen auch einem Benutzer zur Verfügung zu stellen,
ohne die C++-Schnittstellen verwenden zu müssen, gibt es die Template-Klasse \c IndexCommandLine.
Diese erzeugt für eine fertige Indexklasse aus einem anzugebenen Interface zum Einlesen
von Daten ein kleines Kommandozeilen-Tool, mit dem die Funktionen eines Index per
Tastatureingabe einiger primitiver Befehle (z.B. ADD, REMOVE oder SEARCH) gesteuert 
werden können.

Eine genaue Beschreibung liegt in der Dokumentation zur Klasse \c groupindex::IndexCommandLine vor.

*/

namespace groupindex
{

template 
 <class Set,                  // Klasse für Elemente der Menge M'  
  class Group,                // Klasse für Elemente der Gruppe G  
  class Representation = DefaultRepresentation<Set, Group>,   // Klasse fuer Elemente aus dem Repraesentantensystem R'
  class GList = GInvertedList<Group>,
  class GroupContainers = default_group_container<Group, GList>,    // Diese Klasse enthält typedefs für Iteratoren, die für Gruppenelemente bzw. G-inverteirte Listen zu verwenden sind
  class SetContainers = default_set_container<Set>       // Diese Klasse enthält typedefs für Iteratoren, die für Mengenelemente zu verwenden sind
  >

class GroupIndex
{

private:

    NameToIndexMap nameToIndexMap;              
    IndexToNameMap indexToNameMap;              

    int maxFileIndex;                                   

    clock_t insertion_time;
        
public:

    typedef Group IndexGroup;
    typedef Set IndexSet;
    typedef Representation IndexRepresentation;

        Representation representation;
        
        time_t start;

        time_t finish;

    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
    std::string getFileName(int fileindex)
    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        {
                IndexToNameMap::iterator it;
                it = indexToNameMap.find(fileindex);
                if (it != indexToNameMap.end())
                        return indexToNameMap[fileindex];
                else
                {
                        throw IndexingException(IndexingException::UNKNOWN_FILEINDEX);
                        return std::string(); // leeren String zurückliefern.
                }
        }

    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        std::string getUniqueFileName(std::string& filename)
    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        {
                if (!hasFileIndex(filename))
                        return filename;
                
                int i=0;
                char buffer[20];

                while (true)
                {
                        
                        std::string ufilename = filename;
                        my_itoa(i,buffer,10);
                        ufilename.append("_");
                        ufilename.append(buffer);
                        if (!hasFileIndex(ufilename))
                                return ufilename;

                }
        }

    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        bool hasFileIndex(const std::string& filename)
    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        {
                NameToIndexMap::iterator it;
                it = nameToIndexMap.find(filename);
                if (it == nameToIndexMap.end())
                        return false;
                else
                        return true;
        }


    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        int getFileIndex(std::string filename)
    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        // liefert den zu filename gemappten index zurück.
        // bestizt filename keinen index, so wird ein neuer angelegt.
        {
                NameToIndexMap::iterator it;
                it = nameToIndexMap.find(filename);
                if (it != nameToIndexMap.end())
                        return nameToIndexMap[filename];
                else
                        return createNewFileMapping(filename);
        }

private:
    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        int createNewFileMapping(std::string filename)
    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        {

                if (filename.empty())
                        return -1;

                int fileindex = maxFileIndex;
                maxFileIndex++;

                nameToIndexMap.insert(NameToIndexEntry(filename, fileindex));
                indexToNameMap.insert(IndexToNameEntry(fileindex, filename));

                return fileindex;
        }
          
public:
    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        GroupIndex(Representation sr)
    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        {
                representation = sr;
        init();
        };

    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        GroupIndex()
    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        {
                representation = Representation();
        init();
        };
  
    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        ~GroupIndex()
    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        {

                clear();
        
        }

    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        void clear()
    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        {
                indexToNameMap.clear();
                nameToIndexMap.clear();
                representation.clear();
        }

private:

    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        virtual void initFileRead(char* filename)
    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        {
        std::cout<<"initFileRead\n";
                std::/*i*/fstream ifs;
        ifs.open(filename,std::ios::binary);
                
                if (!ifs)
                {
                        throw IndexingException(IndexingException::FILE_ERROR_OPEN);
                }

                initFileRead(ifs);

        }

public:

    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        GroupIndex(Representation& rep, const char* filename)
    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        {
        std::/*i*/fstream ifs;
        ifs.open(filename,std::ios::in | std::ios::binary);
        representation = rep;
        initFileRead(ifs);
    }

    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
    GroupIndex(Representation rep, std::/*i*/fstream& ifs) 
    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        {
        representation = rep;
        initFileRead(ifs);
    }

    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        //void initFileRead(ifstream ifs)
    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        //{
    //    initFileRead(fdopen(ifs.fd(),"rb"));
    //}

private:    
    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        void initFileRead(std::/*i*/fstream& ifs)
    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        {

        ifs.seekg(0,std::ios::beg);
        ifs.seekp(0,std::ios::beg);


        // BEGIN DEBUG
        long ffpos = ifs.tellg();
        // END DEBUG

        if (!ifs || ifs.eof())
        {
            nameToIndexMap.clear();
            indexToNameMap.clear();
            return;
        }


                char c_null = '\0';
                char buffer[2048];
                maxFileIndex = 0;

                // Anzahl der Files lesen
                int filecount;
        // BEGIN DEBUG
        ffpos = ifs.tellg();
        // END DEBUG
                ifs.read((char*)&filecount, sizeof(int));
        // BEGIN DEBUG
        ffpos = ifs.tellg();
        // END DEBUG
        if (!ifs || ifs.eof())
        {
            nameToIndexMap.clear();
            indexToNameMap.clear();
            return;
        }
          
                for (int i=0; i<filecount; i++)
                {
                        // fileindex lesen
                        int fileindex;
            // BEGIN DEBUG
            ffpos = ifs.tellg();
            // END DEBUG
                        ifs.read((char*)&fileindex, sizeof(int));
            // BEGIN DEBUG
            ffpos = ifs.tellg();
            // END DEBUG
            int i=0;
            do ifs.read(&buffer[i],1); while (buffer[i++]!=0);
        
                        std::string filename = std::string(buffer);

                        // (fileindex, filename)-Tupel anlegen
                        nameToIndexMap.insert(NameToIndexEntry(filename, fileindex));
                        indexToNameMap.insert(IndexToNameEntry(fileindex, filename));

                        if (fileindex>maxFileIndex)
                                maxFileIndex = fileindex;
                }

        // BEGIN DEBUG
        ffpos = ifs.tellg();
        // END DEBUG

        // G-Listen zum Lesen vorbereiten
                if (filecount>0)
                {
                        ifs>>representation;
                        maxFileIndex++;
                }


    }

public:
    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        GroupIndex(std::/*i*/fstream& ifs)
    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        {
        initFileRead(ifs);
        };

    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        void init()
    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        {
                
            insertion_time = 0;                 
                maxFileIndex = 0;
                representation.init();
                
        };

    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        friend std::ofstream& operator<< (std::ofstream& o, GroupIndex& idx)
    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        {
                
                idx.writeToFile(o);
        return o;
        }

private:        
    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        void writeToFile(std::ofstream& o)
    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        {
                
                char c_null = '\0';
                // fileindex<->filename - Map in Datei schreiben

                // Anzahl der Dateien schreiben
                int filecount = nameToIndexMap.size();

                o.write((char*)&filecount, sizeof(int));

                NameToIndexMap::iterator it = nameToIndexMap.begin();

                while (it!=nameToIndexMap.end())
                {
                        std::string fname = (*it).first;
                        int findex = (*it).second;

                        // fname und findex in stream schreiben
                        o.write((char*)&findex, sizeof(int));
                        int flen = fname.size();
                        o.write((char*)fname.c_str(), flen+1);

                        ++it;
                }
          
                // G-Listen in Datei schreiben
                o<<representation;
                
                finish = clock();
                insertion_time += (finish-start);
                
                #ifndef CHURCHILL // wenn CHURCHILL definiert ist, wird keine Statistik erzeugt
                FILE* stat_stream;
                stat_stream = fopen("groupindex.log","w");
                if (stat_stream!=NULL)
                {
                        writeStatistics(stat_stream);
                        fclose(stat_stream);
                }

                #endif

        };

public:
    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        void writeStatistics(FILE* stream)
    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        {
                double total_time = ((double)(1000.0*insertion_time)) / CLOCKS_PER_SEC;
                fprintf(stream,"Gesamtzeit zum Indexieren ohne Einlesen der Daten: %f secs\n",total_time/1000.0);
                representation.writeStatistics(stream);
        }
        

    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        void renameFile(std::string old_filename, std::string new_filename)
    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        {

                if (!hasFileIndex(old_filename)) 
                {
                        throw IndexingException(IndexingException::NO_SUCH_FILE);
                }

                if (hasFileIndex(new_filename))
                {
                        throw IndexingException(IndexingException::FILE_ALREADY_EXISTS);
                }

                int findex = getFileIndex(old_filename);

                indexToNameMap.erase(findex);
                nameToIndexMap.erase(old_filename);

                nameToIndexMap[new_filename] = findex;
                indexToNameMap[findex] = new_filename;  
                
        }

    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        void remove(std::string& filename)
    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        {
                // filename aus der Zuordnung filename <-> fileindex herausnehmen
                
                int fileindex = getFileIndex(filename);
                
                IndexToNameMap::iterator iit;
                iit = indexToNameMap.find(fileindex);
                if (iit != indexToNameMap.end())
                        indexToNameMap.erase(iit);

                NameToIndexMap::iterator nit;
                nit = nameToIndexMap.find(filename);
                if (nit != nameToIndexMap.end())
                        nameToIndexMap.erase(nit);

                // fileindex aus allen G-invertierten Listen herausnehmen
                
                representation.remove(fileindex);
                
        }
        
    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        void remove(char* filename)
    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        {
                std::string str_filename(filename);
                remove(str_filename); 
        }
                
    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        void insert(Set& m, const std::string& filename)
    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        {
                clock_t start = clock();

                int fileindex = getFileIndex(filename);
                representation.insert(m,fileindex);

                clock_t finish = clock();
                insertion_time += (finish-start);

        }
  
    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        void insert(Set& m, char* filename)
    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        {
                insert(m, std::string(filename));
        }
  
    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        int merge(char* indexfile2, int mode = MODE_MERGE_DELETE)
    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        {

                std::/*i*/fstream idxstream2;
        idxstream2.open(indexfile2, std::ios::in | std::ios::binary);

                // geändert für MultiDimGList (r.b. 31.01.2002)
//              if (idxstream2 == NULL)
                if (idxstream2.bad())
                        return -1;
                
                int succ = merge(idxstream2,mode);              

                idxstream2.close();

                return succ;

        }

    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        int merge(std::/*i*/fstream& idxstream2, int mode = MODE_MERGE_DELETE)
    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        {
                
                GroupIndex<Set,Group,Representation>* mergeIndex = new GroupIndex<Set,Group,Representation>(idxstream2);

                std::set<std::string> deleteList;

                // I. Schritt: Zuordnung zwischen Dateinummern und Dateinamen mergen

        NameToIndexMap::iterator it;

        std::pair<std::string,int> val;
        
        for (it = nameToIndexMap.begin(); it != nameToIndexMap.end(); it++)
        {
            
                        std::string fname = (*it).first;
                        if (mergeIndex->hasFileIndex(fname))
                        {
                                // Da ham'mer den Salat: Namenskonflikt!
                                if (mode==MODE_MERGE_MAKE_UNIQUE)
                                {
                                        // eindeutigen Dateinamen besorgen
                                        std::string ufname = getUniqueFileName(fname);
                                        // und umbenennen
                                        mergeIndex->renameFile(fname,ufname);
                                } else if (mode==MODE_MERGE_DELETE) {
                                        // MODE_MERGE_DELETE
                                        // Datei in die deleteList aufnehmen
                                        deleteList.insert(fname);
                } // else : mode==MODE_MERGE_IGNORE -> nix tun
                        }
                }
                
                // II. Schritt: ListTupel aus idx2 nachschlagen und in idx1 einfügen
        int i;
                for (i=0; i<mergeIndex->representation.size(); i++)
                {
                        GList* glist = mergeIndex->representation[i];

            // wer das folgende typename verstehen will, lese bitte im Stroustrup nach ;)
            typename GList::iterator it = glist->begin();
            typename GList::iterator last = glist->end();

                        for (; it!=last; it++)
                        {
                                ListTupel<IndexGroup> lt = *it;
                                std::string fname = mergeIndex->getFileName(lt.i);
                                Set s = mergeIndex->representation.getRepresentative(i);

                                // durch die folgenden beiden Zeilen ist sichergestellt,
                                // dass die G-invertierte Liste zu s ggf. neu angelegt wird.
                                GList* insertList = representation[s];

                                std::set<std::string>::iterator ci = deleteList.find(fname);
                                if (ci==deleteList.end() || mode==MODE_MERGE_MAKE_UNIQUE  || mode==MODE_MERGE_IGNORE)
                                {
                                        int findex = getFileIndex(fname);
                                        insertList->insert(lt.g,findex);
                                } else {
                                        // Namenskonflikt, mode==MODE_MERGE_DELETE
                                        // -> nix tun
                                }
                        }
                }

                idxstream2.close();

                delete mergeIndex;

                return 0;

        }
        
    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        int getIndexNameConflicts(char* indexfile2, std::set<std::string>& conflicting_names)
    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        {
                
                int conflict_count = 0;

                FILE* idxstream2 = fopen(indexfile2, "rb");
                if (idxstream2 == NULL)
                        return -1;

                GroupIndex<Set,Group,Representation> mergeIndex = GroupIndex<Set,Group,Representation>();
                mergeIndex.initFileRead(std::/*i*/fstream(fileno(idxstream2)));


                // Dateinamen aus idx1 in idx2 nachschlagen

                for (int i=0; i<maxFileIndex; i++)
                {
                        std::string fname = getFileName(i);
                        if (mergeIndex.hasFileIndex(fname))
                        {
                                
                                // Da ham'mer den Salat: Namenskonflikt!
                                conflict_count++;
                                conflicting_names.insert(conflicting_names.end(),fname);

                        }
                }

                fclose(idxstream2);
                
                return conflict_count;

        }
        
    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        int getFilenames(std::set<std::string>& filenames)
    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        {
                
        NameToIndexMap::iterator it;

        std::pair<std::string,int> val;
        
        for (it = nameToIndexMap.begin(); it != nameToIndexMap.end(); it++)
            filenames.insert((*it).first);

        return filenames.size();

        }
        
    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        long search(Set* query, int query_size, ListTupel<IndexGroup>*& result)
    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
    {
        return search(query, query_size, result, 0);
    }

    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
        long search(Set* query, int query_size, ListTupel<IndexGroup>*& result, int mismatches)
    // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
    {
        typename SetContainers::query_container c_query;
        
        // query-Array in query_container übertragen
        for (int i=0; i<query_size; i++)
            c_query.insert(c_query.begin(), query[i]);

        typename GroupContainers::result_container c_result;
        long rsize;

        rsize = search(c_query, c_result, mismatches);

        result = new ListTupel<IndexGroup>[rsize];
        typename GroupContainers::result_container::iterator r_it = c_result.begin();
        typename GroupContainers::result_container::iterator r_end = c_result.end();

        int j=0;
                rsize = 0;      // 3.7.02 r.b.
        for (; r_it!=r_end; r_it++)
        {
            result[j] = *r_it;
            j++;
                        rsize++;        // 3.7.02 r.b.
        }
        return rsize;

    }

    long search(const typename SetContainers::query_container& query, typename GroupContainers::result_container& result, int mismatches=0)
    {

        if (mismatches>=query.size())
            throw IndexingException(IndexingException::INVALID_QUERY);

            // Ermitteln der Ergebnislisten

            result.clear();
            if (query.size()<=0)
            {
                    return 0;
            }

            // result_lists und operator_list sind Arrays von Pointern, 
            // damit beim Sortieren niemand auf die Idee kommt, copy-Konstruktoren aufzurufen...
            GList** result_lists = new GList*[query.size()]; 

        typename SetContainers::query_container::const_iterator it = query.begin();
        typename SetContainers::query_container::const_iterator last = query.end();
    
        int rl_count = 0;
            for (;it!=last; it++)
            {
              
            // r_m besteht aus einer Menge von Fuzzy-Repräsentanten
            typename SetContainers::representation_container r_m;
        
            // g_m muss nicht den gesamten Stabilisator beinhalten, sondern nur ein Element aus diesem,
            // weil der Stabilisator bereits komplett in den invertierten Listen gespeichert ist.
            // C++-syntaktisch funktioniert das, weil der Stabilisator-Container
            // zuweisungskompatibel mit Group sein muss.
            Group g_m;
            typename GroupContainers::stabilizer_container stab;
            getRepresentation(*it, stab, r_m);
            g_m = stab;


            typename SetContainers::representation_container::iterator r_it = r_m.begin();
            typename SetContainers::representation_container::iterator r_last = r_m.end();

            // ermittle nun base_list als die erste NICHT LEERE (!) invertierte Liste der Fuzzy-Repräsentanten
            GList* base_list = representation[*(r_it)];

            r_it++;
            while (r_it != r_last && base_list==NULL)
            {
                base_list = representation[*(r_it)];
                r_it++;
            }

            // merge base_list mit allen weiteren nicht-leeren Listen der Fuzzy-Repräsentanten
            if (base_list!=NULL)
            {                
                // Kopie der Basisliste anlegen!
                base_list = new GList(*base_list);
#ifndef DONT_MERGE_WHILE_SEARCHING
                while (r_it!=r_last)
                {
                    GList* merge_with_list;
                    merge_with_list = representation[*(r_it++)];
                    if (merge_with_list != NULL)
                        base_list->merge(*merge_with_list);
                }
#else
#endif

                *base_list *= (!g_m);

                result_lists[rl_count++] = base_list;
            } else {
                // Wenn alle Listen der Fuzzy-Repräsentanten leer waren, wird dafür für alle 
                // Treffer-Kandidaten ein Mismatch benötigt.
                mismatches--;
            }

        } 

        if (rl_count==0)
        {
            delete[] result_lists;
            return 0;
        }

            // mache das Array result_lists zu einem heap 
        // (z.B. bezüglich Größe der Listen; nach welchem Kriterium der heap
        // verwaltet wird, entscheidet GList::operator>()
            heapify< GList >(result_lists, rl_count);   

            // ... und jetzt *effizient* die Schnittmenge aller Listen ermitteln

            int count = rl_count;

            GList* current_list = removeTopFromHeap< GList >(result_lists, count);
            int sect_list_size = current_list->size();
            
            // die Ausgangsmenge dient auch als Ergebnismenge, deshalb arbeiten wir auf einer Kopie dieser Liste
            // (-> Aufruf des copy-Konstrukturs!)

            // Bei der Suche muss der nicht-reguläre Fall nicht weiter beachtet werden, wenn
        // die invertierten Listen bereits beim Einfügen mit dem gesamten Stabilisator 
        // gefüllt werden.
        //
        // Wie sich leicht zeigen lässt, genügt es unter dieser Voraussetzung, bei der
        // Suche mit einem beliebigen Element aus dem Stabilisator zu arbeiten.
        // Dass dieses Vorgehen i.A. auch effizienter ist, zeigt die folgende Überlegung:
        //
        // Es bezeichne t \in \N die Grösse des (endlichen) Stabilisators und N die
        // Anzahl der Einträge in der invertierten Liste L \em modulo \em Stabilisator.
        // Dann hat nach oben vorgeschlagenem Vorgehen (Einfügen des gesamten Stabilisators 
        // in die invertierten Listen) die invertierte Liste L t*N Einträge. Durchsuchen 
        // dieser Liste kostet 
        //   (*)    O(log (t*N)) = O(log t + log N) 
        // Zeit.
        //
        // Nach dem alternativen Vorgehen werden die invertierten Listen modulo dem Stabilisator
        // gespeichert, enthalten also nur N Einträge. Zum Nachschlagen in dieser Liste
        // muss allerdings t mal in dieser Liste mit einem Zeitbedarf von je O(log N) gesucht
        // werden, was zu einem Gesamtaufwand von
        //  (**)    O(t*log N)
        // führt, was weniger effizient als (*) ist.

            GList* merge_list = NULL;

        current_list->setCredit(mismatches);

                // Eingefügt für MultiDimGList:
                current_list->setHeapStream(representation.getHeapStream());

            while (count>0 && current_list->size()>0)
            {
                    // Beachte: count wird durch removeTopFromHeap um eins verringert!
                    merge_list = removeTopFromHeap< GList >(result_lists, count);

                        // Eingefügt für MultiDimGList:
                        merge_list->setHeapStream(representation.getHeapStream());

                    // Schnittmenge der Listen bilden
                    current_list->intersect(*merge_list, mismatches);

            }
                    
            int rsize = current_list->size();

        // Ergebnisse der Schnittmengenbildungen nach result übertragen
                // kleine Änderung zwecks Test mit MultDimGList: (true)
        typename GList::iterator res_it = current_list->begin(true);
        typename GList::iterator res_last = current_list->end(true);

        while (res_it != res_last)
            {
                    result.insert(result.begin(),*res_it);
            res_it++;
            }

            // Speicher freigeben
            for (int i=0; i<rl_count; i++)
                    delete result_lists[i];
            delete[] result_lists;

            return rsize;

    }



};




}

#endif

The GroupIndex-Template-Library
Universität Bonn, Institut für Informatik III, 2001