The GroupIndex Template Library

---

IntervalIntersectionGList.h

#ifndef DEF_INTERVALINTERSECTIONGLIST
#define DEF_INTERVALINTERSECTIONGLIST

#pragma warning( once : 4786 )        

#include "compression.h"
#include "GInvertedList.h"

#ifdef list
#undef list
#endif

#include <limits>
#include "util.h"

#include "../avlTree/avlTree.h"         
#include "../ekdTree/dynEkdTree.h"

#define AREA_SEARCH
//#define BIN_SEARCH
//#define LINEAR_SEARCH

namespace groupindex
{

/***************************************************************************************
 * class Interval (Interface)                                                                                                          *
 ***************************************************************************************/
template<class Group, class numeric, int Dim>
class Interval : public ListTupel<Group>
{
        
public:
        
        static const unsigned int longsize;

        numeric cmin[Dim];
        numeric cmax[Dim];

    int matched;

        Interval<Group,numeric,Dim>& operator = (const Interval<Group,numeric,Dim>& intv);

        bool operator < (Interval<Group, numeric, Dim> &i2) const;

        bool operator==(Interval<Group, numeric, Dim > &i2) const;

    friend std::ofstream& operator<<(std::ofstream& ofs, Interval<Group, numeric, Dim > i);

        bool operator > (const Interval<Group,numeric,Dim >& ic2) const;

        Interval<Group, numeric, Dim >();

        ~Interval();

        Interval<Group, numeric, Dim >(ListTupel<Group> mylt);

        Interval<Group, numeric, Dim >(Group myg);

        Interval<Group, numeric, Dim >(Group myg, int newmatched);

        Interval<Group, numeric, Dim >(FILE* stream);

    Interval<Group, numeric, Dim>(std::ifstream& ifs);
    Interval<Group, numeric, Dim>(std::fstream& ifs);

        inline unsigned long indexSize();
        
        inline void writeToFile(FILE* stream);
        
        bool expand(Group &x);

        inline numeric operator[](int i);

        //friend ListTupel<Group>& operator=(ListTupel<Group>& lt, const Interval<Group,numeric,Dim>& i);
        operator ListTupel<Group>&();
};



/* **************************************************************************************
 * class treeSaver      (Interface)                                                                                                    *
 ***************************************************************************************/
template <class treetype>
class treeSaver
{
        public:

                treeSaver();
                treeSaver(treetype* tree, int pos);
                ~treeSaver();
                inline treetype* getTree();
                inline int getFileNum();
                inline bool operator < (treeSaver& compare);
                inline bool operator == (treeSaver& compare);
                operator = (treeSaver& setto);

        friend std::ofstream& operator<<(std::ofstream& o, treeSaver<treetype>& ts);

        private:
                
                treetype** m_tree;
                int                filenum;

};

template <class treetype>
std::ofstream& operator<<(std::ofstream& o, treeSaver<treetype>& ts)
{
    o<<**ts.m_tree;
}

 

template<class Group, class numeric, int Dim, class numeric_writer = double_writer>
/***************************************************************************************
 * class IntervalIntersectionGList (GInvertedList) (Interface)                                         *
 ***************************************************************************************/
class IntervalIntersectionGList : public GInvertedList<Group>
{
 


public:

    typedef dynEkdTree<Interval<Group, numeric, Dim >, Dim, numeric, numeric_writer> tpTREE;
    typedef avlTree<treeSaver<tpTREE> > avl_tree_type;
        IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >(const IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >& glist);

        IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >();

        IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >(long id);

        IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >(std::ifstream& ifs);

        IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >(std::fstream& ifs);

        virtual ~IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >();


    
    // ////////////////////////////////////////////////////////////////////
    // /////////// Iterator Anfang ////////////////////////////////////////
    // ////////////////////////////////////////////////////////////////////
    class iterator
        {
                protected:

                        avlTree<treeSaver<tpTREE> >* m_tree_tree;

                        tpTREE* m_tree;
        
                        typename dynEkdTree<Interval<Group, numeric, Dim>, Dim, numeric, numeric_writer>::iterator m_iterator;

                        int m_current_file;
                        int m_hitsNecessary;

                        bool m_at_end;

            Group m_g_factor;

            Interval<Group, numeric, Dim> m_current_interval;

                        std::list<IntervalIntersectionGList*>* m_merge_list;

            // "Simulation" des Vereinigens von Listen mittels MergeList:
                        std::list<IntervalIntersectionGList*>::iterator m_merge_iterate;
                        std::list<IntervalIntersectionGList*>::iterator m_merge_end;

                public:

            // ////////////////////////////////////////////////////////////////////
                        iterator()
            // ////////////////////////////////////////////////////////////////////
            {
                    m_tree_tree = NULL;
                    m_tree = NULL;
                    m_iterator = NULL;
                    m_current_file = 0;
                    m_hitsNecessary = 0;
                    m_at_end = false;
            }

            // ////////////////////////////////////////////////////////////////////
                        iterator(const iterator& copyFrom)
            // ////////////////////////////////////////////////////////////////////
            {
                    m_tree_tree = copyFrom.m_tree_tree;
                    m_tree = copyFrom.m_tree;
                    m_iterator = copyFrom.m_iterator;
                    m_current_file = copyFrom.m_current_file;
                    m_hitsNecessary = copyFrom.m_hitsNecessary;
                    m_at_end = copyFrom.m_at_end;
            }

            // ////////////////////////////////////////////////////////////////////
                        iterator(avlTree<treeSaver<tpTREE> >& from_tree, bool begin_or_end, int hitsNeeded)
            // ////////////////////////////////////////////////////////////////////
            {
                    m_hitsNecessary = hitsNeeded;

                    m_tree_tree = &from_tree;

                    if (begin_or_end)
                    {
                            m_at_end = false;
                            m_tree = m_tree_tree->getFirst()->getTree();
                            m_current_file = m_tree_tree->getFirst()->getFileNum();
                            m_iterator = m_tree->begin();

                            // Jetzt noch den ersten wirklichen Treffer suchen:
                            if (*m_iterator)
                                    if ((*m_iterator)->matched < m_hitsNecessary)
                                            (*this)++;
                    }
                    else
                            m_at_end = true;
            }


            // ////////////////////////////////////////////////////////////////////
                        iterator(avlTree<treeSaver<tpTREE> >& from_tree, bool begin_or_end, int hitsNeeded, 
                                std::list<IntervalIntersectionGList*>* mergelist, Group& g_factor)
            // ////////////////////////////////////////////////////////////////////
            {
                    m_hitsNecessary = hitsNeeded;

                    m_merge_list = mergelist;

                    m_merge_iterate = mergelist->begin();
                    m_merge_end         = mergelist->end();

                    m_tree_tree = &from_tree;

                m_g_factor = g_factor;

                    if (begin_or_end)
                    {
                            m_at_end = false;
                            m_tree = m_tree_tree->getFirst()->getTree();
                            m_current_file = m_tree_tree->getFirst()->getFileNum();
                                        tpTREE::iterator it(m_tree->begin());
                            //m_iterator = m_tree->begin();
                                        m_iterator = it;

                            // Jetzt noch den ersten wirklichen Treffer suchen:
                            if (*m_iterator)
                                    if ((*m_iterator)->matched < m_hitsNecessary)
                                            (*this)++;
                    }
                    else
                            m_at_end = true;
            }


            // ////////////////////////////////////////////////////////////////////
                        inline const Interval<Group, numeric, Dim>& operator *()
            // ////////////////////////////////////////////////////////////////////
                        {
                if (m_at_end)
                    throw IndexingException(IndexingException::END_ITERATOR_DEREFERENCED);
                m_current_interval = *(*m_iterator);
                m_current_interval.g *= m_g_factor;
                m_current_interval .i = m_current_file;
                                return m_current_interval;
                        }


            // ////////////////////////////////////////////////////////////////////
                        inline bool operator ==(iterator& compare)
            // ////////////////////////////////////////////////////////////////////
            {
                    if (m_at_end)
                            return compare.m_at_end;
                    if (compare.m_at_end)
                            return m_at_end;
                    else
                            //return (m_tree_tree == m_tree_tree) && (m_tree == m_tree)
                                //    && (m_iterator == m_iterator);
                    // ÄNDERUNG -am 07.12.
                            return !compare.m_at_end && (m_tree_tree == compare.m_tree_tree) && (m_tree == compare.m_tree)
                                    && (m_iterator == compare.m_iterator);
            }



            // ////////////////////////////////////////////////////////////////////
                        inline bool operator !=(iterator& compare)
            // ////////////////////////////////////////////////////////////////////
                        {
                                return !(*this==compare);
                        }

            // ////////////////////////////////////////////////////////////////////
                        iterator &operator ++()
            // ////////////////////////////////////////////////////////////////////
            {
                    m_iterator++;
                    if (!*(m_iterator))
                    {
                            treeSaver<tpTREE>* next = m_tree_tree->getNext();

                            // Hier nur solche Elemente erlauben, die auch Treffer sind.
                            if (next)
                            {
                                    m_tree = next->getTree();
                                    m_current_file = next->getFileNum();
                                    m_iterator = m_tree->begin();
                            }
                            else
                                    m_tree = NULL;
                    }

/*                  if (*m_iterator)
                    {
                            if ((*m_iterator)->matched>=m_hitsNecessary)
                                    return *this;
                            else
                                    return (*this)++;
                    }
                    else 
                    {
                            // An dieser Stelle wird die Vereinigung von Listen "simuliert":
                            MergeListGetNext();

                            if (!*(m_iterator))
                                    m_at_end = true;

                            return *this;
                    }*/
                                // Umbau des rekursiven Aufrufs:
                                while (*m_iterator && (*m_iterator)->matched<m_hitsNecessary)
                                {
                                        m_iterator++;
                                        if (!*(m_iterator))
                                        {
                                                treeSaver<tpTREE>* next = m_tree_tree->getNext();

                                                // Hier nur solche Elemente erlauben, die auch Treffer sind.
                                                if (next)
                                                {
                                                        m_tree = next->getTree();
                                                        m_current_file = next->getFileNum();
                                                        m_iterator = m_tree->begin();
                                                }
                                                else
                                                        m_tree = NULL;
                                        }
                    }

                    if (*m_iterator)
                            return *this;
                    else 
                    {
                            // An dieser Stelle wird die Vereinigung von Listen "simuliert":
                            MergeListGetNext();

                            if (!*(m_iterator))
                                    m_at_end = true;

                            return *this;
                    }
            }
                        
            // ////////////////////////////////////////////////////////////////////
                        iterator &operator ++(int)
            // ////////////////////////////////////////////////////////////////////
            {
                    ++m_iterator;
                    if (!*(m_iterator))
                    {
                            treeSaver<tpTREE>* next = m_tree_tree->getNext();

                            if (next)
                            {
                                    m_tree = next->getTree();
                                    m_current_file = next->getFileNum();
                                    m_iterator = m_tree->begin();
                            }
                            else
                                    m_tree = NULL;
                    }

                    // Hier nur solche Elemente erlauben, die auch Treffer sind:
/*                  if (*m_iterator)
                    {
                            if ((*m_iterator)->matched>=m_hitsNecessary)
                                    return *this;
                            else
                                    return (*this)++;
                    }
                    else 
                    {
                            // An dieser Stelle wird die Vereinigung von Listen "simuliert":
                            MergeListGetNext();

                            if (!*(m_iterator))
                                    m_at_end = true;

                            return *this;
                    }*/
                                // Umbau des rekursiven Aufrufs:
                                while (*m_iterator && (*m_iterator)->matched<m_hitsNecessary)
                                {
                                        m_iterator++;
                                        if (!*(m_iterator))
                                        {
                                                treeSaver<tpTREE>* next = m_tree_tree->getNext();

                                                // Hier nur solche Elemente erlauben, die auch Treffer sind.
                                                if (next)
                                                {
                                                        m_tree = next->getTree();
                                                        m_current_file = next->getFileNum();
                                                        m_iterator = m_tree->begin();
                                                }
                                                else
                                                        m_tree = NULL;
                                        }
                    }

                    if (*m_iterator)
                            return *this;
                    else 
                    {
                            // An dieser Stelle wird die Vereinigung von Listen "simuliert":
                            MergeListGetNext();

                            if (!*(m_iterator))
                                    m_at_end = true;

                            return *this;
                    }
            }

            // ////////////////////////////////////////////////////////////////////
                        inline int getCurrentFile()
            // ////////////////////////////////////////////////////////////////////
            {
                    return m_current_file;
            }



       
        public:
            // ////////////////////////////////////////////////////////////////////
            void MergeListGetNext()
            // ////////////////////////////////////////////////////////////////////
            {
                    if (m_merge_iterate != m_merge_end)
                    {
                            m_merge_iterate++;

                            if (m_merge_iterate != m_merge_end)
                            {
                                    m_tree_tree = &((*m_merge_iterate)->treeList);

                                    m_tree = m_tree_tree->getFirst()->getTree();
                                    m_current_file = m_tree_tree->getFirst()->getFileNum();
                                    m_iterator = m_tree->begin();

                                    // Jetzt noch den ersten wirklichen Treffer suchen:
                                    if (*m_iterator)
                                            if ((*m_iterator)->matched < m_hitsNecessary)
                                                    (*this)++;
                            }
                    }
            }


        };
        // /////////// Iterator Ende   ////////////////////////////////////////

    // ////////////////////////////////////////////////////////////////////
    // /////////// pure_iterator Anfang ////////////////////////////////////////
    // ////////////////////////////////////////////////////////////////////
    class pure_iterator : public iterator
        {
    public:

            pure_iterator() 
                : iterator()
            {}

            pure_iterator(const pure_iterator& p_it) 
                : iterator(p_it)
            {}

                        pure_iterator(avlTree<treeSaver<tpTREE> >& from_tree, bool begin_or_end, int hitsNeeded)
                : iterator(from_tree, begin_or_end, hitsNeeded)
            {}

                        pure_iterator(avlTree<treeSaver<tpTREE> >& from_tree, bool begin_or_end, int hitsNeeded, 
                                std::list<IntervalIntersectionGList*>* mergelist, Group& g_factor)
                : iterator(from_tree, begin_or_end, hitsNeeded, mergelist, g_factor)
            {}

            // ////////////////////////////////////////////////////////////////////
                        inline const Interval<Group, numeric, Dim>& operator *()
            // ////////////////////////////////////////////////////////////////////
                        {
                if (m_at_end)
                    throw IndexingException(IndexingException::END_ITERATOR_DEREFERENCED);
                m_current_interval = *(*m_iterator);
                m_current_interval .i = m_current_file;
                                return m_current_interval;
                        }


        };
        // /////////// Pure Iterator Ende   ////////////////////////////////////////



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

        inline pure_iterator pure_begin();
        inline pure_iterator pure_begin(bool);

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

        inline pure_iterator pure_end();
    inline pure_iterator pure_end(bool);

        inline int size() const;
        
        inline friend bool operator < (const IntervalIntersectionGList<Group, numeric, Dim, numeric_writer>& sl1, const IntervalIntersectionGList<Group, numeric, Dim, numeric_writer>& sl2);
        
        inline friend bool operator > (const IntervalIntersectionGList<Group, numeric, Dim, numeric_writer>& sl1, const IntervalIntersectionGList<Group, numeric, Dim, numeric_writer>& sl2);
        
        friend std::ofstream& operator <<(std::ofstream& o, IntervalIntersectionGList<Group, numeric, Dim, numeric_writer>& l);

    // geerbt von GInvertedList
        //void insert(Group& g, int i);

        void merge(IntervalIntersectionGList<Group, numeric, Dim, numeric_writer>& set2);

    void setCredit(int credit);

        inline void intersect(IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >& set2);

        void intersect(IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >& set2, int credit);

        inline void setHeapStream(std::fstream& hps);

protected:

        Group g_factor[maxStabSize];
        int g_factor_stabSize;

        int intersects;

        int intervals_matched;

        int m_credit;

        unsigned long interval_count;
        
        numeric min_dist;

        numeric epsilon;

        
        unsigned long tree_count;

        Interval<Group, numeric, Dim >* intervals;

public:
        //ekdTree< Interval<Group, numeric, Dim > ,Dim, numeric >** treeList;
        avlTree<treeSaver<tpTREE> > treeList;

protected:
        numeric* ranking;
        
        numeric_writer freadInit;


        numeric distance(numeric* g1, numeric* g2);
        
        numeric distance(numeric* g1, Group g2);
        
        numeric distance(Group g1, Group g2);

        void writeToFile(std::ofstream& ofs);
        
        ListTupel<Group> operator[](int index);

        /*virtual bool readIntervals(Interval<Group,Dim,L>* buffer)
        // buffer muss groß genug sein, daß element_count viele ListTupel
        // Platz finden.
        {
        }*/

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

        virtual void readIntervals();

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


        void deleteFile(int fileindex);
        
        bool interval_range_search(Group x, int left,int right, int &hit_pos);

        void printElements();
        
    void pure_printElements();


//      int rangeSearch(tpTREE* search_tree, Interval<Group, numeric, Dim >** result);
        int rangeSearch(Group& g_1, tpTREE* search_tree, int fileNum, Interval<Group, numeric, Dim >** result);
        std::list<IntervalIntersectionGList*> m_merged_with;
};

/***************************************************************************************
 * class Interval (Implementierung)                                                                                                    *
 ***************************************************************************************/


/* 
// /////////////////////////////////////////////////////////////////////////////////////
ListTupel<Group>& operator=(ListTupel<Group>& lt, const Interval<Group,numeric,Dim>& i)
// /////////////////////////////////////////////////////////////////////////////////////
{
        lt = i.lt;
        return lt;
}*/
 
template<class Group, class numeric, int Dim>
Interval<Group,numeric,Dim>::operator ListTupel<Group>&()
{
        return lt;
}
 
 
template<class Group, class numeric, int Dim>
// /////////////////////////////////////////////////////////////////////////////////////
Interval<Group,numeric,Dim>& Interval<Group,numeric,Dim>::operator = (const Interval<Group,numeric,Dim>& intv)
// /////////////////////////////////////////////////////////////////////////////////////
{
        this->g = intv.g;
        this->i = intv.i;
        for (int i=0; i<Dim; i++)
        {
                this->cmax[i] = intv.cmax[i];
                this->cmin[i] = intv.cmin[i];
        }
        this->matched = intv.matched;
    this->credit = intv.credit;
        //GInvertedList<Group> new_gl = GInvertedList<Group>(glist);
        //*this = new_gl;
        return (*this);
}

template<class Group, class numeric, int Dim>
// /////////////////////////////////////////////////////////////////////////////////////
bool Interval<Group,numeric,Dim>::operator < (Interval<Group, numeric, Dim> &i2) const
// /////////////////////////////////////////////////////////////////////////////////////
{
        if (lt.i<i2.lt.i)
                return true;
        return false;
}       

template<class Group, class numeric, int Dim>
// /////////////////////////////////////////////////////////////////////////////////////
bool Interval<Group,numeric,Dim>::operator==(Interval<Group, numeric, Dim > &i2) const
// /////////////////////////////////////////////////////////////////////////////////////
{
        if (lt.i!=i2.lt.i)
                return false;
        for (int i=0; i<Dim; i++)
                if (lt[i]!=i2.lt.g[i])
                        return false;

        return true;
}       

template<class Group, class numeric, int Dim>
// /////////////////////////////////////////////////////////////////////////////////////
std::ofstream& operator<<(std::ofstream& ofs, Interval<Group, numeric, Dim > i)
// /////////////////////////////////////////////////////////////////////////////////////
{
    //ofs<<i.lt.g;
    ofs<<(ListTupel<Group>)i;
    return ofs;
}


template<class Group, class numeric, int Dim>
// /////////////////////////////////////////////////////////////////////////////////////
bool Interval<Group,numeric,Dim>::operator > (const Interval<Group,numeric,Dim >& ic2) const
// /////////////////////////////////////////////////////////////////////////////////////
{
        if (i>ic2.i)
                return false;
        return true;
}

template<class Group, class numeric, int Dim>
// /////////////////////////////////////////////////////////////////////////////////////
Interval<Group,numeric,Dim>::Interval()
// /////////////////////////////////////////////////////////////////////////////////////
{
        matched = 0;
}

template<class Group, class numeric, int Dim>
// /////////////////////////////////////////////////////////////////////////////////////
Interval<Group,numeric,Dim>::~Interval()
// /////////////////////////////////////////////////////////////////////////////////////
{
        matched = 0;
}

template<class Group, class numeric, int Dim>
// /////////////////////////////////////////////////////////////////////////////////////
Interval<Group,numeric,Dim>::Interval<Group, numeric, Dim >(ListTupel<Group> mylt)
// /////////////////////////////////////////////////////////////////////////////////////
{
        matched = 0;
        g = mylt.g;
        i= mylt.i;

        for (int i=0; i<Dim; i++)
        {
                numeric g_l = g[i];
                cmin[i] = g_l;// - Group::epsilon;
                cmax[i] = g_l;// + Group::epsilon;
        }

}

template<class Group, class numeric, int Dim>
// /////////////////////////////////////////////////////////////////////////////////////
Interval<Group,numeric,Dim>::Interval(Group myg)
// /////////////////////////////////////////////////////////////////////////////////////
{
        matched = 0;
        lt.g = myg;

        for (int i=0; i<Dim; i++)
        {
                numeric g_l = g[i];
                cmin[i] = g_l;// - Group::epsilon;
                cmax[i] = g_l;// + Group::epsilon;
        }

}

template<class Group, class numeric, int Dim>
// /////////////////////////////////////////////////////////////////////////////////////
Interval<Group,numeric,Dim>::Interval<Group, numeric, Dim >(Group myg, int newmatched)
// /////////////////////////////////////////////////////////////////////////////////////
{
        matched = newmatched;
        g = myg;

        for (int i=0; i<Dim; i++)
        {
                numeric g_l = myg[i];
                cmin[i] = g_l;// - Group::epsilon;
                cmax[i] = g_l;// + Group::epsilon;
        }

}

template<class Group, class numeric, int Dim>
// /////////////////////////////////////////////////////////////////////////////////////
Interval<Group,numeric,Dim>::Interval(FILE* stream)
// /////////////////////////////////////////////////////////////////////////////////////
{
        lt.g.readFromFile(stream);
        matched = 0;

        for (int i=0; i<Dim; i++)
        {
                numeric g_l = lt.g[i];
                cmin[i] = g_l;// - Group::epsilon;
                cmax[i] = g_l;// + Group::epsilon;
        }

}

template<class Group, class numeric, int Dim>
// /////////////////////////////////////////////////////////////////////////////////////
Interval<Group, numeric, Dim>::Interval(std::ifstream& ifs)
// /////////////////////////////////////////////////////////////////////////////////////
{
        ifs >> (*this);
        matched = 0;

        for (int i=0; i<Dim; i++)
        {
                numeric g_l = g[i];
                cmin[i] = g_l;// - Group::epsilon;
                cmax[i] = g_l;// + Group::epsilon;
        }
}

template<class Group, class numeric, int Dim>
// /////////////////////////////////////////////////////////////////////////////////////
Interval<Group, numeric, Dim>::Interval(std::fstream& ifs)
// /////////////////////////////////////////////////////////////////////////////////////
{
        ifs >> (*this);
        matched = 0;

        for (int i=0; i<Dim; i++)
        {
                numeric g_l = g[i];
                cmin[i] = g_l;// - Group::epsilon;
                cmax[i] = g_l;// + Group::epsilon;
        }
}

template<class Group, class numeric, int Dim>
// /////////////////////////////////////////////////////////////////////////////////////
inline unsigned long Interval<Group,numeric,Dim>::indexSize()
// /////////////////////////////////////////////////////////////////////////////////////
{
        return g.indexSize() + sizeof(long);
}

template<class Group, class numeric, int Dim>
// /////////////////////////////////////////////////////////////////////////////////////
inline void Interval<Group,numeric,Dim>::writeToFile(FILE* stream)
// /////////////////////////////////////////////////////////////////////////////////////
{
        lt.g.writeToFile(stream);
}

template<class Group, class numeric, int Dim>
// /////////////////////////////////////////////////////////////////////////////////////
bool Interval<Group,numeric,Dim>::expand(Group &x)
// /////////////////////////////////////////////////////////////////////////////////////
{

        int i;

        //for (i=0; i<Dim; i++)
        //{
        //      if (abs(cmax[i]-x[i]) >= Group::epsilon)
        //              return false;
        //}
        for (i=0; i<Dim; i++)
        {
                numeric g_i = x[i];
                cmin[i] = cmin[i] < g_i ? cmin[i] : g_i;
                cmax[i] = cmax[i] > g_i ? cmax[i] : g_i;
        }

        return true;

}

template<class Group, class numeric, int Dim>
// /////////////////////////////////////////////////////////////////////////////////////
inline numeric Interval<Group,numeric,Dim>::operator[](int i) 
// /////////////////////////////////////////////////////////////////////////////////////
{
        return g[i];
}


/***************************************************************************************
 * class treeSaver      (Implementierung)                                                                                      *
 ***************************************************************************************/

template <class treetype>
// /////////////////////////////////////////////////////////////////////////////////////
treeSaver<treetype>::treeSaver()
// /////////////////////////////////////////////////////////////////////////////////////
{
        m_tree=NULL;
        filenum=0;
}

template <class treetype>
// /////////////////////////////////////////////////////////////////////////////////////
treeSaver<treetype>::treeSaver(treetype* tree, int pos)
// /////////////////////////////////////////////////////////////////////////////////////
{
        m_tree  = new treetype*;
        *m_tree  = tree;
        filenum = pos;
}

template <class treetype>
// /////////////////////////////////////////////////////////////////////////////////////
inline treeSaver<treetype>::~treeSaver()
// /////////////////////////////////////////////////////////////////////////////////////
{
        if (m_tree)
    {
        delete m_tree;
        m_tree = NULL;
    }
}

template <class treetype>
// /////////////////////////////////////////////////////////////////////////////////////
inline treetype* treeSaver<treetype>::getTree()
// /////////////////////////////////////////////////////////////////////////////////////
{
        return *m_tree;
}

template <class treetype>
// /////////////////////////////////////////////////////////////////////////////////////
inline int treeSaver<treetype>::getFileNum()
// /////////////////////////////////////////////////////////////////////////////////////
{
        return filenum;
}

template <class treetype>
// /////////////////////////////////////////////////////////////////////////////////////
inline bool treeSaver<treetype>::operator < (treeSaver& compare)
// /////////////////////////////////////////////////////////////////////////////////////
{
        return filenum < compare.filenum;
}

template <class treetype>
// /////////////////////////////////////////////////////////////////////////////////////
inline bool treeSaver<treetype>::operator == (treeSaver& compare)
// /////////////////////////////////////////////////////////////////////////////////////
{
        return filenum == compare.filenum;
}

template <class treetype>
// /////////////////////////////////////////////////////////////////////////////////////
treeSaver<treetype>::operator = (treeSaver& setto)
// /////////////////////////////////////////////////////////////////////////////////////
{
        if (m_tree) delete m_tree;
        m_tree = new treetype*;

        *m_tree = *setto.m_tree;
        filenum = setto.filenum;
}


/***************************************************************************************
 * class IntervalIntersectionGList (GInvertedList) (Implementierung)                           *
 ***************************************************************************************/

template<class Group, class numeric, int Dim, class numeric_writer>
// /////////////////////////////////////////////////////////////////////////////////////
IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >(long id) : GInvertedList<Group>(id)
// ////////////////////////////////////////////////////////////////////////////////////
{
    ranking = NULL;
}

template<class Group, class numeric, int Dim, class numeric_writer>
// /////////////////////////////////////////////////////////////////////////////////////
IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::IntervalIntersectionGList(const IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >& glist) : GInvertedList<Group>(glist)
// /////////////////////////////////////////////////////////////////////////////////////
{
        ranking = NULL;
/*      m_stream = glist.mystream;
        strcpy(insertion_file_name,glist.insertion_file_name);
        my_fileoffset = glist.my_fileoffset;
        mode = glist.mode;

        epsilon = glist.epsilon;

        m_elements = NULL;*/
        intervals = NULL;

        interval_count = glist.interval_count;
        min_dist = glist.min_dist;
        tree_count = glist.tree_count;

        m_element_count = glist.m_element_count;
        intersects = 0;
        m_credit = glist.m_credit;
}

template<class Group, class numeric, int Dim, class numeric_writer>
// /////////////////////////////////////////////////////////////////////////////////////
IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::IntervalIntersectionGList() : GInvertedList<Group>()
// /////////////////////////////////////////////////////////////////////////////////////
{
        ranking = NULL;
        m_elements = NULL;
        intervals = NULL;

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

        mode = MODE_CREATE_INDEX;
        intersects = 0;

        tree_count = 0;
        m_credit = 0;
}

template<class Group, class numeric, int Dim, class numeric_writer>
// /////////////////////////////////////////////////////////////////////////////////////
IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::IntervalIntersectionGList(std::ifstream& ifs)
// /////////////////////////////////////////////////////////////////////////////////////
{

    ranking = NULL;

    ins_buffer_size = INS_BUFFER_SIZE;
    ins_buffer_pos = 0;
    insertion_buffer=NULL;
    
    initFileRead(ifs);
}

template<class Group, class numeric, int Dim, class numeric_writer>
// /////////////////////////////////////////////////////////////////////////////////////
IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::IntervalIntersectionGList(std::fstream& ifs)
// /////////////////////////////////////////////////////////////////////////////////////
{

    ranking = NULL;

    ins_buffer_size = INS_BUFFER_SIZE;
    ins_buffer_pos = 0;
    insertion_buffer=NULL;
    
    initFileRead(ifs);
}

template<class Group, class numeric, int Dim, class numeric_writer>
// /////////////////////////////////////////////////////////////////////////////////////
inline void IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::setHeapStream(std::fstream& hps)
// /////////////////////////////////////////////////////////////////////////////////////
{
}

template<class Group, class numeric, int Dim, class numeric_writer>
// /////////////////////////////////////////////////////////////////////////////////////
inline IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::iterator IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::begin()
// /////////////////////////////////////////////////////////////////////////////////////
{
    readIntervals();
        return iterator(treeList, true, intersects-m_credit, &m_merged_with, m_factor);
}

template<class Group, class numeric, int Dim, class numeric_writer>
// /////////////////////////////////////////////////////////////////////////////////////
inline IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::pure_iterator IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::pure_begin()
// /////////////////////////////////////////////////////////////////////////////////////
{
    readIntervals();
        return pure_iterator(treeList, true, intersects-m_credit, &m_merged_with, m_factor);
}

template<class Group, class numeric, int Dim, class numeric_writer>
// /////////////////////////////////////////////////////////////////////////////////////
inline IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::iterator IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::begin(bool)
// /////////////////////////////////////////////////////////////////////////////////////
{
        return begin();
}

template<class Group, class numeric, int Dim, class numeric_writer>
// /////////////////////////////////////////////////////////////////////////////////////
inline IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::pure_iterator IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::pure_begin(bool)
// /////////////////////////////////////////////////////////////////////////////////////
{
        return pure_begin();
}

template<class Group, class numeric, int Dim, class numeric_writer>
// /////////////////////////////////////////////////////////////////////////////////////
inline IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::iterator IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::end()
// /////////////////////////////////////////////////////////////////////////////////////
{
        return iterator(treeList, false, intersects-m_credit, &m_merged_with, m_factor);
}

template<class Group, class numeric, int Dim, class numeric_writer>
// /////////////////////////////////////////////////////////////////////////////////////
inline IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::iterator IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::end(bool dummy)
// /////////////////////////////////////////////////////////////////////////////////////
{
        return end();
}

template<class Group, class numeric, int Dim, class numeric_writer>
// /////////////////////////////////////////////////////////////////////////////////////
inline IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::pure_iterator IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::pure_end()
// /////////////////////////////////////////////////////////////////////////////////////
{
        return pure_iterator(treeList, false, intersects-m_credit, &m_merged_with, m_factor);
}

template<class Group, class numeric, int Dim, class numeric_writer>
// /////////////////////////////////////////////////////////////////////////////////////
inline IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::pure_iterator IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::pure_end(bool dummy)
// /////////////////////////////////////////////////////////////////////////////////////
{
        return pure_end();
}

template<class Group, class numeric, int Dim, class numeric_writer>
// /////////////////////////////////////////////////////////////////////////////////////
inline int IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::size() const
// /////////////////////////////////////////////////////////////////////////////////////
{
        return interval_count;
}

template<class Group, class numeric, int Dim, class numeric_writer>
// /////////////////////////////////////////////////////////////////////////////////////
numeric IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::distance(numeric* g1, numeric* g2)
// /////////////////////////////////////////////////////////////////////////////////////
{

        numeric max_dist = 0;
        numeric diff;

        for (int i=0; i<Dim; i++)
        {
                numeric l1 = g1[i];
                numeric l2 = g2[i];
                if (l2 < l1)
                        diff = l1-l2;
                else
                        diff = l2-l1;
                if (max_dist<diff)
                        max_dist = diff;
        }

        return max_dist;

}

template<class Group, class numeric, int Dim, class numeric_writer>
// /////////////////////////////////////////////////////////////////////////////////////
numeric IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::distance(numeric* g1, Group g2)
// /////////////////////////////////////////////////////////////////////////////////////
{

        numeric max_dist = 0;
        numeric diff;

        for (int i=0; i<Dim; i++)
        {
                numeric l1 = g1[i];
                numeric l2 = g2[i];
                if (l2 < l1)
                        diff = l1-l2;
                else
                        diff = l2-l1;
                if (max_dist<diff)
                        max_dist = diff;
        }

        return max_dist;

}

template<class Group, class numeric, int Dim, class numeric_writer>
// /////////////////////////////////////////////////////////////////////////////////////
numeric IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::distance(Group g1, Group g2)
// /////////////////////////////////////////////////////////////////////////////////////
{

        numeric max_dist = 0;
        numeric diff;

        for (int i=0; i<Dim; i++)
        {
                numeric l1 = g1[i];
                numeric l2 = g2[i];
                if (l2 < l1)
                        diff = l1-l2;
                else
                        diff = l2-l1;
                if (max_dist < diff)
                        max_dist = diff;
        }

        return max_dist;

}

template<class Group, class numeric, int Dim, class numeric_writer>
// /////////////////////////////////////////////////////////////////////////////////////
inline bool operator < (const IntervalIntersectionGList<Group, numeric, Dim, numeric_writer>& sl1, const IntervalIntersectionGList<Group, numeric, Dim, numeric_writer>& sl2)
// /////////////////////////////////////////////////////////////////////////////////////
{ 
        return sl1.size() < sl2.size();
}

template<class Group, class numeric, int Dim, class numeric_writer>
// /////////////////////////////////////////////////////////////////////////////////////
inline bool operator > (const IntervalIntersectionGList<Group, numeric, Dim, numeric_writer>& sl1, const IntervalIntersectionGList<Group, numeric, Dim, numeric_writer>& sl2)
// /////////////////////////////////////////////////////////////////////////////////////
{ 
        return sl1.size() > sl2.size();
}

template<class Group, class numeric, int Dim, class numeric_writer>
// /////////////////////////////////////////////////////////////////////////////////////
std::ofstream& operator << (std::ofstream& o, IntervalIntersectionGList<Group, numeric, Dim, numeric_writer>& l)
// /////////////////////////////////////////////////////////////////////////////////////
{
        l.writeToFile(o);
        return o;
}

template<class Group, class numeric, int Dim, class numeric_writer>
// /////////////////////////////////////////////////////////////////////////////////////
void IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::writeToFile(std::ofstream& ofs)
// /////////////////////////////////////////////////////////////////////////////////////
{

    // insertion_buffer Flushen
    if (insertion_buffer != NULL && ins_buffer_pos != 0)
    {

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

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

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

        buf_insertion_stream.close();

    }

        std::ifstream insertion_stream;
    insertion_stream.open(m_insertion_file_name,std::ios::binary);

    // Zunächst werden bereits indexierte Objekte verworfen, d.h, 
    // es werden nur Elemente indexiert, die seit dem letzten Schreibvorgang
    // mit insert() eingefügt wurden.
    m_element_count = m_new_element_count;
    // Später könnten hier zunächst die bereits indexierten Elemente 
    // (von denen es m_element_count viele gibt) noch zusätzlich eingelesen werden.

        if (!insertion_stream)
        {
                throw IndexingException(IndexingException::FILE_ERROR_OPEN);
                return;
        }

        // file-pointer an Anfang setzen
    insertion_stream.seekg(0,std::ios::beg);

        Interval<Group, numeric, Dim >* code_elements = new Interval<Group, numeric, Dim >[m_element_count];

        tree_count = 0;

        if (code_elements==NULL /*|| treeList==NULL*/)
        {
                throw IndexingException(IndexingException::OUT_OF_MEMORY);
        }
        
        // Alle Datensätze aus File in array lesen;
        // Platzbedarf aller ekdTrees aus der Liste berechnen
        for (int i=0; i<m_element_count; i++)
        {
                ListTupel<Group> lt;
                
                insertion_stream>>lt;

                if (!insertion_stream)
                {
                        throw IndexingException(IndexingException::FILE_ERROR_READ);
                        return;
                }

                //Interval<Group,Dim,L> ilc(lt);
                Interval<Group, numeric, Dim > ilc(lt);
                code_elements[i] = ilc;
        }

    insertion_stream.close();

        // array sortieren bzgl. Dateiindex (i.e. lt.i)
        heapsort< Interval<Group, numeric, Dim > >(code_elements,m_element_count);

    min_dist = FLT_MAX;
        
        tree_count = 0;
        int tree_start = 0;
        int tree_size = 0;
    int ins_pos = 1;

/*      for (i=1; i<m_element_count; i++)
        {
                // durch diese Abfrage wird verhindert, daß gleiche ListTupel mehrfach in
                // einer G-invertierten Liste gespeichert werden.
                numeric dist = distance(code_elements[i].g,code_elements[ins_pos-1].g);
                if ((code_elements[i].i != code_elements[ins_pos-1].i) 
                        || dist != 0)
                {
            code_elements[ins_pos] = code_elements[i];
            ins_pos++;
        }
    }
    m_element_count = ins_pos;*/

        for (i=1; i<m_element_count; i++)
        {
                if (i<m_element_count && code_elements[i].i!=code_elements[i-1].i)
                {
                        
                        // neuen ekdTree erzeugen
                        treeList.insert(treeSaver<tpTREE>
                                (new tpTREE(&(code_elements[tree_start]),i-tree_start), code_elements[i-1].i));
                        
                        tree_size += treeList.findData(treeSaver<tpTREE >(NULL, code_elements[i-1].i))->getTree()->indexSize() 
                                + sizeof (int);
                        
                        if (treeList.findData(treeSaver<tpTREE >(NULL, code_elements[i-1].i))->getTree()->epsilon<min_dist)
                                min_dist = treeList.findData(treeSaver<tpTREE >(NULL, code_elements[i-1].i))->getTree()->epsilon;

                        tree_count++;
                        tree_start = i;

                }
        }

        // ekdTree für die letzten Elemente der Liste erzeugen
        treeList.insert(*(new treeSaver<tpTREE>
                (new tpTREE(&(code_elements[tree_start]),i-tree_start), code_elements[i-1].i)));

        tree_size += treeList.findData(treeSaver<tpTREE >(NULL, code_elements[i-1].i))->getTree()->indexSize() + sizeof (int);
        if (treeList.findData(treeSaver<tpTREE >(NULL, code_elements[i-1].i))->getTree()->epsilon<min_dist)
                min_dist = treeList.findData(treeSaver<tpTREE >(NULL, code_elements[i-1].i))->getTree()->epsilon;
        tree_count++;



        //... zuerst die Minimaldistanz in die Datei schreiben
        // ACHTUNG: möglicher Konflikt bei LEDA/real; deshalb werden
        // ALLE Minimaldistanzen, gleich welchen Typs, als numeric_writer in die Datei geschrieben
    

        numeric_writer md;
        md = min_dist;
        md.write(ofs);
        //... und dann die Anzahl von ekd-Bäumen
        ofs.write((char*)&tree_count,sizeof(unsigned long));
        //... und dann die Anzahl von Einträgen insgesamt
        ofs.write((char*)&m_element_count,sizeof(unsigned long));
        // ... dann die Länge der Liste schreiben (Platz für min_dist und tree_count NICHT mitrechnen!)
        //long bytesize = unique_element_count*(Group::indexSize()+sizeof(int));
    long pos_old = ofs.tellp();

    unsigned long bytesize = tree_size;
    ofs.write((char*)&bytesize, sizeof(unsigned long));

        long tmp = ofs.tellp();
        
        //int written = 1;
        avlTree<treeSaver<tpTREE> >::iterator itTree = treeList.begin();
        avlTree<treeSaver<tpTREE> >::iterator itStop = treeList.end();
        int FileNum;
        while (itTree!=itStop)
        {
                FileNum = (*itTree)->getFileNum();
                ofs.write((char*)&FileNum, sizeof(FileNum));
                
        ofs<<*((*itTree)->getTree());
                //delete (*itTree)->getTree();
                ++itTree;
        }

    long pos_new = ofs.tellp();

    delete[] code_elements;
        
    ::remove(m_insertion_file_name);
}

template<class Group, class numeric, int Dim, class numeric_writer>
// /////////////////////////////////////////////////////////////////////////////////////
ListTupel<Group> IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::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;
        
        // offset im File berechnen und von der Stelle aus lesen...
        long offset = my_fileoffset + index*(Group::indexSize()+sizeof(int));
        fseek(mystream, offset, SEEK_SET);
        fread(&lt, Group::indexSize(), 1, mystream);
        return lt;
}

template<class Group, class numeric, int Dim, class numeric_writer>
// /////////////////////////////////////////////////////////////////////////////////////
void IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::readElements(ListTupel<Group>* buffer)
// /////////////////////////////////////////////////////////////////////////////////////
// buffer muss groß genug sein, daß element_count viele ListTupel
// Platz finden.
/*********************************************************************
* FORMAT:                                                                                                                        *
* sizeof(unsigned long) Bytes Länge der gesamten Liste in Bytes      *
* sizeof(numeric)        Bytes Minimaldistanz                        *
* sizeof(unsigned long) Bytes Anzahl von ekd-Bäumen                                      *
*                                                                    *
* Danach für jeden ekd-Baum der Liste:                               *
* sizeof(int) Dateiindex                                                                                         *
* sizeof(unsigned long) Bytes Größe des ekd-Baumes in Bytes          *
**********************************************************************
*/
{
        readIntervals();
}

template<class Group, class numeric, int Dim, class numeric_writer>
// /////////////////////////////////////////////////////////////////////////////////////
void IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::readIntervals()
// /////////////////////////////////////////////////////////////////////////////////////
{

        //if (epsilon>Group::max_epsilon)
        //      epsilon = Group::max_epsilon;

        intervals_matched = m_element_count;

        if (tree_count==0)
                return;

        // wenn die Elemente bereits gelesen sind, werden sie nicht nochmal gelesen...
        if (treeList.numberOfNodes()>0)
                return;

    m_stream->seekg(m_fileoffset, std::ios::beg);
        if (!(*m_stream))
        {
                throw IndexingException(IndexingException::FILE_ERROR_READ);
                return;
        }

        for (int i=0; i<tree_count; i++)
        {

                int tidx;
                m_stream->read((char*)&tidx,sizeof(int));
                if (!(*m_stream))
                {
                        throw IndexingException(IndexingException::FILE_ERROR_READ);
                        return;
                }

                treeList.insert(treeSaver<tpTREE>(new tpTREE(*m_stream), tidx));
                if (!(*m_stream))
                {
                        throw IndexingException(IndexingException::FILE_ERROR_READ);
                        return;
                }
        }

        //interval_count = element_count;
}
        
template<class Group, class numeric, int Dim, class numeric_writer>
// /////////////////////////////////////////////////////////////////////////////////////
void IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::readElements()
// /////////////////////////////////////////////////////////////////////////////////////
{
        intervals_matched = m_element_count;

        if (tree_count>0)
                readIntervals();
}

/*template<class Group, class numeric, int Dim, class numeric_writer>
// /////////////////////////////////////////////////////////////////////////////////////
void IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::insert(Group& g, int i)
// /////////////////////////////////////////////////////////////////////////////////////
{

        // Index muss sich im Einfügemodus befinden
        FILE* insertion_stream = fopen(m_insertion_file_name, "ab");

        if (insertion_stream==NULL)
        {
                throw IndexingException(IndexingException::FILE_ERROR_OPEN);
                return;
        }

        if (ferror(insertion_stream)!=0)
        {
                throw IndexingException(IndexingException::FILE_ERROR_OPEN);
                return;
        }

        ListTupel<Group>* lt = new ListTupel<Group>();
        lt->g = g;
        lt->i = i;

        //fwrite(lt,sizeof(ListTupel<Group>),1,insertion_stream);
        g.writeToFile(insertion_stream);
        fwrite(&i,sizeof(int),1,insertion_stream);
        
        fclose(insertion_stream);

        delete lt;

        m_element_count++;

}*/

template<class Group, class numeric, int Dim, class numeric_writer>
// /////////////////////////////////////////////////////////////////////////////////////
void IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::initFileRead(std::ifstream& ifs)
// /////////////////////////////////////////////////////////////////////////////////////
/************************************************************************
* FORMAT:                                                                                                                           *
* sizeof(numeric_writer)        Bytes   Minimaldistanz                          *
* sizeof(unsigned long) Bytes   Anzahl von ekd-Bäumen                                   *
* sizeof(unsigned long) Bytes   Anzahl von Einträgen insgesamt              *
* sizeof(unsigned long) Bytes   Länge des verbleibenden Teils der Liste *
*                                                               in Bytes                                                                *
*                                                                       *
* Danach für jeden ekd-Baum der Liste:                                  *
*                                                                                                                                               *
* sizeof(int) Bytes             Dateiindex                                                              *                               
* ? Bytes                       ekd-Baum                                                                *
*************************************************************************
*/
{

        freadInit = 1.0;

        // Minimaldistanz dieser Liste auslesen
        numeric_writer md;
        md.read(ifs);
        min_dist = md;

        if (!ifs)
        {
                throw IndexingException(IndexingException::FILE_ERROR_READ);
                return;
        }

        // Anzahl ekd-Bäume der aktuellen Liste ermitteln
        ifs.read((char*)&tree_count, sizeof(unsigned long));
        if (!ifs)
        {
                throw IndexingException(IndexingException::FILE_ERROR_READ);
                return;
        }

        // Anzahl Einträge in der aktuellen Liste ermitteln
        ifs.read((char*)&m_element_count, sizeof(unsigned long));
        if (!ifs)
        {
                throw IndexingException(IndexingException::FILE_ERROR_READ);
                return;
        }
    interval_count = m_element_count;

        // Wieviele Bytes müssen bis zum Anfang der nächsten G-Liste übersprungen werden?
        // => bsize viele!
        unsigned long bsize;
        ifs.read((char*)&bsize, sizeof(unsigned long));
        if (!ifs)
        {
                throw IndexingException(IndexingException::FILE_ERROR_READ);
                return;
        }

        // An der aktuellen Position in der Datei können bei Bedarf die Einträge 
        // der Liste ausgelesen werden; deshalb merken wir uns diese Position
        // in der Memeber-Variable my_fileoffset!

        m_stream = &ifs;
        m_fileoffset = ifs.tellg();
        if (!ifs)
        {
                throw IndexingException(IndexingException::FILE_ERROR_READ);
                return;
        }

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

}

template<class Group, class numeric, int Dim, class numeric_writer>
// /////////////////////////////////////////////////////////////////////////////////////
void IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::initFileRead(std::fstream& ifs)
// /////////////////////////////////////////////////////////////////////////////////////
/************************************************************************
* FORMAT:                                                                                                                           *
* sizeof(numeric_writer)        Bytes   Minimaldistanz                          *
* sizeof(unsigned long) Bytes   Anzahl von ekd-Bäumen                                   *
* sizeof(unsigned long) Bytes   Anzahl von Einträgen insgesamt              *
* sizeof(unsigned long) Bytes   Länge des verbleibenden Teils der Liste *
*                                                               in Bytes                                                                *
*                                                                       *
* Danach für jeden ekd-Baum der Liste:                                  *
*                                                                                                                                               *
* sizeof(int) Bytes             Dateiindex                                                              *                               
* ? Bytes                       ekd-Baum                                                                *
*************************************************************************
*/
{

        freadInit = 1.0;

        // Minimaldistanz dieser Liste auslesen
        numeric_writer md;
        md.read(ifs);
        min_dist = md;

        if (!ifs)
        {
                throw IndexingException(IndexingException::FILE_ERROR_READ);
                return;
        }

        // Anzahl ekd-Bäume der aktuellen Liste ermitteln
        ifs.read((char*)&tree_count, sizeof(unsigned long));
        if (!ifs)
        {
                throw IndexingException(IndexingException::FILE_ERROR_READ);
                return;
        }

        // Anzahl Einträge in der aktuellen Liste ermitteln
        ifs.read((char*)&m_element_count, sizeof(unsigned long));
        if (!ifs)
        {
                throw IndexingException(IndexingException::FILE_ERROR_READ);
                return;
        }
    interval_count = m_element_count;

        // Wieviele Bytes müssen bis zum Anfang der nächsten G-Liste übersprungen werden?
        // => bsize viele!
        unsigned long bsize;
        ifs.read((char*)&bsize, sizeof(unsigned long));
        if (!ifs)
        {
                throw IndexingException(IndexingException::FILE_ERROR_READ);
                return;
        }

        // An der aktuellen Position in der Datei können bei Bedarf die Einträge 
        // der Liste ausgelesen werden; deshalb merken wir uns diese Position
        // in der Memeber-Variable my_fileoffset!

        m_stream = &ifs;
        m_fileoffset = ifs.tellg();
        if (!ifs)
        {
                throw IndexingException(IndexingException::FILE_ERROR_READ);
                return;
        }

        // stream-Position auf nächste Liste setzen
    ifs.seekg(bsize, std::ios::cur);
    
    //char buf[1024];
    //ifs.read(&(buf[0]),1024);

        if (!ifs)
        {
                throw IndexingException(IndexingException::FILE_ERROR_READ);
                return;
        }

}

template<class Group, class numeric, int Dim, class numeric_writer>
// /////////////////////////////////////////////////////////////////////////////////////
void IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::deleteFile(int fileindex)
// /////////////////////////////////////////////////////////////////////////////////////
{
        if (mode!=MODE_CREATE_INDEX)
        {
                throw IndexingException(IndexingException::INDEX_WRONG_MODE);
                return;
        }

        FILE* insertion_stream = fopen(insertion_file_name, "rb");
        if (insertion_stream==NULL)
        {
                throw IndexingException(IndexingException::FILE_ERROR_OPEN);
                return;
        }

        rewind(insertion_stream);

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

        fclose(insertion_stream);

        insertion_stream = fopen(insertion_file_name, "wb");
        if (insertion_stream==NULL)
        {
                throw IndexingException(IndexingException::FILE_ERROR_OPEN);
                return;
        }

        int new_element_count = 0;

        for (i=0; i<element_count; i++)
        {
                if (elements[i].i!=fileindex)
                {
                        elements[i].g.writeToFile(insertion_stream);
                        fwrite(&(elements[i].i),sizeof(int),1,insertion_stream);
                        new_element_count++;
                        // elements[i] in Datei schreiben
                }
        }

        fclose (insertion_stream);

        element_count = new_element_count;

        delete[] elements;

}

template<class Group, class numeric, int Dim, class numeric_writer>
// /////////////////////////////////////////////////////////////////////////////////////
bool IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::interval_range_search(Group x, int left,int right, int &hit_pos)
// /////////////////////////////////////////////////////////////////////////////////////
{
        // EIN FÜR ALLE MAL:
        // Die Intervalle sind ABSTEIGEND sortiert.
        // Der größte Wert hat Index 0, der kleinste Index element_count!

        Interval<Group, numeric, Dim > ilc_x(x);
        
        //BEGIN DEBUG
        
        //for (int i=left; i<=right; i++)
        //{
        //      unsigned long diff = distance(intervals[i].cmin , ilc_x.g);
        //      hit_pos = i;
        //      if (diff<=Group::epsilon)
        //              return true;                    
        //}
        //return false;
        
        // END DEBUG

        bool found = false;
        int mid;

        if (left==right)
        {
                //unsigned long diff = array[left] > x ? array[left]-x : x-array[left];
                numeric diff = distance(intervals[left].cmin , ilc_x.g);
                hit_pos = left;
                if (diff<=Group::epsilon)
                        return true;

                return false;
        }
        
        if (intervals[left]<intervals[right])
        { cout<<"Fehler im Index?\n";cout.flush(); }

        if (ilc_x < intervals[right])
        {
                left = right-1;
                hit_pos = right;
                //unsigned long diff = array[left] > x ? array[left]-x : x-array[left];
                numeric diff = distance(intervals[right].cmin,ilc_x.g);
                if (diff<=Group::epsilon)
                        return true;
                return false;
        }
        if (intervals[left] < ilc_x)
    { 
                //left--;
                right = left+1;
                hit_pos = left;
                //unsigned long diff = array[right] > x ? array[right]-x : x-array[right];
                numeric diff = distance(intervals[left].cmin,ilc_x.g);
                if (diff<=Group::epsilon)
                        return true;
                return false;
        }

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

                Interval<Group, numeric, Dim > cmp = intervals[mid];
                if (cmp==ilc_x)
                        found = true;
                else if (cmp<ilc_x)
                        right = mid;
                else // (current>elements2[mid])
                        left = mid;

        }

        if (found)
        {
                hit_pos = mid;
                return true;
        }

        numeric diff = distance(intervals[left].cmin,ilc_x.g);
        if (diff<=Group::epsilon)
        {
                hit_pos = left;
                return true;
        }

        diff = distance(intervals[right].cmin,ilc_x.g);
        if (diff<=Group::epsilon)
        {
                hit_pos = right;
                return true;
        }

        return false;

}

template<class Group, class numeric, int Dim, class numeric_writer>
// /////////////////////////////////////////////////////////////////////////////////////
inline void IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::intersect(IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >& set2)
// /////////////////////////////////////////////////////////////////////////////////////
{
        intersect(set2, 0);
}

template<class Group, class numeric, int Dim, class numeric_writer>
// /////////////////////////////////////////////////////////////////////////////////////
IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::~IntervalIntersectionGList()
// /////////////////////////////////////////////////////////////////////////////////////
{
    if (insertion_buffer != NULL)
    {
        delete[] insertion_buffer;
        insertion_buffer = NULL;
    }

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

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

        m_elements = NULL;

    // dynEkdTrees löschen...
    treeSaver<tpTREE>* current_tree = treeList.getFirst();

    while (current_tree != NULL)
    {
        delete current_tree->getTree();
        current_tree = treeList.getNext();
    }

}

template<class Group, class numeric, int Dim, class numeric_writer>
// /////////////////////////////////////////////////////////////////////////////////////
void IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::printElements()
// /////////////////////////////////////////////////////////////////////////////////////
{

        int i,j;

        if (treeList.numberOfNodes()==0)
                readIntervals();

        iterator iterate = begin();
        iterator stop    = end();
        while(iterate!=stop)
        {
        std::cout<<(*iterate).i<<", "<<((*iterate).g)<<std::endl;
                iterate++;
        }
}

template<class Group, class numeric, int Dim, class numeric_writer>
// /////////////////////////////////////////////////////////////////////////////////////
void IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::pure_printElements()
// /////////////////////////////////////////////////////////////////////////////////////
{

        int i,j;

        if (treeList.numberOfNodes()==0)
                readIntervals();

        pure_iterator iterate = pure_begin();
        pure_iterator stop    = pure_end();
        while(iterate!=stop)
        {
        std::cout<<(*iterate).i<<", "<<((*iterate).g)<<std::endl;
                iterate++;
        }
}

/*
template<class Group, class numeric, int Dim, class numeric_writer>
// /////////////////////////////////////////////////////////////////////////////////////
int IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::rangeSearch(tpTREE* search_tree, Interval<Group, numeric, Dim >** result)
// /////////////////////////////////////////////////////////////////////////////////////
{
        int count;
        numeric low[Dim];
        numeric high[Dim];

        // untere und obere Grenze für Umgebungsanfrage bestimmen
        numeric local_epsilon = search_tree->epsilon;

        if (local_epsilon>Group::max_epsilon)
                local_epsilon = Group::max_epsilon;
        
        for (int k=0; k<Dim; k++)
        {
                numeric g_k = g_1[k];
                low[k] = g_k - local_epsilon / 2 ;//epsilon;
                high[k] = g_k + local_epsilon / 2 ;//epsilon;
        }
        
        return search_tree->search(low,high,result,1,count);

}
*/

// Version mit "simuliertem" Merge
template<class Group, class numeric, int Dim, class numeric_writer>
// /////////////////////////////////////////////////////////////////////////////////////
int IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::rangeSearch(Group& g_1, tpTREE* search_tree, int fileNum, Interval<Group, numeric, Dim >** result)
// /////////////////////////////////////////////////////////////////////////////////////
{
        int count, count2;
        numeric low[Dim];
        numeric high[Dim];
        numeric dist_min, dist_min2, dist_max, dist_max2;

        Interval<Group, numeric, Dim > ** result2 = new Interval<Group, numeric, Dim > *[1];

#ifndef USE_GROUP_DISTANCE
        // untere und obere Grenze für Umgebungsanfrage bestimmen
        numeric local_epsilon = search_tree->epsilon;

        if (local_epsilon>Group::max_epsilon)
                local_epsilon = Group::max_epsilon;
#else
        numeric local_epsilon = Group::max_epsilon;
#endif
        
        for (int k=0; k<Dim; k++)
        {
                numeric g_k = g_1[k];
                low[k] = g_k - local_epsilon / 2;//epsilon;
                high[k] = g_k + local_epsilon / 2;//epsilon;
        }
        
        search_tree->search(low,high,result,1,count);

        std::list<IntervalIntersectionGList*>::iterator start = m_merged_with.begin();
        std::list<IntervalIntersectionGList*>::iterator stop  = m_merged_with.end();

        treeSaver<tpTREE>* treelook;

        while (start!=stop)
        {
                treelook=(*start)->treeList.findData(treeSaver<tpTREE>(NULL, fileNum));

                if (treelook)
                {
                        treelook->getTree()->search(low, high, result2, 1, count2);
                        if (count==0)
                        {
                                result[0] = result2[0];
                                count     = count2;
                        }
                        else
                                if (count2>0)
                                { 
                                        dist_min  = distance(result[0]->cmin,g_1);
                                        dist_max  = distance(result[0]->cmax,g_1);
                                        dist_min2 = distance(result2[0]->cmin,g_1);
                                        dist_max2 = distance(result2[0]->cmax,g_1);

                                        if (dist_min2 < dist_min && dist_max2 < dist_max)
                                                result[0] = result2[0];
                                }
                }

                start++;
        }

        delete result2;

        return count;
}

template<class Group, class numeric, int Dim, class numeric_writer>
// /////////////////////////////////////////////////////////////////////////////////////
void IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::setCredit(int credit)
// /////////////////////////////////////////////////////////////////////////////////////
{
    m_credit = credit;
}

template<class Group, class numeric, int Dim, class numeric_writer>
// /////////////////////////////////////////////////////////////////////////////////////
void IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::intersect(IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >& glist2, int credit)
// /////////////////////////////////////////////////////////////////////////////////////
{
        m_credit = credit;

        if (intervals==NULL)
                readIntervals();

        //DEBUG
        glist2.readIntervals();
        glist2.m_credit = credit;

        // Liste leer ?
        if (glist2.size()<=0)
        {
                intersects++;
                return;
        }

        intervals_matched = 0;

        // Durchlaufe alle ekdTrees in glist2

        iterator iterate(glist2.begin());
        iterator stop   (glist2.end());

        std::list<std::pair<Interval<Group, numeric, Dim>,int> > ins_list;

        while(iterate!=stop)
        {
                Group g_1 = (*iterate).g;
                g_1 *= m_factor_inverse;

                // zunächst Suchbereich auf gültige Werte von i einschränken
                treeSaver<tpTREE> *treepos = treeList.findData(treeSaver<tpTREE>(NULL, iterate.getCurrentFile()));                              

                if (treepos)
                {
                        // EPSILON-BEREICHSSUCHE im verbleibenden ekd-Baum.
                        // Relevant für das Suchergebnis ist ausschließlich 
                        // das Gruppenelement, da die Dateinummern innerhalb
                        // des Baumes sicher übereinstimmen.

                        Interval<Group, numeric, Dim > ** result = new Interval<Group, numeric, Dim > *[1];

            // int found = rangeSearch(treepos->getTree(), result);
                        // Das Vereinigen von Listen wird simuliert:
                        int found = rangeSearch(g_1, treepos->getTree(), iterate.getCurrentFile(), result);

                        Interval<Group, numeric, Dim >* current_interval = result[0];

                        // Mismatches beachten!
                        if (found>0)
                        {
                                numeric dist_min = distance(current_interval->cmin,g_1);
                                numeric dist_max = distance(current_interval->cmax,g_1);
                        #ifndef USE_GROUP_DISTANCE
                                numeric local_epsilon = treepos->getTree()->epsilon;
                        #else
                                numeric local_epsilon = Group::max_epsilon;
                        #endif


                        #ifndef USE_GROUP_DISTANCE
                                Interval<Group, numeric, Dim >* old_interval = current_interval;
                        #endif
                                if (dist_min <= local_epsilon && dist_max <= local_epsilon)
                                {
                                        current_interval->matched++;
                                        current_interval->expand(g_1);
                                        intervals_matched++;
                                }

                        #ifndef USE_GROUP_DISTANCE
                                // Falls epsilon > Minimaldistanz:
                                for (int i_found = 1; i_found<found; i_found++)
                                {
                                        Interval<Group, numeric, Dim > i_new;
                                        i_new = *old_interval;
                                        old_interval->expand(g_1);
                                        ins_list.push_back(std::pair<Interval<Group, numeric, Dim>, int>(i_new, iterate.getCurrentFile()));
                                }
                        #endif

                        } else {
                                // Einfügen von (g_1) in treeList[pos]
                                treepos->getTree()->insert(*(new Interval<Group, numeric, Dim>(g_1, 0)));

                        }
                        delete[] result;
                } 
                else 
                {
                        // Neuen Baum anlegen für Dateinummer set2FileIndex 
                        // und Interval(g_1) in diesen Baum mit entsprechender Anzahl mismatches
                        // einfügen.
                        treeList.insert(treeSaver<tpTREE>
                                (new tpTREE(new Interval<Group, numeric, Dim>(g_1, 0), 1), iterate.getCurrentFile()));
                }

                iterate++;
        }

#ifndef USE_GROUP_DISTANCE
        std::list<std::pair<Interval<Group, numeric, Dim >, int> >::iterator ins_it = ins_list.begin();
        std::list<std::pair<Interval<Group, numeric, Dim >, int> >::iterator ins_end = ins_list.end();
        for (; ins_it != ins_end; ins_it++)
        {
                treeSaver<tpTREE> *treepos = treeList.findData(treeSaver<tpTREE>(NULL, (*ins_it).second));                              
                treepos->getTree()->insert(*(new Interval<Group, numeric, Dim>(((*ins_it).first).g, 0)));
        }
#endif
        intersects++;
        
}

template<class Group, class numeric, int Dim, class numeric_writer>
// /////////////////////////////////////////////////////////////////////////////////////
void IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::merge(IntervalIntersectionGList<Group, numeric, Dim, numeric_writer>& set2)
// /////////////////////////////////////////////////////////////////////////////////////
{
        m_merged_with.insert(m_merged_with.begin(), &set2);
}

/*
template<class Group>
ostream& operator<<(ostream& o, GInvertedList<Group> g)
{
        IntervalIntersectionGList<Group> em = *((IntervalIntersectionGList<Group>*)((void*)&g));
        if (!em.readElements())
                return o;
        for (int i=0; i<em.size(); i++)
        {
                o<<em.elements[i].i<<" - "<<em.elements[i].g<<endl;
        }
        o<<endl;
        return o;
}

*/



/*
template<class Group, class numeric, int Dim, class numeric_writer>
// /////////////////////////////////////////////////////////////////////////////////////
inline Interval<Group, numeric, Dim, numeric_writer>& IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::iterator::operator *() const
// /////////////////////////////////////////////////////////////////////////////////////
{
        return *m_iterator;
}
*/

/*template<class Group, class numeric, int Dim, class numeric_writer>
// /////////////////////////////////////////////////////////////////////////////////////
inline bool IntervalIntersectionGList<Group, numeric, Dim, numeric_writer >::iterator::operator !=(iterator& compare)
// /////////////////////////////////////////////////////////////////////////////////////
{
        return !(*this==compare);
}*/


}

#endif // DEF_INTERVALINTERSECTIONGLIST

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