The GroupIndex Template Library

---

DefaultRepresentation.h

#ifndef DEFAULTREPRESENTATION
#define DEFAULTREPRESENTATION

#pragma warning( disable : 4786 )        

#include "GInvertedList.h"
#include <string>
#include <cstdlib>
#include <assert.h>


namespace groupindex
{

template <
    class Set, 
    class Group, 
    class GList = GInvertedList<Group>,
    class GroupContainers = default_group_container<Group, GList>,
    class SetContainers = default_set_container<Set>
>

class DefaultRepresentation

{

protected:

        Set* gListRepresentatives; 

        long gList_count;

        long expected_size;

        long increment_size;

        long current_size;

        long filecounter;

        
        void expandGLists();

        GList** gLists;

        void insertGList(const Set& r, long pos);

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

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

        // Hinzugefügt für MultiDimGList:
        std::fstream* m_heapStream;

public: 

    class iterator
    {

    protected:

        Set* pos;        
        Representaion* rep;

    public:

        std::pair<Set,GList*> operator*()
        {
            return std::pair<Set,GList*>(*pos, rep->gLists[*pos]);
        }

        iterator& operator++()
        {
            pos++;
            return *this;
        }

        iterator& operator++(int)
        {
            pos++;
            return *this;
        }

        bool operator==(const iterator& cmp) const
        {
            return (rep==cmp.rep && pos==cmp.pos);
        }

        iterator& operator=(const iterator& copy_from)
        {
            rep = copy_from.rep;
            pos = copy_from.pos;
        }

        iterator()
        {
            rep = NULL; 
            pos = NULL;
        }

        iterator(Representation* r)
        {
            rep = r; 
            pos = NULL;
        }

        iterator(Representation* r, Set* p)
        {
            rep = r; 
            pos = p;
        }

        iterator(const iterator& copy_from)
        {
            rep = copy_from.rep;
            pos = copy_from.pos;
        }

    };

    iterator begin();

    iterator end();


        DefaultRepresentation(long i_expected_size, long i_increment_size);

        DefaultRepresentation();

        GList* operator[](int index);

        GList* operator[](const Set& r);

        Set getRepresentative(long i);


        virtual void insert(Set m, int i);      

  
        void remove(int fileindex);
        
        virtual void init();
            
        //GList* getGList(const int i) const
        GList* operator[](const int& i) const;

        long getGListIndex( Set& r);
        
        long size() const;


        ~DefaultRepresentation();

        void clear();
        
        void writeStatistics(FILE* stream);

    friend std::ofstream& operator<< ANSI_BRACES (std::ofstream& ofs, DefaultRepresentation& dr);

    friend std::/*i*/fstream& operator>>(std::/*i*/fstream& ifs, DefaultRepresentation& dr);

        // Eingefügt für MultiDimGList:
        void          setHeapStream(std::fstream& hps);
        std::fstream& getHeapStream();
};



template <
    class Set, 
    class Group, 
    class GList,
    class GroupContainers,
    class SetContainers
>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
void DefaultRepresentation<Set,Group,GList,GroupContainers,SetContainers>::expandGLists()
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{
        
        current_size += increment_size;
        GList** new_gLists = new GList*[current_size];
        Set* new_gListRepresentatives = new Set[current_size];

        for (long i=0; i<gList_count; i++)
        {
                new_gLists[i] = gLists[i];
                new_gListRepresentatives[i] = gListRepresentatives[i];
        }

        // Umstellung von gLists auf ein Zeiger-Array

        delete[] gLists;
        delete[] gListRepresentatives;

        gLists = new_gLists;
        gListRepresentatives = new_gListRepresentatives;

};



template <
    class Set, 
    class Group, 
    class GList,
    class GroupContainers,
    class SetContainers
>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
std::ofstream& operator<<(std::ofstream& ofs, DefaultRepresentation<Set,Group,GList,GroupContainers,SetContainers>& dr)
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{
    dr.writeToFile(ofs);
    return ofs;
}



template <
    class Set, 
    class Group, 
    class GList,
    class GroupContainers,
    class SetContainers
>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
std::/*i*/fstream& operator>>(std::/*i*/fstream& ifs, DefaultRepresentation<Set,Group,GList,GroupContainers,SetContainers>& dr)
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{
    dr.initFileRead(ifs);
    return ifs;
}



template <
    class Set, 
    class Group, 
    class GList,
    class GroupContainers,
    class SetContainers
>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
void DefaultRepresentation<Set,Group,GList,GroupContainers,SetContainers>::writeStatistics(FILE* stream)
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{
        unsigned long number_of_gLists = gList_count;
        unsigned long max_size = 0;
        unsigned long min_size = 0xffffffff;
        unsigned long total_size = 0;
        int glist_insertion_fails = 0;
        int valid_list_count = 0;

        for (long i=0; i<gList_count; i++)
        {
                long size = gLists[i]->size();
                if (size>0)
                {
                        total_size += size;
                        if (size>max_size)
                                max_size = size;
                        if (size<min_size)
                                min_size = size;
                        //glist_insertion_fails += gLists[i]->glist_insertion_fails;
                        valid_list_count++;
                }
#ifdef VERBOSE_STATISTICS               
                fprintf(stream,"%d %d\n",i,size);

#endif
        }

        fprintf(stream,"Anzahl G-invertierter Listen: %d  \n",number_of_gLists);
        fprintf(stream,"Einträge in größter Liste: %d  \n",max_size);
        fprintf(stream,"Einträge in kleinster Liste: %d  \n",min_size);
        fprintf(stream,"Einträge insgesamt: %d  \n",total_size);
        fprintf(stream,"Einträge durchschnittlich: %f  \n",(double)total_size/(double)valid_list_count);
        fprintf(stream,"glist_insertion_fails: %d  \n",glist_insertion_fails);

}



template <
    class Set, 
    class Group, 
    class GList,
    class GroupContainers,
    class SetContainers
>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
GList* DefaultRepresentation<Set,Group,GList,GroupContainers,SetContainers>::operator[](int index)
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{
        return gLists[index];
}



template <
    class Set, 
    class Group, 
    class GList,
    class GroupContainers,
    class SetContainers
>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
void DefaultRepresentation<Set,Group,GList,GroupContainers,SetContainers>::clear()
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{
        
        if (gListRepresentatives!=NULL)
                delete[] gListRepresentatives;

    for (int i=0; i<gList_count; i++)
        delete gLists[i];
    
    if (gLists!=NULL)
                delete[] gLists;

        gLists = NULL;
        gListRepresentatives = NULL;

        current_size = 0;
        
        gList_count = 0;

        filecounter = 0;

}



template <
    class Set, 
    class Group, 
    class GList,
    class GroupContainers,
    class SetContainers
>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
DefaultRepresentation<Set,Group,GList,GroupContainers,SetContainers>::DefaultRepresentation(long i_expected_size, long i_increment_size)
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{

        expected_size = i_expected_size;
        increment_size = i_increment_size;


        gLists = NULL;
        gListRepresentatives = NULL;

        current_size = 0;
        
        gList_count = 0;

        filecounter = 0;

};



template <
    class Set, 
    class Group, 
    class GList,
    class GroupContainers,
    class SetContainers
>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
Set DefaultRepresentation<Set,Group,GList,GroupContainers,SetContainers>::getRepresentative(long i)
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{

    if (gListRepresentatives!=NULL)
                return gListRepresentatives[i];
        else
        throw IndexingException(IndexingException::INDEX_OUT_OF_BOUNDS);

}




template <
    class Set, 
    class Group, 
    class GList,
    class GroupContainers,
    class SetContainers
>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
DefaultRepresentation<Set,Group,GList,GroupContainers,SetContainers>::DefaultRepresentation()
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{
        expected_size = 1000;
        increment_size = 100;
        gLists = NULL;
        gListRepresentatives = NULL;
        current_size = 0;
        gList_count = 0;
        filecounter = 0;
};



template <
    class Set, 
    class Group, 
    class GList,
    class GroupContainers,
    class SetContainers
>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
GList* DefaultRepresentation<Set,Group,GList,GroupContainers,SetContainers>::operator[](const Set& r)
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{

        if (gList_count==0)
        {
                return NULL;
        }

        long left = 0;
        long right = gList_count-1;
        bool found = false;
        int mid = 0;

        
        // Binärsuche
        while (left<=right && !found)
        {
                        
                mid = (left+right)/2;

                Set cmp = gListRepresentatives[mid];                    
                if (r<cmp)
                        right = mid-1;
                else if (r==cmp)
                        found = true;
                else // M.a.W. : (cr>cmp)
                        left = mid+1;
        }

        if (found)
                return gLists[mid];
        else
                return NULL;
};



template <
    class Set, 
    class Group, 
    class GList,
    class GroupContainers,
    class SetContainers
>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
void DefaultRepresentation<Set,Group,GList,GroupContainers,SetContainers>::insert(Set m, int i)
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{
        
    typename SetContainers::representation_container r_m;
    typename GroupContainers::stabilizer_container stab;

        getRepresentation(m, stab, r_m);

    // Falls \c Group::getRepresentation() Fuzzy-Repräsentanten berechnet, 
    // so wird in die Liste von \em jedem Fuzzy-Repräsentanten der komplette
    // Stabilisator eingefügt.
    // Es sei angemerkt, dass beim Einfügen in den Index nur nach \em sehr reiflicher
    // Überlegung Fuzzy-Repräsentanten berechnet werden sollten, weil der Index dadurch
    // u.U. _sehr_ groß werden kann.

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

    for (; r_it != r_last; r_it++)
    {
        
        long r_m_list_idx = getGListIndex(*(r_it));

        // Füge kompletten Stabilisator in gLists[r_m_list_idx] ein
        typename GroupContainers::stabilizer_container::iterator s_it = stab.begin();
        typename GroupContainers::stabilizer_container::iterator s_last = stab.end();

                for (; s_it!=s_last; s_it++)
        {   
                        gLists[r_m_list_idx]->insert(*s_it,i);
        }

    }

}



template <
    class Set, 
    class Group, 
    class GList,
    class GroupContainers,
    class SetContainers
>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
void DefaultRepresentation<Set,Group,GList,GroupContainers,SetContainers>::writeToFile(std::ofstream& ofs)
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{

        // > Anzahl der Listen schreiben                
        ofs.write((char*)&gList_count, sizeof(long));
        ofs.write((char*)&filecounter, sizeof(long));
        
        for (long i=0; i<gList_count; i++)
        {

                // > Repräsentanten der Liste schreiben
                ofs<<gListRepresentatives[i];

                // > Größe der Liste schreiben

                // > Listeninhalt schreiben
                gLists[i]->setHeapStream(*m_heapStream);
        ofs<<*(gLists[i]);

        }

};
  


template <
    class Set, 
    class Group, 
    class GList,
    class GroupContainers,
    class SetContainers
>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
void DefaultRepresentation<Set,Group,GList,GroupContainers,SetContainers>::remove(int fileindex)
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{
        for (long i=0; i<gList_count; i++)
        {
                gLists[i]->remove(fileindex);
        }
}



template <
    class Set, 
    class Group, 
    class GList,
    class GroupContainers,
    class SetContainers
>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
void DefaultRepresentation<Set,Group,GList,GroupContainers,SetContainers>::init()
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{

        if (gLists!=NULL)
                delete[] gLists;
        if (gListRepresentatives!=NULL)
                delete[] gListRepresentatives;
        
        gListRepresentatives = new Set[expected_size];
        gLists = new GList*[expected_size];

        current_size = expected_size;

};


template <
    class Set, 
    class Group, 
    class GList,
    class GroupContainers,
    class SetContainers
>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
void DefaultRepresentation<Set,Group,GList,GroupContainers,SetContainers>::setHeapStream(std::fstream& hps)
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{
        m_heapStream = &hps;
}

template <
    class Set, 
    class Group, 
    class GList,
    class GroupContainers,
    class SetContainers
>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
std::fstream& DefaultRepresentation<Set,Group,GList,GroupContainers,SetContainers>::getHeapStream()
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{
        return *m_heapStream;
}

template <
    class Set, 
    class Group, 
    class GList,
    class GroupContainers,
    class SetContainers
>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
void DefaultRepresentation<Set,Group,GList,GroupContainers,SetContainers>::initFileRead(std::/*i*/fstream& ifs)
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{

        Set represents;
        
        // Anzahl der G-Listen lesen
        long gcount;
        ifs.read((char*)&gcount, sizeof(long));
        if (!ifs)
        throw IndexingException(IndexingException::FILE_ERROR_READ);
        ifs.read((char*)&filecounter, sizeof(long));

        gListRepresentatives = new Set[gcount];
        gLists = new GList*[gcount];
        current_size = gcount;
        
        gList_count = gcount;

        for (int i=0; i<gcount; i++)
        {
        
        // BEGIN DEBUG
        long ffpos = ifs.tellg();
        // END DEBUG

        // Repräsentanten der aktuell gelesenen Liste ermitteln
                ifs>>represents;
                if (!ifs)
                        throw IndexingException(IndexingException::FILE_ERROR_READ);

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

        gListRepresentatives[i] = represents;

                gLists[i] = new GList(ifs);

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

        // Eingefügt für MultiDimGList:
                gLists[i]->setHeapStream(*m_heapStream);

        }

}



template <
    class Set, 
    class Group, 
    class GList,
    class GroupContainers,
    class SetContainers
>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
GList* DefaultRepresentation<Set,Group,GList,GroupContainers,SetContainers>::operator[](const int& i) const
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{
        return gLists[i];
}




template <
    class Set, 
    class Group, 
    class GList,
    class GroupContainers,
    class SetContainers
>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
long DefaultRepresentation<Set,Group,GList,GroupContainers,SetContainers>::getGListIndex(Set& r)
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{

        if (gList_count==0 || r<gListRepresentatives[0])
        {
                insertGList(r, 0);
                return 0;
        }

        if (gListRepresentatives[gList_count-1]<r)
        {
                long lpos = gList_count;
                insertGList(r, gList_count);
                return lpos;
        }

        long left = 0;
        long right = gList_count-1;
        bool found = false;
        int mid = 0;

        while (left<=right && !found)
        {

                mid = (left+right)/2;

                Set cmp = gListRepresentatives[mid];                    

                if (r<cmp)
                        right = mid-1;
                else if (r==cmp)
                        found = true;
                else // M.a.W. : (cr>cmp)
                        left = mid+1;

                        
        }

        if (found)
        {
                return mid;
        }
        
        if (gListRepresentatives[mid]<r)
                mid++;

        insertGList(r, mid);

        return mid;

}



template <
    class Set, 
    class Group, 
    class GList,
    class GroupContainers,
    class SetContainers
>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
long DefaultRepresentation<Set,Group,GList,GroupContainers,SetContainers>::size() const
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{
        return gList_count;
}



template <
    class Set, 
    class Group, 
    class GList,
    class GroupContainers,
    class SetContainers
>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
void DefaultRepresentation<Set,Group,GList,GroupContainers,SetContainers>::insertGList(const Set& r, long pos)
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{
        
        if (gList_count>=(current_size-1))
                expandGLists();

        for (long i=gList_count; i>pos; i--)
        {
                gLists[i] = gLists[i-1];
                gListRepresentatives[i] = gListRepresentatives[i-1];
        };

        gList_count++;
        gListRepresentatives[pos] = r;
        gLists[pos] = new GList(filecounter++);

};




template <
    class Set, 
    class Group, 
    class GList,
    class GroupContainers,
    class SetContainers
>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
DefaultRepresentation<Set,Group,GList,GroupContainers,SetContainers>::~DefaultRepresentation()
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{
        clear();
}


template <
    class Set, 
    class Group, 
    class GList,
    class GroupContainers,
    class SetContainers
>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
DefaultRepresentation<Set,Group,GList,GroupContainers,SetContainers>::iterator
    DefaultRepresentation<Set,Group,GList,GroupContainers,SetContainers>::begin()
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{
        return iterator(this,&(gListRepresentatives[0]));
}

template <
    class Set, 
    class Group, 
    class GList,
    class GroupContainers,
    class SetContainers
>
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
DefaultRepresentation<Set,Group,GList,GroupContainers,SetContainers>::iterator
    DefaultRepresentation<Set,Group,GList,GroupContainers,SetContainers>::end()
// /////////////////////////////////////////////////////////////////////////////////////////////////////////////
{
        return iterator(this,&(gListRepresentatives[gList_count]));
}


}
#endif

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