The GroupIndex Template Library

---

CompressedGInvertedList.h

#pragma warning( disable : 4786 )        
#include "compression.h"
#ifndef GROUPINDEX
#include "GroupIndex.h"
#endif

namespace groupindex
{

template<class Group>


class CompressedGInvertedList : public GInvertedList<Group>
{
 

public:


        unsigned long byte_size; // Anzahl bytes, die von den komprimierten ListTupeln belegt wird

        Group g_factor;

        CompressedGInvertedList<Group>()
        {
                elements = NULL;

                insertion_file_name[0] = '\0';
                element_count = 0;

                mode = MODE_CREATE_INDEX;

                //g_factor.one();

        }
        
        
        ListTupel<Group> operator[](int index)
        // VORSICHT: Vor Aufruf dieses Operators müssen die Variablen
        // mystream, my_fileoffset sowie gsize mit initFileRead() gesetzt
        // werden!
        {       

                ListTupel<Group> lt = ListTupel<Group>();

                if (mode!=MODE_SEARCH)
                        return lt;
                
                if (elements==NULL)
                        readElements();

                lt = elements[index];

                return lt;

        };

        void mult(Group g)
        {

                // Multiplikation wird "lazy" ausgeführt, d.h. dann, wenn
                // sie tatsächlich gebraucht wird.

                g_factor = g;

        }

        unsigned long size()
        {
                return element_count;
        }

        long byteSize()
        {
                return sizeof(ListTupel<Group>)*size();
        }
        
        bool writeToFile(FILE* stream)
        // Sortiere die Tupel dieser Liste und schreibe diese in die Datei stream
        // Diese Methode muß _genau_ this.byteSize() viele Bytes in die Datei stream schreiben.
        {

                if (mode!=MODE_CREATE_INDEX)
                        return false;

                if (element_count<=0)
                        return true;

                FILE* insertion_stream;
                insertion_stream = fopen(insertion_file_name,"rb");
                if (insertion_stream == NULL)
                        return false;

                // file-pointer an Anfang setzen
                rewind(insertion_stream);

                gsize = sizeof(ListTupel<Group>);
                
                ListTupel<Group>* elements = new ListTupel<Group>[element_count];
                
                // Alle Datensätze aus File in array lesen
                for (int i=0; i<element_count; i++)
                {
                        fread(&(elements[i]), gsize, 1, insertion_stream);
                        if (ferror(insertion_stream)!=0)
                                return false;
                }

                fclose(insertion_stream);

                // array sortieren 
                heapsort< ListTupel<Group> >(elements,element_count);

                int bitPos = 31;
                int longPos = 0;

                // Platzbedarf der komprimierten G-Liste ermitteln 
                // und doppelte Listeneinträge 'rausschmeißen
                unsigned long bitSize = 0;
                unsigned long maxSize;
                unsigned long unique_element_count = element_count;
                for (i=0; i<element_count; i++)
                {
                        if ((elements[i]==elements[i-1]))
                                // Element doppelt vorhanden -> 'raus damit!
                                unique_element_count--;
                        else
                        {
                                unsigned long isize = deltaSize(&(elements[i].i),sizeof(int));
                                unsigned long gsize = deltaSize(&(elements[i].g),sizeof(Group));
                                bitSize += isize;
                                bitSize += gsize;
                                if (isize>maxSize)
                                        maxSize = isize;
                                if (gsize>maxSize)
                                        maxSize = isize;
                        }
                }
                
                // Puffer für komprimierte G-Liste reservieren
                unsigned long byte_size = (bitSize+31)/8;
                void* buffer = malloc(byte_size);

                
                deltaEncode(&(elements[0].i),sizeof(int),buffer,longPos,bitPos);
                deltaEncode(&(elements[0].g),sizeof(Group),buffer,longPos,bitPos);
                // G-Liste komprimieren
                for (i=1; i<element_count; i++)
                {
                        if (!(elements[i]==elements[i-1]))
                        {
                                deltaEncode(&(elements[i].i),sizeof(int),buffer,longPos,bitPos);
                                deltaEncode(&(elements[i].g),sizeof(Group),buffer,longPos,bitPos);
                        }
                };

                // komprimierte G-Liste wegschreiben

                fwrite(&unique_element_count,sizeof(unsigned long),1,stream);

                unsigned long lpos = longPos+1;
                fwrite(&byte_size,sizeof(unsigned long),1,stream);

                fwrite(buffer,1,byte_size,stream);

                // Speicher freigeben
                delete[] elements;
                free(buffer);

                // Speicher freigeben
                remove(insertion_file_name);

                return true;
                
        }
        
        void initFileRead(FILE* stream)
        {

                my_fileoffset = ftell(stream);

                // Anzahl von ListTupeln in der aktuellen Liste ermitteln
                fread(&element_count, sizeof(long), 1, stream);

                // Größe der komprimierten Liste auslesen
                fread(&byte_size, sizeof(unsigned long), 1, stream);

                mystream = stream;

                mode = MODE_SEARCH;

                // stream-Position auf nächste Liste setzen
                fseek(stream, byte_size, SEEK_CUR);

        }
    
        bool readElements(ListTupel<Group>* list_buffer)
        // buffer muss groß genug sein, daß element_count viele ListTupel
        // Platz finden.
        {
                
                fseek(mystream, my_fileoffset + 2*sizeof(unsigned long), SEEK_SET);

                void* buffer;
                buffer = malloc(byte_size);

                long read_cnt = fread(buffer, 1, byte_size, mystream);
                if (read_cnt < byte_size)
                {
                        return false;
                }

                int longPos = 0;
                int bitPos = 31;

                for (int i=0; i<element_count; i++)
                {
                        if (deltaDecode(buffer, (void*)&(list_buffer[i].i), longPos, bitPos)==0)
                                list_buffer[i].i = 0;
                        if (deltaDecode(buffer, (void*)&(list_buffer[i].g), longPos, bitPos)==0)
                                zeroes(&(list_buffer[i].g),sizeof(Group));
                        list_buffer[i].g.mult(g_factor);
                }


                free(buffer);

                return true;

        }

        bool readElements()
        {
                if (elements!=NULL)
                        return true;

                elements = new ListTupel<Group>[element_count];
                return readElements(elements);
        }
        
        void intersect(ResultList<Group, CompressedGInvertedList<Group> >* set2)
        {
                if (elements==NULL)
                        readElements();

                // Für set2->elements ist sicher gestellt, daß 
                set2->readToBuffer(set2->elements);

                ListTupel<Group>* elements2 = set2->elements;

                int insert_position = 0;

                for (int i=0; i < element_count; i++)
                {
                        
                        // Binärsuche nach elements1[i] in elements2
                        ListTupel<Group> current = elements[i];

                        Group g_m_2_inv = set2->g_m;
                        g_m_2_inv.invert();
                        
                        ListTupel<Group> l1 = elements[i]; 
                        
                        // folgende Multiplikation findet nun in readelements statt
                        //l1.g.mult(g_factor);
                        // Diese Elemente sind bereits mit dem g_m inversen multipliziert (-> siehe (***) )

                        int left = 0;
                        int right = set2->size();
                        bool found = false;
                        int mid = 0;

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

                                ListTupel<Group> cmp = elements2[mid];                  

                                // ACHTUNG: mit dieser Operation funktioniert's nur, wenn die
                                // Gruppenoperation Ordnungserhaltend ist.
                                cmp.g.mult(g_m_2_inv);
                
                                if (l1.i==cmp.i && l1.g.isSimilar(cmp.g))
                                        found = true;
                                else if (l1<cmp)
                                left = mid+1;
                                        else // (current>elements2[mid])
                                right = mid-1;
                        }


                        if (found)
                        {
                                // elements[i] wurde in elements2 gefunden und gehört deshalb in die Ergebnismenge!
                                elements[insert_position] = elements[i];
                                insert_position++;
                        }

                }

                element_count = insert_position;

        };


        ~CompressedGInvertedList<Group>()
        {

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

                elements = NULL;
        }

};

}

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