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, 10 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 *
#	User	Rev	Content
1	root	1.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	root	1.2	unsigned int page;
82	root	1.1	public:
83	root	1.2	MT(unsigned int pagesize) : page(pagesize) {};
84	root	1.1	// 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	root	1.3	friend GiSTlist<MTentry *> MTnode::RangeSearch(const MTquery& query);
99			friend void MTcursor::FetchNode();
100	root	1.1
101			protected:
102			// Required members
103			GiSTnode *CreateNode() const { return new MTnode; }
104	root	1.2	GiSTstore *CreateStore() const { return new MTfile(page); }
105	root	1.1
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