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 |