#ifndef __XTREE#define __XTREE#include "linlist.h"//////////////////////////////////////////////////////////////////////////////// defines//////////////////////////////////////////////////////////////////////////////#define MAXREAL 9.99e20#define MAX_DIMENSION 256#define EXT_SIZE 5#define MAX_OVERLAP 0.2#define MIN_FANOUT 0.35#ifndef S3#ifndef TRUE#define TRUE 1#define FALSE 0#endif  // TRUE#define min(a, b) (((a) < (b))? (a) : (b)  ) #define max(a, b) (((a) > (b))? (a) : (b)  ) #endif  // S3//////////////////////////////////////////////////////////////////////////////// C-prototypes//////////////////////////////////////////////////////////////////////////////float area(int dimension, float *mbr);float margin(int dimension, float *mbr);float overlap(int dimension, float *r1, float *r2);float OBJECT_DIST(const void  *Point1,const void  *Point2);float MINMAXDIST(const void  *Point, float *bounces);float MINDIST(const void *Point, float *bounces);bool inside(float &p, float &lb, float &ub);void enlarge(int dimension, float **mbr, float *r1, float *r2);bool is_inside(int dimension, float *p, float *mbr);bool section(int dimension, float *mbr1, float *mbr2);bool section_c(int dimension, float *mbr1, const void *center, float radius);void check_mbr(int dimension, float *mbr);int sort_lower_mbr(const void *d1, const void *d2);int sort_upper_mbr(const void *d1, const void *d2);int sort_center_mbr(const void *d1, const void *d2);int sort_min_dist(const void *element1, const void *element2);int prune_branch_list(float *nearest_distanz, const void *activebrunchList, int n);int test_branch_list(const void *abL, const void *sL, int n, int last);#ifndef S3void error(char *t, bool ex);#endif//////////////////////////////////////////////////////////////////////////////// externals//////////////////////////////////////////////////////////////////////////////extern int XTDirNode__dimension;extern void* XTDirNode__my_tree;extern int XTDataNode__dimension;extern float page_access;//////////////////////////////////////////////////////////////////////////////// enums / types//////////////////////////////////////////////////////////////////////////////enum SECTION {OVERLAP, INSIDE, S_NONE};enum R_OVERFLOW {SPLIT, SUPERNODE, NONE};typedef float *floatptr;typedef int bitvector;//////////////////////////////////////////////////////////////////////////////// classes//////////////////////////////////////////////////////////////////////////////#ifdef S3class Index;class Result;#endif // S3struct SortMbr{    int dimension;    float *mbr;    float *center;    int index;};struct DataStruct{    int dimension;    float *Data;};struct BranchList{    int entry_number;    float mindist;    float minmaxdist;    bool section;};template <class DATA> class XTNode{    friend class XTree<DATA>;protected:   XTree<DATA> *my_tree;                // pointer to X-tree    int capacity;                       // max. # of entries    int dimension;    int num_entries;                    // # of used entries    bool dirty;                         // TRUE, if node has to be writtenpublic:    int block;    char level;                         // level of the node in the tree    int get_num()                       // returns # of used entries    { return num_entries;}    virtual int get_num_of_data() = 0;  // returns number of data entries                                        // behind that node    virtual DATA * get(int i) = 0;      // returns the i-th object in the                                         // tree lying behind that node        virtual bool is_data_node() = 0;	// returns TRUE, if "this" is                                         // *XTDataNode     virtual float *get_mbr() = 0;       // returns mbr enclosing whole page    virtual void print()                // prints rectangles    { }    int topological_split(float **mbr, int **distribution, int *dim);                                        // splits an Array of mbr's into 2                                         // and returns in distribution                                        // which *m mbr's are to be                                        // moved    int overlap_free_split(float **mbr, int *split_hist, int **distribution, int *dim);#ifdef S3    virtual void neighbours(LinList<DATA> *sl,   		    float eps,           // berechnet fuer alle DATAs in		    Result *rs,          // sl die Nachbarn, die in der eps-		    norm_ptr norm) = 0;  // Umgebung liegen#endif // S3    virtual void nearest_neighbour_search(DATA *Point, DATA  *Nearest,float *nearest_distanz) = 0;    virtual void nearest_neighbour_search(DATA *Point, 		SortedLinList<DATA> *res, float *nearest_distanz) =  0;    virtual void range_query(float *mbr, SortedLinList<DATA> *res) = 0;    virtual void range_query(DATA *center, float radius, SortedLinList<DATA> *res) = 0;     virtual void overlapping(float *p, int *nodes_t) = 0;    virtual void nodes(int *nodes_a) = 0;    virtual void write_info(FILE *f) = 0;	    virtual R_OVERFLOW insert(DATA *d, XTNode<DATA> **sn, int *dim) = 0;                                         // inserts d recursivly, if there                                        // occurs a split, FALSE will be                                        // returned and in sn a                                         // pointer to the new node    virtual void region(float *mbr) = 0;                                        // prints all entries sectioning                                        // mbr    virtual void point_query(float *p) = 0;                                         // prints all entries equal to p                                             XTNode(XTree<DATA> *rt);    XTNode(XTree<DATA> *rt, int _block);    virtual ~XTNode();};template <class DATA> class XTDirNode: public XTNode<DATA>{    friend class XTree<DATA>;    int nodesize;                       // size of Directory Node                                        // nodesize > 1 => SuperNode    DirEntry<DATA> *entries;            // array of entries    bool son_is_data;                   // TRUE, if son is a data pagepublic:    int* intern_block;                  // array of blocks    int block_capacity;    void read_header(char* buffer);     // reads header of buffer    void read_from_buffer(char *buffer, int offset);// reads data from buffer    void write_to_buffer(char *buffer, int offset); // writes data to buffer    bool is_data_node()    {return FALSE;}    int get_num_of_data();              // returns number of data entries                                        // behind that node    DATA * get(int i);                  // returns the i-th object in the                                         // tree lying behind that node    void print();                       // prints rectangles    float *get_mbr();                   // returns mbr enclosing whole page    float *calc_mbr(DirEntry<DATA> *de, int num_entries);    					// calculates mbr enclosing DirEntries        void enter(DirEntry<DATA> *de);     // inserts new entry    void adapt_node(int mult);                 // adapt node to supernode      bool split(XTDirNode<DATA> **sn, int *dim);    					// splits directory page to *this and sn    					// returns FALSE, if supernode was created    int choose_subtree(float *brm);     // chooses best subtree for insertion#ifdef S3    void neighbours(LinList<DATA> *sl,  // berechnet fuer alle DATAs in		    float eps,          // sl die Nachbarn, die in der eps-		    Result *rs,         // Umgebung liegen		    norm_ptr norm);#endif // S3    void nearest_neighbour_search(DATA *QueryPoint, 				DATA *Nearest,float *nearest_distanz);    void nearest_neighbour_search(DATA *QueryPoint, 			SortedLinList<DATA> *res,			float *nearest_distanz);    void range_query(float *mbr, SortedLinList<DATA> *res);    void range_query(DATA *center, float radius, SortedLinList<DATA> *res);	    R_OVERFLOW insert(DATA *d, XTNode<DATA> **sn, int *dim);                                          // inserts d recursivly, if there                                        // occurs a split, FALSE will be                                        // returned and in sn a                                         // pointer to the new node    void region(float *mbr);            // prints all entries sectioning mbr    void point_query(float *p);         // prints all entries equal to p    void overlapping(float *p, int *nodes_t);    void nodes(int *nodes_a);    void write_info(FILE  *f);    XTDirNode(int _nodesize, XTree<DATA> *rt);                      XTDirNode(XTree<DATA> *rt, int _block);    virtual ~XTDirNode();};template <class DATA> class XTDataNode: public XTNode<DATA>{    DATA *data;                         // array of datapublic:    void read_from_buffer(char *buffer);// reads data from buffer    void write_to_buffer(char *buffer); // writes data to buffer    bool is_data_node()    {return TRUE;}    void print();                       // prints vector    int get_num_of_data();              // returns number of data entries                                        // in that node    DATA * get(int i);                  // returns the i-th object in this node     float *get_mbr();                   // returns mbr enclosing whole page     void split(XTDataNode<DATA> *sn, int *dim);    					// splits data page into sn and *this;                                        // returns split dimension#ifdef S3    void neighbours(LinList<DATA> *sl,  // berechnet fuer alle DATAs in		    float eps,          // sl die Nachbarn, die in der eps-		    Result *rs,         // Umgebung liegen		    norm_ptr norm);#endif // S3    void nearest_neighbour_search(DATA *QueryPoint, 				DATA *Nearest, float *nearest_distanz);    void nearest_neighbour_search(DATA *QueryPoint, 			SortedLinList<DATA> *res, float *nearest_distanz);    void range_query(float *mbr, SortedLinList<DATA> *res);    void range_query(DATA *center, float radius, SortedLinList<DATA> *res);    R_OVERFLOW insert(DATA *d, XTNode<DATA> **sn, int *dim);                                          // inserts d recursivly, if there                                        // occurs a split, FALSE will be                                        // returned and in sn a                                         // pointer to the new node    void region(float *mbr);            // prints all entries sectioning                                        // mbr    void point_query(float *mbr);       // prints all entries equal to p    void overlapping(float *p, int *nodes_t)    { nodes_t[0]++; }    void nodes(int *nodes_a)    { nodes_a[0]++; }    void write_info(FILE *f);    XTDataNode(XTree<DATA> *rt);                      XTDataNode(XTree<DATA> *rt, int _block);    virtual ~XTDataNode();};template <class DATA> class DirEntry{    friend class XTDirNode<DATA>;    friend class XTree<DATA>;    XTree<DATA> *my_tree;               // pointer to my Xtree    int son;                            // block # of son    XTNode<DATA> *son_ptr;              // pointer to son if in main mem.    bool son_is_data;                   // TRUE, if son is a data page    int dimension;                      // dimension of the box    float *bounces;                     // pointer to box    int num_of_data;                    // amount of data entries behind the                                        // son of this entry    bitvector history;			// split-history of sonpublic:    bool is_inside(float *v);           // tests, if v is inside the box    SECTION section(float *mbr);        // tests, if mbr intersects the box    XTNode<DATA>* get_son();            // returns pointer to the son,                                        // loads son if necessary    bool section_circle(DATA *center, float radius);    void read_from_buffer(char *buffer);// reads data from buffer       void write_to_buffer(char *buffer); // writes data to buffer      int get_size();                     // returns amount of needed buffer space    virtual DirEntry<DATA> & operator = (DirEntry<DATA> &_d);    DirEntry(int dimension = XTDirNode__dimension, 	     XTree<DATA> *rt = (XTree<DATA> *)XTDirNode__my_tree);    virtual ~DirEntry();};template <class DATA> class XTree {public:    friend class XTNode<DATA>;    friend class XTDirNode<DATA>;    friend class XTDataNode<DATA>;    int root;                            // block # of root node    XTNode<DATA> *root_ptr;              // root-node    bool root_is_data;                   // TRUE, if root is a data page    int dimension;                       // dimension of the datas    int num_of_data;	                 // # of stored data     int num_of_dnodes;	                 // # of stored data pages    int num_of_inodes;	                 // # of stored directory pages    CachedBlockFile *file;	         // storage manager for harddisc blocks    void load_root();                    // loads root_node into memory    int akt;                             // # of actually got data (get_next)    char *header;    float node_weight[20];               // weight for simulation of cache    char *block_buffer;                  // buffer for reading and writing nodes protected:    char *user_header;    void read_header(char *buffer);      // reads XTree header    void write_header(char *buffer);     // writes XTree headerpublic:    int get_num()                        // returns # of stored data    { return num_of_data; }                  void insert(DATA *d);                // inserts new data into tree#ifdef S3    bool erase(PolygonId &i)             // erases object # i    { error("XTree::erase: not implemented", FALSE); }#endif    DATA *get_first()                    // trace    { akt = 0; return get(akt); }        // through    DATA *get_next()                     // all     { akt++; return get(akt); }          // data    DATA *get(int i);                    // get i-th data    void set_node_weight(int cache_size); // calculate influence of cache#ifdef S3    void neighbours(LinList<DATA> *sl,   // berechnet fuer alle DATAs in		    float eps,           // sl die Nachbarn, die in der eps-		    Result *rs,          // Umgebung liegen		    norm_ptr norm);#endif // S3    void region(float *mbr);             // print all entries intersection                                          // the box mbr    void point_query(float *p);          // print all entries equal to p    void nearest_neighbour_search(DATA *QueryPoint, DATA *Nearest);        void nearest_neighbour_search(DATA *QueryPoint, SortedLinList<DATA> *res);    void k_nearest_neighbour_search(DATA *QueryPoint, int k, SortedLinList<DATA> *NeighborList);    void range_query(float *mbr, SortedLinList<DATA> *res);    void range_query(DATA *center, float radius, SortedLinList<DATA> *res);    void print_info(FILE *f);    void overlapping(float *p, int *nodes_t);    void nodes(int *nodes_a);    void write_info(FILE *f);    XTree(char *fname, 	  int _b_length, int cache_size, 	  int _dimension);    XTree(char *fname, int cache_size);    virtual ~XTree();};//////////////////////////////////////////////////////////////////////////////// implementation////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// DirEntry//////////////////////////////////////////////////////////////////////////////template <class DATA> DirEntry<DATA>::DirEntry(int _dimension, XTree<DATA> *rt){    dimension = _dimension;    my_tree = rt;    bounces = new float[2*dimension];    son_ptr = NULL;    num_of_data = 0;    history = 0;    }template <class DATA> DirEntry<DATA>::~DirEntry(){    if (bounces != NULL)        delete [] bounces;    if (son_ptr != NULL)	delete son_ptr;}template <class DATA> DirEntry<DATA>& DirEntry<DATA>::operator = (DirEntry &_d){    dimension = _d.dimension;    son = _d.son;    son_ptr = _d.son_ptr;    son_is_data = _d.son_is_data;    num_of_data = _d.num_of_data;    memcpy(bounces, _d.bounces, sizeof(float) * 2 * dimension);    history = _d.history;        return *this;}template <class DATA> bool DirEntry<DATA>::is_inside(float *v){    int i;    for (i = 0; i < dimension; i++)    {