Tree-M/MT/MT.h

/*********************************************************************
*                                                                    *
* Copyright (c) 1997,1998, 1999                                      *
* Multimedia DB Group and DEIS - CSITE-CNR,                          *
* University of Bologna, Bologna, ITALY.                             *
*                                                                    *
* All Rights Reserved.                                               *
*                                                                    *
* Permission to use, copy, and distribute this software and its      *
* documentation for NON-COMMERCIAL purposes and without fee is       *
* hereby granted provided  that this copyright notice appears in     *
* all copies.                                                        *
*                                                                    *
* THE AUTHORS MAKE NO REPRESENTATIONS OR WARRANTIES ABOUT THE        *
* SUITABILITY OF THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING  *
* BUT NOT LIMITED TO THE IMPLIED WARRANTIES OF MERCHANTABILITY,      *
* FITNESS FOR A PARTICULAR PURPOSE, OR NON-INFRINGEMENT. THE AUTHOR  *
* SHALL NOT BE LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE AS A      *
* RESULT OF USING, MODIFYING OR DISTRIBUTING THIS SOFTWARE OR ITS    *
* DERIVATIVES.                                                       *
*                                                                    *
*********************************************************************/

#ifndef MT_H
#define MT_H

#include "GiST.h"
#include "GiSTentry.h"
#include "MTfile.h"
#include "MTnode.h"
#include "MTcursor.h"
#ifdef _WIN32   // for MAXDOUBLE
#include <float.h>
#include <limits.h>
#define MAXDOUBLE DBL_MAX
#define MINDOUBLE DBL_MIN
#define MAXINT INT_MAX
#else   // under UNIX these constants are defined in values.h
#include <values.h>
#endif

class MTkey;
class TopQuery;
class MTcursor;

typedef enum {
        MIN_R_INCR=0,
        MIN_OVERLAP=1,
        MIXED=2
} tb_function;  // tie breaking functions

typedef enum {
        RANDOM=0,
        CONFIRMED=1,
        MAX_UB_DIST=2,
        MIN_RAD=3,
        MIN_OVERLAPS=4,
        SAMPLING=5,
} pp_function;  // promotion functions

typedef enum {
        RANDOMV=0,
        SAMPLINGV=1,
        MAX_LB_DIST=2,
        mM_RAD=3
} pv_function;  // confirmed promotion functions

typedef enum {
        LB=0,
        AVG=1,
        UB=2
} r_function;   // min_MAX_radius functions

typedef enum {
        G_HYPERPL=0,
        BAL_G_HYPERPL=1,
        BALANCED=2
} s_function;   // split functions

class MT : public GiST {
        unsigned int page;
public:
        MT(unsigned int pagesize) : page(pagesize) {};
        // optional, for debugging support
        GiSTobjid IsA() { return MT_CLASS; }

        int IsOrdered() const { return 1; }     // the children of each node are ordered on increasing distances from the parent
        int MaxLevel() const;   // height of the M-tree
        GiSTlist<MTentry *> RangeSearch(const MTquery& query);  // range search
        MTentry **TopSearch(const TopQuery& query);     // generic search algorithm: k-NN search for a TopQuery
        MTnode *ParentNode(MTnode *node);       // return the parent of node (the caller should delete the object)
        void BulkLoad(MTentry **data, int n, double padFactor, char *name);     // bulk-loading algorithm
        void CollectStats();    // level-stats collecting function: total number of pages, average radius and average covered volume (if applicable)
        BOOL CheckNode(GiSTpath path, MTentry *e);      // debug function: check for node consistency

        // friend methods and functions
        friend void MTnode::InvalidateEntry(BOOL isNew);
        friend GiSTlist<MTentry *> MTnode::RangeSearch(const MTquery& query);
        friend void MTcursor::FetchNode();

protected:
        // Required members
        GiSTnode  *CreateNode()  const { return new MTnode; }
        GiSTstore *CreateStore() const { return new MTfile(page); }

        // Service methods for Bulk Load
        GiSTlist<char *> *SplitTree(int *ncreated, int level, GiSTlist<MTentry *> *children, char *name);       // split this M-tree into a list of M-trees whose names are returned
        void Append(MTnode *to, MTnode *from);  // append the sub-tree of node from to node to
private:
        void AdjKeys(GiSTnode *node);   // slightly different from AdjustKeys (necessary to keep track of the distance from the parent)
};

int PickRandom(int from, int to);       // pick a determined number of samples in the range [from, to[

#endif
Revision:	1.3
Committed:	Fri Jul 27 12:48:23 2001 UTC (22 years, 9 months ago) by root
Content type:	text/plain
Branch:	MAIN
CVS Tags:	HEAD
Changes since 1.2:	+2 -2 lines
Log Message:	* empty log message *
#	Content
1	/*********************************************************************
2	* *
3	* Copyright (c) 1997,1998, 1999 *
4	* Multimedia DB Group and DEIS - CSITE-CNR, *
5	* University of Bologna, Bologna, ITALY. *
6	* *
7	* All Rights Reserved. *
8	* *
9	* Permission to use, copy, and distribute this software and its *
10	* documentation for NON-COMMERCIAL purposes and without fee is *
11	* hereby granted provided that this copyright notice appears in *
12	* all copies. *
13	* *
14	* THE AUTHORS MAKE NO REPRESENTATIONS OR WARRANTIES ABOUT THE *
15	* SUITABILITY OF THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING *
16	* BUT NOT LIMITED TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, *
17	* FITNESS FOR A PARTICULAR PURPOSE, OR NON-INFRINGEMENT. THE AUTHOR *
18	* SHALL NOT BE LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE AS A *
19	* RESULT OF USING, MODIFYING OR DISTRIBUTING THIS SOFTWARE OR ITS *
20	* DERIVATIVES. *
21	* *
22	*********************************************************************/
23
24	#ifndef MT_H
25	#define MT_H
26
27	#include "GiST.h"
28	#include "GiSTentry.h"
29	#include "MTfile.h"
30	#include "MTnode.h"
31	#include "MTcursor.h"
32	#ifdef _WIN32 // for MAXDOUBLE
33	#include <float.h>
34	#include <limits.h>
35	#define MAXDOUBLE DBL_MAX
36	#define MINDOUBLE DBL_MIN
37	#define MAXINT INT_MAX
38	#else // under UNIX these constants are defined in values.h
39	#include <values.h>
40	#endif
41
42	class MTkey;
43	class TopQuery;
44	class MTcursor;
45
46	typedef enum {
47	MIN_R_INCR=0,
48	MIN_OVERLAP=1,
49	MIXED=2
50	} tb_function; // tie breaking functions
51
52	typedef enum {
53	RANDOM=0,
54	CONFIRMED=1,
55	MAX_UB_DIST=2,
56	MIN_RAD=3,
57	MIN_OVERLAPS=4,
58	SAMPLING=5,
59	} pp_function; // promotion functions
60
61	typedef enum {
62	RANDOMV=0,
63	SAMPLINGV=1,
64	MAX_LB_DIST=2,
65	mM_RAD=3
66	} pv_function; // confirmed promotion functions
67
68	typedef enum {
69	LB=0,
70	AVG=1,
71	UB=2
72	} r_function; // min_MAX_radius functions
73
74	typedef enum {
75	G_HYPERPL=0,
76	BAL_G_HYPERPL=1,
77	BALANCED=2
78	} s_function; // split functions
79
80	class MT : public GiST {
81	unsigned int page;
82	public:
83	MT(unsigned int pagesize) : page(pagesize) {};
84	// optional, for debugging support
85	GiSTobjid IsA() { return MT_CLASS; }
86
87	int IsOrdered() const { return 1; } // the children of each node are ordered on increasing distances from the parent
88	int MaxLevel() const; // height of the M-tree
89	GiSTlist<MTentry *> RangeSearch(const MTquery& query); // range search
90	MTentry **TopSearch(const TopQuery& query); // generic search algorithm: k-NN search for a TopQuery
91	MTnode ParentNode(MTnode node); // return the parent of node (the caller should delete the object)
92	void BulkLoad(MTentry *data, int n, double padFactor, char name); // bulk-loading algorithm
93	void CollectStats(); // level-stats collecting function: total number of pages, average radius and average covered volume (if applicable)
94	BOOL CheckNode(GiSTpath path, MTentry *e); // debug function: check for node consistency
95
96	// friend methods and functions
97	friend void MTnode::InvalidateEntry(BOOL isNew);
98	friend GiSTlist<MTentry *> MTnode::RangeSearch(const MTquery& query);
99	friend void MTcursor::FetchNode();
100
101	protected:
102	// Required members
103	GiSTnode *CreateNode() const { return new MTnode; }
104	GiSTstore *CreateStore() const { return new MTfile(page); }
105
106	// Service methods for Bulk Load
107	GiSTlist<char > SplitTree(int ncreated, int level, GiSTlist<MTentry > children, char name); // split this M-tree into a list of M-trees whose names are returned
108	void Append(MTnode to, MTnode from); // append the sub-tree of node from to node to
109	private:
110	void AdjKeys(GiSTnode *node); // slightly different from AdjustKeys (necessary to keep track of the distance from the parent)
111	};
112
113	int PickRandom(int from, int to); // pick a determined number of samples in the range [from, to[
114
115	#endif