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 {
public:
        // 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<GiSTobject *> MTnode::RangeSearch(const MTquery& query);
        friend MTentry *MTcursor::FetchNode();

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

        // 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.1
Committed:	Sun May 6 00:45:52 2001 UTC (23 years, 1 month ago) by root
Content type:	text/plain
Branch:	MAIN
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			public:
82			// optional, for debugging support
83			GiSTobjid IsA() { return MT_CLASS; }
84
85			int IsOrdered() const { return 1; } // the children of each node are ordered on increasing distances from the parent
86			int MaxLevel() const; // height of the M-tree
87			GiSTlist<MTentry *> RangeSearch(const MTquery& query); // range search
88			MTentry **TopSearch(const TopQuery& query); // generic search algorithm: k-NN search for a TopQuery
89			MTnode ParentNode(MTnode node); // return the parent of node (the caller should delete the object)
90			void BulkLoad(MTentry *data, int n, double padFactor, char name); // bulk-loading algorithm
91			void CollectStats(); // level-stats collecting function: total number of pages, average radius and average covered volume (if applicable)
92			BOOL CheckNode(GiSTpath path, MTentry *e); // debug function: check for node consistency
93
94			// friend methods and functions
95			friend void MTnode::InvalidateEntry(BOOL isNew);
96			friend GiSTlist<GiSTobject *> MTnode::RangeSearch(const MTquery& query);
97			friend MTentry *MTcursor::FetchNode();
98
99			protected:
100			// Required members
101			GiSTnode *CreateNode() const { return new MTnode; }
102			GiSTstore *CreateStore() const { return new MTfile; }
103
104			// Service methods for Bulk Load
105			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
106			void Append(MTnode to, MTnode from); // append the sub-tree of node from to node to
107			private:
108			void AdjKeys(GiSTnode *node); // slightly different from AdjustKeys (necessary to keep track of the distance from the parent)
109			};
110
111			int PickRandom(int from, int to); // pick a determined number of samples in the range [from, to[
112
113			#endif