x_tree.h

X-tree的C++源码

#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 S3
void 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 S3
class Index;
class Result;
#endif // S3

struct 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 written
public:
    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 page
public:
    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 data
public:
    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 son
public:
    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 header
public:
    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++)
    {