The GroupIndex Template Library

---

GInvertedList.h

#ifndef DEF_GINVERTEDLIST
#define DEF_GINVERTEDLIST

#pragma warning( disable : 4786 )        

#ifndef maxStabSize
#define maxStabSize 6
#endif

#include "ListTupel.h"
#include "default_containers.h"
#include "consts.h"
#include "heap.h"
#ifndef DEF_LIMITS
#include <climits>
#define DEF_LIMITS
#endif
#ifndef VISUALC_INCLUDES
#include <unistd.h>
#include <sys/stat.h>
#include <mingw/stdlib.h>
#endif
const unsigned short power2[] = { 128, 64, 32, 16, 8, 4, 2, 1 } ;
#include <cstdio>
#include <cstdlib>
#include <io.h>


namespace groupindex
{


template <class Group>
std::ofstream& operator<<(std::ofstream& ofs, ListTupel<Group>& lt)
{
    ofs<<lt.g;
    ofs.write((char*)&(lt.i),sizeof(int));
    return ofs;

}

template <class Group>
std::ifstream& operator>>(std::ifstream& ifs, ListTupel<Group>& lt)
{
    ifs>>lt.g;
    ifs.read((char*)&(lt.i),sizeof(int));
    return ifs;

}

template<class Group>
class GInvertedList
{

protected:
    class read_iterator;

public:

    class iterator;

    //typedef iterator iterator;

protected:

    ListTupel<Group>* insertion_buffer;
    int ins_buffer_size;
    int ins_buffer_pos;
        // Änderung für MultiDimGList (r.b. 23.01.2002)
        //std::ifstream* m_stream;              // Datei        
        std::fstream* m_stream;
        // MultiDimGList Ende
        
        long m_fileoffset; 

        long m_id; 

        char m_insertion_file_name[1024];
        
    Group m_factor_inverse;

    Group m_factor;

        ListTupel<Group>* m_pos_beg;

    ListTupel<Group>* m_pos_end;
 
        int m_element_count; 

        int m_new_element_count; 

        ListTupel<Group>* m_elements;

    std::set<int> m_deleted_fileindices;

    void initFileRead(std::ifstream& ifs);
    void initFileRead(std::fstream& ifs);

    virtual void readElements();

    virtual void readElements(int credit);

        virtual void readElements(ListTupel<Group>* buffer, int credit);

    void clear();

    inline void setFileName(long id);

        virtual void writeToFile(std::ofstream& ofs);

    inline read_iterator find(const ListTupel<Group>& lt);
        
        inline read_iterator find(const ListTupel<Group>& lt, read_iterator& it);
        
        inline void remove(read_iterator& it);

    // vermindert den \c credit des Elements an der Position \c lt und löscht das Element ggf. aus der Liste
    inline void decrease(read_iterator& it);
    
        inline void assign(const read_iterator& new_beg, const read_iterator& new_end);
                
        void initInsertion();

    void insert(read_iterator& pos, const ListTupel<Group>& lt);

        void initUpdate();

public:
   
    GInvertedList<Group>(const GInvertedList<Group>& glist);

    GInvertedList<Group>(long id);

    GInvertedList<Group>();

    GInvertedList(std::/*i*/fstream& ifs);

    inline GInvertedList<Group>& operator*=(const Group& g);

    inline iterator begin();
        inline iterator begin(bool dummy);

    inline iterator end();
        inline iterator end(bool dummy);

protected:
    inline read_iterator _begin(void*);

    inline read_iterator _end(void*);

public:
    inline int size() const;

    void setCredit(int credit)
    {
    }

    friend std::ofstream& operator<< ANSI_BRACES (std::ofstream& o, GInvertedList<Group>& l);

        virtual void insert(const Group& g, int i);

        void remove(int fileindex);

        void intersect(GInvertedList<Group>& set2, int& mismatches);

        void merge(GInvertedList<Group>& set2);

        inline void setHeapStream(std::fstream& hps)
        {
        }

        ~GInvertedList();

protected:
    
    class read_iterator
    {

    protected:
            
            ListTupel<Group>* lt;

    public:
            
        // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
            inline read_iterator() {}
        // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
            
        // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
            inline read_iterator(ListTupel<Group>* l)
        // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
            {
                    lt = l;
            }

        // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
            inline ListTupel<Group>& operator*() const
        // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
            {
                    return *lt;
            }

        // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
            inline read_iterator& operator++()
        // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
            {
        
            do
            {
                            lt = &lt[1];
            } while (lt->credit<0);

            return *this;
            }

        // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
            inline read_iterator& operator++(int)
        // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
            {

            do
            {
                            lt = &lt[1];
            } while (lt->credit<0);

            return *this;
            }

        // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
            inline bool operator!=(const read_iterator& it)
        // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
            {
                    return !(lt == it.lt);
            }

        // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
            inline bool operator==(const read_iterator& it)
        // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
            {
                    return (lt == it.lt);
            }

    };


public:    
    // Einen Orden bekommt derjenige, der es schafft, den folgenden Klassen-Rumpf aus der Klassendefinition
    // herauszuholen (und zwar so, dass der MS-Compiler es trotzdem noch mag...)

    class iterator : public read_iterator
    {

    protected:
        Group* m_factor;

    public:

        inline iterator() {}

        inline iterator(const read_iterator& it) : read_iterator(it) {}

        inline iterator(const iterator& it) : read_iterator((read_iterator)it) 
        {
            m_factor = it.m_factor;
        }

        // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
            inline iterator(ListTupel<Group>* l, Group* g)
        // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
            {
                    lt = l;
            while (lt->credit<0)
                lt = &lt[1];
            m_factor = g;
            }

        // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
            inline ListTupel<Group> operator*()
        // /////////////////////////////////////////////////////////////////////////////////////////////////////////////
            {

            ListTupel<Group> r_lt;

            // m_factor von rechts an (*lt).g 'dranmultiplizieren und 
            // das Ganze in r_lt festhalten
                        r_lt.g = (*lt).g;
            r_lt.g *= (*m_factor);
            r_lt.credit = (*lt).credit;

            r_lt.i = (*lt).i;
                    return r_lt;
            }

    };

};

        


template<class Group>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
void GInvertedList<Group>::writeToFile(std::ofstream& ofs)
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{

    // insertion_buffer Flushen
    if (insertion_buffer != NULL)
    {

        if (chdir("list")==-1)
            #ifdef VISUALC_INCLUDES
            mkdir("list");
            #else
            mkdir("list",0);
            #endif
        else
            chdir("..");

            std::/*o*/fstream insertion_stream;
        insertion_stream.open(m_insertion_file_name, std::ios::app | std::ios::out | std::ios::binary);
            if (!insertion_stream)
            {
            throw IndexingException(IndexingException::FILE_ERROR_OPEN);
                    return;
            }

        for (int j=0; j<ins_buffer_pos; j++)
            insertion_stream<<insertion_buffer[j];
        ins_buffer_pos = 0;

        insertion_stream.close();

    }

    // Bereits indexierte Elemente in m_elements lesen
    readElements();

        ListTupel<Group>* new_elements = NULL;
    if (m_new_element_count>0)
    {
            std::ifstream insertion_stream;
        insertion_stream.open(m_insertion_file_name,std::ios::binary);

        if (insertion_stream == NULL || !insertion_stream)
            throw IndexingException(IndexingException::FILE_ERROR_OPEN);

        new_elements = new ListTupel<Group>[m_new_element_count+1];
        // stop-Element für iterator einfügen
        new_elements[m_new_element_count].credit = 0;

        // Alle ListTupel aus glist_-Datei in array lesen
            for (int i=0; i<m_new_element_count; i++)
            {
                    insertion_stream>>new_elements[i];
                    if (!insertion_stream)
                throw IndexingException(IndexingException::FILE_ERROR_READ);
            }

            insertion_stream.close();

            // array sortieren 
            heapsort< ListTupel<Group> >(new_elements,m_new_element_count);

    }
    
        ListTupel<Group>* all_elements = new ListTupel<Group>[m_element_count+m_new_element_count];
    long bytesize = 0;

        // mergen von m_elements und new_elements nach all_elements
    int i_old = 0;
    int i_new = 0;
    int i_all = 0;

    while (i_old<m_element_count || i_new<m_new_element_count)
        {

        if (i_new>=m_new_element_count || i_old<m_element_count && m_elements[i_old]>new_elements[i_new])
        {

            std::set<int>::iterator found = m_deleted_fileindices.find(m_elements[i_old].i);
            if (found==m_deleted_fileindices.end())
            {
                            all_elements[i_all] = m_elements[i_old];
                bytesize += m_elements[i_old].size();
                i_all++;
            }

            do {
                i_old++;
            } while (i_old<m_element_count && m_elements[i_old]==m_elements[i_old-1]);

        } else {

            while (i_old<m_element_count && m_elements[i_old]==new_elements[i_new])
            {
                // Duplikat entfernen
                i_old++;
            }

            std::set<int>::iterator found = m_deleted_fileindices.find(new_elements[i_new].i);
            if (found==m_deleted_fileindices.end())
            {
                            all_elements[i_all] = new_elements[i_new];
                bytesize += new_elements[i_new].size();
                i_all++;
            }

            do {
                i_new++;
            } while (i_new<m_new_element_count && new_elements[i_new]==new_elements[i_new-1]);
        
        }

        }

    int all_element_count = i_all;


    // Länge der Liste, Anzahl von Einträgen und ID schreiben    
    ofs.write((char*)&m_id,sizeof(long));
    ofs.write((char*)&all_element_count,sizeof(long));
    ofs.write((char*)&bytesize,sizeof(long));

    m_fileoffset = ofs.tellp();

        // Schreiben von all_elements
    for (i_all = 0; i_all<all_element_count; i_all++)
        {

                ofs<<all_elements[i_all];

        };

    m_element_count = all_element_count;
    m_new_element_count = 0;

    // belegte Resourcen (Speicher und Dateien) freigeben
    delete[] m_elements;
        delete[] new_elements;
    delete[] all_elements;
    m_elements = NULL;

    // Alle ListTupel stehen jetzt in der Indexdatei; die temporäre glist_-Datei
    // kann daher gelöscht werden.
    ::remove(m_insertion_file_name);

    m_deleted_fileindices.clear();

}

template<class Group>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
GInvertedList<Group>::GInvertedList<Group>(const GInvertedList<Group>& glist)
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{
    ins_buffer_size = glist.ins_buffer_size;
    ins_buffer_pos = glist.ins_buffer_pos;
    if (glist.insertion_buffer!=NULL)
    {
        insertion_buffer = new ListTupel<Group>[ins_buffer_size];
        for (int i=0; i<ins_buffer_pos; i++)
            insertion_buffer[i] = glist.insertion_buffer[i];
    }
        else
                insertion_buffer = NULL;
        
        m_stream = glist.m_stream;
        strcpy(m_insertion_file_name,glist.m_insertion_file_name);
        m_fileoffset = glist.m_fileoffset;
        m_factor = glist.m_factor;
        m_factor_inverse = glist.m_factor_inverse;

        m_elements = NULL;
        m_element_count = glist.m_element_count;
        m_new_element_count = glist.m_new_element_count;

        m_pos_beg = NULL;
        m_pos_end = NULL;

    m_id = glist.m_id;

}

template<class Group>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
GInvertedList<Group>::GInvertedList<Group>()
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{
        m_elements = NULL;
    m_stream = NULL;

        m_insertion_file_name[0] = '\0';
        m_element_count = 0;
        m_new_element_count = 0;

        m_pos_beg = NULL;
        m_pos_end = NULL;

    ins_buffer_size = INS_BUFFER_SIZE;
    ins_buffer_pos = 0;
    insertion_buffer=NULL;
        
    m_id = -1;
};

template<class Group>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
GInvertedList<Group>::GInvertedList<Group>(long id)
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{
        m_elements = NULL;
        m_element_count = 0;
        m_new_element_count = 0;

        m_pos_beg = NULL;
        m_pos_end = NULL;

    m_id = id;

    ins_buffer_size = INS_BUFFER_SIZE;
    ins_buffer_pos = 0;
    insertion_buffer=NULL;

    initInsertion();
    
};

template<class Group>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
inline GInvertedList<Group>& GInvertedList<Group>::operator*=(const Group& g)
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{
        m_factor = g;
        m_factor_inverse = g;
        !m_factor_inverse;
    return *this;
};

template<class Group>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
inline GInvertedList<Group>::iterator GInvertedList<Group>::begin()
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{
    
    if (m_elements==NULL)
        readElements();

        return iterator(m_pos_beg, &m_factor);
};

template<class Group>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
inline GInvertedList<Group>::iterator GInvertedList<Group>::begin(bool dummy)
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{
        return begin();
}

template<class Group>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
inline GInvertedList<Group>::iterator GInvertedList<Group>::end()
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{
        return iterator(m_pos_end);
};

template<class Group>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
inline GInvertedList<Group>::iterator GInvertedList<Group>::end(bool dummy)
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{
        return end();
}

template<class Group>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
inline GInvertedList<Group>::read_iterator GInvertedList<Group>::_begin(void*)
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{
        return read_iterator(m_pos_beg);
};

template<class Group>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
inline GInvertedList<Group>::read_iterator GInvertedList<Group>::_end(void*)
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{
        return read_iterator(m_pos_end);
};


template<class Group>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
inline int GInvertedList<Group>::size() const
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{
        return m_element_count;
};

template<class Group>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
void GInvertedList<Group>::insert(const Group& g, int i)
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{
    
    // Falls noch nicht geschehen, wird zunächst die temporäre Datei initialisiert
    // initUpdate();

        m_new_element_count++;

    if (insertion_buffer == NULL)
        insertion_buffer = new ListTupel<Group>[ins_buffer_size];

    ListTupel<Group> lt(g,i);
        if (ins_buffer_pos < ins_buffer_size)
    {
        insertion_buffer[ins_buffer_pos++] = lt;
        return;
    }

    if (chdir("list")==-1)
        #ifdef VISUALC_INCLUDES
        mkdir("list");
        #else
        mkdir("list",0);
        #endif
    else
        chdir("..");

        std::/*o*/fstream insertion_stream;
    insertion_stream.open(m_insertion_file_name, std::ios::app | std::ios::out | std::ios::binary);
        if (!insertion_stream)
        {
        throw IndexingException(IndexingException::FILE_ERROR_OPEN);
                return;
        }

    for (int j=0; j<ins_buffer_size; j++)
        insertion_stream<<insertion_buffer[j];
        insertion_stream<<lt;
    ins_buffer_pos = 0;

    insertion_stream.close();

};

template<class Group>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
void GInvertedList<Group>::initInsertion()
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{
    setFileName(m_id);
};


template<class Group>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
inline void GInvertedList<Group>::setFileName(long id)
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{

        char sNum[28];
        my_itoa(id, sNum, 16);
        strcpy(m_insertion_file_name,"list/glist_");
        strcat(m_insertion_file_name,sNum);

    m_stream = NULL;
        
}


template<class Group>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
void GInvertedList<Group>::initFileRead(std::ifstream& ifs)
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{
    
    long bytesize;

    // Indexweite eindeutige ID der Liste lesen
    ifs.read((char*)&m_id, sizeof(long));
    
        // Anzahl Einträge lesen
    ifs.read((char*)&m_element_count, sizeof(long));

    m_new_element_count = 0;

    // Länge der aktuellen Liste ermitteln
        ifs.read((char*)&bytesize, sizeof(long));
        if (!ifs)
        throw IndexingException(IndexingException::FILE_ERROR_READ);

    // Namen für Einfüge-Datei anhand von m_id festlegen
    initInsertion();

        m_stream = &ifs;
        //m_fileoffset = offset;
        m_fileoffset = ifs.tellg();


        // stream-Position auf nächste Liste setzen
    ifs.seekg(bytesize, std::ios::cur);
        if (!ifs)
                throw IndexingException(IndexingException::FILE_ERROR_READ);

}

template<class Group>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
void GInvertedList<Group>::initFileRead(std::fstream& ifs)
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{
    
    long bytesize;

    // Indexweite eindeutige ID der Liste lesen
    ifs.read((char*)&m_id, sizeof(long));
    
        // Anzahl Einträge lesen
    ifs.read((char*)&m_element_count, sizeof(long));

    m_new_element_count = 0;

    // Länge der aktuellen Liste ermitteln
        ifs.read((char*)&bytesize, sizeof(long));
        if (!ifs)
        throw IndexingException(IndexingException::FILE_ERROR_READ);

    // Namen für Einfüge-Datei anhand von m_id festlegen
    initInsertion();

        m_stream = &ifs;
        //m_fileoffset = offset;
        m_fileoffset = ifs.tellg();


        // stream-Position auf nächste Liste setzen
    ifs.seekg(bytesize, std::ios::cur);
        if (!ifs)
                throw IndexingException(IndexingException::FILE_ERROR_READ);

}

template<class Group>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
GInvertedList<Group>::GInvertedList<Group>(std::/*i*/fstream& ifs)
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{

    ins_buffer_size = INS_BUFFER_SIZE;
    ins_buffer_pos = 0;
    insertion_buffer=NULL;
    
        m_elements = NULL;
    m_pos_beg = NULL;
    m_pos_end = NULL;

    initFileRead(ifs);

}    

template<class Group>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
void GInvertedList<Group>::readElements()
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{
        if (m_elements!=NULL || m_stream==NULL)
        // nix zu tun
                return;

        m_elements = new ListTupel<Group>[m_element_count+1];

    // stop-Element für iterator einfügen
    m_elements[m_element_count].credit = 0;
        readElements(m_elements, 0);
    m_pos_beg = &(m_elements[0]);
    m_pos_end = &(m_elements[m_element_count]);
};

template<class Group>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
void GInvertedList<Group>::readElements(int credit)
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{
        if (m_elements!=NULL || m_stream==NULL)
        // nix zu tun
                return;

        m_elements = new ListTupel<Group>[m_element_count+2];


    // stop-Element für iterator einfügen
    m_elements[m_element_count].credit = 0;
        readElements(m_elements, credit);
    m_pos_beg = &(m_elements[0]);
    m_pos_end = &(m_elements[m_element_count]);
};

template<class Group>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
void GInvertedList<Group>::readElements(ListTupel<Group>* buffer, int credit) 
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{
        if (m_stream==NULL)
        return;


    (*m_stream).seekg(m_fileoffset, std::ios::beg);
    int i;
    for (i=0; i<m_element_count; i++)
    {
        (*m_stream)>>(ListTupel<Group>&)buffer[i];
        buffer[i].credit = 0;
/*// BEGIN DEBUG
                Group g = buffer[i].g;
                std::cout << i << ": (" << g << ") -> ";
                g *= m_factor;
                std::cout << "(" << g << ")\n";
// END DEBUG*/
    }
    //(*m_stream).read((char*)buffer, m_element_count*sizeof(ListTupel<Group>));
        if (!(*m_stream))
        {
                throw IndexingException(IndexingException::FILE_ERROR_READ);
        }

   for (i=0; i<m_element_count; buffer[i++].credit = credit);


};

template<class Group>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
void GInvertedList<Group>::clear()
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{
    delete[] m_elements;
    m_elements = NULL;
}

template<class Group>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
void GInvertedList<Group>::remove(int fileindex)
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{
    // TODO: anpassen!
    // alle ListTupel (sowohl die bereits indexierten als auch die in m_insertion_file_name
    // enthaltenen), die nicht Dateinummer fileindex haben, 
    // in Datei m_insertion_file_name schreiben, dann m_element_count
    // auf 0 setzen und m_new_element_count auf Anzahl der verbliebenen ListTupel setzen.

    m_deleted_fileindices.insert(fileindex);

/*      ifstream insertion_stream;
    insertion_stream.open(m_insertion_file_name,ios::binary);
        if (insertion_stream == NULL)
        throw IndexingException(IndexingException::FILE_ERROR_OPEN);

    // Bereits indexierte Elemente in m_elements lesen

        ListTupel<Group>* new_elements = new ListTupel<Group>[m_new_element_count+1];
    // stop-Element für iterator einfügen
    new_elements[m_new_element_count].credit = 0;

        // Alle ListTupel aus glist_-Datei in array lesen
        for (int i=0; i<m_new_element_count; i++)
        {
                insertion_stream>>new_elements[i];
                if (!insertion_stream)
            throw IndexingException(IndexingException::FILE_ERROR_READ);
        }

        insertion_stream.close();

    ofstream output_stream;

    char out_file_name[1024];
    strcpy(out_file_name, m_insertion_file_name);
    strcat(out_file_name, "~");

    output_stream.open(out_file_name,ios::binary | ios::app);

        for (i=1; i<m_new_element_count; i++)
        {
        if (new_elements[i].i!=fileindex)
            output_stream<<new_elements[i];
        else 
            m_new_element_count--;
        };

        delete[] new_elements;

    output_stream.close();

    // Alle ListTupel stehen jetzt in der Indexdatei; die temporäre glist_-Datei
    // kann daher gelöscht werden.
    if (::remove(m_insertion_file_name)!=0)
        throw IndexingException(IndexingException::FILE_ERROR_WRITE);

    if (rename(out_file_name,m_insertion_file_name)!=0)
        throw IndexingException(IndexingException::FILE_ERROR_WRITE);
  */  
}


template<class Group>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
GInvertedList<Group>::read_iterator GInvertedList<Group>::find(const ListTupel<Group>& lt) 
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{
        read_iterator found = end();
        int left = 0;
        int right = size();
        int mid = 0;

        ListTupel<Group> l1 = lt;
        l1.g *= m_factor_inverse;

        while (left<=right && found==end())
        {
                mid = (left+right)/2;

                ListTupel<Group>* cmp = &m_elements[mid];                       
                if (l1.i==(*cmp).i && !(l1.g!=(*cmp).g))
                        found = read_iterator(cmp);
                else if (l1<*cmp)
                        left = mid+1;
                else // (current>m_elements2[mid])
                        right = mid-1;
        }

        return found;
};


template<class Group>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
GInvertedList<Group>::read_iterator GInvertedList<Group>::find(const ListTupel<Group>& lt, read_iterator& it)
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{
        return find(lt);
};

template<class Group>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
inline void GInvertedList<Group>::assign(const read_iterator& new_beg, const read_iterator& new_end)
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{
        m_pos_beg = &*new_beg;
        m_pos_end = &(*new_end);
    (*new_end).credit = 0;
};

template<class Group>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
inline void GInvertedList<Group>::remove(read_iterator& it)
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{
    (*it).credit = -1;
}

template<class Group>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
inline void GInvertedList<Group>::decrease(read_iterator& it)
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{
    if ((--((*it).credit))==-1)
        m_element_count--;
}

template<class Group>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
void GInvertedList<Group>::intersect(GInvertedList<Group>& glist2, int& mismatches)
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{
    
    if (m_elements==NULL)
        readElements(mismatches);

    glist2.readElements(mismatches>0 ? mismatches-1 : 0);

    //cout<<*this<<endl<<endl<<glist2<<endl<<endl<<endl;

        // iterator, der auf das nächste zu suchende ListTupel zeigt
        read_iterator it = _begin(NULL);

        // iterator, der auf die Position zeigt, an der das nächste Element einzufügen ist.
        read_iterator ins = _begin(NULL);
        read_iterator last = _end(NULL);

        for (; it != last; it++)
        {
                
                ListTupel<Group> l1 = *it;
        l1.g *= m_factor;

                read_iterator found = glist2.find(l1);

                if (found!=glist2.end())
                {
            glist2.remove(found);
            *ins = *it;
                        ins++;
        } else {
            // l1 hat einen Mismatch
            decrease(it);
            if ((*it).credit>=0)
            {
                *ins = *it;
                ins++;
            }
        }

        }
        
        // neuen Bereich der Liste festlegen auf Bereich vom bisherigen ersten Element bis zur aktuellen Einfügeposition,
        // die durch den Iterator ins angezeigt wird;
        // die Bedeutung von assign() ist dieselbe wie die des assign() der stl-Container (z.B. list oder vector).
    assign(_begin(NULL), ins);

    if (mismatches>0)
    {
        merge(glist2);
        mismatches--;
    }

    glist2.clear();

};

template<class Group>
bool operator>(const GInvertedList<Group>& l1, const GInvertedList<Group>& l2)
{
    return l1.size() > l2.size();
}

template<class Group>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
void GInvertedList<Group>::merge(GInvertedList<Group>& glist2)
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{

    glist2.readElements();
    readElements();

    m_element_count = size()+glist2.size();
    ListTupel<Group>* new_elements = new ListTupel<Group>[m_element_count+1];
    // stop-Element für iterator einfügen
    new_elements[m_element_count].credit = 0;
    
    read_iterator it1 = _begin(NULL);
    read_iterator it2 = glist2._begin(NULL);
    int ins_pos = 0;

    while (it1!=(read_iterator)(end()) || it2!=(read_iterator)(glist2.end()))
    {
        if (it2==(read_iterator)(glist2.end()) || ( it1!=(read_iterator)(end()) && (*it1)<(*it2) ) )
        {
            new_elements[ins_pos++] = *it1;
            it1++;
        } else {
            (*it2).g *= (glist2.m_factor); 
            (*it2).g *= (m_factor_inverse);
            new_elements[ins_pos++] = *it2;
            it2++;
        }
    }

    delete[] m_elements;
    m_elements = new_elements;
    assign(read_iterator(&new_elements[0]),read_iterator(&new_elements[m_element_count]));

}

template<class Group>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
GInvertedList<Group>::~GInvertedList<Group>()
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{
        if (m_elements != NULL)
                delete[] m_elements;

    ::remove(m_insertion_file_name);

        m_elements = NULL;

    if (insertion_buffer != NULL)
        delete[] insertion_buffer;
    insertion_buffer = NULL;

};

template<class Group>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
std::ofstream& operator<<(std::ofstream& o, GInvertedList<Group>& l)
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{
        l.writeToFile(o);
        return o;
};

template<class Group>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
std::ostream& operator<<(std::ostream& o, GInvertedList<Group>& l)
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{
        o<<l.m_factor<<"*("<<endl;
    l.readElements();
    GInvertedList<Group>::read_iterator it = l.begin();
    GInvertedList<Group>::read_iterator fin = l.end();

    for (; it!=fin; it++)
        o<<"  <"<<(*it).g<<", "<<(*it).i<<", "<<(*it).credit<<">"<<endl;
    o<<")"<<endl<<endl;

        return o;
};

}

#endif

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